Reinforcement Learning for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?
Not on the map. Why?
Abstract (arXiv)
We study learning algorithms for the classical Markovian bandit problem with discount. We explain how to adapt PSRL [24] and UCRL2 [2] to exploit the problem structure. These variants are called MB-PSRL and MB-UCRL2. While the regret bound and runtime of vanilla implementations of PSRL and UCRL2 are exponential in the number of bandits, we show that the episodic regret of MB-PSRL and MB-UCRL2 is tildeO(S√nK) where K is the number of episodes, n is the number of bandits and S is the number of states of each bandit (the exact bound in S, n and K is given in the paper). Up to a factor √ S, this matches the lower bound of Omega(√SnK) that we also derive in the paper. MB-PSRL is also computationally efficient: its runtime is linear in the number of bandits. We further show that this linear runtime cannot be achieved by adapting classical non-Bayesian algorithms such as UCRL2 or UCBVI to Markovian bandit problems. Finally, we perform numerical experiments that confirm that MB-PSRL outperforms other existing algorithms in practice, both in terms of regret and of computation time.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 22 of its 58 references that are in the map. First posted on arXiv 16 Jun 2021.
Builds on
22 of 58 references.
References · 22
- 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
- 2018Is Q-learning Provably Efficient?cited by 485
- 2017A Tutorial on Thompson Samplingcited by 420
- 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
- 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
- 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 116
- 2017Learning Unknown Markov Decision Processes: A Thompson Sampling Approachcited by 65
- 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
- 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
- 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 43
- 2020Whittle index based Q-learning for restless bandits with average rewardcited by 43
- 2020Nearly Minimax Optimal Reinforcement Learning for Discounted MDPscited by 42
10 more
- 2014Near-optimal Reinforcement Learning in Factored MDPscited by 41
- 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 41
- 2016On Lower Bounds for Regret in Reinforcement Learningcited by 39
- 2019Regret Bounds for Thompson Sampling in Episodic Restless Bandit Problemscited by 34
- 2017Posterior sampling for reinforcement learning: worst-case regret boundscited by 28
- 2020Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Banditscited by 26
- 2020Tightening Exploration in Upper Confidence Reinforcement Learningcited by 24
- 2020Improved Worst-Case Regret Bounds for Randomized Least-Squares Value Iterationcited by 19
- 2020Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processescited by 13
- 2020Concentration Inequalities for Multinoulli Random Variablescited by 12
Built on by
Citing papers per year: 2022: 1.
1 paper.