# Evolving Robustness--Exploration Trade-off in Online Reinforcement Learning via Quantile Bayesian Risk MDPs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 23 of its 51 references that are in the map.
- First posted on arXiv 23 May 2026.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [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)
- [Why is Posterior Sampling Better than Optimism for Reinforcement Learning?](https://mlsanity.com/paper/1607.00215/) (2016)
- [Online Robust Reinforcement Learning with Model Uncertainty](https://mlsanity.com/paper/2109.14523/) (2021)
- [Robust Reinforcement Learning using Offline Data](https://mlsanity.com/paper/2208.05129/) (2022)
- [Sample Complexity of Robust Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2112.01506/) (2021)
- [Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP](https://mlsanity.com/paper/1901.09311/) (2019)
- [Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coverage](https://mlsanity.com/paper/2305.09659/) (2023)
- [Nearly Minimax Optimal Reinforcement Learning for Discounted MDPs](https://mlsanity.com/paper/2010.00587/) (2020)
- [From Dirichlet to Rubin: Optimistic Exploration in RL without Bonuses](https://mlsanity.com/paper/2205.07704/) (2022)
- [Conservative Exploration in Reinforcement Learning](https://mlsanity.com/paper/2002.03218/) (2020)
- [Online Policy Optimization for Robust MDP](https://mlsanity.com/paper/2209.13841/) (2022)
- [Probabilistic Inference in Reinforcement Learning Done Right](https://mlsanity.com/paper/2311.13294/) (2023)
- [Posterior Sampling for Reinforcement Learning Without Episodes](https://mlsanity.com/paper/1608.02731/) (2016)
- [Context in Public Health for Underserved Communities: A Bayesian Approach to Online Restless Bandits](https://mlsanity.com/paper/2402.04933/) (2024)
- [ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2508.03768/) (2025)
- [Bayesian Risk-Averse Q-Learning with Streaming Observations](https://mlsanity.com/paper/2305.11300/) (2023)
- [Safe and Robust Reinforcement Learning: Principles and Practice](https://mlsanity.com/paper/2403.18539/) (2024)
- [Approximate Bilevel Difference Convex Programming for Bayesian Risk Markov Decision Processes](https://mlsanity.com/paper/2301.11415/) (2023)
- [EUBRL: Epistemic Uncertainty Directed Bayesian Reinforcement Learning](https://mlsanity.com/paper/2512.15405/) (2025)
- [Online Bayesian Risk-Averse Reinforcement Learning](https://mlsanity.com/paper/2509.14077/) (2025)

## Abstract (arXiv)

In online reinforcement learning, data scarcity creates epistemic uncertainty that makes robustness important early in learning, whereas sufficient exploration is needed to learn the true-environment optimal policy. We study this time-varying robustness--exploration trade-off through a quantile Bayesian risk-aware Markov decision process (BR-MDP), in which the quantile level controls how posterior uncertainty enters the Bellman backup. We characterize this control through an asymptotic normality result for the difference between the quantile BR-MDP value and the value in the true environment. The result implies that upper/lower-tail quantiles induce optimism/pessimism towards epistemic uncertainty, and the magnitude of the optimism/pessimism decreases as data accumulate. Building on this characterization, we propose an online Bayesian risk-aware algorithm with an adaptive quantile schedule that emphasizes robustness early and gradually encourages exploration of less-visited state--action pairs. We establish sublinear Bayesian regret bounds with respect to both the true optimal value and the optimal BR-MDP robust value. Numerical experiments demonstrate strong performance in both exploration-demanding and exploration-costly environments.