  We study structured multi-armed bandits, which is the problem of online
decision-making under uncertainty in the presence of structural information. In
this problem, the decision-maker needs to discover the best course of action
despite observing only uncertain rewards over time. The decision-maker is aware
of certain convex structural information regarding the reward distributions;
that is, the decision-maker knows the reward distributions of the arms belong
to a convex compact set. In the presence such structural information, they then
would like to minimize their regret by exploiting this information, where the
regret is its performance difference against a benchmark policy that knows the
best action ahead of time. In the absence of structural information, the
classical upper confidence bound (UCB) and Thomson sampling algorithms are well
known to suffer minimal regret. As recently pointed out, neither algorithms
are, however, capable of exploiting structural information that is commonly
available in practice. We propose a novel learning algorithm that we call
"DUSA" whose regret matches the information-theoretic regret lower bound up to
a constant factor and can handle a wide range of structural information. Our
algorithm DUSA solves a dual counterpart of the regret lower bound at the
empirical reward distribution and follows its suggested play. We show that this
idea leads to the first computationally viable learning policy with asymptotic
minimal regret for various structural information, including well-known
structured bandits such as linear, Lipschitz, and convex bandits, and novel
structured bandits that have not been studied in the literature due to the lack
of a unified and flexible framework.
