Nested bandits
In many online decision processes, the optimizing agent is called to choose
between large numbers of alternatives with many inherent similarities; in turn,
these similarities imply closely correlated losses that may confound standard
discrete choice models and bandit algorithms. We study this question in the
context of nested bandits, a class of adversarial multi-armed bandit problems
where the learner seeks to minimize their regret in the presence of a large
number of distinct alternatives with a hierarchy of embedded
(non-combinatorial) similarities. In this setting, optimal algorithms based on
the exponential weights blueprint (like Hedge, EXP3, and their variants) may
incur significant regret because they tend to spend excessive amounts of time
exploring irrelevant alternatives with similar, suboptimal costs. To account
for this, we propose a nested exponential weights (NEW) algorithm that performs
a layered exploration of the learner's set of alternatives based on a nested,
step-by-step selection method. In so doing, we obtain a series of tight bounds
for the learner's regret showing that online learning problems with a high
degree of similarity between alternatives can be resolved efficiently, without
a red bus / blue bus paradox occurring.