# Model-free Posterior Sampling via Learning Rate Randomization

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Oct 2023.

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

- [Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedback](https://mlsanity.com/paper/2405.07637/) (2024)
- [Provably Efficient and Agile Randomized Q-Learning](https://mlsanity.com/paper/2506.24005/) (2025)
- [CAE: Repurposing the Critic as an Explorer in Deep Reinforcement Learning](https://mlsanity.com/paper/2503.18980/) (2025)
- [Q-learning with Posterior Sampling](https://mlsanity.com/paper/2506.00917/) (2025)
- [Knowledge Boundary Discovery for Large Language Models](https://mlsanity.com/paper/2603.21022/) (2026)
- [ReversedQ: Opportunities for Faster Q-Learning in Episodic Online Reinforcement Learning](https://mlsanity.com/paper/2605.20592/) (2026)

## Abstract (arXiv)

In this paper, we introduce Randomized Q-learning (RandQL), a novel randomized model-free algorithm for regret minimization in episodic Markov Decision Processes (MDPs). To the best of our knowledge, RandQL is the first tractable model-free posterior sampling-based algorithm. We analyze the performance of RandQL in both tabular and non-tabular metric space settings. In tabular MDPs, RandQL achieves a regret bound of order widetildeO(√H5SAT), where H is the planning horizon, S is the number of states, A is the number of actions, and T is the number of episodes. For a metric state-action space, RandQL enjoys a regret bound of order widetildeO(H5/2 T(dz+1)/(dz+2)), where dz denotes the zooming dimension. Notably, RandQL achieves optimistic exploration without using bonuses, relying instead on a novel idea of learning rate randomization. Our empirical study shows that RandQL outperforms existing approaches on baseline exploration environments.