Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo
Authors: Haque Ishfaq
Qingfeng Lan
Pan Xu
A. Rupam Mahmood
Doina Precup
Anima Anandkumar
Kamyar Azizzadenesheli
Venue: ICLR 2024 poster (2024)
Keywords: Exploration
Reinforcement Learning
Thompson Sampling
Langevin Monte Carlo
Deep Reinforcement learning
Primary area: reinforcement learning
TL;DR: We propose a provably and practically efficient reinforcement learning algorithm based on Langevin Monte Carlo.

Abstract: We present a scalable and effective exploration strategy based on Thompson sampling for reinforcement learning (RL). One of the key shortcomings of  existing Thompson sampling algorithms is the need to perform a Gaussian approximation of the posterior distribution, which is not a good surrogate in most practical settings. We instead directly sample the Q function from its posterior distribution, by using  Langevin Monte Carlo, an efficient type of Markov Chain Monte Carlo (MCMC) method. Our method only needs to perform noisy gradient descent updates to learn the exact posterior distribution of the Q function, which makes our approach easy to deploy in deep RL.  We provide a rigorous theoretical analysis for the proposed method and demonstrate that, in the linear Markov decision process (linear MDP) setting, it has a regret bound of $\tilde{O}(d^{3/2}H^{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. We apply this approach to deep RL, by using Adam optimizer to perform gradient updates. Our approach achieves better or similar results compared with state-of-the-art deep RL algorithms on several challenging exploration tasks from the Atari57 suite.

Published as a conference paper at ICLR 2024
PROVABLE AND PRACTICAL: PLORATION IN REINFORCEMENT LEARNING VIA
EFFICIENT EX-
LANGEVIN MONTE CARLO
Haque Ishfaq" Mila, McGill University haque www.agssaaila....mmcmmmmmm wwg.iiiiio ilg.ll... ca
Qingfeng Lan" University of Alberta, Amii glan3@ualberta.com
Pan Xu Duke University
A. Rupam Mahmood University of Alberta CIFAR AI Chair, Amii
Doina Precup Mila, McGill University Google DeepMind
Anima Anandkumar
California Institute of Technology, Nvidia
Kamyar Azizzadenesheli Nvidia
ABSTRACT
We present a scalable and effective exploration strategy based on Thompson sam- pling for reinforcement learning (RL). One of the key shortcomings of existing Thompson sampling algorithms is the need to perform a Gaussian approximation of the posterior distribution, which is not good surrogate in most practical set- tings. We instead directly sample the Q function from its posterior distribution, by using Langevin Monte Carlo, efficient type of Markov Chain Monte Carlo (MCMC) method. Our method only needs to perform noisy gradient descent up- dates learn the exact posterior distribution of the Q function, which makes our approach easy to deploy in deep RL. We provide a rigorous theoretical analysis for the proposed method and demonstrate that, the linear Markov decision process (linear MDP) setting, it has a regret bound of ( H3/2 /T), where d is the dimension of the feature mapping. H is the planning horizon, and T is the total number of steps. We apply this approach to deep RL, by using Adam optimizer perform gradient updates. Our approach achieves better similar results com- pared with state-of-ther -feth--rr-- deep RL algorithms on several challenging exploration tasks from the Atari57 suite!
INTRODUCTION
Balancing exploration with exploitation a fundamental problem in reinforcement learning (RL)
(Sutton and Barto 2018). Numerous exploration algorithms have been proposed (Jaksch et al. 2010 Oshand and Van Roy 2017 OStrovski et al., 2017 Azizzadenesheli et al. 2018 Jin et al, However, there is big discrepancy between provably efficient algorithms, which typ-
2018
ically limited to tabular or linear MDPs with a focus on achieving tighter regret bound, and more heuristic-based algorithms for exploration deep RL, which scale well but have no guarantees.
A generic and widely used solution to the exploration-exploitation dilemma is the use of optimism in the face of uncertainty (OFU) (Auer al. (002). Most works of this type inject optimism through bonuses added to the rewards or estimated Q functions (Jaksch et al. 22100) Azar et al.) 2017]: Jin al. 2018 2020). These bonuses, which are typically decreasing functions of counts on the number of visits of state-action pairs, allow the agent to build upper confidence bounds (UCBs) on the optimal Q functions and act greedily with respect to them. While UCB-based methods provide strong theoretical guarantees in tabular and linear settings, they often perform poorly in practice
"Equal contribution
Our code is available httph:t//gtthub...//.

---

Published as a conference paper at ICLR 2024
(Osband al. 2013 Osband and Van Roy 2017). Generalizations to non-tabular and non non-linee -ineer settings have also been explored (Bellemare et al., 2016 Tang et al. 2017 Ostrovski et al. 2017: Burda et al. 2018
Inspired by the well-known Thompson sampling Thompson 1933 for multi-armed bandits, another line of work proposes posterior sampling for RL (PSRL) (Osband et al. 2013 Agrawal and Jia 2017]. which maintains a posterior distribution over the MDP model parameters of the problem hand. At the beginning of each episode, PSRL samples new parameters from this posterior, solves the sampled MDP, and follows its optimal policy until the end of the episode. However, generating exact posterior samples is only tractable in simple environments, such as tabular MDPs where Dirichlet priors can be used over transition probability distribution. Another closely related algorithm is randomized least-square value iteration (RLSVI), which induces exploration through noisy value iteration (Osband et al. 2016a Russo 2019 Ishfag et al. (022). Concretely, Gaussian noise added to the reward before applying the Bellman update. This results in a Q function estimate that is equal to an empirical Bellman update with added Gaussian noise, which can be seen as approximating the posterior distribution of the Q function using a Gaussian distribution. However, in practical problems, Gaussian distributions may not be good approximation of the true posterior of the Q function. Moreover, choosing an appropriate variance is an onerous task; and unless the features fixed, the incremental computation of the posterior distribution is not possible.
Algorithms based on I Langevin dynamics are widely used for training neural networks in Bayesian settings (Welling and Teh 2011). For instance, by adding a small amount of exogenous noise, Langevin Monte Carlo (LMC) provides regularization and allows quantifying the degree of un- certainty on the parameters of the function approximator. Furthermore, the celebrated stochastic gradient descent, resembles a Langevin process (Cheng et al. (020). Despite its huge influence in Bayesian deep learning. the application of LMC in sequential decision making problems relatively unexplored. [Mazumdar et al. (020) proposed an LMC- approximate Thompson sampling al- gorithm that achieves optimal instance-dependent regret for the multi-armed bandit (MAB) problem. Recently, Xu et al. (2022) used LMC to approximately sample model parameters from the poste- rior distribution in contextual bandits and showed that their approach can achieve the same regret bound as the best Thompson sampling algorithms for linear contextual bandits. Motivated by the success of the LMC approach in bandit problems, in this paper, we study the use of LMC to approx- imate the posterior distribution of the Q function, and thus provide an exploration approach which is principled, maintains the simplicity and scalability of LMC, and can be easily applied in deep RL. algorithms.
Main contributions. We propose a practical and efficient online RL. algorithm, Langevin Monte Carlo Least-Squares Value Iteration (LMC-LSVT), which simply performs noisy gradient descent updates to induce exploration. LMC-LSVI is easily implementable and can be used in high- dimensional RL tasks, such as image-based control. Along with providing empirical evaluation in the RiverSwim environment and simulated linear MDPs, we prove that LMC-LSVI achieves a (d3/22 VT) regret in the linear MDP setting, where d is the dimension of the feature mapping, H is the planning horizon, and T is the total number of steps. This bound provides the best possible dependency on and H for any known randomized algorithms and achieves sublinear regret in T..
Because preconditioned Langevin algorithms (Li al. 2016) can avoid pathological curvature prob- lems and saddle points in the optimization landscape, also propose Adam Langevin Monte Carlo Deep Q-Network (Adam LMCDQN), ), a preconditioned variant of LMC-LSVIbasse based on the Adam optimizer KKingma and Ba 2014). In experiments on both N-chain (Osband et al. 2016b) and chal- lenging Atari environments (Bellemare et al.) 2013) that require deep exploration, Adam LMCDQN performs similarly or better than state-of-the-aae exploration approaches in deep RL.
Unlike many other provably efficient algorithms with function approximations (Yang and Wang 2020 Cai et al. 2020 Zanette et al. 2020a|| Xu and Gu 2020 Wu et al. 2020 Ayoub et al. 2020 Zanette et al., 20202) Zhou et al.) 2021, He et al. 2023). LMC- can easily be extended to deep
RL settings (Adam LMCDQN). We emphasize that such unification of theory and practice is rare
(Feng et al. 2021 Kitamura et al. 2023 Liu et al. 2023) in the current literature of both theoretical
RI. and deep RI..
2

---

Published as a conference paper at ICLR 2024
2 PRELIMINARY
Notation. For any positive integer n, we denote the set (1, by [n]. For any set A, ( 4 denotes the inner product over set A. @ and 2 represent element-wise vector product and division respectively. For function growth, we use O(-), ignoring poly polyloggartthmic factors.
We consider an episodic discrete-time Markov decision process (MDP) of the form (S, H.P. where S is the state space, A is the action space, is the episode length, transition probability distributions, and
[ h=1 are the state {ra f/ are the reward functions. Moreover, for each h [H], (- Ir a) denotes the transition kernel at step h E [H] which defines a non-stationary environment. Th : S x + [0, 1] is the deterministic reward function at step h A policy æ is a collection of H functions { S - Ahhejm where TA (z) is the action that the agent takes in state x at the h-th step in the episode. Moreover, for each h E [H], we define the value function V S as the expected value of cumulative rewards received under policy when starting at the h-th time step. In particular, we have
from an arbitrary state
V (z) = E, E The (IW', ax)) = x]
Similarly, define the action-value function (or the Q function) QT, S x A R as the expected value of cumulative rewards given the current state and action where the agent follows policy æ afterwards. Concretely,
(x) = Er 1= The (2 aw)
an = a].
We denote (x) V (x) and Qh (2 a) Qh (z),a) where ot is the optimal policy. To simplify notation, we denote [PA, ( a) = (2)x.)()11..) (xx).. Thus, we write the Bellman equation associated with a policy π as
Q7 a) = (rr + PA PP (r,a), Similarly, the Bellman optimality equation is (2 a) (rh- F (1t)))))
(x) = Q% (n())),
v=+ = 0.
(1)
(x =
(=) =0
The agent interacts with the environment for K episodes with the aim of learning the optimal policy. At the beginning of each episode k. an adversary picks the initial state x4. and the agent chooses policy n². We measure the suboptimality of an agent by the total regret defined as
Regret( K) = > [Vi(<+)) - Vi (af)).
Langevin Monte Carlo (LMC). LMC is an iterative algorithm (Rossky et al., 1978 Roberts and Stramer 2002. Neal et al. 2011). which adds isotropic Gaussian noise to the gradient descent update at each step:
Wk+1 Wi TM (((w)) V 2mp
where L(w) is the objective function, 7h is the step-size parameter, B is the inverse temperature parameter, and cg is an isotropic Gaussian random vector in Rdd. Under certain assumptions, the LMC update will generate Markov chain whose distribution converges to a target distribution o exp(-BL(w)) (w)) (Roberts and Tweedie 1996. (Bakry al. 20144). In practice, one can also replace the true gradient V ((wx) with some stochastic gradient estimators, resulting in the famous stochastic gradient Langevin dynamics (SGLD) (Welling and Teh 201T) algorithm.
LANGEVIN MONTE CARLO FOR REINFORCEMENT LEARNING
In this section, we propose Langevin Monte Carlo SquareS Value Iteration (LMC-LSVI), as shown in Algorithm [ Assume we have collected data trajectories in the first k 1 episodes as {( aj, r(xī, af)......" In an T afr }>}== | To estimate the Q function for stage h at the k-th episode of the learning process, we define the following loss function:
(ww) = > (rx (1%% a + max Qh (1) - Q(w 60I of)) + A||wa|1?, (4)
We study the deterministic reward functions for notational simplicity. Our results can be easily generalized the case when rewards are stochastic.
3

---

Published as a conference paper at ICLR 2024
where -). is a feature vector of the corresponding state-action pair and Q(wn: (x a.)) denotes any possible approximation of the Q function that is parameterized by wh and takes 2(2% (7) as input. At stage ht we perform noisy gradient descent on (.) for Jk times as shown in Algorithm | where Jj is also referred to the update number for episode k. Note that the LMC-LSVI algorithm displayed here is a generic one, which works for all types of function approximation of the Q func- tion. Similar to the specification of Langevin Monte Carlo Thompson Sampling (LMCTS) to linear bandits, generalized linear bandits, and neural contextual bandits (Xu et al.) 2022). we can also de- rive different variants of LMC-LSVI for different types of function approximations by replacing the functions Q wwn: (22 ( and the loss function L (wn))
In this paper. we will derive the theoretical analysis of LMC-LSVI under linear function approx- imations. In particular, when the function approximation of the Q function is linear, the model approximation of the function, denoted by 0% in Line 11 of Algorithm becomes
Q) + min(d(;,-) Tu,
J2 H - h - 1s+.
(5)
Denoting V m ()) we have (wk) = 2(A b/), where
A-1
Ah Σ (1t (Nooh Al and by
Σ
(1n ab) + Vh (xt1(x)+1)) (1)
(6)
By setting V = O, we get the minimizer of L as T = (A
We can prove that the iterate wh "he in Equation 5 follows the following Gaussian distribution.
Proposition 3.1. The parameter w/ Js used in episode of Algorithm follows a Gaussian distri- bution N JJ I.kJJs ), with mean and covariance matrix:
2hh
Jr Ph
A .... ......!!u
1.0 + w/
Σ A
Le (I m
Inh.jk Σ
Bi A/
Jen 1 (I- A7 (Ai) (I A.) -
A A
where A, = I - An for E [k]].
Proposition 3.1 shows that in linear setting the parameter wh k. follows a tractable distribution. This allows us to provide a high probability bound for the parameter wx in Lemma B.3 which is then used in Lemma B.7 to show that the estimated Q function is optimistic with high probability.
We note that the parameter update in Algorithm i presented an isotropic noise for the purpose of theoretical analysis in Section However, in practice, one can use stochastic gradient (Welling and Teh 2011: Zou et al. 2021 or variance-reduced stochastic
full gradient descent step plus
gradient (Dubey et al., 2016)) Xu al. 2018 Zou et al. 2018 to improve the sample efficiency of LMC-LSVI.
2019 of the loss function I (.0
4 THEORETICAL ANALYSIS
We now provide a regret analysis of LMC-LLVI under the linear MDP setting (Jin et al. 2020 and Wang 2020 2019). First, we formally define a linear MDP.
Yang
Definition 4.1 (Linear MDP). A linear MDP is an MDP (8, H,P,,) P) with feature S x A
Rd, if for any h E [H] there exist d unknown (signed) measures μan (Mh ,1 ...., 2h over S and an unknown vector 0n E R&d, such that for any (x. E S x A, we have
(d)
P xr, a) (6(x, a). un (a)))) and ru (a., a) = (,(x, a), 0n).
Without loss of generality, we assume [ a)llz < 1 for all (x E S x A, and max(Ilun [[]]]]]] S V for all h [M].
4

---

end for Published as a conference paper at ICLR 2024
Algorithm Langevin Monte Carlo Least-Squares Value Iteration (LMC-LSVI)
1: Input: step sizes {m 0pk21, inverse temperature {8x loss function Ls(w)
2: Initialize w 0 for [H], Jo
3: for episode k = ..... K do
4: Receive the initial state sf
5: for step h - H. H
do
6: u' k.0
k-1,Je-1
wh
7:
for j 1,..., Ju do
8:
JJ ~ IN
9:
wh wh
AJ RJ-1
M/ (. -
2
K.j. ch
10:
end for
11:
(..)) min ( o(.,)))) H - +
12:
(-) max (:()a
13:
end for
for step h 1,2, ................................ H. do
15:
a Take action ag + argmax (s a), observe reward ( lk ax) and next state sh
end for
17:
We refer the readers to Wang al. 20200) Lattimore et al. (020), and Van Roy and Dong (2019) for related discussions on such linear representation. Next, we introduce our main theorem.
Theorem 4.2. X in Equation (4) A Ö(HV)) in Algorithm I and 6 (2 1). For any & E [K] let the learning rate Ths 1/(44maa (N.)), the update number Js. 2ns (g(HHKK)) where Kt-- (mnas(Af)) (amm)//mm(())) Amina (N)) is the condition number of Nr Under Definition 4.1 the regret of Algorithm satisfies
Regret(K) ((1311233333)
with probability al least 1
compare the regret bound of our algorithm with the state-of-the-art results the literature of theoretical reinforcement learning in Table Compared to the lower bound Q(dH proved in Zhou et al. 2021), our regret bound is worse off by factor of VdH under the linear MDP setting. However, the gap of Vd in worst-case regret between UCB and T-S- bS-ed methods is long standing in simpler setting of linear bandit (Hamidi and Bayati 2020). When converted to linear bandits by setting H = 1, our regret bound matches that of LMCTS (Xu et al., 2022) and the best-known regret upper bound for LinTS from Agrawal and Goyal (201 and Abeille and
open problem,
Lazaric (2117).
require that the failure probability 8 2/ However, in frequentist regret analysis is desirable that the regret bound holds for arbitrarily small failure probability. This arises from Lemma B.7 where we get an optimistic estimation with a constant probability. However, this result can improved by using optimistic reward sampling scheme pro- posed in Ishfaq et al. 2021 Concretely, we can generate M estimates for Q function (Qf:") Ime[M] make optimistic estimate of Q function by setting (-.)) = min minnmaxmmeti 1Q (...)) H - h 1-+1] 1}. We provide the regret analysis for this approach, whose proof essentially follows the same steps in that of Theorem 4.2 in Appendix [ However, for the simplicity of the algorithm design, we use the currently proposed algorithm.
Remark 4.3. In Theorem 4.2
through maintaining M samples of w: {ux J..
Ime[M]. Then,
DEEP Q-NETWORK WITH LMC EXPLORATION
In this section, investigate the where deep Q-networks (DQNs) (Mih et al. 2015
used, which is used as the backbone many deep RL algorithms and prevalent in woaldworld RL applications due its scalability and implementation ease.
5

---

Published as a conference paper at ICLR 2024
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.
Computational Tractability
Algorithm
Regret
Exploration
LSVI-UCB Jin et al. 2020)
UCB
Yes
OPT-RLSVI (7anette et al
2020a)
H(P OldIt (V)
TS
Yes
ELEANOR (Zanette et al.
2020b)
Optimism
No
LSVI-PHI [Ishfaq et al. 2021
0(1122-01223
TS
Yes
LMC-LSVT (this paper)
0 25/2//////
LMC
Yes
While LMC and SGL.D have been shown to converge to the true posterior under idealized settings
(Chen al. 2015: Teh al., 2016 Dalalyan 2017); in practice, most deep neural networks often exhibit pathological curvature and saddle points (Dauphin et al.]
al.] (014)), which render the first-order gradient-based algorithms inefficient, such as SGLD. To mitigate this issue, Li et al. (2016) proposed
et al. (2022) proposed Adam based adaptive SGLD algorithm, where an adaptively adjusted bias term included in the drift function to enhance escape from saddle points and accelerate the convergence in the presence of pathological curvatures.
RMSprop (Tieleman et al. 2012) based preconditioned SGLD. Similarly,KKin
Similarly, in sequential decision problems, there have been studies that show that deep RI algo- rithms suffer from training instability due the usage of deep neural networks (Sinha et al. [020]
Ota et al. 2021] Sullivan et al.) 2022). Henderson et al. (2018) empirically analyzed the effects of different adaptive gradient descent optimizers on the performance of deep RL algorithms and suggest that while being sensitive to the learning rate, RMSProp provides the best performance overall. Moreover, even though the original DQN algorithm (Mnih et al. 2015) used RMSProp optimizer with Huber loss, Ceron and Castro (2021) showed that Adam optimizer with mean-squared error (MSE) loss provides overwhelmingly superior performance.
Adam (Kingma and Ba 2014)
Motivated by these developments both in the sampling community and the deep RL community, now endow DQN-style algorithms (Mnih et al.) 2015) with Langevin Monte Carlo. In particular, we propose Adam Langevin Monte Carlo Deep Q-Network (Adam LMCDQN) in Algorithm 2 where we replace LMC in Algorithm learning the posterior distribution.
[ with the Adam SGLD (aSGLD) (Kim et al. 2022) algorithm in
In Algorithm V (w) denotes an estimate of (L)(w) based on one mini-batch of data sam- pled from the replay buffer. ai and 02 are smoothing factors for the first and second moments of stochastic gradients, respectively. a is the bias factor and λ₁ is a small constant added to avoid zero-divisors. Here, u/ can be viewed as an approximator of the true accond-moment matrix
B(VT) (10) ( ( (ma I) and the bias term m - Ø // 1 + > can be viewed the rescaled momentum which is isotropic near stationary points. Similar Adam, the bias term, with an appropriate choice of the bias factor is expected to guide the sampler to converge to global
optimal region quickly.
EXPERIMENTS
In this section, we present an empirical evaluation of Adam LMCDQN, For the empirical evaluation of LMC-LSVT in the RiverSwim environment (Strehl and Littman 2008 Oshand et al., 2013) and simulated linear MDPs, we refer the reader to Appendix F.1 First, we consider hard exploration problem and demonstrate the ability of deep exploration for our algorithm. We then proceed to experiments with 8 hard Atari games, showing that Adam LMCDQN is able to outperform several strong baselines. Note that for implementation simplicity, in the following experiments, we set all the update numbers Jj. and the inverse temperature values 33 be the same number for all & E [K]. We also emphasize that even though in Theorem (.2 we specify a theoretical value for Jg. as we show in this section, in practice, a small value for Jr (we use Jr = 4 for N-Chain and Jr 1 for

---

Published as a conference paper at ICLR 2024
Algorithm 2 Adam LMCDQN
1: Input: step sizes {m 0b.21, inverse temperature (3e smoothing factors dr and az bias factor a, loss function (w).
2: Initialize 1.f from appropriate distribution for h E [M]] Jo = 0, m. = 0 and un = 0 for
h E [4] and
[K].
3: for episode k = 1,2..... K do
4: Receive the initial state st.
5: for step h = H. H
1,... do K.0
wh A.0 k-1,J m
k- 1-1,J--1
k.0 k-1,Jk-1
6:
w/
n
1/2
7:
for j = 1,..., Ju do
8:
c Jo ~N(0,I)
9:
"h Kj kJ-1 1-1_ ?) V ( (1)
w/n
k-5-1) + am
kit-1
V un
kW-1
+ +x11) +
+v 2m
B ch
10:
m kjj = amm,
k.j-1 1 + (1 a1) V (1 k-jj1
KJ a2uh f.2
RJ- + a2) V w
12:
end for
(..) < Quw b ((.,-))
14:
()) + max Q (:
15:
end for
16:
for step h = 1,2...... H do
17:
Take action a + argmax Qh (s a). observe reward r (st a²)
and next state s sh+1
18:
end for
19:
end for
Atari) can yield good performance for our algorithm. We also emphasize that in our implementation of Adam LMCDQN we use fixed values of an 0.9, 02 = 0.99, and λ = 10-8 instead of tuning them.
Remark 1.1. We note that in our experiments in this section, as baselines, we use commonly used algorithms from deep RL literature as opposed methods presented in Table [ This is because while these methods are provably efficient under linear MDP settings, in most cases, it is not clear how to scale them deep RL settings. More precisely, these methods assume that good feature is known in advance and Q values can be approximated as linear function over this feature. If the provided feature is not good and fixed, the empirical performance of these methods is often poor. For example, LSVI-UCB (Jin et al. 2020) computes UCB bonus function of the form [[ a) A- where A Rdxd the empirical feature covariance matrix. When we update the feature over iterations in deep RL, the computational complexity of LSVI-UCB becomes unbearable as it needs to repeatedly compute the feature covariance matrix to update the bonus function. In the same vein, while estimating the function, OPT-RSLVI (Zanette al.) (020a) needs rely the feature norm with respect to the inverse covariance matrix. Lastly, even though LSVI-PHE (Ishfaq et al. 2021 is computationally implementable in deep RL. settings, requires sampling independent and identically distributed (i.i.d.) noise for the whole history every time to perturb the reward, which appears be computationally burdensome in most practical settings.
6.1 DEMONSTRATION OF DEEP EXPLORATION
We first conduct experiments in N-Chain (Osband et al.) 2016b) to show that Adam LMCDQN is able to perform deep exploration. The environment consists of a chain of N states, namely 8N. The agent always starts state 82, from where can either move left or right. 1 in state sN. The
81, 82, "2,....,8.. The agent receives small reward 0.001 in state $ and larger reward horizon length is N + 9, so the optimal return is 10. Please refer to Appendix F2 for a depiction of the environment.
In our experiments, we consider N to be 25, 50, 75, or 100. For each chain length, we train different algorithms for 10y steps across 20 seeds. We use DQN (Mnih et al. (2015), Bootstrapped DQN (Osband et al., 2016b) and Noisy-Net (Fortunato et al.) (017)) as the baseline algorithms. We use DQN with e-greedy exploration strategy, where decays linearly from 1.0 to 0.01 for the first 000
7

---

Published as a conference paper at ICLR 2024
training steps and then is fixed as 0.01. For evaluation, set 0 in DQN. We measure the performance of each algorithm in each run by the mean return of the last 10 evaluation episodes. For all algorithms, we sweep the learning rate and pick the one with the best performance. For Adam LMCDQN, we sweep a and 8g in small ranges. For more details, please check Appendix F2
In Figure ! we show the performance of Adam LMCDQN and the baseline methods under dif- ferent chain lengths. The solid lines repre- sent the averaged return over 20 random seeds and the shaded areas represent standard er- rors. Note that for Adam LMCDON, we set Jk = 4 for all chain lengths. As N in- creases, the hardness of exploration increases, and Adam LMCDQN able to maintain high performance while the performance of other baselines especially Bootstrapped DQN and Noisy-Net drop quickly. Clearly, Adam LM- CDQN achieves significantly more robust per- formance than other baselines as N increases, showing its deep exploration ability.
12
10
Adam LMCDQN
Noisy-Net
Bootstrapped DQN
8-
Retum
2-
25
50
75
100
N
Figure 1: A comparison of Adam LMCDQN and other baselines in N-chain with different chain lengths N. All results are averaged over 20 runs and the shaded areas represent standard errors. As N increases, the exploration hardness increases.
6.2 EVALUATION ATARI GAMES
To further evaluate algorithm, we conduct experiments in Atari games (Bellemare et al. (2013). Specifically, 8 visually complicated hard ex- ploration games (Taiga et al. 2019) are selected, including Alien, Freeway, Gravitar, H.E.R.O,, Pit- fall, Qbert, Solaris, and Venture. Among these games, Alien, H.E.R.O., and Qbert are dense reward environments, while Freeway, Gravitar, Pitfall, Solaris, and Venture are sparse reward environments, according to Taiga et al. (2019).
Main Results. We consider baselines: Double DQN (Van Hasselt et al.) 2016). Prioritized DQN (Schaul et al., 2015), C51 (Bellemare et al., 2017). QR-DQN (Dabney et al. (0188), IQN (Dabney al. 2018b). Bootstrapped DQN (Osband et al. 20T6b) and Noisy-Net (Fortunato et al. 2017). Since a large Js greatly increases training time, we set J/ 1 in Adam LMCDQN so that all exper- iments can be finished in a reasonable time. We also incorporate the double Q trick (Van Hasseli, 2010 Van Hasselt et al.) 2016), which is shown to slightly boost performance. We train Adam LMCDQN for 50M frames (i.e., 12.5M steps) and summarize results across over 5 random seeds. Please check Appendix F.3. for more details about the training and hyper-parameters settings.
In Figure 2 we present the learning curves of all methods in 8 Atari games. The solid lines corre- spond the median performance over 5 random seeds, while the shaded areas represent 90% con- fidence intervals. Overall, the results show that our algorithm Adam LMCDQN is quite competitive compared the baseline algorithms. In particular, Adam LMCDQN exhibits strong advantage against all other methods in Gravitar and Venture.
Sensitivity Analysis. In Figure 3al we draw the learning curves of Adam LMCDQN with different bias factors a in Qbert. The performance of our algorithm is greatly affected by the value of the bias factor. Overall, by setting a 0.1, Adam LMCDQN achieves good performance in Qbert as well as in other Atari games. On the contrary, Adam LMCDQN is less sensitive to the inverse temperature AR. as shown in Figure 3b
Ablation Study. In Appendix F33.2 we also present results for Adam LMCDQN without applying double Q functions. The performance of Adam LMCDQN is only slightly worse without using dou- ble Q functions, proving the effectiveness of our approach. Moreover, we implement Langevin DQN (Dwaracherla and Van Roy/ 2020) with double Q functions and compare it with our algorithm Adam LMCDQN. Empirically, we observed that Adam LMCDQN usually outperforms Langevin DQN in sparse-reward hard- bard-exploratiio games, while in dense-reward hard-exploration games, Adam LM- CDQN and Langevin DQN achieve similar performance.
8

---

Published as a conference paper at ICLR 2024
Allen
Fi Frewsidy
Crankiet
H.E.R.O.
1000
500
10000
802
250
5000
Piful!
Solari
500
20000
3000
1000
15000
2000
1000
10000
500
-1000
-000
(milloom)) Proniooed DGN
Acaen LSCDDNN
No sylvet DGN
Doubre DON
C31
015-DON
Borairapped DGN
ICN
The return curves of various algorithms in eight Atari tasks over 50 million training frames. Solid lines correspond to the median performance over random seeds, and the shaded areas correspond to 90% confidence interval.
Figure 2:
16000
35000
a-10
B. = 10
Bx. 10
14000
30000
A, 1018
8. 1040
12000
a=0.1
10
8. 10"
a=0.01
25000
A. 1014
a=0.001
Return
Return
15000
6000
4000
2000
5000
Frame (millions)
Frame (millions)
(a) Different bias factor in Adam LMCDQN
(b) Different temperatures 8g in Adam LMCDQN
Figure 3: (a) comparison of Adam LMCDQN with different bias factor a in Qbert. Solid lines correspond to the average performance over random seeds, and shaded areas correspond to stan- dard errors. The performance of Adam LMCDQN is greatly affected by the value the bias factor. (b) A comparison Adam LMCDQN with different values of inverse temperature parameter B4 in Qbert. Adam LMCDQN is not very sensitive to inverse temperature Sg.
7 CONCLUSION AND FUTURE WORK
We proposed the LMC-LSVI algorithm for reinforcement learning that uses Langevin Monte Carlo to directly sample a Q function from the posterior distribution with arbitrary precision. LMC-LSVI achieves the best-available regret bound for randomized algorithms the linear MDP setting. Fur- thermore, proposed Adam LMCDQN, practical variant of LMC-LSVI, that demonstrates com- petitive empirical performance challenging exploration tasks. There are several avenues for future research. It would be interesting to explore if one improve the suboptimal dependence // for randomized algorithms. Extending the current results to more practical and general settings (Zhang et al., 2022; Ouhamma al. 2023) Weisz al., 2023) is also exciting future direction. On the empirical side, it would interesting to see whether LMC based approaches can be used in continuous control tasks for efficient exploration.
ACKNOWLEDGMENTS
We gratefully acknowledge funding from the Canada CIFAR AI Chairs program, the Reinforcement Learning and Artificial Intelligence (RLAI) laboratory. the Alberta Machine Intelligence Institute (Amii), Mila Quebec Artificial Intelligence Institute, the Natural Sciences and Engineering Re-

---

Published as a conference paper at ICLR 2024
search Council (NSERC) of Canada, the US National Science Foundation (MMS-232312) and the Whitehead Scholars Program at the Duke University School of Medicine. The authors would like to thank Vikranth Dwaracherla, Sehwan Kim, and Fabian Pedregosa for their helpful discussions. The authors would also like to thank Ziniu Li for giving great advice about Atari experiments.
REFERENCES
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018. [
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(Apr):1533-1600, 2010. (p. (p.
Ian Osband and Benjamin Van Roy. Why posterior sampling better than optimism for reinforce- ment learning? In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 2701-2716 JMLR. org, 2017. (pp. and
Georg Ostrovski, Mare G Bellemare, Aäron Oord, and Rémi Munos. Count-based exploration with neural density models. In International conference on machine learning, pages 2721-2730.
PMLR, 2017. (pp. and 2
Kamyar Azizzadenesheli, Emma Brunskill, and Animashree Anandkumar. Efficient exploration through bayesian deep g-nttworks. In 2018 Information Theory and Applications Workshop (ITA), pages 1-9. IEEE, 2018. (p.
Chi Jin, Zeyuan Allen-Zhor Sebastien Bubeck, and Michael Jordan. Is q-learning provably effi- cient? In Advances in Neural Information Processing Systems, 2018. [p-
Peter Auer, Nicolo Cesa- Biaa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235-266 2002. (p. 1]
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 263-272. JMLR. org, 2017. (p. I
Chi Jin, Zhuoran Yang, Zhaoran Wang. and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. Conference on Learning Theory, pages 2137- 2143. PMLR, 2020. (pp.
39 40
42
and 43
Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. In Advances in Neural Information Processing Systems, pages 3003-3011, 2013. (pp. 2
6
18
and 43
Mare Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying caunt-based exploration and intrinsic motivation. Advances in neural information pro- cessing systems, 29, 2016. (p. 2
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAl Xi Chen, Yan Duan, John Schul- man, Filip DeTurek, and Pieter Abbeel. exploration: study of count-based exploration for deep reinforcement learning. Advances in neural information processing systems, 30, 2017. (p-
2
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. International Conference on Learning Representations, 2018. (p.2)
William R Thompson. On the likelihood that one unknown probability exceeds another in view of
the evidence of two samples. Biometrika, 25(3/4):285299 2244 1933. (p.2)
Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst- case regret bounds. In Advances in Neural Information Processing Systems, pages 1184-1194, 2017. (p.
10

---

Published as a conference paper at ICLR 2024
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, 2016a. (pp. and 18
Daniel Russo. Worst-case regret bounds for exploration via randomized value functions. In Ad- vances in Neural Information Processing Systems, pages 14410-1444 14420, 2019. (pp. Lnd [8]
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, pages 4607 PMLR,
2021. (pp. 2 5
40
42
and 43)
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), pages 681-
688, 2011. (pp. 2
and 18)
Xiang Cheng, Dong Yin, Peter Bartlett, and Michael Jordan. Stochastic gradient and langevin processes. In International Conference on Machine Learning, pages 1810-1819. PMLR, 2020.
(p. 2
Eric Mazumdar, Aldo Pacchiano, Yian Ma, Michael Jordan, and Peter Bartlett. On approximate thompson sampling with langevin algorithms. In International Conference on Machine Learning, pages 6797-6807. PMLR, 2020. (p.2)
Pan Xu, Hongkai Zheng, Eric V Mazumdar, Kamyar Azizzadenesheli, and Animashree Anand- kumar. Langevin monte carlo for contextual bandits. In International Conference on Machine Learning, pages 24830-24850, PMLR, 2022. (pp. 2 5nd
Chunyuan Li, Changyou Chen, David Carlson, and Lawrence Carin. Preconditioned stochastic gradient langevin dynamics for deep neural networks. In Thirtieth AAAI Conference on Artificial Intelligence, 2016. (pp. and
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 2014. (pp. 2 and 18)
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via
bootstrapped dqn. Advances neural information processing systems, 29, 2016b. (pp.
18 43
and 44
Mare G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environ- ment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47: 253-279, 2013. (pp. and 8)
Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference Machine Learning, pages 10746-1077 10756. PMLR, 2020. (pp.
and
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy opti- mization. In International Conference on Machine Learning, pages 1283-1294. PMLR, 2020.
(pp. 20 and 43)
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Confer- ence Artificial Intelligence and Statistics, pages 1954-1964, PMLR, 2020a. (pp. and
18
Pan Xu and Quanquan Gu. A finite-time analysis of g-learning with neural network function approx- imation. In International Conference on Machine Learning, pages 10565. PMLR, 2020.
(p.2)
Yue Frank Wu. Weitong Zhang, Pan Xu, and Quanquan Gu. A finite-time analysis of two time-scale actor-critic methods. Advances in Neural Information Processing Systems, 33:17617-17622
2020. (p.
11

---

Published as a conference paper at ICLR 2024
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pages 463-474. PMLR, 2020. (p. 2
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near op- timal policies with low inherent bellman error. In International Conference Muchine Learning, pages 10978-10989. PMLR, 2020b. (pp. 2 Bandd
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learn- ing for linear mixture markov decision processes. In Conference on Learning Theory, pages 4532 4576. PMLR, 2021. (pp.
2 and
Jiafan He, Heyang Zhao, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal reinforcement learning for linear markov decision processes. In International Conference on Machine Learning, pages 12790-12822 PMLR, 2023. (p.2)
Fei Feng, Wotao Yin, Alekh Agarwal, and Lin Yang. Provably correct optimization and exploration with non-linear policies. In International Conference on Machine Learning, pages 3263-3273.
PMLR, 2021. (p.2)
Toshinori Kitamura, Tadashi Kozuno, Yunhao Tang, Nino Vieillard, Michal Valko, Wenhao Yang, Jincheng Mei, Pierre Ménard, Mohammad Gheshlaghi Azar, Rémi Munos, al. Regulariza- tion and pariance-weighter regression achieves minimax optimality in linear mdps: Theory and practice. arXiv preprint arXiv:2305.13188 2023. (p. 2
Zhihan Liu, Miao Lu, Wei Xiong, Han Zhong, Hao Hu, Shenao Zhang, Sirui Zheng, Zhuoran Yang. and Zhaoran Wang. Maximize to explore: One objective function fusing estimation, planning, and exploration. In shirty-seventh Conference on Neural Information Processing Systems, 2023.
(p.2)
Peter Rossky, Jimmie Doll, and Harold Friedman. Brownian dynamics as smart monte carlo simulation. The Journal of Chemical Physics, 69(10):4628-44 4633, 1978. (p. (p.3)
Gareth O Roberts and Osnat Stramer. Langevin diffusions and petropolis-hasttng algorithms.
Methodology and computing in applied probability, 4(4):337-357, 2002. (p. (p.3)
Radford M Neal et al. Meme using hamiltonian dynamics. Handbook of markov chain monte carlo, 2(11):2, 2011. (p.
Gareth O Roberts and Richard L Tweedie. Exponential convergence of langevin distributions and their discrete approximations. Bernoulli, pages 341-363, 1996. (p.
Dominique Bakry, Ivan Gentil, Michel Ledoux, et al. Analysis and geometry of Markov diffussoo operators, volume 103. Springer, 2014. (p.
Difan Zou, Pan Xu, and Quanquan Gu. Faster convergence of stochastic gradient langevin dynamics for non-log-concave sampling. In Uncertainty in Artificial Intelligence, pages 1 1152-1162, PMLR, 2021. (p.
Kumar Avinava Dubey, Sashank Reddi, Sinead Williamson, Barnabas Poczos, Alexander Smola, and Eric P Xing. Variance reduction in stochastic gradient langevin dynamies. Advances in neural information processing systems, 29, 2016. (p. (p.
Pan Xu, Jinghui Chen, Difan Zou, and Quanquan Gu. Global convergence of langevin dynam- ics based algorithms for nonconvex optimization. Advances in Neural Information Processing Systems, 31, 2018. 4p.4)
Difan Zou, Pan Xu, and Quanquan Gu. Subsampled stochastic variance-reduced gradient langevin dynamics. In International Conference on Uncertainty in Artificial Intelligence, 2018, (p.4)
Difan Zou, Pan Xu, and Quanquan Gu. Sampling from non-log-onn non-log-concave concave distributions via variance- reduced gradient langevin dynamics. In The 22nd International Conference on Artificial Intelli- gence and Statistics, pages 2936-2945. PMLR, 2019. (p.
12

---

Published as a conference paper at ICLR 2024
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004. PMLR, 2019. (p.
Ruosong Wang, Russ R Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33, 2020. (p.
Tor Lattimore, Csaba Szepesvari, and Gellert Weisz. Learning with good feature representations in bandits and in rl with generative model. In International Conference on Machine Learning, pages 3670- PMLR, 2020. (p.5)
Benjamin Van Roy and Shi Dong. Comments on the wawaaaaaaaaggaeeeeee lower bounds. arXiv preprint arXiv:1911.00 .79900 2019. (p.5)
Nima Hamidi and Mohsen Bayati. On worst-case regret linear thompson sampling. arXiv preprint arXiv:2006.066 06790, 2020. (p.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoff's. In International Conference on Machine Learning, pages 127-135, 2013. (p. (p-5)
Mare Abeille and Alessandro Lazaric. Linear thompson sampling revisited. In Artificial Intelligence and Statistics, pages 176-1 84. PMLR, 2017. (p. 5)
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):529-533, 2015, (pp. 5 and
Changyou Chen, Nan Ding, and Lawrence Carin. On the convergence of stochastic gradient meme algorithms with high-order integrators. Advances neural information processing systems, 28,
2015. (p. 6
Yee Whye Teh, Alexandre H Thiery, and Sebastian Vollmer. Consistency and fluctuations for stochastic gradient langevin dynamics. Journal of Machine Learning Research, 17, 2016. (p.
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. (p- 6))
Yann N Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem in high-dimensional non-convex op-
timization. Advances in neural information processing systems, 27, 2014. (p. 6
Tijmen Tieleman, Geoffrey Hinton, et al. Lecture 6.5-rmsprop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):26-31,
2012. (p. (
Sehwan Kim, Qifan Song, and Faming Liang. Stochastic gradient langevin dynamics with adaptive drifts. Journal of statistical computation and simulation, 92(2):318-336, 2022. (pp. 6 and [8]
Samarth Sinha, Homanga Bharadhwaj. Aravind Srinivas, and Animesh Garg. D2rl: Deep dense
architectures in reinforcement learning. arXiv preprint arXiv:2010.09163. 2020. (p. 6
Kei Ota, Devesh K Jha, and Asako Kanezaki. Training larger networks for deep reinforcement learning. arXiv preprint arXiv:2 102.07920, 2021. (p-
Ryan Sullivan, Justin K Terry, Benjamin Black, and John P Dickerson. Cliff diving: Exploring reward surfaces in reinforcement learning environments. arXiv preprint arXiv:2205.070/5. 2022.
(p.
Peter Henderson, Joshua Romoff, and Joelle Pineau. Where did my optimum go?: An em- pirical analysis of gradient descent optimization in policy gradient methods. arXiv preprint 1r10v 2018. 6p.
13

---

Published as a conference paper at ICLR 2024
Johan Samir Obando Ceron and Pablo Samuel Castro. Revisiting rainbow: Promoting more insight- ful and inclusive deep reinforcement learning research. International Conference on Machine Learning. pages 1373-1388 1383. PMLR, 2021. (p.
Alexander L Strehl and Michael Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, (188):1309-1333 2008.
(pp. and 42
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: 7706. /0295, 2017. (pp. and T8)
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. (p. 8)
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. (pp. 8 and [8
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience replay. arXiv preprint wrXiv:1511.059555 2015. (p. 8)
Mare G Bellemare, Will Dabney, and Rémi Munos. distributional perspective on reinforcement learning. In International Conference on Machine Learning, pages 449-458. PMLR, 2017. (p-
Will Dabney, Mark Rowland, Mare Bellemare, and Rémi Munos. Distributional reinforcement learning with quantile regression. In Proceedings of the AAAI Conference on Artificial Intelli- gence, 2018a. (p.
Will Dabney, Georg Ostrovski, David Silver, and Rémi Munos. Implicit quantile networks for distributional reinforcement learning. In International conference on machine learning, pages 1096-1105. PMLR, 2018b. (p.
Hado Van Hasselt. Double q-learning. Advances in neural information processing systems, 23, 2010. (p.8)
Vikranth Dwaracherla and Benjamin Van Roy. Langevin dqn. arXiv preprint arXiv:2002.07282, 2020. (pp.
and
Tianjun Zhang, Tongzheng Ren, Mengjiao Yang, Joseph Gonzalez, Dale Schuurmans, and Bo Dai. Making linear mdps practical via contrastive representation learning. In International Conference
Machine Learning, pages 26447-26466. PMLR, 2022. (p. 9
Reda Ouhamma, Debabrota Basu, and Odalric Maillard. Bilinear exponential family mdps: fre- quentist regret bound with tractable exploration & planning. In Proceedings of the AAAI Confer- ence on Artificial Intelligence, volume 37, pages 9336-9344, 2023. (p.
Gellért Weisz, András György, and Csaba Szepesvari. Online RL in Linearly Reallizza MDPs Is as Easy as in Linear MDPs If You Learn What to Ignore. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. (p. 9)
Malcolm Strens. A bayesian framework for reinforcement learning. In ICML, volume 2000, pages 943-950. 2000. (p. 18)
Zhihan Xiong. Ruoqi Shen, Qiwen Cui, Maryam Fazel, and Simon Shaolei Du. Near-optimal ran- domized exploration for tabular markov decision processes. In Advances in Neural Information Processing Systems, 2022. (p. [8]
Ziniu Li, Yingru Li, Yushun Zhang, Tong Zhang, and Zhi Zhi-Quan Luo. Hyperdqn: A randomized exploration method for deep reinforcement learning. In International Conference on Learning Representations, 2021. (p. [8]
14

---

Published as a conference paper at ICLR 2024
Ian Osband, John Aslanides, and Albin Cassirer. Randomized prior functions for deep reinforcement learning. Advances in Neural Information Processing Systems, 31, 2018. (p. 18 )
Matthias Plappert, Rein Houthooft, Prafulla Dhariwal, Szymon Sidor, Richard Y Chen, Xi Chen, Tamim Asfour, Pieter Abbeel, and Marein Andrychowicz. Parameter space noise for exploration. In International Conference on Learning Representations, 2018. (p. [8_[8]
Nikki Lijing Kuang, Ming Yin, Mengdi Wang. Yu-Xiang Wang, and Yian Ma. Posterior sampling with delayed feedback for reinforcement learning with linear function approximation. Advances in Neural Information Processing Systems, 36, 2024. (p. [8]
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, 12051-12551,, 2021. (p. 18
Tong Zhang. Feel-good thompson sampling for contextual bandits and reinforcement learning. SIAM Journal on Mathematics of Data Science, 4(2):834-857, 2022. (p. 18]
Daniil Tiapkin, Denis Belomestny. Éric Moulines, Alexey Naumov, Sergey Samsonov, Yunhao Tang, Michal Valko, and Pierre Ménard. From dirichlet to rubin: Optimistic exploration in rl without bonuses. International Conference on Machine Learning, pages 21380-21431. PMLR,
2022. (p. 18
Ian Osband, Benjamin Van Roy, Daniel Russo, and Zheng Wen. Deep exploration via randomized value functions. Journal of Machine Learning Research, 20(124):1 2019a. (p. I8]
Ian Osband, Yotam Doron, Matteo Hessel, John Aslanides, Eren Sezener, Andre Saraiva, Katrina McKinney, Tor Lattimore, Csaba Szepesvari, Satinder Singh, et Behaviour suite for reinforce- ment learning. In International Conference on Learning Representations, 2019b. (p. 18]
Milton Abramowitz and Irene A Stegun. Handbook of mathematical functions with formulas, graphs, and mathematical tables, volume 55. US Government printing office, 1964. (p. (p.39)
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312-2333 2312-2320, 2011. (p. 40
Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012. (p. 40)
Roman Vershynin. High-ddmennsonal probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018. (p. 40
Jiayi Weng, Huayu Chen, Dong Yan, Kaichao You, Alexis Dubureq, Minghao Zhang, Yi Su, Hang Su, and Jun Zhu. Tianshou: A highly modularized deep reinforcement learning library. Journal of Machine Learning Research, 2022. (p. 44
John Quan and Georg Ostrovski. DQN Zoo: Reference implementations of DQN-based agents, 2020. URL http:tttt/ggghhhbbbtttt com. deepmi nd/ hdddddgg_ooo (p.
15

---

Published as a conference paper at ICLR 2024
CONTENTS
Introduction
Preliminary
3
Langevin Monte Carlo for Reinforcement Learning
4
Theoretical Analysis
4
5
Deep Q-Network with LMC Exploration
6
Experiments
6.1
Demonstration of Deep Exploration
6.2
Evaluation in Atari Games
7
Conclusion and Future Work
Related Work
18
Proof of the Regret Bound of LMC-LSVI
19
B. I Supporting Lemmas
19
B.2 Regret Analysis
20
C Proof of Supporting Lemmas
22
Proof of Proposition B.1
22
Proof of Lemma B.3
23
Proof of Lemma B.4
30
4 Proof of Lemma B.5
30
Proof of Lemmal
32
C.6 Proof of Lemma B.7
33
Removing the interval constraint on in Theorem
35
D.i
Multi-Sampling LMC-ISVI
35
................................
D.2 Supporting Lemmas
36
D.3 Regret Analysis of MS-LMC-LSVI
38
Auxiliary Lemmas
39
Gaussian Concentration
39
Inequalities for summations
E.3
Linear Algebra Lemmas
40
Covering numbers and self-normalized processes
40
Experiment Details
42
16

---

Published as a conference paper at ICLR 2024
F1
Experiments for LMC-LSVI
42
F.1.1
Randomly generated linear MDPs
42
2
The RiverSwim environment
43
V-Chain
43
F3
Atari
44
F3.1
Experiment Setup
44
E.3.2
Additional Results
45
17

---

Published as a conference paper at ICLR 2024
A RELATED WORK
Posterior Sampling in Reinforcement Learning. Our work is closely related to a line of work that uses posterior sampling, i.e., Thompson sampling in RL (Strens) 2000). Osband al. (2)16a), Russo (2019) and Xiong et al. (2022) propose randomized least-squares value iteration (RLSVI) with frequentist regret analysis under tabular MDP setting. RLSVI carefully injects tuned random noise into the value function in order to induce exploration. Recently, Zanettee et al.] (2020a) and Ishfaq et al. (202I) extended RLSVI the linear setting. While RLSVI enjoys favorable regret bound under tabular and linear settings, it can only be applied when a good feature is known and fixed during training, making it impractical for deep RI. (Li et al.] (022). Osband et al. (2016b) 2018) addressed this issue by training an ensemble of randomly initialized neural networks and viewing them as approximate posterior samples of Q functions. However, training an ensemble of neural networks is computationally prohibitive. Another line of work directly injects noise to
parameters (Fortunato et al.) 2017] Plappert et al. 2018). Noisy-Net (Fortunato et al. (2017) learns noisy parameters using gradient descent, whereas Plappert et al.) (2018) added constant Gaussian noise to the parameters of the neural network. However, Noisy-Net Net is not ensured to approximate the posterior distribution (Fortunato al. (017). Proposed by Dwaracherla and Van Roy (2020), Langevin DQN is the closest algorithm to our work. Even though Langevin DQN is also inspired by SGLD (Welling and Tch 201T), Dwaracherla and Van Roy| (2020) did not provide any theoretical study nor regret bound for their algorithm under any setting. In a concurrent work. Kuang et al.) (2024) studied linear MDP with delayed feedback, where they also used an LMC-based posterior sampling algorithm, which theoretically resembles similarity to part of our theoretical study with no deep RL variant studied.
A recently proposed model-free posterior sampling algorithm is Conditional Posterior Sampling (CPS) algorithm (Dann et al. 202I). Similar to Feel-Good Thompson Sampling proposed in (Zhang, 2022). CPS considers opimistic prior term which helps with initial exploration. However, the proposed posterior formulation in CPS does not allow computationally tractable sampling. Another recently proposed algorithm Bayes-UCBVI (Tiapkin et al., 2022) uses the quantile of Q-value function posterior as UCBs on the optimal Q-value functions which can be thought of as determin- istic version of PSRL (Osband et al., 2013). While Bayes-UCBVI is extendable to deep RL, it does not have any theory for the function approximation case and their analysis only works in the tabular setting. Even for Bayes-UCBVI to work in deep RL, it needs well-chosen posterior, and sampling from the posterior is not addressed in their algorithm. Moreover, the Atari experiment in Tiapkin al. 2022) only shows average comparison against Bootstrapped DQN (Osband et al.) (016b) and Double DQN (Van Hasselt et al. 2016) across all 57 games. However, in-average comparison across 57 games not a sufficient demonstration of the utility of Bayes-UUBBV especially when comes to hard exploration tasks.
Comparison to Dwaracherla and Van Roy (2020). Here we provide a detailed comparison of Langevin DQN (Dwaracherla and Van Roy 2020) and our work. On the algorithmic side, at each time step, Langevin DQN performs only one gradient update, while we perform multiple (i.c., J&) noisy gradient updates, as shown in Algorithm D and Algorithm 2 This is crucial difference as a large enough value for Js allows us to learn the exact posterior distribution of the parame- ters (wn)eete up to high precision. Moreover, they also proposed to preconditioned SGLD optimizer which is starkly different from our Adam LMCDQN. Their optimizer is more akin to a heuristic variant of the original Adam optimizer (Kingma and Ba 2014) with a Gaussian noise term added to the gradient term. Moreover, they do not use any temperature parameter in the noise term. On the contrary, Adam LMCDQN is inspired by Adam SGLD (Kim et al., 2022), which enjoys convergence guarantees in the supervised learning setting. Overall, the design of Adam LM- CDQN heavily inspired from the theoretical study of LMC-LSVI and Adam SGLD (Kim et al,, 2022). Lastly, while Dwaracherla and Van Roy (2020) provided some empirical study in the tabular deep sea environment (Osband et al. 2219a b). they did not perform any experiment in challenging pixel-based environment (e.g., Atari). We conducted comparison in such environments in Ap- pendix F3.22 Empirically, we observed that Adam LMCDQN usually outperforms Langevin DQN in sparse-rewe reward hard-exploos explooraloot games, such as Gravitar, Solaris, and Venture; while in dense- reward hard-exploration games such as Alien, H.E.R.O and Qbert, Adam LMCDQN and Langevin DQN achieve similar performance.
18

---

Published as a conference paper at ICLR 2024
B PROOF OF THE REGRET BOUND OF LMC-LSVI
Additional Notation. For any set A, ( denotes the inner product over set A. For vector E R. || Vz is the Euclidean norm of For matrix V Rm**, denote the operator norm and Frobenius norm by ||V|2 and |[[[ respectively. For a positive definite matrix V E ddd and vector E R. we denote | = =vz Vv.
B.1 SUPPORTING LEMMAS
Before deriving the regret bound of LMC-LSVI, we first outline the necessary technical lemmas that are helpful in our regret analysis. The first result below shows that the parameter obtained from LMC follows Gaussian distribution.
Proposition B.1. The parameter uh R.Jn used in episode k of Algorithm Sollows Gaussian distri- bution N (1r
Dk.Je), where the mean vector and the covariance matrix are defined as R.Ja,
k.Ja Ph
A A...A
Av
1.0
A
Jet (T- (T-A,) wh.
Wh
Jeh.Je
Miis
(I- A? (Ai)-
" (T+ A.) A A
Bi
where A, - 2n for E [k]]
Definition B.2 (Model prediction error). For any (k; E [K] [H]. we define the model prediction error associated with the reward rh+
(2, a) = rn(a, + PA P (z, a) (x, a).
Lemma B.3. Let Algorithm 7 For any (ks h) E [K] x [H]. we have
k,Jk wh
16 -
HdVK
3/2 Bb, 33g8
2K
with probability at least 1 1- 8. Lemma B.4. Let X = 1 in Algorithm 7
For any fixed 0 < < 1, with probability 1 5, we have
for all (k, e [K] [H].
Σ 0(zh ag) [V++1 PAVA Shhh+1 (0% ah)
(AR)-1
1/2
2/2K
2 8
$ <dHvd
log(K (K + + log
+ log
2
H
where B5 = 16 Hdv K +
V
2K 3
d3/2
Lemma B.5, Let = in Algorithm
Define the following event
E(K, H,
= - -{1 -(100,, |00,
a) wh rn(x a) PA a)) s 5F
v(h,k) E [H] x K] and V(z, ((x,))
(9)
where we denote Cs logg(K (K 1) log
2v2KB5/2
log 2
1/2
and Bg is defined in
Lemma B.4 Then have P(E(K, H. H))))
5.
19

---

Published as a conference paper at ICLR 2024
Lemma B.6 (Error bound). Let À in Algorithm (K, H,,,, for all (h, E [ x [K] and (x, a) A. with probability at least 1 , we have
For any E (0,1) conditioned the event
2d (1/6) + 4/3 [1((,,))l((x))
ax) & 5HvaCs + 5/
(10)
33x
where C& defined in Lemma B.5
Lemma B.7 (Optimism). Let X Algorithm Conditioned on the event (KK, ((K,H,8) 8), for all (h, k) E [ x [K] and (z, a) E S x A, with probability at least 2x/2ex' we have
(1, a) S O.
(11)
B.2 REGRET ANALYSIS
We first restate the main theorem as follows.
Theorem B.8. Let = in Pk Ö(H Vd) in Algorithm 7 Mand E (2 1). For any
[ let the learning rate Uk 1/44 (AH)), the update number Jk 2ng log ( where K2 Amax (A),) ( (Af) is the condition number of Mr Under Definition 4.1 the regret
of Algorithm satisfies
Regret(K) 2 /T),
with probability at least 1 1
Proof of Theurem B.
By Lemma 4.2 in Cai al. (202)), holds that
K
Regret (T) =
Σ
(i(1 - VT (af)
k=1
K
H
Ex- [10 m. axn) T/C [xa))
x1
DK
t=1
A=1
(
(E
I% (2n, an) 21 =4]
(1
af))
(12)
(18)
(19)
where D and M are defined as
D = ((Q) - Q (ati :) (. - (0) Q (ah,
(13)
M = PA((V vati) att (Vh+1 Vittt
(14)
Next, we will bound the above terms respectively. Bounding Term (i): For the policy o at time step of episode k, we will prove that
K
H
(-1 mx) - - xx)) x1 at < O. KQ m.
(15)
Jrmn
To this end, note that o acts greedily with respect action-valus function Q If difference ) - Ix) is O. Otherwise, the difference is negative since क is deterministic with respect to Q Concretely, म takes value of where nÿ would take value of O. Moreover, Q would have the greatest value at the state-action pair where . equals This completes the proof.
then the
Bounding Terms (ii) and (iii): From (5), note that truncate Ø to the range [0, H - h h+ This implies for any (h, k) [K] [H]. we have [D]] 2H. Moreover, R(D] 0. where F
20

---

Published as a conference paper at ICLR 2024
corresponding filtration. Thus, Dj is martingale difference sequence. So, applying Azuma- Hoeffding inequality, we have with probability 5/3,
K
H
ΣΣ R=1k=1
D
& v 2/12Tlog((//))
where T = K.. Similarly, show that M is martingale difference sequence. Applying Azuma-Hoeffdiig inequality, we have with probability 6/3.
K
H
122HTT
Therefore, by applying union bound, we have that for any 8 > 0, with probability 1 25/3, it holds that
K
H
K
H
D
M
22 22/
2
log(30))
(16)
k=
A=1
k=1k=1
where T = KH.
Bounding Term (iv):
Suppose the event E(K, H, 8') holds. by union bound, with probability 1 - (82 + 2//c0 11))
) we have,
K
Ex (2h, and 21 = 1/ (2h ah)
H
(ath att)
H
2dlog (1/8))
5HVdC& +5/
+ 4/3
|0 ab)l
33K
k= hm1
2d (1/8")
K Σ
"
5H /dC +5/
+ 44/3
11 a ((a))
38K
R=
2d log (1/8")
H1
K
1/2
5H 5H +
44/3
Σ
VK
Σ
| at) al
3,3
h=1
k=1
2dg (1/8")
5HVdC8 +
+ 4/3
H /2dk log(1 + K)
33g
ldg (1/8")
5H vdC. +
4/3
2dHHT log(1 K)
333
Here the first, the second, and the third inequalities follow from Lemma B.7 Lemma B.6 and the Cauchy-Schwarz inequality respectively. The last inequality follows from Lemma E.4 The last equality follows from
VPk = 10H /dCa + & which we defined Lemma B.7
By Lemma B.5 the event E(K, H, 8') occurs with probability 1 8'. Thus, by union bound, the occurs and it holds that
event (K,, H.
Σ
Ex 11 (Th, an) 2 |=1==i = =tt (2 att)
with probability at least (1 (5' 8 2//201)) Since 8 E (0, 1), setting 8' 5/6, we have
8 1
1- (8' 82 +
> 1
2en
3
2 2en
21

---

Published as a conference paper at ICLR 2024
The martingale inequalities from Equation 16 occur with probability 1 - 26/3. By Equation 15
and applying union bound, we get that the final regret bound 0(2//2113/2 with probability at least 1 - (6 + 2//em In other words, the regret bound holds with probability at least 1 - 8 where
E 2V/25 1).
C PROOF OF SUPPORTING LEMMAS
In this section, we provide the proofs of the lemmas that we used in the regret analysis of LMC- LSVIin the previous section.
C.I PROOF OF PROPOSITION B.
Proof of Proposition B.1
First note that for linear MDP, we have
(l = 2 - br)
The update rule is:
k.j R-j-1 Wh uh
R.j. mh V (w 1) + 3
(w
En
which leads to wh. J. = w/
w/
k-
2771 (ARit - b/:) + v 3m en Je
=(1- (2) w/
k.Ja-1 11 + 2m + v 2. Bi 1
J--1
(I 21)
Je k.0
wh
+
Σ
(I (1-2)-At)'
22ubbt + v 2m (
1=0
J-
J4- Σ t-0
= -I 24p, Ah)
Ju
w/
8.0
+ 21
Σ (I - 27h Ai) U// + 21
(1-21AA
A.Ju-t cn
1=0
Note that in Line 6 of Algorithm
we warm-start from previous episode and set w/ k.0 = wi
--1,J--1
Denoting A; = - 21); Aj, we note that A; is symmetric. Moreover, when the step size is chosen such that 0 < ?) < 1/22 (Ak)), A, satisfies T > A₁ > 0. Therefore, we further have J&
Jx-1
k.Je wh
A k- --1,de-1 + 27
w/
ALA + v 2n
A4.
Je
J -1
-Aukun No- 1,je 1 + (T- As) (4 + A +... + A 1 1 +
Σ
Apchi
1=0
J4
= 1.Je
+ (I Abr ) wih + v 2m 3-1
A
c
b A
J 1.:
1,0 = A A..
w
Alii (I - A /
2n, A
A
Ale
1=1
Im
where in the first equality we used 1/ Ar in the second equality we used the definition of A and in the third equality we used the fact that I + A +... + - (1-A8 (I A)-1, We recall a property of multivariate Gaussian distribution: if N' Laxa), then we have Ae + μ ~ N(,, AAT) for any A E dd and μ E R4, This implies w R. follows the Gaussian distribution R,Ju,
N( 2ih )) where
k
k.Jo A A......A A wh 14
1 +
Σ A
J++1 [I A7" Th. b+1
(17)
i=1
22

---

Published as a conference paper at ICLR 2024
We now derive the covariance matrix D...e For a fixed i, denote M, /2n.0 1 ....... A/13'
Then we have,
J:- M;
J4
(
J-1 M.A((M.))))) ~N 0,
J/-1
Mi
1.J.-t ~ 0,
Σ
Σ
A
M,
1=0
1=0
1=0
Thus we further have
J
A?l
Mi
1=1
1=0
21,
A
Jes1
Σ
A7
A
1=0
Σ
AA
A..AA (I- A (I-A3) A
k
(2 - - 4 ...AA
Je
Bi
k
2=1
This completes the proof.
C.2 PROOF OF LEMMA B.3
Before presenting the proof, we first need to prove the following two technical lemmas.
Lemma C.1. For any (k E [K] x [H]. we have
| S 2H v kd/X.
Proof of Lemma
C.1
We have
| ||
(A
(n a + ((+a(1)41) 6(5 ah)
=
1/2
1
V
(1 a7) + Vhs (#h+1)] 600 (0thh.7)10 (
1/2
2H
Vk
[ o.. 0
VX
x 2H Bi//kd/A.
where the first inequality follows from Lemma E.5 the second inequality due < V H and the reward function being bounded by 1, and the last inequality follows from Lemma E.3
Lemma C.2. Let in Algorithm For any (h, k) [H] x [K] and (x, E x A. we have
2d (1/0)
4
((xx,)) T)T w ((x, wh < 5/
+
|
388
3
with probability at least 1 - 82.
Proof of Lemma C.2 By the triangle inequality, we have
((x, a) Tw k.Je (0x a) ToT wx < (o(x,a) a) (wh k.Jo
ke + (())a))
(mh - wx) (18)
u4
23

---

Published as a conference paper at ICLR 2024
Bounding the term [(z,a) a)T (wh - 1/ we have
a( a) (wfith Uh (hilhi) s (ba,, a)T (x)).l) 1/2
alll
-1/2
Since wh K.Ju
Ni s.hi we have (xhiih))
-1/2
w/
k.du
pnn""
(i.J0) )
~ NO, laxa). Thus, we
have
P
1/2
k.Ja
2 Addlog 24dlog(110) S0²
(19)
When we choose
Th S
(A,))) 11/(4
for all k, we have
< Av = I 2 A/ < (1 - 21Je Amin (A 1,
2
(20)
< I + Ax = 21 A < 2I.
2
Also note that Ag and (A 1 commute. Therefore, we have
2h (A -1 (T (T- 21)1 ... (T Ak) (T- 20 Ah) (A%) -1
(I 21/1- ...(I AT) (AR) -1 (I 27)
(21)
A (Ah) Att.
Recall the definition of 2/ Then
6(I, a)
T Lnhhdh ((I
4:
0(2,0) a) T AA A.. Jit1 A2-) (Ah) (1+ A.) (1+A " .... (x,
B
k
$
2
0(z, a) aaT A ... A..
Jan ((AR)~1 - 4 (AR) AAA4)) A ... ....A,, azz,a
33,
2
a(x,a) T A ! ((AR)~ - -AA2t) 1+1
A...A,
333
i=l
2
6(x a) A A (A!) -1 A ... A 6(x a) +
2
olI a) (At) -1 o(x,a),
38x
33x
where the first inequality is due to 20 and the last equality is due to setting 3r = 3x for all E [K]. By Sherman-Morrison formula and we have
(At) (A = (Ah) -1 Ma ah (z o/)) (Af)
(A + b(th ( T)
(At)
1 110(2) agp [lllp (Ap)-1
This implies
a(x,a) A ... A ((At) -1 (A A Litn
A (() a)
= Max, a) T Ale A (Ah) M( d0(2) (,))))))))) (AA)
A ... A (xx
1+ 1or ag 11l 1laaz
2 (Mx,0) a) T A ... A (At) -1 Marh 2
< Ag ... Aliit (At) 1/2 o( a0) 1|: |AA) 1/2 2l04/ oh) 1
2
k
< (1 2m, Amii (M
23: |0
ah) 11
11 a) 1))
j=it1
24

---

Published as a conference paper at ICLR 2024
where the last inequality is due 20p. So, have
((z,a) a) 21) -(2,0((xx))))))))) -
Σ II (1- 2ny Amin (A²)) 235
(1-21)
11 a ablllcns-- 110(2, a)(Aa))
335
i=1 1=i+1
+ 3,3k
||0((1,
()(AA)))
Using the inequality v + S a for a, b > O, we thus get
k
(1- 2n, Amin (A²))
[ o>1l> 1
II
|1 a Whla0))11111 (1 ()llass)))))
3,3
==1 -=
(22)
Let's denote the R.H.S. of 22 as Th (6(2, a)).
Therefore, it holds that
P (lole Twhn o(ss,)) a) k.Ja 2 20th ( dlog (1/8) 1h
P' (o(z, a) whth a( ph "i ž 2 d log (1/0)]l0(z, a) st.6
|oco,o) (= 1/2 || || (>))1) 11/2 (w p/: )1 )
2 2v d (1/8)ll a) all 2
$ 52
(23)
where the last inequality follows from
19 wh)
Bounding the term p(x,a)) aT
(1h
k
Recall that,
Mh
k.Je = A.e
A/ hh
1.0
A
J+t
(1 -A!4 )
Wh
= A ...
A
w/
1.0
Jal 1+1
(whh
wxt11
1/
A
A A w + 10
A
...
J1
wh 1,0
+
A
A/H
(w) - 0 i+1
+ w
This implies that
ő(2, T)TT k.Je wh) =0(z,)) TA A..A (wh² w// + Ólz, a)
Σ
A
A (Øf - wb iit
1=1
(24)
25

---

Published as a conference paper at ICLR 2024
In Algorithm we choose w) 1,0 0 and wh
(A 0. Thus have, 4 0. Using
inequalities in 20 and Lemma C.I we have
12 0
0 r a)
Av
A (00g 1
Σ (I,, a)
aaaaTaa A
241 (wh) - =
Amin (Ak)) J3 (10(10; a)) 1211, t
j=++1
2n, Amin (Nh))"
1 (1 a)ll (110%/12 + (0t++112)
j=1+1
2nj Amin (Nh))) 2 (, a)ll SHH/id/a
Σ
II (1- - 24j2min (M:)) a)l22.
SAHVKaI
-=i=
So, holds that
((x, a)T (1 wh) s 4H / Kd/> Σ II (1 2nz (1-21) Amin (A:)) 1 (1 (25)
1=1j=
Substituting 23 and 25 into 18
we get with probability at least 1 62,
(12, a) "w (b a) T wh
k II (1- (1-21; 2mi2min (N))) 3 11 a)lla + +2V
2d log (1/0)
< <4H/K//
|1bb,, a)llag))++
3,8
1=i+1
2d log (1/5)
(1 (1-21) 201 Amin (Az)) 1 |1 at a || a
+ 2
33x
J=
(26)
Let's denote the R.H.S. of (26) as Q. Recall that, for any j E [K], we require ny S 1/(4Amax (A₂)) Choosing 17, 1/(4Amax (A,)) yields
[ 2n Amin (AA))* J3 =11-1/(2k)))
where Ki A-mam (A/)) Amin (A,)). In order to have (1 - 11(((2))))) < e, we need to pick Jj such that
log (1/e)
J,
log 1-1/(2mg)
Now we use the well-known fact that e > x for 0 < x. < 1. Since 1/(2k,) I 1/2, we have log (1/(1- ((111/2x)) 2 1/2nz. Thus, it suffices set J; 2xy log (1/e) to ensure
1/2m,)) & Also, note that since A3 > I, we have 1 2 | a)ll 2 [10(,, a)ll(a)) Setting
26

---

Published as a conference paper at ICLR 2024
d/ and À obtain
4H
/// Kd 10(2, 0))2 1
2d (1/6)
[1((2 +
Σ
x l a))
33K
Kd V V
HH
2d log (1/0)
(1((())))(
+ Σ
k-1
V
33K
2ml
2d 2d (1/0)
4-i-1 |b, ()l(a)))((())>
+//
[10(x;)))l(a))) +
Σ k-i-1
(1b a)l(a)))))))
33x
2d log (1/0)
4 +
5/
l1 a))l(a)))))))
33K
where the second inequality is due to || (10((z,) (a) 2 1/V////(z, E k-i-1
a)ll2 and the fourth inequality E/= e < 1 c) 4/3. So, have
due
P (o(x,a) wh H.Jh o(x, a) w
To - /VV
2d 2d (1/5)
4
(10(,, (1(aa)))
+ 3
33K
2 P () hirt a( Tw &Q)
2 1 8².
This completes the proof.
Proof of Lemma B.3 From Proposition B.1
we know
R.Ju w
follows Gaussian distribution
N( k,J2 sk.Je) Thus can write,
J. = |
JeJe + skc <
J. ||
+ +1
1/
where chijee (O, s.h
Bounding (114 k.Jk I|2: From Proposition B. we have,
J.Je Un
=
A
A
w
A
A
(I - A!" 1
1=1
A
A Jit1
A+1
(I -
A!'² Tht
1=1
27

---

Published as a conference paper at ICLR 2024
where the inequality follows from the fact that set wh 0 in Algorithm I ity. Denoting the Frobenius of a matrix X by || e| we have
and triangle inequal-
J++1 (I - A/ 86l12
k
A
dit1 (I
(I- - A7t² |1- |0%/12
i=1
Kd k
$ 2H
A
1/13" (1-1::) 1
i=1
S 2H
kd
k
Vd
A (1- 4 )12
1=1
K
h:
... ||A-1 1 || (I- )|1
<2Hd
AAull2
K 22Hd
k
(1 2n, Amin(((())) J5 (117112 + 11A%/1l))
II jmi+1
π
K
k
II (1- 2n, (1-21; Amin (mn)( 35 (11ZI1+ + I1A.11/)
22Hd
j=i+1
K
k
II (1- 2n, Amnin (A%) (1 (1 - -21%% (amm((()))))))))))))) (Ab)) jmit1
22Hd
Ā 1=1
22Hd
K Σ
k
II jmi+1
(1 - 2ny Amin (A2) + II (1 (1- 20 Amii) (1-2)))mim(A2))) jm
k
where the second inequality is from Lemma C.I the third inequality is due to the fact that vank(A,) ... A/45'(T A and the fifth one is from Lemma E.6land and (20).
)/")) < d. the fourth one uses the submultiplicativity of matrix norm,
As in Lemma C.2 setting J, 2 2n, log (1/c) where Ni = AA)))(Af)) drmin (Ah) and e 1/(4HKd), x=
we further get
K k S 2Hd
A ... A411 (I -
(e- + c(
K
S AHd
K
= =4Hdy
K
4
< AHd
16
K
= 3 Hd
Thus, setting À = 1, we have
1 112 W 16
Hdvk.
3
Bounding [|et. I12: Since ch ~ NN( ~1(0, Ixi
), using Lemma E.
we have
P ||st ||2 < V Tr (>th)))
2 1 - 8.
28

---

Published as a conference paper at ICLR 2024
Recall from Proposition B.1
that
k
1111 (I- (M1) -1 (1 ( A.) A .....
Bi
Thus,
b:
Tr (D..E (
Tr
A
A (1 (1- APU1 (A
(I A.) A ... A/t1
Bi
i=1
h
Tr
(A
Tr (A/t)) Tr (I- A4" TO ((A)) Tr ((++A))))
==1
x Tr
A
1:11 i+1
Tr
where used Lemma
B.7
Note that if matrix A and B positive definite matrix such that
A > B > O, then Tr(AA
Tr(B). Also, recall from 20) that, when Thk- I 1/(4Amax (Af)) for all
k, we have
A₂ 1 - A2 < (1 27 Amin (A 1.
2 < I + A+ = 21 - -2 < 21.
So, we have A < (1 - 21 Ami (AR)) 13 and
Tr (4
S Tr ((1 21th Amin (AR)) 1)
S (1
20 Amin (A/))) J3
$ de
d
4HKd $
where third inequality follows from the fact that in Lemma C.2 we chose J, such that (1-2ng 2n, Amin((f))
(Aa)) J3 S and the first equality follows from the choice of 1/(4HKd). Simi-
larly, we have 1 A?t. < (1 2b.r) I and thus,
Tr (1 (T- ARth)
(1 225 d.
Likewise, using (1+ A:) < 3 we have
Tr 11) <
3 d.
Finally, note that all cigenvalues of AJ, are greater than or equal to I, which implies all eigenvalues of (Af)) -1 are less than or equal to Since the trace of matrix equal to the sum of its eigenvalues, we have
((A -)) S d- d.
Using the above observations and the choice of 3, = 3K for all E [K], we have
K
Tr (It.Je
1 2
d 2 Kdd
3x
33K
Thus we have
PP
Sh
V
1
3/8
2
Kd
2
P
5h
ck,e
2
I
V8
Tr (xtidl)
2 1--6 8. 21-6.
29

---

Published as a conference paper at ICLR 2024
So, with probability at least
6, we have
wh
R,Jx
16
HldVK< +
|/
3,300 3
2K
13/2
which completes the proof.
C.3
PROOF OF LEMMA B.4
Proof of Lemma B.4
Applying Lemma
B.3
with probability 1 18/2, we have
J /
16
HdvK +
4K
d2/2 -B6/2.
(27)
3
33k8
Now, considering the function class V = { maxae o( a)
T w, H. ||wll2 S B8/2) and
combining Lemma E.8 and Lemma E.10 we have that for any and ò > with probability at least 1 - 8/2.
Σ 6027 ohh [V (27 Pr Vi n+1 (2 I (x
(A/)-1
d
k+
B6/2
2
2
log
+ dlog
+ +lo
2
X
1: +
B8/2 E
2 1/2
2v 2/2kE 2kE
< 2H
log
+ d dlog
log
(28)
V2
Setting A = 1, 2v2k*
H
we get
Σ o( ah) (V - Pn vht (2% an)
(At)-1
1/2
B8/2
< <2HVd
log(A: + +1) + log 2
+ log
+
HH
8
2//2k
21/2
1/2
f2/2K B8/2
2
s <3HVd
log( K + 1) + log 2
+ log
(29)
H
with probability stated result.
8/2. Now combining
and
through union bound, we obtain the
C.4 PROOF OF LEMMA B.5
Proof of Lemma B.5
We denote the inner product over by (s (s. Using Definition 4.1 we have
PA v/ (2, 0) = ((x.a) a) (mh, Vitzi's
= =(x,a) a)T (AR) Agaun Vhtis
k-1
= a(z (AR)
Σ
slah ())o(ha ah) + xx) (un, Vitiis
(30)
a) (At)
6l2% a (P. V (2% a7) AI Viri)s) Σ
30

---

Published as a conference paper at ICLR 2024
Using 30
we obtain,
6(2, a) wh - rn( a) - Ph 1 (2,
k-1
= (Ah) -1
(1 ah) + Vhtt 2(27 a,)) ra(o, a)
T=1
- b(x, (AR)
Σ oa (P + AI (ur, Vitils
a(x,a) (AA)
PA V ( a ca on) (
+ 6(x, (A (AA
Σ
(a (n)d(T)
(2)
(i)
- A0(2, (AA)) (mn, viti)s.
(31)
(i))
We now provide an upper bound for each of the terms in (31 Term(i). Using
inequality and Lemma B.4 with probability at least 1 - 8, we have
6(x,0) (AA))
Σ p a1) (V (2)+1) PA ( af]]
plrh, an) ( PV-. (2h, añl]
| al),))))
(A/))-1
1/2
s <3HVa log(K + + + log
22/2K B8/2
+ log
2
|| a))((a))
(32)
Term (ii). First note that,
o(z, ((r,a) 1
Σ nh ( (D) (n(2r,a)
a( ((At)
rn aI 00)0% 0.)) -0(z, a) T
6(2,
6(z, ((TT))((A)))))
(1 a o0)6% o Ar
a( ((A)))
(0 a (0)))(22..000 ah)
6l (6) 0 AIO
o(z, T(A)))
(2 1002 a.)
6( o - X10,
=-10(2,a) -1
(33)
31

---

Published as a conference paper at ICLR 2024
Here we used the definition FA (2, a) Schwarz inequality, we further get,
( 0n) from Definition 4.1
Applying Cauchy-
-àØ(2, a) (A(T)
I All( (
s VVlloo, ())) .10,112
(34)
I VAd]oo(z a) ()(())))
Here we used the observation that the largest eigenvalue of (AA) at most 1/A and |001l2 I vd from Definition 4.1 Combining (33) and (34), we get,
a(x,a) (A
Σ Th
atd
rn(a,a) & -
Vidllo(,,a)lloo>>> (35)
Term(iii). Applying X0(x, a) (AA)) (un. Vh+ s (1o(,, illun, Vh (nsllslle
inequality, we get,
S (1) -llua Vit1)slle
$
(36)
S (Allé(za))l((a))
Σ 1ItNR
HVAd (( a))
where the the last inequality follows from Σ || & in Definition 4.1 and (36), and letting À 1, get, with probability least 1 -
Combining
32
35
JØ(I, a)
T (x a) - PP
22/2K B8/2
2
1/2
3HVd
log( (K(K (K+ + 1) + log
log
vdd HVAd
l1b alllas)))
2
H
1
2/2K B5/2
2 8
1/2
< 55Hva
log( K + + log
+ log
(1o(z,
2
H
5HT |,, a))((a))-
(2/2KBr/2) + log 27 1/2
where we denote C3 = log(K +1 + log
C.5 PROOF OF LEMMA B.6
Proof of Lemma
B.6
First note that,
1/ (2, (2, an( - PA V h4 (x, a)
minfø(z, a) wh k.de H
- (2, - PA (o,
I őiz, a) T "w (x( - PA P
= olx, a) Tw k.Jz - 00xx a) T .t
,l, a) Tw, - (2, a) Pn V (x, a)
á(x, a) Twj k.de olx a) wh ,( a) o - rr(x a) PA, V (z.
Applying Lemma C.2 for any kh [H] [K] and (z, a) E S x A, we have
2d log (1/0)
((1, To k.Ju 66x, a) wh <
wh
5/
+ 3 llós,, a)ll
33x
32

---

Published as a conference paper at ICLR 2024
with probability at least - 8².
From Lemma B.5 S A, we have
conditioned on the event H, for all (h, E [H] x [K] and (z,a) e
10 a) T a (2) - PA (2, P
So, with probability 1 - 1-
(1, S (2) + (ii)
2d 2d (1/0)
5HvVCa + +
+ 4/3 10(2,,))la
33k
This completes the proof.
C.6 PROOF OF LEMMA B.7
Proof of Lemma B. We want to show Q (z. a) (, +P a) with high probability.
H. 11 Also note that ra (2 a) + V (x, H 1. Thus, when o(x, a) T k.Js H h we trivially have (z a) 2 (z, + b.Je H-h+1 and thus Q (z)
Recall that Q (2r a) minfØ(x, a) Wh J.
h FA. FAVV h+1 (xx, a). So, we now consider the case, when p(x, a) Twh 6(2, Tw,
Based on the mean and covariance matrix defined Proposition B.1 follows the distribution (o(x,, a) Ph k.J2
we have that 6(x, a) w k.
T
,6(2,a)
- (( a)).
Define, Z4 Palz,a)P,, Vh (x.a)))))) Aith
When [ul < 1, by Lemma E.2 we have
Volona) s. ((..a)
P (o(r, T w0 2 (a(2,,) + Pr V (x
6(1, a) wh
k.Ju - Φ(0, a) 14
T k.ja
(n( + PA V. a), - )(I,a) a)T k.Ju
Pn
P
Vo(z, a) Nit (12,
Vola, a) 1t 6(2,0)
exp (-Zz/2)
2
2e
We now show that 17xl < under the event E(K, H, 6). First note that by triangle inequality, have
(ra(t, a) Pr PP a) ((0, a)T
14 k.Jo
$ (1n((,,)) + PA V (I, a) (1x, a) wh + Ól, Tah ó(τ, T J.Ja
By definition the event (K, H, 8) from Lemma B.5
we have,
(m) PA (x, 6(x, w < 5HV
From 25 we have
(o(z,)) a) Too wh a(2,a) ( S 4H 4H
II (1 2m (A1))" [10(2,
1=141
33

---

Published as a conference paper at ICLR 2024
As in proof of Lemma
C.2
setting 7 1/(4Amax(Af)), J, 2 2ng log(////))) we have for all
j E [K]. (1 (1-2 Amin (/
J3
S. Setting e 1/HHHK)) we have,
k.Je (6(,,)) Twhh ()(,,a) 11
S AHWKK
4HKd
[1 [
IN
d'lé(a, a)l( 1
1 a)
10(zz, all(aa))
So, we have
(z, - Mxx,) pn [ s (sHvāc, + 3 [
(37)
Now, recall the definition of Jr from Proposition B.1
(12 a)
T) Jh ((
k
(x,, a) T A ...... A/ (I- A2:) (At) -1 (I + A,) A ... A (()
3
i=1
Σ
a) A A (I (I- A (Ai) -1 A A. (0
2
28
i=1
where we used the fact that 1 < (1 + As)- Recall that in 21.. we showed A2 (A%) -1 A (At) A So.
0(I, a)
In (xx a)
((r, a) A A..A ((A)) - A (Ai) A/ A ... á(r,a)
23,
1=1
1-1
((I, a) A ... (1 - (4) A 10r a)
233
1=1
28x Mxx a) T 2 A (A)) -1 ... A p(x a) +
1 (tx, a) T (At)-' (a,
23x
where we used the choice of 3r Bx for all i [K]. By Sherman-Morrison formula and (6) have
(Ai) (A - (A = -(Ai) - (Ai, + blah (h) T)-
(At) -1
(Af) 1 + || at) 1
34

---

Published as a conference paper at ICLR 2024
which implies
Ó(z, a) T A Je4 ((A))- (A A (.,
tha (A%) o( a ). oh) (AA)
p(a, a) A ... ... Ait1
Jess A
1 ( 0/ (A))
(0(z, a) T A
A/T (AA) - ah)
A/ Me (11)
1/2 p(x, a) 1/: (1/)) 00000//00/000000////////)/ a ) ||
II (1 (1-21)) Mma (1a)) 23h j=i+1
(I 10(22 of 1 (1 a) a)(aa))>
where we used ( < 1/i S 110(2, a (l(a)) I 1. Therefore, we have
6(x, a) _ Ex. 6(x,a)
1
10(2, a) I1 ((at)
II (1 Amin (At)) mmi)) 23: (10(2,a)l(Ap))
23
28x
k- k
(1- 2n, Amin (Az)) 2 | a a a) a)
2BK
j=i+1
Similar to the proof of Lemma
C.2
when we choose Jj 2 Kij log(3v we have
| a)llsk. 2
1
10(2, (o(=a)))
|0(x,, a)l2
Σ (v3R)=- ll0(z, a)lla
k-1
1
BK
(3Vk)*
[[o((,,a)l(at))
3vh 11((r, - 6v (1((x,
1
1
(38)
2 BB
10(x, a))((a))-1,
2/3K
where we used the fact that Amin ( ((A)) 2 1/k. Therefore, according (37) and (38. holds that
rn(x, a) + Ph PR h++1 1 a) - -(0 a) 14
k.Jo
Z
V M1x a) 1 ()1
(39)
5H SHVdCK+ +
2VDK
which implies [Zal < when
10H 10HH + -
VBx
D REMOVING THE INTERVAL CONSTRAINT ON 8 IN THEOREM 4.2
As discussed in Remark 4.3 one shortcoming of Theorem 4.2 is that it requires the failure probability
5 to be in the interval 2/
1). However, in frequentist regret analysis it is desirable that the regret
bound holds for arbitrarily small failure probability. Motivated from optimistic reward sampling scheme proposed in (Ishfaq et | (202I), below propose modification of LMC-LSVI for which we have the same regret bound that holds with probability 1 - for any e 10, We call this version of the algorithm MS-LMC-LSVI where MS stands for multi-sampling.
D.1 MULTI-SAMPLING LMC-LSVI
Multi- Saltii-Sapping LMC-LSVI follows the same algorithm as LMC-LSVI (Algorithm) I with one maintain parameterization wP for each step h. [H] After
difference. In Algorithm [
35

---

Published as a conference paper at ICLR 2024
performing noisy gradient descent on this parameter Jg times in Line 7 to 10, this perturbed parameter to define our estimated Q function Line 11. We follow exactly the same procedure in MS-LMC-LSVI but instead of maintaining one estimate of Q function, [mE[aa through maintaining M samples of w: {w,, ".. J where (t.)) -) Tu, ", k.... and Jme [m][M] are intialized as zero vector. Then, we can make an optimistic estimate of Q function by setting the following
generate M esti- J
mates for function {Q*m) ]me[ar]
Q+(+))) = min max (0h" (-)), mm(M)
(40)
D.2 SUPPORTING LEMMAS
First, we outline the supporting lemmas required for the regret analysis of MS-LMC-LSVI. Lemma D.I. Let X 1 in 4). For any (k, [K] [H] and m E [M], have
w
k.
16 K +
2K
88/2
Bg,
3
33x0
with probability at least 1 -
Proof of Lemma D.I The proof is identical to that of Lemma
B.3
Lemma D.2. Let X 1 in 44. For any fixed 0 < 8 < 1, with probability 1 ô, have for all (k, h) E [ x [H].
k
Σ
p(o an) (v IPh Vhet (I [ñ]]
(at))=
2 1/2 g
2/2K (22KBB/2M B8/(2M)
$ 3HVd
2
log(K + +1) log
+ log
H
where B₁
16 Hdv
2K d3/2 38gg
Proof of Lemma D.2 1 - 8/2, for all m [M) have
Applying Lemma D.I and applying union bound over all m, with probability
k.J.m w
16 HdvK
4MK 3
8/2 B8/(2M)
(41)
3
Similar to the proof of Lemma (max.e.4 min { maxxme[M o(-,a)
considering the function class V
w H Vm E [M], 1 ||2 I B5/(2M)) and combin-
ing Lemma E.8 and Lemma E.11 we have that for any E > and > 0, with probability at least 5/2,
Σ o(1h, aT) [V/+ Pn V
(2 ahl
(A))-1
d
k+ A
(8/(2M))
2 1/2
2 2v2ks
2H
log
+ d.M dog log
+ log
(42)
As in the proof of Lemma
B.4 setting 1,
11 2//44
we get
Σ pl a VV ( Pr V (1 a7)
(AR)
2 2222K10 22/KBB8/2n B8/(2M)
2
1/2
< 3/1 vd
log(K +
1) +
A log
log
(43)
2/
with probability 1 1 5/2.. Applying union bound completes the proof.
36

---

Published as a conference paper at ICLR 2024
Lemma D.3. Let À 1 in 4.. Define the following event
E(K, M,
= -11occ a) wh - _
- s 5H 5H SH 1
E( [H] x |]] and (()
(44)
where we denote Cs,M 1 log(K K +1) M log (o/caa)
+ log /
1/2 and Bs is defined
in Lemma D.2 Then have P(E(K, H, H,M) 2 1 8.
Proof of Lemma D.3 The proof is exactly the same as that of Lemma B.5 We just need to replace Lemma B.4 with Lemma D.2 when it is used.
Lemma D.4 (Error bound). Let X = 1 in 14. For any 8 E (0.1) conditioned on the event
EKK, H. 6, for all (h, k) [H] [K] and (z,a) E x with probability least 82, we have
(1), & (5HVCCs+ + +
2d (1/0)
33x + 4/3 (1 (1(a))
(45)
where Cs.M is defined in Lemma
D.3
Proof of Lemma D.4 The proof is exactly the same that of Lemma B.6 We just need to replace
Lemma B.5 with Lemma D.3 when it is used.
Lemma D.5 (Optimism). Les X = in and M log( HK/5)/ log(1/( ((1-c)) where e: 2/20a
and 5 E (0,1) 1). Conditioned on the event E(K, H. M, 8), for all (h, k) E [H] x [K] and (I,u)
A, with probubility least 1 8, we have
[x 0) 5.
(46)
Proof of Lemma D.3 We have (x a) h+ 1, when maxme[M] Q (x. a) H h+ and we trivially have (xx a) S 0.
kim Using the exact same proof steps Now, we consider the case, when Q (I, a) = max [M] 2 as done in Lemma B.7 we can first show that for any (k: h) E [K] x [H] and any m E [M]
P (@ (z,a)) +
PA ( (1, 2
1
(47)
2//ee
where Q
6(I, Wh
k.Ja.
Note that
(lh(1, 50, ((,,))
= - ((, e
(48)
=1 =I-P(lladjsxxA (m, + PP,
37

---

Published as a conference paper at ICLR 2024
Now,
P (3(z,a) E S x A Q (z) S
P ((I,a) ESxA: max Q ph (r, + +PAVitz
mEiM]
= PP (3),)) E A: Vm E [M]; (2, S (m( + PA V h+ (2,,
< IP
Vm [M], [mm: 0m) E A: Qh, kmm (Im, rr (I am) + Ph Vh+z (1mm (m))aa))
II ((2 E SxA: (z, <m(,,a) PA m=1 M
II m=1
(1 P Qhh (I, (0h:((r,aa)
M
2veen
HK'
where the last inequality follows from 47
Thus, from (88) we have
8
P (( v(r,a) 2 HK'
Denoting c
and solving for M, we have M log H 8/8) log(11(( c))
2v
Applying union bound over and k. v(z, a) E S x A and v(h, k)) E [H] x [K].with probability 1 - 6, we have, (2r, O. This completes the proof.
D.3 REGRET ANALYSIS OF MS-LMC-LSVI
Theorem D.6. Let = 1 in 4 Dy = Ö(H For any k E [K], let the learning rate TJs
1/(4Amax (AH)), the update number Ju = 2n log( (4/ (4H where KR = Amax (mnx((At)/) Amin (A/) is the condition number of Ar. For any 5 (0, let M loolloH///O (oog(1((100)) where 2v/en
Under Definition 4.1 the regret of MS-LMC-LSVI satisfies
Regret(K)
with probability at least 1 1 5.
Proof of Theorem D.6 The proof is essentially same as that Theorem B.8 The only difference is
in computing the probabilites while applying union bound. Nevertheless, we highlight the key steps.
We use the same regret decomposition from (22) We bound the term (i), (ii) and (iii) in (12) exactly
in the same way in the proof of Theorem B.8 and thus with probability 28/3, we have
K
Mi 22/2222 (og(38))
(49)
Now we bound term (iv) in I2). Suppose the event E(K, H, M, 8') defined in Lemma D.3
holds.
Using Lemma D.4 and Lemma D.5 with union bound, similar to the proof of Theorem B.8 show that with probability (d' + d'), we have
we can
K
H
E (T,, an) a1 = 2t9 - - a = /T).
(50)
k=
38

---

Published as a conference paper at ICLR 2024
By Lemma D.3 the event (K, H,M, M, 8') occurs with probability 1 1 8'. By union bound the event (KK H. M occurs and (50) holds with probability at least (8"2 + + 8'). As E (0,1),
setting 8' 6/9, we have 1 - 8 + 8' + 8') 2 1 36' = 1 -1-66 6/3.
Applying another union bound over the last incquality and the martingale incqualities from 449 we have, the regret is bounded by O(d5/2 H3/2 /T) with probability at least 1 - and this completes the proof.
E AUXILIARY LEMMAS
E.1 GAUSSIAN CONCENTRATION
In this section, we present some auxiliary technical lemmas that are of general interest instead of closely related to our problem setting.
Lemma E.1. Given a multivariate normal distribution X ~ N(0, Edxa), we have,
|xlla s V Tr(E) 1 2
E.1 From the properties of multivariate Gaussian distribution, X = E2//2g for & ~ (0, Taxa). As 21/2 is symmetric, it can be decomposed as E1/2 = QAQT, where Q is orthogonal and A is diagonal. Hence,
Proof of Lemma
P (1 S C²) = P = (I =
=
since orthogonal transformation preserves the norm. Another property of standard Gaussian distri- bution is that it is spherically symmetric. That is, Q & for any orthogonal matrix Q. So,
IP (IAQ E112 S 02) IP (1AAI1 C²)
as Q is also orthogonal. Observe that ||AE|12 = Σi= APE? is the sum of the independent x distributed variables with E (1ΛET12) = Σi= 2, = Tr((3) = Σín Var(X.). From Markov's inequality.
11AEE12 S $0²)
21 e (1AE113)
So.
8 C E (1AE12) +C=
1
Var(X.) - mT(),
which completes the proof.
Lemma E.2 (Abramowitz and Stegun 1964)). Suppose Z is Gaussian random variable Z N(,,o²), where o > O. For 0 < <
we have
1
P(Z > n + 20) 2
P(Z < < p-p-pp0 < 2
88
8
And for 2 1, we have
2222/2 /2
--
SP(IZ
11 > 20 5
22
2 /
E.2 INEQUALITIES FOR SUMMATIONS
Lemma E.3 (Lemma D.I in Jin et al. (0200). Let An = XI + Eie dieTT where di E Rd and
O. Then il holds that
07 (AA)) S d. Σ
39

---

Published as a conference paper at ICLR 2024
Lemma E.4 (Lemma 11 in Abbasi- Yadkori et al. (2011)). Using the same notation as defined in this paper
K
Σ
ax) l(Aaa S 2d
A + K
Lemma E.5 (Lemma D.5 in Ishfaq et al. (2021)) Let A E Raxdd be a positive definite matrix where
its largest eigenvalue Amax () X. Let 01,.... 3.k be vectors in TRo. Then it holds that
1/2
Ak
Σ | l13
E.3 LINEAR ALGEBRA LEMMAS
Lemma E.6. Consider two symmetric positive semidefinite square matrices A and B. If 2 B, then |All2 2 |B
Proof of Lemma E.6 Note that A - B is also positive semidefinite. Now,
||B||2 sup x Br S sup ||]|=1
Br + x (A B)z) sup T Ax ||A||2. (x Bx
(51)
||||==1
||
This completes the proof.
Lemma E.7 HHom and Johnson 2012)). If A and B are positive semi-definite square matrices of the same size, then
0 S [T((B)]] < Tr(4²) TT(AA)T((B*) < (TT))))
E.4 COVERING NUMBERS AND SELF-NORMALIZED PROCESSES
Lemma E.8 (Lemma D.4 in Jin et al. (020)). Let {
stochastic process on state space with corresponding filtration {Fi) Let { be an Rdd-vllued stochastic process where di E F;-1, and [|>:|| < 1. Let A = Al + E PiO T. Then for any ō > 0, with probability at least 1 - for all k O, and any V V with sup.es [V(s) < H, we have
* Σ - ((V(s)) F-Lll 1=1
d
1: *+
No
8k262
[[V(s))
411
log
+ log
+
A
6
A
where Ne is the s-covering number of V with respect to the distance dist( V, V) sup (V(s) V'(s)).
Lemma E.9 (Covering number Euclidean ball, Vershynin (2188) ). For Forann e 0, the e-covering
number, No. of the Euclidean ball of radius B > 0 in I8 satisfies
N₂ < (1 2B44
2B d 3B
Lemma E.10. Let V denote a class of functions mapping from S to lR with the following parametric form
[0))=in|//m min max ol a)T H v(-)
aEA
where the parameter t satisifies || & and for all (x. a) E S x A. we have [| a) S Let Nv.s be the s-covering number of V with respect the distance dist(V, V sup, V VVx) -V(()) Then
log Ny.c S dogg (1 2B/e) dog (3B/e).
40

---

Published as a conference paper at ICLR 2024
Proof of Lemmal E.10
Consider any two functions V1, V2 V with parameters wi and wy respec- tively. Since both ( H} and max, are contraction maps, we have
dist(V1 (V1, V2) s sup d( a) T w1 0(x, a) w22
x,a
< sup
1o W1 - -Juul w2l
d
1 (w) w2)
(52)
sup
d:|lel|s1
sup || w2 11
d:
S w1 wall
Let Ne. denote the e-covering number of {w E IRd
||m|| S B). Then, Lemma E.9 implies
2B
3B
No.: I 1
Let Cw.e be an E-cover of {w E Rdd V2 parameterized by w2 satisfies dist 11, 1/2 S &. Thus, we have,
||w|| < B}. For any V1 E V, there exists We E Cw.e such that
log Nv.c S log Nw.. S dloog(1 + 2B/e) s dlog(3B/e).
which concludes the proof.
Lemma E.11. Let V denote a class of functions mapping from S to IR with the following parametric form
max ((,aa) wtt w"T,. 3
(-) max min
aEA
(m[MM]
where the parameter nh satisifies ||wn have [ < 1. Let Nv.o be the s-covering number of V with respect to the distance disi(V V') sup, (vx) V'())) Then
< B for all m E [M], and for all (r,,a) E S x A.
log Nv.e S dM log (1 + 2B/s) S dM log (3B/s).
Proof of Lemma E.17
The proof is analogous that of Lemma E.10 We provide the detailed proof
for completenes.
Consider any two functions V1, V/2 V with
Vi max min aEAA
max a) Tu H mm|M
and
(.,a))'"" max @(, a)) "2 11 M
1/2 max min aEAA
Since both minf., H} and max, contraction maps, have
dist(Vi, V22 < sup
max Ó(I, a) "TT" max 6(I, a) "w""
a.a mE[a]]
ME[M]
max o " mc(M] mE(M]
sup
di lolls1
(53)
< sup
max |1 - w ||
di (ell
ME
max |ww" w.
mE[M]
41

---

Published as a conference paper at ICLR 2024
Random MDPs: best run
50
Episode Return
30
20
OPPO
10
LSVI-PHE
LMC-LSVI
0
LSVI-UCB
5
6 X 102
Training Episodes
Figure 4: Comparison of LMC-LSVI, OPPO (Cai al. 2020), LSVI-UCB (Jin et al. 2020) and LSVI-PHE (Ishfag et al. 2021) in randomly generated non sta-stationary linearly parameterized MDPs with 10 states, actions, horizon length H 100 and sparse transition matrix.
For any m [M]. let (m an e-cover of (w E RRd | || By Lemma E.9 know,
B} with respect to the 2-norm.
2B d I
3B
cTTl < 1
holds that y $ I |cm]. Thus, we have,
M
log Nv.s log II m=1
dM log(1 + +B/e) s dM AMMo3/B//e)
which concludes the proof.
F EXPERIMENT DETAILS
In this section, first, we provide experiments for LMC-LSVI randomly generated linear MDPs and the riverswim environment (Strehl and Littman 2008 Osband et al., 2013) and compare against provide more implementation
provably efficient algorithms designed for linear MDPs. Then, details about experiments in N N-Chain and Atari games. In total, all experiments (including hyper- parameter tuning) took about GPU (V100) years and 20 CPU years.
F.1 EXPERIMENTS FOR LMC-LSVI
F.1.1 RANDOMLY GENERATED LINEAR MDPs
In this section, use randomly generated non-stationary and linearly parameterized MDPs with 10 states, 4 actions, horizon length of = 100 and a spares transition matrix. As a training setup, use 4 randomly generated linear MDPs. For each MDP, we use 5 seeds for total of 20 runs per hyperparameter combination. Figure we compare our proposed LMC-LSVI against OPPO
(Cai et al. 2020), LSVI-UCB (Jin al. 2020 and LSVI-PHE (Ishfaq et al. 2021
42

---

Published as a conference paper at ICLR 2024
F.1.2 THE RIVERSWIM ENVIRONMENT
In the Riverswim environment, there are N states which are lined up in a chain. Figure depicts the case when N 6. The agent begins in the leftmost state 81 and in each state can take one of the two actions- "left" or "right". Swimming to the left, with the current, deterministically moves the agent to the left while swimming to the right against the current often fails. The optimal policy is to swim to the right and reach to the rightmost state 8.. Thus, deep exploration is required to obtain the optimal policy in this environment. We experiment with the variant of RiverSwim where
N 12 and H 40. We use LSVI-UCB (Jin et al., 2020). LSVI-PHE (Ishfaq et al. 2021). > OPPO
(Cai et al. 2020) and OPT-RLSV (Zanette et al. (020a) as baselines. As shown in Figure 6a LMC- LSVI achieves similar performace LSVI-UCB and outperforms other baselines. Figure shows the performance of LMC-LSVI as we vary the update number Jn. As we see, even with a relatively small value of JR, LMC-LSVI manages to learn near-optimal policy quickly.
0.6
0.6
0.6
0.35
0.35
0.35
0.35
(1,r 1000
81
0.05
0.05
83
0.05
0.05
0.4
(0.6,
Figure 5: The state RiverSwim environment from Osband et al. (2013). Here, state 81 has a small reward while state š6 has large reward. The dotted arrows represent the action "left" and deterministically move the agent to the left. The continuous arrows denote the action "right" and move the agent to the right with relatively high probability. This action represents swimming against the current, hence the name RiverSwim.
F.2 N-CHAIN
There are two kinds of input features 1hh = (1fx: sx}) and Othem (s:) (1fx S s,}) in [0. 1) Osband et al. (2016b) found that @therm (8t) has lightly better generalization. So following Osband et al. (2016b), we use @therm (8+) as the input features.
For both DQN and Adam LMCDQN, the Q function is parameterized with multi-layer perceptron (MLP). The size the hidden layers in the MLP is [32, 32]. and ReLU is used as the activation function. Both algorithms are trained for 10a steps with experience replay buffer of size 10 We measure the performance of each algorithm by the mean return of the last 10 test episodes. The mini-batch size is 32, and update the target network for every 100 steps. The discount factor 0.99.
DQN is optimized by Adam, and do hyper-parameter sweep for the learning rate with grid search. Adam LMCDQN is optimized by Adam SGLD with (n = 0.9, 02 0.99, and x = 10-8 For Adam LMCDQN, besides the learning rate, also sweep the bias factor a, the inverse temperature 3k, and the update number Jg. We list the details of all swept hyper-parameters in Table
Table 2: The swept hyper-parameter in N V-Chiin.
VALUES
LEARNING RATE 7 BIAS FACTOR
(10-1,3x 1 10-22 3 x 10-3 10 3,-3,3 x - 10-4) {1.0, 0.1, 0.01]
INVERSE TEMPERATURE 3R UPDATE NUMBER Jr
1101 10 10t2 10t0 10*)
[1. 16, 32
43

---

Published as a conference paper at ICLR 2024
Riverswim 12: best
Riverswim 12- LMC-LSVI:
Episode Return
Episode Return
un 9.
*
Bacine 1ST
IMC-EVV
Reastrne
1
SVT-
2.00
1.75
Training Episodes
x 10
Training Episodes x10*
(a) Episode returns for best runs
(b) Episode returns for different J+
Figure 6: Experiment in the Riverswim environment [Strehl & Littman, 2008] with chain length 12. (a) Mean episode returns for best runs, after hyperparameter optimization. (b) Mean episode returns for different values of Jg LMC-I-SVI.
r
1000
81
82
8N-1
SN
Figure 7: N-Chain environment Osband et al. 2016b).
F.3 ATARI
F.3.1 EXPERIMENT SETUP
We implement DQN, Bootstrapped DQN, Noisy-Net and Adam LMCDQN with tianshou framework (Weng et al. 2022). For the other five baseline algorithms, we take the results from DQN Zoo (Quan) and Ostrovski 2020 Both DQN and Adam LMCDQN use the same network structure, following the same observation process as in Mnih et al. (2015). To be specific, the observation is 4 stacked frames and reshaped to (4, 84, 84). The raw reward is clipped {-1, 0, +1} for training, but the test performance is based on the raw reward signals.
Unless mentioned explicitly, we use most of the default hyper-paramene parameters from tianshou's DQN D For each task, there is just one training environment to reduce the exploration effect of training in multiple environments. There are test environments for robust evaluation. The mini-batch size is 32. The buffer size is 1M. The discount factor is 0.99.
For DQN, we use the e-greedy exploration strategy, where decays linearly from 1.0 to 0.01 for the first LM training steps and then is fixed 0.05. During the test, set 0. The DQN agent is optimized by Adam with a fixed learning rate 10-4
For our algorithm Adam LMCDQN, since large Js significantly increases training time, so we set Ju = so that all experiments can be finished a reasonable time. The Adam LMCDQN agent is optimized by Adam SGLD with learning rate 7) 10-4, 0g 0.9, d2 0.99, and X 10 88 We do a hyper-paramete sweep for the bias factor a and the inverse temperature 3t, as listed in Table 3
dqn.py py
44

---

Published as a conference paper at ICLR 2024
Table 3: The swept hyper-parameter Atari games.
HYPER-PARAMETER
VALUES
BIAS FACTOR a INVERSE TEMPERATURE 3r
01.0,0.1,00 0.01) {10%,, 10 10
F.3.2 ADDITIONAL RESULTS
Our implementation of Adam LMCDQN applies double networks by default. In Figure 8 compare the performance of Adam LMCDQN with and without applying double Q functions. The performance of Adam LMCDQN is only slightly worse without using double Q functions, prov- ing the effectiveness of our approach. Similarly, there is no significant performance difference for Langevin DQN (Dwaracherla and Van Roy 2020) with and without double Q functions, as shown in Figure
Alen
Freeway
Coev
H.E. H.E.R.O..
1000
15000
10300
Retum
9000
630
10
200
0-
0-
0-
5:00
-0
250
-5000
FR
Q"bert
Solars
Venture
200
20000
1000
-200
000
-030
-20000
0-
20
40
10
20
40
20
30
Fiama (millioss)
Frame (miillons))
Frame ((illons))
Frame (milliora)
LMCDON
Q)
Adam (wo,
Figure 8: The return curves of Adam LMCDQN in Atari over 50 million training frames, with and without double functions. Solid lines correspond to the median performance over random seeds, while shaded areas correspond to 90% confidence interval. The performance of Adam LMCDQN is only slightly worse without using double Q functions, proving the effectiveness of our approach.
Allen
Freeway
Gravitar
H.E.R.O.
2530
10000
1030
500
-10
-202
-2900
OThert
Spaae
Ventume
5000
600
200
102
400
20
30
90
30 Frome (millions)
20
40
13
50
40
10
20
40
63
Framte (million))
Fromb (m (millions)
Frome (millionn))
Langevnn
Langewin (wo
Figure 9: The return curves Langevin DQN in Atari over 50 million training frames, with and without double Q functions. Solid lines correspond to the median performance over 5 random seeds, while shaded areas correspond to 90% confidence interval. There is no significant performance improvement by applying double Q functions in Langevin DON.
Moreover, also compare Langevin DQN with algorithm Adam LMCDQN in Figure 10 Both algorithms incorporate the double Q trick by default. Overall, Adam LMCDQN usually outperforms Langevin DQN in sparse-reward hard-exploration games, such Gravitar, Solaris, and Venture,
45

---

Published as a conference paper at ICLR 2024
while in dense-reward hard-exploration games, such as Alien, H.E.R.O and Qbert, Adam LMCDQN and Langevin DQN achieve similar performance.
Freeway
3300
1000
15000
2303
770
10000
500
0000
-1000
-10
-200
-5000
Q'bort
Solarts
Venture
402
20000
2000
1600
202
15000
1500
1000
500
-007
0-
-503
-5000
-000
-000
20
20
Frome (milloon))
Fromm (million))
Frame (m (ionn)))
Frame (milloon))
Acem LSCDDNN
DCN
Figure 10: The return curves of Adam LMCDQN and Langevin DQN in Atari over 50 million training frames. Solid lines correspond to the median performance over 5 random seeds, while shaded correspond to 90% confidence interval.
46


Reviews:
[{"review_id": "djsa05WDMT", "reviewer": "Reviewer_yHqj", "summary": "The paper studies usefulness of LMC algorithms for MDPs. It first shows an LMC algorithm deployed with LSVI for linear MDPs and upper bounds the corresponding regret. It also proposes versions of LMC used with Adam and DQN for practical purposes. The performance of the practical algorithm is illustrated on multiple atari games.", "questions": "Please check the weaknesses for questions .", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The paper proposes a regret upper bound for applying LMC with LSVI for linear MDPs.\n2. The paper proposes a practical version of LMC to be applied with DQN. It works in practice as shown through multiple experiments.", "weaknesses": "1. The theoretical analysis is shown for linear MDPs and the practical algorithm is applied with DQN. Thus, the theory and applications serve two different purposes and does not compliment each other. It makes the paper look like an assortment of results for different settings than a coherent study.\n2. If the aim is to design a practical algorithm, why analysing it for linear MDPs, which is known to be unfit for practice (the version stated in the paper) [1]? Why not analysing it for more practical models like [1], [2], [3]?\n3. The regret bound for LMC lsvi is loose in terms of both d and H. Why is it so? Is it due to any fundamental hardness in analysis or inherent to LMC algorithms or just a shortcoming of the analysis done in the paper? Can you explain this?\n4. The practical version is claimed to be better than the existing LMC algorithm for RL cause the proposal has theoretical guarantees and also employs better practical techniques. The first is not completely valid as the setting plus algorithm for analysis and practice are really different. The second is also not clear as the experimental results leave the question of performance improvement statistically inconclusive . Can you provide a reason where adam LMC DQN would work better than langevin DQN and where it would be worse?\n\n[1] Zhang, Tianjun, Tongzheng Ren, Mengjiao Yang, Joseph Gonzalez, Dale Schuurmans, and Bo Dai. \"Making linear mdps practical via contrastive representation learning.\" In International Conference on Machine Learning, pp. 26447-26466. PMLR, 2022. \n[2] Ouhamma, Reda, Debabrota Basu, and Odalric Maillard. \"Bilinear exponential family of MDPs: frequentist regret bound with tractable exploration & planning.\" In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 37, no. 8, pp. 9336-9344. 2023.\n[3] Weisz, Gellért, András György, and Csaba Szepesvári. \"Online RL in Linearly $ q^\\pi $-Realizable MDPs Is as Easy as in Linear MDPs If You Learn What to Ignore.\" arXiv preprint arXiv:2310.07811 (2023).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Q8k4x1yIS2", "reviewer": "Reviewer_SrMF", "summary": "They have introduced online RL algorithms incorporating Langevin Monte Carlo. \n\n   *They have established the regret bound for Q-learning with Langevin Monte Carlo under linear MDPs. \n\n   *They have adapted the aforementioned algorithm to use the ADAM optimizer, demonstrating its favorable empirical performance through experiments.", "questions": "I raised several concerns for the weakness section.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "While the literature on Bayesian model-free algorithms is extensive, it is indeed lacking in works that offer both robust theoretical guarantees and practical viability. In my view, this paper effectively bridges this gap. \n\n* The paper presents a good comparison, highlighting noteworthy contributions compared to existing works.\n\n* Section 3 offers a non-trivial and novel analysis that significantly enhances the paper.\n\n* The practical version's experimental results in Section 5 demonstrate promising performance.", "weaknesses": "* It looks Algorithms they use in practice (Algorithm 2) are not analyzed. So, this algorithm is \"practical\", but I am not sure it is fair to say this is \"provable.\" \n\n* Some aspects of the comparisons appear to lack complete fairness.\n\n   * In Table 1, it is unclear what precisely the author intends to convey with \"computational traceability\" and \"scalability.\" These terms should be defined more formally in the caption of the table. \n\n   * Furthermore, it may not be entirely fair to say that OPT-RLSVI and LSVI-PHE lack scalability in Table 1. While I acknolwedge that the proposed algorithms (OPT-RLSVI and LSVI-PHE) may not perform well in practice, one could argue that they could exhibit scability with the incorporation of certain simple heuristics, even if formal guarantees are absent. Indeed, the LSVI-PHE paper includes moderate experiments. The author has similarly extended theoretically justified algorithms to practical versions without formal backing as they did. So, in this sense, I am not sure why it is reasonable to say the author's algorithm is scalable, but their algorithms are not scalable.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9REDoQRQwx", "reviewer": "Reviewer_dAXr", "summary": "The paper is about online RL algorithm design and theoretical analysis. Different from most previous RL theory works which lack deep RL demonstrations, this work proposes a both practical (scalable to deep RL domains) and provably efficient online RL algorithm (LMC-LSVI) based on the celebrated Langevin Monte Carlo algorithm. Theoretically, it proves that with linear function approximation LMC-LSVI achieves a $\\widetilde{\\mathcal{O}}(d^{3/2}H^{5/2}T^{1/2})$-online regret. On the practical side, LMC-LSVI is further extended to the Adam LMCDQN algorithm which performs similarly or even better than SOTA explorative deep RL algorithms in some challenging RL domains.", "questions": "1. Regarding the theoretical analysis (Theorem 4.2), I am curious why the failure probability $\\delta$ must be larger than a certain quantity, say $1/(2\\sqrt{2e\\pi})$? Is this inevitable for a sampling-stype algorithm and analysis? This will narrow the applicability of the theory since for frequentist regret analysis we always hope that the regret bound can hold for arbitrarily small fail probability.\n2. The authors say in the contribution part that \"unlike any other provably efficient algorithms for linear MDPs, it can easily be extended to deep RL settings\",..., \"such unification of theory and practice is unique in the current literature of both theoretical RL and deep RL\", which to my knowledge is overclaimed. Even though the perspective of Langevin dynamic are less explored in this regime, which is done by this paper, there do exist other works trying to achieve sample efficiency while being compatible with practical deep RL methods, e.g., [1, 2, 3]. So it seems improper to describe the work as unique given this line of research.\n\n**References:**\n\n[1] Feng, Fei, et al. \"Provably Correct Optimization and Exploration with Non-linear Policies.\" *International Conference on Machine Learning*. PMLR, 2021.\n\n[2] Kitamura, Toshinori, et al. \"Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practice.\" *International Conference on Machine Learning*. PMLR, 2023.\n\n[3] Liu, Zhihan, et al. \"One Objective to Rule Them All: A Maximization Objective Fusing Estimation and Planning for Exploration.\" *arXiv preprint arXiv:2305.18258* (2023).", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Bridging the gap between RL theory and practice is of great importance to the advance of RL research. This work gives a possible and positive answer to this question in the specific setting of online RL where exploration-exploitation balance is a key problem. \n2. The proposed  Langevin Monte Carlo Least-Squares Value Iteration (LMC-LSVI) algorithm turns out to have a quite clean form which simply adds a noise term to the gradient descent update of the Bellman error (Line 9 of Algorithm 1) to incentivize exploration. This advantage thus allows for a deep RL extension where Adam-based adaptive SGLD is further applied.\n3. The proposed algorithm enjoys theoretical guarantees (in the linear function approximation setting) which is missing in most previous deep RL exploration methods even for LFAs.", "weaknesses": "The rate of the online regret in linear function approximation setting is far from tight compared with known lower bounds. But from my view this is understandable given that a new approach is derived whose practicability is of higher importance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)