Dynamic Regret Minimization for Bandits without Prior Knowledge
summary
Shows an algorithm that achieves the optimal dynamic regret bound sqrt(S T) (and the V^{1/3} T^{2/3} regime) without knowing the number of environment changes, building on Auer, Gajane and Ortner (COLT 2019). It schedules multi-scale detection blocks of length about 1/epsilon^2 with probability p_epsilon (shorter but more frequent for large changes, longer but rarer for small changes), uses consecutive sampling and a black-box reduction to any UCB / no-regret base algorithm, and proves the regret guarantees extend to k-armed bandits and broader RL settings.
AI-written summary · about
chapters (12)
- 0:00Introduction and context
- 1:15Bandit problems and challenges
- 4:56Dynamic regret and prior work
- 7:51Proposed algorithm overview
- 10:25Multi-scale detection strategy
- 15:25Algorithm implementation details
- 18:48Regret analysis for single change
- 25:15Handling multiple change points
- 30:36Generalizing to complex problems
- 33:28Tracking optimal policy changes
- 37:14UCB equivalence and summary
- 40:58Future work and Q&A
related talks
01h 15mBridging Stochastic and Adversarial Bandits
01h 01mStochastic Bandits: Foundations and Current Perspectives
01h 09mStochastic Bandits: Foundations and Current Perspectives
01h 21mAdversarial Bandits: Theory and Algorithms
32mRevisiting the Exploration-Exploitation Trade-Off in Bandit Models
01h 17mOnline Reinforcement Learning and Regret
31mLearning to Control Unknown Systems
56mA Tutorial on Reinforcement Learning II