# From Dirichlet to Rubin: Optimistic Exploration in RL without Bonuses

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

## Key facts

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

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

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model](https://mlsanity.com/paper/1911.08265/) (2019)
- [Exploration by Random Network Distillation](https://mlsanity.com/paper/1810.12894/) (2018)
- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [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)
- [Count-Based Exploration with Neural Density Models](https://mlsanity.com/paper/1703.01310/) (2017)
- [Never Give Up: Learning Directed Exploration Strategies](https://mlsanity.com/paper/2002.06038/) (2020)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [Deep Exploration via Randomized Value Functions](https://mlsanity.com/paper/1703.07608/) (2017)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Efficient Exploration through Bayesian Deep Q-Networks](https://mlsanity.com/paper/1802.04412/) (2018)
- [Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning](https://mlsanity.com/paper/1802.04020/) (2018)
- [Worst-Case Regret Bounds for Exploration via Randomized Value Functions](https://mlsanity.com/paper/1906.02870/) (2019)
- [Information-Directed Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/1812.07544/) (2018)
- [UCB Momentum Q-learning: Correcting the bias without forgetting](https://mlsanity.com/paper/2103.01312/) (2021)
- [Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs](https://mlsanity.com/paper/1803.01626/) (2018)
- [Bootstrapped Thompson Sampling and Deep Exploration](https://mlsanity.com/paper/1507.00300/) (2015)
- [Logistic Q-Learning](https://mlsanity.com/paper/2010.11151/) (2020)
- [DORA The Explorer: Directed Outreaching Reinforcement Action-Selection](https://mlsanity.com/paper/1804.04012/) (2018)
- [Principled Exploration via Optimistic Bootstrapping and Backward Induction](https://mlsanity.com/paper/2105.06022/) (2021)
- [KL-UCB-switch: optimal regret bounds for stochastic bandits from both a distribution-dependent and a distribution-free viewpoints](https://mlsanity.com/paper/1805.05071/) (2018)
- [Concentration Inequalities for Multinoulli Random Variables](https://mlsanity.com/paper/2001.11595/) (2020)
- [Gaussian-Dirichlet Posterior Dominance in Sequential Learning](https://mlsanity.com/paper/1702.04126/) (2017)
- [From Optimality to Robustness: Dirichlet Sampling Strategies in Stochastic Bandits](https://mlsanity.com/paper/2111.09724/) (2021)

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

- [Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo](https://mlsanity.com/paper/2305.18246/) (2023)
- [Posterior Sampling for Deep Reinforcement Learning](https://mlsanity.com/paper/2305.00477/) (2023)
- [Optimistic Posterior Sampling for Reinforcement Learning with Few Samples and Tight Guarantees](https://mlsanity.com/paper/2209.14414/) (2022)
- [Q-Star Meets Scalable Posterior Sampling: Bridging Theory and Practice via HyperAgent](https://mlsanity.com/paper/2402.10228/) (2024)
- [Provably and Practically Efficient Adversarial Imitation Learning with General Function Approximation](https://mlsanity.com/paper/2411.00610/) (2024)
- [A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithms](https://mlsanity.com/paper/2303.06058/) (2023)
- [Model-Based Epistemic Variance of Values for Risk-Aware Policy Optimization](https://mlsanity.com/paper/2312.04386/) (2023)
- [Sharp Deviations Bounds for Dirichlet Weighted Sums with Application to analysis of Bayesian algorithms](https://mlsanity.com/paper/2304.03056/) (2023)
- [Minimax Optimal Reinforcement Learning with Quasi-Optimism](https://mlsanity.com/paper/2503.00810/) (2025)
- [CAE: Repurposing the Critic as an Explorer in Deep Reinforcement Learning](https://mlsanity.com/paper/2503.18980/) (2025)
- [Adversarial Imitation Learning with General Function Approximation: Theoretical Analysis and Practical Algorithms](https://mlsanity.com/paper/2605.01778/) (2026)
- [MinMaxMin Q-learning](https://mlsanity.com/paper/2402.05951/) (2024)
- [Smart Exploration in Reinforcement Learning using Bounded Uncertainty Models](https://mlsanity.com/paper/2504.05978/) (2025)
- [When a Reinforcement Learning Agent Encounters Unknown Unknowns](https://mlsanity.com/paper/2505.13188/) (2025)
- [Deep Actor-Critics with Tight Risk Certificates](https://mlsanity.com/paper/2505.19682/) (2025)
- [Sharper Perturbed-Kullback-Leibler Exponential Tail Bounds for Beta and Dirichlet Distributions](https://mlsanity.com/paper/2508.07991/) (2025)
- [Minimax Optimal Strategy for Delayed Observations in Online Reinforcement Learning](https://mlsanity.com/paper/2603.03480/) (2026)
- [Fitted Q-Iteration with Continuous Actions and Adaptive Data: Smoothed Coverage and Minimax Rates](https://mlsanity.com/paper/2605.05791/) (2026)
- [Evolving Robustness--Exploration Trade-off in Online Reinforcement Learning via Quantile Bayesian Risk MDPs](https://mlsanity.com/paper/2605.24345/) (2026)
- [Quantile of Means: A Bonus-Free Ensemble Method for Minimax Optimal Reinforcement Learning](https://mlsanity.com/paper/2606.20107/) (2026)
- [Mathematical methods of reinforcement learning](https://mlsanity.com/paper/2607.06935/) (2026)
- [Minimax-Optimality of Posterior Sampling for Reinforcement Learning](https://mlsanity.com/paper/2609.33246/) (2026)

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