Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits
We study the linear contextual bandit problem with finite action sets. When the problem dimension is $d$, the time horizon is $T$, and there are $n \leq 2^{d/2}$ candidate actions per time period, we (1) show that the minimax expected regret is $\Omega(\sqrt{dT (\log T) (\log n)})$ 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 $\sqrt{\log T}$ factors from previous analysis, and our information-theoretical lower bound also improves previous results by one $\sqrt{\log T}$ factor, revealing a regret scaling quite different from classical multi-armed bandits in which no logarithmic $T$ 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.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-Armed BanditsSimilar Papers 제목 키워드 기반
Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model
The curse of dimensionality is a widely known issue in reinforcement learning (RL). In the tabular setting where the state space $\mathcal{S}$ and the action space $\mathcal{A}$ are both finite, to obtain a nearly optima…
Q-Learningreinforcement-learningReinforcement Learning (RL)Nesterov Meets Optimism: Rate-Optimal Separable Minimax Optimization
We propose a new first-order optimization algorithm -- AcceleratedGradient-OptimisticGradient (AG-OG) Descent Ascent -- for separable convex-concave minimax optimization. The main idea of our algorithm is to carefully le…
On the Suboptimality of Thompson Sampling in High Dimensions
In this paper we consider Thompson Sampling (TS) for combinatorial semi-bandits. We demonstrate that, perhaps surprisingly, TS is sub-optimal for this problem in the sense that its regret scales exponentially in the ambi…
Thompson SamplingVocal Bursts Intensity PredictionBest of Both Worlds in Online Control: Competitive Ratio and Policy Regret
We consider the fundamental problem of online control of a linear dynamical system from two different viewpoints: regret minimization and competitive analysis. We prove that the optimal competitive policy is well-approxi…
Bandit algorithms to emulate human decision making using probabilistic distortions
Motivated by models of human decision making proposed to explain commonly observed deviations from conventional expected value preferences, we formulate two stochastic multi-armed bandit problems with distorted probabili…
Decision MakingMulti-Armed Bandits