IEEE Transactions on Information Theory · 2023 · 14 citations · 17 references
ComputingComputer ScienceMathematicsAlgorithmsMachine LearningOptimizationConvex OptimizationLinear ProgrammingOptimization TheoryReinforcement LearningReinforcement Learning FoundationsStochastic OptimizationBandit AlgorithmsContextual BanditsMaximax RegretMinimax OptimizationMinimax Search
We study the linear contextual bandit problem with finite action sets. When the problem dimension is <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$d$ </tex-math></inline-formula> , the time horizon is <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$T$ </tex-math></inline-formula> , and there are <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$n \leq 2^{d/2}$ </tex-math></inline-formula> candidate actions per time period, we 1) show that the minimax expected regret is <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\Omega (\sqrt {dT (\log T) (\log n)})$ </tex-math></inline-formula> for every algorithm, and 2) introduce a Variable-Confidence-Level (VCL) SupLinUCB algorithm whose regret matches the lower bound up to iterated logarithmic factors. Our algorithmic result saves two <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\sqrt {\log T}$ </tex-math></inline-formula> factors from previous analysis, and our information-theoretical lower bound also improves previous results by one <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\sqrt {\log T}$ </tex-math></inline-formula> factor, revealing a regret scaling quite different from classical multi-armed bandits in which no logarithmic <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$T$ </tex-math></inline-formula> term is present in minimax regret. Our proof techniques include variable confidence levels and a careful analysis of layer sizes of SupLinUCB on the upper bound side, and delicately constructed adversarial sequences showing the tightness of elliptical potential lemmas on the lower bound side.
17
A contextual-bandit approach to personalized news article recommendation
Lihong Li, Wei Chu, John Langford et al. · 2010 · 2.5K citations · Full text
Asymptotically efficient adaptive allocation rules
Tze-Leung Lai, Herbert Robbins · Advances in Applied Mathematics · 1985 · 2.5K citations