Q-learning with Posterior Sampling
Authors: Priyank Agrawal
Shipra Agrawal
Azmat Azati
Venue: ICLR 2026 Poster (2026)
Keywords: Reinforcement Learning Theory
Regret Analysis
Posterior Sampling
Q-learning
Primary area: reinforcement learning
TL;DR: Near optimal regret bounds for Q-learning with posterior sampling algorithm in a tabular episodic RL setting

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 $\tilde O(H^2\sqrt{SAT})$, closely matching the known lower bound of $\Omega(H\sqrt{SAT})$. Here, S, A denote the number of states and actions in the underlying Markov Decision Process (MDP), and $T=KH$ with $K$ being the number of episodes and $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.

Published as a conference paper at ICLR 2026
Q --EAARNING WITH POSTERIOR SAMPLING
Priyank Agrawal & Shipra Agrawal
Azmat Azati BNP Paribas
Department of Industrial Engineering and Operations Research Columbia University
(aa5288 ) @ecolumbiii edu
(pa2608, sa3305 (eo corolumbiaa edu
ABSTRACT
Bayesian posterior sampling techniques have demonstrated superior empirical performance in many apploration-exploiaattii settings. However, their theoretical analysis remains a challenge, especially in complex settings like reinforcement learning. In this paper, introduce Q-Learning with Posterior Sampling (PSQL), a simple Q-lcarning-baet baased algorithm that uses Gaussian posteriors on Q-values for exploration, akin 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 Ó (SAT, closely matching the known lower bound Q(H AAT). Here, S, A denote the number of states and actions in the underlying Markov Decision Process (MDP), and T K H with K being the number of episodes and 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.
INTRODUCTION
In an online Reinforcement Learning (RL) problem, an agent interacts sequentially with an unknown environment and uses the observed outcomes learn interaction strategy. The underlying mathematical model for RL is a Markov Decision Process (MDP). In the tabular episodic setting, the MDP has finite state space S, finite action space A and planning horizon H. On taking an action a in state at step h, the environment produces a reward and next state from the (unknown) reward model (s, a) and transition probability model Pa. (s, a) of the underlying MDP.
Q-learning WWtkinns& & Dayan 1992) is a classic dynamic programming (DP)-based algorithm for RL. The DP equations (aka Bellman equations) provide 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 E S.a A, h [H), the Q-value Qi (s, a) is given by:
Qn(s,a) = max RA a) + Σ Pa S'VVn+1(s'),, with aEA
S'ES
Vnt+(1') == max Q1+1(s': (s',a'),
with (*+ = 0, vs. The optimal action in state s is then given by the argmax action in the above.
When the reward and transition models of the MDP are unknown, the Q-learnig 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 construct estimate of the right hand side of the Bellman equation, aka target, by bootstrapping the current estimate V/+ for the next step value function. That is, on playing an action a in state s at step h, and observing reward Th and next state s', the target is typically constructed
Th Vs+1(s').
work done as graduate student Columbia

---

Published as a conference paper at ICLR 2026
And the estimate (s, a) for Qn a) is updated to fit the Bellman equations using the Q-learning update rule
Qn(s, a) + (1 (1- (s.,)a) + an
(2)
Here On is an important parameter of the Q-learning algorithm, referred to as the learning rate. is typically function of the number of previous visits n for the state and action
There are several ways to interpret the Q-learning update rule. The traditional frequentist interpretation gradient descent step for least squares
popularized by Mnih et al. (2015) interprets this update regression error minimization problem. We propose a more insightful interpretation of Q-learning obtained using Bayesian inference theory (details in Section 3.T.. Specifically, if assume Gaussian prior
N(Qu(s.a), nn)
on the Q-value Qu (s, a). and a Gaussian likelihood function WiQn (s, a), x²) for the target 2, then using Bayes rule, one can derive the Bayesian posterior as the Gaussian distribution
(s) )
where Qn (1 aa)))((sss o.,
Importantly, the Bayesian posterior tracks not just the mean but also the variance or uncertainty in the Q-value estimate. Intuitively, the state and actions with small number of past visits (i.e., small n) have large uncertainty their current Q-value estimate, and should be explored more. The posterior sampling approaches implement this idea by simply taking sample from the posterior, which 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. This uncertainty quantification useful for managing the exploration-exploiaaiio exploitation tradeoff for regret minimization. The exploration methodology distinct from algorithms that use additive bonuses or randomized perturbations in the estimates.
Following this intuition, we introduce Q-learning with Posterior Sampling (PSQL) algorithm that main- tains a posterior on Q-values for every state and ac- tion. Then, to decide an action in any given state, simply generates a sample from the posterior for each action, and plays the arg action of the sampled Q-values.
5000
Sagae-Banddg
Cumulative regret
2000
Popularized by their success in the multi-armed ban- dit settings (Thompson 1933 Chapelle & Li 2011
2000
Kaufmann al.) 2012 Agrawal & Goyal (017).
and in deep reinforcement learning regimes (Osband
30000
Fpisodes
et al.
2016a
Fortunato al.
2017 Azizzadezzzeeeeehhell
2018 Li et al. 2021b] Fan & Mingl [202 Sasso at
Figure 1: Performance comparison of PSQL*(( heuristic derived from PSQL),
et al.
2023). the posterior sampling approaches are
generally believed to be more efficient in managing the exploration-ees -eooattionneplliiaationn tradeoff than their UCB (Upper Confidence Bound) counterparts. Our pre- liminary experiments (see Figure I suggest that this is also the case for Q-learning approach in the tabular RL setting. However, obtaining provable guarantees for posterior sampling approaches have historically been more challenging.
UCBQL (Jin et al.] 2018); Staged- RandQL/Tiapp
et al. 2023). and
RLSVI (Russo] (019) in a chain MDP
environment (for details, and more experi-
ments, see Appendix A)
Several previous works (e.g.. Li et al. 10)21a): Jin et al. (2018) use UCB-based exploration bonuses to design optimistic Q-learning algorithms with optrmml regret bounds For the posterior sampling based approaches however, the first tractable
1Or, Q (s, (s, a) +a (2 Q 4, a)) where = Q (s. a) is called the Temporal Difference (TD). For the empirical study reported here, implement vanilla version of posterior sampling with Q-learning. The PSQL algorithm presented later modifies the target computation as described later in Section 3 for the sake of theoretical analysis.
'The algorithm from Jin al. 2018 is referred UCBQL in the and experiments
2

---

Published as a conference paper at ICLR 2026
Q-learning based algorithm with provable regret bounds was provided only recently by Tiapkin et al. (2023) for the
algorithm. However, the Staged-RandQL (and RandQL) algorithm presented in their work deviated from the natural approach of putting 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 & Jia (2017). RandQL implements sampling from the implied distribution on Q-estimates in a more efficient way via learning rate randomization, so that it qualifies as a model-free algorithm.
Another closely related approach with provable regret bounds is the RLSVI (Randomized Least Squared Value Iteration) algorithm by Osband et al.) (2016b; 2019); Russo (2019); Zanette al.) (2020); Agrawal et al. (202T); Xiong et al. (2022). The RLSVI algorithm is an approximate value iteration approach that can be interpreted as maintaining "empirical posteriors" over the value functions by injecting noise. However, in the tabular setting considered here, RLSVI reduces to model-based algorithm. (See Section 2.1 for further comparisons.) There are several other model- based posterior sampling algorithms in the literature with near optimal regret bounds (Osband et al.
2013. Osband & Van Roy [017]] Ouyang et al. 2017 Agrawal & Jia 2022 Agarwal & Zhang 2022
Tiapkin et al. (022). Model-based algorithms directly estimate the reward and/or transition model. instead of the implied optimal value functions, or policy parameters. In many settings, model- based algorithms can be more sample efficient. But, model-free approaches like Q-learning have gained popularity in practice because of their simplicity and flexibility, and underlie most successful modern deep RL algorithms (c.g.. D.N Mnih et al. (2013), DDQN van Hasselt al. (2015). A3C Mnih et al.) (2016)). Provable regret bounds for a simple posterior sampling based Q-learning algorithm like PSQL, therefore, still remains problem of significant interest.
Our contributions are summarized as follows.
We propose the Q-learning with Posterior Sampling (PSQL) algorithm that is the first Q- learning algorithm with natural and efficient exploration provided by the Bayesian posterior sampling approach. Our preliminary experiments demonstrate promising empirical perfor- mance of this simple algorithm compared to contemporary approaches. (See Section 3 for algorithm design and Appendix for experiments.)
We provide novel derivation of Q-learning as a solution to Bayesian inference problem with a regularized Evidence Lower Bound (ELBO) objective. Besides forming the basis of our PSQL algorithm design, this derivation provides a more insightful interpretation of the learning rates introduced in some previous works on Q-learming (c.g.. .c.g...jin et al. 2018)) to obtain provable regret bounds. (See Section 3.1
We prove a near-optimal regret bound of 0(12 VSAT) for PSQL which closely match the known lower bound of S2 C(HvSA7) (Jin et al. 2018 ). Our result improves the regret bounds available for the closely related approach of RLSVI (Russo 2019) and matches those recently derived by Tiapkin et al.] (2023) for more complex posterior sampling based
algorithm Haaged-RandLL. (See Section 2
Our regret analysis reveals several key difficulties in combining posterior sampling with DP and TD-Icarning-boe bbased algorithms due to error accumulation in the bootstrapped target; along with novel ideas for overcoming these challenges. (See Section 4.1
2 OUR SETTING AND MAIN RESULT
In the online reinforcement learning setting, the algorithm interacts with environment in K sequential episodes, each containing H steps. At step h 1,..., H of each episode k. the algorithm observes the current state kk,b, takes an action 4xeh and observes reward rk. and the next state $k,++1-
The reward and next state are generated by the environment according fixed underlying MDP AS R, P), so that Pr(Ss,A-1 = s'|sA,A 8, 9RAA a) Pa,s, a. 8'). E((x,A|SK.A = A = a|= = (s, a). However, the reward functions and the transition probability distributions Rn, Ph, h = 1...., H are apriori unknown to the algorithm. The goal is to minimize total regret compared to the optimal value given by the dynamic programming equation (I.. Specifically, let T& denote the policy used by the algorithm in episode k. so that 0k.h T& (sk,h). We aim to bound regret, defined
Reg(K) K) Σk (s1,)) A (SK,1))
3

---

Published as a conference paper at ICLR 2026
for any set of starting states $4,1, k I....,K.
Since the algorithm can only observe the environment's 's response at a visited state and action, a main challenge in this problem is managing the exploration-exxpootaaiin tradcoff. This refers to the dilemma between picking actions that are most likely to be optimal according to the observations made so far, versus picking actions for that allow visiting less-explored states and actions. The two main approaches for managing apploaatio-eexploitatiii tradeoffs are the optimistic approaches based on UCB and posterior sampling approaches (aka Thompson Sampling in multi-armed bandit settings).
In this paper, we present Q-learning algorithm with posterior sampling (PSQL. that achieves the following regret bound. Here Ö(-) hides absolute constants and logarithmic factors.
Theorem 1 (Informal), The cumulative regret of our PSQL (Algorithm) 7 in K episodes with horizon H. is bounded as Reg(K)) S Ô [122 (H'VSAT) where T K H.
2.1
RELATED WORKS
Algorithm
Regret D(HLa/SAT
Comments
UCB
UCBQL JJin et
2018
Q-learning with UCB
SaanlySettlld-Advaataa (Li et al. 2021a
Ó(HYSAT)
Q-learning with UCB
Posterior sampl.
Conditional Posterior Sampling DDan et al.
2021
Ö(HSAVT)
computationally intractable approximate value itcration approximate value iteration
RLSVT RRusso, 2019
SHAS
C-RLSVI (Ag Agrawal al. 2021
((HT
Staged RandQL Tiapkin et al.
2023
V(H*VSAT))
randomized learning rates
PSQL this work
VSAT)
Gaussian posteriors on Q-values
Lower bound
Jin al.
2018
Q SAA)
Table 1: Comparison of our regret bound to related works ( Dann et al. 22021) 1 is in function approximation setting).
Our work falls under the umbrella of online episodic reinforcement learning on regret minimization in tabular setting. In the category the Upper Confidence Bound (UCB)-based, algorithms, there is a huge body of research both on model-basee
(Bartlett & Tewari 2012 Azar et al. 2017 Fruit et al.
2018. Zanette Brunskill 2019 Zhang et al.] 20200 Boone & Zhang 2024), and model free (in
et al. 2018. Bai et al. [2099] Ménard et al.] 2021; Zhang & Xie 2023
Agrawal & Agrawal 2024
algorithms. In facfact, Jin et al. (2088) were the first to provide a near-optimal worst-case regret bound
of ((VH' subsequently improved to Ó(H SAT) by Zhang et al.
2020 Li et al. a021aa)
Motivated by the superior empirical performance of Bayesian posterior sampling approaches com-
pared to their UCB counterparts (Chapelle & Li 2011 Kaufmann et al. 2012] Osband et al.] 2013
Osband & Van Roy 2017 Osband et al. | (019) there have been several attempts at deriving provable regret bounds for these approaches in the episodic RL setting. Among model-based approaches, near optimal regret bounds have been established for approaches that use (typically Dirichlet) posteriors
on transition models (Ouyang et al., 2017 Agrawal & Jia 2017] Tiapkin et al. (0022). There have been relatively limited studies on model-free, sample-efhciiet and computationalyy efficient Bayesian algorithms. Dann et al. (2021) proposed one such framework but is computationally intractable. Our work aims to fill this gap.
A popular approach closely related to posterior sampling is Randomized Least Square Value It- eration (RLSVI) (Osband et al. 2016b 2019 Russo 2019 Zanette et al. 2020) and RLSVI-like approaches (Agrawal et al. 2021 Xiong et al. 2022 Ishfaq et al. 2021 2023 2024p. In RLSVI, the exploration carried out by injecting randomized uncorrelated noise to the reward samples, followed by re-fitting of Q-function estimate by solving least squares problem all the past data, incurring heavy computation and storage costs. This process has been interpreted as forming an approximate posterior distribution over value functions. RLSVI too enjoys "superior-than UCB" empirical performance. In contrast to Q-larnning (or TD-learning approaches in general) these ap- proaches do not bootstrap on the older estimates and hence their techniques not broadly applicable
4

---

Published as a conference paper at ICLR 2026
in our analysis. However, its worst-case regret bounds (Russo 2019) remain suboptimal (see Table in their dependence on the size of the state space.
algorithms that model-free, tractable and enjoy O Q(H'VSAA regret by randomizing the learning rates of the Q- learning update rule. Their algorithmic design is based on Dirichlet posteriors on transition models and efficient implementation of the implied distribution randomization. Our algorithm is much simpler with far lesser randomized sampling steps and in our preliminary experiments (see Figure T
More recently, Tiapkin et al. (2023) proposed (RandQL and
Q-value estimates via learning rate
and Section A) our PSQL approach with simple Gaussian based posteriors shows better/comparable performance compared to these algorithms.
In Table | we provide detailed comparison of our results with the above-mentioned related work on
posterior sampling algorithms for RL.
3 ALGORITHM DESIGN
We first present Bayesian posterior based derivation of the Q-learning update rule, which forms the basis for our algorithm design.
3.1 POSTERIOR DERIVATION
An insightful interpretation of the Q-learning update rule can obtained using Bayesian inference. Let 0 denote the Bayesian parameter that we are inferring, which in our case is the quantity Qn a). Given a prior p on log likelihood function E(O,-) +), and a sample 2, the Bayesian posterior q is given by the Bayes rule:
(0) x p(0) exp(E((,,
(5)
which can also be derived as an optimal solution of the following optimization problem (see Chapter 10 in Bishop Nasrabadi (2006), whose objective is commonly referred to as Evidence Lower Bound (ELBO):
max Egg - [ =)] K(gllp))
(6)
where KL(-II-) - So (() log( )(8)) denotes KL-divergence function. is well known that when p(-)
is Gaussian, say A (T,, ) and the likelihood given 0 is Gaussian (0, a²), then the posterior g(-) is given by the Gaussian distribution
Ni, d')), with πt a1-a,, an
with a, n learning update rule (2) with learning rate on, 1.
1. Therefore, substituting 0 as Qn and ji as Qn (s. a). the above yields the Q-learning
caveat is that the above assumes to be an unbiased sample from the target distribution, whereas in Q-learnnng, is biased due to bootstrapping. In recent work. Jin et al. (2018) observed that in order to account for this bias and obtain theoretical guarantees for Q-learning, the learning rate needs to also provide meaningful interpretation be adjusted to a, #+1. In fact, Bayesian inference
of this modified learning rate proposed in Jin et al. (2018). Consider the following "regularized"
Bayesian inference problem (Khan & Rue 2023) which adds an entropy term to the ELBO objective in 6
max Eg [0(0 0, 2)] - (L(())p) + X, H(q))
(8)
where Hg)) denotes the entropy of the posterior. We show in Lemma B.I (refer Appendix B that for the choice of X,, when the prior p(0) is Gaussian A/ - and the likelihood of given is Gaussian N(, ). then the posterior q(-) (-) is given by the Gaussian distribution in with the H+1 as suggested in Jin et al. (0188). same learning rate On H-n
Substituting as Qn(s. a) and f has Qn, a) in (8) we derive that given Gaussian prior (V a), ش over Qn (s, a). Gaussian likelihood (acihhoodd(((((( (sQ)ns,a), Ø4T on target the following posterior maximizes the regularized ELBO objective:
N((Qu(s, a), =² where
@n(5,a) (1 (.-))@@@(s0 anz,
5

---

Published as a conference paper at ICLR 2026
and is the number of samples for s, observed so far. where 0%1, H-
#+1
The entropy regularization term of (8) introduces extra uncertainty in the posterior. Intuitively, this makes sense for Q-learning as the target 2 is bootstrapped on previous interactions and likely has additional bias. The weight A. of this entropy term decreases as the number of samples increases and the bootstrapped target is expected to have lower bias. This derivation may of independent interest as it provides an intuitive explanation of the modified learning rate schedule proposed (H+n H+1
as compared to 1)) in Jin et al. (2018), where was motivated mainly by the mechanics of regret analysis. The above posterior derivation forms the basis of our algorithm design presented next.
3.2 ALGORITHM DETAILS
detailed pscudo-code of our PSQL algorithm is provided as Algorithm 12 uses the current Bayesian posterior to generate samples of Q- values the current state and all actions, and plays the arg max action. Specifically, at a given episode k, let 8h be the current state observed in the beginning of the episode and for action a, let (Sh, a) be the number of visits of state 8n and action before this episode. Let Qn (8h, a) be the current estimate of the posterior mean, and
(n)) x+1 64 H m+1
a²
(10)
Then, the algorithm samples for each a,
(nh, a) ~ N ( a), a (N (s),
and plays the arg max action on := arg max, Qn a).
The algorithm then observes a reward rh and the next state 81+1, computes a target z, and updates the posterior mean estimate using the Q-learning update rule. A natural setting of the target would be
Th max,' Q++1 (3h+1, a'), which we refer to the "vanilla version" or PSQL However, due to unresolvable difficulties in regret analysis discussed later Section the PSQL algorithm computes the target in slightly optimistic manner (r,, + V 1++(s)) (s)) as we describe later in this section. Our experiments (Appendix[A) show that although this modification does impact performance, PSQL still remains significantly superior to its UCB counterpart.
Algorithm Q-learning with Posterior Sampling (PSQL)
1: Initialize: Q (s, a) V O, Qn(s, a) Vi((s) H, Nn, a) = 0 a, h. 1,2,.... do
2: for episodes
3: Observe $1.
4: for step h = 1,2, ... H do
5: Sample Qn (sh, a) ~ ()) (N a)))), for all a E A.
6:
Play == arg max as), Observe Th and sp+1-
7:
8:
= + Terssrructaargee (h, Th, 8h+1, Q N1+1)- n = Na(sn, an) +- Nn(sh, , an) + 1, On == #+1
9:
H4n
10:
(sn, 5- (1 ar ) (8h, an) + Un
end for
12: end for
Specifically, given reward 7/ = r' and next state $h+1 = 8', a value function estimate V (s') is computed as the maximum of J samples from the posterior on Quti(s', a), with à being the arg max action of posterior mean standard deviation. That is, let
arg max Qn+i(s',an a) (NN+11 a)), and V (+1(s') max V4 JEJ
with J = J(5) = (og(SAT/6) Iog(4/(4-Pi))
= (--1)
8.
(11)
Observe that the above procedure computes V V (s') that is more optimistic than single sample
maximum (i.e., "vanilla version" max,/ Qn d')). However, the optimism is limited only to the

---

Published as a conference paper at ICLR 2026
Algorithm 2 consttructtarrgeetd... Q.
Return r, if +
Set arg max, Q(s', a) (NV(s, a)). Set J == (o) as in I 1 Take maximum of the J samples from the posterior of target VA+1* */
Sample Vi ~N (Q(s', ,),, (N((s( ( jor E [J(6), a A.
V(s) t max, V
Return Vs').
target computation not to the main decision decision-making in Line 6, marking an important departure from UCB based optimism (e.g., Jin et al. (018)). Multiple sampling from the posteriors is common technique considered in the past works Tiapkin et al.) [002]] Agrawal & Jia 2017 Agrawal et al. 2017) aid analysis. Finally, the algorithm uses the computed target Th (8/41) to
update the posterior mean via the Q-learning update rule, with an H+n
#+1.
(x) + (1 an) a) az.
Let n (s, a). then Algorithm Iimples (a = I1-=1 (1 - a²) and a² = a; a,)).
@k,n(s,a) a Σ a (Te.n + - VR, (1khh
(12)
4 REGRET ANALYSIS
We prove the following regret bound for PSQL.
Theorem 2. The cumulative regret of PSQL (Algorithm 72 in K episodes satisfies
Reg(K) (K) == < k= (sk,1) - V/" (sL.1) < O ( (HRSAAT))
with probability at least where X = log(JSAT/8) and T KH.
4.1 CHALLENGES AND TECHNIQUES.
Most of the unique challenges for the theoretical analysis of Q-learning with posterior sampling associated with the bootstrapped nature TD-Icanning itself. As shown (12), mean estimate at the given step h depends at + 1 of the past estimates propagate to the estimate at step h. In model-based methods(e.g.. Azar al. (2017): Osband & Van Roy (2017 7 Zanette et al. (2020) such issues are non-existent they recalculate their estimates from scratch at each time step.
weighted average of the past next-step h + estimates, causing the errors
Optimism dies down under recursion. One difficulty in analyzing Bayesian posterior sampling algorithms is the absence of high probability optimism (the property that the estimates upper bound the true parameters). Observe that the regret of an algorithm in any episode & can be decomposed as:
V (SK,1) V (SK,1) (Vi (sk.1) QR, (S 1, as.1)) + 1 Ox,1) V (sk,1)). (13)
Optimism enror
Estimation error
In algorithms like UCBQL (Jin al., 2018). there is no optimism error since the UCB estimate is high-confidence upper bound on the optimal value function. Prior posterior sampling ap- proaches (Agrawal Goyal| 20122, 2017: Russo 2019 Agrawal al., 202T) were able to bound optimism error by proving constant probability optimism, and then boosting to high probability by a statistical argument. However, due to the recursive nature of Q-learning their techniques do not directly apply.
To see this, suppose that we have a constant probability p of optimism of posteriors on value functions in state H. The optimism of stage H - value requires optimism of stage H value; leading to p² probability of optimism in stage H 1. Continuing this way, we get an exponentially small probability of optimism for stage 1.
7

---

Published as a conference paper at ICLR 2026
Multiple sampling from the posteriors only partially helps. To get around the issues with constant probability optimism, many posterior sampling algorithms (e.g., bondel-based PSRL Agrawal & Jia (2022), MNL-bandit Agrawal et al. (2017) Tiapkin et al. (2022) Ishfag et al. (2021) etc.) taking max over multiple (say J) samples from the posterior in order to get high probability optimism. We follow similar modification, with differences described later in the section. We believe that, due
to bootstrapping nature of Q-learning (or TD-learning methods in general), merely taking multiple samples for either decision-making and the target construction would lead exponential (in H) accumulation of errors, even for J as small as 2. Below, we provide rough argument.
We expect the bias of Qn (sample from the posterior distribution) to track Q7 with error that scales as standard deviation of Qx)) (lets call that error e). Now, suppose J samples are used in decision- making (i.e., we take multiple samples from the posterior distributions at Line of A Algorithm [ We incur regret whenever the bias of max, Q exceeds Q" Using the standard techniques, this error at step H has an error bound of e (oo(///)) with probability 1 - 6. This error subsequently propagates multiplicatively via bootstrapping of Bellman equation. For the step H 1, the optimism Continuing this argument, step 1, the cumulative optimism error will be of the order c c log(1/6), i.e., exponential in H for any J ' 2. The usual trick of obtaining high probability optimism by taking multiple samples from the posterior doesn't ' work for Q-learning, at least not without further novel ideas.
error contribution will be E E J2 log (/6) with probability
Our techniques.
The design of target computation procedure is pivotal PSQL.. Our algorithm design is characterized by two key items: (1) using optimistic posterior sampling in target computation only; (2) using the argmax action of the posterior mean (with a standard deviation offset) in our larget computation.
First motivated by the observation that break the recursive multiplicative decay in constant probability of optimism, we just need to ensure high probability optimism of the next-stage value function estimate used in the target computation. Second is motivated by the previous discussion that merely taking multiple samples may lead to exponential error. In our analysis, we show that the action a special action, whose standard deviation close to the the played action a₁ with constant probability (Lemma C.2 As result, we are able to demonstrate that as in the standard Q-learning (*(5)) (defined with @) cannot be too far from Q (sh. ox). Intuitively they are tracking the similar quantities. In summary, our algorithm uses combination of vanilla (single-sample) and optimistic (mult)))e-sample) posterior sampling for action selection and target computation, respectively.
4.2 PROOF SKETCH
We provide a proof sketch for Theorem 2 All the missing details from this section are in Appendix C Here, we use Qu.,, 2r,te VK,,,N Nr. to denote the values of Qr. Qn, Vn, No. respectively at the beginning of episode i of Algorithm visited at episode k step /.
And, as before, kk ak.h denote the state and action
Following the regret decomposition in (3) we bound the regret by bounding optimism error and estimation error. We introduce several new technical ideas to this end. Leveraging our algorithm design, we first prove that A is a tracking upper bound (optimistic estimate) to Vi.- Second and the most crucial bit to show that deviation of V k. (sk.h) from the sample used in decision-making Q a) can be tractably bounded across rounds of interactions. This combined with the optimism of Ra naturally bounds the optimism error. Third we demonstrate the estimation error has recursive structure, i.e., error at step h depends on error h + 1 and terms attributed to k, (SK.k) from QR. (SK,A, (k,)). Therefore, first two
stochasticity in the model; and deviation of V k parts are utilized to prove estimation error bound.
(a) V k. used in the target, is optimistic estimate of Vi Lemma (Abridged). For any episode and index h, the following holds with probability at least 1 8/KH,
(K,K) 2 (8K,))
where 8 is a parameter of PSQL used to define the number of samples J used to compute the target.
8

---

Published as a conference paper at ICLR 2026
The above is an abridged version of Lemma C.1 The proof of which inductively uses the optimism and estimation error bounds available for the next stage (h 1) to bound the estimation error the posterior mean Qn (s, a). Then, anti-concentration (i.e., lower tail bounds) of the Gaussian posterior distribution provides the desired constant probability optimism.
(b) (8k.A) used in the target, is not far away from Q (8k. (k,h). The following lemma is an abridged version of Lemma C.3 and tells us that the gap is of the order of (N (g,A))
which goes down (see (TO) as 8k,h, dg.h is visited often with rate 1/v (NV.N ag,b). This is central to our analysis.
Lemma (Abridged). In Algorithm with probability 1- 26, the following holds for all k [K] and h E [H].
V.A - Qu.n (8k, 0n S ((a (k))),
where O()) hides multiplicative logarithmic terms.
The challenge here is that V (F,,t1() is obtained by sampling from the posterior of Q(sk,++1,)) at action (== argmax, (k.A(Sk,n.a) + (NN,, a))) and not 0g,h+1 (== arg max, (SK.A, a)). To get around this difficulty, we show in Lemma C.2 that (NN,, (sk.h.))))))) a))² < 20 (SE.A, ax,1))² log((18)) with a non-zero probability. Finally, using probability boosting argument (Lemma E. prove Lemma Combined with Lemma to obtain a high probability optimism error bound.
Lemma 3 (Optimism error). In Algorithm with probability 25, the following holds for all k E [K] and h E [H].
(SK,N) (k, (k,))
where Ö()) hides multiplicative logarithmic terms.
(c) Bounding estimation error. In Q-learning, estimate of the next stage value function (here, V V= is used to compute the target order to update the Q-value for the current stage (here, the posterior mean @.. As a result, the error in the posterior mean for stage depends on the error in the value function estimates for
Lemma 4 (Posterior mean estimation error). With probability least 1 - 6, for all k. h, s,a [K] x [ x S x A.
Qk, (s, a) - (s, a) S (o(NEM(s, 0 Ei= at (V (VRihta (sk, - Vi+ (8k),h+1)):
where n (s, and = log(SAKH/0), And, ot = a,l1i-it1(1 -aj), i 0, with 0 (1-3))-0)
Conceivably, we should able apply the above lemma inductively to obtain an estimation error bound (Lemma(5). Lemma again plays crucial role in the above recursive bound.
Lemma (Cumulative estimation error.). With probability at least - 8, the the following holds for all h [.).
ΣKE (Sk,h akhh) Vo (
< (IPVSATTogU/SA///0
(c) Putting it all together. To obtain the final regret bound, we simply sum up the optimism error bound in Lemma For K episodes and add it to the cumulative estimation error bound above.
CONCLUSION
We presented posterior sampling- basedd based approach for incorporating exploration in Q-learning Our PSQL algorithm is derived from an insightful Bayesian inference framework and shows promising empirical performance in preliminary experiments. (Detailed experimental setup and empirical results on additional environments provided in Appendix A) We proved Ö(H² (HH2255 VSAT) regret bound

---

Published as a conference paper at ICLR 2026
in tabular episodic RL setting that closely matches the known lower bound. Future directions include a theoretical analysis of the vanilla version of PSQL (called PSQL* in experiments) that uses single sample from next stage posterior in the target computation. The vanilla version outperforms Algorithm empirically Cempricalll but is significantly harder to analyze. Another avenue is tightening the H dependence in the regret bound; Appendix [F Foutlines a sketch for improving it by v H although at the expense of making the algorithm more complex. Further refinements are potentially achievable using techniques from Li et al. a222 Zhang et al. (2020).
REFERENCES
Alekh Agarwal and Tong Zhang. Model-based rl with optimistic posterior sampling: Structural conditions and sample complexity. Advances in Neural Information Processing Systems, 35: 35284-35297, 2022.
Priyank Agrawal and Shipra Agrawal. Optimistic q-learning for average reward and episodic reinforcement learning. arXiv preprint arXiv:2407.13743 2024.
Priyank Agrawal, Jinglin Chen, and Nan Jiang. Improved worst-case regret bounds for randomized least-squares value iteration. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 6576,6573, 2021.
Shipra Agrawal and Navin Goyal. Analysis of thompson sampling for the multi- aamtid-ameddd bandit problem. In Conference on learning theory, pp. 39-1. JMLR Workshop and Conference Proceedings, 2012.
Shipra Agrawal and Navin Goyal. Near-optimal regret bounds for thompson sampling. Journal of the ACM (JACM), 64(5):1225 24, 2017.
Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. Advances in Neural Information Processing Systems, 2017.
Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: Worst-case regret bounds. Mathematics of Operations Research, 48(1 (351):33333))) 392, 2022.
Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi. Thompson sampling for the mnl-bandit. In Conference on learning theory, pp. 76-78. PMLR, 2017.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference on Machine Learning, pp. 263-272. PMLR, 2017.
Kamyar Axizzadenesheli, Emma Brunskill, and Animashree Anandkumar. Efficient exploration through bayesian deep g-networks. In 2018 Information Theory and Applications Workshop (ITA), pp. 1-9. IEEE, 2018.
Yu Bai, Tengyang Xie, Nan Jiang, and Yu-Xiang Wang. Provably efficient q-learning with low switching cost. Advances in Neural Information Processing Systems, 32, 2019.
Peter L Bartlett and Ambuj Tewari. Regal: A regularization based algorithm for reinforcement learning in weakly communicating mdps. arXiv preprint 1205. 2012.
Christopher Bishop and Nasser M Nasrabadi. Pattern recognition and machine learning, volume Springer, 2006.
Victor Boone and Zihan Zhang. Achieving tractable minimax optimal regret in average reward mdps. arXiv preprint arXiv:2406.01234. 2024.
Nicolo Masa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. Advances in neural information processing systems, 24, 2011.
10

---

Published as a conference paper at ICLR 2026
Christoph Dann, Mehryar Mohri, Tong Zhang, and Julian Zimmert. A provably efficient model-free posterior sampling method for episodic reinforcement learning. Advances in Neural Information 12051, 2021.
Processing Systems,
Ying Fan and Yifei Ming. Model-basee reinforcement learning for continuous control with posterior sampling. In International Conference on Machine Learning, pp. 3078-3087. PMLR, 2021.
Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Ian Osband, Alex Graves, Vlad Mnih, Remi Munos, Demis Hassabis, Olivier Pietquin, al. Noisy networks for exploration. arXiv preprint arXiv: 170..
706. 10295, 2017.
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner. Efficient bias-span conatnnconttaieed in reinforcement learning. In International Conference on Machine Learning, pp. 1578-1586. PMLR, 2018.
Haque Ishfaq, Qiwen Cui, Viet Nguyen, Alex Ayoub, Zhuoran Yang. Zhaoran Wang, Doina Precup, and Lin Yang. Randomized exploration in reinforcement learning with general value function approximation. In International Conference Machine Learning, pp. 4607-4616. PMLR, 2021.
Haque Ishfaq, Qingfeng Lan, Pan Xu, A Rupam Mahmood, Doina Precup, Anima Anandkumar, and Kamyar Azizzadenesheli. Provable and practical: Efficient exploration in reinforcement learning via langevin monte carlo. arXiv preprint wrXiv:2305.88246 2023.
Haque Ishfaq, Yixin Tan, Yu Yang, Qingfeng Lan, Jianfeng Lu, A Rupam Mahmood, Doina Precup, and Pan Xu. More efficient randomized exploration for reinforcement learning via approximate sampling. arXiv preprini arXiv:2406. 12241, 2024.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is Q-learning provably efficient? Advances in neural information processing systems, 31, 2018.
Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In International conference on algorithmic learning theory, pp- 199-213 Springer, 2012.
Mohammad Emtiyaz Khan and Håvard Rue. The bayesian learning rule. Journal of Machine Learning Research, 24(281):1 1-4,, 2023.
Jeremias Knoblauch, Jack Jewson, and Theodoros Damoulas. An optimizationn-cntric view on bayes' rule: Reviewing and generalizing variational inference. Journal of Muchine Learning Research, 23 (132):1-109, 2022.
Gen Li, Laixi Shi, Yuxin Chen, Yuantao Gu, and Yuejie Chi. Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Advances in Neural Information Processing Systems, 34: 34:177622 17722-1776, 2021a.
Ziniu Li, Yingru Li, Yushun Zhang, Tong Zhang, and Zhi-Quan Luo. Hyperdqn: A randomized exploration method for deep reinforcement learning. In International Conference on Learning Representations, 2021b.
Pierre Ménard, Omar Darwiche Domingues, Xuedong Shang, and Michal Valko. Ucb momentum learning: Correcting the bias without forgetting. In International Conference on Machine Learning, pp. 7609-7618, PMLR, 2021.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602, 2013. htLhttts:: pttttps://ariiv.. http://axivvvvooa wttp
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 5 51877540::59-533. 2015.
Volodymyr Mnih, Adrià Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy P. Lillicrap. Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning, 2016.
11

---

Published as a conference paper at ICLR 2026
Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism for reinforcement learning? In International conference on machine learning, pp. 2701-2710. PMLR, 2017.
Ian Osband, Daniel Russo, and Benjamin Van Roy. (More) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013.
lan Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. Advances in neural information processing systems, 29, 2016a.
Ian Osband, Benjamin Van Roy. and Zheng Wen. Generalization and exploration via randomized value functions. In International Conference on Machine Learning, pp. 2377-2386. PMLR, 2016b.
Ian Osband, Benjamin Van Roy. Daniel Russo, and Zheng Wen. Deep exploration via randomized value functions. Journal of Machine Learning Research, 20(124):1-62, 2019.
Yi Ouyang, Mukul Gagrani, Ashutosh Nayyar, and Rahul Jain. Learning unknown markov decision processes: A thompson sampling approach. Advances in neural information processing systems, 30, 2017.
Daniel Russo. Worst-case regret bounds for exploration via randomized value functions. Advances in Neural Information Processing Systems, 32, 2019.
Remo Sasso, Michelangelo Conserva, and Paulo Rauber. Posterior sampling for deep reinforcement learning. In International Conference on Machine Learning, pp. 0-00000000000 PMLR, 2023.
Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, 3: 9-44, 1988.
William R Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of samples. Biometrika, 25(3/4):285-294 1933.
Daniil Tiapkin, Denis Belomestny, Daniele Calandriello, Eric Moulines, Remi Munos, Alexey Naumov, Mark Rowland, Michal Valko, and Pierre Ménard. Optimistic posterior sampling for reinforcement learning with few samples and tight guarantees. Advances in Neural Information Processing Systems, 35:10737-10751, 2022.
Daniil Tiapkin, Denis Belomestny, Daniele Calandriello, Eric Moulines, Remi Munos, Alexey Naumov, Pierre Perrault, Michal Valko, and Pierre Ménard. Model-free posterior sampling via learning rate randomization. Advances in Neural Information Processing Systems, 36773719-73774, 2023.
Hado van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double learning, 2015.
Martin Wainwright, High-dimensional statistics: non-asymptotic viewpoint, volume 48. Cam- bridge University Press, 2019.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8:279-292, 1992.
Zhihan Xiong, Ruoqi Shen, Qiwen Cui, Maryam Fazel, and Simon S Du. Near-optimal randomized exploration for tabular markov decision processes. Advances in neural information processing systems, 35:6358-6371, 2022.
Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pp. 7304-7312. PMLR, 2019.
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least- squtre value iteration. International Conference on Artificial Intelligence and Statistics, pp. 1964. PMLR, 2020.
Zihan Zhang and Qiaomin Xie. Sharper model-free reinforcement learning for weward markov decision processes. In The Thirty Sixth Annual Conference on Learning Theory, pp. 5476-5477. PMLR, 2023.
12

---

Published as a conference paper at ICLR 2026
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learningvia serrence-advantag decomposition. Advances in Neural Information Processing Systems, 33: 15207, 2020.
13

---

Published as a conference paper at ICLR 2026
The Use of Large Language Models Commonly availaible LLM tools only used help to improve english writing, grammar and typeset in Latex. LLMs were not used to generate any research ideas or analysis present in this work.
A EXPERIMENTS
we proved that our Q-learning with posterior sampling algorithm PSQL enjoys regret bounds comparable to its CCB-counterparrts c.g.,Jim et al. (2018). In this section, we present empirical results that validate theory and compare the empirical performance of the posterior sampling approach against several benchmark UCB-based and randomized algorithms for reinforcement learning.
In section 4
For the empirical studies, we use the vanilla version of posterior sampling, which we denote as PSQL* * (see Figure D In this vanilla version, the target computation step h is the default FA max, Q++ ($ a'). As discussed in Section 3.2 PSQL modified this target computation to make it slightly optimistic, to deal with the challenges in theoretical analysis. Later, we also compare the empirical performance PSQL and PSQL* While the modified target computation does slightly deteriorate the performance of PSQL, in our experiments, it still performs significantly better compared the benchmark UCB-based approach Jin al. (2018).
Specifically, we compare the posterior sampling approach to the following three alorithms.
UCBQL Jin et al. (2018) (Hoeffding version): the seminal work which gave the first UCB based Q-leamnin regret analysis.
RLSVI Russo (211)): popular randomized algorithm that implicitly maintains posterior distributions on Value functions.
Staged- RandQl (ainQi. al. (2023 recently proposed randomized Q-learning based algorithm that uses randomized learning rates to motivate exploration.
Environment description. We report the empirical performance of RL algorithms on two tabular environments described below. In each environment, we report each algorithm's 's average performance over 10 randomly sampled instances.
(One-dimensional "chain" MDP:) An instance of this MDP is defined by two parameters p [0.7, 0.95] and S E {7, 8,........ 14). from the given ranges. The resultant MDP environment a chain in which the agent starts at state (the far-left state), and state S (the right-most state) is the goal state. At any given step h in an episode, the agent can take "left" or "right" action. The transitions are to the state in the direction of the action taken with probability p, and in the opposite direction with probability 1 p.
In random instance, & S are chosen randomly
(Two-dimensional "grid-world" MDP, similar to FrozenLake environment the popular Gymnasium library:) A random instance of this MDP is defined by 4 x 4 grid with random number of "hole" states placed at on the grid uniformly at random that the agent must avoid else the episode ends without any reward. The agent starts at the upper-left corner, and the goal state is the bottom-right corner of the grid. There is at least one feasible path from the starting state the goal state that avoids all hole states. any given time step, the agent can take the "left", "right", "bottom" and "up" actions. After an action is taken, the agent has 1/3 probability transit to the direction of the action taken, and 1/3 probability each to transit to the two perpendicular directions.
In both the above environments, the goal state carries the reward of (H - h) H, where H is the duration of the episode and h is the time index within the episode at which the goal state reached. No other state has any reward. The duration of an episode is set at H 32 for all experiments.
Findings. We observed that the performance of all the algorithms sensitive to constants in the exploration bonuses or in the posterior variances. These constants were tuned such that the respective algorithms performed the best in the two environments. We made the following parameter choices for the algorithmic simulations for fair comparison:
14

---

Published as a conference paper at ICLR 2026
6 is fixed for all algorithms as 0.05.
In UCBQL Jin et al. (2018), the Q-function estimates are initialized as the maximum value any state in the environment (=: Vmna). The exploration bonus for any h, 8, with visit counts is given by
V log (SAT/8)
n
with e = 0.01
PSQL and PSQL*, the Q-function posterior means are initialized as Vmax (same as UCBQL) and the standard deviation of the posterior for any h, with visits is given by
V max
max (1, n2
with = 0.02.
In RLSVI Russo (2019), the per-reward perturbation is mean zero Gaussian with standard deviation for any h, s, with n visits is given by,
1/2 mix log (AAT/)))
1
with 0.005.
In Staged-RandOl Tiapin al. (2023). for the initialization of the Q-function estimates, we use a tighter upper bound of (H h)/ H at step available in our environment, instead of the default H h suggested in their paper. We no 1/S and ro in their paper.
Our results are summarized in Figure and The error bars represent one standard deviation interval around the mean cumulative regret of algorithm over 10 runs on randomly generated instances of the environment. We observe that the randomized/postery sampling algorithms PSQL", RLSVI,
PSQ.
GOOD
RLSVI LCBQL
Slagel-flerttt)
UEACL
Raneet--annOLL
Curnilative reglet
Cunulative reeret
4000
25000
2000
30200
2000
1000
0-
10000
20000
40000
Episades
Episades
(a) the-dimensional "chain" MDP
(b) Two-dimensional "grid" MDP
Figure 2: Regret comparison: x-axes denotes episode index, y-axes denotes cumulative regret
and Braged-RandQU have lower regret than their UCB counterpart: UCBQL. Also, PSQL* * has significantly lower regret than the other two randomized algorithms.
direct practical implication is that, PSQL* enjoys shorter learning time (number of episodes after which the cumulative regret is below the specified threshold (Osband et al., 2019)). Further, the variance across different runs is also the lowest of all, suggesting PSQL* enjoys higher robustness.
we compare the performance of PSQL*, the single sample vanilla version of posterior sampling, with the PSQL algorithm for which provided regret bounds. As explained in Section 4.I Chhallegee and Techniques), in order to achieve optimism in the target, PSQL computed the next state value by taking the max multiple samples from the posterior of empirical mean maximizer
In Figure B
15

---

Published as a conference paper at ICLR 2026
action @ arg max, (sa. a) (sh, d)). This introduces extra exploration, and result, we observe that PSQL* displays a more efficient eyploration-exploiaattie tradeoff, PSQL still performs significantly better than the UCB approach. These observations motivate investigation into the theoretical analysis of the vanilla version, which we believe will require significantly new techniques.
8000
LCBOL
1SQ_*
UCSCL
PSOL-
PSQL
Curulaativ regret
Curnulative rearet
15000
2000
10000
2000
Euisudes
Episodes
(a) One-dimensional "chain" MDP
(b) Two-dimensional "grid" MDP
Figure 3: Regret comparison: x-axes denotes episode index, y-axes denotes cumulative regret
B BAYESIAN INFERENCE BASED INTERPRETATION FOR Q-LEARNING
In this section, we describe the mathematical steps for calculating the updated posterior distribution
from (8)
First, in Proposition B.I we derive the well-known result that solving the optimization problem in (6) gives the posterior distribution expected by Bayes rule. Let 0 E θ be the Bayesian parameter that we are inferring with Ae be the space of distributions on θ Let p(0). [(0, -). and (()) be the the current prior distribution on 0, the negative log likelihood function and the posterior distribution to be calculated.
Proposition B.1 (Also in Khan & Rue (2023); Knoblauch et al. (002))). Let (L(((0)(p(())
(( ). Given log likellihood function E(O, 2), and prior p(0), the distribution that So (0) log( p(O)
maximizes ELBO objective,
max Eang [[(0,=)] (L((()))P())) yEas
(14)
is given by the Bayes rule
Buyes (0) x p(0) exp(e(0, z)).
(15)
Proof. Note that the ELBO objective function is equivalent to
log(exp(-((0,2)((0 [ log (())
p(0)) x())
/ log p(0) exp(((,))
(())
(()),
which is maximized when p(0) Bayc
Now, we study the calculation of the posterior distribution of Qs a) after observing n + visits of (h, s, a) in Lemma B.I
ELB over the space Ae Lemma B.1. Consider the following maximization problem (regularized ELBO) of distributions over a parameter O.
problem
max Eo~g [((0, 2)] -]] KLL((O)ll)(()) A. H()()))
(16)
16

---

Published as a conference paper at ICLR 2026
Then, if p-) is given by the pdf the Gaussian distribution (fn-11 o² n-1 and E(O, 2) log(@o (z))
where (2)2) Pr(=(0) is the pdf of the Gaussian distribution ((, H+1 and Xn n. then the where
o²
optimal solution q()) (16) is given by the Gaussian distribution N N(p
H +
An = -1-00 (1-ax))n-11 + an with O'p
H +
Proof. Denote the objective value at given distribution rELBO(()) Then,
rFLLB(()) J. log(exp(((0)=) ()(())
1 log ((0)
p(0) ((0) An (log(((0))g())
(0) --/ log p(0) exp(((8,,
((0),
which is maximized distribution q with (0) (p(0) 2))p(((.2))) Then,
1
(n - 1) (0 - Pn-1) 2
(H + 1)(2 - 8)2
(())
x exp
An +
202
202
(2 + n)) - 20((n 1)7m- -1 + (H 1)z)
71
o exp
H + n
20
0 20
exp
11
20
(0 )2
cxp
20
where Th,
H+n pn-1
1-1
H+1 H+n
= (1
an) + an
C MISSING PROOFS FROM SECTION
4
C.I OPTIMISM
Lemma C.1 (Unabridged version). The samples from the posterior distributions and the mean of the from posterior distributions defined in Algorithm satisfy the following properties: for any episode k E [K] and index h E [H].
(a) (Posterior distribution mean) For any given with probability at least 1 - 2(k-1)6
KH
KH
(s)(s))) 2 () a) (o(N).
(17)
(b) (Posterior distribution sample) For any given s, a, with probability at least pı (p1 ( conditioned on (17) being true,
(8, a) 2 Q7(s,
(18)
(c) (In Algorithm k' < k
With probability least KH the following holds for all episodes
VH,N(SH.N) 2 (sK.)).
(19)
Here 8 is parameter of the algorithm used to define the number of samples J used to compute the target
Proof. We prove the lemma statement via induction over k. h.
17

---

Published as a conference paper at ICLR 2026
Base case: l: 1, [H]. Note that (1, = 0 for all 8, s, E S x A x [H]. Therefore,
(1, H for all 8, a. ((17) is trivially true). As (s, a) I H for all 8, a, h, therefore
Q1. 2 Qú (s, a), with probability at least 1/2 (> Pı). ie. (8) is true. By the choice of J and
Lemma E.2 (9) also follows.
Induction hypothesis: Given > 1, 1,1 < H, assume that the statements (a),(b), and (c) are true for < k2 S 1, E [H], and for k' k. + H.
Induction step: For k. h, we show 17 holds with probability 2(k-1)6
18 holds with
KH
KH
probability at least pl ( in the event (17) holds, and finally 19 2k4
holds with probability
1
KH
In case n (s) then Qr. (s, a) H and b as in the base case, the induction statement holds. For the rest of the proof we consider nR, (8, a) > 0.
(s, a) > 0 and therefore by the same reasoning
Let (s, a), then Algorithm immlles.
Qu,n(s, a Σ dn (reah + RR (SR2.)+1)).
(20)
To prove the induction step for equation.
17 consider the following using 12 and Bellman optimality
n
ac) - (),
E
on (kihh - -r((,, + V kg (Sk,)+1) Pros,a Vi:"
(rkg, rr)(s,a) Vnai (Sk,)+41 Ph, Vi)
an (Vr.tti(Sk,Ntt) Vhe (sk)
19 from induction hypothesis for h + 1 S H, with probability 1 2(k: 1)6
(using
KH
(note that this is trivially true when h + 1 H since VA, Vi+t 0)
(TKL.A (s, + V/+ [ Ph.s,a Vi.
(using Corollary D.2 with probability 1
KH
1l K (H)))
(s, +
(N
(21)
Therefore, with a union bound we have with probability 1 2(k-1)8 KH
KH
()) 2 (8) - VoNNe, a))²
(22)
When 22 holds, then from the definition of cumulative density of Gaussian distribution we get,
Pr (Qnn(s,a) (s, + (o(Nen(s,a)))) 2 ((-1).
Now, we show Q (1(8,00) (s) with probability at least ((-1) - 5- 5/H, where
à = arg max (s. ((N(s a)), and a" = arg max Q7, (s,
AEA
asA
18

---

Published as a conference paper at ICLR 2026
By the definition of â and properties of Gaussian distribution:
(s.) 2 (s. + ((N(s, a))
+(Nss,))
Qi, a²)
with probubility at leust pi 1)
with probubility at least
2(k 1/6/KH 6/KH
Setting J 2
log H1/() 1og(1/(1-p)) in Algorithm we use Lemma E.2
to show that with probability -
5
KH
VR,A(SEN)) 2 (sk.))
(23)
Finally we use a union bound to combine (2) and 23 to prove 19) holds with probability least
1
2
C.2 ACTION MISMATCH BOUND
Lemma C.2 (Bounding action mismatch). For given k A.hhssa Sk and let ā
arg max, Qu,n a) + Vo(NeM((L....))
(N 2)) < where p2 = (-2) (A)6, and as defined in Theorem
ax,n)) 2 log(1/5), with probability at least P2.
Proof. Consider the following partition of A actions:
Ā {a: 2o a))² log(1/6) o(N(s, ())
{a 20(NN(s a² (1g() S (oV(s, a)){
A
Clearly, E A. We prove that with probability at least o - Ad, we have à E A, so that ()) 2n 2o(NN (N(s, a))² log(1/8).
By definition of a, we have that for all a,
(s. Vo(N(s, a))² s Q
Also, by construction of A. we have that for Va E A.
((s, (N( + 22
a) log(118) < (s (NN)) Vo(N(s, a))²
From Gaussian tail bounds (see Corollary D.I we have for Va E A.
Pr (Q(s,a) s (2) + (o(Nss) (2s log(1 2 1 A6
so that Va E A.
() (2( O 1 11-46 A6
Pr
Also for the Gaussian random variable Q((s, 7), we have with probability at least (--2).
( @) @ @) 2 (N),
Using union bound on the last two events,, we get
(s.@@) max (),,a), with probability at least Φ(-2) A6.
(24)
A
Since is in A. the above scenario, the action that maximizes Q(s.)) must be A. Therefore,
((N(s,)) 2) < (N((8, a²)² log(1 /8) with probability Φ A6.
19

---

Published as a conference paper at ICLR 2026
Proposition C.1 (High probability action mismatch). For given k, k,h,sk, Sk, let @ orgmax, (SK, a). Then,
1 Bar, 2oog
(8K,, 2)) (N
+ log
P2
where p2 = x (A)o, and ô as defined in Theorem ag.h given Sk.h and the history before round k, h.
2 Here Eag, denotes expectation over
Proof. This follows by using previous lemma along with Lemma E.1 with X (NN,,s(skh ok,h)) log(/ X X* (NN.A(SA,..))) and X
C.3 TARGET ESTIMATION ERROR BOUND
The following lemma characterizes the target estimation error.
Lemma C.3 (Target estimation error). In Algorithm with probability 1 25, the following holds for all k E [K] and h E [H].
Vkn(( (sK,, (K,A)
4 B. (ok)))
S (e( log + P2
1 F(k,
=
P2
where = = (A)5 and as defined in Theorem 2 J is defined in 111. and Eg [-] denotes expectation over the randomness in the action taken at k. conditioned all history the start of the ha step in the episode k (i.e., only randomness is that in the sampling from the posterior distribution).
Proof. We have arg ã max, (K, a). For the remainder of the proof, drop k, from the subscript and denote 4g.b by à. From Algorithm V(s) is the maximum of samples drawn from Gaussian distribution with mean as (s, @) and standard deviation as (NNss, a))² Using Gaussian tail bounds Corollary D.I along with union bound over J samples, for any d (0, 1), with probability at least 1 0,
V(s) s ((s,ā) + ()
s (s.@a) + (2 a))² (1/8) + (2o 1ogg
where Q(s,, a) the sample corresponding the à action drawn by the algorithm at the k. Using union bound to combine the statements, with probability at least 20 we have,
V(s)
S Q a) + 22/2 2))² (og()/))
+ ((s,a)+2244)) 20 k))² (J/5)
(25)
To complete the proof, we use Proposition C.I and an union bound over all k, h to have the following with probability at least 25
VRA(SK. - ak.1)
S (NE, (8,.
F..
ac))) Dog (KgH//))))
P2
20

---

Published as a conference paper at ICLR 2026
C.4 OPTIMISM ERROR BOUND
Corollary C.I (Optimism error bound). In Algorithm 7 with probability 36, the following holds for any E [K] and h E [H].
Vi2 (sw,h) - QU.A on
4 (Ma
s 4oNNu..(Saa log((HH0)))) + p2
= P2
h)).
where = ( (A)5 and as defined in Theorem 2 J is defined in (11). and Ea [.] denotes expectation over the randomness in the action taken at k. conditioned all history the start of the ha step in the episode k (i.e., only randomness is that in the sampling from the posterior distribution).
Proof. From Lemma
C.3 we have with probability at least 1 - 20,
(s,,)))))) QK.n ak.h)
S 4o(Na.lSee, acN) log(JKH/8) + (M..
P2
1 F(,,h,8).
P2
Further, Lemma
C.I (c) gives with probability at least - 8,
V7 (Sk.N) (K,,))
We complete the proof via union bound.
Corollary C.2.
With probability 8. the following holds for all [H],
K
(SK.N) - Qu s O(VESSATX)
where x log(JSAT/0).
Proof. From Corollary C.1 we have for all k, h simultaneously, with probability 1 - 35,
(E,n) QR. (Sk,h, (k.A)
< (N (k.))) log(JKH/8) - -B..loNNe..ss.. (
P2
By combining the definition the variance in 10 with Corollary
D.4 the result follows easily.
C.5 POSTERIOR MEAN ESTIMATION ERROR BOUND
Lemma 4 (Posterior mean estimation error). With probability at least - 5, for all k h, s, E [K] x [ x x A.
Qu, a) - (8, a) S (o(Nu,(s,a))4n a Ei af (V VR (8k,,++1) - Vir (Sk).t+1))
where = (x, a), and log(SAKH/O)) And, at, a,llg-it2(1 -a;), i > 0, with
of MT. 1T az))
21

---

Published as a conference paper at ICLR 2026
Proof. First consider fixed h, s.a. From 12) and Bellman optimality equation, we have (assume n (k, 2 1).
( (s, (
Σ a (Kkih ( - rh(s, (r((,a) + +V (0 - Ph,e, Vix
Σ
On (Tkih (Tkahh-rh6 (s, V/+ Vit (skaNht) Phooaai'
Σ
on I Vht (sk.)t+))))
1=1
(Using Corollary
D.I with probability 1 8)
s (o
+
o (ke,tt1SSH,,tt)) - Vit
(Sk,,tt)))))
(26)
When (s, = 0, then trivially (s, (8, H = a H, and for (8, 0. then a = O. Combining these two cases and with a union bound over all 8, a, h k. we complete the proof.
C.6 CUMULATIVE ESTIMATION ERROR BOUND
Lemma (Cumulative estimation error.). With probability at least - 5, the following holds for all [
ak.a) Ek= (QuA (k.a) Vi (sk.t))
Proof. For the purpose of writing this proof, define Φu.h Qe,n an.n) (5 8k, (k,h ak.h) VITh (sK,)), and Bk., == VK, V7. (sk,h) Clearly 8x,n 2 Φi.h. Further, v(nu,a) + (NN,, (H)
Now consider, (K,, an.n) Vo (8H,L) S (K,n( - Q (Kk, (k.h)
QKn(KKRN, (kRA)) ( (KAA) + Qh, (sk,,, - QT (8H,1, 0x,1) (from Lemma with probability - 8, with n + Na.h 4x,1))
S a + 20(TE.)m
Pk. + PonnAOen (V Vi++1)
H.H + 20(nu.n)
a Bk 0.,4+1 64.141
+ +P PL. -Vin1- v
(Vi+) - Vit (SK,
From Lemma with probability 25
< 0 H + 20((na)))
P2 Σ
o P(k + 1,8) + maA
a 2k.
0K,4+1 + dR,
(27)
where
MALA == Ps aak. (Vi+1
h+1 - (Vi+i(SmA41)) Vir (88,
Now, we club all episodes together have,
K
K
K
K
H K +
Σ
5k
S
a
H
Au(nk,))
Σ
my.h
P2
k=
h= km
22

---

Published as a conference paper at ICLR 2026
K
K
0sh++1 +
5KA+1-
k=
From Lemma E.5 (c), it follows (aR,A = for, F(k, h, 6/KH)]) Ek= Ei (1+ 1/H)
E
dg, Further from the initialization,
K
K
H
MEEA - 03H SAH = HSA.
Jom
Therefore, we have,
K
K
K Σ
SAH
+
40(mm,) + ma,h)
+ + (1HH
F(k, h 1,8/HH) +
P2 k=1
R=
Am
R=
+(1 1/11
GRA++
Unrolling the above H times to have with union bound over k. E [K] x [H] with probability 1 - 8 (6 is scaled by 1/KH H due to the union bound):
K
(8k,1, (8K,1) S
eSAH
ΣΣ
(oo(mu,)) mR.... +
e
H
K
(28)
P2 hml km
where we have used 6g.n 2 Φh.n and 5k.H+1 O. Now, we analyze each term the right hand side of (88 one by one. From Corollary D.3
K
< O(VHISATT
1
From Corollary D.4 with probability at least 1 5-
1
K
1 ll Hp2 k=1k=1
F(ke, h 1,8/KH)
F(k, h + 1,8/KH)
P2
K
s 0(1)
log
(29)
h= km
s o (VHASATX))
(30)
where X log(JSAT/5).
Finally, from Lemma D.I
we have with probability 1-8
H K
OVHHTTlog K KH/5)
Mi.b
$
Combining the above, we complete the proof.
Theorem 2. The cumulative regret of PSQL (Algorithml 12 in K episodes satisfies
Reg(K)= = KK (SK, ViTh (sk, < O (IPVSATx),
with probability at least where X log(JSAT/5) and T KH.
23

---

Published as a conference paper at ICLR 2026
Proof. First combine Corollary C.2 and Lemma to get with probability at least 1 - 8 (x log(JSAT/6))
Σ (T VT (FL,) SO (a.)))(((HAAAAAA (VH+SATX).
Observing that the rewards are bound, there Ek= Ei=1 RA (5k,A. ak,h)) E (s 2 O(HyTToo((155) with probability at least 6. This completes the proof of the theorem.
D CONCENTRATION RESULTS
Corollary D.1. For given k. h, s, E [K] H X A Nx,,(s, with probability 1 8, it holds,
(Q,,(s,,)) (s,a()
(31)
Proof. The result directly follows form Lemma E.6
Corollary D.2. For some given h 8, a [K] x [H] 8 A, the following holds with probability at least 5 (with n = NR.1 a)),
H log(1/5)
o (rk,, - a(s,a) + (it,a Ps.a Vi++1
< 4V
h++1
Proof. Let k; denote the index of the episode when (s, a) was visited for the in time at step h. Set I; a (Tk,,h R2, (s. a) + V(s++1) Ps.a, V) and consider filtration F, as the o- r-fieed generated by all random variables in the history set Hk. Tk.. - Ra (s, a) V(s++1) 1-11) P..... a... (V) - H+1.
Using the definition of the learning rate (Lemma E.5 (b)), we have Σ; x S H(H + 1)2/n.
We apply Zzuma-Hoefdiing inequality (see Lemma E. L combined with union bound over all
(s, h) E S x A x [H] and all possible values of n K to get the following with probability at least 1 1-8, 5,
2H log(1/6)
2
n
We complete the proof using the observation
11
x+1
2n
Lemma D.1. with probability least 1 - 8, the following holds
H (Vi+ (it1) W Vit (Sk, S H2 22222T log(1/8)
P Pannnan
11
Proof. For Fkih Psu.nore (Vi+1 1 (Vi+z (sk,b_1) V (sk,)+1)) and filtration Hggh where is is the episode index, {IIg,h H4. A } forms a martingale difference sequence with |Kk, & H. We complete the proof using Lemma E.3 and union bound.
Lemma D.2. Let DR. be the distribution of actions at time step k. h conditioned on the history at the start of step h of the kis episode, then with probability at least 8, for some h
Ean-Deh
50 CO(VAllog() log(1/5)
Vnan(SEAha)) a)
Vnec (Bk () +1
24

---

Published as a conference paper at ICLR 2026
Proof. For brevity exposition,
E|Zx]
Baw [men Ex
(o and Fx f Hk.h- Consider,
K
[|| Zx) 1 (E|Z+)) + Z
(By Jensen's 's inequality for f(x) x²)
K
EIZ
km
(by linearity of expectation)
K
+
E
Σ
+
j+1
25A log( K).
To bound Σ (E 7x.
7&), we apply Bernstein inequality for martingale, Lemma K = 1, d = 2S log K) to get the required result.
E.4 with
L
Lemma D.3.
K
(N, .k.h) +1 <O(VSAK)
Proof.
K
K
V2
(K akhh) +1
N N akhh)
NK.Maaa)
0(1) Σ
V T
0 (VSAK)
Corollary D.3. The following holds,
H
ΣΣ
(s.. S O (VHH'AATT)
A=1k=1
Proof. From Lemma D.3 and we get the result.
Corollary D.4. Let Da. be the distribution of actions at time step k, h conditioned on the history the start of step h of the high episode, then with probability at least -8
K
Vo(NEa(SAs. (C(N)a/(A..)))11gUKRRR)))) + 220 (Ne. logg)))))(())KKK))
B BanDein
De,n
A=1 P2
0 (VHSSATX).
x log(JSAT/5)
25

---

Published as a conference paper at ICLR 2026
Proof.
Using Lemma D.2
have with probability 1 6,
K
5. so (V(VAllo((H K) log(110)
nk (Sk,,,
I (s (k,h) +
k=
From Lemma
D.3
and
(T)..
K
4
o alg So (OVVRSAATY)
P2
which dominates the remaining terms.
E TECHNICAL PRELIMINARIES
Lemma E.1 (High confidence from constant probability). For some fixed scalars X*, X, and
p,5 (0,1), 1), suppose that X D satisfies X 2 X with probability least p. X 2 X with
probability least 6, and B[X] 2 X. Then, with probability least 1 - 26,
x x - 1 [ED[X]-X]
(32)
Proof. For the purpose of this proof, a symmetric sample X-alt also drawn from distribution D but independent of X. Let Oull denotes the event when Xtalt X (occurring with probability p).
Consider (using notation [[| + Ep!:D
X X < E X
Oail]
x
E a
X
Oall]
(33)
where the last inequality holds with probability 1 - 8 by definition of X. The law of total expectation suggests,
E aaat
x
Pr((O
x X Oalt] + Pr(O
E
a
X
O
where Jelli is the compliment of the event Oalt, Now, E all
E
all
allt
S
E[Xaalr- [[ 2 X, where the last inequality is by the assumption made in the lemma. Therefore, the second term in the above is non-negative, and we have
E xralt
X
Pr(O"")
X
X
Oall
(34)
Using Pr((OM) S p. E [[ proof.
E and a union bound to combine 333 and
we complete the
Lemma E.2. Let (1)).990 .q........ be M i..d samples such that for any g()) 2 V with
probability p. Then with probability least 8,
max ( 2 V iEM
when M is at least
log(1/8) (gg()((1-)))
Proof. For given index i, the probability that (+) < V is at most 1 -pp Therefore, by independence
of samples, the probability of maxieJ (0) < V* is at most (1 MM Therefore, the lemma statement
follows by setting M 1og(1/(1-p)) p))-
log(1/8)
Li
Let [A,,F, ) be martingale difference sequence, and suppose [A < almost surely for all i 1. Then for all n 2
Lemma E.3 (Corollary 2.1 in Wainwright 2019)).
2n² Σm de
P
A n
< 2exp
(35)
1=1
26

---

Published as a conference paper at ICLR 2026
In other words, with probability most 6, we have,
(2/6) Σi=1 di
A
(36)
1=1
Lemma E,4 (Lemma A8 in Cesa-Bianche Bianchi & Lugosi (0066). Let (() be martingale
difference sequence, and suppose [Ail S K almost surely for all 2 Let Σj=1 A₁ be the associated martingale. Denote the sum of the conditional variances by
B[A Fi-1l.
Then for all constants t, d > O,
8²
max S 2 & u S
exp
2(d Kt/3)
Lemma E.5 (Lemma 4.1 in Jin et al. (0118). The following holds:
(a) 1 S Zi=1
a 2
Va
v
(b) maxien a < 2C and Σ (a 2C
t
(c) E < 1 + 1/C.
Lemma E.6 (Gaussian tail bound), For a Gaussian random variable ~ NN,,, it follows with probability least 8.
Pr (x - ul olllolllloollooooo
Proof. The proof follows by instantiating Chernoff-style bounds for the given Gaussian random variable.
F SHARPER REGRET USING BERNSTEIN CONCENTRATION
In this section, provide sketch of the extension of Algorithm I to randomized Q-learning procedure that uses Bernstein concentration based variance. This extension closely follows that in Jin et al. 2018) using some of the techniques developed in the proof of Theorem
We want to account for the variance in the transitions. To this end, we define some additional notations. The variance in transition for any (s, a) is defined using the variance operator Vn, below,
Va == EyenPan [V'+ - [Ph.s.a Vn+ils,a]*
(37)
The empirical variance for any (s, a) for any <- NE, a) is given by,
V Va
1 Σ
V ( Σ V WR,k+1 (8k,
(38)
Vo,(n, h s,a) = min dv n+1 ( VHTSAm
113
64
(39)
n+1
n
+1
Theorem F.1. The cumulative regret of Algorithm in episode satisfies with probability at least 1 1-8,
K H
ΣΣ
RA (Sk,,, S0
( (VHSSATIX).
E=1
k=
where X log(JS (o)(JSAT))) and log (S
27

---

Published as a conference paper at ICLR 2026
Algorithm 3 Randomized Q-learning
1: Input: Parameters: (0, 1). Set J = J(6).
2: Initialize: 1 a) = 1 = 0, V(s a) E s x A. and Qn(s,a) = Ps(()) =
H & (N, a) 0, Mr (s) (s, = (s, 0V(s.a, E A [H].
3: for episodes = 1,2, .................... do
4: Observe 81.
5: for step h = 1, 1,2,... H do
6: 1 Play arg max action of the sample of Qs */
7: Sample Ya Qu (sh,a) NV(2n a), (N (sh, a), h sh. a)).
8:
Play dĄ arg a Qn (s).aa) a).
9:
Use observations to construct one step lookahead target */
Observe Th and $h+1-
& < Construcc $1+1, Qu+1. Nx+1).
11:
12:
Use the observed reward and next state to update Qn distribution */ n = Na(sh: (n)) +- (sk un) + 1.
14:
(sh, an) + (1 (1- an Q (sh, an) ) + azz.
Ph (5): an) t ph (5h, ap) (z rh).
16:
(sh, an) f (sh: an) + (2--11²
Calculate ( an) (m an) Mn //)3
18:
/ Vu(nn, h, Shi an) t- minfcly
H1 n+I
(ba+1 (sh, ax) + H)m + a+1
WTSAAX ), / 64 64
19:
end for
20:
end for
F.1 PROOF OF THEOREM
The main mathematical reasoning closely follows that in the proof of Theorem 2 of Jin et al. with specific differences arising due constant probability optimism and the definition of V k.h. For
2018
any k, h,, a with = NR.A (s, a), we have vs(n, h, 8, a) S 64 "+I Therefore, Corollary C.2 and
Lemma 5 apply as they are. Hence, we get with probability at least - 5 for all h
K
Σ TKA (x., V,T*( S o @(HH-SATX)
(40)
where X (AT())))))). Further, following the steps and notations of the proof of Lemma we have with probability at least - 5,
(see 28
K
H K
( (sK.)) s eSAH²
ΣΣ
(Annstn, 8k, ax,)) + ma.h
H
K
(41)
P2
k=1k=1
Due to our observation that us h, SE, ana)) & 64 n+ therefore we get from
Lemma D.2 and Corollary D.4 hold,
H Σ
(Vob(n, h, Sk, x + magh
Qu.1 (sk,1, ax,1) VI**(SK (SK.1) s eSAH
ΣO
h=1k=1
where X log (SS()S)7))). We wish to bound
(n, 8k,b, aR.))
(42)
K H
H n n+1
SH'SAn
Σ
clp
V an + Hm +
(43)
n + 1
Aml
28

---

Published as a conference paper at ICLR 2026
Consider,
K
H
V
3 (0 A
(44)
(o 0k,A) +1
R= R=
Further,
K
H
H
(VWVAAHH(OLL + H)
+1
K
H
H
K
H
V (B +
n+1
k=
h=1
Vn (sLAh + HSSATH,
(45)
k=1A=1
where the last incquality follows from Lemma D.3. Since we have Lemma F.5 steps in (C.16) Jin et al. (2018) to get
we can follow the
K S
This gives us
K
vb(n, Sk,,, ok. S0 S HOWHHSTTT H
Thus we have,
Σ (.1( ViT (sk.1) < HP/HTAA V A
Finally, combining with Corollary
we complete the proof.
F.2 SUPPORTING LEMMA
Corollary F.1 (Corollary of Lemma probability at least -88 8.
We have for all s, S Ax [H] [K] with
-1((s) 50
(v.
Han
a H Σ on (V (Vh.h-1(Sk.htt)) - Viita (8k, (46)
22
where = Nn.a(s, a), and 11 log(SAKH/00)
Proof. The proof follows from using (39 in place of (N (s, a))² in Lemma
Lemma E1 (Based on Lemma C.7 in Jin et al.
2018). Suppose 46 in Corollary F. holds. For
any h (H) let BK, V.. V. (sk.h) vectors, then we have with probability at least 5,
and let (wr. wk) be non-negative weight
K
wr S OSSA|luoloo VH + /SA Hx)).
where X ()S(T5))/))
29

---

Published as a conference paper at ICLR 2026
Proof. For any fixed k, let <- (5k, (k.n) and Øk QK,, ak,1)) - (skh)) Then we have
BR,b
(S,,) Vi (s
(from Lemma C.3
with probability at least 1 26)
0k
Fk, h)
p2
(from Lemma C.5
with probability 1)
s Qk.h a
Q (k ) + 220(n)m + F(k, h,
P2
(from Corollary F.1
with probability 1 -)
S a 1
a BR A+1 = - F(k, h,
(47)
|n+1
P2
We now compute the summation Ek WrBk We follow the proof of Lemma C.7 in Jin et al. 2018). with the only difference being the term Σ the proof of Corollary D.4
we F(k, h, 6), which we bound below. From
P2
Wk F(k; h, P2
|wll OSSAV H log (JSAK/0)
2wR
Hi KH/0)
P2
P2
NE.h +
<
1 H + V SA| 1
where X = log JSAT/6). Other terms are evaluated in the same way as the proof of Lemma C.7 in Jin al. (2018).
Lemma F2 (Based on Lemma C.3 of Jin et al. (0118). ). For any episode k E [K] with probability 8/ K, if Corollary Kl holds for all Ee' < k, the for all 8, a, E A x [H]:
SAV H
2'X
V VhtVi+eee 10.. V a) 00
+
n
n
where n = Nr.n(SkAA.a... x = log(JSAT/0).
Proof. The proof almost identical to that of Lemma C.3 of Jin al. (2018) except Lemma instead of Lemma C.7 of Jin et al. (2018).
F.
Lemma F.3. (Bernstein concentration) For some given k, h, 8, E [K] x H x A, the following holds with probability at least 5 (with n = (s,,(s,a)),
a (FRi, - R(s, + 1 (8k,, P. Pa Vo+t)
<
v (s(n,h,sa))
where
H min dv n+1 (VaVa+ + Hy
SHTSAm +1
H
vo(n, 8,
64
n +
Proof. Let denote the index of the episode when (s, a) was visited for the in time step h. Set I; = a (Fk,, - generated by all random variables in the history set H Hk... n- We apply Azuma coonma-oeffdding (Lemma E.3
R, (s, a)), yJ = o (V ) Ps..a V) and consider filtration F, as the a field
to calculate Σn= Ty and Azuma- iamaa-Brnsttein for Σ 1= Mi/. Consider with probability 6.
H2
(V(8k))) Paiae V)
< 0(1)
v (o Finlaaa
H2n
< O(1)
WA VAVilleaa7 +
30

---

Published as a conference paper at ICLR 2026
Using Lemma F2 and suitable union bound, have with probability 1 1-6,
(s, Hin+ V /HTSAn11 X
(V - Pariar" V)
0(1)
Σ
n n+1
vs(n, h 8, a).
where the last term dominates the concentration of Σi= Tzl-
Lemma F.4 (Based on Lemma C.I The samples from the posterior distributions and the mean of the posterior distributions as defined in Algorithm 3 satisfy the following properties: for any episode k E [K] and index h E [.f].
2(k-1)6 (a) (Posterior distribution mean) For any given 8, a, with probability at least 1
KH
KH
(x, 2 () Vo,(n,h,s,0)
(48)
(b) (Posterior distribution sample) For any given 8, a, with probability least pa (p) (
(s, a) 2 (s)
(49)
(c) (In Algorithm With probability at least 265
KH
(s,,())))) Z Vž (sk.h)
(50)
Proof. The proof is identical to that of Lemma C.1 except that use Lemma F3 Corollary D.2
instead of
Lemma F5 (Based on Lemma C.6 of Jin al. 2018 following for all k. h E [K] x [H].
With probability least 48, we have the
V n k.N (8K, ax Vn Vith (Sk,A, (k,)
S
2H Pannaau
-V 1 -Viti
SAV H
HTSAX²
+0
+
n
n
where n = (N and x = log(JSAT/8).
Proof. Consider,
V R.n (8k,), ax.k) (s
< vn Ve.n(snA ak.)) V Vitz an
Vn ap.)) Vn A (Sk anw)
where for the first term apply Lemma F22 (which holds when Corollary F. and Lemma F.T hold) and for the second term we have from the definition of variance.
Wn Vi+t (SK,A, an,)) Vn Wi (sk an.
< 2HP 2.Pa (V v+t1):
31


Reviews:
[{"review_id": "7ox6h6q2Gp", "reviewer": "Reviewer_ZF74", "summary": "The authors introduce PSQL, a novel model-free method that utilizes Gaussian Bayesian inference on Q-values. This approach incorporates a different target value based on the optimism principle, though this optimistic target value does not influence the actual decision-making process. The paper provides regret bounds that are nearly optimal and comparable to those achieved by other posterior sampling methods. Additionally, the authors establish a modified version, PSQL, which uses the target value chosen as in standard Q-learning. The results demonstrate that PSQL outperforms several baseline methods in tabular environments.", "questions": "See weaknesses.", "limitations": "", "rating": 2, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Authors discuss the limitations of the analysis of the vanilla PSQL algorithm", "weaknesses": "- In my opinion, the empirical results are not sufficiently extensive. It would be interesting, for example, to consider a comparison with the PSRL algorithm, which was shown to outperform Staged-RandQL in a recent study (Tiapkin et al., 2023). Furthermore, the paper lacks a comparison in more complex environments, specifically those with a continuous state space;\n- Another interesting direction would be to extend this algorithm to more practical scenarios with a general state space. If this is possible, what quantity should be chosen for the variance in that setting?\n- What regret bound can be achieved in the \"vanilla version\" of the PSQL algorithm? Could a non-trivial polynomial bound be established\n- It appears there is a potential issue with the inequality  $\\mathbb{E}[\\tilde{X}^{\\text{alt}}| \\bar{\\mathcal{O}}^{\\text{alt}}] \\leq \\underline{X}$ in Lemma E.1. This is because the statement assumes $\\mathbb{E}[\\tilde{X}]\\geq \\underline{X}$, but the inequality seems to require the opposite for the proof to hold.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KPMOrA1kGg", "reviewer": "Reviewer_UBp9", "summary": "This paper presents Q-Learning with Posterior Sampling (PSQL), a model-free reinforcement learning algorithm that employs Gaussian posteriors on Q-values for exploration. By interpreting Q-learning as a Bayesian inference problem with a regularized ELBO objective, the authors design a conceptually simple algorithm that combines single-sample posterior sampling for action selection with multiple-sample optimism for target computation. This design allows them to prove a near-optimal regret bound of O(H^2 \\sqrt(SAT)), while preliminary experiments show competitive or superior empirical performance compared to UCBQL, RLSVI, and Staged-RandQL.", "questions": "1. Can alternative posterior distributions preserve Q-value structure more faithfully than Gaussians?\n\n2. Is there a principled or adaptive way to select the posterior variance to avoid heuristic tuning?\n\n3. Can the multiple-sampling step for optimism be replaced with a cheaper or more elegant alternative?\n\n4. How does the approach scale to function approximation or deep RL settings?\n\n5. How does posterior optimism interact with TD bootstrapping bias in long horizons?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The work is theoretically grounded, algorithmically simple, and provides new insights into the Bayesian interpretation of Q-learning. The regret guarantee is strong, and the analysis tackles key challenges in combining posterior sampling with TD learning.", "weaknesses": "Using Gaussian posteriors on Q-values may destroy important structural properties of Q-functions (e.g., boundedness or Bellman consistency), since Gaussian distributions are unbounded. The choice of posterior variance is subtle and strongly affects performance, requiring careful tuning. Moreover, the use of multiple posterior samples for target computation increases the algorithm’s computational complexity, and the theoretically unanalyzed single-sample variant (PSQL*) outperforms the analyzed one in practice, indicating a gap between theory and implementation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "NWMFR43bFf", "reviewer": "Reviewer_wHwf", "summary": "The authors proposed a model-free exploration method based on introducing the idea of Randomized Least-Squares Value Iteration (RLSVI) into the Q-learning framework. This algorithm, called Posterior Sampling Q-learning (PSQL), uses a Gaussian posterior estimate of Q-values and achieves a regret guarantee of $\\tilde{O}(H^2 \\sqrt{SAT})$, which is the same as Q-learning with UCB bonuses or Staged Randomized Q-learning. Additionally, the algorithm shows strong empirical performance on standard low-dimensional benchmarks.", "questions": "- It would be beneficial to discuss an RLSVI-style model-based algorithm that achieves the minimax optimal regret guarantee (Xiong et al. 2022).\n- What prevents you from using a standard RSLVI analysis with a single sample there?\n- What prevents you from extending the sketch of the proof in Appendix F to a complete proof for a variance-shaped noise? What is a main challenge there?\n- Is it possible to provide a deep-learning version of your method?\n\n### References\n\nXiong, Z., Shen, R., Cui, Q., Fazel, M., & Du, S. S. (2022). Near-optimal randomized exploration for tabular Markov decision processes. Advances in neural information processing systems, 35, 6358-6371.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Interesting alternative explanation of the UCB-Q-learning learning rate, that appears from the additional entropy regularization in the variational approximation, with a clear intuition of \"collapse avoidance\" with entropy due to bias in the estimate;\n- Strong empirical performance as well as theoretical regret guarantees;", "weaknesses": "- Lack of empirical comparison with a usual RandQL. Although this method does not offer the same rigorous guarantees as its staged version, it would be interesting to compare PSQL* and a usual RandQL without stages.\n- The regret bound does not match the regret bound of a variance-reduced version of Q-learning (Li et al. 2021);", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IFIDcjbn2M", "reviewer": "Reviewer_7R7w", "summary": "The paper proposes Posterior Sampling Q-Learning (PSQL), a tabular method that maintains Gaussian posteriors over Q-values and uses posterior samples for exploration; to obtain a $\\tilde{O}(H^{2}SAT^{1/2})$ regret bound, the analyzed variant makes the bootstrapped target optimistic by taking the maximum over multiple posterior draws for the next-state value. While the vanilla single-sample version exhibits strong empirical performance, the optimistic variant required for the theory is not competitive, lagging behind RLSVI and offering no gains over Staged-RandQL on the authors’ own benchmarks.", "questions": "- Given that the analyzed optimistic variant performs worse than RLSVI and Staged-RandQL, how do the authors reconcile the theoretical guarantees with practical usefulness? Can they provide intuition or evidence that the analyzed algorithm offers benefits beyond these baselines?\n- If the practical PSQL* deviates from the analyzed variant, do the authors plan to benchmark it against more practical exploration algorithms such as [1] on more challenging domains (e.g., Atari, Maze2D) to establish empirical competitiveness?\n- In lines 118–119 the paper says model-based methods directly model the rewards and transitions “instead of” the implied value function or policies; could the authors clarify this phrasing? In practice, model-based RL often uses learned models to improve the value function and/or policy.\n- What exactly are the authors claiming as “first” in the first contribution point, “provided by the Bayesian posterior”? Could they clarify how their notion of “Bayesian posterior” differs from earlier posterior-based Q-learning efforts (e.g., [1]) and what concrete novelty they intend to highlight?\n\n[1] Ishfaq et al., Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo, ICLR 2024.", "limitations": "", "rating": 2, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Provides a near-optimal $\\tilde{O}(H^{2}SAT^{1/2})$ regret analysis for a posterior-sampling variant of tabular Q-learning.\n- The vanilla practical instantiation consistently outperforms classical baselines such as UCB-QL and Staged-RandQL on the reported tasks, showing promise for posterior-sampling driven exploration in tabular settings.", "weaknesses": "- The empirically evaluated “vanilla” algorithm differs from the theoretically analyzed optimistic variant; the latter is not competitive with RLSVI or Staged-RandQL on the reported benchmarks, leaving the practical relevance of the theory unclear. This mismatch makes it difficult to understand the paper’s positioning: the theoretically grounded algorithm underperforms in practice and does not improve existing regret bounds, yet the practical algorithm—which shows promise—is not benchmarked against other practical exploration baselines on more demanding tasks.\n- Experimental coverage is very limited (two toy tabular environments) and omits stronger practical baselines (e.g., recent posterior-sampling or optimistic methods); if the practical implementation departs from the analyzed algorithm, broader comparisons to other exploration strategies become essential, but they are absent here.\n- Presentation can be clarified: the introduction currently reads as an unstructured list of related work rather than positioning the contribution, and some statements about model-based methods could be refined.\n- The “first Bayesian posterior” claim is confusing: several prior works already use posterior-sampling within Q-learning, so the novelty of this phrasing is unclear and should be clarified.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)