mlsanityData to 7 Oct 2026

From Dirichlet to Rubin: Optimistic Exploration in RL without Bonuses

arXiv 2205.07704 ↗First posted 16 May 2022stat.ML cs.LGcited by 22

Not on the map. Why?

Abstract (arXiv)

We propose the Bayes-UCBVI algorithm for reinforcement learning in tabular, stage-dependent, episodic Markov decision process: a natural extension of the Bayes-UCB algorithm by Kaufmann et al. (2012) for multi-armed bandits. Our method uses the quantile of a Q-value function posterior as upper confidence bound on the optimal Q-value function. For Bayes-UCBVI, we prove a regret bound of order widetildeO(√H3SAT) where H is the length of one episode, S is the number of states, A the number of actions, T the number of episodes, that matches the lower-bound of Omega(√H3SAT) up to poly-log terms in H,S,A,T for a large enough T. To the best of our knowledge, this is the first algorithm that obtains an optimal dependence on the horizon H (and S) without the need for an involved Bernstein-like bonus or noise. Crucial to our analysis is a new fine-grained anti-concentration bound for a weighted Dirichlet sum that can be of independent interest. We then explain how Bayes-UCBVI can be easily extended beyond the tabular setting, exhibiting a strong link between our algorithm and Bayesian bootstrap (Rubin, 1981).

Key facts. Cited by 22 papers in the map (data through 7 Oct 2026). Builds on 29 of its 71 references that are in the map. First posted on arXiv 16 May 2022.

Builds on

29 of 71 references.

References · 29

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  2. 2015Deep Reinforcement Learning with Double Q-learningcited by 1,704
  3. 2019Mastering Atari, Go, Chess and Shogi by Planning with a Learned Modelcited by 1,327
  4. 2018Exploration by Random Network Distillationcited by 966
  5. 2016Deep Exploration via Bootstrapped DQNcited by 518
  6. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  7. 2018Is Q-learning Provably Efficient?cited by 485
  8. 2017Count-Based Exploration with Neural Density Modelscited by 255
  9. 2020Never Give Up: Learning Directed Exploration Strategiescited by 210
  10. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  11. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  12. 2014Learning to Optimize via Information-Directed Samplingcited by 168
17 more
  1. 2017Deep Exploration via Randomized Value Functionscited by 155
  2. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  3. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 104
  4. 2018Efficient Exploration through Bayesian Deep Q-Networkscited by 67
  5. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 65
  6. 2019Worst-Case Regret Bounds for Exploration via Randomized Value Functionscited by 57
  7. 2018Information-Directed Exploration for Deep Reinforcement Learningcited by 52
  8. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 45
  9. 2018Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPscited by 41
  10. 2015Bootstrapped Thompson Sampling and Deep Explorationcited by 40
  11. 2020Logistic Q-Learningcited by 34
  12. 2018DORA The Explorer: Directed Outreaching Reinforcement Action-Selectioncited by 27
  13. 2021Principled Exploration via Optimistic Bootstrapping and Backward Inductioncited by 26
  14. 2018KL-UCB-switch: optimal regret bounds for stochastic bandits from both a distribution-dependent and a distribution-free viewpointscited by 20
  15. 2020Concentration Inequalities for Multinoulli Random Variablescited by 12
  16. 2017Gaussian-Dirichlet Posterior Dominance in Sequential Learningcited by 4
  17. 2021From Optimality to Robustness: Dirichlet Sampling Strategies in Stochastic Banditscited by 4

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 5; 2024: 3; 2025: 6; 2026: 7.

22 papers.

Sort:

By area:

  1. 2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
  2. 2023Posterior Sampling for Deep Reinforcement Learningcited by 16
  3. 2022Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guaranteescited by 12
  4. 2024Q-Star Meets Scalable Posterior Sampling: Bridging Theory and Practice via HyperAgentcited by 6
  5. 2024Provably and Practically Efficient Adversarial Imitation Learning with General Function Approximationcited by 6
  6. 2023A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithmscited by 4
  7. 2023Model-Based Epistemic Variance of Values for Risk-Aware Policy Optimizationcited by 3
  8. 2023Sharp Deviations Bounds for Dirichlet Weighted Sums with Application to analysis of Bayesian algorithmscited by 2
  9. 2025Minimax Optimal Reinforcement Learning with Quasi-Optimismcited by 2
  10. 2025CAE: Repurposing the Critic as an Explorer in Deep Reinforcement Learningcited by 1
  11. 2026Adversarial Imitation Learning with General Function Approximation: Theoretical Analysis and Practical Algorithmscited by 1
  12. 2024MinMaxMin Q-learningcited by 0
10 more
  1. 2025Smart Exploration in Reinforcement Learning using Bounded Uncertainty Modelscited by 0
  2. 2025When a Reinforcement Learning Agent Encounters Unknown Unknownscited by 0
  3. 2025Deep Actor-Critics with Tight Risk Certificatescited by 0
  4. 2025Sharper Perturbed-Kullback-Leibler Exponential Tail Bounds for Beta and Dirichlet Distributionscited by 0
  5. 2026Minimax Optimal Strategy for Delayed Observations in Online Reinforcement Learningcited by 0
  6. 2026A Measure-Theoretic Finite-Sample Theory for Adaptive-Data Fitted Q-Iterationcited by 0
  7. 2026Evolving Robustness--Exploration Trade-off in Online Reinforcement Learning via Quantile Bayesian Risk MDPscited by 0
  8. 2026Quantile of Means: A Bonus-Free Ensemble Method for Minimax Optimal Reinforcement Learningcited by 0
  9. 2026Mathematical methods of reinforcement learningcited by 0
  10. 2026Minimax-Optimality of Posterior Sampling for Reinforcement Learningcited by 0