# Reinforcement Learning for Markovian Bandits: Is Posterior Sampling more Scalable than Optimism?

arXiv: https://arxiv.org/abs/2106.08771 · HTML: https://mlsanity.com/paper/2106.08771/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 58 references that are in the map.
- First posted on arXiv 16 Jun 2021.

## Builds on (most cited first, 22 of 22)

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Why is Posterior Sampling Better than Optimism for Reinforcement Learning?](https://mlsanity.com/paper/1607.00215/) (2016)
- [Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning](https://mlsanity.com/paper/1802.04020/) (2018)
- [Learning Unknown Markov Decision Processes: A Thompson Sampling Approach](https://mlsanity.com/paper/1709.04570/) (2017)
- [Randomized Exploration for Reinforcement Learning with General Value Function Approximation](https://mlsanity.com/paper/2106.07841/) (2021)
- [Whittle index based Q-learning for restless bandits with average reward](https://mlsanity.com/paper/2004.14427/) (2020)
- [Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function](https://mlsanity.com/paper/1906.05110/) (2019)
- [Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs](https://mlsanity.com/paper/1803.01626/) (2018)
- [Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs](https://mlsanity.com/paper/2010.00587/) (2020)
- [Near-optimal Reinforcement Learning in Factored MDPs](https://mlsanity.com/paper/1403.3741/) (2014)
- [On Lower Bounds for Regret in Reinforcement Learning](https://mlsanity.com/paper/1608.02732/) (2016)
- [Regret Bounds for Thompson Sampling in Episodic Restless Bandit Problems](https://mlsanity.com/paper/1905.12673/) (2019)
- [Posterior sampling for reinforcement learning: worst-case regret bounds](https://mlsanity.com/paper/1705.07041/) (2017)
- [Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits](https://mlsanity.com/paper/2011.02664/) (2020)
- [Tightening Exploration in Upper Confidence Reinforcement Learning](https://mlsanity.com/paper/2004.09656/) (2020)
- [Improved Worst-Case Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/2010.12163/) (2020)
- [Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes](https://mlsanity.com/paper/2006.13405/) (2020)
- [Concentration Inequalities for Multinoulli Random Variables](https://mlsanity.com/paper/2001.11595/) (2020)

## Built on by (most cited first, 1 of 1)

- [On learning Whittle index policy for restless bandits with scalable regret](https://mlsanity.com/paper/2202.03463/) (2022)

## 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.