algorithmic

# More Efficient Randomized Exploration for Reinforcement Learning via
Approximate Sampling

Haque Ishfaq11footnotemark: 1
<EMAIL_ADDRESS>
Mila, McGill University &Yixin Tan
<EMAIL_ADDRESS>
Duke University &Yu Yang
Duke University &Qingfeng Lan
University of Alberta &Jianfeng Lu
Duke University &A. Rupam Mahmood
Amii, University of Alberta &Doina Precup
Mila, McGill University &Pan Xu
Duke University Equal contribution

###### Abstract

Thompson sampling (TS) is one of the most popular exploration techniques in
reinforcement learning (RL). However, most TS algorithms with theoretical
guarantees are difficult to implement and not generalizable to Deep RL. While
the emerging approximate sampling-based exploration schemes are promising,
most existing algorithms are specific to linear Markov Decision Processes
(MDP) with suboptimal regret bounds, or only use the most basic samplers such
as Langevin Monte Carlo. In this work, we propose an algorithmic framework
that incorporates different approximate sampling methods with the recently
proposed Feel-Good Thompson Sampling (FGTS) approach (Zhang, 2022; Dann et
al., 2021), which was previously known to be computationally intractable in
general. When applied to linear MDPs, our regret analysis yields the best
known dependency of regret on dimensionality, surpassing existing randomized
algorithms. Additionally, we provide explicit sampling complexity for each
employed sampler. Empirically, we show that in tasks where deep exploration is
necessary, our proposed algorithms that combine FGTS and approximate sampling
perform significantly better compared to other strong baselines. On several
challenging games from the Atari 57 suite, our algorithms achieve performance
that is either better than or on par with other strong baselines from the deep
RL literature.

##  1 Introduction

A fundamental problem in reinforcement learning (RL) is balancing exploration-
exploitation trade-off. One effective mechanism for addressing this challenge
is Thompson Sampling (TS) (Thompson, 1933; Strens, 2000; Osband et al.,
2016b), which gained popularity due to its simplicity and strong empirical
performance (Osband et al., 2016a; 2018; Ishfaq et al., 2024). While there
have been numerous works on TS in both RL theory (Osband et al., 2013; Russo,
2019; Zanette et al., 2020a; Ishfaq et al., 2021; Xiong et al., 2022) and deep
RL literature (Osband et al., 2016a; 2018; Fortunato et al., 2018; Plappert et
al., 2018; Ishfaq et al., 2024; Li et al., 2024), there remains a substantial
gap between algorithms that excel in theoretical properties and those that
demonstrate strong empirical performance. This disparity highlights the need
for a unified framework that provides the ultimate unification of theory and
practice for Thompson sampling.

In particular, heuristic RL algorithms that are motivated by TS (Osband et
al., 2016a; 2018; Fortunato et al., 2018) have shown great empirical potential
while often lacking any theoretical guarantee. Existing RL theory works on TS
suffer from sub-optimal dimension dependency compared to its upper confidence
bound (UCB) counterparts (Jin et al., 2020; Zanette et al., 2020a; Ishfaq et
al., 2021; 2024). Recently proposed Feel-Good Thompson sampling (FGTS) (Zhang,
2022; Dann et al., 2021) bypasses this issue by incorporating an optimistic
prior term in the posterior distribution of Q function. However, these works
fail to provide any computationally tractable sampling procedure from this
posterior distribution.

Recently there has been some works that use Langevin Monte Carlo (LMC)
(Dwaracherla & Van Roy, 2020; Xu et al., 2022; Ishfaq et al., 2024; Hsu et
al., 2024) to implement TS which are both provably efficient and practical.
However, these works lack generality by confining only to LMC and it remains
unclear whether many other advanced approximate sampling methods are
compatible with this algorithmic scheme for implementing TS. Moreover, the
theoretical analyses of these works are limited to linear MDPs (Jin et al.,
2020) while having sub-optimal regret bound. Thus, it is unclear how the
sampling error of LMC would affect the theoretical regret guarantee under more
general structural assumptions. This shows a clear divergence between the RL
theory and the deep RL literature when it comes to TS. To this end, we aim to
design an approximate TS based RL algorithm that is generalizable and flexible
enough to use different approximate samplers while achieving optimal
dependency in the regret bound.

With this aim, we propose several FGTS class of algorithms that incorporates
different approximate samplers from the Markov Chain Monte Carlo (MCMC)
literature. Unlike previous works that assume exact posterior sampling (e.g.,
Zhang (2022); Dann et al. (2021); Agarwal & Zhang (2022a; b)) by assuming
access to unrealistic sampling oracle, we propose practically implementable
approximate posterior sampling scheme under FGTS framework using different
approximate samplers.

###  1.1 Key Contributions

We highlight the main contributions of the paper below:

  * •

We present a class of practical and efficient TS based online RL algorithms
that prioritizes easy implementation and computational scalability.
Concretely, we present practically implementable FGTS style algorithms that
are based on approximate samplers from the MCMC literature. Our proposed
algorithm allows flexible usage of different approximate samplers such as
Langevin Monte Carlo (LMC) (Durmus et al., 2019) or Underdamped Langevin Monte
Carlo (ULMC) (Chen et al., 2014; Cheng et al., 2018) and is easy to implement
compared to other state-of-the-art exploration focused deep RL algorithms.

  * •

Our main theoretical result provides regret bound under general Markov
decision processes and value function classes. Our general analytical
framework decomposes the regret bound into two components: 1) the idealistic
regret bound assuming exact TS (as addressed in many previous works such as
Agarwal & Zhang (2022b; a)), and 2) the additional term introduced by using
approximate samplers. This generalizable and fine-grained analysis allows us
to analyze the impact of sampling error for any RL setting with an existing
exact-sampling regret bound and known convergence rates for the approximate
samplers.

  * •

When applied to linear MDPs (Jin et al., 2020), our proposed algorithm
achieves a regret bound of $\tilde{O}(dH^{\frac{3}{2}}\sqrt{T})$, where $d$ is
the dimension of the feature mapping, $H$ is the planning horizon, and $T$ is
the total number of steps. This regret bound has the best known dimension
dependency for any randomized and UCB based algorithms.

  * •

We provide extensive experiments on both $N$-chain environments (Osband et
al., 2016a) and challenging Atari games (Bellemare et al., 2013) that require
deep exploration. Our experiments indicate our proposed algorithms perform
similarly or better than state-of-the-art exploration algorithms from the deep
RL literature.

###  1.2 Additional Related Work

Randomized least-squares value iteration (RLSVI) based algorithms induce deep
exploration by injecting judiciously tuned random noise into the value
function (Russo, 2019; Zanette et al., 2020a; Ishfaq et al., 2021; Xiong et
al., 2022). Osband et al. (2016a; 2018) propose deep RL variant of RLSVI
wherein they train an ensemble of randomly initialized neural networks and
view them as approximate posterior samples of Q functions. Another deep RL
variant of RLSVI is Noisy-Net (Fortunato et al., 2018) that directly injects
noise to neural network parameters during the training phase. More recently,
Dwaracherla & Van Roy (2020); Ishfaq et al. (2024) propose using LMC to
perform approximate TS. While Ishfaq et al. (2024) provides regret bound for
their proposed LMC-LSVI algorithm under linear MDP, their regret bound, like
other existing randomized exploration algorithms, has sub-optimal dependency
on the dimension of the linear MDP. Hsu et al. (2024) further extends LMC-LSVI
to the cooperative multi-agent reinforcement learning setting. Dann et al.
(2021) proposes conditional posterior sampling based on FGTS (Zhang, 2022)
with a regret bound that has optimal dependency on the dimension in linear
MDPs, but their algorithm is intractable due to the need to access to some
unknown sampler oracle.

##  2 Preliminary

In this paper, we consider an episodic discrete-time Markov decision process
(MDP), denoted by $(\mathcal{S},\mathcal{A},H,\mathbb{P},r)$, with
$\mathcal{S}$ being the state space, and $\mathcal{A}$ the action space. The
MDP is non-stationary across $H$ different stages, which form an episode. $H$
is also often referred to as the episode length.
$\mathbb{P}=\\{\mathbb{P}_{h}\\}_{h=1}^{H}$ is the collection of the state
transition probability distributions, $\mathbb{P}_{h}(\cdot\mid x,a)$ denotes
the transition kernel at stage $h\in[H]$. Let $r=\\{r_{h}\\}_{h=1}^{H}$ be the
collection of reward functions, which we assume to be deterministic and
bounded in $[0,1]$ for the simplicity of the presentation.

We define a policy $\pi$ in this MDP as a collection of $H$ functions
$\\{\pi_{h}:\mathcal{S}\rightarrow\mathcal{A}\\}_{h\in[H]}$, where
$\pi_{h}(x)$ means the action at state $x$ given by policy $\pi$ at stage $h$
of the episode.

At stage $h\in[H]$, we define the value function
$V_{h}^{\pi}:\mathcal{S}\rightarrow\mathbb{R}$ as the total expected rewards
collected by the agent if it starts at state $x_{h}=x$ and follows policy
$\pi$ onwards, i.e.,
$V_{h}^{\pi}(x)=\mathbb{E}_{\pi,\mathbb{P}}\big{[}\sum_{h^{\prime}=h}^{H}r_{h^{\prime}}(x_{h^{\prime}},a_{h^{\prime}})\big{|}x_{h}=x\big{]}$.

We also define the action-value function (or Q function)
$Q_{h}^{\pi}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ as the total
expected rewards by the agent if it starts at state $x_{h}=x$ and action
$a_{h}=a$ and follows policy $\pi$ onwards, i.e.,
$Q_{h}^{\pi}(x,a)=\mathbb{E}_{\pi,\mathbb{P}}\big{[}\sum_{h^{\prime}=h}^{H}r_{h^{\prime}}(x_{h^{\prime}},a_{h^{\prime}})\big{|}x_{h}=x,a_{h}=a\big{]}$.

To simplify the notation, we denote operator
$[\mathbb{P}_{h}V_{h+1}^{\pi}](x,a)=\mathbb{E}_{x^{\prime}\sim\mathbb{P}_{h}(\cdot|x,a)}V_{h+1}^{\pi}(x^{\prime})$.
Thus, we write the Bellman equation associated with a policy $\pi$ as

$\displaystyle
Q_{h}^{\pi}(x,a)=(r_{h}+\mathbb{P}_{h}V_{h+1}^{\pi})(x,a),\qquad
V_{h}^{\pi}(x)=Q_{h}^{\pi}(x,\pi_{h}(x)),\qquad V_{H+1}^{\pi}(x)=0.$ (2.1)

We denote the optimal policy as $\pi^{*}=\\{\pi_{h}^{*}\\}_{h=1}^{H}$, which
is the collection of the optimal policies at each stage $h$. We further denote
$V_{h}^{*}(x)=V_{h}^{\pi^{*}}(x)$ and $Q_{h}^{*}(x,a)=Q_{h}^{\pi^{*}}(x,a)$.
It can be shown that $\pi^{*}$ is a deterministic policy and it satisfies
$Q_{h}^{\pi*}(s,a)=\max_{\pi}Q^{\pi}(s,a)$ and
$V_{h}^{\pi^{*}}(s)=\max_{\pi}V_{h}^{\pi}(s)$ for all $s\in{\mathcal{S}}$ and
$a\in\mathcal{A}$ (Bertsekas, 2019).

We denote the Bellman optimality operator by ${\mathcal{T}}_{h}^{*}$ that maps
any function $Q$ over ${\mathcal{S}}\times\mathcal{A}$ to

$\displaystyle\textstyle[{\mathcal{T}}_{h}^{*}Q](x,a)=r_{h}(x,a)+\mathbb{E}_{x^{\prime}\sim\mathbb{P}_{h}(\cdot|x,a)}\big{[}\max_{a^{\prime}\in\mathcal{A}}Q_{h+1}(x^{\prime},a^{\prime})\big{]}.$
(2.2)

Note that the optimal Q function satisfies
${\mathcal{T}}_{h}^{*}Q_{h+1}^{*}=Q_{h}^{*}$, for all $h\in[H]$.

The agent follows the following iterative interaction protocol. At the
beginning of each episode $k\in[K]$, an adversary picks an initial state
$x_{1}^{k}$ for stage $1$, and the agent executes a policy $\pi^{k}$ and
updates the policy in the next stage according to the received rewards. We
measure the suboptimality of the agent by the total regret defined as

$\text{Regret}(K)=\sum_{k=1}^{K}\text{REG}_{k}:=\sum_{k=1}^{K}\big{[}V_{1}^{*}(x_{1}^{k})-V_{1}^{\pi^{k}}(x_{1}^{k})\big{]}.$

###  2.1 Notations

We use $a=O(b)$ to indicate that $a\leq Cb$ for a universal constant $C>0$.
Also, we write $a=\Theta(b)$ if there are universal constants $c^{\prime}>c>0$
such that $cb\leq a\leq c^{\prime}b$, and the notation $\tilde{O}(\cdot)$ and
$\tilde{\Theta}(\cdot)$ mean they hide polylog factors in the parameters. For
two probability distributions $p$ and $q$ on the same probability space, we
denote their total variation (TV) distance by $TV(p,q)$. For
$T:\mathbb{R}^{d}\to\mathbb{R}^{d}$, the pushforward of a distribution $p$ is
denoted as $T_{\\#}p$, such that $T_{\\#}p(A)=p(T^{-1}(A))$ for any measurable
set $A$.

##  3 Algorithm Design

In this section, we present our core algorithm, a general framework that
leverages Feel-Good Thompson Sampling (FGTS) (Zhang, 2022; Dann et al., 2021)
alongside various approximate sampling techniques such as Langevin Monte Carlo
(LMC) (Durmus et al., 2019) and Underdamped Langevin Monte Carlo (ULMC) (Chen
et al., 2014; Cheng et al., 2018). The proposed general algorithm is displayed
in Algorithm 1.

Our algorithm design resembles that of Ishfaq et al. (2024) in the sense that,
unlike other approximate TS algorithms (Russo, 2019; Zanette et al., 2020a;
Ishfaq et al., 2021), it performs exploration by coupling approximate sampling
into value iteration step. However, our design choice offers significant
flexibility of the algorithm: it allows us to employ a wide range of prior
distributions and integrate different samplers, enabling us to tailor the
exploration process to specific problem characteristics. The generality of our
framework allows it to address suboptimality observed in existing exploration
approaches (Ishfaq et al., 2024). By incorporating a flexible prior selection
mechanism, we can overcome limitations inherent in specific prior choices
employed by other methods. This flexibility enables us to potentially achieve
better performance across diverse exploration problems.

Algorithm 1 Least-Squares Value Iteration with Approximate Sampling
Exploration (LSVI-ASE)

1: Input: feel-good prior weight $\eta$, step sizes
$\\{\tau_{k,h}>0\\}_{k,h\geq 1}$, temperature $\beta$, friction coefficient
$\gamma$, loss function $L_{k}(w)$.

2: Initialize $w_{h}^{1,0}=\textbf{0}$ for $h\in[H]$, $J_{0}=0$.

3: for episode $k=1,2,\ldots,K$ do

4: Receive the initial state $s_{1}^{k}$.

5: for step $h=H,H-1,\ldots,1$ do

6: $w_{h}^{k,0}=w_{h}^{k-1,J_{k-1}}$

7: for $j=1,\ldots,J_{k}$ do

8: Generate $w_{h}^{k,j}$ via a sampler in Section 3.2

9: end for

10:
$Q^{k}_{h}(\cdot,\cdot)\leftarrow\min\\{Q(w_{h}^{k,J_{k}};\phi(\cdot,\cdot)),H-h+1\\}^{+}$

11: $V^{k}_{h}(\cdot)\leftarrow\max_{a\in\mathcal{A}}Q_{h}^{k}(\cdot,a)$.

12: end for

13: for step $h=1,2,\ldots,H$ do

14: Take action
$a^{k}_{h}\leftarrow\mathop{\mathrm{argmax}}_{a\in\mathcal{A}}Q_{h}^{k}(s_{h}^{k},a)$.

15: Observe reward $r^{k}_{h}(s_{h}^{k},a_{h}^{k})$, get next state
$s^{k}_{h+1}$.

16: end for

17: end for

###  3.1 Feel-Good Thompson Sampling

Assume we have collected data trajectories in the first $k-1$ episodes as
$D_{k-1}=\\{(x_{1}^{\tau},a_{1}^{\tau},r(x_{1}^{\tau},a_{1}^{\tau})),\ldots,(x_{H}^{\tau},a_{H}^{\tau},r(x_{H}^{\tau},a_{H}^{\tau}))\\}_{\tau=1}^{k-1}$.
To estimate the $Q$-function for stage $h$ at the $k$-th episode of the
learning process, we define the following loss function for $h\in[H]$:

$\displaystyle\textstyle
L_{h}^{k}(w_{h})=\eta\sum_{\tau=1}^{k-1}\left[r_{h}(x_{h}^{\tau},a_{h}^{\tau})+\text{max}_{a\in\mathcal{A}}Q^{k}_{h+1}(x_{h+1}^{\tau},a)-Q(w_{h};\phi(x_{h}^{\tau},a_{h}^{\tau}))\right]^{2},$
(3.1)

where $\phi(\cdot,\cdot)$ is a feature vector of the corresponding state-
action pair and $Q(w_{h};\phi(x_{h}^{\tau},a_{h}^{\tau}))$ denotes any
possible approximation of the Q function that is parameterized by $w_{h}$ and
takes $\phi(x_{h}^{\tau},a_{h}^{\tau})$ as input. $Q_{h}^{k}$ is defined in
Line 10 of Algorithm 1 and is the truncated estimated Q function. Moreover, we
let
$L^{k}_{0}(w_{1})=-\lambda\text{max}_{a\in\mathcal{A}}Q(w_{1};x_{1}^{k},a)$,
where $L_{0}^{k}$ is the Feel-Good exploration prior term (Zhang, 2022). The
posterior distribution at episode $k$ and stage $h>1$ is then given by

$\displaystyle q_{k}^{h}(w_{h})\propto
p_{0}^{h}(w_{h})\exp(-L_{h}^{k}(w_{h})),$

where $p_{0}^{h}$ is the prior distribution of $w_{h}$. And at stage $h=1$, we
have $q_{k}^{1}(w_{1})\propto
p_{0}^{1}(w_{1})\exp(-L_{1}^{k}(w_{1})-L_{0}^{k}(w_{1}))$. Then at episode
$k$, the exact target (joint) posterior of $Q$, which is denoted by $q_{k}$,
is given by

$\displaystyle\textstyle q_{k}(w)\propto
p_{0}(w)\exp(-\sum_{h=0}^{H}L_{h}^{k}(w_{h})),$ (3.2)

where $p_{0}(w)=\prod_{h=1}^{H}p_{0}^{h}(w_{h})$. Compared to standard TS
(Thompson, 1933; Osband et al., 2013), FGTS incorporates an additional
exploration term $\exp(-L_{0}^{k}(w_{1}))$ in the likelihood function. This
term encourages the selection of value functions at the first time step that
yield large values for the initial state. This bias is particularly beneficial
during early learning stages when wider exploration is crucial.

Challenges of FGTS in practice: Despite the regret of FGTS has been proven to
be achieving the optimal dependency on the dimension in bandits (Zhang, 2022)
and reinforcement learning (Dann et al., 2021), existing FGTS algorithms are
often computationally intractable as they assume access to sampling oracles
for sampling from a high-dimensional distribution at each iteration.
Specifically, previous FGTS based algorithms proposed by Zhang (2022); Dann et
al. (2021) simply sample $Q$ function from the posterior distribution defined
in (3.2) in the beginning of each episode and then follow a greedy policy with
respect to the sampled $Q$ function. However, this assumes access to a
sampling oracle which allows one to sample from (3.2) that is not generally
available in practice. Since we cannot directly sample from the true posterior
distribution $q_{k}$, we propose using approximating samplers to generate
posterior estimates which we describe next.

###  3.2 Approximate Samplers

In this subsection, we present different approximate sampling methods which we
use to approximately sample from the posterior distribution defined in (3.2).
Let $p\propto e^{-L}$ be a probability density on $\mathbb{R}^{d}$ such that
$L$ is continuously differential. The goal is to generate samples from $p$.

Langevin Monte Carlo.  LMC leverages the Euler discretization method to
approximate the continuous-time Langevin diffusion process, making it a
popular sampling algorithm in machine learning (Welling & Teh, 2011). Langevin
diffusion with stationary distribution $p$ is the stochastic process defined
by the stochastic differential equation (SDE) $dw_{t}=-\nabla
L(w_{t})dt+\sqrt{2}dB_{t}$, where $B_{t}$ is a standard Brownian motion in
$\mathbb{R}^{d}$. To obtain the LMC algorithm, we take the Euler-Murayama
discretization of the SDE. For a fixed step size $\tau>0$, temperature $\beta$
and $w_{0}\in\mathbb{R}^{d}$, LMC is defined by the iteration

$\displaystyle w_{k+1}=w_{k}-\tau\nabla
L(w_{k})+\sqrt{2\beta^{-1}\tau}\xi_{k},$

where $\xi_{k}\sim\mathcal{N}(0,I_{d})$. Previous works have thoroughly
established strong theoretical guarantees for the convergence of LMC
(Dalalyan, 2017; Xu et al., 2018; Zou et al., 2021).

In Line 8 of Algorithm 1, we can use LMC to approximately sample
$w_{h}^{k,J_{k}}$ from the posterior defined in (3.2). In our deep RL
experiment in Section 5, we also incorporate adaptive bias term for the
gradient of loss function as introduced in Ishfaq et al. (2024).

Underdamped Langevin Monte Carlo.  While LMC offers an elegant approach, its
scalability suffers as the problem dimension, error tolerance, or condition
number increases (Zheng et al., 2024; Zhang et al., 2023). To mitigate these
limitations, we exploit Underdamped Langevin Monte Carlo (ULMC), which
exhibits enhanced scalability in such high-dimensional or poorly conditioned
settings. The appeal of ULMC lies in its connection to Hamiltonian Monte Carlo
(HMC) (Brooks et al., 2011). Since underdamped Langevin diffusion (ULD)
incorporates a Hamiltonian component, its discretization can be viewed as a
form of HMC. Notably, HMC has been empirically observed to converge faster to
the stationary distribution compared to LMC (Cheng et al., 2018). Introducing
a balance of exploration and exploitation through momentum, the ULD is given
by the SDE

$\displaystyle\begin{split}dw_{t}&=P_{t}dt,\\\ dP_{t}&=-\nabla
L(w_{t})dt+\gamma P_{t}dt+\sqrt{2\beta^{-1}\gamma}dB_{t},\\\ \end{split}$

where $\gamma,\beta>0$ are friction coefficient and temperature respectively.
We note that instead of using Euler-Maruyama as for LMC, the ULMC can be
implemented in the following way:

$\displaystyle dw_{t}$ $\displaystyle=P_{t}dt,$ $\displaystyle dP_{t}$
$\displaystyle=-\nabla L(w_{k\tau})dt+\gamma
P_{t}dt+\sqrt{2\beta^{-1}\gamma}dB_{t},$ (3.3)

for $t\in[k\tau,(k+1)\tau]$, where $\tau>0$ is the step-size. This formulation
of ULMC can be integrated in a closed form (Cheng et al., 2018; Zhang et al.,
2023), and hence our theoretical analysis is based on this scheme. However,
obtaining the closed-form solution is computationally expensive in our setting
due to the cubic cost $O(d^{3})$ of Cholesky decomposition. So, we employ an
adapted Euler-Maruyama method in our experiments for efficient numerical
integration. Applying Euler-Maruyama with step size $\tau>0$, we obtain the
following iteration scheme of $w_{k}$ and $P_{k}$:

$\displaystyle w_{k+1}=w_{k}+\tau P_{k},$ $\displaystyle
P_{k+1}=P_{k}-\tau\nabla L(w_{k})-\gamma\tau
P_{k}+\sqrt{2\beta^{-1}\gamma\tau}\xi_{k},$ (3.4)

where $\xi_{k}\sim\mathcal{N}(0,I_{d})$. In practice, to improve the
performance, we follow Ishfaq et al. (2024) to incorporate adaptive bias term
to the gradient, which leads to the following update:

$\displaystyle\begin{split}&m_{k}=\alpha_{1}m_{k-1}+\left(1-\alpha_{1}\right)\nabla
L(w_{k})\\\ &v_{k}=\alpha_{2}v_{k-1}+\left(1-\alpha_{2}\right)\nabla
L(w_{k})\odot\nabla L(w_{k})\\\ &P_{k}=(1-\gamma\tau)P_{k-1}+\tau\left(\nabla
L(w_{k})+am_{k}\oslash\sqrt{v_{k}+\lambda\bf{1}}\right)+\sqrt{2\beta^{-1}\gamma\tau}\xi_{k}\\\
&w_{k+1}=w_{k}-\tau P_{k},\end{split}$ (3.5)

where the hyperparameters $\alpha_{1},\alpha_{2}\in[0,1)$ control the
exponential decay rates of the moving averages (Kingma & Ba, 2014).

##  4 Theoretical Analysis

This section presents the theoretical analysis of our proposed algorithm. We
begin by establishing a regret bound for general function classes, shedding
light on the impact of sampling error on regret. Subsequently, we focus on
linear MDPs (Jin et al., 2020), providing a detailed analysis of both the
regret bound and the corresponding sampling complexity.

###  4.1 Regret Bound for General Function Classes

Assume that the agent is given a $Q$-function class
$\mathcal{Q}=\mathcal{Q}_{1}\times\mathcal{Q}_{2}\times\ldots\times\mathcal{Q}_{H}$
of functions $Q=\\{Q_{h}\\}_{h\in[H]}$ where
$Q_{h}:\mathcal{X}\times\mathcal{A}\rightarrow\mathbb{R}$. For any
$Q\in\mathcal{Q},h\in[H]$ and state-action pair $x,a$, we define the Bellman
residual as

$\mathcal{E}_{h}(Q;x,a)=\mathcal{E}(Q_{h},Q_{h+1};x,a)=Q_{h}(x,a)-{\mathcal{T}}_{h}^{*}Q_{h+1}(x,a).$
(4.1)

We have the following assumptions on the value-function class:

######  Assumption 4.1.

[Realizability]. Assume that $Q^{*}\in\mathcal{Q}$.

######  Assumption 4.2.

[Boundedness] Assume that $\exists b\geq 1$ such that for all
$Q\in\mathcal{Q}$ and $h\in[H]$, $Q_{h}(x,a)\in[0,b-1]$, for all
$(x,a)\in{\mathcal{S}}\times\mathcal{A}$.

######  Assumption 4.3.

[Completeness] For all $h\in[H]$ and $Q_{h+1}\in\mathcal{Q}_{h+1}$, there is a
$Q_{h}\in\mathcal{Q}_{h}$ such that $Q_{h}={\mathcal{T}}_{h}^{*}Q_{h+1}$.

It’s important to note that these assumptions are only necessary for general
function classes. One can verify that these assumptions are satisfied in some
specific settings, such as linear MDPs (Jin et al., 2020) defined in Section
4.3.

We first introduce two metrics following Dann et al. (2021) that characterizes
the structural complexity of the MDP and the effective size of the value-
function class $\mathcal{Q}$ respectively.

######  Definition 4.4.

[Decoupling Coefficient] Let $\mathcal{K}_{\text{DC}}$ be the smallest
quantity so that for any sequence of functions
$\\{Q^{k}\\}_{k\in\mathbb{N}}\subset\mathcal{Q}$ and $h\geq 0$, it holds that,

$\displaystyle\sum_{h=1}^{H}\sum_{k=1}^{K}\mathbb{E}_{[x_{h},a_{h}]\sim
p(\cdot|Q^{k},x_{1})}\big{[}\mathcal{E}_{h}(Q^{k};x_{h},a_{h})\big{]}\leq\inf_{\mu\in(0,1]}\bigg{[}\mu\sum_{h=1}^{H}\sum_{k=1}^{K}\sum_{s=1}^{k-1}\mathbb{E}_{[x_{h},a_{h}]\sim
p(\cdot|Q^{s},x_{1})}[\mathcal{E}_{h}(Q^{k};x_{h},a_{h})]^{2}+\frac{\mathcal{K}_{\text{DC}}}{4\mu}\bigg{]}.$

The decoupling coefficient, $\mathcal{K}_{\text{DC}}$, measures the growth
rate of average Bellman residuals compared to cumulative squared Bellman
residuals. We refer the readers to Dann et al. (2021) for further details on
relationship between decoupling coefficient and other complexity measures
typically used in RL such as Bellman-Eluder dimension (Jin et al., 2021).

######  Definition 4.5.

For any function $Q^{\prime}\in\mathcal{Q}_{h+1}$, we define the set
$\mathcal{Q}_{h}(\epsilon,Q^{\prime})=\\{Q\in\mathcal{Q}_{h}:\sup_{x,a}|Q(x,a)-{\mathcal{T}}^{*}_{h}Q^{\prime}(x,a)|\leq\epsilon\\}$
of functions that have small Bellman error with $Q^{\prime}$ for all state-
action pairs. Using this set, we define
$\kappa(\epsilon)=\sup_{Q\in\mathcal{Q}}\sum_{h=1}^{H}-\ln
p_{0}^{h}(\mathcal{Q}_{h}(\epsilon,Q_{h+1}))$.

The set $\mathcal{Q}_{h}(\epsilon,Q_{h+1})$ includes the functions that
approximately satisfy the Bellman equation and
$p_{0}^{h}(\mathcal{Q}_{h}(\epsilon,Q_{h+1}))$ denotes the probability that is
assigned on this set by the prior. From the definition, it is clear that the
complexity $\kappa(\epsilon)$ takes a small value if the prior is high for any
$Q\in\mathcal{Q}$ and in that case, it is equivalent to an approximate
completeness assumption. Please refer to Dann et al. (2021) for further
details on this metric.

We denote the sampled posterior by Algorithm 1 at episode $k$ by
$q_{k}^{\prime}$, which generally deviates from the true posterior $q_{k}$
defined in (3.2) due to the inherent limitations of approximate samplers
discussed in Section 3.2. At each episode k, we define the sampling error
$\delta_{k}=TV(q_{k},q_{k}^{\prime})$ as the TV distance between the true
posterior and the approximate posterior generated by our sampler.

Using the quantities defined above, we present our first theorem: a
frequentist (worst-case) expected regret bound for Algorithm 1:

######  Theorem 4.6.

Under Assumption 4.1, 4.2 and 4.3, if $\eta\leq 2/5b^{2}$, then

$\displaystyle\mathbb{E}[\text{Regret}(K)]\leq\frac{\lambda}{\eta}\mathcal{K}_{\text{DC}}+\frac{2K}{\lambda}\kappa(b/K^{2})+\frac{6H}{\lambda}+\frac{b}{K}+\sum_{k=1}^{K}\left[\left(\frac{\eta}{4\lambda}b^{2}H(k-1)+b\right)\cdot\delta_{k}\right],$

where the expectation incorporates the inherent randomness of the MDP through
samples drawn from it and the algorithm’s own stochastic elements. If we
further set $\eta=1/4b^{2}$,
$\lambda=\sqrt{K\kappa(b/K^{2})/b^{2}\mathcal{K}_{\text{DC}}}$ and assume
$\lambda b^{2}\geq 1$ and without loss of generality that $b\geq 16$, then the
bound becomes

$\displaystyle\mathbb{E}[\text{Regret}(K)]=O\left(b\sqrt{\mathcal{K}_{\text{DC}}\kappa(b^{2}/K)K}+b^{2}H+\frac{b}{K}\right)+\frac{1}{16}b^{2}\sum_{k=1}^{K}k\delta_{k}.$
(4.2)

######  Remark 4.7.

It is important to emphasize that the theorem establishes the relationship
between the regret and the sampling error, without necessarily asserting that
the sampling error $\delta_{k}$ is small for general function classes. In
Section 4.3, we delve deeper into controlling the sampling error with respect
to the sampling complexity for linear MDPs.

######  Remark 4.8.

The final term in (4.2) highlights that during initial episodes (small $k$),
our approximate samplers can have relaxed accuracy requirements. This aligns
with the algorithm’s exploratory phase, where precise posterior estimates are
less crucial compared to later exploitation stages when accurate value
estimation becomes critical.

######  Remark 4.9.

The derived regret bound from Theorem 4.6, can be decomposed into two parts:

$R_{origin}=\frac{\lambda}{\eta}\mathcal{K}_{\text{DC}}+\frac{2K}{\lambda}\kappa(b/K^{2})+\frac{6H}{\lambda}+\frac{b}{K},\quad\mathrm{and}\quad
R_{sample}=\sum_{k=1}^{K}\left[\left(\frac{\eta}{4\lambda}b^{2}H(k-1)+b\right)\cdot\delta_{k}\right].$
(4.3)

Here $R_{sample}$ accounts for the sampling error. It is noteworthy that
$R_{origin}$ mirrors Theorem 1 from Dann et al. (2021), and consequently, we
adhere to their analytical framework for deriving this part. For $R_{sample}$,
we separately examine different samplers for their respective sampling
complexities.

######  Remark 4.10.

Note that if we can do TS exactly at each step, i.e. $\delta_{k}=0$ for all
$k$, then Theorem 4.6 reduces to Theorem 1 in Dann et al. (2021). Also as
discussed in their work, the decoupling coefficient $\mathcal{K}_{\text{DC}}$
can vary in different settings.

###  4.2 Analysis of Errors Induced by Approximating Samplers

It is important to note that $\delta_{k}$ within Theorem 4.6 cannot be
directly controlled by the chosen approximating samplers employed in Algorithm
1. Therefore, a further decomposition of this term is necessary (see details
in Section A.3):

######  Proposition 4.11.

Let $\delta_{k}^{h}$ be the sampling error (in the total variation sense)
induced by our sampler at step $h\in[H]$ and episode $k\in[K]$ and let
$\delta_{k}$ be as defined in Section 4.1. Then
$\delta_{k}\leq\sum_{h=1}^{H}\delta_{k}^{h}$.

######  Remark 4.12.

Proposition 4.11 allows us to decompose the sampling error $\delta_{k}$ into
individual components $\delta_{k}^{h}$, representing the total variation
distance at step $h$ within episode $k$. Notably, these individual components
$\delta_{k}^{h}$ are directly controllable by our approximate samplers. This
translates to the overall sampling error
$\delta_{k}\leq\sum_{h=1}^{H}\delta_{k}^{h}$ highlighting the crucial role of
sampler accuracy in each step in managing the cumulative error
$\sum_{h=1}^{H}\delta_{k}^{h}$.

######  Remark 4.13.

One should expect both sampling error and truncation error to contribute to
the total error $\delta_{k}$, however, by considering truncation as a
transport map between probability distributions and assuming that the exact
target distribution is invariant with respect to the truncation due to its
belonging to the given function class $\mathcal{Q}$, we are able to disregard
the effect of truncation error using the data-processing inequality. See
Appendix A.3 for details.

The proposition implies that the regret arising from the approximate sampler
defined in (4.3) is upper-bounded by
$R_{sample}\leq\sum_{k=1}^{K}\big{[}(\eta/4\lambda)b^{2}H(k-1)+b)\cdot\sum_{h=1}^{H}\delta_{k}^{h}\big{]}$.

###  4.3 Applications to Linear MDPs

|  |  | Computational | Sampling
---|---|---|---|---
Algorithm | Regret | Exploration | Tractability | Complexity
LSVI-UCB (Jin et al., 2020) | $\tilde{\mathcal{O}}(d^{3/2}H^{3/2}\sqrt{T})$ | UCB | Yes | NA
OPT-RLSVI (Zanette et al., 2020a) | $\tilde{\mathcal{O}}(d^{2}H^{2}\sqrt{T})$ | TS | Yes | NA
ELEANOR (Zanette et al., 2020b) | $\tilde{\mathcal{O}}(dH^{3/2}\sqrt{T})$ | Optimism | No | NA
CPS (Dann et al., 2021) | $\tilde{\mathcal{O}}(dH^{2}\sqrt{T})$ | FGTS | No | NA
LSVI-PHE (Ishfaq et al., 2021) | $\tilde{\mathcal{O}}(d^{3/2}H^{3/2}\sqrt{T})$ | TS | Yes | NA
LMC-LSVI (Ishfaq et al., 2024) | $\tilde{\mathcal{O}}(d^{3/2}H^{3/2}\sqrt{T})$ | LMC | Yes | $\tilde{\Theta}(\frac{\kappa^{3}K^{3}H^{3}}{d\ln(dT)})$
LSVI-ASE with LMC sampler | $\tilde{\mathcal{O}}(dH^{3/2}\sqrt{T})$ | FGTS & LMC | Yes | $\tilde{\Theta}(\frac{\kappa^{3}K^{3}H^{3}}{d\ln(dT)})$
LSVI-ASE with ULMC sampler | $\tilde{\mathcal{O}}(dH^{3/2}\sqrt{T})$ | FGTS & ULMC | Yes | $\tilde{\Theta}(\frac{\kappa^{3/2}K^{2}H^{2}}{\sqrt{d\ln(dT)}})$

Table 1: Regret upper bound for episodic, non-stationary, linear MDPs. Here,
computational tractability refers to the ability of a computational problem to
be solved in a reasonable amount of time using a feasible amount of
computational resources.

A concrete example where we can interpret the regret bound from Theorem 4.6 is
the linear MDP (Jin et al., 2020; Yang & Wang, 2020; 2019) setting.

######  Definition 4.14.

(Linear MDP). An MDP $(\mathcal{S},\mathcal{A},H,\mathbb{P},r)$ is said to be
a linear MDP with a feature
$\phi:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}^{d}$, if for any
$h\in[H]$, there exist $d$ unknown (signed) measures
$\mu_{h}=(\mu_{h}^{(1)},\ldots,\mu_{h}^{(d)})$ over $\mathcal{S}$ and an
unknown vector $\theta_{h}\in\mathbb{R}^{d}$ such that for any
$(x,a)\in\mathcal{S}\times\mathcal{A}$, we have
$\mathbb{P}_{h}(\cdot|x,a)=\langle\phi(x,a),\mu_{h}(\cdot)\rangle$ and
$r_{h}(x,a)=\langle\phi(x,a),\theta_{h}\rangle$.

Without loss of generality, we assume $\|\phi(x,a)\|_{2}\leq 1$ for all
$(x,a)\in\mathcal{S}\times\mathcal{A}$, and
$\max\\{\|\mu_{h}(\mathcal{S})\|_{2},\|\theta_{h}\|_{2}\\}\leq\sqrt{d}$ for
all $h\in[H]$.

We first bound $\kappa(\epsilon)$ defined in Definition 4.5 for linear MDP.
While previous work by Dann et al. (2021) provides bounds with a uniform prior
distribution over the function class, it does not align with the way TS
algorithms are implemented in practice. For this, we consider a Gaussian
distribution as the prior distribution.

######  Lemma 4.15.

If the stage-wise priors $p_{0}^{h}$ are chosen as
$\mathcal{N}(0,\sqrt{d}HI_{d})$, then
$\kappa(\epsilon)=dHO(\ln(dH/\epsilon))$.

######  Remark 4.16.

While Gaussian priors are commonly used (He et al., 2015; Goodfellow et al.,
2016), we highlight that the prior distribution $p_{0}^{h}$ can be any
distribution in practice, as long as a suitable bound for $\kappa(\epsilon)$
exists. This flexibility allows for incorporating domain-specific knowledge
into the prior.

We can now illustrate Theorem 4.6 for linear MDP:

######  Corollary 4.17.

If we set $\eta=2/5H^{2}$ and
$\lambda=\sqrt{K\kappa(H/K^{2})/dH^{3}(1+\ln(2T))}$, then the expected regret
of Algorithm 1 after $K$ episodes in a linear MDP is bounded as

$\displaystyle\textstyle\mathbb{E}[\text{Regret}(K)]=O(dH^{\frac{3}{2}}\sqrt{T}\ln(dT))+\sum_{k=1}^{K}\alpha_{k}\big{(}\sum_{h=1}^{H}\delta_{k}^{h}\big{)},$

where $\alpha_{k}=O(\sqrt{\ln(dT)/K}H^{2}k)$ and $T=HK$ is the total number of
steps.

###  4.4 Sampling Complexity of Different Samplers

In this section, we characterize the sampling complexity of the proposed
algorithms to demonstrate that we can achieve the desired regret bound as long
as the chosen sampler is executed a sufficient number of times. We begin by
establishing an appropriate notion of complexity.

######  Definition 4.18.

(Sampling Complexity) The agent has access to the gradient
$\nabla_{w}Q(w;\phi(x,a))$ for any $w\in\mathbb{R}^{d}$. Then, if
$\nabla_{w}Q$ is evaluated $G_{k}$ times at any episode $k\in[K]$, then we
define $G_{k}$ as the sampling complexity at episode $k$, and
$SC=\sum_{k\in[K]}G_{k}$ be the cumulative sampling complexity.

######  Remark 4.19.

In Algorithm 1, $G_{k}$ specifically represents the total number of iterations
employed by our approximate samplers from line 5 to line 9 during episode $k$.
It follows that within our analysis, $G_{k}=J_{k}$ and
$SC=\sum_{k\in[K]}G_{k}=\sum_{k\in[K]}J_{k}$.

######  Theorem 4.20.

Consider a linear MDP defined in Definition 4.14. Assume that there exists
$\kappa>0$ such that for any $(k,h)\in[K]\times[H]$, the loss function defined
in (3.1) satisfies $M_{k,h}I\geq\nabla^{2}L_{h}^{k}\geq m_{k,h}I$ and
$M_{k,h}/m_{k,h}\leq\kappa$ for some $M_{k,h}\geq m_{k,h}>0$. Then we can
achieve the regret bound of $O(dH^{\frac{3}{2}}\sqrt{T}\ln(dT))$ using our
approximate samplers with the cumulative sampling complexity stated below:
(1) LMC: $SC=\tilde{\Theta}(\frac{\kappa^{3}K^{3}H^{3}}{d\ln(dT)})$ with step
size $\tau_{k,h}=\tilde{\Theta}(\frac{d\ln(dT)}{M_{k,h}H^{2}k^{2}\kappa})$;
(2) ULMC: $SC=\tilde{\Theta}(\frac{\kappa^{3/2}K^{2}H^{2}}{\sqrt{d\ln(dT)}})$
with step size $\tau_{k,h}=\tilde{\Theta}(\frac{\sqrt{d\ln(dT)}}{M_{k,h}Hk})$.

######  Remark 4.21.

Theorem 4.20 reveals a critical relationship between the choice of sampling
method and the sampling complexity of Algorithm 1. Leveraging established
results on demonstrating the faster mixing of ULMC over LMC in strongly log-
concave settings (see Appendix B for details), the theorem confirms that
Algorithm 1, when employing ULMC, achieves the desired accuracy with lower
data requirements than its LMC-based counterpart. This aligns with the
intuitive notion that ULMC’s momentum-based exploration enables faster
learning, thereby reducing the necessary data for effective Thompson sampling.

##  5 Experiments

In this section, we provide an empirical evaluation of our proposed algorithms
with deep Q-networks (DQNs) (Mnih et al., 2015) in two sets of environments:
(1) the N-chain environment (Osband et al., 2016a) and (2) the Atari game
suite (Bellemare et al., 2013; Taiga et al., 2019). We evaluate our algorithms
with different implementations. In particular, we implement the Algorithm 1
with different choices of prior terms and samplers. By choosing Feel-Good
exploration prior term in (3.1) and underdamped Langevin Monte Carlo sampler
with adaptive bias term in (3.5), we implement the Algorithm 1 named as Feel-
Good Underdamped Langevin Monte Carlo Deep Q-Network (FG-ULMCDQN). We
implement the Algorithm 1 with the Feel-Good exploration prior term and the
adaptive Langevin Monte Carlo sampler introduced in Ishfaq et al. (2024),
named Feel-Good Langevin Monte Carlo Deep Q-Network (FG-LMCDQN). We also
provide an implementation for the Algorithm 1 without the Feel-Good
exploration prior term named Underdamped Langevin Monte Carlo Deep Q-Network
(ULMCDQN). Then we evaluate our implementations in the above mentioned
environments. Our code is available at https://github.com/panxulab/LSVI-ASE.

###  5.1 Experiments in N-Chain

We demonstrate that our proposed algorithms can explore effectively in sparse-
reward environment by conducting experiments in $N$-Chain environment (Osband
et al., 2016a) that demands deep exploration capabilities to perform well. An
$N$-chain environment can be constructed by a chain of $N>3$ states denoted by
$s_{1},s_{2},\ldots,s_{N}$. Each episode of interaction, which starts at state
$s_{2}$, lasts for $N+9$ steps and in each step the agent can either move to
the left or right. A myopic agent would gravitate toward state $s_{1}$ which
has a small reward of $r=0.001$ whereas an efficient agent with deep
exploration capabilities would try to reach state $s_{N}$ which has a larger
reward of $r=1$. As each episode runs for $N+9$ steps, the optimal return for
an episode is $10$. We refer the reader to Section C.1 for a depiction of the
environment.

Figure 1: A comparison of different methods in $N$-chain with different chain
lengths $N$. As $N$ increases, the exploration hardness increases. All results
are averaged over $20$ runs and the shaded areas represent $95\%$ confidence
interval.

In our experiments, we progressively increase the difficulty level by setting
$N$ to be $25$, $50$, $75$, and $100$. For each chain length, we run each
learning algorithm for $10^{5}$ steps across $20$ seeds. As baseline
algorithms, we use DQN (Mnih et al., 2015), Bootstrapped DQN (Osband et al.,
2016a), Noisy-Net (Fortunato et al., 2018) and Adam LMCDQN (Ishfaq et al.,
2024). The performance of each algorithm in each run is measured by the mean
return of the last $10$ evaluation episodes. We sweep the learning rate and
pick the one with the best performance for each algorithm. For our algorithms
which use ULMC as a sampler, we sweep the friction coefficient $\gamma$. For
FG-LMCDQN and FG-ULMCDQN, we sweep the weight for the feel-good prior term
$\eta$ in the loss function. Please check Section C.1 for further details.

Figure 1 shows the performance of our proposed algorithms as well as the
baseline algorithms under different chain lengths. The solid lines represent
the average return over $20$ random seeds and the shaded areas represent the
$95\%$ confidence interval. For all of our proposed algorithms, namely
ULMCDQN, FG-ULMCDQN and FG-LMCDQN, we set $J_{k}=4$ in Algorithm 1 for all
chain lengths.

From Figure 1, we see that as the chain length $N$ increases, the performance
of the baselines drops drastically. Whereas, our FGTS based algorithms FG-
LMCDQN and FG-ULMCDQN are able to maintain steady performance. In particular,
we would like to highlight that FG-ULMCDQN is able to get almost close to the
optimal return of $10$ for all values of $N$, showing the benefit of using
Feel Good prior along with underdamped LMC together in environments where deep
exploration is absolutely necessary to perform well.

###  5.2 Experiments in Atari Games

Figure 2: The return curves of various algorithms in eight hard Atari tasks
over 50 million training frames. Solid lines correspond to the median
performance over 5 random seeds, and the shaded areas correspond to $95\%$
confidence interval.

We evaluate our algorithms in 8 visually complicated hard exploration games,
namely Alien, Freeway, Gravitar, H.E.R.O., Pitfall, Qbert, Solaris, and
Venture from the Atari game suite (Bellemare et al., 2013; Taiga et al.,
2019). As classified in Taiga et al. (2019), among these games, Alien,
H.E.R.O., and Qbert are dense reward environments and Freeway, Gravitar,
Pitfall, Solaris, and Venture are sparse reward environments. In our
experiments, we set $J_{k}=1$ in Algorithm 1 to finish the training in a
reasonable time. Following (Ishfaq et al., 2024), we also incorporate the
double Q trick (Van Hasselt, 2010; Van Hasselt et al., 2016) in our
implementation. As baselines we consider Adam LMCDQN (Ishfaq et al., 2024),
Noisy-Net (Fortunato et al., 2018), Prioritized DQN (Schaul et al., 2015), C51
(Bellemare et al., 2017), Bootstrapped DQN (Osband et al., 2016a) and IQN
(Dabney et al., 2018). All algorithms are trained for 50M frames (i.e., 12.5M
steps) and run for 5 different random seeds. We refer the reader to Section
C.2.1 for further details on training and hyper-parameter choices. Figure 2
depicts the learning curves of all algorithms in 8 Atari games. Compared to
the baseline algorithms, our algorithms appear to be quite competitive despite
being much simpler in implementation. We highlight the advantages of
approximate sampling based algorithms in Gravitar and Venture.

(a) Different FG prior weight $\eta$ in FG-ULMCDQN

(b) Different friction coefficient $\gamma$ in ULMCDQN

Figure 3: (a) A comparison of FG-ULMCDQN with different values of weight
$\eta$ for the feel good prior term in Alien. Solid lines correspond to the
average performance over 5 random seeds, and shaded areas correspond to $95\%$
confidence interval. The performance of FG-ULMCDQN is not very sensitive to
the values of $\eta$ as long it is not very large. (b) A comparison of ULMCDQN
with different values of the friction coefficient $\gamma$ in Alien.

Sensitivity Analysis. In Figure 3(a), we draw the learning curves of FG-
ULMCDQN with different weight factor $\eta$ for the FG prior term. We observe
that as long the value of $\eta$ is not too high, the performance of FG-
ULMCDQN is less sensitive to the value of $\eta$. In Figure 3(b), we observe
that for very high or low value of friction coefficient $\gamma$, the
performance of ULMCDQN collapses.

##  6 Conclusion

This work introduces a novel algorithmic framework that leverages efficient
approximate samplers to make FGTS practical for real-world RL. Unlike prior
approaches reliant on unrealistic sampling oracles, our framework enables
computationally feasible exploration. Furthermore, our theoretical analysis
provides a deeper understanding of the relationship between samplers and
regret in FGTS algorithms. This newfound knowledge paves the way for practical
exploration strategies with strong provable guarantees. Notably, our algorithm
achieves an improved regret bound in linear MDPs, and showcases consistent
performance in deep exploration environments.

Future directions include exploring the integration of alternative approximate
samplers within our framework. Promising candidates include Metropolis-
adjusted Langevin Acceptance (MALA) (Besag et al., 1995) and various proximal
sampling algorithms (Lee et al., 2021). Investigating efficient methods to
incorporate these samplers into the RL setting while maintaining the
framework’s strengths will further enhance its applicability to diverse
exploration problems.

#### Acknowledgments

We gratefully acknowledge funding from the Canada CIFAR AI Chairs program, the
Reinforcement Learning and Artificial Intelligence (RLAI) laboratory, Mila -
Quebec Artificial Intelligence Institute, the Natural Sciences and Engineering
Research Council (NSERC) of Canada, the US National Science Foundation
(DMS-2323112) and the Whitehead Scholars Program at the Duke University School
of Medicine. Qingfeng Lan would also like to acknowledge Alberta Innovates for
the support they provided him for his research.

## References

  * Agarwal & Zhang (2022a) Alekh Agarwal and Tong Zhang.  Model-based RL with optimistic posterior sampling: Structural conditions and sample complexity.  In _Advances in Neural Information Processing Systems_ , 2022a.
  * Agarwal & Zhang (2022b) Alekh Agarwal and Tong Zhang.  Non-linear reinforcement learning in large action spaces: Structural conditions and sample-efficiency of posterior sampling.  In _Conference on Learning Theory_ , pp. 2776–2814. PMLR, 2022b.
  * Bellemare et al. (2013) Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling.  The arcade learning environment: An evaluation platform for general agents.  _Journal of Artificial Intelligence Research_ , 47:253–279, 2013.
  * Bellemare et al. (2017) Marc G Bellemare, Will Dabney, and Rémi Munos.  A distributional perspective on reinforcement learning.  In _International Conference on Machine Learning_ , pp. 449–458. PMLR, 2017.
  * Bertsekas (2019) Dimitri Bertsekas.  _Reinforcement learning and optimal control_.  Athena Scientific, 2019.
  * Besag et al. (1995) Julian Besag, Peter Green, David Higdon, and Kerrie Mengersen.  Bayesian computation and stochastic systems.  _Statistical science_ , pp. 3–41, 1995.
  * Brooks et al. (2011) Steve Brooks, Andrew Gelman, Galin Jones, and Xiao-Li Meng.  _Handbook of Markov Chain Monte Carlo_.  Chapman and Hall/CRC, May 2011.  ISBN 9780429138508.  doi: 10.1201/b10905.  URL http://dx.doi.org/10.1201/b10905.
  * Chen et al. (2014) Tianqi Chen, Emily Fox, and Carlos Guestrin.  Stochastic gradient Hamiltonian Monte Carlo.  In _International Conference on Machine Learning_ , pp. 1683–1691. PMLR, 2014.
  * Cheng et al. (2018) Xiang Cheng, Niladri S Chatterji, Peter L Bartlett, and Michael I Jordan.  Underdamped Langevin MCMC: A non-asymptotic analysis.  In _Conference on Learning Theory_ , pp. 300–323. PMLR, 2018.
  * Chewi et al. (2022) Sinho Chewi, Murat A Erdogdu, Mufan Li, Ruoqi Shen, and Shunshi Zhang.  Analysis of Langevin Monte Carlo from Poincare to Log-Sobolev.  In _Conference on Learning Theory_ , pp. 1–2. PMLR, 2022.
  * Dabney et al. (2018) Will Dabney, Georg Ostrovski, David Silver, and Rémi Munos.  Implicit quantile networks for distributional reinforcement learning.  In _International Conference on Machine Learning_ , pp. 1096–1105. PMLR, 2018.
  * Dalalyan (2017) Arnak S Dalalyan.  Theoretical guarantees for approximate sampling from smooth and log-concave densities.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 79(3):651–676, 2017.
  * 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.
  * Durmus et al. (2019) Alain Durmus, Szymon Majewski, and Błażej Miasojedow.  Analysis of Langevin Monte Carlo via convex optimization.  _The Journal of Machine Learning Research_ , 20(1):2666–2711, 2019.
  * Dwaracherla & Van Roy (2020) Vikranth Dwaracherla and Benjamin Van Roy.  Langevin DQN.  _arXiv preprint arXiv:2002.07282_ , 2020.
  * Fortunato et al. (2018) Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Matteo Hessel, Ian Osband, Alex Graves, Volodymyr Mnih, Remi Munos, Demis Hassabis, Olivier Pietquin, Charles Blundell, and Shane Legg.  Noisy networks for exploration.  In _International Conference on Learning Representations_ , 2018.
  * Goodfellow et al. (2016) Ian Goodfellow, Yoshua Bengio, and Aaron Courville.  _Deep learning_.  MIT press, 2016.
  * He et al. (2015) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Delving deep into rectifiers: Surpassing human-level performance on imagenet classification.  In _Proceedings of the IEEE International Conference on Computer Vision_ , pp. 1026–1034, 2015.
  * Hsu et al. (2024) Hao-Lun Hsu, Weixin Wang, Miroslav Pajic, and Pan Xu.  Randomized exploration in cooperative multi-agent reinforcement learning.  _arXiv preprint arXiv:2404.10728_ , 2024.
  * Ishfaq et al. (2021) Haque Ishfaq, Qiwen Cui, Viet Nguyen, Alex Ayoub, Zhuoran Yang, Zhaoran Wang, Doina Precup, and Lin Yang.  Randomized exploration in reinforcement learning with general value function approximation.  In _International Conference on Machine Learning_ , pp. 4607–4616. PMLR, 2021.
  * Ishfaq et al. (2024) Haque Ishfaq, Qingfeng Lan, Pan Xu, A Rupam Mahmood, Doina Precup, Anima Anandkumar, and Kamyar Azizzadenesheli.  Provable and practical: Efficient exploration in reinforcement learning via Langevin Monte Carlo.  In _The Twelfth International Conference on Learning Representations_ , 2024.
  * Jin et al. (2020) Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan.  Provably efficient reinforcement learning with linear function approximation.  In _Conference on Learning Theory_ , pp. 2137–2143. PMLR, 2020\.
  * Jin et al. (2021) Chi Jin, Qinghua Liu, and Sobhan Miryoosefi.  Bellman eluder dimension: New rich classes of RL problems, and sample-efficient algorithms.  _Advances in Neural Information Processing Systems_ , 34:13406–13418, 2021.
  * Kingma & Ba (2014) Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  _arXiv preprint arXiv:1412.6980_ , 2014.
  * Lee et al. (2021) Yin Tat Lee, Ruoqi Shen, and Kevin Tian.  Structured logconcave sampling with a restricted Gaussian oracle.  In _Conference on Learning Theory_ , pp. 2993–3050. PMLR, 2021\.
  * Li et al. (2024) Yingru Li, Jiawei Xu, Lei Han, and Zhi-Quan Luo.  Q-star meets scalable posterior sampling: Bridging theory and practice via hyperagent.  In _Forty-first International Conference on Machine Learning_ , 2024\.
  * 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.
  * Osband et al. (2013) Ian Osband, Daniel Russo, and Benjamin Van Roy.  (More) efficient reinforcement learning via posterior sampling.  In _Advances in Neural Information Processing Systems_ , pp. 3003–3011, 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_ , pp. 2377–2386. PMLR, 2016b.
  * Osband et al. (2018) Ian Osband, John Aslanides, and Albin Cassirer.  Randomized prior functions for deep reinforcement learning.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Plappert et al. (2018) Matthias Plappert, Rein Houthooft, Prafulla Dhariwal, Szymon Sidor, Richard Y Chen, Xi Chen, Tamim Asfour, Pieter Abbeel, and Marcin Andrychowicz.  Parameter space noise for exploration.  In _International Conference on Learning Representations_ , 2018.
  * Quan & Ostrovski (2020) John Quan and Georg Ostrovski.  DQN Zoo: Reference implementations of DQN-based agents, 2020.  URL http://github.com/deepmind/dqn_zoo.
  * Russo (2019) Daniel Russo.  Worst-case regret bounds for exploration via randomized value functions.  In _Advances in Neural Information Processing Systems_ , pp. 14410–14420, 2019.
  * Schaul et al. (2015) Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver.  Prioritized experience replay.  _arXiv preprint arXiv:1511.05952_ , 2015.
  * Strens (2000) Malcolm Strens.  A Bayesian framework for reinforcement learning.  In _ICML_ , volume 2000, pp. 943–950, 2000.
  * Taiga et al. (2019) Adrien Ali Taiga, William Fedus, Marlos C Machado, Aaron Courville, and Marc G Bellemare.  On bonus based exploration methods in the Arcade learning environment.  In _International Conference on Learning Representations_ , 2019.
  * 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.
  * Van Hasselt (2010) Hado Van Hasselt.  Double Q-learning.  _Advances in Neural Information Processing Systems_ , 23, 2010.
  * Van Hasselt et al. (2016) Hado Van Hasselt, Arthur Guez, and David Silver.  Deep reinforcement learning with double Q-learning.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2016.
  * Vempala & Wibisono (2019) Santosh Vempala and Andre Wibisono.  Rapid convergence of the unadjusted Langevin algorithm: Isoperimetry suffices.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Welling & Teh (2011) Max Welling and Yee W Teh.  Bayesian learning via stochastic gradient Langevin dynamics.  In _Proceedings of the 28th International Conference on Machine Learning (ICML-11)_ , pp. 681–688. Citeseer, 2011.
  * Weng et al. (2022) Jiayi Weng, Huayu Chen, Dong Yan, Kaichao You, Alexis Duburcq, Minghao Zhang, Yi Su, Hang Su, and Jun Zhu.  Tianshou: A highly modularized deep reinforcement learning library.  _Journal of Machine Learning Research_ , 2022.
  * Xiong et al. (2022) Zhihan Xiong, Ruoqi Shen, Qiwen Cui, Maryam Fazel, and Simon Shaolei Du.  Near-optimal randomized exploration for tabular Markov decision processes.  In _Advances in Neural Information Processing Systems_ , 2022.
  * Xu et al. (2018) Pan Xu, Jinghui Chen, Difan Zou, and Quanquan Gu.  Global convergence of Langevin dynamics based algorithms for nonconvex optimization.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Xu et al. (2022) Pan Xu, Hongkai Zheng, Eric V Mazumdar, Kamyar Azizzadenesheli, and Animashree Anandkumar.  Langevin Monte Carlo for contextual bandits.  In _International Conference on Machine Learning_ , pp. 24830–24850. PMLR, 2022.
  * Yang & Wang (2019) Lin Yang and Mengdi Wang.  Sample-optimal parametric Q-learning using linearly additive features.  In _International Conference on Machine Learning_ , pp. 6995–7004. PMLR, 2019.
  * Yang & Wang (2020) Lin Yang and Mengdi Wang.  Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound.  In _International Conference on Machine Learning_ , pp. 10746–10756. PMLR, 2020.
  * Zanette et al. (2020a) 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_ , pp. 1954–1964. PMLR, 2020a.
  * Zanette et al. (2020b) Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill.  Learning near optimal policies with low inherent Bellman error.  In _International Conference on Machine Learning_ , pp. 10978–10989. PMLR, 2020b.
  * Zhang et al. (2023) Shunshi Zhang, Sinho Chewi, Mufan Li, Krishna Balasubramanian, and Murat A Erdogdu.  Improved discretization analysis for underdamped Langevin Monte Carlo.  In _The Thirty Sixth Annual Conference on Learning Theory_ , pp. 36–71. PMLR, 2023.
  * Zhang (2022) Tong Zhang.  Feel-good Thompson sampling for contextual bandits and reinforcement learning.  _SIAM Journal on Mathematics of Data Science_ , 4(2):834–857, 2022.
  * Zheng et al. (2024) Haoyang Zheng, Wei Deng, Christian Moya, and Guang Lin.  Accelerating approximate Thompson sampling with underdamped Langevin Monte Carlo.  _arXiv preprint arXiv:2401.11665_ , 2024.
  * Zou et al. (2021) Difan Zou, Pan Xu, and Quanquan Gu.  Faster convergence of stochastic gradient Langevin dynamics for non-log-concave sampling.  In _Uncertainty in Artificial Intelligence_ , pp. 1152–1162. PMLR, 2021.

##  Appendix A Regret Analysis

###  A.1 Proof of Main Results

In this section, we restate and provide the proof of our main result Theorem
4.6 and its corollary for the linear MDP.

######  Theorem A.1.

[Restatement of Theorem 4.6] Under Assumption 4.1, 4.2 and 4.3, if $\eta\leq
2/5b^{2}$, then

$\displaystyle\mathbb{E}[\text{Regret}(K)]\leq\frac{\lambda}{\eta}\mathcal{K}_{\text{DC}}+\frac{2K}{\lambda}\kappa(b/K^{2})+\frac{6H}{\lambda}+\frac{b}{K}+\sum_{k=1}^{K}\left[\left(\frac{\eta}{4\lambda}b^{2}H(k-1)+b\right)\cdot\delta_{k}\right],$

where the expectation incorporates the inherent randomness of the MDP
environment through samples drawn from it and the algorithm’s own stochastic
elements. If we further set $\eta=1/4b^{2}$ and
$\lambda=\sqrt{\frac{K\kappa(b/K^{2})}{b^{2}\mathcal{K}_{\text{DC}}}}$ and
assume $\lambda b^{2}\geq 1$ and without loss of generality that $b\geq 16$,
then the bound becomes

$\displaystyle\mathbb{E}[\text{Regret}(K)]=O\left(b\sqrt{\mathcal{K}_{\text{DC}}\kappa(b^{2}/K)K}+b^{2}H+\frac{b}{K}\right)+\frac{1}{16}b^{2}\sum_{k=1}^{K}k\delta_{k}.$
(A.1)

###### Proof of Theorem 4.6.

Given any policy $\pi^{k}$ and initial state $x_{1}^{k}$, by Lemma A.4, we can
decompose the regret:

$\displaystyle\text{REG}_{k}$
$\displaystyle=\sum_{h=1}^{H}\mathbb{E}_{\pi^{k}}\left[Q_{h}^{k}(x_{h}^{k},a_{h}^{k})-r_{h}(x_{h}^{k},a_{h}^{k})-\mathbb{E}_{x_{h+1}\sim\mathbb{P}_{h}(\cdot|x_{h}^{k},a_{h}^{k})}\max_{a\in\mathcal{A}}Q_{h+1}^{k}(x_{h+1},a)\right]$
$\displaystyle\qquad-\left[V_{1}^{k}(x_{1}^{k})-V_{1}^{*}(x_{1}^{k})\right]$
$\displaystyle=:\sum_{h=1}^{H}\text{BE}_{k}^{h}-\text{FG}_{k}.$

and hence we can rewrite the expected regret of episode $k$ (scaled by
$\lambda$) as

$\displaystyle\lambda\mathbb{E}_{Q^{k}\sim q_{k}^{\prime}}\text{REG}_{k}$
$\displaystyle=\lambda\mathbb{E}_{Q^{k}\sim
q_{k}^{\prime}}\bigg{[}\sum_{h=1}^{H}\text{BE}_{k}^{h}-\text{FG}_{k}\bigg{]}$
$\displaystyle=\mathbb{E}_{Q^{k}\sim
q_{k}^{\prime}}\sum_{h=1}^{H}\bigg{[}\lambda\text{BE}_{k}^{h}-\frac{\eta}{4}\sum_{s=1}^{k-1}\mathbb{E}_{[x_{h},a_{h}]\sim
p(\cdot|Q^{s},x_{1})}[\mathcal{E}_{h}(Q^{k};x_{h},a_{h})]^{2}\bigg{]}$
$\displaystyle\quad+\mathbb{E}_{Q^{k}\sim
q_{k}^{\prime}}\bigg{[}\sum_{h=1}^{H}\frac{\eta}{4}\sum_{s=1}^{k-1}\mathbb{E}_{[x_{h},a_{h}]\sim
p(\cdot|Q^{s},x_{1})}[\mathcal{E}_{h}(Q^{k};x_{h},a_{h})]^{2}-\lambda\text{FG}_{k}\bigg{]}$
$\displaystyle=:F_{k}^{dc}+F_{k}^{\kappa}.$

Summing over $k=1,2,\ldots,K$, we obtain that

$\displaystyle\lambda\mathbb{E}[\text{Regret}(K)]=\sum_{k=1}^{K}F_{k}^{dc}+\sum_{k=1}^{K}F_{k}^{\kappa}.$

Using Definition 4.4, we can bound the first term by

$\displaystyle\sum_{k=1}^{K}F_{k}^{dc}\leq\frac{\lambda^{2}}{\eta}\mathcal{K}_{\text{DC}}$
(A.2)

for any $\frac{\eta}{4\lambda}<1$. For the $F_{k}^{\kappa}$ term, by
Assumption 4.2, $\mathcal{E}_{h}(Q^{k};x_{h},a_{h})^{2}\leq b^{2}$ and
$|\text{FG}_{k}|\leq b$. Therefore,

$\displaystyle\left\lvert\sum_{h=1}^{H}\frac{\eta}{4}\sum_{s=1}^{k-1}\mathbb{E}_{[x_{h},a_{h}]\sim
p(\cdot|Q^{s},x_{1})}[\mathcal{E}_{h}(Q^{k};x_{h},a_{h})]^{2}-\lambda\text{FG}_{k}\right\rvert\leq\frac{\eta}{4}b^{2}H(k-1)+\lambda
b.$

Then by the property of total variation distance,

$\displaystyle F_{k}^{\kappa}\leq\mathbb{E}_{Q^{k}\sim
q_{k}}\bigg{[}\sum_{h=1}^{H}\frac{\eta}{4}\sum_{s=1}^{k-1}\mathbb{E}_{[x_{h},a_{h}]\sim
p(\cdot|Q^{s},x_{1})}[\mathcal{E}_{h}(Q^{k};x_{h},a_{h})]^{2}-\lambda\text{FG}_{k}\bigg{]}+\bigg{[}\frac{\eta}{4}b^{2}H(k-1)+\lambda
b\bigg{]}\cdot\delta_{k},$

where $\delta_{k}=TV(q_{k},q_{k}^{\prime}).$ The first term on the right
handside is exactly the analog of $F_{k}^{\kappa}$ with the expectation taken
over the exact target distribution of our algorithm. By Theorem A.5 (which is
Theorem 1 of Dann et al. (2021)),

$\displaystyle\sum_{k=1}^{K}\mathbb{E}_{Q^{k}\sim
q_{k}}\bigg{[}\sum_{h=1}^{H}\frac{\eta}{4}\sum_{s=1}^{k-1}\mathbb{E}_{[x_{h},a_{h}]\sim
p(\cdot|Q^{s},x_{1})}[\mathcal{E}_{h}(Q^{k};x_{h},a_{h})]^{2}-\lambda\text{FG}_{k}\bigg{]}\leq
2K\kappa(b/K^{2})+6H+\frac{\lambda b}{K}.$

Hence

$\displaystyle\sum_{k=1}^{K}F_{k}^{\kappa}\leq
2K\kappa(b/T^{2})+6H+\frac{\lambda
b}{K}+\sum_{k=1}^{K}\bigg{[}\frac{\eta}{4}b^{2}H(k-1)+\lambda
b\bigg{]}\cdot\delta_{k}.$

Combining this inequality with (A.2), we obtain that

$\displaystyle\mathbb{E}[\text{Regret}(K)]$
$\displaystyle\leq\frac{1}{\lambda}\bigg{[}\sum_{k=1}^{K}F_{k}^{dc}+\sum_{k=1}^{K}F_{k}^{\kappa}\bigg{]}$
$\displaystyle\leq\frac{\lambda}{\eta}\mathcal{K}_{\text{DC}}+\frac{2K}{\lambda}\kappa(b/K^{2})+\frac{6H}{\lambda}+\frac{b}{K}+\sum_{k=1}^{K}\bigg{[}\frac{\eta}{4\lambda}b^{2}H(k-1)+b\bigg{]}\cdot\delta_{k}.$

If we further set $\eta=1/4b^{2}$ and
$\lambda=\sqrt{\frac{K\kappa(b/K^{2})}{b^{2}\mathcal{K}_{\text{DC}}}}$, then a
direct calculation gives us

$\displaystyle\frac{\lambda}{\eta}\mathcal{K}_{\text{DC}}+\frac{2K}{\lambda}\kappa(b/K^{2})+\frac{6H}{\lambda}=6b\sqrt{\mathcal{K}_{\text{DC}}\kappa(b/K^{2})K}+6H\sqrt{\frac{b^{2}\mathcal{K}_{\text{DC}}}{\kappa(b/K^{2})K}}.$

Since $\lambda b^{2}\geq 1$, we have

$\displaystyle\sqrt{\frac{b^{2}\mathcal{K}_{\text{DC}}}{\kappa(b/K^{2})K}}\leq
b^{2}.$

And since $b\geq 16$, we have

$\displaystyle\frac{\eta}{4\lambda}b^{2}H(k-1)+b\leq\frac{1}{16}b^{2}(k-1)+b\leq\frac{1}{16}b^{2}k.$

Combining these results, we obtain (4.2). ∎

Next, we restate Corollary 4.17 and provide proof for it.

######  Corollary A.2.

Assume Algorithm 1 is run on a $d$-dimensional linear MDP. If we set
$\eta=\frac{2}{5H^{2}}$ and
$\lambda=\sqrt{\frac{K\kappa(H/K^{2})}{dH^{3}(1+\ln(2T))}}$, then the expected
regret after $K$ episodes is bounded as

$\displaystyle\mathbb{E}[\text{Regret}(K)]\leq
O(dH^{\frac{3}{2}}\sqrt{T}\ln(dT))+\sum_{k=1}^{K}\alpha_{k}\big{(}\sum_{h=1}^{H}\delta_{k}^{h}\big{)},$

where $\alpha_{k}=O\bigg{(}\sqrt{\frac{\ln(dT)}{K}}H^{2}k\bigg{)}$ and $T=HK$
is the total number of steps.

###### Proof of Corollary 4.17.

For linear MDPs, by proposition A.8, $b=H$, $\mathcal{K}_{\text{DC}}\leq
2dH(1+2\ln(KH))$ and $\kappa(H/K^{2})=dH\ln(dHK)$. Therefore $R_{origin}$
defined in (4.3) becomes $O(dH^{\frac{3}{2}}\sqrt{T}\ln(dT))$. Moreover, by a
direct calculation,

$\displaystyle\alpha_{k}:=\frac{\eta}{4\lambda}b^{2}H(k-1)+b=O\bigg{(}\sqrt{\frac{\ln(dT)}{K}}H^{2}k\bigg{)}$

and hence $R_{sample}$ defined in (4.3) becomes

$\displaystyle\sum_{k=1}^{K}\alpha_{k}\delta_{k}\leq\sum_{k=1}^{K}\alpha_{k}\big{(}\sum_{h=1}^{H}\delta_{k}^{h}\big{)},$

where the last inequality is due to Proposition 4.11. In conclusion,

$\displaystyle\mathbb{E}[\text{Regret}(K)]\leq
R_{origin}+R_{sample}=O(dH^{\frac{3}{2}}\sqrt{T}\ln(dT))+\sum_{k=1}^{K}\alpha_{k}\big{(}\sum_{h=1}^{H}\delta_{k}^{h}\big{)}.$

∎

With this result, we are ready to prove Theorem 4.20:

######  Theorem A.3 (Restatement of Theorem 4.20).

Consider a linear MDP defined in Definition 4.14. Assume that there exists
$\kappa>0$ such that for any $(k,h)\in[K]\times[H]$, the loss function defined
in (3.1) satisfies for some $M_{k,h}\geq m_{k,h}>0$:

$\displaystyle M_{k,h}I\geq\nabla^{2}L_{h}^{k}\geq m_{k,h}I,\quad
M_{k,h}/m_{k,h}\leq\kappa.$

Then we can achieve the regret bound $O(dH^{\frac{3}{2}}\sqrt{T}\ln(dT))$
using our approximate samplers with the cumulative sampling complexity stated
below:
(1) LMC: $SC=\tilde{\Theta}(\frac{\kappa^{3}K^{3}H^{3}}{d\ln(dT)})$ with step
size $\tau_{k,h}=\tilde{\Theta}(\frac{d\ln(dT)}{M_{k,h}H^{2}k^{2}\kappa})$;
(2) ULMC: $SC=\tilde{\Theta}(\frac{\kappa^{3/2}K^{2}H^{2}}{\sqrt{d\ln(dT)}})$
with step size $\tau_{k,h}=\tilde{\Theta}(\frac{\sqrt{d\ln(dT)}}{M_{k,h}Hk})$.

###### Proof of Theorem 4.20.

We give the proof for ULMC. The proof for LMC is essentially the same using
Theorem B.1. Note that for linear MDP, if we let

$\displaystyle\max_{h\in[H]}\delta_{k}^{h}\leq\frac{O(Hd\ln(dT)/\sqrt{K})}{\alpha_{k}}=O\left(\frac{d\sqrt{\ln(dT)}}{Hk}\right)$
(A.3)

at episode $k$, then $\alpha_{k}\sum_{h=1}^{H}\delta_{k}^{h}\leq
O(H^{2}d\ln(dT)/\sqrt{K})$. This implies that for linear MDP,
$\mathbb{E}[\text{Regret}(K)]=O(dH^{\frac{3}{2}}\sqrt{T}\ln(dT))$. For ULMC,
by Theorem B.2, the requirements in (A.3) can be achieved by setting the step
size $\tau_{k,h}=\tilde{\Theta}(\frac{\sqrt{d\ln(dKH)}}{M_{k,h}Hk})$ and after
$N_{k,h}=\tilde{\Theta}(\frac{\kappa^{3/2}Hk}{\sqrt{d\ln(dKH)}})$ iterations.
Summing $N_{k,h}$ over all $k\in[K]$ and $h\in[H]$, we obtain that the
cumulative sample complexity is
$\tilde{\Theta}(\frac{\kappa^{3/2}K^{2}H^{2}}{\sqrt{d\ln(dKH)}})$. ∎

###  A.2 Useful Lemmas

In this section, we give some lemmas that are useful in the proof of our main
results.

######  Lemma A.4 (Regret Decomposition).

The regret at episode $k$ can be decomposed into two terms

$\displaystyle\text{REG}_{k}=\mathbb{E}_{\pi^{k},\mathbb{P}}\Bigg{[}\sum_{h=1}^{H}Q_{h}^{k}(x_{h}^{k},a_{h}^{k}))-[{\mathcal{T}}_{h}^{*}Q^{k}_{h+1}](x_{h}^{k},a_{h}^{k})\Bigg{]}-[V_{1}^{k}(x_{1}^{k})-V_{1}^{*}(x_{1}^{k})]$

###### Proof of Lemma A.4.

Recall that the Bellman optimality operator ${\mathcal{T}}_{h}^{*}$ maps any
state-action function $Q^{k}_{h+1}$ to

$[{\mathcal{T}}_{h}^{*}Q_{h+1}^{k}](x,a)=r_{h}(x,a)+\mathbb{E}_{x^{\prime}\sim\mathbb{P}_{h}(x,a)}[\max_{a^{\prime}\in\mathcal{A}}Q^{k}_{h+1}(x^{\prime},a^{\prime})],$

and hence

$\displaystyle
r_{h}(x_{h}^{k},a_{h}^{k})=[{\mathcal{T}}_{h}^{*}Q_{h+1}^{k}](x_{h}^{k},a_{h}^{k})-\mathbb{E}_{x_{h+1}^{k}\sim\mathbb{P}_{h}(x_{h}^{k},a_{h}^{k})}[\max_{a\in\mathcal{A}}Q^{k}_{h+1}(x_{h+1}^{k},a)].$

By definition,

$\displaystyle V_{1}^{\pi^{k}}(x_{1}^{k})$
$\displaystyle=\mathbb{E}_{\pi^{k}}\Bigg{[}\sum_{h=1}^{H}r_{h}(x_{h}^{k},a_{h}^{k})\bigg{|}x_{1}=x_{1}^{k}\Bigg{]}.$

And then, we have

$\displaystyle V_{1}^{\pi^{k}}(x_{1}^{k})$
$\displaystyle=\mathbb{E}_{\pi^{k}}\Bigg{[}\sum_{h=1}^{H}r_{h}(x_{h}^{k},a_{h}^{k})\bigg{|}x_{1}=x_{1}^{k}\Bigg{]}$
$\displaystyle=\mathbb{E}_{\pi^{k}}\Bigg{[}\sum_{h=1}^{H}\Big{[}[{\mathcal{T}}_{h}^{*}Q_{h+1}^{k}](x_{h}^{k},a_{h}^{k})-\mathbb{E}_{x_{h+1}^{k}\sim\mathbb{P}_{h}(x_{h}^{k},a_{h}^{k})}[\max_{a\in\mathcal{A}}Q^{k}_{h+1}(x_{h+1}^{k},a)]\Big{]}\bigg{|}x_{1}=x_{1}^{k}\Bigg{]}$
$\displaystyle=\mathbb{E}_{\pi^{k},\mathbb{P}}\Bigg{[}\sum_{h=1}^{H}\Big{[}[{\mathcal{T}}_{h}^{*}Q_{h+1}^{k}](x_{h}^{k},a_{h}^{k})-\max_{a\in\mathcal{A}}Q^{k}_{h+1}(x_{h+1}^{k},a)\Big{]}\bigg{|}x_{1}=x_{1}^{k}\Bigg{]}$
$\displaystyle=\mathbb{E}_{\pi^{k},\mathbb{P}}\Bigg{[}\sum_{h=1}^{H}\Big{[}[{\mathcal{T}}_{h}^{*}Q_{h+1}^{k}](x_{h}^{k},a_{h}^{k})-Q^{k}_{h+1}(x_{h+1}^{k},a_{h+1}^{k})\Big{]}\bigg{|}x_{1}=x_{1}^{k}\Bigg{]}$
$\displaystyle=\mathbb{E}_{\pi^{k},\mathbb{P}}\Bigg{[}\sum_{h=1}^{H}\Big{[}[{\mathcal{T}}_{h}^{*}Q_{h+1}^{k}](x_{h}^{k},a_{h}^{k})-Q^{k}_{h}(x_{h}^{k},a_{h}^{k})\Big{]}\bigg{|}x_{1}=x_{1}^{k}\Bigg{]}+\mathbb{E}_{\pi^{k}}\big{[}Q_{1}^{k}(x_{1}^{k},a_{1}^{k})\big{]}$
$\displaystyle=\mathbb{E}_{\pi^{k},\mathbb{P}}\Bigg{[}\sum_{h=1}^{H}\Big{[}[{\mathcal{T}}_{h}^{*}Q_{h+1}^{k}](x_{h}^{k},a_{h}^{k})-Q^{k}_{h}(x_{h}^{k},a_{h}^{k})\Big{]}\Bigg{]}+V_{1}^{k}(x_{1}^{k}).$

∎

We restate Theorem 1 of Dann et al. (2021) below.

######  Theorem A.5 (Theorem 1 of Dann et al. (2021)).

Assume that parameter $\eta\leq\frac{2}{5b^{2}}$ is set sufficiently small and
that Assumption 4.2 holds. Then the expected regret (with Thompson sampling
excuted exactly) after $K$ episodes on any MDP $M$ is bounded as

$\displaystyle\mathbb{E}[\text{Regret}(K)]\leq\frac{\lambda}{\eta}\mathcal{K}_{\text{DC}}+\frac{2K}{\lambda}\kappa(b/T^{2})+\frac{6H}{\lambda}+\frac{b}{K},$

where the expectation is over the samples drawn from the MDP and the
algorithm’s internal randomness.

###  A.3 Analysis of Sampling Error

Recalling the procedure for obtaining the $Q$ function at episode $k$: we
first sample $w_{H}$ to obtain $Q_{H}^{k}$, and then for $h=H-1,\ldots,1$, we
sample $w_{h}$ conditional on $Q_{h+1}^{k}$ to obtain $Q_{h}^{k}$. Let’s
denote the target conditional distribution of $Q_{h}^{k}$ given $Q_{h+1}^{k}$
as $q^{k}_{h,h+1}$. If Thompson sampling is executed precisely at each step,
we should acquire the $Q$ function $Q_{h}^{k}\sim q_{k}^{h}$ such that
$q_{k}^{h}=q^{k}_{h,h+1}(\cdot|Q_{h+1}^{k})$ for all $h\in[H]$. We denote the
joint distribution of $\\{q_{k}^{h}\\}_{h\in[H]}$ as $q_{k}$. However, due to
the high computational complexity, we can only obtain a sequence of
$\\{\widetilde{Q}_{h}^{k}\sim\widetilde{q}_{k}^{h}\\}_{h\in[H]}$ that
satisfies
$\widetilde{q}_{k}^{h}=\widetilde{q}^{k}_{h,h+1}(\cdot|\widetilde{Q}_{h+1}^{k}),$
where $\widetilde{q}^{k}_{h,h+1}$ is a transition kernel close to
$q^{k}_{h,h+1}$ and depends on the approximating sampler. We denote the joint
distribution of $\\{\widetilde{q}_{k}^{h}\\}_{h\in[H]}$ as $q_{k}^{\prime}$.
Note that given $\widetilde{Q}_{h+1}^{k}$ generated by our algorithm, our goal
is to sample from $q^{k}_{h,h+1}(\cdot|\widetilde{Q}_{h+1}^{k})$ while we can
only obtain a sample close to that, denoted as $\widetilde{q}_{k}^{h}$. Our
samplers can only control the distance (error) between
$\widetilde{q}^{k}_{h,h+1}(\cdot|\widetilde{Q}_{h+1}^{k})$ and
$q^{k}_{h,h+1}(\cdot|\widetilde{Q}_{h+1}^{k})$. We denote their total
variation distance by $\delta_{k}^{h}$. However, the sampling error in Theorem
4.6 is in terms of the distance between the joint distributions at episode
$k$: $\delta_{k}=\text{TV}(q_{k},q_{k}^{\prime})$. Therefore, for a concrete
analysis of sampling error, it is imperative to express $\delta_{k}$ in terms
of $\\{\delta_{k}^{h}\\}_{h\in[H]}$. The expression relies on the following
proposition:

######  Proposition A.6.

Suppose that we have four random variables $X_{i}$ and $Y_{i}$, $i=1,2$.
Denote the conditional distribution of $Y_{i}$ given $X_{i}=x$ by
$p_{i}(\cdot|x)$, $i=1,2$. Let $q_{i}$ be the joint distribution of
$(X_{i},Y_{i})$ and $q^{X}_{i}$ be the distribution of $X_{i}$, $i=1,2$. If
$\sup_{x}\mathrm{TV}(p_{1}(\cdot|x),p_{2}(\cdot|x))\leq\epsilon<\infty$, then

$\displaystyle\mathrm{TV}(q_{1},q_{2})\leq\mathrm{TV}(q_{1}^{X},q_{2}^{X})+\epsilon.$

###### Proof of Proposition A.6.

In this proof, we abuse notation by identifying a measure with its density for
convenience. By definition of total variation distance,

$\displaystyle 2\mathrm{TV}(q_{1},q_{2})$
$\displaystyle=\int|p_{1}(y|x)q_{1}^{X}(x)-p_{2}(y|x)q_{2}^{X}(x)|dydx$
$\displaystyle\leq\int|p_{1}(y|x)q_{1}^{X}(x)-p_{2}(y|x)q_{1}^{X}(x)|dydx+\int|p_{2}(y|x)q_{1}^{X}(x)-p_{2}(y|x)q_{2}^{X}(x)|dydx$
$\displaystyle\leq\int\bigg{(}\int|p_{1}(y|x)-p_{2}(y|x)|dy\bigg{)}q_{1}^{X}(x)dx+\int\bigg{(}\int
p_{2}(y|x)dy\bigg{)}|q_{1}^{X}(x)-q_{2}^{X}(x)|dx$
$\displaystyle=2\int\mathrm{TV}(p_{1}(\cdot|x),p_{2}(\cdot|x))q_{1}^{X}(x)dx+\int|q_{1}^{X}(x)-q_{2}^{X}(x)|dx$
$\displaystyle\leq 2\epsilon+2\mathrm{TV}(q_{1}^{X},q_{2}^{X}),$

where for the last equality, we use the fact that for any fixed $x$,
$p_{2}(y|x)$ is a probability density and hence $\int p_{2}(y|x)dy=1$. This
concludes the proof. ∎

With this proposition in hand, we are ready to prove Proposition 4.11 which we
restate here first.

######  Proposition A.7.

Let $\delta_{k}^{h}$ be the sampling error (in the total variation sense)
induced by our sampler at step $h$ episode $k$ and $\delta_{k}$ be defined in
section 3.1, $h\in[H]$ and $k\in[K]$. Then
$\delta_{k}\leq\sum_{h=1}^{H}\delta_{k}^{h}$.

###### Proof of Proposition 4.11..

Let $q_{k}^{h:H}$ be the joint distribution of $\\{q_{k}^{s}\\}_{h\leq s\leq
H}$ and $\tilde{q}_{k}^{h:H}$ be the joint distribution of
$\\{\tilde{q}_{k}^{s}\\}_{h\leq s\leq H}$. Then by Proposition A.6,

$\displaystyle\delta_{k}=\mathrm{TV}(q_{k},q_{k}^{\prime})\leq\delta_{k}^{1}+\mathrm{TV}(q_{k}^{2:H},\tilde{q}_{k}^{2:H}).$

Likewise, for $h=2,\ldots,H-1$,

$\displaystyle\mathrm{TV}(q_{k}^{h:H},\tilde{q}_{k}^{h:H})\leq\delta_{k}^{h}+\mathrm{TV}(q_{k}^{h+1:H},\tilde{q}_{k}^{h+1:H}).$

Since $q_{k}^{H:H}=q_{k}^{H}$ and $\tilde{q}_{k}^{H:H}=\tilde{q}_{k}^{H}$, we
have $\mathrm{TV}(q_{k}^{H:H},\tilde{q}_{k}^{H:H})=\delta_{k}^{H}$. Then we
conclude the proof by combining the above inequalities. ∎

Now let $T$ be the truncation map

$\displaystyle T(x):=\min\\{x,b\\}^{+}$

used in Algorithm 1. Then conditional on $\tilde{Q}_{h+1}^{k}$,
$\tilde{q}_{k}^{h}$ is now given by

$\displaystyle\widetilde{q}_{k}^{h}=T_{\\#}[\widetilde{q}^{k}_{h,h+1}(\cdot|\widetilde{Q}_{h+1}^{k})].$

Since we assume that $Q_{h}^{k}\in\mathcal{Q}$ for all $h$ and $k$, we have
that $q_{k}^{h}=T_{\\#}[q_{k}^{h}]$. And therefore the data-processing
inequality gives

$\displaystyle
TV(\tilde{q}_{k}^{h},q_{k}^{h})=TV(T_{\\#}[\widetilde{q}^{k}_{h,h+1}(\cdot|\widetilde{Q}_{h+1}^{k})],T_{\\#}[q_{k}^{h}])\leq
TV(\widetilde{q}^{k}_{h,h+1}(\cdot|\widetilde{Q}_{h+1}^{k}),q_{k}^{h}),$

which is exactly the sampling error in Proposition A.7. And hence the
conclusion in the proposition still holds for $\delta_{k}$ with the truncation
error.

###  A.4 Proof of Linear MDPs

In this section, we prove some properties for linear MDPs.

######  Proposition A.8.

In linear MDPs, the linear function class $\mathcal{Q}$ satisfies Assumption
4.1 and 4.2 with $b=H$. And the decoupling coefficient is bounded by

$\displaystyle\mathcal{K}_{\text{DC}}\leq 2dH(1+\ln(2KH)).$

###### Proof of Proposition A.8.

Note Assumption 4.1 can be verified directly by the definition of linear MDP.
This boundedness follows from the fact that $r_{h}\in[0,1]$ for all $h\in[H]$
and hence $Q_{h}(x,a)\leq H-h+1\leq H$ for any
$x,a\in{\mathcal{S}}\times\mathcal{A}$. Since $Q_{h}$ is arbitrary here, we
have $b=H$. For the upper bound of the decoupling coefficient, we refer to
(Dann et al., 2021, Proposition 1). ∎

######  Proposition A.9.

In linear MDPs, the linear function class $\mathcal{Q}$ satisfies Assumption
4.3. And given any state $x\in\mathcal{S}$ and $h\in[H]$, we have the
following representation of $Q\in\mathcal{Q}$:

$\displaystyle Q_{h}(x,a)-[{\mathcal{T}}_{h}^{*}Q_{h+1}](x,a)=\langle
u_{h},\phi(x,a)\rangle.$

###### Proof of Proposition A.9.

The linearity of the action-value functions directly follows from the Bellman
equation:

$\displaystyle
Q_{h}(x,a)=r_{h}(x,a)+(\mathbb{P}_{h}V_{h+1})(x,a)=\langle\phi(x,a),\theta_{h}\rangle+\int_{\mathcal{S}}V_{h+1}(x^{\prime})\langle\phi(x,a),d\mu_{h}(x^{\prime})\rangle.$

And likewise

$\displaystyle[{\mathcal{T}}_{h}^{*}Q_{h+1}](x,a)=\langle\phi(x,a),\theta_{h}\rangle+\int_{\mathcal{S}}\max_{a^{\prime}\in\mathcal{A}}Q_{h+1}(x^{\prime},a^{\prime})\langle\phi(x,a),d\mu_{h}(x^{\prime})\rangle.$

Then the completeness follows by defining

$\displaystyle
Q_{h}(x,a)=\langle\phi(x,a),\theta_{h}+\int_{\mathcal{S}}\max_{a^{\prime}\in\mathcal{A}}Q_{h+1}(x^{\prime},a^{\prime})d\mu_{h}(x^{\prime})\rangle.$

And therefore

$\displaystyle
Q_{h}(x,a)-[{\mathcal{T}}_{h}^{*}Q_{h+1}](x,a)=\langle\phi(x,a),u_{h}\rangle,$

where
$u_{h}=\int_{\mathcal{S}}(V_{h+1}(x^{\prime})-\max_{a^{\prime}\in\mathcal{A}}Q_{h+1}(x^{\prime},a^{\prime}))d\mu_{h}(x^{\prime})$.
∎

Next, we restate Lemma 4.15 and provide proof for it.

######  Lemma A.10.

If the stage-wise priors $p_{0}^{h}$ are chosen as
$\mathcal{N}(0,\sqrt{d}HI_{d})$, then
$\kappa(\epsilon)=dHO(\ln(dH/\epsilon))$.

###### Proof of Lemma 4.15.

By our choice of $p_{0}^{h}$,

$\displaystyle
p_{0}^{h}(\mathcal{Q}_{h}(\epsilon,Q_{h+1}))=O(\epsilon^{d}(2\pi\sqrt{d}H)^{d/2}).$

And hence

$\displaystyle\ln\left(\frac{1}{p_{0}^{h}(\mathcal{Q}_{h}(\epsilon,Q_{h+1}))}\right)=O(d\ln(1/\epsilon)+d\ln(dH))=dO(\ln(dH/\epsilon)).$

And finally,

$\displaystyle\kappa(\epsilon)=\sum_{h=1}^{H}\ln\left(\frac{1}{p_{0}^{h}(\mathcal{Q}_{h}(\epsilon,Q_{h+1}))}\right)=dHO(\ln(dH/\epsilon)).$

∎

##  Appendix B More Details on Approximate Samplers

In this section, we provide details of samplers with the target distribution
$\mu\propto e^{-L}$ in $\mathbb{R}^{d}$, where $L$ is twice continuously
differentiable, satisfying the conditions
$mI_{d}\preccurlyeq\nabla^{2}L\preccurlyeq MI_{d}$ for some $M\geq m>0$. We
also define the condition number of $\mu$ by $\kappa=\frac{M}{m}$.

###  B.1 Langevin Monte Carlo (LMC)

The Langevin Monte Carlo (LMC) algorithm samples from a target distribution
$\mu\propto\exp(-L)$, using a discretized version of the continuous-time
Langevin diffusion. Given an initial distribution $p_{0}$, and a step size
$\tau>0$, LMC generates a Markov chain $\\{w_{n}\\}_{n=0}^{N}$, starting from
$w_{0}\sim p_{0}$ where $w_{n}\in\mathbb{R}^{d}$. At each iteration $(n+1)$,
the chain updates its state, $w_{n}$, using:

$\displaystyle w_{n+1}$ $\displaystyle=w_{n}-\tau\nabla
L(w_{n})+\sqrt{2\tau}\xi_{n},$

where $\xi_{n}$’s are samples from the d-dimensional standard Gaussian
independent of $w_{n}$. $N$ is the total number of iteration. The convergence
of LMC to the target distribution is a well-known result, holding true under
specific assumptions (Chewi et al., 2022). For illustration, The following
theorem provides a concrete example with sufficient conditions for
convergence, which establishes the theoretical foundation for our analysis.

######  Theorem B.1 (Vempala & Wibisono (2019)).

Denote the distribution of $w_{n}$ by $p_{n}$. For any
$\epsilon\in[0,\kappa\sqrt{d}]$, if we take $\tau=O(\frac{\epsilon^{2}}{\kappa
Md})$, then we obtain the guarantee $TV(p_{N},\mu)\leq\epsilon$ after

$\displaystyle
N=\tilde{\Theta}\left(\frac{\kappa^{2}d}{\epsilon^{2}}\right)\quad\text{iterations}.$

###  B.2 Underdamped LMC

The underdamped Langevin dynamics (ULD) for $(w_{t},P_{t})\in\mathbb{R}^{2d}$
is driven by the SDE

$\displaystyle\begin{split}dw_{t}&=P_{t}dt,\\\ dP_{t}&=-\nabla
L(w_{t})dt+\gamma P_{t}dt+\sqrt{2\beta^{-1}\gamma}dB_{t},\\\ \end{split}$
(B.1)

which can be viewed as a second-order Langevin dynamics. We can use different
discretization schemes to obtain discrete-time algorithms. For ULMC using the
scheme (3.3), we have the following convergence result:

######  Theorem B.2 (Zhang et al. (2023)).

For ULMC, assume that our target distribution satisfies that
$\mathbb{E}_{\mu}[\|\cdot\|]=m_{1}<+\infty$, $\nabla L(0)=0$ (without loss of
generality) and $L(0)-\min L=\tilde{O}(d)$. Then if we set
$\tau=\tilde{\Theta}(\frac{\epsilon m^{1/2}_{1}}{Md^{1/2}})$ and
$\gamma=\Theta(\sqrt{M})$ with a warm start, the law of the $N$-th iterate of
ULMC $p_{N}$ satisfies

$\displaystyle TV(p_{N},\mu)\leq\epsilon\quad\text{after}\quad
N=\tilde{\Theta}\left(\frac{\kappa^{3/2}d^{1/2}}{\epsilon}\right)\quad\text{iterations}.$

##  Appendix C Experiment Details

In this section, we provide further details on our experiment and
implementation.

###  C.1 $N$-Chain

We use $\phi_{\text{therm}}(s_{t})=(\mathbf{1}\\{x\leq s_{t}\\})$ in
$\\{0,1\\}^{N}$ as input feature following Osband et al. (2016a). We further
follow the same protocol as in Ishfaq et al. (2024) for our experiments. For
all the baseline algorithms, as well as our proposed algorithms FG-LMCDQN, FG-
ULMCDQN and ULMCDQN, we parameterize the Q function using a multi-layer
perceptron (MLP). We use $[32,32]$ sized hidden layers in the MLP and $ReLU$
as the activation functions. All algorithms are trained for $10^{5}$ steps
where the experience replay buffer size is $10^{4}$. The performance of each
algorithm is measured by the mean return of the last $10$ test episodes. We
use mini-batch size of $32$ and set discount factor as
$\gamma_{\text{discount}}=0.99$. The target network is updated every $100$
steps.

For our proposed algorithms, we do a grid search for the hyper-parameters:
learning rate $\tau$, bias factor $a$ in the optimizers, the temperature
$\beta$, the friction coefficient $\gamma$ and the Feel-Good prior weight
$\eta$. We list the detailed values of all swept hyper-parameters in Table 2.
Following Ishfaq et al. (2024), for the adaptive bias term, we set
$\alpha_{1}=0.9$, $\alpha_{2}=0.99$, and $\lambda=10^{-8}$ in (3.5).

Figure 4: N-Chain environment (Osband et al., 2016a). Hyper-parameter | Values
---|---
learning rate $\tau$ | {$0.01$, $0.001$}
bias factor $a$ | {$1.0$, $0.1$, $0.01$}
temperature $\beta$ | {$10^{12}$, $10^{10}$, $10^{8}$}
update number $J_{k}$ | {$4$}
friction coefficient $\gamma$ | {$1$, $0.1$, $0.01$}
feel-good prior weight $\eta$ | {$1$, $0.1$, $0.01$}
Table 2: The swept hyper-parameter in $N$-Chain experiments.

###  C.2 Atari

####  C.2.1 Experiment Setup

For our Atari experiments, our training and evaluation protocol follows that
of Mnih et al. (2015); Ishfaq et al. (2024). We implement FG-LMCDQN, FG-
ULMCDQN and ULMCDQN using the Tianshou framework (Weng et al., 2022).

To maintain a reasonable training time, for all our algorithms FG-LMCDQN, FG-
ULMCDQN and ULMCDQN, we set $J_{k}=1$. Similar to the N-chain experiments,
following Ishfaq et al. (2024), for the adaptive bias term, we set
$\alpha_{1}=0.9$, $\alpha_{2}=0.99$, and $\lambda=10^{-8}$ in (3.5). We list
the detailed values of all swept hyper-parameters in Table 3.

Hyper-parameter | Values
---|---
learning rate $\tau$ | {$0.01$, $0.001$, $0.0001$}
bias factor $a$ | $\\{0.1,0.01\\}$
temperature $\beta$ | $\\{10^{16},10^{14},10^{12}\\}$
update number $J_{k}$ | {$1$}
friction coefficient $\gamma$ | {$10$, $1$}
feel-good prior weight $\eta$ | {$1$, $10^{-2}$, $10^{-3}$, $10^{-4}$, $10^{-5}$}
Table 3: The swept hyper-parameter in Atari games.

####  C.2.2 Raw Scores in Atari

In Table 4, we directly compare the performance of our proposed algorithms FG-
LMCDQN, FG-ULMCDQN and ULMCDQN with other baselines by presenting the maximal
score obtained by each algorithm in each of the 8 Atari games. The results are
averaged over 5 random seeds.

${}_{\text{Methods}}\mkern-6.0mu\setminus\mkern-6.0mu{}^{\text{Games}}$ | Alien | Freeway | Gravitar | H.E.R.O | Pitfall! | Q*bert | Solaris | Venture
---|---|---|---|---|---|---|---|---
Human | 7128 | 30 | 3351 | 30826 | 6464 | 13455 | 12327 | 1188
Random | 228 | 0 | 173 | 1027 | -229 | 164 | 1263 | 0
IQN | 1691 $\pm$ 155 | 34 $\pm$ 0 | 413 $\pm$ 31 | 11229 $\pm$ 1098 | -5 $\pm$ 4 | 14324 $\pm$ 643 | 1082 $\pm$ 258 | 3 $\pm$ 3
BootstrappedDQN | 1067 $\pm$ 133 | 29 $\pm$ 1 | 312 $\pm$ 50 | 13538 $\pm$ 696 | -53 $\pm$ 19 | 11786 $\pm$ 1474 | 923 $\pm$ 383 | 12 $\pm$ 12
C51 | 1878 $\pm$ 1878 | 34 $\pm$ 0 | 254 $\pm$ 52 |  17500 $\pm$ 2170 | -19 $\pm$ 16 | 13394 $\pm$ 1500 | 303 $\pm$ 191 | 31 $\pm$ 31
PrioritizedDQN | 1799 $\pm$ 202 | 23 $\pm$ 10 | 149 $\pm$ 37 | 14462 $\pm$ 1249 | -46 $\pm$ 16 | 9464 $\pm$ 880 |  1377 $\pm$ 423 | 23 $\pm$ 23
NoisyNetDQN | 1545 $\pm$ 217 | 32 $\pm$ 0 | 124 $\pm$ 47 | 6003 $\pm$ 1903 | -31 $\pm$ 21 | 11046 $\pm$ 1594 | 1373 $\pm$ 361 | 24 $\pm$ 21
AdamLMCDQN | 1772 $\pm$ 188 | 33 $\pm$ 0 | 799 $\pm$ 34 | 11366 $\pm$ 348 | -6 $\pm$ 4 | 14628 $\pm$ 498 | 938 $\pm$ 189 |  1326 $\pm$ 92
ULMCDQN | 1999 $\pm$ 687 | 34 $\pm$ 0 | 697 $\pm$ 64 | 15201 $\pm$ 3141 | -3 $\pm$ 2 |  14704 $\pm$ 794 | 1195 $\pm$ 390 | 1132 $\pm$ 195
FG-LMCDQN |  2380 $\pm$ 645 | 23 $\pm$ 10 | 744 $\pm$ 73 | 11576 $\pm$ 202 |  0 $\pm$ 0 | 14674 $\pm$ 436 | 735 $\pm$ 132 | 1069 $\pm$ 60
FG-ULMCDQN | 2030 $\pm$ 446 |  34 $\pm$ 0 |  844 $\pm$ 312 | 14044 $\pm$ 1220 | -9 $\pm$ 9 | 14385 $\pm$ 579 | 1278 $\pm$ 851 | 1198 $\pm$ 198

Table 4: Experiments results on 8 Atari Games. Table 4 presents the scores in
each environment with 50M frames. For each environment, the algorithms perform
5 runs with random seeds. Then we average the scores for each game over 5 runs
as the final result with a 95% confidence interval. We consider 6 baselines:
IQN (Dabney et al., 2018), Bootstrapped DQN (Osband et al., 2016a), C51
(Bellemare et al., 2017), Prioritized DQN (Schaul et al., 2015), NoisyNet DQN
(Fortunato et al., 2018) and AdamLMCDQN (Ishfaq et al., 2024). The scores for
IQN, C51 and Prioritized DQN are taken from DQN Zoo (Quan & Ostrovski, 2020).
The scores for Bootstrapped DQN, NoisyNet DQN and AdamLMCDQN are taken from
https://github.com/hmishfaq/LMC-LSVI which is the official github repository
of Ishfaq et al. (2024). We implemented our algorithms ULMCDQN, FG-LMCDQN and
FG-UMLCDQN with Tianshou framework (Weng et al., 2022) in which we also use
the double Q method (Van Hasselt et al., 2016). Our algorithms have
demonstrated advantages in Alien, Freeway, Gravitor and Pitfall compared with
baselines.