Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximation
Authors: Nikki Lijing Kuang
Ming Yin
Mengdi Wang
Yu-Xiang Wang
Yian Ma
Venue: NeurIPS 2023 poster (2023)
Keywords: Posterior Sampling
Reinforcement Learning Theory
Linear Markov Decision Processes
Delayed Feedback
Langevin Monte Carlo
TL;DR: We provide the first analysis for the class of PS algorithms to handle delayed feedback in RL frameworks.

Abstract: Recent studies in reinforcement learning (RL) have made significant progress by leveraging function approximation to alleviate the sample complexity hurdle for better performance. Despite the success, existing provably efficient algorithms typically rely on the accessibility of immediate feedback upon taking actions. The failure to account for the impact of delay in observations can significantly degrade the performance of real-world systems due to the regret blow-up. In this work, we tackle the challenge of delayed feedback in RL with linear function approximation by employing posterior sampling, which has been shown to empirically outperform the popular UCB algorithms in a wide range of regimes. We first introduce \textit{Delayed-PSVI}, an optimistic value-based algorithm that effectively explores the value function space via noise perturbation with posterior sampling. We provide the first analysis for posterior sampling algorithms with delayed feedback in RL and show our algorithm achieves $\widetilde{O}(\sqrt{d^3H^3 T} + d^2H^2 \mathbb{E}[\tau])$ worst-case regret in the presence of unknown stochastic delays. Here $\mathbb{E}[\tau]$ is the expected delay. To further improve its computational efficiency and to expand its applicability in high-dimensional RL problems, we incorporate a gradient-based approximate sampling scheme via Langevin dynamics for \textit{Delayed-LPSVI}, which maintains the same order-optimal regret guarantee with $\widetilde{O}(dHK)$ computational cost. Empirical evaluations are performed to demonstrate the statistical and computational efficacy of our algorithms.

Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximation
Nikki Lijing Kuang
Ming Yin
Mengdi Wang Princeton University
University of California, San Diego 1 1kuanguussd.cem edu
Princeton University my0049@princeton. edu
mengdiv@princeton edu edu
Yu-Xiang Wang
Yi-An Ma
University of California, Santa Barbara yuxiangwecs wus.b.u..eee
University of California, San Diego
yianmaQucsd.edd edu
Abstract
Recent studies in reinforcement learning (RL) have made significant progress by leveraging function approximation alleviate the sample complexity hurdle for better performance. Despite the success, existing provably efficient algorithms typically rely on the accessibility of immediate feedback upon taking actions. The failure to account for the impact of delay in observations can significantly degrade the performance of real-worle systems due to the regret blow-up. In this work, we tackle the challenge of delayed feedback in RL with linear function approx- imation by employing posterior sampling, which has been shown to empirically outperform the popular UCB algorithms in a wide range of regimes. We first intro- duce Delayed- PSVI, an optimistic value-based algorithm that effectively explores the value function space via noise perturbation with posterior sampling. We pro- vide the first analysis for posterior sampling algorithms with delayed feedhack RL and show our algorithm achieves O(vd' H3T + d H²E(T]) worst-case regret in the presence of unknown stochastic delays. Here E[r] is the expected delay. To further improve its computational efficiency and to expand its applicability in high-dimensional RL problems, incorporate gradient-based approximate sampling scheme via Langevin dynamics for Delayed-LPSVI, which maintains the same order-optimal regret guarantee with ()HHK computational cost. Em- pirical evaluations are performed demonstrate the statistical and computational efficacy of our algorithms.
Introduction
Reinforcement Learning (RL) is the main workhorse for sequential decision-making problems where an agent needs to balance the trade-off between exploitation and exploration in the unknown environ- ment. The flexible and powerful function approximation endowed by deep neural networks greatly contributes to the empirical success of RL domains such as Large Language Models (LLMs) [50, 59], robotics [51 I], and AI for Science [37]. In general, collecting real-world training data from such practical systems can be expensive, which requires algorithms to be both sample efficient and computationally efficient. Recently, there have been growing efforts towards studying provably effi- cient RI. algorithms settings ranging from tabular Markov Decision Processes (MDPs) [29, 45, 69] to large-scale RL with function approximation [13, 35]. However, these algorithms typically rely
"Equal contribution.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

on the availability of immediate observations of states, actions and rewards in learning no-regret policies. Unfortunately, such an assumption rarely satisfied in real-world domains, where delayed feedback is ubiquitous and fundamental. In recommender systems and online advertisement, for instance, responses from users (e.g. click, purchase) may not be immediately observable, which can take hours or days. In healthcare and clinical trials, medical feedback from patients on the ef- fectiveness of treatments can only be determined at a deferred time frame. More examples exist in platforms that involve human interaction and evaluation, including human-robot collaboration in teleoperating systems and multi-agent systems [15, 39), aligning LLMs with human values [50, 63], and fine-tuning generative AI models using RL with human feedback (RLHF) [11, 41].
Despite the practical importance of addressing delays in decision-makinn problems, theoretical un- derstanding of delayed feedback in RL remains limited. Recent parallel works study exploration under delayed feedback via upper confidence bound (UCB) algorithms [8] in tabular RI. [29, 45], adversarial MDPs [36, 40], and RI. with low policy-switching scheme [68] (see Table 1). Never- theless, posterior sampling (PS) analysis that handles delayed feedback remains untackled in both bandit and RL literature. We aim to bridge the gap in this work.
PS is a randomized Bayesian algorithm that extends Thompson sampling (TS) [57] to RL, which selects an action according to its posterior probability of being the best. This philosophy inspires a number of promising exploration strategies that explicitly or implicitly adopt PS explore [52], including bootstrapped DQN [42, 47] and RLSVI [49]. Compared to the popular UCB algorithms, it bears greater robustness in the presence of delays [14], and provides exceptional computational effi- ciency with competitive empirical performance [1 [14, 65]. The fact that posteriors are often intractable in practice necessitates the use of approximate Bayesian inference such as ensemble sampling, vari- ational inference (VI) and Markov Chain Monte Carlo (MCMC) [20, 38, 47].
In this paper, we provide the first analysis for the class of PS algorithms that handles delayed feed- back in RL frameworks, in which the trajectory information is randomly delayed according to some unknown distribution. We highlight that delayed feedback model imposes new challenges that do not arise in standard RL settings. Algorithmically. it requires the computation of new posterior variance due to the weaker concentration arising from delays. Theoretically, it complicates the fre- quentist analysis of PS algorithms in several ways: (a) the lack of timely update in posterior learning can cause distribution shift, especially the case of approximate sampling: (b) delays need to be carefully disentangled to quantify the penalty in regret decomposition and it prohibits the direct ap- plication of previous analysis; (c) balance between concentration and anti-concentration needs to be handled deliberately to achieve sub-linear regret.
To tackle these challenges, we introduce two novel value-based algorithms for linear MDPs under unknown stochastic delayed feedback. Developed upon Bayesian linear modeling with a multi- round ensembling mechanism (M Polylog (H, K, d, 8) round), our algorithms achieve a sub- linear worst-case regret without requiring the knowledge of delay, thereby addressing the question raised in [60] that "No frequentist analysis exists for posterior sampling with delayed feedback". Empirical studies show that our algorithms outperform (CB-based methods in terms of both statis- tical accuracy and computational efficiency when delays are well-behaved or even long-tailed. We summarize our main contributions as follows.
We propose the Delayed Posterior Sampling Value Iteration (Delayed-PSVI, Algorithm 1) for linear MDPs. achieves a nigh-probability worst-case regret of H(v + d2 ( where [E(T] is the expected delay.
We leverage Langevin Monte Carlo (LMC) for approximate inference and introduce De- layed Langevin Posterior Sampling Value Iteration (Delayed-LPSV) Algorithm 2), which maintains the same order-optimal worst-case regret of Ō ((vá d H + d H² To the best of our knowledge, this is the first analysis that provably incorporates LMC in lincar MDPs and jointly considers the impact of delays.
Both algorithms achieve the optimal dependence on the parameters d and T in leading terms under the class of PS algorithms, and recover the best-available frequentist regret of σ(v ( H3T) [31, 72] in non-delayed linear MDPs when R[[]] 0. In particular, Delayed-LPSVI reduces the computational complexity of Balayed-PSVV from Ö(d
ltt provides a stronger guarantee opposed to the weaker worst-case expected regret and Bayesian regret.

---

to ((dHK), expanding the applicability in complex figh-dimensional RL tasks while po- tentially providing more flexible form of approximation.
Algorithms
Setting
Exploration
Worst-case Regret
Computation
[28]
Lineur Bandits
UCB
O &
Confidence sei optimization
[29]
Tabular MDPs
UCB
Ö(VSAR*T + BTD
Active update
[68]
I Linear MDPs
UCB
Öly F(T)
Multi-batch reduction
[40]
Adversorial MDPs
UCB
OUA'SAK H SI
Confidence set optimization O(id Md)BK)
Delayed-PSVI (Thm
Linear MDPs
PS
Ö 6' <E
Delayed-1.PS (Thm 2)
Linear MDPs
PS
ÖLVENPT of
O((N dуMик))
Delayed-PSI PSLB (Car 2)
Linear Bandits
PS
Ö(veT + d
O((N + d)MK)
UCB Lower bound [27]
Lincar MDPs
UCB
(ddyTT)
Lower [24]
Linear Bandits
Q(vaTT)
Table I: Summary of regret bounds in linear bandits and episodic MDPs under stochastic delay. We denote by T' the time horizon, K the number of episodes, H the episode length, the dimension of feature space, M the number of sampling rounds, and N the total iterations in running LMC. Our choice of M and N has order of Polylog(H, d, 8); ensuring hoth Delayed-PSVI and Delayed-I.PSVI are computationally efficient and statistically sample-efficient. We remark that the gap in the frequentist regret between P$ and best UCB- based methods unavoidable by factor of vá [24]. Thus, our dependencies on d and are optimal the class of PS algorithms. Our results fulfill the caveat [60] that no worst-case analysis exists for PS with delay.
1.1 Related Work.
Delayed feedback. In bandit literature, delay is extensively studied in both stochastic [22, 56, 60, 77] and adversarial settings [32, 58, 78] for UCB-based methods. In comparison, while delay draws much attention in empirical RL studies [12. 17, 18], there is a lack of theoretical understanding until very recently. Parallel works focus on UCB-based methods in various RL settings [16, 28, 36, 40, 45, 68]. To provide the first analysis for PS algorithms in this context, we consider stochastic delays under linear function approximation without requiring any policy-swind scheme in [68].
Posterior sampling. To encourage efficient exploration, PS is adopted in value-based methods to inject randomness in empirical Bellman update via Gaussian noise. From the Bayesian perspective, it is equivalent to maintaining an approximate Gaussian posterior for parameterized value function. Its sample complexity is studied in tabular settings [48, 49, 53), with the sharp worst-case regret of ((H2SVAT) [5]. Under linear function approximation, frequentist regret of ((VDHTT) [31, 72] and Bayesian regret of ((d HHT) [19] are established. However, in complex problem domains that require higher computational efficiency and more refined surrogates, approximate inference is the remedy. Toward this end, we resort to gradient-
MCMC method.
Langevin Monte Carlo. LMC is class of MCMC methods tailored for large-scale online learning with strong convergence guarantee by utilizing the first-order gradient information [64]. has been successfully applied to stochastic bandits [43], linear bandits [65] and tabular RL [38]. In this work, we extend its usage in linear MDPs and demonstrate its convergent property under delay.
RL with Function Approximation. Function approximation is widely adopted to empower RL for large-scale applications. Fruitful results have been established for regret minimization in two types of MDPs under linear function approximation: linear mixture MDPs [9, 67]. and linear MDPs [35, 66]. In linear mixture MDPs where transition kernel parameterized as a linear combination of base models, provably efficient algorithms are discussed [13, 75, 76] and [75] provides the corresponding lower bound of Q(dH VT). In contrast, linear MDPs enjoy a linear structure in value functions by assuming a low-rank representation for both transitions and reward function, where algorithms are shown to enjoy polynomial sample complexity [27, 35, 62, 73]. When it comes to general function approximation, theoretical guarantees are developed based on measures of cluder dimension [54, 61] and Bellman rank [33]. In this work, we focus delayed feedback in linear MDPs.
2 Preliminaries
We study the finite-horizon episodic MDP (S, H.,, r), which time-inhomogeneous, and de- note by S. A the state and action spaces respectively, H the episode length, IP {IPx H the
3

---

transition dynamics, and r frr reward function. At each step h E [H], Ph: S x A - As specifies the probabilities of transitioning from the current state-action pair into the next state, and rh S x A + [0, 1] emits a bounded reward. We adopt the prior protocol of linear MDPs as follows.
Definition 1 (Linear MDPs [35, 66]). Suppose there exists known feature map 6 : 8 A - R that encodes each state-action pair into d-dimensional feature vector. An MDP is a linear MDP for any time step [M], V(s,a) ES x A. both the transition dynamics IP and reward function r are linear in o:
Pa(-1s,)) a) = ó(s a) pn()), ra(8,a) 6(s,a) a)=
(1)
where Pb : :S + Id contains d unknown probability measures over S, and 6n ER.. Furthermore, we assume that V(s, a) ESS A, (l a)ll S 1, and vh E ||,, S vd. IISs dun(s')l s Vd, where ||-|] denotes the Euclidean norm.
A non-stationary policy л ) assigns the action to take at step l in state 8n E S. Accord- ingly, we define the value functions of a policy æ as the expected rewards received under m
()) Ex - mee = 8, a (8) = Ex _ |
We further denote by x² the optimal policy whose value functions are defined (s) V (s) = sup, (s) and (7,s,a) := QT (s sup, (7, a). Under Definition 1, the action-value functions are always linear in the feature map, and there exists some wi such that Q7 wF (Lemma A. For ease of notation, V(s, a), denote [PA, Vr i a) = Egr (V (s))) By Bellman equation and Bellman optimality equation,
(7, a) = (rh + PA P (s, (s. (r%, + PP (i (s) = (rx + VP
(s) Q7(s (s)):
The goal of the agent to maximize the cumulative episodic rewards or equivalently, minimize the regret that quantifies the difference between the value of the optimal policy π and that of the executed policies. Formally, the worse-case regres over K episodes is given as:
K R(T) Σ
(2)
Remark 1. Different rypes of regret used in literature measure the performance of PS al- gorithms. Bayesian regret EEw~poot ([T(T) |w*] is often considered when assuming a prior po(w) over the true parameter w*. Frequentist regret E[](T)) is considered when w" is fixed, where the expectation is taken over all the randomness over data and algorithm. As explained in Appendix A.2, the worst-case regret that we study is stronger than the frequentist regret.
2.1 Delayed Feedback Model
In this work, we consider stochastic delays across episodes. More specifically, the trajectory (i.c., sequence of states, actions and rewards) generated in each episode is not immediately observable in the presence of delay. The formal definition is given as follows.
Definition 2 (Episodic Delayed Feedback). In each episode E [K], the execution of a fixed policy T generates a trajectory {st a rh, sh:11 -hemm- Such trajectory information is called the feedback of episode k. Let represent the random delay between the rollout completion of episode and the time point at which its feedback becomes observable.
Remark 2. Various types of delays have been independently studied in the literature, including delays in states 14, 12, 16], delays in rewards 125, 45, 60), delays in actions[56), and delays in trajectories (29, 68]. We focus on the last scheme which facilitates the delayed analysis of value- based methods in episodic linear MDPs.
'Linear MDPs recover tabular MDPs by taking d' = -S1LA), where feature map is one-one mapping for each state-action pair.

---

Algorithm 1: Delayed Posterior Sampling Value Iteration (Delayed-PSVD)
Input: priors po(w)]) - (0, Al), scaling factor v, multi-round paramter M, hyper parameters and o².
Initialization: vk, h. Quua( Vi++((s-), V,(,),))),,,))))) Da. + O.
2 for episode l: 1,..., do
Sample initial state sf for time step
H.
do
yv - yh..... ......33.. Vn
with yi r 11% (
2n. 10 0²
with 6- k (55 0%)
S < o D + AI, wh a ((2))
p(wf Dr. un) c NN v² ($2))
for m = I..... M do p(wx Da. Wh)
Sample Wh w.."
o(..)) " w.. Update (h(:)) max 2.m
(..)(,)))
11
(..).)) +- max, min (Qh ()), h 1) Update x.(()) +- argmax,e.4 min(@h (1), for time step 1, ..... do
1}
16
Choose action aj π
Collect trajectory observations D,, Dd, Uf af (h+))+1)}
n7
Feedback generated in episode cannot be immediately observed the presence delay
Episodic delays do not disrupt the policy rollout within an episode, but alter the utilization of infor- mation subsequent episodes. More precisely, the feedback of episode remains inaccessible for the following тą episodes, becoming observable only at the onset of the (k + 7k)-th episode. To track whether the feedback generated at episode is revealed at episode k', we utilize the indicator 1 1 f + т k'} (where denotes "yes" and 0 denotes "no"). We follow the standard assumption in literature in [28, 68] to assume delays are sub-exponential. It is crucial to note that this assumption primarily serves the purpose of theoretical analysis and is not prerequisite for the effective functioning of our algorithms in practical settings. Without loss of generality, we dis- cuss the performance bound under general random delays in Section 4 and empirically study the performance against different types of delays in Section 5.
Assumption -Subeexponential Episodic Delay). The episodic delays { 1k non-negative, integer-valued, independlnt and identically distributed (v, b)-subexppoennial random variables: The siddd f=(+) with fr(+) being the probability mass function, and [[(T] being the expected value. For all l [K]. the moment generating function of Tk satisfies:
E [exp (7 (Tx -E(D)) exp (1 (1 {2272)
where u and b are non-negative, and hy S 1/b.
3 Delayed Posterior Sampling Value Iteration
In this section, we introduce novel optimistic value-based algorithm, namely, Delayed Posterior Sampling Value Iteration (Delayed-PSVD), which efficiently explores the value function space in linear MDPs by embracing several critical components: posterior sampling that injects random noise when performing the least-square value iteration, optimism via multi-round sampling to achieve the optimal worst-case regret and delayed feedback model that encodes episodic trajectory delays.
Noisy value iteration via posterior sampling. At the beginning of each episode, we apply PS to sample an estimated value function from the posterior, which maintained using the observed feedback D over the previous episodes. Specifically, at each time step, the Q-function is parameter- ized by some E I such that Q(s, a) a(s, a)T w is approximation of the corresponding true optimal Q Q-function Q* (s, a). Let po (w) be the prior w, and p(y) w/ D) be the likelihood of the observation y. then the posterior of satisfies:
P(w|D, y) exp(- -[w,, y. (w),,
5

---

where L()) is the bog-likelihod.. Unlike the case of model-based RL (MBRL). where PS is utilized to maintain an exact posterior over the environment model, we aim adopt PS to perform noisy value- iteration by injecting randomness for efficient exploration of the value function space. Specifically, at each step E [H], we consider Gaussian-noiss perturbation in Delayed-PSVI by setting prior as (o(wa) = (0, Ala), and log-likelihood (with 2/- = {0%, 0he The 1h
[TE|k-11) ! as
L(wn, Vn Dn) = Σ (6(5) a7) Tw,, wp - -vh),
(3)
where yı: = lw....... . yh. " with 27 = TT a7) + episode k; the posterior of w follows a Gaussian distribution,
Then for all step h E [M]] of
p (Dn Und x ((D2)) - ( ( (0
where 2 = x0 + Ala and t [ n)),,, (l) p0 "t)...,,,0$ 068 k-1 0 )- Adding the scal- ing factors 0² and 2² yields the Line 10 of Algorithm 1. It is important to note that while the induced likelihood cxp(-L(wf . )) from (3) is Gaussian, we do not assume y/ r% (5), o)) + +Vn+1(57441 follows a Gaussian distribution. Instead, the above likelihood model can be used for non-Gaussian problems as we need not sample from the exact Bayesian posterior model [2. 74].
On the other hand, the ūijk computed in Line 9 of Algorithm 1 together with the greedy choice V()) R max. ac)a)) (Line 15) approximates the solution of Bellman optimality equation via the least-square ridge regression: o argmin w Σ a,)) " (r max 2²))² + Ma. Con- sequently, Line 5-10 essentially performs the Posterior Sampling Value Iteration.
Optimism via multi-round sampling scheme. Unlike the Bayesian regret or the worst-case pected regret, the high-probability worst-case regret in (2) needs to control the sub-optimal gap with arbitrarily high probability of at least 1 - 5. However, sampling once each time step only pro- vides a constant-probabiliy optimistic estimation, which breaks the high probability requirement. In addition, the estimation error incurred by sampling (i.e. constant-probability pessimistic esti- mation) at each timestep will propagate to the previous time steps during the backward posterior sampling value iteration. This phenomenon does not appear in the 1-horizon bandit problem due to saturated-arm analysis [2, 6]. To remedy this issue, we design a multi-round sampling scheme that generates M estimates (QT") [ME[M]] for Q-fuction through M i.i.d. sampling procedures, and
constructs an optimistic estimate by setting Q = maxm Qm Notably, our choice of M has order Polylog(H, H,, K, dd 8), and thus makes our algorithm sample-efficient without increasing the overall complexity dependence. As shown in Line 11-14 of Algorithm 1, this scheme guarantees the op- timistic estimates Q > Q" can be achieved as desired. Lastly, ensemble sampling methods enjoy empirical success and popularity in RL [21, 23, 31], including double q-learning [26] and boot- strapped DQN [42, 471. We are among the first few works to explain its theoretical effectiveness.
Episodic delayed feedback model. Recall that by Definition 2, when delay тыe takes place, the feedback { ahh r sh JNe(H)) of episode & cannot be observed until the beginning of the i + Tk- th episode. Accordingly, the delayed version of the fully observed y", 22 now becomes,
vh < 1 1 o
4 + [11.-1 ((5) ,...... 1A-1A-1
k-1)).
%
As a result, episodic delays are considered during the posterior updates in subsequent episodes. This completes the design of Delayed-PSVV as presented in Algorithm 1. In the remainder of this section, we present the main theoretical guarantees of Delayed-PSS PSVI and the proof sketch of Theorem 1.
Theorem 1. Suppose delays satisfy Assumption 1. In any episodic linear MDP with time horizon T = KH, where K is the total number of episodes, for any O < 5 < 1, let X = 1, o² = 1, M = log(4H K / //))////(////////////oo/////////
and v = Cs/a Re Ö(vdM (Cs/a in Lemma B. Then with probability at least 1 8, there exists some absolute constants c, c, c" > O such that the regret of Delayed-PSVI (Algorithm 1) satisfies:
R(T) S CO
Here i is a Polylog term of H, d, K,5.
'Here Q min( a), ) H h 1} is the truncated version.

---

On the complexity bound. Theorem 1 provides the first analysis for PS algorithms under delay and answers the conjecture from [60]. Our result recovers the best-available frequentist regret of O(v HT)) for PS algorithms when there is no delay ([E[T] = 0). According to [24], the worst- case regret of linear Thompson sampling is lower bounded by 92( 22(vdT)) and this implies our regret dependencies on parameter d and T are optimal under the class of PS algorithms.? 5 The order V in our regret is v VH--suboptimll to the optimal dependence in [27]. As an initial study for pos- terior sampling with delayed feedback, improving the horizon dependence is beyond our pursuit and we leave it for future work. Moreover, the presence of delay incurs an additive regret term Ō H(E()) As T grows, the impact of delay will not dominate the overall regret. Furthermore, our high-probability regret bound directly implies the following worst-case expected regret.
Corollary 1. Under the setting of Theorem 1, the expected regret of Delayed-PSVI is bounded by
E[R(T)) S O(Vd + Od H²E()] +
Here is a Polylog of H, d, K. The expectation is taken over the randomness in data and algorithm.
Proof of Corollary 1 is included in Appendix A.2. Additionally, we present the following corollary in linear bandits, whose main regret OVd is optimal for PS algorithms.
Corollary 2 (Delayed Posterior Sampling for Linear Bandits), For the linear bandit with yt o. nh, where Ie E Dr IRd and тι be mean-zero noise with B-subgaussian. Let T be the total number of steps. Under Assumption 1, for any 0 < 8 < 1, with probability at least 5, the regret of Delayed-PSLB satisfies:
R(T) O
+
Here i is a Polylog term of K,
3.1 Sketch of the analysis
Due the space limit, we outline the key steps in analysis and defer the complete proof of Theorem Appendix B. To bound the worst-case regret in (2), first note that
R(T)
Vi - + (st)
(TTA(st)
k=
Our goal is to attain an optimistic estimation so that A error A For optimistic PS algorithms, Gaussian anti-concentration is the main tool [6. 65) to
opt S O while controlling the estimation
achieve optimism with constant probability. However, the probability of optimism will diminish as
the algorithm pro-ppropsgates with respect time. In contrast, we maintain m [M] independent ensembles Q" so that roughly speaking, IP(QT 2 Q*) 2 R4
for all valid m. For any 0 < 1,
with the choice M log(1/m) (og(6663)), the optimistic estimator Q max QT satisfies P(Q Q*) 2 1 (Lemma B.6). We then proceed to prove A opt 0.
To control A one key challenge is to bound the error term Σk | (s*, Il)) (at) -1 Due to the presence of delays, we cannot directly apply the Elliptical Potential Lemma in the non-delayed settings. Therefore, we decompose (12*)-1 into (Σ*)-1 + Mj. where Σ
Σ/=1 ø (8%, 0.) ø (5h, af,"" + Al is the full information matrix, and show
Σ |0s at al) S max TK
Σ El a" ('))
KE[K]
By doing so, Ek (|* > can be upper bounded by Ö(dlog(K) via the Elliptical
Potential Lemma and [ can be upper bounded by Ö(E[r]) via the sub-exponential tail bound. Combing all these steps completes the proof.
Note for non-sampling based algorithms, e.g. UCB, the regret attain Õ(VPTT) [1].
7

---

Algorithm 2: Delayed Langevin Posterior Sampling Value Iteration (Delayed-LPSVI)
Input: Wa. 7/,, .N.. 7y and rounds M, A. Delayed loss LE as (5). Initialization: vk E [K], E [H). +=+1(>-) - 0, V + O. (5-) +
2 for episode l- 1,...., KK do
Sample initial state si
for time step H..... ..... do
for m 1, M do
Wa LMC ( wo, me, Nk.
ILLM is given by Algorithm
2i ((-)
Φ(-) T(-)Tomp t
Update (x)) max 2
V (:-)) max. min minn(Q (Qt (a(()))) a), H h
Update policy (-) t argmax min h+ 1
11
for time step
..... Choose action d; n (s
12
Collect trajectory observations D,, Dj U f ( ag ry +1+1
13
Feedback generated in episode cannot be immediately observed in the presence delay
4 Delayed Posterior Sampling via Langevin Dynamies
Delayed-PSVI performs noisy value iteration for linear MDPs by injecting randomness for explo- ration via Gaussian noise. From the Bayesian perspective, it constructs Laplace approximation to obtain Gaussian posterior given the observed data. However, sampling from a Gaussian distri- bution with a general covariance matrix O% can be computationally expensive in high-dimensional RL tasks. Specifically, Line 10 of Algorithm 1 is conducted via w := w + 12 -/2 where Ç Ç~ (0, Ta). The complexity of computing the matrix inverse involved (e.g. via Cholesky decom- position) is at least (dd),, which prohibitively high for large d. More importantly, in complex problem domains, flexible form of non-Gaussian noise perturbation may be desirable.
To tackle these challenges, we incorporate gradient- approximate sampling scheme via Langevin dynamics for PS algorithms, namely, LMC, and introduce the Delayed-Langevin Poste- rior Sampling Value Iteration (Delayed-LPSVI) Algorithm 2. The update rule of LMC essentially performs the following noisy gradient update:
W/ f W 17 VL(,,)1) + + 22m7e
where ez iid. NOO, Ta). is based on the Fuler-Murayama discretization of the Langevin stochastic differential equation (SDE):
dw(() = -V)=)vv((w()) + 2 dB((),
(4)
where B() E Rd is Brownian motion, > 0 and / 0. Under certain regularity conditions the drift term (t) in (4), it can be shown that the Langevin dynamics converges to a unique stationary distribution (dw) x exp (-BL(w)) (w))dw. As result, LMC is capable of generating samples from arbitrarily complex distributions which can be intractble without closed form. With sufficient number of iterations, the posterior of we is in proportional to exp( exp(-v/1/n{(ww)
In our problem, specify L to be the following delayed loss function
k-1
[w) = E1. ((0(s), w) - TT) + Nllwo|2
(5)
T=1
h+1 ( Compared to Delayed-PSVI, Algorithm 2 does not require the matrix inversion computation. Below we present the worst-case regret of Delayed-LPSVI and discuss the key insights in our analysis. The full proof is deferred to Appendix C.
where 37, :- +Vr
Theorem 2. Suppose delays satisfy Assumption
In any episodic linear MDP with time hori- zon T = KH, where K is the total number of episodes and H is the fixed episode length,
for any < 8 < 1, let X = 1, N₁ max{log( 32H2 (K+)) + 1)/[2log(1/(1 21,)),,
1og2 1 ))* log( 4HK3 ) log(1/(11 2na 11), ( 7 16C3/4 Ō(dMH2),
llg((1(1 anp
/x/ak
8

---

0 and M = Jog(4HH//b) log (og(64/63) Then with probability at least 1 - 8, there exists some absolute constants c, c' c" > 0 such that the regret of Algorithm 2 satisfies:
R(T) S cv H + B + c.
Here l is a Polylog term of H. d, K, and Cs defined in Lemma C.9.
Neglecting the constants and Polylog fac- tors, Delayed-LPSSV maintains the same or- der regret of Ö(vdH + d' {T])) as
Algorithm 3: Langevin Monte Carlo
LMC(L, wo, 17, N,
Delayed-PSVI while significantly improving the computational efficiency. Precisely, LMC requires ( complexity to perform gradi- ent steps in Line of Algorithm and an ex- Output: WN
fort= 1... Draw & ~ (N Ia)
do
Wy f- W 7/ VVVL(u-1)) + Voye
tra ((d) operations to compute 2% in Line
7. Thus, the total computation complexity of LMC is O((N d)MHK). On the other hand, sampling without LMC (Line5-8 in Algorithm 1) requires (dd)) operations, and the multi-round sampling (Line9-11) incurs O(dM) additional operations, which implies for total computation complexity of ((dd + dM)HK) As the choice of N in Algorithm 2 has logarithmic order, and M log( ( log(64/63), the overall complexity of Delayed-LPSVI is Ö(dHK), whereas the overall computational complexity of Delayed-PSV is Ö(d HK). Notably, Delayed-LPSVI reduces the computational overhead of Delayed-PSVI Ö(d)).
On the analysis. The key step in the proof of Theorem 2 is to show the convergence guarantee of LMC. Indeed, by recursion, one can show
N-1
UN = ANAwO + (1 (L-ANN, w + 22
AN
where An. = 1 2 For any wo. it implies wN follows the Gaussian distribution
N A + (1 A wh, @t.) With the choice of 17s 40max (9t)* Ab, x La and [ - (1
(2N)) (2h) x + < ( which is the key to connect @ with (1t)) (Lemma C.2), the 28,,
main analysis for Delayed-PSV goes through by utilizing this connection.
On arbitrary delayed feedback. The current study considers the stochastic delays that are sub- exponential Assumption 1. What if delay has an arbitrary distribution (e.g. Cauchy distribution has unbounded mean)? Indeed, the regret can be (roughly) bounded by V H3T + (q) for d, (q) to be the g-th quantile of delay r. We do not focus on this setting since there is 1/g blow-up in the main regret that many distributions (e.g. sub-exponential) do not need sacrifice. We include the discussion in Appendix A.3.
5 Experiments
To validate whether our posterior sampling algorithms are competitive outperform the non- sampling-basse algorithms in the delayed setting, in this section, we examine their empirical perfor- mance in two simulated RL environments with different delayed feedback distributions. In particu- lar, we consider a linear MDP environment following [44, 46], and a variant of the popular River- Swim [55]. In both environments, we benchmark Delayed-PSVI (Algorithm 1), Delayed-LPSVI (Algorithm 2) against LSVI-UCB [35] with delayed feedback, namely. Delayed-UCBVI. In this section, we discuss results in the first setting and defer the discussion of RiverSwim in Appendix E.
5.1 Synthetic Linear MDP
We construct a synthetic linear MDP instance with |S| 2, |A| = 50, 10, and H 20. The linear feature mapping embeds each state-action pair with its binary representation and induces the following reward function: r(8, a) = 0.99 if = 0, a = 0; r(s, a) = 0.01 otherwise. The design of the environment results in the same optimal value V (>1) when d and H are fixed. Algorithms are examined under three types of delays that are commonly encountered real-world phenomena, including sub-exponential delays and fong-tail delays:

---

10
Dverage Return
01
D-USS
D4U251
D-UCT7
D/UC7
D4CCY
500
1000
-500
2000
2000
3000
1000
15000
2000
2000
3000
500
1000
-500
2000
2300
3000
Figure I: Left:(a) Multinomial delay with delay categories {10, 20, 30}. (b) Poisson delay with rate E/r] 50. (c) Long- tail Pareto delay with shape 1.0, scale 500. Results are reported over 10 experiments. Delayed-PSVI and DPLVV demonstrate robust performance under both well-behaved and long-tail tail delays.
Multinomial delay. Delays follow Multinomial distribution with three categories { [10, 20,30,, 30}, with the corresponding probabilities as {0.5, 0.3, 0.2}.
Poisson delay. Delays follow a Poisson distribution with the expected delay as E[r] = 50.
Long-tail delay. Delays discretized from Pareto distribution with the shape param- eter as 1.0 and the scale parameter as 500.
To run Delayed-LPSVV sample, and let M 2, = 40, = cq/ Am For Delayed-PSVI, we set parameters
warm start LMC by initializing wo each time step with the previous
M = 2, == vdH. In the case of Delayed-UCBVI we set the bonus coefficient as B = c3/2- dH Vlog(dH). To make fair comparison, hyperparameter values and fix C3 = 0.1, G = 0.5, y = 0.02. Experiments are repeated with 10 different random seeds, and the returns averaged over episodes in Figure 1. Further elaboration on additional metrics available in Appendix F.2.
perform grid search to determine the optimal
Results and Discussions. Both Delayed-PSVI and Delayed-LPSV exhibit consistent and robust performance with resilience, not only under the well-behaved delays that decay exponentially fast, as assumed in Assumption 1, but also under the heavy-tailed delays, such as those following Pareto distributions. Notably, when confronted with the challenge of long-tail delays, our algorithms ex- cel Delayed-UCBVI in terms of statistical accuracy (yielding higher return) and convergence rate. Specifically, the performance of Delayed-UCCE -CrredUUUUBII degrades under long- tail delays, resulting from its computational inefficiency in iteratively constructing confidence intervals. In contrast, PS methods offer a higher degree flexibility to adjust the range of exploration, owing to the inherent random- ized algorithmic nature. To assess the computational advantages facilitated by LMC, consider additional synthetic environments with varied dimensions for a more comprehensive analysis. For detailed statistics and further discussions, please refer to Appendix E.2. It is noteworthy that in practical high-dimensional RL tasks, the computational savings achieved by Delayed-LPSVI, in comparison Delayed-PSVI, are considerably more significant.
6 Conclusion
In this paper, we study posterior sampling with episodic delayed feedback in linear MDPs. We introduce two novel value-based algorithms: Delayed-PSVI and Delayed-LPSVI. Both algorithms are proved to achieve O(v H3 di ((](] worst-case regret. Notably, by incorporating LMC for approximate sampling, Delayed-LPSVI reduces the computational cost by Ō while main- taining the same order of regret. Our empirical experiments further validate the effectiveness of our algorithms by demonstrating their superiority over the UCB-based methods.
This work provides the first delayed-feedbact analysis for posterior sampling algorithms in RL, paving the way to several promising avenues for future research. Firstly, it is interesting to extend the current results to settings with general function approximation [34, 71]. Additionally, leveraging the sharp analysis outlined in [27] to improve the suboptimal dependence on H for posterior sampling algorithms presents intriguing avenue for exploration. Furthermore, addressing other types of delay (e.g. adversarial delay) that differ from stochastic one will contribute to the ongoing field of delayed feedback studies in online learning, and we leave the investigation in future works.
Parreto distribution with shape parameter less than 5.0 are known to have hevy right tails.
10

---

Acknowledgements
Ming Yin and Yu-xiang Wang are gratefully supported by National Science Foundation (NSF) Awards #2007117 and #2003257. Nikki Kuang and Yi-An Ma supported by the NSF SCALE MoDI-2134209 and the CCF-211 (TILOS) awards, as well as the U.S. Department of En- ergy, Office of Science, and the Facebook Research award. Mengdi Wang gratefully acknowledges funding from Office of Naval Research (ONR) N00014-21-1-2288. Air Force Office of Scientific Research (AFOSR) FA9550- 1-0003,, and NSF 19-589,
References
[1] Yasin Yadkor,, Dávid Pál. and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
[2] Mare Abeille and Alessandro Lazaric. Linear thompson sampling revisited. In Artificial Intel- ligence and Statistics, pages 176-184. PMLR, 2017.
[3] Milton Abramowitz and Irene A Stegun. Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, volume 55. US Government Printing Office, 1964.
[4] Mridul Agarwal and Vaneet Aggarwal. Blind decision making: Reinforcement learning with delayed observations. Pattern Recognition Letters, 150:176-182. 2021.
(5] Priyank Agrawal, Jinglin Chen, and Nan Jiang. Improved worst-case regret bounds for ran- domized least-squares value iteration. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 6566-6573, 2021.
[6] Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference on machine learning, pages 127-135, PMLR, 2013.
[7] Shipra Agrawal and Randy Jia. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds. Advances in Neural Information Processing Systems, 30, 2017.
[8] Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
[9] Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based rein- forcement learning with value-targeted regression. In International Conference Machine Learning, pages 463-474. PMLR, 2020.
[10] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272. PMLR, 2017.
[11] Kevin Black, Michael Janner, Yilun Du, Ilya Kostrikov, and Sergey Levine. Training diffusion models with reinforcement learning. arXiv preprint w:Xi::2305.13300 2023.
[12] Yann Bouteiller, Simon Ramstedt, Giovanni Beltrame, Christopher Pal, and Jonathan Binas. Reinforcement learning with random delays. In International conference on learning repre- sentations, 2020.
[13] Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimization. In International Conference on Machine Learming, pages 1283-1294 PMLR, 2020.
[14] Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. Advances in neural information processing systems, 24, 2011.
[15] Baiming Chen, Mengdi Xu, Zuxin Liu, Liang Li, and Ding Zhao. Delay-aware multi- agent reinforcement learning for cooperative and competitive environments. arXiv preprint 2rX1v:2005.05441, 2020.

---

[16] Minshuo Chen, Yu Bai, H Vincent Poor, and Mengdi Wang. Efficient rl with impaired ob- servability: Learning to act with delayed and missing state observations. arXiv preprint arXiv:2306.0124. 2023.
[17] Esther Derman, Gal Dalal, and Shie Mannor. Acting in delayed environments with non- stationary markov policies. In International Conference on Learning Representations, 2020.
[18] Gabriel Dulac-Amold, Daniel Mankowitz, and Todd Hester. Challenges of real-world rein- forcement learning. arXiv preprint arXiv:1904. 11199004.21,,, 12901, 2019.
[19] Ying Fan and Yifei Ming. Model-based reinforcement learning for continuous control with posterior sampling. In International Conference on Machine Learning, pages 3078-3087. PMLR, 2021.
[20] Matthew Fellows, Anuj Mahajan, Tim GJ Rudner, and Shimon Whiteson. Virel: A variational inference framework for reinforcement learning. Advances in neural information processing systems, 32, 2019.
[21] Scott Fujimoto, Herke Hoof, and David Meger. Addressing function approximation error in actor-critic methods. In International conference machine learning, pages 1587-1596. PMLR, 2018
[22] Manegueu Anne Gael, Claire Vernade, Alexandra Carpentier, and Michal Valko. Stochastic bandits with arm-dependent delays. In International Conference on Machine Learning, pages 3348 3356. PMLR, 2020.
[23] Tuomas Haarnoja, Aurick Zhou, Picter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference machine learning, pages 1861-1870. PMLR, 2018.
[24] Nima Hamidi and Mohsen Bayati. On frequentist regret of linear thompson sampling. arXiv preprint arXiv:2006..6679, 2020.
[25] Beining Han, Zhizhou Ren, Zuofan Wu, Yuan Zhou, and Jian Peng. Off Off-policy reinforcement learning with delayed rewards. In International Conference on Machine Learning, pages 8280- 8303. PMLR, 2022.
[26] Hado Hasselt. Double q-learning. Advances in neural information processing systems, 23, 2010.
[27] Jiafan He. Heyang Zhao, Dongruo Zhou, and Quanquan Gu. Nearly minimax optimal re- inforcement learning for linear markov decision processes. In International Conference on Machine Learning, pages 12790-12822. PMLR, 2023.
(28) Benjamin Howson, Ciara Pike-Burke, and Sarah Filippi. Delayed feedback in generalised linear bandits revisited. In International Conference Artificial Intelligence and Statistics, pages 0095-6119 19. PMLR, 2023.
[29] Benjamin Howson, Ciara Pike-Burke, and Sarah Filippi. Optimism and delays in episodic reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 6061-6094. PMLR, 2023.
[30] Daniel Hsu. Sham Kakade, and Tong Zhang. A tail inequality for quadratic forms of subgaus- sian random vectors. 2012.
[31] Haque Ishfaq, Qiwen Cui, Viet Nguyen, Alex Ayoub, Zhuoran Yang, Zhaoran Wang, Doina Precup, and Lin Yang. Randomized exploration in reinforcement learning with general value function approximation. In International Conference Machine Learning, pages 4607-4616. PMLR, 2021.
[32] Shinji Ito Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, and Ken-Ichi Kawarabayashi, Delay and cooperation in nonstochastic linear ban- dits. Advances in Neural Information Processing Systems, 33:4872 4883, 2020.
12

---

[33] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contextual decision processes with low bellman rank are pac-learnable. In International Con- ference on Machine Learning, pages 774-1713. PMIR, 2017.
[34] Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances in neural information processing systems, 14:13406-13413 2021.
[35] Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137- 2143. PMLR, 2020.
[36] Tiancheng Jin, Tal Lancewicki, Haipeng Luo, Yishay Mansour, and Aviv Rosenberg. Near-optimal regret for adversarial mdp with delayed bandit feedback. arXiv preprint arXiv:2201.13172 2022.
[37] John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ron- neberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Zidek, Anna Potapenko, et al. Highly accurate protein structure prediction with alphafold. Nature, 596(7873):583-58) 2021.
[38] Amin Karbasi, Nikki Lijing Kuang, Yian Ma, and Siddharth Mitra. Langevin thompson sam- pling with logarithmic communication: bandits and reinforcement learning. In International Conference on Machine Learning, pages 15828-15860. PMLR, 2023.
[39] Parham M Kebria, Abbas Khosravi, Saeid Nahavandi, Peng Shi, and Roohallah Alizadehsani. Robust adaptive control scheme for teleoperation systems with delay and uncertainties. IEEE transactions on cybernetics, 50(7):3243-3253, 2019.
[40] Tal Lancewicki, Aviv Rosenberg, and Yishay Mansour. Learning adversarial markov deci- sion processes with delayed feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7281-7289, 2022.
[41] Kimin Lee, Hao Liu, Moonkyung Ryu, Olivia Watkins, Yuqing Du, Craig Boutilier, Pieter Abbeel, Mohammad Ghavamzadeh, and Shixiang Shane Gu. Aligning text-to-image models using human feedback. urXiv preprint arXiv:2302.1 12192, 2023.
[42] Ziniu Li, Yingru Li, Yushun Zhang, Tong Zhang, and Zhi-Quan Luo. Hyperdqn: A randomized exploration method for deep reinforcement learning. In International Conference on Learning Representations, 2021.
[43] Eric Mazumdar, Aldo Pacchiano, Yian Ma, Michael Jordan, and Peter Bartlett. On approxi- mate thompson sampling with langevin algorithms. In International Conference on Machine Learning, pages 6797-6807. PMLR, 2020.
[44] Yifei Min, Tianhao Wang. Dongruo Zhou, and Quanquan Gu. Variance-aware off off-policy eval- uation with linear function approximation. Advances in neural information processing systems, 34:7598-7618 2021.
[45] Washim Uddin Mondal and Vaneet Aggarwal. Reinforcement learning with delayed, compos- ite, and partially anonymous reward. arXiv preprint arXiv:2305.0255: 2023.
[46] Thanh Nguyen-Tang, Ming Yin, Sunil Gupta, Svetha Venkatesh, and Raman Arora. On instance-dependent bounds for offline reinforcement learning with linear function approxima- tion. arXiv preprint arXiv:221 2..1::2211.13208, 2022.
[47] Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn. Advances in neural information processing systems, 29,2099 2016.
[48] Ian Osband, Benjamin Van Roy, Daniel Russo, Zheng Wen, et al. Deep exploration via randomized value functions. J. Mach. Learn. Res., 20 20(124):1-62. 2019.
[49] Ian Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via random- ized value functions. In International Conference on Machine Learning, pages 2377-2386. PMLR, 2016.
13

---

[50] Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35:27730-27744, 2022.
[51] Abhishek Padalkar, Acorn Pooley, Ajinkya Jain, Alex Bewley, Alex Herzog, Alex Irpan, Alexander Khazatsky, Anant Rai, Anikait Singh, Anthony Brohan, et al. Open x-embodiment: Robotic learning datasets and rt-x models. arXiv preprint arXiv:2310.0888 2023.
[52] Carlos Riquelme, George Tucker, and Jasper Snock. Deep bayesian bandits showdown: An empirical comparison of bayesian deep networks for thompson sampling. In International Conference Learning Representations, 2018.
[53] Daniel Russo. Worst-case regret bounds for exploration via randomized value functions. Ad- vances in Neural Information Processing Systems, 32, 2019.
[54] Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of opti- mistic exploration. Advances in Neural Information Processing Systems, 26, 2013.
[55] Alexander L Strehl and Michael L Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 7498):1309-131. 2008.
[56] Wei Tang, Chien-Ju Ho, and Yang Liu. Bandit learning with delayed impact of actions. Ad- vances in Neural Information Processing Systems, 01226604426811 2021.
[57] William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3-4):285-294 1933.
(58) Tobias Sommer Thune, Nicolò Cesa-Bianchi, and Yevgeny Seldin. Nonstochastic multiarmed bandits with unrestricted delays. Advances Neural Information Processing Systems, 32, 2019.
[59] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXIv:2307.09288. 2023.
[60] Claire Vernade, Alexandra Carpentier, Tor Lattimore, Giovanni Zappella, Beyza Ermis, and Michael Brueckner. Linear bandits with stochastic delayed feedback. In International Confer- ence on Machine Learning, pages 9712-9721. PMLR, 2020.
[61] Ruosong Wang, Russ R Salakhutdinov. and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Ad- vances in Neural Information Processing Systems, 33:6123-6135, 6635, 2020.
[62] Yining Wang, Ruosong Wang, Simon Du, and Akshay Krishnamurthy. Optimism in reinforcement learning with generalized linear function approximation. arXiv preprint 19X.v:191..04136. 2019.
[63] Yufei Wang, Wanjun Zhong, Liangyou Li, Fei Mi, Xingshan Zeng, Wenyong Huang, Lifeng Shang. Xin Jiang, and Qun Liu. Aligning large language models with human: A survey. arXiv preprint arXiv:2307. 12966, 2023.
[64] 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.
[65] 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-2485 24850. PMLR, 2022.
[66] 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.
14

---

[67] Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pages 10746-10756. PMLR, 2020.
[68] Yunchang Yang, Han Zhong, Tianhao Wu, Bin Liu, Liwei Wang, and Simon S Du. A framework for sequential decision making with delayed feedback. arXiv preprint arXiv: 2023.
[69] Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal provable uniform convergence in of- fline policy evaluation for reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 1567-1575. PMLR, 2021.
[70] Ming Yin, Yaqi Duan, Mengdi Wang. and Yu-Xiang Wang. Near-optimal offline reinforce- ment learning with linear representation: Leveraging variance information with pessimism. International Conference on Learning Representations, 2022.
[71] Ming Yin, Mengdi Wang, and Yu-Xiang Wang. Offline reinforcement learning with differ- entiable function approximation is provably efficient. International Conference on Learning Representations, 2023.
[72] Andrea Zanette, David Brandfoobrener, Emma Brunskill, Mattco Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In Inter- national Conference on Artificial Intelligence and Statistics, pages 1954-1964. PMLR, 2020.
[73] Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pages 10978-10989, PMLR, 2020.
[74] Tong Zhang. Feel-good thompson sampling for contextual bandits and reinforcement learning. SIAM Journal on Mathematics of Data Science, 4(2):834-857, 8578 2022.
[75] Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference Learning Theory, pages 4532-45 4576. PMLR, 2021.
[76] Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference on Machine Learning, pages 12793-12802. PMLR, 2021.
[77] Zhengyuan Zhou, Renyuan Xu, and Jose Blanchet. Learning in generalized linear contextual bandits with stochastic delays. Advances in Neural Information Processing Systems, 32, 2019.
[78] Julian Zimmert and Yevgeny Seldin. An optimal algorithm for adversarial bandits with arbi- trary delays. In International Conference on Artificial Intelligence and Statistics, pages 3285- 3294. PMLR, 2020.
15

---

Appendices
A Some Properties
A.1 Properties of Linear MDPs
Lemma A.1. In linear MDPs, the action-value function is also linear in feature map. v(s,a)
S E [H] and & E R&, under any fixed policy
Qh a) = 0(s a wx where wx. == On + B (s') and wa E Rd. As corollary, there exists wxt such that Q7. = oJ Tww,.
Proof of Lemma A.I. By Bellman equation.
()) rn(s, a) Ex Ea or. / Viti(d') d(o(s, aa pn(s))
a(
where w = 0g + Ep, (
A.2 Worst-case regret as a stronger criterion
We use Theorem 1 as example. Using the worst-case result, i.e. with probability 1 1 Ó.
R(T) S ev H e"c.
Here has the functional form Polylog(d, K, H. 8). Then choosing 5 = 1/(HK) to obtain with probability 1/HHK),
R(T) S eV + (( +cl:=
for = Polylog(d, H). Therefore.
E[R(T) ([000)))1())))))(1(0000111111111
1A HK -(R(T) 2 A) < 1+1.
This completes Corollary 1.
A.3 Discussion on the arbitrary delay
For completeness of our study, also briefly discuss the case when delay is arbitrary. In genreal, the regret can be (roughly) bounded by H of delay т. This could be achieved by creating a low-switching variant of our Theorem I/Theorem and applying the reduction of the concurrent work [68]. We do not focus on this setting since there 1/q blow-up in the main regret that many distributions (e.g. sub-exponential) do not need to sacrifice.
for d, (q) to be the q-th quantile
B Regret Analysis for Delayed-PSVI
To proceed with the regret analysis, introduce some helpful notations. Besides (s,
max, ((s,a)T, th -m. (7 = max, (s, a) in Algorithm 1, we define
@h(s,a)) ((s, T) ())() max (%, a), O = min(( h 11:
( (P = o(s, Tw, with w = On (sd=ns))ddu())).
16

---

Regret decomposition: We start by rewriting regret in terms of value-function error decomposition following the standard analysis of optimistic algorithms [10]:
R(T) = - (F V/ (of)
where each episode A corresponds to the regret resulting from optimism, and A tracks down the regret incurred from estimation error. Efficient RL algorithms thus need to strike a balance between both terms. More specifically, it desirable to generate optimistic estimations over the true value function, while keeping estimation error relatively small. By cautious design of noise pertur- bation, we show in Theorem 1 that Algorithm 1 effectively achieves vT order regret in episodic MDPs with linear function approximation.
Proof of Theorem I. The proof proceeds by bounding A and A est respectively.
Step I: bound regret from optimism.
By Lemma B.7, the optimism provided by our algorithm guarantees with probability at least 1 18/2
for all k E [K]. A ope :- (s (s < O.
Step 2: bound regret from estimation error. To bound the estimation enror, first condition the following event
1
: mi [ (r% + Pa V 1) (s, a)l s B (|o(s, ()) + K3'
Vs, a, h, k,
with 3 = /22 log(16c.HMK/0)+
8H2 log ( (MAA) + dM log(1
+ log 16
1V3
2 2vAvdH. Here Ca and CH.d..,,. are defined in Lemma B.8.
Recall that A est == (x+) 1ITh (sf) and define c = E(VA+ (o%+1) - V (0)+1) 10
Wh+t (5%+1) Vi (sh+1)- Then by applying Lemma B.1 recursively, the total estimation error
Σk Abso be decomposed as:
K Σ
est
k=1
K
1
V2
($2
V n2
(5)
+ + + 8
Dbll + K3
1=1
"1
H K
( a ( +
1= k=1
A=1
On hand, by definition, | < 2H for all [H] k E [K]. Therefore, (ch) is martingale difference sequence (since the computation v is independent the new observation at episode k). By azzuma-Hofffding incquality (for t > 0),
H
-12
IP
ΣV
ch
>
2 exp
-8/8,
2K H²
which implies with probability 5/8,
H
ch
2KH3 log(8/8) /2HTT log(8/5).
Note here the equals 6/4 as of Lemma B.8. Therefore, by Lemma B.8, P(E) 2 1 1-88 8/4.
17

---

Step 3: bounding the delayed error. By Lemma B.4, with probability 1 - -8/8,
H K
ΣΣ
[0(s
a (22) S H / 2dK log K)/d) + lo
H
log((d K)/d).
h-1k=1
Here Dr,5.H.K == + 2B|T] + 2/ defined in Lemma D.6. Consequently,
[B[r] log( 24KH
+ $ j log( 24KH + Dr,K, and Dr,K,5 is
K
8
ΣE |0 a (
(nt)) S 3H 2dK log (d + TA,K log((o+ (8)
k=1h=1
Note that by Lemma B.8, event & holds with probability 1 1-6/4, and by union bound with (7) and (8), we have with probability - 8/2.
K
A est S /2H2T log (og((8/)) 2dK log((d K)d)) log((++)/dd++ (4)0 K2
Finally, by a union bound over Stepl, Step2 and Step3, we obtain with probability 1 - 8,
K
R(T)
A
opt
eat
est
H K2
S 22H2T log (8/8) 3H 2dk
3dHD, log((d+ K)/d)
SCN e H
where e > is some universal constant and is a Polylog term of H, d. K, The last step is due to: by the choice of X 1, 1, Cafs and M = log(4HH/6)) 1og(64/63), we can bound Cs (in Lemma B0) by Cs S call ddM with co universal constant and is contains only the Polylog terms. This implies 2² S C, H Note Ca S dis. therefore / is dominated by the I CzdHis for some universal constants C2, C3. Since R(T) is dominated by the second term in the second last inequality, plug back the upper bound for 3 gets the result. Finally, it is readily to verify DT,A,H.K is bounded by c'E(T]e (()).
first term 3 < C 222
Lemma B.1. Define Sh = EV( and condition on the event (10) in Lemina B.8. Then for all l: E [K], E [H) the following holds,
h+1 (oh+z)= Viti (sh+2)
18h, at]
Vi+ (s%+1) + Wii (sh+1)
V (sh) V (sh) < Vih (sh+z)) -W (5%+1) + ch + 3 ||o[sh at) 11 + K3
Proof of Lemma B.I. Since at (s()), it implies V/ (x+) (hi, at) (recall @ min(@ H - h + 1}) and Vith (xt) = 27, (sh at). Hence,
KV%% (sh) VTTh (sh) (Vitt (si+z) Vit (sh+z) chi
IVV/ (sh) Vrth (sh) - B (si+1) Vitt (sh+1) 1s, atll
-IV (s%) - - -IP, ( at))
(s at: - (F (5 af)l
<B 11 a (1a))) + バ3
where the last step is by the event defined in (10).
B.1 Bounding the delayed error term Σk
|1 i at) (
Recall the delayed covariance matrix D
Σt=1 1 (7) of AZ with 1a,
1[s + Ts S t). then we can define the full design matrix Σ/ and the complement matrix A as
k-1
E = Σ
S5s (70 aT) + WI, A = Σ [ss + 10(0 a)) af), (9)
18

---

then My = O + -. Also, denote the number of missing episodes as: UA = =E== 1[s + To > k].
Then we have the following Lemmas.
Lemma B.2. For À > 0, (52) = (-
Proof of Lemma B.2. Since À > 0, both S2 and 2 are invertible with:
(1 =(>x)) + (0 (2
= =1 + (2 120))
= =(2x)= + (2%) (())))
Lemma B.3. Denote of == (55 a/t) Let X > 0, then
1 K
(1+
max Us Tk) | (1
(2)))-
2 k=1
kE[K]
Proof of Lemma B.3. By definition and Trace of matrix, we have
= -1
T 11
Tr((Et)
Denote A = (2%))- A and B = (9 - (O)) then A, B both have non-negative eigenvalues
(by Lemma 14) and this implies
TrAAB) Tr (AB
Tr B BB//2 AB1/2 TT Tr (BV(T((A)IBB)) Tr(B)
and this implies
1
1
| ( -A))))))))))))--- = TVT[BBB| & V TTATBH
- 2 Tr(A) +
TT)
1 2
| (ot) 2
Σ
1l + T3
-- 11 0 || [1
+ maxxe[k] UR
|1 2
Σ
k-1
1 + Te > k - 111110%
2
(Et) 1
where the last inequality uses Lemma D.15. Next, by changing the order summation, we have
K k-1
K 1
K
Il+ k - 1]
Σ
1 +
11 (,))-
=
k=H+1
K K-1
K-1 oc
K-1
= =Σ
1/7 > s) 11bl
Σ
1/7 5)
1101
Σ Te o1 2
(xx)
which implies
K
( (
1 + [MX Uk
11 1
1
K
2 k=
1=1
1 + maxke[k] Up
K
1 (xx) +
1
Σ
K
k-1
1|
1]
2
A=1
1 + m Uk
K
K-1
|
Σ
|0
2
(x)))
+
To
1=1
19

---

where the second step uses (E = (2)) -1 for k 2 t.
Lemma B.4 (Bounding the delayed error). With probability 1-888
H K
ΣΣ
Ell
(a)) S H / 2d log(dd K)/d) dH d...... log((d + K)/d).
h-1k=1
Here DTS.HKK 1 2B 2 2TE log 24k + 3 log( ( D D7, and K,, is defined in Lemma D.6.
Proof of Lemma B.4. Now Combine Lemma B.2 and Lemma B.3, we obtain (at))
S
|
(2))-
o (A))))))))))---
K
ll (2t)
max Us + Tx) o1 (E))- RE KE|K]
k=1
For term (*), since À 1, by Cauchy-Schwarts Schwartz inequality and Elliptical Potential Lemma D.8,
K
K
dct(EEk+1) det(2)))
Σ o
S
| h
S
2K log
S
v 2dK log((d + K)/d)
(2))
(2))
For term (**), by Lemma D.15 and Lemma D.6 and union bound, with probability -5/8.
k
max Us + Tw)
(
2
RE K]
1=1
1
$ (1 + max Up max Tk)
1 (I+))
kE[K]
kE(K)
k=1
1
(1 + max Up + max Tk 2d (10gg++4 + K)
2 KE|K]
K](K]
24K
24K
<d(1 + E[T] + 2
[E[T] log
+
log(
+ max Th) log((d+ (K)(dd))/dd) KE[K]
6
3
5
24K
24K
<d(1 + E[T] 2
2 log(
log(
+ E D log (dd K)/d)
Denote Dr,6,K == 1 + E[r] + 2 2F (r)
log(
24K
4 + log(
+ E[r] + D K, then we have 24K
8
3
with probability 1 8/8.
K
| at) o S 2dK log( + K)/d) + dD log((d K)/d), Σ
then apply union bound over h E [H] to obtained the stated result.
B.2 Proofs of Anti-concentratton for Delayed-PSVI
In this section, we prove the optimism via anti-concentration for Delayed-PSVI. We first present two assisting lemmas.
Lemma B.5 (Anti-concentrration for Optimism). Suppose the event
F. ()),0) (rī: Pr (s,, Cs (é(s,a))los 1, Vs, a, h, k} holds. Choose C3 and M3 log H
( log(64/63)) Then we have with probability 8.
()),))) 2 (rx + P (s, a( S A,h e [H], [K].
20

---

Proof of Lemma B.5. For the rest of the proof, we condition on the event
= ( a) (rå + Pr Wi+1) a)} s Cs ( a) (mat)) 1. Vs, h, k}
where 8' will be specified later and Cs is defined in the Lemma 1. Also note @ (s,a) (h a) ((s, ( wh) ~ _N(0 2f 22, a)"
"h." (5)
((0.1)
V VPs(s, a) -
Therefore,
( 2 (rx V (s, Vs,a 2%)
2tTTH (s,a) (4,
(ra + Ps Pn (s, (s,
P
as,a Φh
(i, - (1)())))))) ()),a))
Vidd(, -(0
1) (rn +h - Vs,a @%
>P 1)0, Z C3|UV)
1/2
2/88
64'
where the first event uses the condition on E and the second inequality chooses v Cy and uses
Lemma D.5. Apply Lemma B.6 with f rr + Pr V/ for Ms =log(1/0)/log(f) log(///633))))
P (Q% a) 2 (rx + IP, // (s, a), Ys,
2% 8
By law of total expectation E[ = E[1A] = P[A], it implies
PP (s) a) 2 (rx + Pr V - 1) (s, a), Vs, a) > 2-
Apply a union bound for h, k, we have for M1 =
log (09(64/63), with probability 1 1-6 5,
P ((* (rn + Ps (s.
21-8.
The following lemma is used to prove Lemma B.5.
Lemma B.6. For any function f : S x A + RR. For any 0 < 8 < 1. Suppose for any (k. h, m) E
[K] x [M] x [M] f. (s, a) 2 f(s a), Vs,a 0% 2 c for some constant e > 0. Let M =
h
log(116)/ log
[1 (0/logg(/////
c)). Then
IP (O)t(s,)) 2 (ss Ys, a @h) 2 1-
Proof of Lemma B.6. For any fixed (ki h) E [K] x [H]. we have
P {(s a) s.t. max (s, a) 1 ()) @% mE[M]
P ((sss a) s.t. Vm [M], (s, S f(s,a) 2%) (Sm, am) S f (Sm: am) Q1
< TP Vmm E [M], ((5m am) s.t. 2h."m (sm,
M
= II
(ss 8.1. Th.m (s, < (() @%)
m0= M
II m=1
[1 - P (0% (s, a) 2 f(s, Vs [%)] s (1 - c) = 5.
21

---

then this implies
2(s, @%) 2 6.
With the above lemmas, we are ready to prove the optimism achieved by Delayed-PSVI with respect to Qh-
Lemma B.7 (Optimism). For any 0 S 8 < 1, we set the input in Algorithm as v = C5/4 and
Ms = (4H (/HK//8) (gg(6/63)) then with probability 1 - 8/2, we have
(s, a) (s, (s) (s) V [H] l. [K].
Here Cg is defined in Lemma B.10.
Proof of Lemma B.7. Step1: Suppose the event
E 10 a) (râ Pr, V (s) Cs | a) (aat)+ Vs, a, k}
holds. Choose Cs and Ms log(4ll log(64/63). Then we show, for any h [M]]. with probability 1 8/4, (8, 2 ()),,)), (s) 2 (s) for all (s.a) E S A. [M].
k E [K].
First, due to our choice of Ms log / log (60//6444))) by Lemma B.5, with probability 6/4.
(s) 2 (rM + PA PA V(s e A,h [H), k [K].
which we condition on.
Next, we finish the proof by backward induction. Base case: for h + 1, the value functions
are zero, and thus Q4 2 Qi++1 holds trivially, which also implies V 2 Vi+1- Suppose the conclusion holds true for + 1. Then for time step h and any E [K],
2 0% = @% (rm PA. V
(7% PA V/ Q%
2 h (rx + PA + ) + (r + FH - Q7
2 (rA + Pr, v 2
where the first inequality uses the induction hypothesis and the second inequality uses the condi-
tion. Lastly, (.) max, min ( (-, a). H + 1} I max, min (:
a), H - h +
max, (7(:aa)) Vg By induction, this finishes the Step1.
Step2: By Lemma 1010, with probability - 5/4, for all &: E [K], h E [M], S, E A, it holds
(1 a) - (r), + PA (s,,) a)
S C2y4 (lo(1, (o)))
Therefore, in Stepl, choose 8' = 8/4, and union bound we obtain: for the choice v = C3/4 and M₂ = log(4H log (64/633), then with probability - 5/2, we have
2 a) (s, (A) ((ss) S A. he [H) & EE [K].
B.3 Proofs of Conventration for Delayed-PSVI
Lemma B.8 (Pointwise Concentration). Algorithm guarantees that with probability - 8, Vk E [K], [H] E S. A, it holds:
min (mi, h (r + VA (s, < 51l1o(s, (llss,))lls a)) +
(10)
K3
where 3 = 20 log (C2HMK/0) 88'2 1 log (**A) dM log(1
2VSh=CH.AR.M.47
log
HVX
2 2VAdd.. In particular, here log Ca dlog(1 + 28 8H SHvdKK) and CH..k.M.- = 2H vVId+u 220gg(//88)
22

---

Proof of Lemma B.8. Recall that Ir + P4 & H - h + 1, therefore r + PA Ph
min(r + Fn V h+1 H 1--++11,, This implies
[PPx [PAARttil(ssa) =
m a) H - h 1} minff [P.V a), - h 1}} < (s, r
[PP V h+1 (s,, a)). Hence
min((h((s a), h + -44 - [PA - ls. - ()))aa)- r -PP (F
a) - ()) a) + (s)
r Pr V/ (ss.
S () - a) + ()( + P [
R1
Ra
The proof then directly follows Lemma B.9 and Lemma B.10 to bound R₁ and Rz respectively (together with union bound).
Lemma B.9 (Concentration of R1). For any 0 < < 1. define the event È as
E = =(0h(s,0)) a) w S 22 loggooC. Ilo (00 +
1
K3
Wk [K] S
(11)
then E happens with probability 1-5. Here log Ca = dlog (1 2v log(2/6)/A4 1og2//// SHVZ)
Proof of Lemma B.9. In the Stepl and Step2, we abuse ,. denote wt) for arbitrary to avoid notation redundancy.
In Step1: We first show for any &e E [K], h [H) (s) E S x A, with probability 1 - 6,
|Ø(s, (w w S 2v log(2/0) [ a)l(a))-
Indeed, by design of Algorithm 1, प ~ N 0² (1 ), which gives,
o(s, a) T ( x ~ N((, (s,, a) T)
Therefore, (ss ()"((Tt k is 22,
a) a) (() -b -sub-Gausiian By concentration of sub-
Gaussian random variables, we have
P (1o(s.0) (( - 21) < 2cxp (-2v2o(s,)) ((()))
(1200111000000000000000001011111 2o(s,a) 1 == 8
12
Solving for ò gives with probability 1 1-8, [ss a)T (a) w+)) s v 222 (alisaa)a(()))) (00))-1-l a) log(2/0) 2222 log (2/5) ( a))(o))>
Step2: For any 0 < d < 1, define the event E as
E = { (((s,a)Tee w a(s,a)T(i) at s l2g2log |o(s, ( a)l( 1 + K3
1
Vk E [K] h E [M], S
(12)
then E happens with probability 1- Here log C2 d (oolog((+(1 2 log &H
In Lemma 1. set 0 = w - : and A = (52 and B = 1/X, and let V/ be the 2k epsilon net
for the class of values (Ø, प w C v T (1))) 6 || < 1} (where C 22v² log(2/8)), then it must also be the I/s epsilon net for the class of values F ((((s,,) a). / w
C (01 ((2))) (0()))1(()0)) (8,a) E S x A}. let V is the smallest subset of y such that it is
23

---

1 -pssiln net for the class of values F. Then we can select VsxA to be the set of state-action 2K pairs such that for any fø K पे x C T (9 1 E V. there exists (s, a) E Vsx.A satisfies (Ø(s, a), म - / C ((s, a) ( a)l - fo - 1/2K3, then we have Vsx.A is a -eK--ep net F and |sx s [V] S [ Therefore.
suplooss a), प x C ((s, a) ( ( 8,0
(K)(s,a), क. الاها C ( a) + 1/K
sup (sa))VeXA
2v² log( 8H and K, we have the stated Then by a union bound over (1 + / the result.
Step3: Note QA maxm o² th hence by union bound over M, we have
(5 (ss a) wh = max (555 a) T ((8 T
$ max jo(s, a)=a w. a(s,a)=
Iv 2v² log( | (1))))))))(()))))))))))
+ K3
for all k, h, 8, a with probability 8. Here the last inequality follows Step2, which completes the proof.
8.
Lemma B.10 (Concentration of R2). For any 0 < 5 < 1, with probability 1- for all E [K] h e [H]. E S. A, holds
(5) - (r% PAVA h+ 1) (s, a)) Co (lo(s, a))(()))))(
/8H12 d log 2222) + dM + 2v CH + log + 2/AvTH and the
where Cs
HVA
/V22ttr/2oog(M//
quantity CH.Ak.M. = 211 x
dk
VA
Proof of Lemma B.10. For any (k, [K] x
H and (s,a) E S x A. denote
((s,))Tuf, = (rh: + PA V (8, a), where wf 0g + [ Viirld')dpaa (s)))d
Recall VT = 1,, (5% a + V (3) from Algorithm and denote 27 == r (8% am) +
h+t1 15) Then by definition,
A-1 - 6(3% = (()))
A-1
w = (S2
Σ L.
Σ r=1
1 6(5), al)o%.
From 2 defined line 7 of Algorithm 1, we have $ = 2t S
AI. Plug it into the definition of
by we have
k-1 1 T (55 a7) (T. - 6(8%, ( Twt + 0(5), a, Tw))
ot = (0 1
Σ
k-1
= -(
Σ
1 1 ((s) a7) (TT - ((5 ( T + (12 (o A1) w
24

---

We then proceed to bound , - w which gives
k Wh - ( -1
1 1 065 ah) (Th o(8h: ah) -(22)))) -'
(5
7, (6h ah)
V.h (1
2(12
(ii)
Term (i). Since S2 is positive definite, multiplying the first term (i) with @(s, a) and by Cauchy- Schwartz inequality, obtain,
Σ 1 1 (18 (Vi. (Vh+i((T+1) Pr Vh+ (5% 15% (6%%
a)(s,a) a()) s (1 a) kagp
Apply Lemma B.11, we have with probability at least 1 - 6, for any (1) E [K] x [H]. and (s,a) 8 A,
(i)) s C, (c116((s.))l((0)))
(13)
where C1 = 8H2 log k+1 + dM log(1 + 2V + log
HVA
Term (ii). By Lemma B.12, ((s. a) E S A. and (k, h) E [K] ((s, aF
can be bounded
as
(oss.a)T(n)
( a) a) - s 2 X (0ss (())))))
(14)
Combining (13), (14), we have with probability 1- 8, for any (k, h) E [K] x [H] and (s,a) E S Ax
@h(s,a) (rh + Py The fe 18. = 10 a) ( m S (ss ((i) + (o(s,)
< (C1 + 2VAVdH) (10 1.
This concludes the proof.
Lemma B.11. For any 0 < 5 < 1, with probability 5, we have v(k. E [K] [H].
1 - ((5h.a))) ax) (Vo+i(5h+1)
V h+1 (8h, (5)
(92
d
1 k *++)) + dog(
2v 2v8k3 BV8K-CH M...C...MMM.. log
2
<8H²
log
HVX
8
here C...KKM. = 2H
dk X
vy /2ggt//2
VA
Proof of Lemma B. First note that
(.) == max min a), (H h 1)} = max min max km (H - + 1)}
max min max (-, a) T w wh.. ,(H h 1)}.
Recall that km - wh)/v NN Ta), then by Lemma D.7, with probability 1 5/2, have
Vā
kk.m W
12 at)
2d + 2ogg(1)))
NNote here v is in the line 10 of Algorithm 1. At the end we will choose y to be Poly(H, d, K) and this will affect the overall dependence of the guarantee since CH..A.MM.. inside the log term.
25

---

Apply the union bound over all m, then above implies with probability 1 1 1-8/2 vm E [M]
uV224uy - 2H dk / = CC..k.M...... (15)
- [ +
VX
Now consider the function class V == {max, máx ((;,a) um || S C...a.M.s..
so by Lemma D.13 the c-log covering number for V dM log(1 + [CHakMe) ). Since minf;s } is a non-expansive operator, the e-log covering number for the function class V fmax, m m Φ(: a)''"" w" (H h 1)} | z CH.dkk,M.s. is most dM log(1 + (.M.M.)))))) Hence, for any V V, there exists V in the e-covering such that V V + Av with |l S c. Then with probability 8/2,
1 1 (V) PA (sh. an))
(80))-1
T. 100 (V"())-1) Pv a)
(00))
(16)
2
1 1 (o (Av PA (sh am))
(1+)-1
+ 8
<2
1 1,, k- 10 ((hh (V
- PPV'
X
((0))-
-1
d
k 1+ dM log(1 + 2CH,de, +
2
+ 8k262
<AH²
log
where the second inequality can be conducted using a direct calculation and the third inequality uses Lemma D.9 and union bound over the covering number. Now by (15) and (16) and a union bound, we have for any > 0, with probability -8
Σ Ssh an)
(Vi+i(5h+a)) PA PA (1t
((0
d
h+ A A
2 + dM log(1 + 2CH.N. +log log
8k262
24
log
2
8
d
k A A
doMl + 2V8h>CHaM log
<8H²
log
2
A
HVA
where the last step choose e² H, K to obtain the stated result.
H 22 X/8K2 so SAZe s 4112. Lastly, apply the union bound over
Lemma B..2. V(s,a) E A. h E [H] k E [K], it holds that
(a(s,a) T 2 VaH (1 a)ll
Proof of Lemma 12. Note that the precision matrix 2% for any step h and episode & is always positive definite. By Cauchy-Schwartz inequality and Lemma D.I.
| (2)))) -'u = |0s,, =ss ( 112((2)) 1/2
< | a) k ||
< | a) - v || [|((2)))
1
< ||o(s a) ))) ||
Amin (12
Note that Amin (2
Amin(5) 2 X. Applying Lemma D.3 for || completes the proof.
26

---

C Regret Analysis for Delayed-LPSVI
Proof of Theorem 2. The proof structure is similar to that of Theorem We proceed by bounding opt and A Est respectively.
Ak
Step 1: bound regret from optimism. By Lemma C.5, with probability 1- 6/2.
opt = (s V ( - O, vk E [K].
Step bound regret from estimation error. We first condition on the event that
3 = {1l min (Q)(( H (rx + Pn V. (s, a)l - [lo(s, ())) K3 Vs, a, ask,h,,)) h,
with 3 = 22 [oggo
8H2
log (
+ dM log(1 CVS. Rv2
log 16 8
+
2VAVTH. Here Ca and Cn..A. are defined in Lemma C.6.
Similarly, define
& =VV+ (sh+1) Vh+t (sh+t) 1sh, a Vht (sh+1) + V41 (sh+1)
Then by Lemma C.I.
K
K
k est
(s - V (+++
1=1
k=1
F (5%)
1i (sh) st + +B 1110ostt +
1 (17)
K3
k=
N
H
Sh
+
ΣΣ
Σ
[ss a 10 +
K2.
k=
k=11=1
By definition, 14 < 2H for all h E [H]
k E [K], therefore {ch) martingale difference
sequence. By Azuma- Hoeffding's inequality,
t 2K H3 6/8,
Σ
cA
=1 exp
v0 0.
1=
Thus, with probability 1- 8/8.
H
ΣΣ
ch
2K log(8/8) /2H2T. log(8/5).
(18)
A=1A=1
Step bounding the delayed error. By Lemma B.4, with probability 1 1-888.
B B Eit (1
at) (aty-1 S 3H / 22k log((d + K)/d) + 3dH Dr. log((d + K)/d).
(19)
Here D,,,H,K = 2B[r] + 2/ 2E/r] log( 24KH + 3/2 log( 21KH + Dr,K, & and Kr, K,5 is defined in Lemma D.6. By Lemma C.6, event & holds with probability - 8/4, by union bound with (18) and (19), have with probability 1 8/2,
K
(o((tkK))( H K2
A eet S /2H2T log 2dK log((d +
Finally, by union bound over Step1, Step2 and Step3, we obtain with probability 5,
K
R(T)
opt
est
eat
/ 2H2T log (8/8) 3H / 2dK log( B.H.D....H... log( ()/d) H
K2
Scv
27

---

where e > 0 is some universal constant and is a Polylog term of H, d, K, 8. Similarly, we can bound < CdHus for some universal constant C, and is readily verify D,,6,H,K K is bounded by e'E(rr] O(t).
Lemma C.1. Define ch = EV h+1 (sh+1) W++ (sh+1) 1sh afl V (sh+1) + hit (s/++)) and condition on the event (21) in Lemma C.6. Then for all [K], [H], the following holds.
Vix (sh) V (sh)
S V (sh+1) V
Vitti (sf+1) + c ||o(sh a (a))
K
Proof of Lemma C.I. By the event defined in (21), the proof follows exactly as in that of Lemma B.1.
C.1 Convergence of Langevin Monte Carlo
The following lemma is crucial to prove the optimism and bound the error in Langevin analysis. For ease of notation, within the episode k we simply v denote d for conciseness.
Lemma C.2 (Convergence of LMC). Denote (ik " Jmmela] be the weights returned by Line of Algorithm Set r) Dxmas (8,,)' we have
W
k.m
(A + A 1 0%)
Vm E [M]
where
An, I - 2
K
2 AI +
Sn i 0 (shh o
h-1
wh = (2t)) -1
Φn (5 a k7)9%
7=1
O 7(1 - A
(S2 k -2(T + An.x)
Furthermore, we have
1 (1
1 2Nr
(I2
0% <
2K
Ammaz (9 Auiin (
where Kh =
is the condition number.
Proof of Lemma C.2. Let by Ik=1 (58 a,)o%% then VL (w) 202 w 2b Therefore, fix h, m. and within the Algorithm 3 we have
wN =NN-1 - (1) WN-1 - 0/:) + 22TTEN
=(T - 21/00 2 2n 22TTIeN
-AN + 2nbb / 21TTEN
N-1
N-1
=NNowN + +2 Σ
Ah. + 207
A
1=0
=AN + (I )
/2
Σ 1=0
1/
where the last equality uses (0²)) - by w and > -- 2 O, so
Σ N-1
A' = (I (I-
Ei=
A)-1, Since é, are i.i.d gaussian noise, from the above directly have
WN ~ NA wo + (1 A +
28

---

where
N N-1
N-1
/ -Col|y IV 2m
AN, (afEN-1)=2000 = 207. Cov|
Σ
A N11
1=0
1=0
N-1
22my
Σ
A 2m A - App k=
1=0
=x(1 A
N
((2 - (I + An,x)
Next, due to the choice of 17 = Dxmar (1,))* we have
< An, = - -21122 - (1- - 27jAmin (22)))
2
A x (1 - -21 (2
(20)
22N
(1 (1 211 min (22)))2N) I I A x (1 22N )
In addition,
1
I An,k I -27 + (1 - 2n m1)))
(12%))
2
3
x I 1++AA An.k (2 21/ 221 (1%)))
2
1
1 (I+ An, -1 2
2
27/2min (52))
3
The above two implies
(1 2 (2N
2
(s2 - 0 <73( 22N (22 -1
2 - 27 (1))
(1 - 2m/ (
(( x 0 < (
Replacing N with N₂ and wN with wn w m for all m E [M] completes the proof.
C.2 Proofs of optimism for Delayed-LPSVI
Lemma C.3 (Anti-concenttration for Optimism). Suppose the event
= ( a) - (ri) Pr V (s. & Cy (1,( ()) Vs, a, h, k}
holds. Choose N₂ 2 max mlog( 32 (K-
Aidk + 1)/ log(1/( /(1 Ine D. 2log(1/(2 2n 11 }. 7
log2
1602, and M₁ = (og((HH(o)) locc////33663/ Then we have with probability 6,
()) 2 (ra + PA V/L a), V(s,a) E ESx A, [M], [K].
Proof of Lemma C.3. For the rest of the proof, we condition on the event
E= = ==(0(s),a) (r): P. (P a)) s C' [ a) 1o0 Vs, k,
where 8' will be specified later and Cs is defined in the Lemma C.9.
a(s,a)"( (wi (I AN NNO0 N10.0fs.0)
29

---

Also note
@ha a) - (s,,)) A Y ~ o(s, o(o(sa)
2t (s. - (( No 1o
N(0,1).
Vo(s,a)TOx00s.c0)
Therefore,
P 0h 88 a) 2 (rn + Pn P (1, (s,,,
Un (8, ol. a²
No 10
(rn + Pa (s a) ((s 1 Vs, a
2
Vo(s,a) (((s,))=O)6(300))
(rn + PA Vo (s, a) a(8, N Vs,a
1)
Vols, (
(rh Fh (s.
0) o(s aT A Dob
>P 1)
Vs,
1 (1
)2N,
6(s, ( -
20h
1/2 1
2P 1(001)21
z
2V8T
8T
64
where the first two inequalities follow Lemma C.2 and Lemma C.4 respectively and the thrid in- equality results from Lemma D.5. Applying Lemma B.6 with Th PA V& and without
conditioning, for M3 (og(1/5)) =og((/////oo((///6)))
P () 2 (rn PA (H, 2 1-6.
Apply a union bound for h, ki, we have for M₁ log(H 1og(64/63)) with probability 8,
(0h((s a) 2 (rn + + +. 2 21-6.
Lemma C.4. Suppose the event
= 1 - (ri: + P. V/ (s, a)) < Cx (0(s,))l((g)) Vs, a h, k}
holds.
Choose N₂ 2 maxgl 3211" (K d)dk
log2 1)/[2log(1/(1 2x 111) 2log(1/(1 2ng
and
7 = =16C3. Then
(Trh + Ir (p+1))))s - No )
-
$1, V [K].
(0)))))))))))) 1 1- 2xr, )2NNx)
Proof of Lemma C.4. By direct calculation,
(rr. PA V..Vi a) ois a) A
l0(s, a)T (OO)AAAA ANN
2/ 1 - (1 znz J2N. o(s, (1)))
(1 - (1 Z )2N,
-10))
[rr + Pa (P.1))))) -(s,,) wلنl
(1 , )20)) ((..a)= (I2
30

---

For the first term above, by CS inequality we have
((ss - (0(5))) a) -|co0t) 1/1 17th
s 3V00).a)((0 (0) A No. -2H1 X
dk
1 )NO 2H V dk:
S <V0( vk+ 11 216
and this indicates
(0(8, a)Th A Ah.
Vk + A. (1 (1-22,)) ) 2H V
2k%,
A
1
-
2
1 1- Zun )2N( o(s,a)
1 1 (1 (1- 1 yaNa
where the last inequality is by N2 2 log( For the second term above.
(K+)kk 7
+ 1)/ log(1/ z4z )].
(Pn+ Vn (s,0) ((a
C₂'
C2' 1 2
I
3 (1-(1-14))) )2Nz) @( (2 10(s,a)
(1-1(11-2)))
(1 2pn )2Nx)
(3
Here the second inequality uses N₂ 2log(1/(1 20 1602.
log2
and the last equal sign comes from
Lemma C.5 (Optimism for Langevin Posterior Sampling). For any S 8 < 1, we set the input in Algorithm as N& 2 max{ 32/H (K + 1) log(1/(1 24Z ]4n))]] 2log(1/(1 my و 7
log
7X
160% 8/4 and Ms = log(4HH/8)) / log(64/63). then with probability 1 - -8/2, we have
(5, 2 Qh(s, a), (=)) 2 (s) Vs x [M], k E [K].
Here C8 is defined in Lemma C.9.
Proof of Lemma C.5. Stepl: Suppose the event
E = =((0((s,,) - (rā Pr V (s, o)) s Cs ((((s, (((s))))()))-1 Vs, h,
holds. Choose N₂ 2 max (log( (K- + 1)/(2lo((1/ - Zmz 11 2lo
log
160g and Ms- log(4H/K/0) (6g(6//)3) Then we show, for any h E [M], with probability
1- 8/4, (% a) 2 (s, a). (s) 2 (s) for all (s, E E x A, h E [H] k E [K].
First, due to our choice of M₁- 8/4.
by Lemma C.3, with probability 1
(s, 2 (ra + PA v4 (s, a), V(s ES x A, E [M] E [K].
which we condition on.
Next, finish the proof by backward induction. Base case: for h. H + the value functions
are zero, and thus @ #++1= 2 Qi++1 holds trivially, which also implies V 2 Vä+1- Suppose the conclusion holds true for h + Then for time step h and any [K].
Q 0% = 2 (ra + PA V + (ra + PA V/ Q7
2 Q) (rn + PA (. + (ra + PPVV - Q
= Q -(ra + Pl V 0
31

---

where the first inequality uses the induction hypothesis and the second inequality uses the condi-
tion. Lastly, (.) max, ( (..a)))))))))))))))) a), H1 1} S max, min ( a), H h + 1}
maxa (7(-a)) V (-). By induction, this finishes the Stepl.
[ E S, E A, it holds Step2: By Lemma C.9, with probability 1 6/4, for all &s E [K] E
(s. - (1% PA
V (s, a)
Ca)
Therefore, in Stepl, choose 8' 8/4, and union bound we obtain: for the choice N₂ 2 max( 7
2n, )) 21og(1/(1- 11 7 16C and Ms
log
log( (/HK///////// (O//H/////oo(0/4/033) then with probability 8/2. we have
(s. a), (s) V k (K].
C.3 Proofs of Concentration for Delayed-LPSVI
Lemma C.6 (Pointwise Concentration for Langevin Posterior Sampling). Choose No. > log( AHK. )/ log(L/(L 3). Algorithm 2 guarantees that Vk E [K] [M]] E S A. Vxjak
the following holds with probability 1 8,
1 - h - (rh + PA V. (8, (8110(s,a)11g 1 K3
(21)
log (*t²) + dMllo((1+ + 2v88 CH C.M.M....... M.6/3 + log
where 3 = 22 log(44C + 8
2
HVX
+2VXVdH. In particular, here log Ca = dllog(1 + (16/27)1og(/8)// 16H V))k3) and CH..KK.M. = 2H /227+ 27 (og(
VX
Proof of Lemma C.6. Recall that In PAVi < H - h + 1, therefore r PA Vk
minfr PP H - h+ This implies min
[P (PA
I+1 ( a), H - + 13 minfr + I - =
(1((s - -
[P h421 (s, a)). Hence
V-
(in a), 0) h +1] r - [Px (P (s, a) - ()(s,))- , -IP -Pr
() ()) + (s. - Pr V/ (s)
< ()) - ()) + (1(,0)) - r PA 15
The proof then directly follows Lemma C.7 and Lemma C.9 to bound RS and R2 respectively (together with a union bound).
Lemma C.7 (Concentration of RS with Langevin Posterior Sampling). Suppose No AHK3 )/ log(1/(1 )) For any 0 < 8 < 1, define the event E as A/ak
>
log(
= (ss, (o000-((ss00 a(s, w < |27 (l(ss a)(os))) + K3'
1
Vk V S
(22)
then E. hhpppens w.p. 1 --6 8. Here log Co dlog(1 + (16 27 log 16H1 16HH
32

---

Proof of Lemma C.7. In the Stepl and Step2, we abuse म to denote " for arbitrary m to avoid notation redundaney.
In Stepl: We first show for any l E [K], E [ (s, a) E x A. with probability - 6,
((ssa) (w - w - v 22 10 (1 + 2
Indeed, by Lemma C.2 we have ( (I - A No 11 (0 O which gives.
o(s.a)" - (I A ~ NO < o "00 a)). Therefore, o(s T (I Ap uub-Gaussian random variables, we have
Ny ) is o(s, a) TO a) - Sub-Gausaan. By concentration of
P ((0(s, a - - A wit) 21) S 2exp (-
t
200ss a) (0) =
Solving for d gives with probability 1 - 8.
((ss, (w (I - w)) S /2llo((200) (lo(s, a)lle; S (og(2/) (, ((ss,))l(a))) a)](())-
where the last inequality is by Lemma C.2, and by Lemma C.8, the above further implies
( - w - l2 [ (d(s,))llag a)l(ag)-- + 2K3
Step2: we prove that for any 0 < 8 < 1, define the event E as
E { ((s).0) o) wh (( w S \277og((C.HHK/) || ((()))) K3
1
Vk [K], h
(23)
then E happens w.p. Here log Ct = dlogg( + (16. log(2/))) 16H
In Lemma 1.12, set पे - w and A (st)) and 1/A, and let be the ズ epsilonn net for the class of values (K म - w Cv ΦJ -1 2 | I 1) (where C 2 log(2/))), then it must also be the ; epsilon net for the class of values F {l(é(s, wh x C
C (ss a) (10)))00)) a) केे : (s, a) E A). let is the smallest subset of V such that it _ epsilon net for the class of values F. Then we can select Vsx to be the set of state-action pairs such that for any Ss (0), / x C o -1 E V 2KJ. there ex-
ists (s,a) a) E VsxA satisfies [(o(s, a), प, x C p(s, T (S p0s a)
2 fo s
1
1/4K3, then we have Vsxa a a ) -epsilon net of F and [sx A I |V| S [V]. Therefore,
sup 8.a
(160(s,)) कy x (00 2K3
< sup (s.a)
(K0(s,)), a - को)ه - /
((s,a) -
+ 1/(2
2K3
$1/(2k²).
where the last inequality is from Stepl. Then by union bound over H, K and (1 + (16/27 log(2/0)/X + 16/ V Vd) kzdd we have with probability 1 1-d.
(Ko(s, a), w/ - wt)) - 22 06s -
sup 8.0.h.k
1
+
2.3
2
K3¹
33

---

where log Ca = d loo(1 + (1622/1lgll/////////++++ 16
(6))))
Step3:
We finish the proof. Note Q% max, 6² 1h m
hence by union bound over M, we have
(s, a) - 0ls a) w% = max (s8, a) Tw, ((x,a)
S max (0(s, u o(s a
m
1
S 27 (og lo(s, a (
K
for all k. h, s, a with probability - Here the last inequality uses Step2. This finishes the proof.
Lemma C.8. Let N₂ 2 log(
KH VA/dk )
log(1/(1- 2NT, and 1m then
[(ss,)) 2 a0
1
2K3
Proof of Lemma C.8. By direct calculation,
(0(ssa) a)" T A wh
S llo(s, a)ll ||
No |
S
||
No
|
$ ||1,,, Nx 2H
dk A
1
22
dk
1
2kh
2K3
where the third inequality by Lemma D.4 and the fourth inequality is by (20). The last inequality is by the choice of Ng.
Lemma C.9 (Concentration of R2 with Langevin Posterior Sampling). For any 0 < < 1. with probability 5, for all & [K], H S, A. holds
(h( - (+ PA & A+ (s, a)) Co Co
where Cs //H13 d log (kt2) + dM lo +
2V88CHaaMM + log + +2/AVdH and the HVX
quantity CH...K... = 2H / dk 2 + log((M
VX
Proof of Lemma C.9. For any hk, E [K] [M] and (s, a) E E x A, denote
((8,a) (u = (r + PA V (s, a), where w := 0n + Vhi (s')d
Recall Vi 1,,--1 (5% a + V (s1)) from Algorithm and denote 87 = r/ (8%. a5) +
h441 (5) Then by definition.
wh (S
Σ 1 6(5% at)o% (9
Σ 1 615) at,
By definition of 22, we have 2 = 5 A1. Plug it into the definition of w we have
k-1
a = (2
Σ
1 T (55 am) VT. - d(8%, a o + ((5), a.) w
k-1
= -2
Σ
(o) A1) w 1 1 p(5), a7)) (T - ((5 a (wa) + (12
34

---

We then proceed to bound , - w which gives
k-1
wh wh = (12
7 0( ah) (Th
6(sh: ah) Tw?))
-((2 -mm -
7 pl ah) (S
- -((22
(ii)
Term (i). Since S2 is positive definite, multiplying the first term (t) with Φ(s, a) and by Cauchy- Schwartz inequality, obtain,
(ō(s, (1)) - 11 a) (02
Σ 1 005 a7) (Vit (ST+1)) Ph Vh (8% ())
((2))
Apply Lemma C.10, we have with probability at least 1 - 6, for any (1) E [K] x [H]. and (s,a) E 8 Exx. A,
(()) s C. (c)lé((,,))((a))-
(24)
where C
8112 log (+ dM log(1 +
log
HV3
Term (ii). By Lemma B.12, v(s,a) a) E E A, and (k, h) E [K] [M) (0(5 a) (ii) can be bounded
as
a) [i) > (o(s, a) (0))) < 2v Vevvvll dH | a) [()))
(25)
Combining (24), (25), we have with probability 6, for any (k: h) [K] x [M] and (s,a) a) E ESA.
@h(s,a) (rh PA Ve R+ (s, a) = (0 ( w -
+ (
$ (C1 + 2 (108,, 11
This concludes the proof.
Lemma C.10. For any 0 < 8 < 1, with probability 1 8, we have Vkk h) E [K] x [H].
Σ 1 1r ((5),
(V
P.. 1ot1 (5% (sh.0R))
(9
d
k +
2 8 2v 2/8K3C C/B.C.......... log
<8H²
log
+ dM log(1 +
HVX
here CH..kk,as. 2HH dk
V2dT+ + / 2y loR( M/8)
VA
Proof of Lemma C. First note that
()) = max min maiin(@hie (Wh (H (H h hh 1)} = max min max km.m (H - + 1)}
a
m
max minfmax @l: a) W/ ,(H h + 1)}.
Choosing wo 0, then by Lemma C.2 and (0%) 11/2 (wik. - (T A NO Ia), and by
Lemma D.7, with probability 8/2, we have
km W
(1 A1-AN of
< (+))
(I- AI ) S vd / log(L/00
We will choose to be Poly(Hl d, K) and this will not affect the overall dependence of the guarantee since C...d...Ms is inside the log term.
35

---

where the first inequality uses Lemma C.2 again. Apply the union bound over all m, then above implies with probability 1 6/2. Vm E [M]
22d + 27 (M/6)
dk
22d + 2 log(M
- ||
2H
CH.d.k.M...
V
(26)
1 - | Now consider the function class D == {max, max, o(, T " 1m I CH.d,k.MM..). by Lemma D.13 the c-log cov-
(where we used
[ 11- No Dao A
-
A
No.
cring number for V is dM log(1 + 2.H.a.k,M.... Since min(.-) is a non-expansive operator, the c-log covering number for the function class V == {max, min (max, o(:, a) "aaT))TT" "m,, (H - h + 1)} : ||w"|| I CH.d.A.M.s. J. is at most dMM log(1 + ).A) Hence, for any V E V. there exists V in the e-covering such that V = V + Dy with |l Sc. Then with probability 1 8 5/2,
I 1 (V) Pa V (sh aR))
(22))
Σ 1 1 106-10(5h -A .)))
(00)) )-1
1-1
2
Σ 1 1 1 (Av (AT()) PAAv (sh, aT))
(27)
(of)-1
8k762
<2
Σ 10.k-o ah) - Psh am))
A
(0f))
<1112
[d log
k (x++))=
dM log(1 + 2CH.....MM.. log
86:22
2
where the second inequality can be conducted using a direct calculation and the third inequality uses Lemma D.9 and union bound over the covering number. Now by (26) and (27) and a union bound, we have for any > with probability 1 8,
Σ (ssh. a1)
(V (V/+=1(hh4)) Pr P
(22))1
d
k+
2C 2CH.a.M.M..
2 log ]]
8k-6²
<4H²
log
+ d.Mlgg( +
2
A
A
d
k + A X
2 2/ CH...... log
28H²
log
+dMlog(1
+
2
HVĀ
where the last step choose e2 H, K to obtain the stated result.
H2 H22/882 so SA2.2 S 4H² Lastly, apply the union bound over
D Auxiliary lemmas
D.1 Useful Norm Inequalities
Lemma D.1. Suppose v E Rdd, and A is some positive definite matrix whose eigenvalues satisfy Xmaze A) 2 ...2 Amin (A) > O. be shown that
Vmmin ()) ||a||| S ||vlla S Ammax (A) ||o||
Proof of Lemma D.I. Consider the eigenvalue decomposition of A, which gives = UAUT, where A = diag(Amax (A).... ...., Amiu (A). Then
| (A))(FF)3 V Amaxx(A
|1l / A/max (A) ||/||
36

---

Similar argument shows || 2 Amiin
Lemma D.2 (Lemma D.I of [35]). Let Of be the precision matrix of the posterior distribution of
w step of episode k; where Dt a 2 11 --1 with E- Ala and o² = Then
10(sh, a ( sd.
Lemma D.3 (Bound on Weights of Q-function). Suppose the linear MDP assumption and at each
step h E [ rewards Th are bounded between [0. 1), then the norm of the true parameler wij under fixed policy a satisfies
vh [ || S 2HH
In addition, for any (s,a) E S x A, let Φ(s, a Tw == (rn + Ps. P a), we also have
wh H k []],
| < 2H
Proof of Lemma D.3. By definition in Lemma A.1, the true parameter wy time step
wx On Eg [V (s'))
With bounded rewards Th [0, 1]. we have Viti S H, vs E S. Since ||0,]| S vd, and [E IV (s')ll $ [l[s Hd)n(s))] < Hvd.
Similarly, by definition of the constructed weights u
w = On + Vi
From Line 15 of Algorithm 1, for any h E [M] and s E S, (s) = max, min (in( H h 1} & H. Applying triangle inequality, we have
1.f. Vhin (o))dd)))))))
|| - ||0
| Hduuasss)
$ Vd
< vd.
Lemma D.4 (Bound on Estimated Weights of Algorithm 1), For any step E [H] and episode k E [K], the weight it output by Algorithm I satisfies,
dk
2H
Proof of Lemma D.4. For any vector Rdd it holds
1v
T
T
(2))
r (5% a + V (
Φh
k-1
k-1
k-
v
( -1
2H S
Σ
VT (2 -1
Σ
(x)) T
(s -1
0%
2H
S 2H
|
dk/A,
where the last step by Lemma D.2. The above directly imply the stated result by the definition of norm.
D
37

---

D.2 Concentration Inequalities
Lemma D.5 ((3)), Suppose Z random variable following a Gaussian distribution NN,, o²),
where o > O. The following concentration and anti coteeeeoncntttioonn inequalities hold for any 2 1:
e 12 PP 20)
1
12
S
c
2/
VTZ
And for 2 1, we have,
P F[Z n1) 20)
x
VST
Lemma D.6 (Sub-exponential tail bound). Suppose {T are (v, -ub-xxxxxoool random variables. denote Dr,K,6 == min (V2u²
2u² log (26 2bl 26 }. Then with probability
т S E|r] + Dr.K,5.
k
Lemma D.7 (Multivariate Gaussian Concentration). Suppose X NO Ia). Then with probability
1 1,
| < V2d + v 2lg((110))
Proof. Apply Proposition of [30], choose
Las then E La and Tr(E) d. ||||| 1. Then
||IX|| d 2v dt + 2t $ e = || 2 2(vd+ vD == :
which implies with probability
||||| S 22d + V2log(1/8).
Lemma D.8 (Elliptical Potential Lemma [1]. Suppose for is an Rd Rd-valued sequence, Po E Raxd is positive definite, and Q Qn + -t1 or If (9)) 2 1, and ||0-|12 S for all T E Zey, then for any & Z.,,
log dot(S2+22)
dct((L(+1))
o (07) or S 2
det(Sti)
det(A))
Lemma D.9 (Self-normalized process [[]). Let {File be filtration, and {ne be real-valued stochastic process such that Tt is Fe-measurable and up/Fi-1 is zero-mean (iee Frnc(Fr-1] = 0). Assume that conditioning on Fo Tt E-sub-Gaussian Let { be an Rd real-valued stochastic process such that dr Femesrrrabl.. Let Do Bddd be positive definite matrix and Q4 Do + -22 "E O. Then for 8 with probability least 1 8, for all t 2 0,
112 -122)
Σ UT
< 20 log
D2
Lemma D.10. Suppose Po = Ald is positive definite matrix in Rdxd and Ωt = Qo +
-= O.
det(S)+1) det(S2g)
(X+ (A+o 2t d
<
Proof of Lemma D.10. By definition, det(S2; = det(AA) = Xd. For any E4 and o, E Rd. notice that 0-0² is rank-1 matrix with eigenvalues ||ø~|| and O. By Definition and triangle inequality,
Σ
TT
T
s Σ
|| st.
Consider the eigenvalue decomposition for 1-1 T-o OTOT.
O T Udiag( A AT
38

---

which suggests
1-1 det(Sc+1)= det(Al to
0,07)
0
20
II
( max Mil + +)) oA+o -2)4
3 + +1
D.3 Covering Argument
Lemma D.11 (Covering number of Euclidean Ball). Consider an Euclidean ball BR equipped with the Euclidean metric, whose radius is R > The e-covering number of Bn satisfies,
2R d
N((BR) & [+
Lemma D.12. Define V to be a class of values with the parametric
So = ká. 0)1 CV
TT A
where the feature space is f0 |10b12 S 1} and || S B, |101| 2H 2H Vd. Let No be the covering number of e-net with respect to the absolute value distance, then we have
logN! s dlog(( 4CVB + 4HHV,
c
Proof of Lemma D.12.
1s0 f0zl [01100) CV 0T A Φ1 (1(02,0)) CV 25 A 62)
< || 12l1
[|0|| + CV [o) A Φ1 - 11 A Φ2
< || d211 2H C 00 |A] 01 dell + CV -22l ||||||11 |
< |1 dell 2H + 20 / (1 Φ211 S (2CVB 2H / || dall) || d2
$20 B 11 - Φ22 & (2CVB B +2
l| Φ21
Let C.. be the 2CVB42HV8 net of space {Ø |1012 < 1). then by Lemma D.11,
| < (1+ 40 B + 4/1 Vd
Therefore, the covering number of space V satisfies
40 + 4HVd
log < dlog(1
Lemma D.13. Let V denote the function class from S to
v()
max max bl. a) n where w S CH..k.MMS Vm [M]
let N₂ be the e-covering number V with respect to the distance dist(V, V*) = sup, Then
log No < d.M log(1 2CH.A..M..
Here C...A = 2H 2 dk
2dd / (Mg66
39

---

Proof. Let V1 max, max, o(,, a "I "wy" and V22 = max, max o a) "u"" Then dis V2) = max max max ( a) "aa"""""" "f"" max max @ a) aaaaa)"""" woy
m S max [o(s a)ll 11os" w2'l I max 1/ we I1, s,0m
m
8,a.m
For any m E M let Cm be the c-net for (w" || v CH...,,66) then by Lemma D.11,
I $ (1 + a m. jd, implies the total log covering number
log Nel & log - W S dM log(1 + 2CH.a.MM.
D.4 Delayed Feedback
Lemma D.14 (Lemma of [28]). Let A, B E Baxd be two symmetric positive semi-definite matri- ces. Then, BAB and AB share the same eigenvalues. Further, these eigenvalues are all non-negative.
Lemma D.15. Let 11, Ot. A be the full design, delayed, and complement matrix respectively. Then (1 U4 (= = ($2))- In addition, with probability 6,
max Ux < + (ogk3//3 + log log(3K/20). R
Proof. The proof follows from Lemma 11 of [28] with Us (Σ)) ż - and then apply Lemma B.2 that (92)-1 (2%) (2*)-++++))) - 4 of [28].
3 -1 The second part comes from Lemma
E Experimental Details
In this section, provide the experimental details of both simulated environments (synthetic linear MDP and RiverSwim) and discuss their results respectively.
F.1 DCIVVed-UCBVI
As shown in Table and Section 2, there is no prior UCB method that concerns exactly the same delayed linear MDP setting without resorting to specific policy-switching schemes. benchmark posterior sampling algorithms, modify the existing LSVI-UCB method to accommodate the delayed feedback, which referred to as the Dclayed-UCBVI Below we include the algorithm of Gelayed-UCBB VI for completeness.
Algorithm 4: Delayed Value Iteration with UCB (Delayed-UUCBVI
Input: bonus paramcter 8, regularization X.
Initialization: vk, h, 1f (,,11,)), 0, D, + 0.
for episode 1: ., K do
Sample initial state of
for time step H,
do
Ys -h.--.. Vi
with vk 1 177 Viti(ch
4 < [Ø] 6 ..... 5
with o 1 1 ((sT.
S < D + X
w (IR)) -
(.. ol.-)) ) "
3 (
10
V.(:.) +- max, min min (:)() H h h+11 1}
11
Update (.) +- argmax, min Q (. a), h+
12
for time step h 1,..,,, H....,,Ho do
Choose action a (s
14
Collect transitions D,, + Dr U ( of r s s
Feedback generated in episode cannot be immediately observed in the presence of delay
40

---

E.2 Synthetic Linear MDP Environment
In this section, we describe the further details in Section 5.1.
Environment Details. Following [44, 46, 70], we construct set of synthetic linear MDP environ- ments with |S| 2, feature dimension d 10, planning horizon H 20, and varying action space |A| E {20, 50, 100). Each action E A C {0, 1 is encoded with its 8-bit binary representation and represented by vector ba E IR. The feature map ((:,)) can then be defined as
((s,a) ((s,a)=10 (b (6,. 0(,,)), a(s,a)) a))² E RR,
V(s,a) E S A.
where
8(s.a) [1 1 0) 1(a 0),
otherwise.
In addition, let 0g that induces the reward functions be
p₂ 00 ... 0, r|" E R
with the choice of 0.99, and further define the measures 14l that govern the transition dynamics IP as
H (s) = [0...., 0, s) L C 2 onl:
where (aee {0,1) sequence of integers taking values 0 or 1, is the XOR operator. By design, the set of environments with identical d and H has the same optimal value Vi (s1).
Further Results and Discussions. Figure depicts the empirical distributions delays considered in section 5.1. Additionally, the average return achieved by each method upon convergence is ported in Table 2, corresponding to the results shown in Figure 1. Our empirical findings indicate that posterior sampling methods excel UCB-based methods in terms of both statistical accuracy and computational efficiency. More specifically, under different types of delays, both Delayed- -IVI and Delayed-LPSV achieve higher return (lower regret) and exhibit faster convergence compared to Delayed- UCBVI.
While delays following multinomial distribution and Poisson distributions decay exponentially fast, Pareto delays are heavy-tailed. When computational budget limited or when episodes are finite, feedback is only partially observable under long-tailed delays and is not guaranteed to be revealed to the agent. This setup captures the practical scenarios when small time windows are considered for decision-making or in online recommender systems, where only positive feedback (e.g. click, make a purchase) are often observed. As shown in Table 2, performance of Delayed-UCBVI can dramatically deteriorate in the presence of long-tailed delays.
Furthermore, our results presented in Table and Table 3 illustrate the consistent behavior poste- rior sampling in environments with delayed feedback, considering both statistical and computational aspects. When employing feature mapping, performance of the algorithms much less dependent on the sizes of state and action space in contrast to tabular settings. It is worth noting that in large state and action space, the neighborhoods of substantial number of state-action pairs may remain unvisited, leading to increased uncertainty in estimation. In such cases, adjusting the scale of ex- ploration by decreasing the noise scaling factor a for Delayed-PSVI can yield faster convergence. Finally, as shown in Table 3, Delayed-LPSVI achieves appealing performance as Delayed-PSW PSVI while reducing computation through the use of approximate sampling with Langevin dynamics.
Multinomial Delay (10, 20, 30)
Poisson Delay (b][] 50)
Pareto Delay (Shape 1.0, Scale 500)
Delayed-PSVI (a = 0.1)
11.53 = 0.76
11.48 0.81
11.53 + 0.74 10.98 + 0.40
Delayed-LPae LPSVI (c, 0.5)
11.56 = 0.48
11.37 + 0.48
Delayed-UCBVI (ca 0.1)
10.61 = 0.76
10.54 + 0.81
7.20 = 0.38
Table 2: Average return achieved by DSLVyed-PSVI. Delayed-LPSVI and Delayed-UCBB upon convergence
under different delays. Environment setup: [S| = 2. |A| = 20, d = 10. H 20. Optimal average return
V (s1) = 11.96. Results are obtained over experiments.
41

---

0.14
rub
0.07
Passon MM03
0.05
0.00
0.10
0.05
Reboblit Denste
0.04
0.00
0.00
0.03
0.03
0.02
0.94
0.02
0.01
0.01
10
15
25
30
30
0.00
50
100
323
150
Figure 2:
(a) Multinomial delays with delay categories [10, 20, 30). (b) Poisson delays with rate B[[] = 50. (c) Long-tail tail Pareto delays with shape 1.0, scale 500. The first two types of delays are well-behaver and decay exponentially fast. while pareto delays are heavy-tailed.
Empirical distributions of three types of delays.
SS] A = 20
S||AA| = 40
| = 100
S||
200
Delayed-PSVI (a = 0.3)
1418
1290
1669
2633
Delayed-PSVV (a 0.2)
531
1114
1323
Delayed-PSVI (a 0.1)
391
571
650
709
Delayed-LPSVI (c,, 0.5)
293
246
517
566
Delayed-UCBVI (cs = 0.1)
3205
2713
3351
3694
Table 3: Number episodes for each method to achieve its highest expected return. Different synthetic envi- ronments are examined with varied [S] and IA). Optimal average return is (81) = 11.96 for all environments (d = 10, H = 20). Results are obtained over 10 experiments with Poisson delays (E(r) = 50).
A 20
[S|| = 40
|S| = 100
S|| = 200
Delayed-PSVI (a = 0.3)
11.23 1 1.00
11.07 1.05
10.93 + 1.11
10.80 + 1.13
Delayed-PSVI (a = 0.2)
11.39 + 0.91
11.28 0.94
11.16 1.02
11.11 + 1.03
Delayed-PSVI (a 0.1)
11.37 0.74
11.48
11.39 0.86
11.33 0.92
Delayed-LPSVI (G, 0.5)
11.31 0.46
11.37 1.448
11.57 0.48
11.57 1 0.78
Delayed-UCBVI (c. 0.1)
10.98 + 1.78
10.54
9.67 0.54
10.01 + 0.16
Table Average return achieved by Delayed-PSVI, Delayed-LPSVI and Delayed-UCBE UCBVI upon convergence in
different lincar MDP environments with varied |S| and [A]. Optimal average return is V/" (s1) = 11.96 for all
environments (d = 10, H 20). Results are obtained over 10 experiments with Poisson delays (E[r] 50).
E.3 RiverSwim
RiverSwim environment is known be difficult exploration problem for least-squares value iter- ation with e-greedy exploration due to the sparse reward setting. It models an agent swimming in the river who can either swim towards the right (against the current) or towards the left (with the current). While trying to move rightwards may fail with some probability, moving leftwards always yield successful transition. We consider the environment with linear feature maps where [S] 5, d = 10, H = 20, and Poisson delays. Accordingly, the tabular environment can be recovered with canonical basis in Rd as its feature mapping:
Φ(s, a) es,a 12
(s, ESx A.
Define 6% as
(s, a) = [0.005, O, 0,..,,0,111 1.0 e RR
then reward functions induced by 0, are given by:
0.005
if s 0, left;
Th as)
1.0
if = 4, right;
0.0
otherwise.
In this environment, We warm start LMC for Delayed-LPSVI by reusing the previous sample for
initialization, and set M = 2, N = 40, 7 c,/ Amax (8)), 22M We set parameters
M 2, 1.0 for Delayed-PSVI and the bonus coefficient in Delayed-UCBVI as 3 = c3/2.
42

---

dvk(H- - h). Optimal hyperparameters are determined by gridsearch and we fix c3 = 0.04, Cy 0.5, C. 0.005, 1.13. Experiments are repeated with different random seeds. Cumulative regrets are then depicted in Figure 3.
Results and Discussions. Compared to the previous synthetic environment where dense rewards available, posterior sampling methods are shown to be robust with spare rewards even in the presence of delays. Figure shows that both Delayed- in delayed-feedback settings with linear function approximation. In particular, LMC (Algorithm 3) provides strong concentration such that Delayed-LPP LPSVI is able maintain the order-optimal regret space.
and Delayed-LPSVI outperform Delayed-UCBV
as Delayed- VI when exploring the
250
x10'
D-PSVI
D-LPSVI
200
D-UCBVI
Cumulative Regret
150
100
0
10
20
30 Episode
40
50
60
x10"
Figure 3: Delayed-PSVI and Delayed-I.PSV outperform Delayed-UCBV in sparse-reward setting with Pois- son delays (E(r) 5). Results reported over 5 experiments.
43


Reviews:
[{"review_id": "TN3IL0hbcs", "reviewer": "Reviewer_8fzn", "summary": "This paper considers the scenario where the feedback is delayed. The motivation for such a scenario is recommender/advertisement systems and clinical trials. They present a novel algorithm based on Thompson sampling idea: Delayed-PSVI. The authors present theoretical results for worst-case regret. They also show experimental results on synthetic linear MDP.", "questions": "1. Posterior sample algorithms often are restricted to Gaussian, multinomial distribution due to posterior computation. The proposed algorithm considers normal distribution, which I have commonly seen in posterior sampling algorithms. Is such an assumption restrictive when it comes to real-world application?", "limitations": "-", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Most of the works in RL are focused on instant feedback. This paper consider a real-time problem where the feedback may not instant. The theoretical results along with the experimental section make solid contribution. ", "weaknesses": "-", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate Reviewer 8fzn's thoughtful review and positive assessment of our work. We are pleased to see that the reviewer acknowledges the significance of addressing delayed feedback scenarios in RL, and finds our proposed algorithm, Delayed-PSVI, to be a valuable contribution to this domain.\n\nThe reviewer raises a pertinent question regarding the assumption of restrictive distributions in posterior sampling, considering its potential impact on real-world applications. \n\nWe thank the reviewer for highlighting the concern about the real-world applicability of posterior sampling algorithms. We would like to stress that  \n1. When posterior sampling is adopted to learn reward distributions in bandits or to learn transition dynamics (as PSRL) in model-based RL, it typically relies on the conjugacy assumptions in order to make posteriors tractable. However, in our case, posterior sampling is applied to perform Bayesian linear regression for Q-functions. Intuitively, such model implements noise perturbation in the space of value functions. A Gaussian noise model is able to cope with a wide range of practical scenarios (e.g. sub-Gaussian noise, Poisson noise, multinomial noise etc.) even when practical noises do not follow a Gaussian distribution. Therefore, as mentioned in Line 153 - 156, while we adopt Gaussian prior and Gaussian likelihood, we do not assume that the Bayesian model is correct, and our analysis goes through naturally.\n\n2. More importantly, our algorithm 2 (Delayed-LPSVI) incorporates Langevin Monte Carlo (LMC) as an approximate sampling scheme, which is capable of handling the general cases where posteriors are intractable and are without closed-form. We prove that when using LMC, Delayed-LPSVI is able to achieve the same regret guarantee as Delayed-PSVI. To focus on the delayed feedback, we restrict our discussion to the Gaussian case in both algorithms for consistency. However, algorithm 2 with LMC is powerful to work with non-conjugate posteriors and thus can be used to model complex problem domains in reality when Bayesian linear regression models with Gaussian noise fail to provide desirable performance.\n\nOnce again, thank you for dedicating time to reviewing our work and for providing valuable insights that will contribute to its improvement."}, {"review_id": "sCDrYZVfrE", "reviewer": "Reviewer_UyNX", "summary": "This paper studies the Thompson sampling methods for reinforcement learning problems with delayed feedbacks. The authors tackle the challenge of delayed feedback under the linear function approximation setting. They proposed two new Thompson sampling algorithms, using the exact sampling mechanism and also the Langevin dynamics for an approximate posterior sampling. The regrets and the computation complexity for both algorithms are then analyzed.  They further conduct experiments to compare the empirical results of the proposed methods and the UCB-based algorithms.", "questions": "Please see the Weaknesses.", "limitations": "The authors have discussed the limitations.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1) The authors solve the reinforcement learning (RL) problem with delayed feedback from the angle of posterior sampling rather than the well-explored UCB-based algorithms, which is a new solution to this problem.\n\n2) The second posterior sampling algorithm based on Langevin dynamics outperforms the first algorithm in terms of computation complexity, which improves the efficiency of the posterior sampling methods for the problem of RL with delayed feedback. \n\n3) The authors conduct sufficient empirical comparisons to justify the superiority of the posterior sampling over UCB methods in RL with delayed feedback.", "weaknesses": "\n1) Although this is the first work for RL with delayed feedback by posterior sampling, the technical contribution of this work still seems not significant. In terms of the algorithm design, the methods seem to be combinations of existing posterior sampling methods for linear MDPs and the multi-round sampling scheme in [24]. The theoretical analysis, in my understanding, is also mainly dependent on the analysis for RL without delay and the decomposition of the covariance matrix to show the error caused by the delay. Can the authors further discuss in detail the major technical challenges in this work and the corresponding technical contributions?\n\n2) In order to clearly show the effectiveness of the posterior sampling methods, the authors need to further present a detailed comparison of the regret results in the existing UCB-based approaches and the proposed posterior sampling approach for RL with delayed feedback.\n\n3) Is there any possibility of further improving the regret term associated with the delay? For example, use some techniques to achieve a regret more robust to the delay $\\tau$, i.e., having a sublinear dependence on $\\tau$, or to improve the dependence on the multiplicative factors $H$ and $d$. I am wondering what the best-known result is for the UCB-based approaches under a similar setting.\n\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate Reviewer UyNX's detailed evaluation of our work. We thank the reviewer for the thoughtful feedback and for recognizing the soundness of our work.\n\n    1. Clarification of technical contribution\nRegarding the concern about the technical contribution, we would like to point out that:\n(a) While from the algorithmic perspective, Algorithm 1 behaves similarily as standard posterior sampling procedures and utilize multi-run sampling to ensure worse-case regret guarantee, the main challenges lie in the analysis under the delayed feedback setting. Compared to the standard setting with immediate feedback, the posterior concentration is weaker when delays take place. As the agent needs to take actions by utilizing the observed history and existing posteriors only, which can cause distribution shift. The key is to show that even with weaker posterior concentration, our algorithm is able to achieve the desired concentration and anti-concentration criteria that guarantee the sub-linear regret. Besides, we show that in algorithm 2, the convergence guarantee provided by LMC is strong enough to yield approximate posteriors with high accuracy even with fewer available samples due to delays.\n\n(b) In addition, we incorporate approximate sampling scheme by resorting to Langevin Monte Carlo (LMC) in algorithm 2, which is an important extension from the standard posterior sampling algorithms. By utilizing LMC, algorithm 2 is proved to enjoy computational efficiency while maintaining the same regret guarantee (Thm 2). Besides, owing to the ability of LMC, algorithm 2 (Delayed-LPSVI) is able to generate samples from arbitrarily complex posteriors in complex problem domains, where posterior distributions can be intractable without closed-form. When standard posterior sampling fails to capture the noise model accurately, algorithm 2 (Delayed-LPSVI) is expected to come into play. To the best of our knowledge, this is the first analysis that provably incorporates LMC in linear MDPs and jointly consider the effect of stochastic delays. \n\n    2. Comparison with UCB-based methods\n\nTheoretical understanding of delayed feedback is mainly studied in bandit settings, and is less underexplored in RL until recently. We summarize and compare our work with all existing theoretical works in RL with delayed feedback that we are aware of:\n\n(a) Different RL settings: while [Lancewicki et al. 2022] and [Jin et al. 2022] consider adversarial MDPs, concurrent works [Howson et al 2023] and [Mondal and Aggarwal 2023] study episodic tabular MDPs, our work focuses on linear MDPs. \n\n(b) In [Yang et al 2023], they propose a reduced framework for different sequential decision-making problems. However, their framework relies on policy-switching schemes, which differ from our settings with fixed episodic length.\n\n(c) All the above works study UCB-based methods.\n\nTherefore, there is no prior theoretical work that studies exactly the same setting as ours. In our experiments, we thus adapt the UCBVI algorithm to fit the delayed linear MDP setting and test the empirical performance against it. For a fair comparison, we grid search to choose the optimal parameters for Dealyed-UCBVI in experiments.\n\nWe will further clarify and make a more comprehensive comparison with UCB approaches in our revised manuscript.\n\n\n    3. Comment on potential improvement of delayed dependence\nThe dependence on $\\mathbb{E}[\\tau]$ in the regret term associated with the delay matches that in the concurrent works ([Howson et al 2023] and [Yang et al 2023]). Therefore, we are not optimistic that this dependence can be further improved. We conjecture that more careful analysis may help bring down the dependence on $H$.\n\nOnce again, thank you for dedicating time to reviewing our work and for providing valuable insights to further enhance the quality of our work.\n\n    Reference:\n\nYang, Yunchang, et al. \"A Reduction-based Framework for Sequential Decision Making with Delayed Feedback.\" arXiv preprint arXiv:2302.01477 (2023).\n\nLancewicki, Tal, et al. \"Learning adversarial markov decision processes with delayed feedback.\" Proceedings of the AAAI Conference on Artificial Intelligence. 2022.\n\nJin, Tiancheng, et al. \"Near-optimal regret for adversarial mdp with delayed bandit feedback.\" Advances in Neural Information Processing Systems 35, 2022.\n\nHowson, Benjamin, et al. \"Optimism and delays in episodic reinforcement learning.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2023.\n\nMondal, W. U., & Aggarwal, V. Reinforcement Learning with Delayed, Composite, and Partially Anonymous Reward. arXiv preprint arXiv:2305.02527, 2023."}, {"review_id": "z4he3oMbFy", "reviewer": "Reviewer_RbB5", "summary": "This paper presents a theoretical study of a posterior sampling algorithm for linear MDPs with _delayed rewards_. The authors propose two algorithms, Delayed-PSVI and Delayed-LPSVI, which are based on sampling from a Gaussian posterior distribution over weights induced by a Bellman style likelihood function. The LPSVI variant is similar to PSVI, except the posterior sampling is done using Langevin Monte Carlo instead of sampling from the potentially high-dimensional Gaussian directly (motivation is reduced computational complexity). The authors provide worst-case regret bounds for both algorithms, with optimal dependence on on dimension $d$ and time horizon $T$, and slightly suboptimal dependence on the episode length $H$. The theoretical study is complemented by a toy experiment in which the proposed algorithms perform better than a UCB based baseline.", "questions": "* Can you clarify your comment on page 5, where you claim that your analysis is relevant for double-Q learning? IIUC, the point of having two networks in double-Q learning is to alleviate overestimation of Q-values, whereas, in your analysis, taking multiple samples of the Q function is done to ensure that your estimates are higher than the true optimal Q value with high probability? (That sounds quite different.)\n\n* Could you please clarify why does it make sense to condition the posterior model on past estimates of $\\tilde{V}$? From a Bayesian perspective, the only observed quantities are rewards (and delays); it seems like conditioning on past estimates of $\\tilde{V}$ could lead the algorithm astray, especially if the number of samples required for convergence is large. How does your approach/analysis handle this?", "limitations": "This is not my area of expertise. I am not aware of limitations beyond the already raised simplicity of experiments (which is ok for a theoretical paper like this).", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* To my knowledge, this paper provides the first worst-case regret bounds for Thompson sampling in linear MDPs with delays.\n\n* The bounds are tight up to a $\\sqrt{H}$ factor (and possibly polylog terms).", "weaknesses": "* The experimental setup is somewhat limited, with only two states and 10 feature dimensions.\n\n* Little detail on how LMC was tuned, and evidence it converged in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate Reviewer RbB5's thorough evaluation and positive assessment of our work. We thank the reviewer for providing valuable feedback that will contribute to the refinement of our work.\n\n    1. Clarification of relationship with double Q-learning\nThank you for the good question! Overall speaking, Double q learning and our method are designed for different purposes. Double q learning is designed for preventing the overestimation issue in RL (the learned Q function largely overestimates the true optimal q values), while our multi-round sampling scheme is for achieving optimism. Concretely, we utilize the multi-round sampling scheme to ensure optimism ($\\widetilde{Q} \\geq Q^*$) is achieved with high probability so as to perform worse-case regret analysis for posterior sampling algorithms. The fact that we mention ensampling in existing empirical studies such as double Q-learning is to stress its importance and effectiveness in achieving good empirical performance in various settings. Owing to its empirical popularity, we contribute to explaining its theoretical effectiveness in our work, and justify how it can be adopted to achieve the desired performance guarantee in our scenario.\n\n\n    2. Clarification of posterior models\nThe reason why the posterior model is valid based on the past estimates of $\\widetilde(V)$ are two fold:\n\n(a) In RL, apart from rewards, an agent also observes state transitions. Therefore, delays could take place in rewards, state transitions, and the impact of actions (which in turn also affects state transitions). Recall that from Line 13 of Algorithm 1, $\\widetilde{V}_{h}(\\cdot, \\cdot) \\leftarrow \\max_a\\min (\\widetilde{Q}_h^k(\\cdot, a), H-h+1)$. \n\nAs a result, $\\widetilde{V}_{h}$ is estimated based on the observations of rewards and transitions.\n\n(b) According to the definition of linear MDP (Definition 1), both the transition dynamics and reward functions are linear in feature map. Thus, $Q$ function is also linear in feature map for some parameter $w^*$(see Lemma A.1), where parameter $w^*$ governs both transitions and rewards. Here, our posterior sampling algorithm is to learn the posterior distributions of parameter $w$, and note that $\\widetilde{V}_{h}$ (or $\\widetilde{Q}$) is essentially a linear transformation on the observed transitions and rewards, it therefore serves as the observed data for the posterior. In short, the parameter of interest ($w$) governs both transitions and rewards, to learn its posteriors, we need to condition on the observations that also encode the information from transitions and rewards.\n\n    3. Clarification of experiments\nIn addition, we thank the reviewer's critique regarding the experiments in our paper. Here are a few points that we would like to highlight:\n(a). Our main contribution is to provide a theoretical understanding of posterior sampling algorithms in linear MDP (and linear bandits) under delayed feedback for the very first time. Toward this end, we design two posterior sampling algorithms. One is based on the Bayesian linear regression with Gaussian noise perturbation on value function space, and the other incorporates approximate sampling by resorting to Langevin Monte Carlo (LMC) method). We establish the same worst-case regret bound for both algorithms. \n\n(b). Hence, to corroborate our theoretical findings, we perform experiments in two different sets of environments. Note that in synthetic Linear MDP environments, we vary $|S||A|$ (cardinality of 20, 40, 100, 200) to demonstrate the empirical performance, details can be found in Appendix E.2. Due to the space constraint, we only present results for $|S| = 2, |A|=50$ in the main text. In the main text, even though the state space is small, we do consider a large action space for testing. Essentially, whether with a large number of actions or a large number of states will not affect the empirical results and parameters, as our bounds do not have dependence on $|S|$ and $|A|$. \n\n(c). The parameter setting of LMC closely follows our Theorem 2, which guides us to choose the proper scaling for all parameters, and the actual tuning is to choose the appropriate constant depending on the environments that we are testing upon. For synthetic MDP, parameter details of LMC can be found in Line 303-308; and the counterpart in the RiverSwim environment can be found in Line 989-983. In terms of the convergence of LMC, one can easily discover the convergent behavior from the plots in Figure 1. Upon the convergence of regret performance, we find that further increasing the number of iterations in LMC will not further help improve the overall performance.\n\nOnce again, thank you for dedicating time to reviewing our work and for providing valuable insights that will contribute to its improvement."}, {"review_id": "SrepXVk8Wg", "reviewer": "Reviewer_p2ng", "summary": "This paper studies the problem of online reinforcement learning with delayed feedback. To address this problem, the authors proposed two Thompson sampling-based algorithms, Delayed Posterior Sampling Value Iteration (Delayed-PSVI) and Delayed-Langevin Posterior Sampling Value Iteration (Delayed-LPSVI). Delayed-PSVI adopts a Laplace approximation around the mode and thus it is computationally expensive due to the need of computing the covariance matrix. On the other hand, Delayed-LPSVI adopts the Langvein MCMC and thus is more tractable in computation when the dimension $d$ is large. \n\nTheoretically, the authors proved the worst-case regret bound for the algorithms, which attains a regret bound of $O(\\sqrt{d^3H^3T} + d^2H^2 E[\\tau])$ for linear MDP, and $O(\\sqrt{d^3 T})$ for linear bandits. A lower bound is also proved for linear bandits. Empirically, the authors conducted a comparison between Delayed-PSVI, Delayed-LPSVI, and a UCB variant D-UCBVI on a simulated MDP environment, demonstrating the advantages of Delayed-PSVI.", "questions": "See weakness and strengths.", "limitations": "See weakness and strengths.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The problem setup is useful for modeling many practical scenarios, where the conventional Thompson sampling framework cannot handle well. \n\n- A lower bound is proved for linear bandits with delayed feedback, showing that the first term in the worst-case regret bound is tight.\n\n- The authors also provided empirical evidence for demonstrating the effectiveness of their algorithm, though the setup is synthetic.", "weaknesses": "- The problem is not new, and it has been studied in prior bandit literature, for example, Pike-Burke et al. (2018). The technical contribution might be limited, given the results from bandits and Thompson sampling under the standard setup. It would be better if the authors could emphasize more on the key technical challenges and contrast them with the bandit literature.     \n\n- The assumption on the noise (sub-exponential delay) is not well-motivated and is overly strong. From a practical perspective, the distribution of delay should have a long tail, and it is possible that some users may not respond at all.     \n\n- Also, the delays should not be iid across different users or different groups of users in online recommendation. Thus the iid assumption is too strong.  \n\n-----\n\nThanks the authors for addressing my concerns, I will increase the score to 5.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate Reviewer p2ng's detailed evaluation of our work. We thank the reviewer for recognizing the significance of the delay feedback problem that we address and for providing valuable feedback that will contribute to the refinement of our work.\n\nBelow we provide our response to the questions and critical points raised by the reviewer.\n\n    1. Comparison with existing literature\nExisting literature mainly studies delayed feedback in bandit settings, which is summarized in Section 2 (Preliminaries). In comparison, delayed feedback is less understood in the RL setting, and is more challenging in the sense that:\n\n(a) Existing bandit literature typically studies delays either in rewards or in the selection of arms independently. No prior work jointly studies the effect of delays that take place simultaneously in different aspects. However, in RL, delays can be observed not only in rewards, but also in state transitions, actions which in turn will also affect the transition. Therefore, in our work, we study a more challenging setting by considering delays with respect to the whole episodic trajectory that simultaneously includes transitions, actions, and rewards.\n\n(b) In RL, [Lancewicki et al. 2022] and [Jin et al. 2022] consider adversarial MDPs, concurrent works [Howson et al 2023] and [Mondal and Aggarwal 2023] study stochastic tabular MDPs, whereas our work focuses on linear MDPs for large-scale RL. Our regret bounds does not  depend on $|S|$ or $|A|$. In addition, instead of making the simpler assumption that delays are fixed and constant, we study the more practical setting of stochastic delays, which is unknown and random at each time step.\n\n(c) Existing works in bandits and the very recent works that study delays in RL only provide theoretical guarantees for UCB-based algorithms. How to perform posterior sampling under delayed feedback remains unknown. Therefore, we aim to bridge this gap by providing a theoretical understanding for two posterior sampling algorithms in linear MDP, and providing a corollary for linear bandits. To the best of our knowledge, our analysis is the first work that tackles all such challenges together.\n\nWe will further clarify and make a more comprehensive comparison with existing literature in our revised manuscript.\n\n    2. Clarification of assumptions on delays\nWe would like to highlight that the assumption of sub-exponential delay is mainly required for theoretical analysis: \n(a) For stochastic delays with general / arbitrary / non-sub-exponential distributions, we provide a discussion on the regret bound at the end of Section 4 (Line 277 - 282) and Appendix A.3. Briefly speaking, the regret can be (roughly) bounded by $\\widetilde{O}(\\frac{1}{q}\\sqrt{d^3H^3T}+dH^2 d_\\tau(q))$, where $d_\\tau(q)$ is the $q$-th quantile of delay $\\tau$. This could be achieved by creating a low-switching variant of our Thm 1 and Thm 2. Note that for delays that are not heavy-tailed (which include a wide class of practical phenomena, e.g. Poisson, multinomial, Gaussian, etc.), sharp analysis can be obtained by positing the sub-exponential assumption. Therefore, we focus on the latter case.\n\n(b) Such an assumption is common and standard in prior works with theoretical guarantees under delayed feedback (e.g. [Howson et al 2023, Yang et al 2023]). The sub-exponential / sub-Gaussian assumptions are required in order to obtain proper posterior concentration results to prove sub-linear regret bounds. It allows us to obtain tighter bounds by utilizing nice distribution properties.\n\n(c) Our algorithms exhibit promising empirical performance even when the assumption is not satisfied. As shown in experiments (Section 5.1, figure 1(c)), with long-tail delays, the performance of our algorithms does not deteriorate whereas the UCBVI algorithm is suboptimal.\n\n(d) The statistical property of heavy-tailed delays in bandits is studied very recently (Jul 2023) by [Shi etc. 2023]. Nevertheless, this paper focuses on establishing statistical inference approaches and does not analyze the regret guarantee in this scenario. Still, It is unclear whether the result in this paper help achieve a better regret bound other than the one we discussed above in (a).\n \n(e) The i.i.d. assumption on delays is common in the existing theoretical literature. While the non-i.i.d.case is interesting, it is beyond the scope of the current work, and we thus leave it for future study.\n\nOnce again, thank you for dedicating time to reviewing our work and for providing valuable insights that will contribute to its improvement.\n\n    Reference:\n\nYunchang Yang,  et al. \"A reduction-based framework for sequential decision making with delayed feedback.\" arXiv preprint arXiv:2302.01477, 2023.\n\nShi, Lei, et al. \"Statistical Inference on Multi-armed Bandits with Delayed Feedback.\" ICML, 2023.\n\nLancewicki, Tal, et al. \"Learning adversarial markov decision processes with delayed feedback.\" Proceedings of the AAAI Conference on Artificial Intelligence. 2022.\n\nJin, Tiancheng, et al. \"Near-optimal regret for adversarial mdp with delayed bandit feedback.\" Advances in Neural Information Processing Systems 35, 2022.\n\nHowson, Benjamin, et al. \"Optimism and delays in episodic reinforcement learning.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2023.\n\nMondal, W. U., & Aggarwal, V. Reinforcement Learning with Delayed, Composite, and Partially Anonymous Reward. arXiv preprint arXiv:2305.02527, 2023."}, {"review_id": "Ako7dLvAZW", "reviewer": "Reviewer_U3pE", "summary": "The authors study the frequentist regret of TS under stochastic delayed feedback with linear function approximation. They further proposed using LMC as a posterior sampling strategy to improve computational efficiency.", "questions": "1. In Figure 1, why are there non-smooth jumps for average return of D-UCBVI\n2. Please provide some intuition on the bound of $N_k$ (how the condition number scales w.r.t K,H)\n3. To reduce computational complexity, one can also consider updating the parameters less frequently (the feedbacks come in with batches of episodes). I'm curious how this will scale the regret bound", "limitations": "Limitations are addressed as future work in Section 6", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "1. As far as I know, this is little work that develops frequentist regret bound with delayed feedback\n2. The paper provides a theoretical understanding of using LMC for posterior sampling", "weaknesses": "1. Overall, the theories look sound to me (I read Appendix B closely and skimmed Appendix C as it is very similar to Appendix B). However, the math is quite messy (such as missing/inconsistent notations, missing assumptions, incorrect references, incorrect constants, etc), which makes the proof hard to follow. Some examples (not exhaustive) are listed below but the manuscript should be proofread carefully\n    1. Definition 1 should include $r_h\\in[0,1]$ (given the value function is upper bounded by H-h+1)\n    2.  $\\tilde{V}$,  $\\tilde{Q}$ should be introduced or referred to algorithm 1 before using. in line 517, $\\tilde{V_h}^k$ is defined different from line 13 in algorithm 1.\n    3. In algorithm 1 line 7, $\\hat{w}$ should not be divided by $\\sigma^{-2}$\n    4. In theorem 2, $\\kappa_h$ is defined in appendix instead of the main manuscript. $\\eta_k$ is not used in theorem 2\n    5. In appendix section B, all Lemma C.5 should be B.8\n    6. Every lemma/theorem should use the phrase \"with probability **at least**\"\n    7. In Appendix line 648, please show that $\\theta=\\tilde{w}-\\hat{w}<=2H\\sqrt{d}$ as stated in the assumption of Lemma D.12  under event $\\tilde{E}$\n    8. In Lemma D.7, $d+2\\sqrt{dt}+2t \\neq 2(\\sqrt{d}+\\sqrt{t})^2$. The definition of constant $C_{H,d,k,M,\\delta}$ is wrong.\n2. The computational efficiency/overall performance of D-LPSVI should be demonstrated in high-dmensional domain\n3. Missing reference\n    - LMC is studied in general bandit setting (e.g. Mazumdar, Eric, et al. On Thompson Sampling with Langevin Algorithms)\n    - In the discussion of arbitrary delayed feedback, please include Wu, Han, and Stefan Wager. Thompson sampling with unrestricted delays.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate Reviewer U3pE's thorough evaluation of our work. We thank the reviewer for providing valuable feedback that will contribute to the refinement of our work.\n\n    1. Clarification on mathematical definitions and notation issues\nWe thank the reviewer for pointing out the unclear definition and missing details. We will address the issues related to notations and definitions in the revised manuscript to ensure consistency and correctness, which is an easy fix from the current version.\n\nWe would like to point out that:\n\n(a) We define $r_h: \\mathcal{S} \\times \\mathcal{A} \\rightarrow [0, 1]$ in Line 104.\n\n(b) The scaling of $\\sigma^{-2}$ comes from the calculation of Bayesian linear regression model, which appears when noise is not from standard Gaussian.\n\n(c) $\\eta_k$ is presented in theorem 2 as it is a parameter (learning rate) that is required to run Langevin Monte Carlo for Algorithm 2.\n\n    2. Performance validation of Delayed-LPSVI\nTheoretically, we show in theorem 2 that by adopting Langevin Monte Carlo as an approximate sampling scheme, Delayed-LPSVI enjoys the same regret guarantee as Delayed-PSVI. In addition, it further improves computational efficiency compared to Delayed-LPSVI. Empirically, in experiments, we also measure the computational efficiency in a set of synthetic linear MDPs. As shown Table 3 (Appendix E.2), Delayed-LPSVI requires the least number of episodes to achieve its highest expected return.\n\n    3. Related works\nWe have already cited the mentioned paper for LMC. In addition, we do provide a thorough discussion of LMC methods in different sequential decision-making frameworks in section 1.1 (related works). We thank the author for providing further reference for arbitrary delayed feedback. We will include it as well as the concurrent works that study RL with delayed feedback in our revised manuscript.\n\n    4. Clarification of Figure 1\nIt is known that in general, posterior sampling algorithms bear greater robustness in the presence of delays compared to UCB-based methods. The jump in Delayed-UCBVI suggests in the testing environments, it is shortsighted and prone to adopt sub-optimal policies with insufficient exploration. In comparison, Delayed-PSVI and Delayed-LPSVI are randomized Bayesian algorithms, and thus are more effective in discovering optimal policies.\n\n    5.  Intuition on the bound of $N_k$\nCondition number $\\kappa_h := \\frac{\\lambda_{\\max}(\\Omega^k_h)}{\\lambda_{\\min}(\\Omega^k_h)}$. In our case, the number of iterations $N_k$ required for Lagevin Monte Carlo to converge scales with $Polylog(H, K, d)$.\n\n    6. Comment on further reducing computational complexity\nTo consider updating the parameters less frequently, one can adopt low-switching schemes in RL, which is a different focus compared to the current work. It should be noted that with low-switching schemes, the benefit is to bring down the communication cost, but will not  further improve the performance. Our current algorithms achieve the optimal dependence on the parameters $d$ and $T$ under the class\nof posterior sampling algorithms. Careful choice of low-switching schemes is required to ensure the distribution shift is not significant in order to maintain the same optimal regret will, otherwise, regret can easily blow up.\n\nOnce again, thank you for your dedication to reviewing our submission and your valuable feedback that will contribute to the improvement of our work."}, {"review_id": "JU1hUIzS95", "reviewer": "Reviewer_7RMs", "summary": "The paper discusses the challenges of delayed feedback in real-world systems for reinforcement learning and proposes an optimistic algorithm that utilizes noise perturbation via posterior sampling to effectively explore. The algorithm is shown to achieve a worse-case regret that depends on the delay and time horizon, and the paper provides theoretical analysis and empirical results to support the effectiveness of the proposed algorithm.", "questions": "1. The proposed methods (encode value iteration, multi-round sampling) do not seem to be specifically designed for the delayed feedback case, could you explain why these techniques could improve the results with delayed feedback? Also, a straightforward approach could be just to apply PSRL with value iteration and only update the model when the feedback is received. How is that different from the current approach? If there are key differences, it would be a natural baseline missing from the current experimental section.\n2. In Table 1, there is no comparison with other algorithms that handle the delayed feedback problem. Is it possible to compare with other SOTA methods that also address this problem? Also, the same question applies to the experimental section.", "limitations": "The paper could benefit from a comprehensive discussion about its limitations like the linear assumption, synthetic experiments, etc.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper addresses a practical problem in reinforcement learning which is the challenge of delayed feedback in real-world systems.\n2. The paper provides both theoretical analysis and empirical results to support the effectiveness of the algorithm.", "weaknesses": "1. Algorithm-wise, it is not clear what is the core idea to handle the delayed feedback problem, i.e., the key difference between delayed PSVI and normal PSVI (normal PSVI could be adjusted to update only when the feedback is received to handle the delayed feedback case) (See Q1).\n2. Theory-wise, it is not clear what is the improvement from previous work also designed to handle delayed feedback (see Q2).\n3. Experimental-wise, it is good to see a comparison with UCB, but LSVI-UCB is not designed to handle delayed feedback. So it might not be a fair comparison (see Q2).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate Reviewer 7RMs' thorough evaluation of our work. We thank the reviewer for providing valuable feedback that will contribute to the refinement of our work.\n\n    1. Clarification of technical novelty (theory)\nTheory-wise, our main technical contributions and novelties are as follows:\n\n(a) Concentration: compared to the standard setting without delays, the posterior concentration is weaker when delays take place. An agent needs to take actions based on limited observed history and existing posteriors, which can cause distribution shift. The key is to show that even with weaker posterior concentration, our algorithm is able to achieve the desired concentration and anti-concentration criteria that guarantee the sub-linear regret. In particular, for algorithm 2, we show that the convergence guarantee provided by LMC is strong enough to yield approximate posteriors with high accuracy even with fewer available samples due to delays (Lemma C.2).\n\n(b) Delay errors: The presence of delays prohibits the direct application of Elliptical Potential Lemma to bound the term $\\sum_{k=1}^K||\\phi(s^k, a^k)||_{(\\Omega^k)^{-1}}$ in regret decomposition as in the non-delayed case. To address this issue, we decompose the covariance matrix of posteriors into two parts: a full design matrix and a complement matrix. Note that this design is dedicated to delayed settings and requires more careful analysis to bound the delayed error incurred. Details can be found in Appendix B.1, where Lemma B.3 and Lemma B.4 are the key lemmas in addressing it.\n\n    2. Clarification of technical novelty (algorithm)\nFrom the algorithmic perspective, we would like to highlight that,\n\n(a) We provably incorporate approximate sampling scheme by resorting to Langevin Monte Carlo (LMC) in algorithm 2, which is an important extension from the standard posterior sampling algorithms. By utilizing LMC, algorithm 2 is proved to enjoy computational efficiency while maintaining the same regret guarantee (Thm 2). Besides, owing to the ability of LMC, algorithm 2 (Delayed-LPSVI) is able to generate samples from arbitrarily complex posteriors in complex problem domains, where posterior distributions can be intractable without closed-form. When standard posterior sampling fails to capture the noise model accurately, algorithm 2 (Delayed-LPSVI) is expected to come into play. To the best of our knowledge, this is the first analysis that provably incorporates LMC in linear MDPs and jointly considers the effect of stochastic delays.\n\n(b) The general workflow of our algorithms follows a similar philosophy as posterior sampling in standard no-delay RL settings, but with multi-round parameter, the scaling factor of the posterior variance, and the resulting changes in Bayesian linear models that are adapted to account for the delays. This is expected, one can find that most algorithms that study delay feedback (e.g. [Vernade et al 2020, Yang et al 2023]) also result in similar algorithmic procedures as in no-delay setting, but require the computation of new confidence interval / exploration bonus / posterior variance due to the weaker concentration arising from delays. In general, this is challenging, as \n(i) we need to balance between concentration and anti-concentration to make sure the resulting posterior sampling algorithm provides optimistic estimates that do not deviate too much from the true values even when delays take place; (2) it is important to guarantee that the number of runs for sampling (i.e. multi-round parameter) has proper scaling in time horizon. We show that in Lemma B.7, our choice of M has order $Polylog(H, K, d, \\delta)$ and thus does not increase the complexity dependence.\n\n    3. Comparison with other algorithms under delayed feedback\nTheoretical understanding of delayed feedback is mainly studied in bandit settings, and is less underexplored in RL until very recently.  We summarize and compare our work with all existing theoretical works in RL with delayed feedback that we are aware of:\n\n(a) Different RL settings: while [Lancewicki et al. 2022] and [Jin et al. 2022] consider adversarial MDPs, concurrent works [Howson et al 2023] and [Mondal and Aggarwal 2023] study episodic tabular MDPs, our work focuses on linear MDPs. \n\n(b) In [Yang et al 2023], they propose a reduced framework for different sequential decision making problems. However, their framework relies on policy-switching schemes, which differ from our settings with fixed episodic length.\n\nTherefore, there is no prior theoretical work that studies exactly the same setting as ours. As mentioned above, the general algorithmic workflows in no-delay and delayed settings are similar, one can easily adapt the UCBVI algorithm to fit the delayed linear MDP setting and test the performance against it. For a fair comparison, we grid search to choose the optimal parameters for Dealyed-UCBVI in experiments.\n\nOnce again, thank you for dedicating time to reviewing our work and for providing valuable insights that will contribute to its improvement.\n\n    Reference:\nVernade, Claire, et al. \"Linear bandits with stochastic delayed feedback.\" International Conference on Machine Learning. PMLR, 2020.\n\nYang, Yunchang, et al. \"A Reduction-based Framework for Sequential Decision Making with Delayed Feedback.\" arXiv preprint arXiv:2302.01477 (2023).\n\nLancewicki, Tal, et al. \"Learning adversarial markov decision processes with delayed feedback.\" Proceedings of the AAAI Conference on Artificial Intelligence.  2022.\n\nJin, Tiancheng, et al. \"Near-optimal regret for adversarial mdp with delayed bandit feedback.\" Advances in Neural Information Processing Systems 35, 2022.\n\nHowson, Benjamin, et al. \"Optimism and delays in episodic reinforcement learning.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2023.\n\nMondal, W. U., & Aggarwal, V. Reinforcement Learning with Delayed, Composite, and Partially Anonymous Reward. arXiv preprint arXiv:2305.02527, 2023."}, {"review_id": "qZDhIwUaTU", "reviewer": "Reviewer_TvPe", "summary": "This paper introduces and analyzes two \"posterior sampling\" algorithms for learning optimal policies in linear MDPs in a setting where feedback from the environment is delayed (by stochastic amounts of time). The algorithms, called Delayed-PSVI and Delayed-LPSVI (namely Delayed (Langevin) Posterior Sampling Value Iteration) explore by randomly sampling value functions from some notion of a posterior, which concentrates on the optimal value function. The Delayed-LPSVI algorithm circumvents some computational burdens in the inference and sampling procedure of Delayed-PSVI, and instead performs the \"posterior sampling\" with noisy gradient descent updates (akin to SGLD). It is established that the Delayed-[L]PSVI algorithms achieve sublinear regret with respect to the time horizon, which grows linearly with the mean feedback delay. Comparing to a simple modification to an existing optimism-based algorithm for linear MDPs to handle the delayed feedback, the authors demonstrate empirically in some simple environments that their posterior sampling algorithms tend to earn high return more quickly (and it is implied therefore that regret grows more slowly).", "questions": "I am confused about how exactly the delayed feedback works. For example, in Algorithms 1, 2, 4, during the data collection phase, there is a comment saying \"Environment rollouts cannot be observed if there is a delay\". What does this mean? If the rollouts are not observed, which states are being fed to the policy to generate rollouts (i.e., how is $a_h^k\\sim\\pi_h^k(s_h^k)$ computed if $s_h^k$ is not observed)?\n\nThe only way I can see this working is if the agent can observe its trajectory online, but then cannot use the data it collects for updates until a random time in the future. But what is the motivation for such a model? ", "limitations": "As mentioned above, it is unclear what types of real problems are modeled by the particular delayed-feedback setting that is proposed.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "Delayed feedback is an interesting, relevant, and under-explored topic in RL research. This paper provides thorough analysis for posterior sampling algorithms with delayed feedback, with detailed analysis and with empirical evaluation. The algorithms appear to be reasonable and simple to implement.", "weaknesses": "Firstly, while I believe the problem of delayed feedback is an important one to study, I do not particularly understand the motivation and the logistics of the particular setting of delayed feedback that is studied in the paper. In this work, to my understanding, all data from an entire trajectory is kept hidden from the agent until a random future time. As I elaborate on further in the Questions section, I do not understand how hiding this information even allows any feedback control, and I cannot think of a real scenario that this delay models. There is very little discussion about the motivation for this setting.\n\nMoreover, it is not entirely clear to me how the delayed feedback makes the analysis of Delayed-[L]PSVI substantially different from the algorithms they're based on. Suppose that instead of the proposed algorithm, we employ [L]PSVI but only update the value function when new data becomes available. Intuitively, I would expect the regret to grow by a factor of $\\mathbb{E}[\\tau]$ roughly. It would be nice to have an intuitive understanding of how Delayed-[L]PSVI circumvents this multiplicative increase in regret.\n\nFurthermore, perhaps this is due to the fact that the paper proposes a new form of delayed feedback, but the baseline algorithm (to my understanding) is not actually rigorously justified. Thus, it is not clear that it is in fact the posterior sampling that explains the superior performance of Delayed-[L]PSVI.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate Reviewer TvPe's thoughtful review of our work. We are grateful for the detailed feedback, which provides valuable insights.\n\n    1. Common ground of delayed feedback definition with existing literature\nBy Definition 2, we call each trajectory (i.e. rollouts) $[s^t_h,a^t_h,r^t_h,s^t_{h+1}]_{h\\in[H]}$ as feedback at episode k. \n\nIn our algorithms, by saying \"Environment rollouts cannot be observed if there is a delay\", we mean that at episode $k$, if a non-negative delay $\\tau_k$ takes place, the feedback $[s^t_h,a^t_h,r^t_h,s^t_{h+1}]_{h\\in[H]}$ will not be observed until the end of episode $k+\\tau_k$. The formal definition of delayed feedback is provided at the end of Section 2 (Line 130 - 137), and the way to encode the delayed feedback in our algorithm is discussed in Line 179 - 183. \n\nEssentially, the introduction of delays causes the feedback in an episode to return at a future time $k+\\tau_k$.  As a result, at the beginning of episode $k+1$, the algorithm can only update posteriors using the observed feedback it has observed (feedback associated with episodes $i$ s.t. $i + \\tau_i < k + 1$),  but not feedback from all previous episodes $[i]_{i=1}^{k}$. \n\nNote that this setting is a counterpart of delayed feedback in bandit literature such as [Vernade et al 2023], where a censoring variable is defined for delayed feedback to indicate whether or not the reward in round $s$ is revealed by round $t$.  This setting is also similar to concurrent works for RL with delayed feedback, e.g. [Howson, et al 2023].\n\nThis setting is motivated by various practical scenarios. For instance, in recommender systems, feedback from users (e.g. clicks, purchases) often comes in a batched manner and may be observed only after a certain time window (i.e., delays occur by hours, days or even weeks depending on the types of feedback).  In clinical trials, the effectiveness of treatments can only be determined at a deferred time frame. Our setting is to model such sequential decision-making problems with delayed feedback.\n\nWe will further clarify the idea in our revised manuscript.\n\n    2. Contributions and novelties compared to the existing literature in delayed feedback\n\n(a) Existing bandit literature typically studies delays either in rewards or in the selection of arms independently. No prior work jointly studies the effect of delays that take place simultaneously in different aspects. However, in RL, delays can be observed not only in rewards, but also in state transitions, actions which in turn will also affect the transition. Therefore, in our work, we study a more challenging setting by considering delays with respect to the whole episodic trajectory that simultaneously includes transitions, actions, and rewards.\n\n(b) We study the more practical setting of stochastic delays, which is unknown and random at each episode, instead of making the simpler assumption that delays are fixed and constant.\n\n    3. Techincal clarification in obtaining sub-linear regret by controlling the delayed error\n\nIn our regret analysis, we decompose the regret into two parts, which capture the error from optimism and estimation respectively. To obtain a sublinear regret, we need to strike a balance between both terms. The presence of delays prohibits the direct application of Elliptical Potential Lemma to bound the term $\\sum_{k=1}^K||\\phi(s^k, a^k)||_{(\\Omega^k)^{-1}}$ in regret decomposition as in the non-delayed case. To address this issue, we decompose the covariance matrix of posteriors into two parts: a full design matrix and a complement matrix. Note that this design is dedicated to delayed settings and requires more careful analysis to bound the delayed error incurred. Details can be found in Appendix B.1, where Lemma B.3 and Lemma B.4 are the key lemmas in addressing it.\n\nOnce again, thank you for dedicating time to reviewing our work and for providing valuable insights that will contribute to its improvement.\n\n    Reference\n\nVernade, Claire, et al. \"Linear bandits with stochastic delayed feedback.\" International Conference on Machine Learning. PMLR, 2020.\n\nHowson, Benjamin, et al. \"Optimism and delays in episodic reinforcement learning.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2023."}]

Author rebuttal:
We sincerely thank all reviewers for insightful comments on our work. We are grateful that reviewers recognize the significance of addressing delayed feedback in RL; find our proposed algorithms to be a valuable contribution to this domain; and acknowledge that the theoretical analysis is thorough and sound; the setup is practical and useful; empirical comparisons are sufficient.

Our main contribution is to provide a theoretical understanding of posterior sampling algorithms in linear MDP (and linear bandits) under delayed feedback. We provide the first worst-case regret bound for posteror sampling algorithms in this scenario. In addition, we provably incorporate Langevin Monte Carlo (LMC) as an approximate sampling scheme to further improve the computation efficiency and to provide the feasibility in generalizing to more complex problem domains where posterior can be intractable.

We hope the individual responses addressed your questions and clarified our settings, and you may consider increasing the rating to support our work. We are happy to address further questions and feedback.

Meta-review: The concerns around technical novelty and others has been well addressed in the rebuttal. Thus I recommend acceptance.
Decision: Accept (poster)