2006 · 74 citations · 9 references
ComputingComputer ScienceMathematicsAlgorithmsDecision TheoryOptimizationGeometric OptimizationOnline AlgorithmsReinforcement LearningReinforcement Learning FoundationsStochastic OptimizationActual Loss AnalysisAdversarial BanditsAdversary ModelBandit AlgorithmsMulti-armed Bandit OptimizationOnline Convex OptimizationOnline Optimization
We consider “online bandit geometric optimization, ” a problem of iterated decision making in a largely unknown and constantly changing environment. The goal is to minimize “regret, ” defined as the difference between the actual loss of an online decision-making procedure and that of the best single decision in hindsight. “Geometric optimization ” refers to a generalization of the well-known multi-armed bandit problem, in which the decision space is some bounded subset of R d, the adversary is restricted to linear loss functions, and regret bounds should depend on the dimensionality d, rather than the total number of possible decisions. “Bandit ” refers to the setting in which the algorithm is only told its loss on each round, rather than the entire loss function. McMahan and Blum [10] presented the best known algorithm in this setting, and proved that its expected additive regret is O(poly(d)T 3/4). We simplify and improve their analysis of this algorithm to obtain regret O(poly(d)T 2/3). We also prove that, for a large class of full-information online optimization problems, the optimal regret against an adaptive adversary is the same as against a non-adaptive adversary. 1
9
The Nonstochastic Multiarmed Bandit Problem
Peter Auer, Nicolò Cesa‐Bianchi, Yoav Freund et al. · SIAM Journal on Computing · 2002 · 2.3K citations
The Weighted Majority Algorithm
N. Littlestone, Manfred K. Warmuth · Information and Computation · 1994 · 2K citations