Q-learning with Posterior Sampling

## Abstract

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 an online 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 setting, the MDP has 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}),$ $$

with $V_{H+1}(s)=0,\,\forall\,s$. 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$-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 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*(^2^22Or, $\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. We propose a more insightful interpretation of $Q$-learning obtained using Bayesian inference theory (details in Section [3.1](https://arxiv.org/html/2506.00917v3#S3.SS1)). 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) $$

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 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. This uncertainty quantification is useful for managing the exploration-exploitation tradeoff for regret minimization. The exploration methodology is distinct from algorithms that use additive bonuses or randomized perturbations in the estimates.

Figure: Figure 1: Performance comparison of PSQL^∗(a heuristic derived from 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](https://arxiv.org/html/2506.00917v3#A1)).
Refer to caption: figs_09_20/intro_1d.png

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](https://arxiv.org/html/2506.00917v3#S1.F1)) suggest that this is also the case for our Q-learning approach in the tabular RL setting.
(^3^33For 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 as described later in Section [3](https://arxiv.org/html/2506.00917v3#S3), 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.(^4^44The 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 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 et al. (2020); Agrawal et al. (2021); Xiong et al. (2022). The RLSVI algorithm is an approximate value iteration-based 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 a model-based algorithm. (See Section [2.1](https://arxiv.org/html/2506.00917v3#S2.SS1) 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 and Van Roy, 2017; Ouyang et al., 2017; Agrawal and Jia, 2022; Agarwal and Zhang, 2022; Tiapkin et al., 2022). 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 (e.g., DQN Mnih et al. (2013), DDQN van Hasselt et al. (2015), A3C Mnih et al. (2016)).
Provable regret bounds for a simple posterior sampling based Q-learning algorithm like PSQL, therefore, still remains a 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 performance of this simple algorithm compared to contemporary approaches.
(See Section [3](https://arxiv.org/html/2506.00917v3#S3) for algorithm design and Appendix [A](https://arxiv.org/html/2506.00917v3#A1) for experiments.)
- •
We provide a novel derivation of Q-learning as a solution to a 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$-learning (e.g., Jin et al. (2018)) to obtain provable regret bounds. (See Section [3.1](https://arxiv.org/html/2506.00917v3#S3.SS1).)
- •
We prove a near-optimal regret bound of $\tilde{O}(H^{2}\sqrt{SAT})$ for PSQL which closely match the known lower bound of $\Omega(H\sqrt{SAT})$ (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 a more complex posterior sampling based algorithm Staged-RandQL. (See Section [2](https://arxiv.org/html/2506.00917v3#S2), [4](https://arxiv.org/html/2506.00917v3#S4).)
- •
Our regret analysis reveals several key difficulties in combining posterior sampling with DP and TD-learning-based algorithms due to error accumulation in the bootstrapped target; along with novel ideas for overcoming these challenges. (See Section [4.1](https://arxiv.org/html/2506.00917v3#S4.SS1).)

## 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,\ldots,H$ of each episode $k$, the algorithm observes the current state $s_{k,h}$, takes an action $a_{k,h}$ and observes a reward $r_{k,h}$ and the next state $s_{k,h+1}$.

The reward and next state are generated by the environment according to a fixed underlying MDP $({\cal S},{\cal A},R,P)$, so that $\Pr(s_{k,h+1}=s^{\prime}|s_{k,h}=s,a_{k,h}=a)=P_{h}(s,a,s^{\prime}),\mathbb{E}[r_{k,h}|s_{k,h}=s,a_{k,h}=a]=R_{h}(s,a)$. However, the reward functions and the transition probability distributions $R_{h},P_{h},h=1,\ldots,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 ([1](https://arxiv.org/html/2506.00917v3#S1.E1)). Specifically, let $\pi_{k}$ denote the policy used by the algorithm in episode $k$, so that $a_{k,h}=\pi_{k}(s_{k,h})$. We aim to bound regret, defined as

$$ $\textstyle\text{Reg}(K)\mathrel{\mathop{\ordinarycolon}}=\sum_{k=1}^{K}(V_{1}(s_{k,1})-V^{\pi_{k}}(s_{k,1}))$ (4) $$

for any set of starting states $s_{k,1},k=1,\ldots,K$.

Since the algorithm can only observe the environment’s response at a visited state and action, a main challenge in this problem is managing the exploration-exploitation tradeoff. 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 exploration-exploitation 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 a Q-learning algorithm with posterior sampling (PSQL) that achieves the following regret bound. Here $\tilde{O}(\cdot)$ hides absolute constants and logarithmic factors.

###### Theorem 1 (Informal) .

The cumulative regret of our PSQL (Algorithm [1](https://arxiv.org/html/2506.00917v3#alg1) ) in $K$ episodes with horizon $H$ is bounded as
$\text{Reg}(K)\leq\tilde{O}\mathinner{\left(H^{2}\sqrt{SAT}\right)},$ where $T=KH$.

###### Theorem 1 (Informal) .

### 2.1 Related works

**Table 1: Comparison of our regret bound to related works ( Dann et al. (2021) is in function approximation setting).**
|  | Algorithm | Regret | Comments |
| --- | --- | --- | --- |
| UCB | UCBQL (Jin et al., 2018) | $\tilde{O}(H^{1.5}\sqrt{SAT})$ | Q-learning with UCB |
| Q-EarlySettled-Advantage (Li et al., 2021a) | $\tilde{O}(H\sqrt{SAT})$ | Q-learning with UCB |  |
| Posterior sampl. | Conditional Posterior Sampling (Dann et al., 2021) | $\tilde{O}(HSA\sqrt{T})$ | computationally intractable |
| RLSVI (Russo, 2019) | $\tilde{O}(H^{3}S^{1.5}\sqrt{AT})$ | approximate value iteration |  |
| C-RLSVI (Agrawal et al., 2021) | $\tilde{O}(H^{2}S\sqrt{AT})$ | approximate value iteration |  |
| Staged RandQL (Tiapkin et al., 2023) | $\tilde{O}(H^{2}\sqrt{SAT})$ | randomized learning-rates |  |
| PSQL [this work] | $\tilde{O}(H^{2}\sqrt{SAT})$ | Gaussian posteriors on Q-values |  |
| Lower bound (Jin et al., 2018) | $\Omega(H\sqrt{SAT})$ | - |  |

Our work falls under the umbrella of online episodic reinforcement learning on regret minimization in tabular setting. In the category of the Upper Confidence Bound (UCB)-based algorithms, there is a huge body of research both on model-based (Bartlett and Tewari, 2012; Azar et al., 2017; Fruit et al., 2018; Zanette and Brunskill, 2019; Zhang et al., 2020; Boone and Zhang, 2024), and model-free (Jin et al., 2018; Bai et al., 2019; Ménard et al., 2021; Zhang and Xie, 2023; Agrawal and Agrawal, 2024) algorithms. In-fact, Jin et al. (2018) were the first to provide a near-optimal worst-case regret bound of $\tilde{O}(\sqrt{H^{3}SAT})$, subsequently improved to $\tilde{O}(H\sqrt{SAT})$ by Zhang et al. (2020); Li et al. (2021a).

Motivated by the superior empirical performance of Bayesian posterior sampling approaches compared to their UCB counterparts (Chapelle and Li, 2011; Kaufmann et al., 2012; Osband et al., 2013; Osband and Van Roy, 2017; Osband et al., 2019)
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 and Jia, 2017; Tiapkin et al., 2022).
There have been relatively limited studies on model-free, sample-efficient and computationally 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 Iteration (RLSVI) (Osband et al., 2016b, 2019; Russo, 2019; Zanette et al., 2020). In RLSVI, the exploration is carried out by injecting randomized uncorrelated noise to the reward samples, followed by a re-fitting of a $Q$-function estimate by solving a least squares problem on *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 a “superior-than-UCB” empirical performance. However, its worst-case regret bounds (Russo, 2019) remain suboptimal (see Table [1](https://arxiv.org/html/2506.00917v3#S2.T1)) in their dependence on the size of the state space.

More recently, Tiapkin et al. (2023) proposed (RandQL and Staged-RandQL) algorithms that are model-free, tractable and enjoy $\tilde{O}(H^{2}\sqrt{SAT})$ 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 on $Q$-value estimates via learning rate randomization. Our algorithm is much simpler with far lesser randomized sampling steps and in our preliminary experiments (see Figure [1](https://arxiv.org/html/2506.00917v3#S1.F1) and Section [A](https://arxiv.org/html/2506.00917v3#A1)), our PSQL approach with simple Gaussian based posteriors shows better/comparable performance compared to these algorithms.

In Table [1](https://arxiv.org/html/2506.00917v3#S2.T1) we provide a detailed comparison of our results with the above-mentioned related work on posterior sampling algorithms for RL.

## 3 Algorithm design

We first present a 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 be obtained using Bayesian inference. Let $\theta$ denote the Bayesian parameter that we are inferring, which in our case is the quantity $Q_{h}(s,a)$. Given a prior $p$ on $\theta$, log likelihood function $\ell(\theta,\cdot)$, and a sample $z$, the Bayesian posterior $q$ is given by the Bayes rule:

$$ $q(\theta)\propto p(\theta)\cdot\exp(\ell(\theta,z))$ (5) $$

which can also be derived as an optimal solution of the following optimization problem (see Chapter 10 in Bishop and Nasrabadi (2006)), whose objective is commonly referred to as Evidence Lower Bound (ELBO):

$$ $\max_{q}\mathbb{E}_{\theta\sim q}[\ell(\theta,z)]-KL(q||p)$ (6) $$

where $KL(\cdot||\cdot)=\int_{\theta}q(\theta)\log(\frac{q(\theta)}{p(\theta)})$ denotes KL-divergence function.
It is well known that when $p(\cdot)$ is Gaussian, say ${\cal N}(\widehat{\mu},\frac{\sigma^{2}}{n-1})$, and the likelihood given $\theta$ is Gaussian ${\cal N}(\theta,\sigma^{2})$, then the posterior $q(\cdot)$ is given by the Gaussian distribution

$$ $\textstyle{\cal N}(\widehat{\mu},\frac{\sigma^{2}}{n}),\text{ with }\widehat{\mu}\leftarrow(1-\alpha_{n})\widehat{\mu}+\alpha_{n}z$ (7) $$

with $\alpha_{n}=\frac{1}{n}$. Therefore, substituting $\theta$ as $Q_{h}(s,a)$ and $\widehat{\mu}$ as $\widehat{Q}_{h}(s,a)$, the above yields the Q-learning learning update rule ([2](https://arxiv.org/html/2506.00917v3#S1.E2)) with learning rate $\alpha_{n}=\frac{1}{n}$.

A caveat is that the above assumes $z$ to be an unbiased sample from the target distribution, whereas in Q-learning, $z$ is biased due to bootstrapping. In a 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 be adjusted to $\alpha_{n}=\frac{H+1}{H+n}$. In fact, Bayesian inference can also provide a meaningful interpretation of this modified learning rate proposed in Jin et al. (2018).
Consider the following “regularized" Bayesian inference problem (Khan and Rue, 2023) which adds an entropy term to the ELBO objective in ([6](https://arxiv.org/html/2506.00917v3#S3.E6)):

$$ $\max_{q}\mathbb{E}_{\theta\sim q}[\ell(\theta,z)]-KL(q||p)+\lambda_{n}{\cal H}(q)$ (8) $$

where ${\cal H}(q)$ denotes the entropy of the posterior. We show in Lemma [B.1](https://arxiv.org/html/2506.00917v3#Thmlemma1a) (refer Appendix [B](https://arxiv.org/html/2506.00917v3#A2)) that for the choice of $\lambda_{n}=\frac{H}{n}$, when the prior $p(\theta)$ is Gaussian ${\cal N}(\widehat{\mu},\frac{\sigma^{2}}{n-1})$, and the likelihood of $z$ given $\theta$ is Gaussian ${\cal N}(\theta,\frac{\sigma^{2}}{H+1})$, then the posterior $q(\cdot)$ is given by the Gaussian distribution
in ([7](https://arxiv.org/html/2506.00917v3#S3.E7)) *with the same learning rate $\alpha_{n}=\frac{H+1}{H+n}$* as suggested in Jin et al. (2018).

Substituting $\theta$ as $Q_{h}(s,a)$ and $\widehat{\mu}$ has $\widehat{Q}_{h}(s,a)$ in ([8](https://arxiv.org/html/2506.00917v3#S3.E8)), we derive that given a Gaussian prior ${\cal N}(\widehat{Q}_{h}(s,a),\frac{\sigma^{2}}{n-1})$ over $Q_{h}(s,a)$, Gaussian likelihood ${\cal N}(Q_{h}(s,a),\frac{\sigma^{2}}{H+1})$ on target $z$, the following posterior maximizes the regularized ELBO objective:

$$ $\textstyle{\cal N}(\widehat{Q}_{h}(s,a),\frac{\sigma^{2}}{n}),\,\text{where}\qquad\widehat{Q}_{h}(s,a)\leftarrow(1-\alpha_{n})\widehat{Q}_{h}(s,a)+\alpha_{n}z,$ (9) $$

where $\alpha_{n}=\frac{H+1}{H+n}$, and $n$ is the number of samples for $s,a$ observed so far.

The entropy regularization term of ([8](https://arxiv.org/html/2506.00917v3#S3.E8)) introduces extra uncertainty in the posterior. Intuitively, this makes sense for Q-learning as the target $z$ is bootstrapped on previous interactions and likely has additional bias. The weight $\lambda_{n}$ of this entropy term decreases as the number of samples increases and the bootstrapped target is expected to have lower bias. This derivation may be of independent interest as it provides an intuitive explanation of the modified learning rate schedule proposed ($\frac{H+1}{H+n}$ as compared to $\frac{1}{n}$) in Jin et al. (2018), where it 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

A detailed pseudo-code of our PSQL algorithm is provided as Algorithm [1](https://arxiv.org/html/2506.00917v3#alg1),[2](https://arxiv.org/html/2506.00917v3#alg2).
It uses the current Bayesian posterior to generate samples of $Q$-
values at the current state and all actions, and plays the arg max action. Specifically, at a given episode $k$, let $s_{h}$ be the current state observed in the beginning of the episode and for action $a$, let $N_{h}(s_{h},a)$ be the number of visits of state $s_{h}$ and action $a$ before this episode. Let $\widehat{Q}_{h}(s_{h},a)$ be the current estimate of the posterior mean, and

$$ $\displaystyle\textstyle\sigma(n)=\frac{\sigma^{2}}{n+1}\mathrel{\mathop{\ordinarycolon}}=64\frac{H^{3}}{n+1}\log(KH/\delta).$ (10) $$

Then, the algorithm samples for each $a$,

$$ $\tilde{Q}_{h}(s_{h},a)\sim{\cal N}(\widehat{Q}_{h}(s_{h},a),\sigma(N_{h}(s_{h},a))^{2})$ $$

and plays the arg max action
$a_{h}\mathrel{\mathop{\ordinarycolon}}=\arg\max_{a}\tilde{Q}_{h}(s_{h},a)$.

The algorithm then observes a reward $r_{h}$ and the next state $s_{h+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 $r_{h}+\max_{a^{\prime}}\tilde{Q}_{h+1}(s_{h+1},a^{\prime})$, which we refer to as the “vanilla version" or PSQL*. However, due to unresolvable difficulties in regret analysis discussed later in Section [4](https://arxiv.org/html/2506.00917v3#S4), the PSQL algorithm computes the target in a slightly optimistic manner ($r_{h}+\overline{V}_{h+1}(s)$) as we describe later in this section. Our experiments (Appendix [A](https://arxiv.org/html/2506.00917v3#A1)) show that although this modification does impact performance, PSQL still remains significantly superior to its UCB counterpart.

Figure: Algorithm 1 Q-learning with Posterior Sampling (PSQL)

Figure: Algorithm 2 ConstructTarget($h,r,s^{\prime},\widehat{Q},N)$

Specifically, given reward $r_{h}=r$ and next state $s_{h+1}=s^{\prime}$, a value function estimate $\overline{V}_{h+1}(s^{\prime})$ is computed as the maximum of $J$ samples from the posterior on $Q_{h+1}(s^{\prime},\widehat{a})$, with $\widehat{a}$ being the arg max action of posterior mean + standard deviation.
That is, let

$$ $\widehat{a}\mathrel{\mathop{\ordinarycolon}}=\arg\max_{a}\widehat{Q}_{h+1}(s^{\prime},a)+\sigma(N_{h+1}(s^{\prime},a)),\text{ and }{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\overline{V}_{h+1}(s^{\prime})=\max_{j\in J}\tilde{V}^{j}},$ $$

$$ $\displaystyle\mbox{ with }\textstyle J=J(\delta)\coloneqq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{\log(SAT/\delta)}{\log(4/(4-p_{1}))}},\quad p_{1}=\Phi(-1)-\frac{\delta}{H}-\delta.$ (11) $$

Observe that the above procedure computes a $\overline{V}_{h+1}(s^{\prime})$ that is more optimistic than single sample maximum (i.e., "vanilla version" $\max_{a^{\prime}}\tilde{Q}_{h}(s^{\prime},a^{\prime})$). However, the optimism is limited only to the target computation not to the main decision-making in Line 6, marking an important departure from UCB based optimism (e.g., Jin et al. (2018)). Multiple sampling from the posteriors is a common technique considered in the past works (Tiapkin et al., 2022; Agrawal and Jia, 2017; Agrawal et al., 2017) to aid analysis. Finally, the algorithm uses the computed target $z=r_{h}+\overline{V}_{h+1}(s_{h+1})$ to update the posterior mean via the Q-learning update rule, with $\alpha_{n}=\frac{H+1}{H+n}$:

$$ $\widehat{Q}_{h}(s,a)\leftarrow(1-\alpha_{n})\widehat{Q}_{h}(s,a)+\alpha z.$ $$

Let $n=N_{k,h}(s,a)$, then Algorithm [1](https://arxiv.org/html/2506.00917v3#alg1) implies ($\alpha_{n}^{0}\coloneqq\Pi_{j=1}^{n}(1-\alpha_{j})$ and $\alpha_{n}^{i}\coloneqq\alpha_{i}\Pi_{j=i+1}^{n}(1-\alpha_{j})$),

$$ $\displaystyle\widehat{Q}_{k,h}(s,a)=\alpha_{n}^{0}H+\sum_{i=1}^{n}\alpha_{n}^{i}\mathinner{\left(r_{k_{i},h}+\overline{V}_{k_{i},h+1}(s_{k_{i},h+1})\right)}.$ (12) $$

## 4 Regret Analysis

We prove the following regret bound for PSQL.

###### Theorem 2 .

The cumulative regret of PSQL (Algorithm [1](https://arxiv.org/html/2506.00917v3#alg1),[2](https://arxiv.org/html/2506.00917v3#alg2)) in $K$ episodes satisfies

$$ $\displaystyle\textstyle\text{Reg}(K)\mathrel{\mathop{\ordinarycolon}}=(\sum_{k=1}^{K}V^{*}_{1}(s_{k,1})-V_{1}^{\pi_{k}}(s_{k,1}))\leq O\mathinner{\left(H^{2}\sqrt{SAT}\chi\right)},$ $$

with probability at least $1-\delta$, where $\chi=\log(JSAT/\delta)$ and $T=KH$.

###### Theorem 2 .

### 4.1 Challenges and techniques.

Most of the unique challenges for the theoretical analysis of Q-learning with posterior sampling are associated with the bootstrapped nature of TD-learning itself. As shown in ([12](https://arxiv.org/html/2506.00917v3#S3.E12)), mean estimate at the given step $h$ depends on a weighted average of the past next-step $h+1$ estimates, causing the errors at $h+1$ of the past estimates propagate to the estimate at step $h$. In model-based methods(e.g., Azar et al. (2017); Osband and Van Roy (2017); Zanette et al. (2020)) such issues are non-existent as they recalculate their estimates from scratch at each time step.

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 $k$ can be decomposed as:

$$ $\displaystyle\textstyle V^{*}_{1}(s_{k,1})-V^{\pi_{k}}_{1}(s_{k,1})\leq\underbrace{\textstyle(V^{*}_{1}(s_{k,1})-\tilde{Q}_{k,1}(s_{k,1},a_{k,1}))}_{\text{Optimism error}}+\underbrace{\textstyle(\tilde{Q}_{k,1}(s_{k,1},a_{k,1})-V^{\pi_{k}}_{1}(s_{k,1}))}_{\text{Estimation error}}.$ (13) $$

In algorithms like UCBQL (Jin et al., 2018), there is no optimism error since the UCB estimate is a high-confidence upper bound on the optimal value function. Prior posterior sampling approaches (Agrawal and Goyal, 2012, 2017; Russo, 2019; Agrawal et al., 2021) were able to bound optimism error by proving a 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 if we have a constant probability $p$ of optimism of posteriors on value functions in state $H$. The optimism of stage $H-1$ value requires optimism of stage $H$ value; leading to $p^{2}$ probability of optimism in stage $H-1$. Continuing this way, we get an exponentially small probability of optimism for stage $1$.

Multiple sampling from the posteriors only partially helps.
To get around the issues with constant probability optimism, many posterior sampling algorithms (e.g., model-based PSRL Agrawal and Jia (2022), MNL-bandit Agrawal et al. (2017),Tiapkin et al. (2022) etc.) taking max over multiple (say $J$) samples from the posterior in order to get high probability optimism. We follow a 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 to exponential (in $H$) accumulation of errors, even for $J$ as small as $2$. Below, we provide a rough argument.

We expect the bias of $\tilde{Q}_{h}$ (sample from the posterior distribution) to track $Q^{*}_{h}$ with error that scales as standard deviation of $\tilde{Q}_{h}$) (lets call that error as $\epsilon)$. Now, suppose $J$ samples are used in decision-making (i.e., we take multiple samples from the posterior distributions at Line 6 of Algorithm [1](https://arxiv.org/html/2506.00917v3#alg1)). We incur regret whenever the bias of $\max_{j}\tilde{Q}^{j}$ exceeds $Q^{*}$.
Using the standard techniques, this error at step $H$ has an error bound of $\epsilon\sqrt{J\log(1/\delta)}$ with probability $1-\delta$. This error subsequently propagates multiplicatively via bootstrapping of Bellman equation. For the step $H-1$, the optimism error contribution will be $\epsilon\sqrt{J^{2}\log(1/\delta)}$ with probability $1-\delta$. Continuing this argument, at step $1$, the cumulative optimism error will be of the order $\epsilon\sqrt{J^{H}\log(1/\delta)}$, i.e., exponential in $H$ for any $J\geq 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.

Our techniques. The design of target computation procedure is pivotal to PSQL. Our algorithm design is characterized by two key items: (1) using optimistic posterior sampling in target computation *only*; (2) using the argmax action $\widehat{a}$ of the posterior mean (with a standard deviation offset) in our target computation.

First is motivated by the observation that to 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 $\widehat{a}$ is a special action, whose standard deviation is close to the the played action $a_{h}$ with constant probability (Lemma [C.2](https://arxiv.org/html/2506.00917v3#Thmlemma2a)). As a result, we are able to demonstrate that as in the standard Q-learning $\overline{V}_{h}(s_{h})$ (defined with $\widehat{a}$) cannot be too far from $\tilde{Q}_{h}(s_{h},a_{h})$. Intuitively they are tracking the similar quantities. In summary, our algorithm uses a combination of vanilla (single-sample) and optimistic (multiple-sample) posterior sampling for action selection and target computation, respectively.

### 4.2 Proof sketch

We provide a proof sketch for Theorem [2](https://arxiv.org/html/2506.00917v3#Thmtheorem2). All the missing details from this section are in Appendix [C](https://arxiv.org/html/2506.00917v3#A3). Here, we use $\tilde{Q}_{k,h},\widehat{Q}_{k,h},\overline{V}_{k,h},N_{k,h}$, to denote the values of $\tilde{Q}_{h},\widehat{Q}_{h},\overline{V}_{h},N_{h}$, respectively at the beginning of episode $k$ of Algorithm [1](https://arxiv.org/html/2506.00917v3#alg1), [2](https://arxiv.org/html/2506.00917v3#alg2). And, as before, $s_{k,h},a_{k,h}$ denote the state and action visited at episode $k$, step $h$.

Following the regret decomposition in ([13](https://arxiv.org/html/2506.00917v3#S4.E13)) 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 $\overline{V}_{k,h}$ is a tracking upper bound (optimistic estimate) to $V^{*}_{h}$. Second and the most crucial bit is to show that deviation of $\overline{V}_{k,h}(s_{k,h})$ from the sample used in decision-making, $\tilde{Q}_{k,h}(s_{k,h},a_{k,h})$, can be tractably bounded across rounds of interactions. This combined with the optimism of $\overline{V}_{k,h}$, naturally bounds the optimism error. Third we demonstrate the estimation error has a recursive structure, i.e., error at step $h$ depends on error at $h+1$ and terms attributed to stochasticity in the model; and deviation of $\overline{V}_{k,h}(s_{k,h})$ from $\tilde{Q}_{k,h}(s_{k,h},a_{k,h})$. Therefore, first two parts are utilized to prove estimation error bound.

(a) $\overline{V}_{k,h}$ used in the target, is an optimistic estimate of $V^{*}_{h}$

###### Lemma 1 (Abridged) .

For any episode $k$ and index $h$, the following holds with probability at least $1-\delta/KH$,

$$ $\overline{V}_{k,h}(s_{k,h})\geq V^{*}_{h}(s_{k,h}),$ $$

where $\delta$ is a parameter of PSQL used to define the number of samples $J$ used to compute the target.

The above is an abridged version of Lemma [C.1](https://arxiv.org/html/2506.00917v3#Thmlemma1b). The proof of which inductively uses the optimism and estimation error bounds available for the next stage ($h+1$) to bound the estimation error in the posterior mean $\widehat{Q}_{h}(s,a)$. Then, anti-concentration (i.e., lower tail bounds) of the Gaussian posterior distribution provides the desired constant probability optimism.

(b) $\overline{V}_{k,h}(s_{k,h})$ used in the target, is not far away from $\tilde{Q}_{k,h}(s_{k,h},a_{k,h})$.
The following lemma is an abridged version of Lemma [C.3](https://arxiv.org/html/2506.00917v3#Thmlemma3a) and tells us that the gap is of the order of $\sigma(N_{k,h}(s_{k,h},a_{k,h}))$ which goes down (see ([10](https://arxiv.org/html/2506.00917v3#S3.E10))) as $s_{k,h},a_{k,h}$ is visited often with rate $1/\sqrt{N_{k,h}(s_{k,h},a_{k,h})}$. This is central to our analysis.

###### Lemma 2 (Abridged) .

In Algorithm [1](https://arxiv.org/html/2506.00917v3#alg1), with probability $1-2\delta$, the following holds for all $k\in[K]$ and $h\in[H]$,

$$ $\displaystyle\overline{V}_{k,h}(s_{k,h})-\tilde{Q}_{k,h}(s_{k,h},a_{k,h})\leq\tilde{O}(\sigma(N_{k,h}(s_{k,h},a_{k,h}))),$ $$

where $\tilde{O}(\cdot)$ hides multiplicative logarithmic terms.

The challenge here is that $\overline{V}_{k,h+1}(s_{k,h+1})$ is obtained by sampling from the posterior of $\tilde{Q}(s_{k,h+1},\cdot)$ at action $\widehat{a}$ ($\coloneqq\operatorname*{arg\,max}_{a}\widehat{Q}_{k,h}(s_{k,h},a)+\sigma(N_{k,h}(s_{k,h},a))$) and not $a_{k,h+1}$ ($\coloneqq\operatorname*{arg\,max}_{a}\tilde{Q}_{k,h}(s_{k,h},a)$). To get around this difficulty, we show in Lemma [C.2](https://arxiv.org/html/2506.00917v3#Thmlemma2a) that $\sigma(N_{k,h}(s_{k,h},\widehat{a}))^{2}<2\sigma(N_{k,h}(s_{k,h},a_{k,h}))^{2}\log(1/\delta)$ with a non-zero probability. Finally, using a probability boosting argument (Lemma [E.1](https://arxiv.org/html/2506.00917v3#Thmlemma1d)) we prove Lemma [2](https://arxiv.org/html/2506.00917v3#Thmlemma2). Combined with Lemma [1](https://arxiv.org/html/2506.00917v3#Thmlemma1) to obtain a high probability optimism error bound.

###### Lemma 3 (Optimism error) .

In Algorithm [1](https://arxiv.org/html/2506.00917v3#alg1), with probability $1-2\delta$, the following holds for all $k\in[K]$ and $h\in[H]$,

$$ $\displaystyle V^{*}_{h}(s_{k,h})-\tilde{Q}_{k,h}(s_{k,h},a_{k,h})\leq\tilde{O}(\sigma(N_{k,h}(s_{k,h},a_{k,h}))),$ $$

where $\tilde{O}(\cdot)$ hides multiplicative logarithmic terms.

(c) Bounding estimation error.
In Q-learning, an estimate of the next stage value function (here, $\overline{V}_{h+1}$) is used to compute the target in order to update the $Q$-value for the current stage (here, the posterior mean $\widehat{Q}_{h}$). As a result, the error in the posterior mean for stage $h$ depends on the error in the value function estimates for $h+1$.

###### Lemma 4 (Posterior mean estimation error) .

With probability at least $1-\delta$, for all $k,h,s,a\in[K]\times[H]\times\mathcal{S}\times\mathcal{A}$,

$$ $\displaystyle\textstyle\widehat{Q}_{k,h}(s,a)-Q^{*}_{h}(s,a)\leq\sqrt{\sigma(N_{k,h}(s,a))^{2}\eta}+\alpha_{n}^{0}H+\sum_{i=1}^{n}\alpha_{n}^{i}\mathinner{\left(\overline{V}_{k_{i},h+1}(s_{k_{i},h+1})-V^{*}_{h+1}(s_{k_{i},h+1})\right)},$ $$

where $n=N_{k,h}(s,a)$, and $\eta=\log(SAKH/\delta)$. And, $\alpha_{n}^{i}=\alpha_{i}\Pi_{j=i+1}^{n}(1-\alpha_{j}),\,i>0$, with $\alpha_{n}^{0}=\Pi_{j=1}^{n}(1-\alpha_{j})$.

Conceivably, we should be able to apply the above lemma inductively to obtain an estimation error bound (Lemma [5](https://arxiv.org/html/2506.00917v3#Thmlemma5)). Lemma [2](https://arxiv.org/html/2506.00917v3#Thmlemma2) again plays a crucial role in the above recursive bound.

###### Lemma 5 (Cumulative estimation error.) .

With probability at least $1-\delta$, the following holds for all $h\in[H]$,

$$ $\displaystyle\textstyle\sum_{k=1}^{K}\mathinner{\left(\tilde{Q}_{k,h}(s_{k,h},a_{k,h})-V^{\pi_{k}}_{h}(s_{k,h})\right)}$ $\displaystyle\leq$ $\displaystyle O\mathinner{\left(H^{2}\sqrt{SAT}\log(JSAT/\delta)\right)}.$ $$

(c) Putting it all together. To obtain the final regret bound, we simply sum up the optimism error bound in Lemma [3](https://arxiv.org/html/2506.00917v3#Thmlemma3) for $K$ episodes and add it to the cumulative estimation error bound above.

###### Lemma 1 (Abridged) .

###### Lemma 2 (Abridged) .

###### Lemma 3 (Optimism error) .

###### Lemma 4 (Posterior mean estimation error) .

###### Lemma 5 (Cumulative estimation error.) .

## 5 Conclusion

We presented a posterior sampling-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 are provided in Appendix [A](https://arxiv.org/html/2506.00917v3#A1).) We proved a $\tilde{O}(H^{2}\sqrt{SAT})$ regret bound in a 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 a single sample from next stage posterior in the target computation. The vanilla version outperforms Algorithm [1](https://arxiv.org/html/2506.00917v3#alg1) empirically but is significantly harder to analyze. Another avenue is tightening the $H$ dependence in the regret bound; Appendix [F](https://arxiv.org/html/2506.00917v3#A6) outlines a sketch for improving it by $\sqrt{H}$ although at the expense of making the algorithm more complex. Further refinements are potentially achievable using techniques from Li et al. (2021a); Zhang et al. (2020).

## References

- Agarwal and Zhang (2022)
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.
- Agrawal and Agrawal (2024)
Priyank Agrawal and Shipra Agrawal.
Optimistic q-learning for average reward and episodic reinforcement learning.
*arXiv preprint arXiv:2407.13743*, 2024.
- Agrawal et al. (2021)
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, pages 6566–6573, 2021.
- Agrawal and Goyal (2012)
Shipra Agrawal and Navin Goyal.
Analysis of thompson sampling for the multi-armed bandit problem.
In *Conference on learning theory*, pages 39–1. JMLR Workshop and Conference Proceedings, 2012.
- Agrawal and Goyal (2017)
Shipra Agrawal and Navin Goyal.
Near-optimal regret bounds for thompson sampling.
*Journal of the ACM (JACM)*, 64(5):1–24, 2017.
- Agrawal and Jia (2017)
Shipra Agrawal and Randy Jia.
Optimistic posterior sampling for reinforcement learning: worst-case regret bounds.
In *Advances in Neural Information Processing Systems*, 2017.
- Agrawal and Jia (2022)
Shipra Agrawal and Randy Jia.
Optimistic posterior sampling for reinforcement learning: Worst-case regret bounds.
*Mathematics of Operations Research*, 48(1):363–392, 2022.
- Agrawal et al. (2017)
Shipra Agrawal, Vashist Avadhanula, Vineet Goyal, and Assaf Zeevi.
Thompson sampling for the mnl-bandit.
In *Conference on learning theory*, pages 76–78. PMLR, 2017.
- Azar et al. (2017)
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos.
Minimax regret bounds for reinforcement learning.
In *International Conference on Machine Learning*, pages 263–272. PMLR, 2017.
- Azizzadenesheli et al. (2018)
Kamyar Azizzadenesheli, Emma Brunskill, and Animashree Anandkumar.
Efficient exploration through bayesian deep q-networks.
In *2018 Information Theory and Applications Workshop (ITA)*, pages 1–9. IEEE, 2018.
- Bai et al. (2019)
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.
- Bartlett and Tewari (2012)
Peter L Bartlett and Ambuj Tewari.
Regal: A regularization based algorithm for reinforcement learning in weakly communicating mdps.
*arXiv preprint arXiv:1205.2661*, 2012.
- Bishop and Nasrabadi (2006)
Christopher M Bishop and Nasser M Nasrabadi.
*Pattern recognition and machine learning*, volume 4.
Springer, 2006.
- Boone and Zhang (2024)
Victor Boone and Zihan Zhang.
Achieving tractable minimax optimal regret in average reward mdps.
*arXiv preprint arXiv:2406.01234*, 2024.
- Cesa-Bianchi and Lugosi (2006)
Nicolo Cesa-Bianchi and Gábor Lugosi.
*Prediction, learning, and games*.
Cambridge university press, 2006.
- Chapelle and Li (2011)
Olivier Chapelle and Lihong Li.
An empirical evaluation of thompson sampling.
*Advances in neural information processing systems*, 24, 2011.
- Dann et al. (2021)
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 Processing Systems*, 34:12040–12051, 2021.
- Fan and Ming (2021)
Ying Fan and Yifei Ming.
Model-based reinforcement learning for continuous control with posterior sampling.
In *International Conference on Machine Learning*, pages 3078–3087. PMLR, 2021.
- Fortunato et al. (2017)
Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Ian Osband, Alex Graves, Vlad Mnih, Remi Munos, Demis Hassabis, Olivier Pietquin, et al.
Noisy networks for exploration.
*arXiv preprint arXiv:1706.10295*, 2017.
- Fruit et al. (2018)
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner.
Efficient bias-span-constrained exploration-exploitation in reinforcement learning.
In *International Conference on Machine Learning*, pages 1578–1586. PMLR, 2018.
- Jin et al. (2018)
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan.
Is Q-learning provably efficient?
*Advances in neural information processing systems*, 31, 2018.
- Kaufmann et al. (2012)
Emilie Kaufmann, Nathaniel Korda, and Rémi Munos.
Thompson sampling: An asymptotically optimal finite-time analysis.
In *International conference on algorithmic learning theory*, pages 199–213. Springer, 2012.
- Khan and Rue (2023)
Mohammad Emtiyaz Khan and Håvard Rue.
The bayesian learning rule.
*Journal of Machine Learning Research*, 24(281):1–46, 2023.
- Knoblauch et al. (2022)
Jeremias Knoblauch, Jack Jewson, and Theodoros Damoulas.
An optimization-centric view on bayes’ rule: Reviewing and generalizing variational inference.
*Journal of Machine Learning Research*, 23(132):1–109, 2022.
- Li et al. (2021a)
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:17762–17776, 2021a.
- Li et al. (2021b)
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.
- Ménard et al. (2021)
Pierre Ménard, Omar Darwiche Domingues, Xuedong Shang, and Michal Valko.
Ucb momentum q-learning: Correcting the bias without forgetting.
In *International Conference on Machine Learning*, pages 7609–7618. PMLR, 2021.
- Mnih et al. (2013)
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.
URL [https://arxiv.org/pdf/1312.5602.pdf](https://arxiv.org/pdf/1312.5602.pdf).
- Mnih et al. (2015)
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al.
Human-level control through deep reinforcement learning.
*nature*, 518(7540):529–533, 2015.
- Mnih et al. (2016)
Volodymyr Mnih, Adrià Puigdomènech Badia, Mehdi Mirza, Alex Graves, Timothy P. Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu.
Asynchronous methods for deep reinforcement learning, 2016.
- Osband and Van Roy (2017)
Ian Osband and Benjamin Van Roy.
Why is posterior sampling better than optimism for reinforcement learning?
In *International conference on machine learning*, pages 2701–2710. PMLR, 2017.
- Osband et al. (2013)
Ian Osband, Daniel Russo, and Benjamin Van Roy.
(More) efficient reinforcement learning via posterior sampling.
*Advances in Neural Information Processing Systems*, 26, 2013.
- Osband et al. (2016a)
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy.
Deep exploration via bootstrapped dqn.
*Advances in neural information processing systems*, 29, 2016a.
- Osband et al. (2016b)
Ian Osband, Benjamin Van Roy, and Zheng Wen.
Generalization and exploration via randomized value functions.
In *International Conference on Machine Learning*, pages 2377–2386. PMLR, 2016b.
- Osband et al. (2019)
Ian Osband, Benjamin Van Roy, Daniel J Russo, and Zheng Wen.
Deep exploration via randomized value functions.
*Journal of Machine Learning Research*, 20(124):1–62, 2019.
- Ouyang et al. (2017)
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.
- Russo (2019)
Daniel Russo.
Worst-case regret bounds for exploration via randomized value functions.
*Advances in Neural Information Processing Systems*, 32, 2019.
- Sasso et al. (2023)
Remo Sasso, Michelangelo Conserva, and Paulo Rauber.
Posterior sampling for deep reinforcement learning.
In *International Conference on Machine Learning*, pages 30042–30061. PMLR, 2023.
- Sutton (1988)
Richard S Sutton.
Learning to predict by the methods of temporal differences.
*Machine learning*, 3:9–44, 1988.
- Thompson (1933)
William R Thompson.
On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.
*Biometrika*, 25(3/4):285–294, 1933.
- Tiapkin et al. (2022)
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.
- Tiapkin et al. (2023)
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*, 36:73719–73774, 2023.
- van Hasselt et al. (2015)
Hado van Hasselt, Arthur Guez, and David Silver.
Deep reinforcement learning with double q-learning, 2015.
- Wainwright (2019)
Martin J Wainwright.
*High-dimensional statistics: A non-asymptotic viewpoint*, volume 48.
Cambridge University Press, 2019.
- Watkins and Dayan (1992)
Christopher JCH Watkins and Peter Dayan.
Q-learning.
*Machine learning*, 8:279–292, 1992.
- Xiong et al. (2022)
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.
- Zanette and Brunskill (2019)
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*, pages 7304–7312. PMLR, 2019.
- Zanette et al. (2020)
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric.
Frequentist regret bounds for randomized least-squares value iteration.
In *International Conference on Artificial Intelligence and Statistics*, pages 1954–1964. PMLR, 2020.
- Zhang and Xie (2023)
Zihan Zhang and Qiaomin Xie.
Sharper model-free reinforcement learning for average-reward markov decision processes.
In *The Thirty Sixth Annual Conference on Learning Theory*, pages 5476–5477. PMLR, 2023.
- Zhang et al. (2020)
Zihan Zhang, Yuan Zhou, and Xiangyang Ji.
Almost optimal model-free reinforcement learningvia reference-advantage decomposition.
*Advances in Neural Information Processing Systems*, 33:15198–15207, 2020.

#### The Use of Large Language Models

Commonly availaible LLM tools were only used to 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.

## Appendix A Experiments

In section [4](https://arxiv.org/html/2506.00917v3#S4), we proved that our Q-learning with posterior sampling algorithm  PSQL enjoys regret bounds comparable to its UCB-counterparts, e.g., Jin et al. [2018]. In this section, we present empirical results that validate our theory and compare the empirical performance of the posterior sampling approach against several benchmark UCB-based and randomized algorithms for reinforcement learning.

For the empirical studies, we use the vanilla version of posterior sampling, which we denote as PSQL* (see Figure [1](https://arxiv.org/html/2506.00917v3#S1.F1)). In this vanilla version, the target computation at a step $h$ is the default $z=r_{h}+\max_{a^{\prime}}\tilde{Q}_{h+1}(s_{h+1},a^{\prime})$. As discussed in Section [3.2](https://arxiv.org/html/2506.00917v3#S3.SS2), 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 of PSQL and PSQL*. While the modified target computation does slightly deteriorate the performance of PSQL, in our experiments, it still performs significantly better compared to the benchmark UCB-based approach Jin et 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-learning regret analysis.
- •
RLSVI Russo [2019]: a popular randomized algorithm that implicitly maintains posterior distributions on Value functions.
- •
Staged-RandQL Tiapkin et al. [2023]: a 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 average performance over 10 randomly sampled instances.

- •
(One-dimensional “chain” MDP:) An instance of this MDP is defined by two parameters $p\in[0.7,0.95]$ and $S\in\{7,8,9,\ldots,14\}$. In a random instance, $p,\&\,S$ are chosen randomly from the given ranges. The resultant MDP environment is a chain in which the agent starts at state 0 (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$.
- •
(Two-dimensional “grid-world” MDP, similar to FrozenLake environment in the popular Gymnasium library:) A random instance of this MDP is defined by a $4\times 4$ grid with a random number of “hole” states placed at on the grid uniformly at random that the agent must avoid or 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 to the goal state that avoids all hole states. At 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 to 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 is 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 is 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 a fair comparison:

- •
$\delta$ is fixed for all algorithms as $0.05$.
- •
In UCBQL Jin et al. [2018], the Q-function estimates are initialized as the maximum value of any state in the environment ($\eqqcolon V_{\max}$). The exploration bonus for any $h,s,a$ with visit counts as $n$ is given by
$\sqrt{c\frac{V^{2}_{\max}\log(SAT/\delta)}{n}},$
with $c=0.01$
- •
In PSQL and PSQL*, the Q-function posterior means are initialized as $V_{\max}$ (same as UCBQL) and the standard deviation of the posterior for any $h,s,a$ with $n$ visits is given by
$\sqrt{c\frac{V^{2}_{\max}}{\max\{1,n\}}},$
with $c=0.02$.
- •
In RLSVI Russo [2019], the per-reward perturbation is a mean zero Gaussian with standard deviation for any $h,s,a$ with $n$ visits is given by,
$\sqrt{c\frac{V^{2}_{\max}\log(SAT/\delta)}{n+1}},$
with $c=0.005$.
- •
In Staged-RandQL Tiapkin et al. [2023], for the initialization of the Q-function estimates, we use a tighter upper bound of $(H-h)/H$ at step $h$ available in our environment, instead of the default $H-h$ suggested in their paper.
We use $n_{0}=1/S$ and $r_{0}=1$ as in their paper.

Our results are summarized in Figure [2](https://arxiv.org/html/2506.00917v3#A1.F2) and [3](https://arxiv.org/html/2506.00917v3#A1.F3). The error bars represent one standard deviation interval around the mean cumulative regret of an algorithm over 10 runs on randomly generated instances of the environment.

Figure: (a) One-dimensional “chain” MDP
Refer to caption: figs_09_20/1d_4algo.png

We observe that the randomized/posterior sampling algorithms PSQL*, RLSVI, and Staged-RandQL, have lower regret than their UCB counterpart: UCBQL. Also, PSQL* has significantly lower regret than the other two randomized algorithms.

A direct practical implication is that, PSQL* enjoys a 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.

In Figure [3](https://arxiv.org/html/2506.00917v3#A1.F3), we compare the performance of PSQL*,
the single sample vanilla version of posterior sampling, with the PSQL algorithm for which we provided regret bounds. As we explained in Section [4.1](https://arxiv.org/html/2506.00917v3#S4.SS1) (Challenges and Techniques), in order to achieve optimism in the target, PSQL computed the next state value by taking the max over multiple samples from the posterior of empirical mean maximizer action $\widehat{a}=\arg\max_{a}\widehat{Q}_{h}(s_{h},a)+\sigma(N_{h}(s_{h},a))$. This introduces some extra exploration, and as a result, we observe that
PSQL* displays a more efficient exploration-exploitation tradeoff, PSQL still performs significantly better than the UCB approach.
These observations motivate an investigation into the theoretical analysis of the vanilla version, which we believe will require significantly new techniques.

Figure: (a) One-dimensional “chain” MDP
Refer to caption: figs_09_20/1d_UCB_with_PSQL.png

## Appendix B Bayesian inference based interpretation for Q-learning

In this section, we describe the mathematical steps for calculating the updated posterior distribution from ([8](https://arxiv.org/html/2506.00917v3#S3.E8)).

First, in Proposition [B.1](https://arxiv.org/html/2506.00917v3#Thmproposition1), we derive the well-known result that solving the optimization problem in ([6](https://arxiv.org/html/2506.00917v3#S3.E6)) gives the posterior distribution as expected by Bayes rule. Let $\theta\in\Theta$ be the Bayesian parameter that we are inferring with $\Delta_{\Theta}$ be the space of distributions on $\Theta$. Let $p(\theta)$, $\ell(\theta,\cdot)$, and $q(\theta)$ be the the current prior distribution on $\theta$, the negative log likelihood function and the posterior distribution to be calculated.

###### Proposition B.1 (Also in Khan and Rue [ 2023 ], Knoblauch et al. [ 2022 ] ) .

Let $KL(q(\theta)||p(\theta))=\int_{\theta}q(\theta)\log(\frac{q(\theta)}{p(\theta)})$.
Given log likellihood function $\ell(\theta,z)$, and prior $p(\theta)$, the distribution $q$ that maximizes ELBO objective,

$$ $\max_{q\in\Delta_{\Theta}}\mathbb{E}_{\theta\sim q}[\ell(\theta,z)]-KL(q(\theta)||p(\theta))$ (14) $$

is given by the Bayes rule

$$ $q^{\text{Bayes}}(\theta)\propto p(\theta)\cdot\exp(\ell(\theta,z)).$ (15) $$

###### Proof.

Note that the ELBO objective function is equivalent to

$$ $\displaystyle-\int_{\theta}\log(\exp(-\ell(\theta,z)q(\theta)-\int_{\theta}\log\mathinner{\left(\frac{q(\theta)}{p(\theta)}\right)}q(\theta)$ $\displaystyle=$ $\displaystyle-\int_{\theta}\log\mathinner{\left(\frac{q(\theta)}{p(\theta)\exp(\ell(\theta,z))}\right)}q(\theta),$ $$

which is maximized when $q(\theta)=q^{\text{Bayes}}(\theta)$.
∎

Now, we study the calculation of the posterior distribution of $Q_{h}(s,a)$ after observing $n+1$ visits of $(h,s,a)$ in Lemma [B.1](https://arxiv.org/html/2506.00917v3#Thmlemma1a).

###### Lemma B.1 .

Consider the following maximization problem (regularized ELBO) over the space $\Delta_{\Theta}$ of distributions over a parameter $\theta$.

$$ $\max_{q\in\Delta_{\Theta}}\mathbb{E}_{\theta\sim q}[\ell(\theta,z)]-KL(q(\theta)||p(\theta))+\lambda_{n}{\cal H}(q(\theta)),$ (16) $$

Then, if $p(\cdot)$ is given by the pdf of the Gaussian distribution ${\cal N}(\widehat{\mu}_{n-1},\frac{\sigma^{2}}{n-1})$, and $\ell(\theta,z)=\log(\phi_{\theta}(z))$ where $\phi_{\theta}(z)=\Pr(z|\theta)$ is the pdf of the Gaussian distribution $\mathcal{N}(\theta,\frac{\sigma^{2}}{H+1})$, and $\lambda_{n}=\frac{H}{n}$; then the optimal solution $q(\cdot)$ to ([16](https://arxiv.org/html/2506.00917v3#A2.E16)) is given by the Gaussian distribution ${\cal N}(\widehat{\mu}_{n},\frac{\sigma^{2}}{n})$, where

$$ $\widehat{\mu}_{n}=(1-\alpha_{n})\widehat{\mu}_{n-1}+\alpha_{n}z,\text{ with }\alpha_{n}=\frac{H+1}{H+n}.$ $$

###### Proof.

Denote the objective value at a given distribution $q$ as $rELBO(q)$. Then,

$$ $\displaystyle rELBO(q)$ $\displaystyle=$ $\displaystyle\int_{\theta}\log(\exp(\ell(\theta,z)q(\theta)-\int_{\theta}\log\mathinner{\left(\frac{q(\theta)}{p(\theta)}\right)}q(\theta)-\lambda_{n}\int_{\theta}\log(q(\theta))q(\theta)$ $\displaystyle=$ $\displaystyle-\int_{\theta}\log\mathinner{\left(\frac{q(\theta)^{1+\lambda_{n}}}{p(\theta)\exp(\ell(\theta,z))}\right)}q(\theta),$ $$

which is maximized at distribution $q$ with $q(\theta)\propto(p(\theta)\exp(\ell(\theta,z)))^{1/(\lambda_{n}+1)}$
Then,

$$ $\displaystyle q(\theta)$ $\displaystyle\propto$ $\displaystyle\exp\mathinner{\left[\frac{1}{\lambda_{n}+1}\mathinner{\left(-\frac{(n-1)\mathinner{\left(\theta-\widehat{\mu}_{n-1}\right)}^{2}}{2\sigma^{2}}-\frac{(H+1)(z-\theta)^{2}}{2\sigma^{2}}\right)}\right]}$ $\displaystyle\propto$ $\displaystyle\exp\mathinner{\left[-\frac{n}{H+n}\mathinner{\left(\frac{\theta^{2}(H+n)-2\theta((n-1)\widehat{\mu}_{n-1}+(H+1)z)}{2\sigma^{2}}\right)}\right]}$ $\displaystyle\propto$ $\displaystyle\exp\mathinner{\left[-n\mathinner{\left(\frac{\theta^{2}-2\theta\widehat{\mu}_{n}}{2\sigma^{2}}\right)}\right]}$ $\displaystyle\propto$ $\displaystyle\exp\mathinner{\left[-n\mathinner{\left(\frac{(\theta-\widehat{\mu}_{n})^{2}}{2\sigma^{2}}\right)}\right]}$ $$

where $\widehat{\mu}_{n}=\frac{n-1}{H+n}\widehat{\mu}_{n-1}+\frac{H+1}{H+n}z=(1-\alpha_{n})\widehat{\mu}_{n-1}+\alpha_{n}z$.
∎

###### Proposition B.1 (Also in Khan and Rue [ 2023 ], Knoblauch et al. [ 2022 ] ) .

###### Proof.

###### Lemma B.1 .

###### Proof.

## Appendix C Missing Proofs from Section 4

### C.1 Optimism

###### Lemma C.1 (Unabridged version) .

The samples from the posterior distributions and the mean of the posterior distributions as defined in Algorithm [1](https://arxiv.org/html/2506.00917v3#alg1), [2](https://arxiv.org/html/2506.00917v3#alg2) satisfy the following properties: for any episode $k\in[K]$ and index $h\in[H]$,

- (a)
(Posterior distribution mean)
For any given $s,a$, with probability at least $1-\frac{2(k-1)\delta}{KH}-\frac{\delta}{KH}$,
$\displaystyle\widehat{Q}_{k,h}(s,a)\geq Q^{*}_{h}(s,a)-\sqrt{\sigma(N_{k,h}(s,a))^{2}}.$
(17)
- (b)
(Posterior distribution sample) For any given $s,a$, with probability at least $p_{1}$ ($p_{1}={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\Phi(-1)}$) conditioned on ([17](https://arxiv.org/html/2506.00917v3#A3.E17)) being true,
$\displaystyle\tilde{Q}_{k,h}(s,a)\geq Q^{*}_{h}(s,a).$
(18)
- (c)
(In Algorithm [2](https://arxiv.org/html/2506.00917v3#alg2)) With probability at least $1-\frac{2k\delta}{KH}$, the following holds for all episodes $k^{\prime}\leq k$
$\overline{V}_{k,h}(s_{k,h})\geq V^{*}_{h}(s_{k,h}).$
(19)

Here $\delta$ is a parameter of the algorithm used to define the number of samples $J$ used to compute the target $\overline{V}$.

###### Proof.

We prove the lemma statement via induction over $k,h$.

###### Lemma C.1 (Unabridged version) .

###### Proof.

#### Base case: k = 1 , h ∈ [ H ] k=1,h\in[H] .

Note that $n_{1,h}(s,a)=0$ for all $s,a,h\in\mathcal{S}\times\mathcal{A}\times[H]$. Therefore, $\widehat{Q}_{1,h}(s,a)=H$ for all $s,a,h$ (([17](https://arxiv.org/html/2506.00917v3#A3.E17)) is trivially true). As $Q^{*}_{h}(s,a)\leq H$ for all $s,a,h$, therefore $\tilde{Q}_{1,H}(s,a)\geq Q^{*}_{H}(s,a),$ with probability at least $1/2$ ($>p_{1}$), i.e. ([18](https://arxiv.org/html/2506.00917v3#A3.E18)) is true. By the choice of $J$ and Lemma [E.2](https://arxiv.org/html/2506.00917v3#Thmlemma2c), ([19](https://arxiv.org/html/2506.00917v3#A3.E19)) also follows.

#### Induction hypothesis:

Given $k>1,1\leq h\leq H$, assume that the statements (a),(b), and (c) are true for $1\leq k^{\prime}\leq k-1,h^{\prime}\in[H]$, and for $k^{\prime}=k,h+1\leq h^{\prime}\leq H$ .

#### Induction step:

For $k,h$, we show ([17](https://arxiv.org/html/2506.00917v3#A3.E17)) holds with probability $1-\frac{2(k-1)\delta}{KH}-\frac{\delta}{KH}$, ([18](https://arxiv.org/html/2506.00917v3#A3.E18)) holds with probability at least $p_{1}=\Phi(-1)$ in the event ([17](https://arxiv.org/html/2506.00917v3#A3.E17)) holds , and finally ([19](https://arxiv.org/html/2506.00917v3#A3.E19)) holds with probability $1-\frac{2k\delta}{KH}$.

In case $n_{k,h}(s,a)=0$, then $\widehat{Q}_{k,h}(s,a)=H$ and $b_{k,h}(s,a)>0$ and therefore by the same reasoning as in the base case, the induction statement holds. For the rest of the proof we consider $n_{k,h}(s,a)>0$.

Let $n=N_{k,h}(s,a)$, then Algorithm [1](https://arxiv.org/html/2506.00917v3#alg1) implies,

$$ $\displaystyle\widehat{Q}_{k,h}(s,a)=\alpha_{n}^{0}H+\sum_{i=1}^{n}\alpha_{n}^{i}\mathinner{\left(r_{k_{i},h}+\overline{V}_{k_{i},h+1}(s_{k_{i},h+1})\right)},$ (20) $$

To prove the induction step for ([17](https://arxiv.org/html/2506.00917v3#A3.E17)), consider the following using ([12](https://arxiv.org/html/2506.00917v3#S3.E12)) and Bellman optimality equation.

$$ $\displaystyle\widehat{Q}_{k,h}(s,a)-Q^{*}_{h}(s,a)$ $\displaystyle=$ $\displaystyle\sum_{i=1}^{n}\alpha_{n}^{i}\mathinner{\left(r_{k_{i},h}-r_{h}(s,a)+\overline{V}_{k_{i},h+1}(s_{k_{i},h+1})-P_{h,s,a}V^{*}_{h}\right)}$ (21) $\displaystyle=$ $\displaystyle\sum_{i=1}^{n}\alpha_{n}^{i}\mathinner{\left(r_{k_{i},h}-r_{h}(s,a)+V^{*}_{h+1}(s_{k_{i},h+1})-P_{h,s,a}V^{*}_{h}\right)}$ $\displaystyle+\sum_{i=1}^{n}\alpha_{n}^{i}\mathinner{\left(\overline{V}_{k_{i},h+1}(s_{k_{i},h+1})-V^{*}_{h+1}(s_{k_{i},h+1})\right)}$ (using ( 19 ) from induction hypothesis for $h+1\leq H$ , with probability $1-\frac{2(k-1)\delta}{KH}$ ) (note that this is trivially true when $h+1=H+1$ since $\overline{V}_{k,H+1}=V^{*}_{h+1}=0$ ) $\displaystyle\geq$ $\displaystyle\sum_{i=1}^{n}\alpha_{n}^{i}\mathinner{\left(r_{k_{i},h}-r_{h}(s,a)+V^{*}_{h+1}(s_{k_{i},h+1})-P_{h,s,a}V^{*}_{h}\right)}$ (using Corollary D.2 with probability ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}1-\frac{\delta}{KH}}$ ) $\displaystyle\geq$ $\displaystyle-4\sqrt{\frac{H^{3}{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\log(KH/\delta)}}{n_{k,h}(s,a)+1}}$ $\displaystyle=$ $\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}-\sqrt{\sigma(N_{k,h}(s,a))^{2}}},$ $$

Therefore, with a union bound we have with probability $1-\frac{2(k-1)\delta}{KH}-\frac{\delta}{KH}$,

$$ $\displaystyle\widehat{Q}_{k,h}(s,a)$ $\displaystyle\geq$ $\displaystyle Q^{*}_{h}(s,a)-\sqrt{\sigma(N_{k,h}(s,a))^{2}}$ (22) $$

When ([22](https://arxiv.org/html/2506.00917v3#A3.E22)) holds, then from the definition of cumulative density of Gaussian distribution we get,

$$ $\displaystyle\text{Pr}\mathinner{\left(\tilde{Q}_{k,h}(s,a)\geq\widehat{Q}_{k,h}(s,a)+\sqrt{\sigma(N_{k,h}(s,a))^{2}}\right)}\geq\Phi(-1).$ $$

Now, we show $\tilde{Q}_{k,h}(s,\widehat{a})\geq Q^{*}_{h}(s,a^{*})=V^{*}_{h}(s)$ with probability at least
$\Phi(-1)-\delta-\delta/H$, where

$$ $\widehat{a}=\operatorname*{arg\,max}_{a\in\mathcal{A}}\widehat{Q}_{k,h}(s,a)+\sigma(N(s,a)),\text{ and }a^{*}=\operatorname*{arg\,max}_{a\in\mathcal{A}}Q^{*}_{h}(s,a).$ $$

By the definition of $\widehat{a}$ and properties of Gaussian distribution:

$$ $\underbrace{\tilde{Q}_{k,h}(s,\widehat{a})\geq\widehat{Q}_{k,h}(s,\widehat{a})+\sigma(N(s,\widehat{a}))}_{\text{with probability at least $\phi(-1)$}}\geq\underbrace{\widehat{Q}_{k,h}(s,a^{*})+\sigma(N(s,a^{*}))\geq Q^{*}_{k,h}(s,a^{*})}_{\text{with probability at least $1-2(k-1)\delta/KH-\delta/KH$}}.$ $$

Setting ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}J\geq\frac{\log(KH/\delta)}{\log(1/(1-p_{1}))}}$ in Algorithm [1](https://arxiv.org/html/2506.00917v3#alg1), we use Lemma [E.2](https://arxiv.org/html/2506.00917v3#Thmlemma2c) to show that with probability $1-\frac{\delta}{KH}$

$$ $\displaystyle\overline{V}_{k,h}(s_{k,h})\geq V^{*}_{h}(s_{k,h}).$ (23) $$

Finally we use a union bound to combine ([22](https://arxiv.org/html/2506.00917v3#A3.E22)) and ([23](https://arxiv.org/html/2506.00917v3#A3.E23)) to prove ([19](https://arxiv.org/html/2506.00917v3#A3.E19)) holds with probability at least $1-\frac{2k\delta}{KH}$.

∎

### C.2 Action mismatch bound

###### Lemma C.2 (Bounding action mismatch) .

For a given $k,h,s_{k,h}$, and let $\widehat{a}\coloneqq\operatorname*{arg\,max}_{a}\widehat{Q}_{k,h}(s_{k,h},a)+\sqrt{\sigma(N_{k,h}(s_{k,h},a))^{2}}$,

$$ $\displaystyle\textstyle\sigma(N_{k,h}(s_{k,h},\widehat{a}))^{2}<2\sigma(N_{k,h}(s_{k,h},a_{k,h}))^{2}\log(1/\delta),\quad\text{with probability at least $p_{2}$},$ $$

where $p_{2}=\Phi(-2)-(A)\delta$, and $\delta$ as defined in Theorem [2](https://arxiv.org/html/2506.00917v3#Thmtheorem2).

###### Proof.

Consider the following partition of $A$ actions:

$$ $\displaystyle\overline{\mathcal{A}}$ $\displaystyle\coloneqq$ $\displaystyle\mathinner{\left\{a\mathrel{\mathop{\ordinarycolon}}2\sigma(N(s,a))^{2}\log(1/\delta)>\sigma(N(s,\widehat{a}))^{2}\right\}},$ $\displaystyle\underline{\mathcal{A}}$ $\displaystyle\coloneqq$ $\displaystyle\mathinner{\left\{a\mathrel{\mathop{\ordinarycolon}}2\sigma(N(s,a))^{2}\log(1/\delta)\leq\sigma(N(s,\widehat{a}))^{2}\right\}}.$ $$

Clearly, $\widehat{a}\in\overline{\mathcal{A}}$. We prove that with probability at least $\Phi(-2)-A\delta$, we have $\tilde{a}\in\overline{\mathcal{A}}$, so that $\sigma(N(s,\widehat{a}))^{2}<2\sigma(N(s,a))^{2}\log(1/\delta)$.

By definition of $\widehat{a}$, we have that for all $a$,

$$ $\widehat{Q}(s,a)+{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\sqrt{\sigma(N(s,a))^{2}}}\leq\widehat{Q}(s,\widehat{a}){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}+\sqrt{\sigma(N(s,\widehat{a}))^{2}}}.$ $$

Also, by construction of $\underline{\cal A}$, we have that for $\forall a\in\underline{\mathcal{A}}$,

$$ $\widehat{Q}(s,a)+{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\sqrt{\sigma(N(s,a))^{2}}}+\sqrt{2\sigma(N(s,a))^{2}\log(1/\delta)}\leq\widehat{Q}(s,\widehat{a}){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}+\sqrt{\sigma(N(s,\widehat{a}))^{2}}}+\sqrt{\sigma(N(s,\widehat{a}))^{2}}$ $$

From Gaussian tail bounds (see Corollary [D.1](https://arxiv.org/html/2506.00917v3#Thmcorollary1a)) we have for $\forall a\in\mathcal{A}$,

$$ $\text{Pr}\mathinner{\left(\tilde{Q}(s,a)\leq\widehat{Q}(s,a)+{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\sqrt{\sigma(N(s,a))^{2}}}+\sqrt{2\sigma(N(s,a))^{2}\log(1/\delta)}\right)}\geq 1-A\delta$ $$

so that
$\forall a\in\underline{\mathcal{A}}$,

$$ $\text{Pr}\mathinner{\left(\tilde{Q}(s,a)\leq\widehat{Q}(s,\widehat{a})+{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}2}\sqrt{\sigma(N(s,\widehat{a}))^{2}}\right)}\geq 1-A\delta$ $$

Also for the Gaussian random variable $\tilde{Q}(s,\widehat{a})$, we have with probability at least $\Phi(-{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}2})$,

$$ $\tilde{Q}(s,\widehat{a})>\widehat{Q}(s,\widehat{a})+{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}2}\sqrt{\sigma(N(s,\widehat{a}))^{2}},$ $$

Using a union bound on the last two events,, we get

$$ $\tilde{Q}(s,\widehat{a})>\max_{a\in\underline{\mathcal{A}}}\tilde{Q}(s,a),\quad\text{with probability at least }\Phi(-{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}2})-A\delta.$ (24) $$

Since $\widehat{a}$ is in $\overline{\mathcal{A}}$, in the above scenario, the action $\tilde{a}$ that maximizes $\tilde{Q}(s,\cdot)$ must be in $\overline{\mathcal{A}}$. Therefore, $\sigma(N(s,\widehat{a}))^{2}<2\sigma(N(s,a))^{2}\log(1/\delta)$ with probability $\Phi(-{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}2})-A\delta$.

∎

###### Proposition C.1 (High probability action mismatch) .

For a given $k,h,s_{k,h}$, let $\widehat{a}\coloneqq\operatorname*{arg\,max}_{a}\widehat{Q}_{k,h}(s_{k,h},a)$. Then,

$$ $\displaystyle\sigma(N_{k,h}(s_{k,h},\widehat{a}))<\sigma(N_{k,h}(s_{k,h},a_{k,h}))\sqrt{2\log(1/\delta)}+\frac{1}{p_{2}}\mathbb{E}_{a_{k,h}}[\sigma(N_{k,h}(s_{k.h},a_{k,h}))\sqrt{2\log(1/\delta)}].$ $$

where $p_{2}=\Phi(-2)-(A)\delta$, and $\delta$ as defined in Theorem [2](https://arxiv.org/html/2506.00917v3#Thmtheorem2). Here $\mathbb{E}_{a_{k,h}}[\cdot]$ denotes expectation over $a_{k,h}$ given $s_{k,h}$ and the history before round $k,h$.

###### Proof.

This follows by using previous lemma along with Lemma [E.1](https://arxiv.org/html/2506.00917v3#Thmlemma1d) with $\tilde{X}=\sigma(N_{k,h}(s_{k,h},a_{k,h}))\sqrt{2\log(1/\delta)}$, $X^{*}=\sigma(N_{k,h}(s_{k,h},\widehat{a}))$, and $\underline{X}=0$.
∎

###### Lemma C.2 (Bounding action mismatch) .

###### Proof.

###### Proposition C.1 (High probability action mismatch) .

###### Proof.

### C.3 Target estimation error bound

The following lemma characterizes the target estimation error.

###### Lemma C.3 (Target estimation error) .

In Algorithm [1](https://arxiv.org/html/2506.00917v3#alg1), with probability $1-2\delta$, the following holds for all $k\in[K]$ and $h\in[H]$,

$$ $\displaystyle\overline{V}_{k,h}(s_{k,h})-\tilde{Q}_{k,h}(s_{k,h},a_{k,h})$ $\displaystyle\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}4\sigma(N_{k,h}(s_{k,h},a_{k,h}))\log(JKH/\delta)+\frac{4}{p_{2}}\mathbb{E}_{k,h}[\sigma(N_{k,h}(s_{k,h},a_{k,h}))]\log(JKH/\delta)}$ $\displaystyle\eqqcolon$ $\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{1}{p_{2}}F(k,h,\delta),}$ $$

where $p_{2}=\Phi(-2)-(A)\delta$ and $\delta$ as defined in Theorem [2](https://arxiv.org/html/2506.00917v3#Thmtheorem2), $J$ is defined in ([11](https://arxiv.org/html/2506.00917v3#S3.E11)), and $\mathbb{E}_{a}\mathinner{\left[\cdot\right]}$ denotes expectation over the randomness in the action taken at $k,h$ conditioned on all history at the start of the $h_{\text{th}}$ step in the episode $k$ (i.e., only randomness is that in the sampling from the posterior distribution).

###### Proof.

We have $\arg\widehat{a}=\max_{a}\widehat{Q}_{k,h}(s_{k,h},a)$. For the remainder of the proof, we drop $k,h$ from the subscript and denote $a_{k,h}$ by $\tilde{a}$. From Algorithm [1](https://arxiv.org/html/2506.00917v3#alg1), $\overline{V}(s)$ is the maximum of $J$ samples drawn from a Gaussian distribution with mean as $\widehat{Q}(s,\widehat{a})$ and standard deviation as $\sigma(N(s,\widehat{a}))^{2}$ Using Gaussian tail bounds ( Corollary [D.1](https://arxiv.org/html/2506.00917v3#Thmcorollary1a)) along with a union bound over $J$ samples, for any $\delta\in(0,1)$, with probability at least $1-\delta$,

$$ $\displaystyle\overline{V}(s)$ $\displaystyle\leq$ $\displaystyle\widehat{Q}(s,\widehat{a})+\sqrt{2\sigma(N(s,\widehat{a}))^{2}\log(J/\delta)}$ $\displaystyle\leq$ $\displaystyle\tilde{Q}(s,\widehat{a})+\sqrt{2\sigma(N(s,\widehat{a}))^{2}\log(J/\delta)}+\sqrt{2\sigma(N(s,\widehat{a}))^{2}\log(1/\delta)}$ $$

where $\tilde{Q}(s,\widehat{a})$ is the sample corresponding to the $\widehat{a}$ action drawn by the algorithm at the $k,h$.
Using a union bound to combine the statements, with probability at least $1-2\delta$ we have,

$$ $\displaystyle\overline{V}(s)$ $\displaystyle\leq$ $\displaystyle\tilde{Q}(s,\widehat{a})+2\sqrt{2\sigma(N(s,\widehat{a}))^{2}\log(J/\delta)}$ (25) $\displaystyle\leq$ $\displaystyle\tilde{Q}(s,\tilde{a})+2\sqrt{2\sigma(N(s,\widehat{a}))^{2}\log(J/\delta)}.$ $$

To complete the proof, we use Proposition [C.1](https://arxiv.org/html/2506.00917v3#Thmproposition1a), and an union bound over all $k,h$ to have the following with probability at least $1-2\delta$

$$ $\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\overline{V}_{k,h}(s_{k,h})-\tilde{Q}_{k,h}(s_{k,h},a_{k,h})}$ $\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\leq 4\sigma(N_{k,h}(s_{k,h},a_{k,h}))\sqrt{\log(JKH/\delta)\log(KH/\delta)}+\frac{4}{p_{2}}\mathbb{E}_{k,h}[\sigma(N_{k,h}(s_{k,h},a_{k,h}))]\sqrt{\log(JKH/\delta)\log(KH/\delta)}}.$ $$

∎

###### Lemma C.3 (Target estimation error) .

###### Proof.

### C.4 Optimism error bound

###### Corollary C.1 (Optimism error bound) .

In Algorithm [1](https://arxiv.org/html/2506.00917v3#alg1), with probability $1-3\delta$, the following holds for any $k\in[K]$ and $h\in[H]$,

$$ $\displaystyle V^{*}_{h}(s_{k,h})-\tilde{Q}_{k,h}(s_{k,h},a_{k,h})$ $\displaystyle\leq{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}4\sigma(N_{k,h}(s_{k,h},a_{k,h}))\log(JKH/\delta)+\frac{4}{p_{2}}\mathbb{E}_{k,h}[\sigma(N_{k,h}(s_{k,h},a_{k,h}))]\log(JKH/\delta)}$ $\displaystyle\eqqcolon$ $\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\frac{1}{p_{2}}F(k,h,\delta),}$ $$

where $p_{2}=\Phi(-2)-(A)\delta$ and $\delta$ as defined in Theorem [2](https://arxiv.org/html/2506.00917v3#Thmtheorem2), $J$ is defined in ([11](https://arxiv.org/html/2506.00917v3#S3.E11)), and $\mathbb{E}_{a}\mathinner{\left[\cdot\right]}$ denotes expectation over the randomness in the action taken at $k,h$ conditioned on all history at the start of the $h_{\text{th}}$ step in the episode $k$ (i.e., only randomness is that in the sampling from the posterior distribution).

###### Proof.

From Lemma [C.3](https://arxiv.org/html/2506.00917v3#Thmlemma3a), we have with probability at least $1-2\delta$,

$$ $\displaystyle\overline{V}_{k,h}(s_{k,h})-\tilde{Q}_{k,h}(s_{k,h},a_{k,h})$ $\displaystyle\leq 4\sigma(N_{k,h}(s_{k,h},a_{k,h}))\log(JKH/\delta)+\frac{4}{p_{2}}\mathbb{E}_{k,h}[\sigma(N_{k,h}(s_{k,h},a_{k,h}))]\log(JKH/\delta)$ $\displaystyle\eqqcolon$ $\displaystyle\frac{1}{p_{2}}F(k,h,\delta).$ $$

Further, Lemma [C.1](https://arxiv.org/html/2506.00917v3#Thmlemma1b) (c) gives with probability at least $1-\delta$,

$$ $V^{*}_{h}(s_{k,h})\leq\overline{V}_{k,h}(s_{k,h}).$ $$

We complete the proof via a union bound.
∎

###### Corollary C.2 .

With probability $1-\delta$, the following holds for all $h\in[H]$,

$$ $\displaystyle\sum_{k=1}^{K}V^{*}_{h}(s_{k,h})-\tilde{Q}_{k,h}(s_{k,h},a_{k,h})$ $\displaystyle\leq$ $\displaystyle\mathrm{O}\mathinner{\left(\sqrt{H^{2}SAT}\chi\right)},$ $$

where $\chi=\log(JSAT/\delta)$.

###### Proof.

From Corollary [C.1](https://arxiv.org/html/2506.00917v3#Thmcorollary1), we have for all $k,h$ simultaneously, with probability $1-3\delta$,

$$ $\displaystyle\overline{V}_{k,h}(s_{k,h})-\tilde{Q}_{k,h}(s_{k,h},a_{k,h})$ $\displaystyle\leq 4\sigma(N_{k,h}(s_{k,h},a_{k,h}))\log(JKH/\delta)+\frac{4}{p_{2}}\mathbb{E}_{k,h}[\sigma(N_{k,h}(s_{k,h},a_{k,h}))]\log(JKH/\delta).$ $$

By combining the definition of the variance in ([10](https://arxiv.org/html/2506.00917v3#S3.E10)) with Corollary [D.4](https://arxiv.org/html/2506.00917v3#Thmcorollary4), the result follows easily.
∎

###### Corollary C.1 (Optimism error bound) .

###### Proof.

###### Corollary C.2 .

###### Proof.

### C.5 Posterior mean estimation error bound

See [4](https://arxiv.org/html/2506.00917v3#Thmlemma4)

###### Proof.

First consider a fixed $k,h,s,a$. From ([12](https://arxiv.org/html/2506.00917v3#S3.E12)) and Bellman optimality equation, we have (assume $n=N_{k,h}(s,a)\geq 1$),

$$ $\displaystyle\widehat{Q}_{k,h}(s,a)-Q^{*}_{h}(s,a)$ $\displaystyle=$ $\displaystyle\sum_{i=1}^{n}\alpha_{n}^{i}\mathinner{\left(r_{k_{i},h}-r_{h}(s,a)+\overline{V}_{k_{i},h+1}(s_{k_{i},h+1})-P_{h,s,a}V^{*}_{h}\right)}$ $\displaystyle=$ $\displaystyle\sum_{i=1}^{n}\alpha_{n}^{i}\mathinner{\left(r_{k_{i},h}-r_{h}(s,a)+V^{*}_{h+1}(s_{k_{i},h+1})-P_{h,s,a}V^{*}_{h}\right)}$ $\displaystyle+\sum_{i=1}^{n}\alpha_{n}^{i}\mathinner{\left(\overline{V}_{k_{i},h+1}(s_{k_{i},h+1})-V^{*}_{h+1}(s_{k_{i},h+1})\right)}$ (Using Corollary D.1 with probability $1-\delta$ ) $\displaystyle\leq$ $\displaystyle\sqrt{\sigma(N_{k,h}(s,a))^{2}\log(1/\delta)}+\sum_{i=1}^{n}\alpha_{n}^{i}\mathinner{\left(\overline{V}_{k_{i},h+1}(s_{k_{i},h+1})-V^{*}_{h+1}(s_{k_{i},h+1})\right)}.$ $$

When $N_{k,h}(s,a)=0$, then trivially $\widehat{Q}_{k,h}(s,a)-Q^{*}_{h}(s,a)\leq H=\alpha_{n}^{0}H$, and for $N_{k,h}(s,a)>0$, then $\alpha_{n}^{0}=0$. Combining these two cases and with a union bound over all $s,a,h,k$, we complete the proof.
∎

###### Proof.

### C.6 Cumulative estimation error bound

See [5](https://arxiv.org/html/2506.00917v3#Thmlemma5)

###### Proof.

For the purpose of writing this proof, define $\phi_{k,h}\coloneqq\tilde{Q}_{k,h}(s_{k,h},a_{k,h})-V^{*}_{h}(s_{k,h})$, $\delta_{k,h}\coloneqq\tilde{Q}_{k,h}(s_{k,h},a_{k,h})-V^{\pi_{k}}_{h}(s_{k,h})$, and $\beta_{k,h}\coloneqq\overline{V}_{k,h}(s_{k,h})-V^{*}_{h}(s_{k,h})$. Clearly $\delta_{k,h}\geq\phi_{k,h}$. Further, $v(n_{k,h})\leftarrow\sigma(N_{k,h}(s_{k,h},a_{k,h}))^{2}$.

Now consider,

$$ $\displaystyle\tilde{Q}_{k,h}(s_{k,h},a_{k,h})-V^{\pi_{k}}_{h}(s_{k,h})$ $\displaystyle\leq$ $\displaystyle\tilde{V}_{k,h}(s_{k,h})-Q^{\pi_{k}}_{h}(s_{k,h},a_{k,h})$ (27) $\displaystyle=$ $\displaystyle\tilde{Q}_{k,h}(s_{k,h},a_{k,h})-Q^{*}_{k,h}(s_{k,h},a_{k,h})+Q^{*}_{k,h}(s_{k,h},a_{k,h})-Q^{\pi_{k}}_{1}(s_{k,1},a_{k,1})$ (from Lemma 4 with probability $1-\delta$ , with $n\leftarrow N_{k,h}(s_{k,h},a_{k,h})$ ) $\displaystyle\leq$ $\displaystyle\alpha_{n}^{0}H+\sqrt{2v(n_{k,h})\eta}+\sum_{i=1}^{n}\alpha^{i}_{n}\beta_{k_{i},h+1}+P_{s_{k,h},a_{k,h}}\cdot(V^{*}_{h+1}-V^{\pi_{k}}_{h+1})$ $\displaystyle=$ $\displaystyle\alpha_{n}^{0}H+\sqrt{2v(n_{k,h})\eta}+\sum_{i=1}^{n}\alpha^{i}_{n}\beta_{k_{i},h+1}-\phi_{k,h+1}+\delta_{k,h+1}$ $\displaystyle+P_{s_{k,h},a_{k,h}}\cdot(V^{*}_{h+1}-V^{\pi_{k}}_{h+1})-(V^{*}_{h+1}(s_{k,h+1})-V^{\pi_{k}}_{h+1}(s_{k,h+1}))$ From Lemma C.3 with probability $1-2\delta$ $\displaystyle\leq$ $\displaystyle\alpha_{n}^{0}H+\sqrt{2v(n_{k,h})\eta}+\frac{1}{p_{2}}\sum_{i=1}^{n}\alpha_{n}^{i}F(k_{i},h+1,\delta)+m_{k,h}$ $\displaystyle+\sum_{i=1}^{n}\alpha^{i}_{n}\phi_{k_{i},h+1}-\phi_{k,h+1}+\delta_{k,h+1},$ $$

where

$$ $m_{k,h}\coloneqq P_{s_{k,h},a_{k,h}}\cdot(V^{*}_{h+1}-V^{\pi_{k}}_{h+1})-(V^{*}_{h+1}(s_{k,h+1})-V^{\pi_{k}}_{h+1}(s_{k,h+1})).$ $$

Now, we club all episodes together to have,

$$ $\displaystyle\sum_{k=1}^{K}\delta_{k,h}$ $\displaystyle\leq$ $\displaystyle\sum_{k=1}^{K}\alpha_{n}^{0}H+\sum_{k=1}^{K}\sqrt{4v(n_{k,h})\eta}+\frac{1}{p_{2}}\sum_{k=1}^{K}\sum_{i=1}^{n}\alpha_{n}^{i}F({k_{i},h+1},\delta/KH))+\sum_{h=1}^{H}\sum_{k=1}^{K}m_{k,h}$ $\displaystyle+\sum_{k=1}^{K}\sum_{i=1}^{n}\alpha^{i}_{n}\phi_{k_{i},h+1}-\sum_{k=1}^{K}\phi_{k,h+1}+\sum_{k=1}^{K}\delta_{k,h+1}.$ $$

From Lemma [E.5](https://arxiv.org/html/2506.00917v3#Thmlemma5a) (c), it follows ($a_{k,h}=\{\phi_{k,h},F(k,h,\delta/KH)\})$ $\sum_{k=1}^{K}\sum_{i=1}^{n}\alpha_{n}^{i}a_{k,h+1}\leq(1+1/H)\sum_{k=1}^{K}a_{k,h+1}$. Further from the initialization,

$$ $\displaystyle\sum_{k=1}^{K}\alpha_{n_{k,h}}^{0}H\leq\sum_{k=1}^{K}\mathbb{I}\{n_{k,h}=0\}H\leq SAH=HSA.$ $$

Therefore, we have,

$$ $\displaystyle\sum_{k=1}^{K}\delta_{k,h}$ $\displaystyle\leq$ $\displaystyle\sum_{k=1}^{K}SAH+\sum_{k=1}^{K}\mathinner{\left(\sqrt{4v(n_{k,h})\eta}+m_{k,h}\right)}+(1+1/H)\frac{1}{p_{2}}\sum_{k=1}^{K}F({k,h+1},\delta/KH))+$ $\displaystyle+(1+1/H)\sum_{k=1}^{K}\phi_{k,h+1}-\sum_{k=1}^{K}\phi_{k,h+1}+\sum_{k=1}^{K}\delta_{k,h+1}.$ $$

Unrolling the above $H$ times to have with a union bound over $k,h\in[K]\times[H]$ with probability $1-\delta$ ($\delta$ is scaled by $1/KH$ due to the union bound):

$$ $\displaystyle\sum_{k=1}^{K}\tilde{Q}_{k,1}(s_{k,1},a_{k,1})-V^{\pi_{k}}_{1}(s_{k,1})$ $\displaystyle\leq$ $\displaystyle eSAH^{2}+e\sum_{h=1}^{H}\sum_{k=1}^{K}\mathinner{\left(\sqrt{4v(n_{k,h})\eta}+m_{k,h}\right)}$ (28) $\displaystyle+\frac{e}{p_{2}}\sum_{h=1}^{H}\sum_{k=1}^{K}F({k,h+1},\delta/KH)),$ $$

where we have used $\delta_{k,h}\geq\phi_{k,h}$ and $\delta_{k,H+1}=0$. Now, we analyze each term on the right hand side of ([28](https://arxiv.org/html/2506.00917v3#A3.E28)) one by one.
From Corollary [D.3](https://arxiv.org/html/2506.00917v3#Thmcorollary3),

$$ $\displaystyle\sum_{h=1}^{H}\sum_{k=1}^{K}\sqrt{4v(n_{k,h})\eta}$ $\displaystyle\leq$ $\displaystyle\mathrm{O}\mathinner{\left(\sqrt{H^{4}SAT\eta}\right)}.$ $$

From Corollary [D.4](https://arxiv.org/html/2506.00917v3#Thmcorollary4) with probability at least $1-\delta$,

$$ $\displaystyle\frac{1}{p_{2}}\sum_{h=1}^{H}\sum_{k=1}^{K}\sum_{i=1}^{n}F(k_{i},h+1,\delta/KH)$ $\displaystyle\leq$ $\displaystyle\frac{1+H}{Hp_{2}}\sum_{h=1}^{H}\sum_{k=1}^{K}F(k,h+1,\delta/KH)$ (29) $\displaystyle\leq$ $\displaystyle O(1)\cdot\sum_{h=1}^{H}\sum_{k=1}^{K}\sqrt{v(n_{k,h})\chi\log(KH/\delta)}$ $\displaystyle\leq$ $\displaystyle O\mathinner{\left(\sqrt{H^{4}SAT}\chi\right)},$ (30) $$

where $\chi=\log(JSAT/\delta)$.

Finally, from Lemma [D.1](https://arxiv.org/html/2506.00917v3#Thmlemma1c), we have with probability $1-\delta$

$$ $\displaystyle\sum_{h=1}^{H}\sum_{k=1}^{K}m_{k,h}$ $\displaystyle\leq$ $\displaystyle\mathrm{O}\mathinner{\left(\sqrt{H^{4}T\log(KH/\delta)}\right)}.$ $$

Combining the above, we complete the proof.
∎

See [2](https://arxiv.org/html/2506.00917v3#Thmtheorem2)

###### Proof.

First we combine Corollary [C.2](https://arxiv.org/html/2506.00917v3#Thmcorollary2) and Lemma [5](https://arxiv.org/html/2506.00917v3#Thmlemma5) to get with probability at least $1-\delta$ ($\chi=\log(JSAT/\delta)$),

$$ $\displaystyle\sum_{k=1}^{K}V^{*}_{1}(s_{k,1})-V^{\pi_{k}}_{1}(s_{k,1})\leq O\mathinner{\left(\sqrt{H^{4}SAT}\chi\right)}.$ $$

Observing that the rewards are bound, there $|\sum_{k=1}^{K}\sum_{h=1}^{H}R_{h}(s_{k,h},a_{k,h})-\sum_{k=1}^{K}V^{\pi_{k}}_{1}(s_{k,1})|\leq O(H\sqrt{T\log(1/\delta)})$ with probability at least $1-\delta$. This completes the proof of the theorem.
∎

###### Proof.

###### Proof.

## Appendix D Concentration results

###### Corollary D.1 .

For a given $k,h,s,a\in[K]\times[H]\times\mathcal{S}\times\mathcal{A}$ (let $n=N_{k,h}(s,a)$), with probability $1-\delta$, it holds,

$$ $\displaystyle|\tilde{Q}_{k,h}(s,a)-\widehat{Q}_{k,h}(s,a)|$ $\displaystyle\leq$ $\displaystyle\sqrt{2\sigma(N_{k,h}(s_{k,h},a_{k,h}))^{2}\log(1/\delta)}.$ (31) $$

###### Proof.

The result directly follows form Lemma [E.6](https://arxiv.org/html/2506.00917v3#Thmlemma6).
∎

###### Corollary D.2 .

For some given $k,h,s,a\in[K]\times[H]\times\mathcal{S}\times\mathcal{A}$, the following holds with probability at least $1-\delta$ (with $n=N_{k,h}(s,a)$),

$$ $\displaystyle|\sum_{i=1}^{n}\alpha_{n}^{i}\mathinner{\left(r_{k_{i},h}-R(s,a)+V^{*}_{h+1}(s_{k_{i},h+1})-P_{s,a}V^{*}_{h+1}\right)}|$ $\displaystyle\leq$ $\displaystyle 4\sqrt{\frac{H^{3}\log(1/\delta)}{n+1}}.$ $$

###### Proof.

Let $k_{i}$ denote the index of the episode when $(s,a)$ was visited for the $i_{\text{th}}$ time at step $h$. Set $x_{i}=\alpha_{n}^{i}(r_{k_{i},h}-R_{h}(s,a)+V(s_{i+1})-P_{s_{i},a_{i}}\cdot V)$ and consider filtration $\mathcal{F}_{i}$ as the $\sigma-$field generated by all random variables in the history set $\mathcal{H}_{k_{i},h}$. $r_{k_{i},h}-R_{h}(s,a)+V(s_{i+1})-P_{s_{i},a_{i}}\cdot(V)\leq H+1$. Using the definition of the learning rate (Lemma [E.5](https://arxiv.org/html/2506.00917v3#Thmlemma5a) (b)), we have $\sum_{i}^{n}x^{2}_{i}\leq H(H+1)^{2}/n$. We apply Azuma-Hoeffding inequality (see Lemma [E.3](https://arxiv.org/html/2506.00917v3#Thmlemma3c)) combined with a union bound over all $(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]$ and all possible values of $n\leq K$ to get the following with probability at least $1-\delta$,

$$ $\displaystyle|\sum_{i=1}^{n}x_{i}|$ $\displaystyle\leq$ $\displaystyle 2\sqrt{\frac{2H^{3}\log(1/\delta)}{n}}.$ $$

We complete the proof using the observation $\frac{1}{n+1}\geq\frac{1}{2n},\,n\geq 1$.
∎

###### Lemma D.1 .

with probability at least $1-\delta$, the following holds

$$ $\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}P_{s_{k,h},a_{k,h}}\cdot(V^{*}_{h+1}-V^{\pi_{k}}_{h+1})-(V^{*}_{h+1}(s_{k,h+1})-V^{\pi_{k}}_{h+1}(s_{k,h+1}))\leq H^{2}\sqrt{2T\log(1/\delta)}$ $$

###### Proof.

For $x_{k,h}=P_{s_{k,h},a_{k,h}}\cdot(V^{*}_{h+1}-V^{\pi_{k}}_{h+1})-(V^{*}_{h+1}(s_{k,h+1})-V^{\pi_{k}}_{h+1}(s_{k,h+1}))$ and filtration set $\mathcal{H}_{k,h}$ where $k$ is the episode index, $\{x_{k,h},\mathcal{H}_{k,h}\}$ forms a martingale difference sequence with $|x_{k,h}|\leq H$. We complete the proof using Lemma [E.3](https://arxiv.org/html/2506.00917v3#Thmlemma3c) and a union bound.
∎

###### Lemma D.2 .

Let $\mathcal{D}_{k,h}$ be the distribution of actions at time step $k,h$ conditioned on the history at the start of step $h$ of the $k_{\text{th}}$ episode, then with probability at least $1-\delta$, for some $h$

$$ $\displaystyle\sum_{k=1}^{K}\mathbb{E}_{a\sim\mathcal{D}_{k,h}}\mathinner{\left[\frac{1}{\sqrt{n_{k,h}(s_{k,h},a)+1}}\right]}-\frac{1}{\sqrt{n_{k,h}(s_{k,h},a_{k,h})+1}}\leq O\mathinner{\left(\sqrt{SA\log(K)}\log(1/\delta)\right)}$ $$

###### Proof.

For brevity of exposition, let $\mathbb{E}[Z_{k}]\leftarrow\mathbb{E}_{a\sim\mathcal{D}_{k,h}}\mathinner{\left[\frac{1}{\sqrt{n_{k,h}(s_{k,h},a)+1}}\right]}$, $Z_{k}\leftarrow\frac{1}{\sqrt{n_{k,h}(s_{k,h},a_{k,h})+1}}$, and $\mathcal{F}_{k}\leftarrow\mathcal{H}_{k,h}$. Consider,

$$ $\displaystyle\sum_{k=1}^{K}(\mathbb{E}[Z_{k}]-Z_{k})^{2}$ $\displaystyle\leq$ $\displaystyle(\mathbb{E}[Z_{k}])^{2}+Z_{k}^{2}$ (By Jensen’s inequality for $f(x)=x^{2}$ ) $\displaystyle\leq$ $\displaystyle\sum_{k=1}^{K}Z_{k}^{2}+\sum_{k=1}^{K}\mathbb{E}[Z_{k}^{2}]$ (by linearity of expectation) $\displaystyle=$ $\displaystyle\sum_{k=1}^{K}Z_{k}^{2}+\mathbb{E}\mathinner{\left[\sum_{k=1}^{K}Z_{k}^{2}\right]}$ $\displaystyle\leq$ $\displaystyle\sum_{s,a}\sum_{j=1}^{K}\frac{1}{j+1}+\mathbb{E}\mathinner{\left[\sum_{s,a}\sum_{j=1}^{K}\frac{1}{j+1}\right]}$ $\displaystyle\leq$ $\displaystyle 2SA\log(K).$ $$

To bound $\sum_{k=1}^{K}(\mathbb{E}[Z_{k}]-Z_{k})$, we apply Bernstein inequality for martingale, Lemma [E.4](https://arxiv.org/html/2506.00917v3#Thmlemma4a), with $K=1$, $d=2SA\log(K)$ to get the required result.
∎

###### Lemma D.3 .

$$ $\displaystyle\sum_{k=1}^{K}\frac{1}{\sqrt{N_{k,h}(s_{k,h},a_{k,h})+1}}\leq\mathrm{O}\mathinner{\left(\sqrt{SAK}\right)}$ $$

###### Proof.

$$ $\displaystyle\sum_{k=1}^{K}\frac{1}{\sqrt{N_{k,h}(s_{k,h},a_{k,h})+1}}$ $\displaystyle\leq$ $\displaystyle\sum_{k=1}^{K}\frac{\sqrt{2}}{\sqrt{N_{k,h}(s_{k,h},a_{k,h})}}$ $\displaystyle\leq$ $\displaystyle\mathrm{O}(1)\sum_{s,a}\sum_{k=1}^{N_{K,h(s,a)}}\sqrt{\frac{1}{k}}$ $\displaystyle\leq$ $\displaystyle\mathrm{O}\mathinner{\left(\sqrt{SAK}\right)}.$ $$

∎

###### Corollary D.3 .

The following holds,

$$ $\displaystyle\sum_{h=1}^{H}\sum_{k=1}^{K}\sqrt{4\sigma(N_{k,h}(s_{k,h},a_{k,h}))^{2}\eta}\leq\mathrm{O}\mathinner{\left(\sqrt{H^{4}SAT\eta}\right)}.$ $$

###### Proof.

From Lemma [D.3](https://arxiv.org/html/2506.00917v3#Thmlemma3b) and ([10](https://arxiv.org/html/2506.00917v3#S3.E10)), we get the result.
∎

###### Corollary D.4 .

Let $\mathcal{D}_{k,h}$ be the distribution of actions at time step $k,h$ conditioned on the history at the start of step $h$ of the $k_{\text{th}}$ episode, then with probability at least $1-\delta$

$$ $\displaystyle{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\sum_{k=1}^{K}\frac{4}{p_{2}}\mathbb{E}_{a\sim\mathcal{D}_{k,h}}\mathinner{\left[\sqrt{\sigma(N_{k,h}(s_{k,h},a))^{2}}\log(JKH/\delta)\right]}+\sqrt{2\sigma(N_{k,h}(s_{k,h},a_{k,h}))^{2}}\log(JKH/\delta)}$ $\displaystyle\leq$ $\displaystyle O\mathinner{\left(\sqrt{H^{2}SAT}\chi\right)},$ $$

$\chi=\log(JSAT/\delta)$.

###### Proof.

Using Lemma [D.2](https://arxiv.org/html/2506.00917v3#Thmlemma2b), we have with probability $1-\delta$,

$$ $\displaystyle\sum_{k=1}^{K}\mathbb{E}_{a\sim\mathcal{D}_{k,h}}\mathinner{\left[\frac{1}{\sqrt{n_{k,h}(s_{k,h},a)+1}}\right]}-\frac{1}{\sqrt{n_{k,h}(s_{k,h},a_{k,h})+1}}\leq O\mathinner{\left(\sqrt{SA\log(K)}\log(1/\delta)\right)}$ $$

From Lemma [D.3](https://arxiv.org/html/2506.00917v3#Thmlemma3b) and ([10](https://arxiv.org/html/2506.00917v3#S3.E10)),

$$ $\displaystyle\sum_{k=1}^{K}\frac{4}{p_{2}}\sqrt{\sigma(N_{k,h}(s_{k,h},a))^{2}}\log(JKH/\delta)\leq O\mathinner{\left(\sqrt{H^{2}SAT}\chi\right)},$ $$

which dominates the remaining terms.
∎

###### Corollary D.1 .

###### Proof.

###### Corollary D.2 .

###### Proof.

###### Lemma D.1 .

###### Proof.

###### Lemma D.2 .

###### Proof.

###### Lemma D.3 .

###### Proof.

###### Corollary D.3 .

###### Proof.

###### Corollary D.4 .

###### Proof.

## Appendix E Technical Preliminaries

###### Lemma E.1 (High confidence from constant probability) .

For some fixed scalars $X^{*},\underline{X}$, and $p,\delta\in(0,1)$, suppose that $\tilde{X}\sim\mathcal{D}$ satisfies $\tilde{X}\geq X^{*}$ with probability at least $p$, $\tilde{X}\geq\underline{X}$ with probability at least $1-\delta$, and $\mathbb{E}[\tilde{X}]\geq\underline{X}$. Then, with probability at least $1-2\delta$,

$$ $\displaystyle\textstyle\tilde{X}\geq X^{*}-\frac{1}{p}\mathinner{\left(\mathbb{E}_{\mathcal{D}}[\tilde{X}]-\underline{X}\right)}.$ (32) $$

###### Proof.

For the purpose of this proof, a symmetric sample $\tilde{X}^{\text{alt}}$ also drawn from distribution $\mathcal{D}$ but independent of $\tilde{X}$. Let $\mathcal{O}^{\text{alt}}$ denotes the event when $\tilde{X}^{\text{alt}}\geq X^{*}$ (occurring with probability $p$).

Consider (using notation $\mathbb{E}[\cdot]\leftarrow\mathbb{E}_{\mathcal{D}}[\cdot]$)

$$ $\displaystyle X^{*}-\tilde{X}\leq$ $\displaystyle\mathbb{E}\mathinner{\left[\tilde{X}^{\text{alt}}\mid\mathcal{O}^{\text{alt}}\right]}-\tilde{X}\leq$ $\displaystyle x`x`\mathbb{E}\mathinner{\left[\tilde{X}^{\text{alt}}-\underline{X}\mid\mathcal{O}^{\text{alt}}\right]},$ (33) $$

where the last inequality holds with probability $1-\delta$ by definition of $\underline{X}$.
The law of total expectation suggests,

$$ $\displaystyle\mathbb{E}\mathinner{\left[\tilde{X}^{\text{alt}}-\underline{X}\right]}$ $\displaystyle=$ $\displaystyle\text{Pr}(\mathcal{O}^{\text{alt}})\mathbb{E}\mathinner{\left[\tilde{X}^{\text{alt}}-\underline{X}\mid\mathcal{O}^{\text{alt}}\right]}+\text{Pr}(\overline{\mathcal{O}}^{\text{alt}})\mathbb{E}\mathinner{\left[\tilde{X}^{\text{alt}}-\underline{X}\mid\overline{\mathcal{O}}^{\text{alt}}\right]},$ $$

where $\overline{\mathcal{O}}^{\text{alt}}$ is the compliment of the event $\mathcal{O}^{\text{alt}}$.
Now, $\mathbb{E}\mathinner{\left[\tilde{X}^{\text{alt}}\mid\overline{\mathcal{O}}^{\text{alt}}\right]}=\mathbb{E}\mathinner{\left[\tilde{X}^{\text{alt}}\mid\tilde{X}^{\text{alt}}<X^{*}\right]}\leq\mathbb{E}[\tilde{X}^{\text{alt}}]=\mathbb{E}[\tilde{X}]\leq\underline{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

$$ $\displaystyle\mathbb{E}\mathinner{\left[\tilde{X}^{\text{alt}}-\underline{X}\right]}$ $\displaystyle\leq$ $\displaystyle\text{Pr}(\mathcal{O}^{\text{alt}})\mathbb{E}\mathinner{\left[\tilde{X}^{\text{alt}}-\underline{X}\mid\mathcal{O}^{\text{alt}}\right]}.$ (34) $$

Using $\frac{1}{\text{Pr}(\mathcal{O}^{\text{alt}})}\leq\frac{1}{p}$, $\mathbb{E}[\tilde{X}^{\text{alt}}]=\mathbb{E}[\tilde{X}]$, and a union bound to combine ([33](https://arxiv.org/html/2506.00917v3#A5.E33)) and ([34](https://arxiv.org/html/2506.00917v3#A5.E34)), we complete the proof.
∎

###### Lemma E.2 .

Let $q^{(1)},q^{(2)},\ldots q^{(M)}$ be $M$ i.i.d. samples such that for any $i$, $q^{(i)}\geq V^{*}$ with probability $p$. Then with probability at least $1-\delta$,

$$ $\max_{i\in M}q^{(i)}\geq V^{*},$ $$

when $M$ is at least $\frac{\log(1/\delta)}{\log(1/(1-p))}$.

###### Proof.

For a given index $i$, the probability that $q^{(i)}<V^{*}$ is at most $1-p$. Therefore, by independence of samples, the probability of $\max_{i\in J}q^{(i)}<V^{*}$ is at most $(1-p)^{M}$. Therefore, the lemma statement follows by setting $M=\frac{\log(1/\delta)}{\log(1/(1-p))}$.
∎

###### Lemma E.3 (Corollary 2.1 in Wainwright [ 2019 ] ) .

Let $(\{A_{i},\mathcal{F}_{i}\}_{i=1}^{\infty})$ be a martingale difference sequence, and suppose $|A_{i}|\leq d_{i}$ almost surely for all $i\geq 1$. Then for all $\eta\geq 0$,

$$ $\mathbb{P}\left[|\sum_{i=1}^{n}A_{i}|\geq\eta\right]\leq 2\exp\mathinner{\left(\frac{-2\eta^{2}}{\sum_{i=1}^{n}d_{i}^{2}}\right)}.$ (35) $$

In other words, with probability at most $\delta$, we have,

$$ $|\sum_{i=1}^{n}A_{i}|\geq\sqrt{\frac{ln\mathinner{\left(2/\delta\right)}\sum_{i=1}^{n}d_{i}^{2}}{2}}$ (36) $$

###### Lemma E.4 (Lemma A8 in Cesa-Bianchi and Lugosi [ 2006 ] ) .

Let $(\{A_{i},\mathcal{F}_{i}\}_{i=1}^{\infty})$ be a martingale difference sequence, and suppose $|A_{i}|\leq K$ almost surely for all $i\geq 1$. Let $S_{i}=\sum_{j=1}^{i}A_{i}$ be the associated martingale. Denote the sum of the conditional variances by

$$ $v_{n}^{2}=\sum_{t=1}^{n}\mathbb{E}[A_{i}^{2}\mid\mathcal{F}_{1-1}].$ $$

Then for all constants $t,d>0$,

$$ $\mathbb{P}\mathinner{\left[\max_{i}S_{i}\geq t\,\&\,,v_{n}^{2}\leq d\right]}\leq\exp\mathinner{\left(-\frac{t^{2}}{2(d+Kt/3)}\right)}.$ $$

###### Lemma E.5 (Lemma 4.1 in Jin et al. [ 2018 ] ) .

The following holds:

- (a)
$\frac{1}{\sqrt{n}}\leq\sum_{i=1}^{n}\frac{\alpha^{i}_{n}}{\sqrt{i}}\leq\frac{2}{\sqrt{n}}$.
- (b)
$\max_{i\in n}\alpha_{n}^{i}\leq\frac{2C}{t}$ and $\sum_{i=1}^{n}(\alpha_{n}^{i})^{2}\leq\frac{2C}{t}.$
- (c)
$\sum_{n=i}^{\infty}\alpha^{i}_{n}\leq 1+1/C$.

###### Lemma E.6 (Gaussian tail bound) .

For a Gaussian random variable $X\sim\mathcal{N}(\mu,\sigma^{2})$, it follows with probability at least $1-\delta$,

$$ $\displaystyle\text{Pr}\mathinner{\left(\mathinner{\!\left\lvert X-\mu\right\rvert}\leq\sigma\sqrt{2\log(1/\delta)}\right)}$ $$

###### Proof.

The proof follows by instantiating Chernoff-style bounds for the given Gaussian random variable.
∎

###### Lemma E.1 (High confidence from constant probability) .

###### Proof.

###### Lemma E.2 .

###### Proof.

###### Lemma E.3 (Corollary 2.1 in Wainwright [ 2019 ] ) .

###### Lemma E.4 (Lemma A8 in Cesa-Bianchi and Lugosi [ 2006 ] ) .

###### Lemma E.5 (Lemma 4.1 in Jin et al. [ 2018 ] ) .

###### Lemma E.6 (Gaussian tail bound) .

###### Proof.

## Appendix F Sharper regret using Bernstein concentration

Figure: Algorithm 3 Randomized Q-learning

In this section, we provide a sketch of the extension of Algorithm [1](https://arxiv.org/html/2506.00917v3#alg1) to a 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 [2](https://arxiv.org/html/2506.00917v3#Thmtheorem2).

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 $\mathbb{V}_{h}$ as below,

$$ $\displaystyle[\mathbb{V}_{h}V_{h+1}]_{s,a}\coloneqq\mathbb{E}_{s^{\prime}\sim P_{h,s,a}}\mathinner{\left[V_{h+1}(s^{\prime})-[P_{h,s,a}V_{h+1}]_{s,a}\right]}^{2}.$ (37) $$

The empirical variance for any $(s,a)$ for any $n\leftarrow N_{k,h}(s,a)$ is given by,

$$ $\displaystyle\widehat{\mathbb{V}}_{n}\overline{V}_{h+1}(s,a)=\frac{1}{n}\sum_{i=1}^{n}\left[\overline{V}_{k_{i},h+1}(s_{k_{i},h+1})-\frac{1}{n}\sum_{i=1}^{n}\overline{V}_{k_{i},h+1}(s_{k_{i},h+1})\right]^{2}$ (38) $$

$$ $\displaystyle\sqrt{v_{b}(n,h,s,a)}\coloneqq\min\mathinner{\left\{c(\sqrt{\frac{H}{n+1}\cdot(\widehat{\mathbb{V}}_{n}\overline{V}_{h+1}(s,a)+H)\eta}+\frac{\sqrt{H^{7}SA\eta}\cdot\tau}{n+1}),\sqrt{64\frac{H^{3}}{n+1}}\right\}}.$ (39) $$

###### Theorem F.1 .

The cumulative regret of Algorithm [3](https://arxiv.org/html/2506.00917v3#alg3) in $K$ episode satisfies with probability at least $1-\delta$,

$$ $\displaystyle\sum_{k=1}V^{*}_{1}(s_{k,1})-\sum_{k=1}^{K}\sum_{h=1}^{H}R_{h}(s_{k,h},a_{k,h})\leq O\mathinner{\left(\sqrt{H^{3}SAT\eta}\chi\right)},$ $$

where $\chi=\log(JSAT/\delta)$ and $\eta=\log(SAKH/\delta)$.

###### Theorem F.1 .

### F.1 Proof of Theorem F.1

The main mathematical reasoning closely follows that in the proof of Theorem 2 of Jin et al. [2018] with specific differences arising due to constant probability optimism and the definition of $\overline{V}_{k,h}$. For any $k,h,s,a$ with $n=N_{k,h}(s,a)$, we have $v_{b}(n,h,s,a)\leq 64\frac{H^{3}}{n+1}$. Therefore, Corollary [C.2](https://arxiv.org/html/2506.00917v3#Thmcorollary2) and Lemma [5](https://arxiv.org/html/2506.00917v3#Thmlemma5) apply as they are. Hence, we get with probability at least $1-\delta$ for all $h$

$$ $\displaystyle\sum_{k=1}^{K}r_{k,h}\coloneqq\sum_{k=1}^{K}V^{*}_{h}(s_{k,h})-V^{\pi_{k}}_{h}(s_{k,h})$ $\displaystyle\leq$ $\displaystyle O\mathinner{\left(\sqrt{H^{4}SAT}\chi\right)},$ (40) $$

where $\chi=\log(JSAT/\delta)$.
Further, following the steps and notations of the proof of Lemma [5](https://arxiv.org/html/2506.00917v3#Thmlemma5) (see ([28](https://arxiv.org/html/2506.00917v3#A3.E28)), we have with probability at least $1-\delta$,

$$ $\displaystyle\sum_{k=1}^{K}\tilde{Q}_{k,1}(s_{k,1},a_{k,1})-V^{\pi_{k}}_{1}(s_{k,1})$ $\displaystyle\leq$ $\displaystyle eSAH^{2}+e\sum_{h=1}^{H}\sum_{k=1}^{K}\mathinner{\left(\sqrt{4v_{b}(n,h,s_{k,h},a_{k,h})\eta}+m_{k,h}\right)}$ (41) $\displaystyle+\frac{e}{p_{2}}\sum_{h=1}^{H}\sum_{k=1}^{K}F({k,h+1},\delta/KH)).$ $$

Due to our observation that $v_{b}(n,h,s_{k,h},a_{k,h})\leq 64\frac{H^{3}}{n+1}$, Lemma [D.2](https://arxiv.org/html/2506.00917v3#Thmlemma2b) and Corollary [D.4](https://arxiv.org/html/2506.00917v3#Thmcorollary4) hold, therefore we get from ([41](https://arxiv.org/html/2506.00917v3#A6.E41)),

$$ $\displaystyle\sum_{k=1}^{K}\tilde{Q}_{k,1}(s_{k,1},a_{k,1})-V^{\pi_{k}}_{1}(s_{k,1})$ $\displaystyle\leq$ $\displaystyle eSAH^{2}+\sum_{h=1}^{H}\sum_{k=1}^{K}O\mathinner{\left(\sqrt{v_{b}(n,h,s_{k,h},a_{k,h})}\chi+m_{k,h}\right)},$ $$

where $\chi=\log(JSAT/\delta)$. We wish to bound

$$ $\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}v_{b}(n,h,s_{k,h},a_{k,h})$ (42) $\displaystyle\leq$ $\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}c(\sqrt{\frac{H}{n+1}\cdot(\widehat{\mathbb{V}}_{n}\overline{V}_{h+1}(s_{k,h},a_{k,h})+H)\eta}+\frac{\sqrt{H^{7}SA\eta}\cdot\tau}{n+1}),$ (43) $$

Consider,

$$ $\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\frac{\sqrt{H^{7}SA\eta}\chi}{N_{k,h}(s_{k,h},a_{k,h})+1}\leq O(\sqrt{H^{9}S^{3}A^{3}\chi^{5}}).$ (44) $$

Further,

$$ $\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\sqrt{\frac{H}{n+1}\cdot(\widehat{\mathbb{V}}_{n}\overline{V}_{k,h+1}(s_{k,h},a_{k,h})+H)}$ $\displaystyle\leq$ $\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\sqrt{\frac{H}{n+1}\cdot\widehat{\mathbb{V}}_{n}\overline{V}_{k,h+1}(s_{k,h},a_{k,h})}+\sum_{k=1}^{K}\sum_{h=1}^{H}\sqrt{\frac{H^{2}}{n+1}}$ $\displaystyle\leq$ $\displaystyle\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\widehat{\mathbb{V}}_{n}\overline{V}_{k,h+1}(s_{k,h},a_{k,h})H}+\sqrt{H^{3}SAT\eta},$ (45) $$

where the last inequality follows from Lemma [D.3](https://arxiv.org/html/2506.00917v3#Thmlemma3b). Since we have Lemma [F.5](https://arxiv.org/html/2506.00917v3#Thmlemma5b), we can follow the steps in (C.16) of Jin et al. [2018] to get

$$ $\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\widehat{\mathbb{V}}_{n}\overline{V}_{k,h+1}(s_{k,h},a_{k,h})\leq O(HT).$ $$

This gives us

$$ $\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}v_{b}(n,h,s_{k,h},a_{k,h})\leq O(\sqrt{H^{3}SAT\eta}+\sqrt{H^{9}S^{3}A^{3}\chi^{5}})$ $$

Thus we have,

$$ $\displaystyle\sum_{k=1}^{K}\tilde{Q}_{k,1}(s_{k,1},a_{k,1})-V^{\pi_{k}}_{1}(s_{k,1})\leq O(\sqrt{H^{3}SAT\eta}\chi+\sqrt{H^{9}S^{3}A^{3}\chi^{5}})$ $$

Finally, combining with Corollary [C.2](https://arxiv.org/html/2506.00917v3#Thmcorollary2), we complete the proof.

### F.2 Supporting lemma

###### Corollary F.1 (Corollary of Lemma 4 ) .

We have for all $s,a,h,k\in\mathcal{S}\times\mathcal{A}\times[H]\times[K]$ with probability at least $1-\delta$,

$$ $\displaystyle\widehat{Q}_{k,h}(s,a)-Q^{*}_{h}(s,a)\leq O\mathinner{\left(\sqrt{\frac{H^{3}\eta}{n+1}}\right)}+\alpha_{n}^{0}H+\sum_{i=1}^{n}\alpha_{n}^{i}\mathinner{\left(\overline{V}_{k_{i},h+1}(s_{k_{i},h+1})-V^{*}_{h+1}(s_{k_{i},h+1})\right)},$ (46) $$

where $n=N_{k,h}(s,a)$, and $\eta=\log(SAKH/\delta)$.

###### Proof.

The proof follows from using ([39](https://arxiv.org/html/2506.00917v3#A6.E39)) in place of $\sigma(N_{k,h}(s,a))^{2}$ in Lemma [4](https://arxiv.org/html/2506.00917v3#Thmlemma4).
∎

###### Lemma F.1 (Based on Lemma C.7 in Jin et al. [ 2018 ] ) .

Suppose ([46](https://arxiv.org/html/2506.00917v3#A6.E46)) in Corollary [F.1](https://arxiv.org/html/2506.00917v3#Thmcorollary1b) holds. For any $h\in[H]$, let $\beta_{k,h}\coloneqq\overline{V}_{k,h}(s_{k,h})-V^{*}_{h}(s_{k,h})$ and let $w=(w_{1},\ldots,w_{k})$ be non-negative weight vectors, then we have with probability at least $1-\delta$,

$$ $\displaystyle\sum_{k=1}^{K}w_{k}\beta_{k,h}\leq O(SA||w||_{\infty}\sqrt{H^{7}}\chi^{2}+\sqrt{SA||w||_{1}||w||_{\infty}H^{5}}\chi),$ $$

where $\chi=\log(JSAT/\delta)$.

###### Proof.

For any fixed $k,h$, let $n\leftarrow N_{k,h}(s_{k,h},a_{k,h})$ and $\phi_{k,h}=\tilde{Q}_{k,h}(s_{k,h},a_{k,h})-V^{*}_{h}(s_{k,h})$. Then we have

$$ $\displaystyle\beta_{k,h}$ $\displaystyle=$ $\displaystyle\overline{V}_{k,h}(s_{k,h})-V^{*}_{h}(s_{k,h})$ (47) (from Lemma C.3 with probability at least $1-2\delta$ ) $\displaystyle\leq$ $\displaystyle\phi_{k,h}+\frac{1}{p2}F(k,h,\delta)$ (from Lemma C.5 with probability $1-\delta$ ) $\displaystyle\leq$ $\displaystyle\widehat{Q}_{k,h}(s_{k,h},a_{k,h})-Q^{*}_{h}(s_{k,h},a_{k,h})+\sqrt{2v(n)\eta}+\frac{1}{p_{2}}F(k,h,\delta)$ (from Corollary F.1 with probability $1-\delta$ ) $\displaystyle\leq$ $\displaystyle\alpha_{n}^{0}H+O\mathinner{\left(\sqrt{\frac{H^{3}\eta}{n+1}}\right)}+\sum_{i=1}^{n}\alpha_{n}^{i}\beta_{k_{i},h+1}+\frac{1}{p_{2}}F(k,h,\delta)$ $$

We now compute the summation $\sum_{k=1}^{K}w_{k}\beta_{k,h}$. We follow the proof of Lemma C.7 in Jin et al. [2018], with the only difference being the term $\sum_{k=1}^{K}\frac{w_{k}}{p_{2}}F(k,h,\delta)$, which we bound below. From the proof of Corollary [D.4](https://arxiv.org/html/2506.00917v3#Thmcorollary4).

$$ $\displaystyle\sum_{k=1}^{K}\frac{w_{k}}{p_{2}}F(k,h,\delta)$ $\displaystyle\leq$ $\displaystyle\frac{||w||_{\infty}}{p_{2}}O(SA\sqrt{H^{5}\log^{4}(JSAK/\delta)})+\sum_{k=1}^{K}\frac{2w_{k}}{p_{2}}\mathinner{\left(\sqrt{\frac{H^{3}\chi\log(KH/\delta)}{N_{k,h}+1}}\right)}$ $\displaystyle\leq$ $\displaystyle O(SA||w||_{\infty}\sqrt{H^{5}\chi^{4}}+\sqrt{SA||w||_{1}||w||_{\infty}H^{3}}\chi),$ $$

where $\chi=\log(JSAT/\delta)$. Other terms are evaluated in the same way as the proof of Lemma C.7 in Jin et al. [2018].
∎

###### Lemma F.2 (Based on Lemma C.3 of Jin et al. [ 2018 ] ) .

For any episode $k\in[K]$ with probability $1-\delta/K$, if Corollary [F.1](https://arxiv.org/html/2506.00917v3#Thmcorollary1b) holds for all $k^{\prime}<k$,
the for all $s,a,h\in\mathcal{S}\times\mathcal{A}\times[H]$:

$$ $\displaystyle\mathinner{\!\left\lvert[\mathbb{V}_{h}V_{h+1}]_{s,a}-\widehat{\mathbb{V}}_{n}\overline{V}_{h+1}(s,a)\right\rvert}\leq O\mathinner{\left(\frac{SA\sqrt{H^{9}}\chi^{2}}{n}+\sqrt{\frac{H^{7}SA\chi^{2}}{n}}\right)},$ $$

where $n=N_{k,h}(s_{k,h},a_{k,h})$, $\chi=\log(JSAT/\delta)$.

###### Proof.

The proof is almost identical to that of Lemma C.3 of Jin et al. [2018] except we Lemma [F.1](https://arxiv.org/html/2506.00917v3#Thmlemma1e) instead of Lemma C.7 of Jin et al. [2018].
∎

###### Lemma F.3 .

(Bernstein concentration) For some given $k,h,s,a\in[K]\times[H]\times\mathcal{S}\times\mathcal{A}$, the following holds with probability at least $1-\delta$ (with $n=N_{k,h}(s,a)$),

$$ $\displaystyle|\sum_{i=1}^{n}\alpha_{n}^{i}\mathinner{\left(r_{k_{i},h}-R(s,a)+V^{*}_{h+1}(s_{k_{i},h+1})-P_{s,a}V^{*}_{h+1}\right)}|$ $\displaystyle\leq$ $\displaystyle\sqrt{v_{b}(n,h,s,a)},$ $$

where

$$ $\displaystyle v_{b}(n,h,s,a)\coloneqq\min\mathinner{\left\{c(\sqrt{\frac{H}{n+1}\cdot(\widehat{\mathbb{V}}_{n}\overline{V}_{h+1}(s,a)+H)\eta}+\frac{\sqrt{H^{7}SA\eta}\cdot\tau}{n+1}),64\frac{H^{3}}{n+1}\right\}}.$ $$

###### Proof.

Let $k_{i}$ denote the index of the episode when $(s,a)$ was visited for the $i_{\text{th}}$ time at step $h$. Set $x_{i}=\alpha_{n}^{i}(r_{k_{i},h}-R_{h}(s,a))$, $y_{i}=\alpha_{n}^{i}(V(s_{k_{i+1}})-P_{s_{i},a_{i}}\cdot V)$ and consider filtration $\mathcal{F}_{i}$ as the $\sigma-$field generated by all random variables in the history set $\mathcal{H}_{k_{i},h}$. We apply Azuma-Hoeffding (Lemma [E.3](https://arxiv.org/html/2506.00917v3#Thmlemma3c)) to calculate $|\sum_{i=1}^{n}x_{i}|$ and Azuma-Bernstein for $|\sum_{i=1}^{n}y_{i}|$.
Consider with probability $1-\delta$,

$$ $\displaystyle\mathinner{\!\left\lvert\sum_{i=1}^{n}\alpha_{n}^{i}(V(s_{k_{i+1}})-P_{s_{i},a_{i}}\cdot V)\right\rvert}$ $\displaystyle\leq$ $\displaystyle O(1)\cdot\mathinner{\left[\sum_{i=1}^{n}\sqrt{(\alpha_{n}^{i})^{2}[\mathbb{V}_{h}V^{*}_{h+1}]_{s,a}\eta}+\frac{H^{2}\eta}{n}\right]}$ $\displaystyle\leq$ $\displaystyle O(1)\cdot\mathinner{\left[\sum_{i=1}^{n}\sqrt{\frac{H}{n}[\mathbb{V}_{h}V^{*}_{h+1}]_{s,a}\eta}+\frac{H^{2}\eta}{n}\right]}.$ $$

Using Lemma [F.2](https://arxiv.org/html/2506.00917v3#Thmlemma2d) and a suitable union bound, we have with probability $1-\delta$,

$$ $\displaystyle\mathinner{\!\left\lvert\sum_{i=1}^{n}\alpha_{n}^{i}(V(s_{k_{i+1}})-P_{s_{i},a_{i}}\cdot V)\right\rvert}$ $\displaystyle\leq$ $\displaystyle O(1)\cdot\mathinner{\left[\sum_{i=1}^{n}\sqrt{\frac{H}{n+1}(\widehat{\mathbb{V}}_{n}\overline{V}_{h+1}(s,a)+H)\eta}+\frac{\sqrt{H^{7}SA\eta}\cdot\chi}{n+1}\right]}$ $\displaystyle\leq$ $\displaystyle\sqrt{v_{b}(n,h,s,a)}.$ $$

where the last term dominates the concentration of $|\sum_{i=1}^{n}x_{i}|$.
∎

###### Lemma F.4 (Based on Lemma C.1 ) .

The samples from the posterior distributions and the mean of the posterior distributions as defined in Algorithm [3](https://arxiv.org/html/2506.00917v3#alg3) satisfy the following properties: for any episode $k\in[K]$ and index $h\in[H]$,

- (a)
(Posterior distribution mean)
For any given $s,a$, with probability at least $1-\frac{2(k-1)\delta}{KH}-\frac{\delta}{KH}$,
$\displaystyle\widehat{Q}_{k,h}(s,a)\geq Q^{*}_{h}(s,a)-\sqrt{v_{b}(n,h,s,a)}.$
(48)
- (b)
(Posterior distribution sample) For any given $s,a$, with probability at least $p_{1}$ ($p_{1}=\Phi(-1)$),
$\displaystyle\tilde{Q}_{k,h}(s,a)\geq Q^{*}_{h}(s,a).$
(49)
- (c)
(In Algorithm [2](https://arxiv.org/html/2506.00917v3#alg2)) With probability at least $1-\frac{2k\delta}{KH}$,
$\overline{V}_{k,h}(s_{k,h})\geq V^{*}_{h}(s_{k,h}).$
(50)

###### Proof.

The proof is identical to that of Lemma [C.1](https://arxiv.org/html/2506.00917v3#Thmlemma1b) except that we use Lemma [F.3](https://arxiv.org/html/2506.00917v3#Thmlemma3d) instead of Corollary [D.2](https://arxiv.org/html/2506.00917v3#Thmcorollary2a).
∎

###### Lemma F.5 (Based on Lemma C.6 of Jin et al. [ 2018 ] ) .

With probability at least $1-4\delta$, we have the following for all $k,h\in[K]\times[H]$,

$$ $\displaystyle\widehat{\mathbb{V}}_{n}\overline{V}_{k,h}(s_{k,h},a_{k,h})-\mathbb{V}_{h}V^{\pi_{k}}_{h+1}(s_{k,h},a_{k,h})$ $\displaystyle\leq$ $\displaystyle 2HP_{s_{k,h},a_{k,h}}\cdot(V^{*}_{h+1}-V^{\pi_{k}}_{h+1})$ $\displaystyle+O\mathinner{\left(\frac{SA\sqrt{H^{9}\chi^{4}}}{n}+\sqrt{\frac{H^{7}SA\chi^{2}}{n}}\right)},$ $$

where $n=N_{k,h}(s_{k,h},a_{k,h})$ and $\chi=\log(JSAT/\delta)$.

###### Proof.

Consider,

$$ $\displaystyle\widehat{\mathbb{V}}_{n}\overline{V}_{k,h}(s_{k,h},a_{k,h})-\mathbb{V}_{h}V^{\pi_{k}}_{h+1}(s_{k,h},a_{k,h})$ $\displaystyle\leq$ $\displaystyle\mathinner{\!\left\lvert\widehat{\mathbb{V}}_{n}\overline{V}_{k,h}(s_{k,h},a_{k,h})-\mathbb{V}_{h}V^{*}_{h+1}(s_{k,h},a_{k,h})\right\rvert}$ $\displaystyle+\mathinner{\!\left\lvert\mathbb{V}_{n}V^{*}_{h+1}(s_{k,h},a_{k,h})-\mathbb{V}_{h}V^{\pi_{k}}_{h+1}(s_{k,h},a_{k,h})\right\rvert},$ $$

where for the first term we apply Lemma [F.2](https://arxiv.org/html/2506.00917v3#Thmlemma2d) (which holds when Corollary [F.1](https://arxiv.org/html/2506.00917v3#Thmcorollary1b) and Lemma [F.1](https://arxiv.org/html/2506.00917v3#Thmlemma1e) hold) and for the second term we have from the definition of variance,

$$ $\displaystyle\mathinner{\!\left\lvert\mathbb{V}_{n}V^{*}_{h+1}(s_{k,h},a_{k,h})-\mathbb{V}_{h}V^{\pi_{k}}_{h+1}(s_{k,h},a_{k,h})\right\rvert}$ $\displaystyle\leq$ $\displaystyle 2HP_{s_{k,h},a_{k,h}}\cdot(V^{*}_{h+1}-V^{\pi_{k}}_{h+1}).$ $$

∎

###### Corollary F.1 (Corollary of Lemma 4 ) .

###### Proof.

###### Lemma F.1 (Based on Lemma C.7 in Jin et al. [ 2018 ] ) .

###### Proof.

###### Lemma F.2 (Based on Lemma C.3 of Jin et al. [ 2018 ] ) .

###### Proof.

###### Lemma F.3 .

###### Proof.

###### Lemma F.4 (Based on Lemma C.1 ) .

###### Proof.

###### Lemma F.5 (Based on Lemma C.6 of Jin et al. [ 2018 ] ) .

###### Proof.

## Appendix G scratch

Define

$$ $\sigma(N_{h}(s_{h},a_{h}))\coloneqq A_{h}(N_{h}(s_{h},a_{h}))+B_{h},$ $$

where

$$ $A_{h}(N_{h}(s_{h},a_{h}))=\sqrt{\frac{H^{3}\log(KH/\delta)}{N_{h}(s_{h},a_{h})}}$ $$

and

$$ $B_{h}\coloneqq\alpha_{N_{h}(s_{h},a_{h})}B_{h}+(1-\alpha_{N_{h}(s_{h},a_{h})})(\tilde{Q}_{h+1}(s_{h+1},a_{h+1})-\overline{V}_{h+1}(s_{h}+1)),$ $$

which is same as,

$$ $B_{k,h}=\sum_{i=1}^{N_{k,h}(s_{k,h},a_{k,h})}\alpha^{i}_{n}(\tilde{Q}_{k_{i},h+1}(s_{k_{i},h+1},a_{k_{i},h+1})-\overline{V}_{k_{i},h+1}(s_{k_{i},h+1})).$ $$

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 2
presentation: 3
questions: See weaknesses.
soundness: 2
strengths: Authors discuss the limitations of the analysis of the vanilla PSQL algorithm
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.
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;
- 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?
- What regret bound can be achieved in the "vanilla version" of the PSQL algorithm? Could a non-trivial polynomial bound be established
- 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.

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 3
questions: 1. Can alternative posterior distributions preserve Q-value structure more faithfully than Gaussians?

2. Is there a principled or adaptive way to select the posterior variance to avoid heuristic tuning?

3. Can the multiple-sampling step for optimism be replaced with a cheaper or more elegant alternative?

4. How does the approach scale to function approximation or deep RL settings?

5. How does posterior optimism interact with TD bootstrapping bias in long horizons?
soundness: 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.
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.
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.

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 2
questions: - It would be beneficial to discuss an RLSVI-style model-based algorithm that achieves the minimax optimal regret guarantee (Xiong et al. 2022).
- What prevents you from using a standard RSLVI analysis with a single sample there?
- 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?
- Is it possible to provide a deep-learning version of your method?

### References

Xiong, 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.
soundness: 3
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;
- Strong empirical performance as well as theoretical regret guarantees;
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.
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.
- The regret bound does not match the regret bound of a variance-reduced version of Q-learning (Li et al. 2021);

---

confidence: 3
contribution: 2
initial_rating: 2
presentation: 2
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?
- 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?
- 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.
- 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?

[1] Ishfaq et al., Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo, ICLR 2024.
soundness: 3
strengths: - Provides a near-optimal $\tilde{O}(H^{2}SAT^{1/2})$ regret analysis for a posterior-sampling variant of tabular Q-learning.
- 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.
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.
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.
- 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.
- 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.
- 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.


Decision: Accept (Poster)