Q-learning with Posterior Sampling
Priyank Agrawal, Shipra Agrawal, Azmat Azati · 2025
Read Q-learning with Posterior Sampling by Priyank Agrawal, Shipra Agrawal, Azmat Azati (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-00917.txt.
Introduction
Priyank Agrawal, Shipra Agrawal, and Azmat Azati add posterior sampling to Q-learning, in work from 2025. Posterior sampling explores well in bandit tasks, but proof for full reinforcement learning stayed hard. Dynamic programming and value updates clash with sampling in ways that block clean regret bounds.
Their method keeps Gaussian beliefs over action values and samples from them to explore. In table form episodic tasks, regret grows with horizon, states, actions, and time in a tight form. The bound sits close to the known lower limit for this task class. New proof ideas untangle how sampling joins value backup steps. The team hopes the path extends to richer learning settings later.
Catalog record
| CREATOR | Priyank Agrawal, Shipra Agrawal, Azmat Azati |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 94 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-00917
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Q-learning with Posterior Sampling Priyank Agrawal, Shipra Agrawal, Azmat Azati Abstract Bayesian posterior sampling techniques have demonstrated superior empirical performance in many exploration-exploitation settings. However, their theoretical analysis remains a challenge, especially in complex settings like reinforcement learning. In this paper, we introduce Q-Learning with Posterior Sampling (PSQL), a simple Q-learning-based algorithm that uses Gaussian posteriors on Q-values for exploration, akin to the popular Thompson Sampling algorithm in the multi-armed bandit setting. We show that in the tabular episodic MDP setting, PSQL achieves a regret bound of O ~ ( H 2 S A T ) \tilde{O}(H^{2}\sqrt{SAT}) , closely matching the known lower bound of Ω ( H S A T ) \Omega(H\sqrt{SAT}) . Here, S, A denote the number of states and actions in the underlying Markov Decision Process (MDP), and T = K H T=KH with K K being the number of episodes and H H being the planning horizon. Our work provides several new technical insights into the core challenges in combining posterior sampling with dynamic programming and TD-learning-based RL algorithms, along with novel ideas for resolving those difficulties. We hope this will form a starting point for analyzing this efficient and important algorithmic technique in even more complex RL settings. 1 Introduction In a Reinforcement Learning (RL) problem, an agent interacts sequentially with an unknown environment and uses the observed outcomes to learn an interaction strategy. The underlying mathematical model for RL is a Markov Decision Process (MDP). In the tabular episodic RL setting, there is an underlying MDP with a finite state space {\cal S} , a finite action space {\cal A} and a planning horizon H . On taking an action a in state s at step h , the environment produces a reward and next state from the (unknown) reward model R_{h}(s,a) and transition probability model P_{h}(s,a) of the underlying MDP. Q-learning Watkins and Dayan 1992 is a classic dynamic programming (DP)-based algorithm for RL. The DP equations (aka Bellman equations) provide a recursive expression for the optimal expected reward achievable from any state and action of the MDP, aka the Q -values, in terms of the optimal value achievable in the next state. Specifically, for any given s\in{\cal S},a\in{\cal A},h\in[H] , the Q-value Q_{h}(s,a) is given by: Q_{h}(s,a)=\max_{a\in{\cal A}}R_{h}(s,a)+\sum_{s^{\prime}\in{\cal S}}P_{h}(s,a,s^{\prime})V_{h+1}(s^{\prime}),\text{ with} (1) \textstyle V_{h+1}(s^{\prime})\mathrel{\mathop{\ordinarycolon}}=\max_{a^{\prime}\in{\cal A}}Q_{h+1}(s^{\prime},a^{\prime}). Here, the terminal value V_{H+1}(s) is 0 for all s . The optimal action in state s is then given by the argmax action in the above. In the reinforcement learning setting, where the reward and transition models of the MDP are unknown, the Q -learning algorithm uses the celebrated Temporal Difference (TD) learning idea Sutton 1988 to construct increasingly accurate estimates of Q -values using past observations. The key idea here is to construct an estimate of the right hand side of the Bellman equation, aka target , by bootstrapping the current estimate \widehat{V}_{h+1} for the next step value function. That is, on playing an action a in state s at step h , and observing reward r_{h} and next state s^{\prime} , the target z is typically constructed as: z\mathrel{\mathop{\ordinarycolon}}=r_{h}+\widehat{V}_{h+1}(s^{\prime}) And then the estimate {\widehat{Q}}_{h}(s,a) for Q_{h}(s,a) is updated to fit the Bellman equations using the Q-learning update rule 1 1 1 Or, \widehat{Q}_{h}(s,a)\leftarrow\widehat{Q}_{h}(s,a)+\alpha_{n}(z-\widehat{Q}_{h}(s,a)) where z-\widehat{Q}_{h}(s,a) is called the Temporal Difference (TD). \widehat{Q}_{h}(s,a)\leftarrow(1-\alpha_{n})\widehat{Q}_{h}(s,a)+\alpha_{n}z. (2) Here \alpha_{n} is an important parameter of the Q -learning algorithm, referred to as the learning rate. It is typically a function of the number of previous visits n for the state s and action a . There are several ways to interpret the Q-learning update rule. The traditional frequentist interpretation popularized by Mnih et al. 2015 interprets this update as a gradient descent step for a least squares regression error minimization problem. Another, arguably more insightful, interpretation of Q -learning can be obtained using Bayesian inference theory. Specifically, if we assume a Gaussian prior \textstyle{\cal N}(\widehat{Q}_{h}(s,a),\frac{\sigma^{2}}{n-1}) on the Q -value Q_{h}(s,a) , and a Gaussian likelihood function {\cal N}(Q_{h}(s,a),\sigma^{2}) for the target z , then using Bayes rule, one can derive the Bayesian posterior as the Gaussian distribution \textstyle{\cal N}(\widehat{Q}_{h}(s,a),\frac{\sigma^{2}}{n}),\qquad\qquad\text{ where }\widehat{Q}_{h}(s,a)\leftarrow(1-\alpha_{n})\widehat{Q}_{h}(s,a)+\alpha_{n}z (3) (See Section 3.1 for further details.) Importantly, the Bayesian posterior tracks not just the mean but also the variance or uncertainty in the Q -value estimate. This uncertainty quantification is particularly useful for managing the exploration-exploitation tradeoff for regret minimization in reinforcement learning. Figure 1 : A comparison of PSQL ∗ , UCBQL Jin et al. 2018 ; (Staged) RandQL Tiapkin et al. 2023 , and RLSVI Russo 2019 in a chain MDP environment (for details, and more experiments, see Appendix A ). Intuitively, the state and actions with a small number of past visits (i.e., small n ) have large uncertainty in their current Q -value estimate, and should be explored more. The posterior sampling approaches implement this idea by simply taking a sample from the posterior, which is likely to be closer to the mean (less exploration) for actions with small posterior variance, and away from the mean (more exploration) for those with large variance. Following this intuition, we introduce Q-learning with Posterior Sampling (PSQL) algorithm that maintains a posterior on Q-values for every state and action. Then, to decide an action in any given state, it simply generates a sample from the posterior for each action, and plays the arg max action of the sampled Q -values. Popularized by their success in the multi-armed bandit settings Thompson 1933 ; Chapelle and Li 2011 ; Kaufmann et al. 2012 ; Agrawal and Goyal 2017 , and in deep reinforcement learning regimes ( Osband et al. 2016a ; Fortunato et al. 2017 ; Azizzadenesheli et al. 2018 ; Li et al. 2021b ; Fan and Ming 2021 ; Sasso et al. 2023 ) , the posterior sampling approaches are generally believed to be more efficient in managing the exploration-exploitation tradeoff than their UCB (Upper Confidence Bound) counterparts. Our preliminary experiments (see Figure 1 ) suggest that this is also the case for our Q-learning approach in the tabular RL setting. 2 2 2 For the empirical study reported here, we implement a vanilla version of posterior sampling with Q-learning. The PSQL algorithm presented later modifies the target computation slightly as described later in Section 3 , for the sake of theoretical analysis. However, obtaining provable guarantees for posterior sampling approaches have historically been more challenging. Several previous works (e.g., Li et al. 2021a ; Jin et al. 2018 ) use UCB-based exploration bonuses to design optimistic Q-learning algorithms with near-optimal regret bounds. 3 3 3 The algorithm from Jin et al. 2018 is referred as UCBQL in the text and experiments . For the posterior sampling based approaches however, the first tractable Q -learning based algorithm with provable regret bounds was provided only recently by Tiapkin et al. 2023 for the Staged-RandQL algorithm. However, the Staged-RandQL (and RandQL) algorithm presented in their work deviated from the natural approach of putting a posterior on Q-values, and instead derived a Dirichlet Bayesian posterior on the transition probabilities, which is conceptually closer to some model-based posterior sampling algorithms, e.g., the PSRL algorithm in Agrawal and Jia 2017 . RandQL implements