A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learning
Authors: Christoph Dann
Mehryar Mohri
Tong Zhang
Julian Zimmert
Venue: NeurIPS 2021 Poster (2021)
Keywords: Reinforcement Learning
Posterior Sampling
Regret Bounds
Theory

Abstract: Thompson Sampling is one of the most effective methods for contextual bandits and has been generalized to posterior sampling for certain MDP settings. However, existing posterior sampling methods for reinforcement learning are limited by being model-based or lack worst-case theoretical guarantees beyond linear MDPs. This paper proposes a new model-free formulation of posterior sampling that applies to more general episodic reinforcement learning problems with theoretical guarantees. We introduce novel proof techniques to show that under suitable conditions, the worst-case regret of our posterior sampling method matches the best known results of optimization based methods. In the linear MDP setting with dimension, the regret of our algorithm scales linearly with the dimension as compared to a quadratic dependence of the existing posterior sampling-based exploration algorithms.

A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learning
Christoph Dann Google Research
Mehryar Mohri Google Research and NYU
Tong Zhang Google Research and HKUST
Julian Zimmert Google Research
Abstract
Thompson Sampling is one of the most effective methods for contextual bandits and has been generalized to posterior sampling for certain MDP settings. However, existing posterior sampling methods for reinforcement learning are limited by being model-based or lack worst-case theoretical guarantees beyond linear MDPs. This paper proposes a new model-free formulation of posterior sampling that applies to more general episodic reinforcement learning problems with theoretical guarantees. We introduce novel proof techniques to show that under suitable conditions, the worst-case regret of our posterior sampling method matches the best known results of optimization based methods. In the linear MDP setting with dimension, the regret our algorithm scales linearly with the dimension compared to a quadratic dependence of the existing posterior sampling-based exploration algorithms.
Introduction
key challenge in reinforcement learning problems is to balance exploitation and exploration. The goal is to make decisions that currently expected to yield high reward and that help identify less known but potentially better alternate decisions. In the special case of contextual bandit problems, this trade-off well understood and one of the most effective and widely used algorithms is Thompson sampling [Thompson, 1933]. Thompson sampling is a Bayesian approach that maintains posterior distribution of each arm being optimal for the given context. At each round, the algorithm samples an action from this distribution and updates the posterior with the new observation. The popularity of Thompson sampling stems from strong empirical performance [Li al., 2010], as well competitive theoretical guarantees in the form of Bayesian [Russo and Van Roy, 2014] and frequentist regret bounds [Kaufmann et al., 2012].
The results in the contextual bandit setting have motivated several adaptations Thompson sampling the more challenging Markov decision process (MDP) setting. Most common are model-based adaptations such as PSRL [Strens, 2000, Osband et al., 2013, Agrawal and Jia, 2017] or BOSS [Asmuth al., 2012], which maintain posterior distributions over MDP models. These algorithms determine their current policy by sampling a model from this posterior and computing the optimal policy for it. The benefit of maintaining posterior over models instead of the optimal policy or optimal value function directly is that posterior updates can be more easily derived and algorithms are easier to analyze. However, model-based approaches are limited small-scale problems where a realizable model class of moderate size is available and where computing the optimal policy of model computationally tractable. This rules out many practical problems where the observations are rich, e.g. images or text.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

There are also model-free posterior sampling algorithms that are inspired by Thompson sampling. These aim to overcome the limitation of model- bosel-based algorithms by only requiring a salue-function class and possibly weaker assumptions on the MDP model. Several algorithms have been proposed le.g. Osband et al., 20, Fortunato et al., 2017, Osband et al., 2018] with good empirical per- formance but with no theoretical performance guarantees. A notable exception is the randomized least-squares value iteration (RLSVI) algorithm by Osband et al. [2016b] that admits frequentist regret bounds in tabular [Russo. 2019] and linear Markiov decision processes [Zanette et al., 2020a]. However, to the best of our knowledge, no such results are available beyond the linear setting.
In contrast, there has been impressive recent progress in developing and analyzing provably efficient algorithms for more general problem classes based on the OFU (optimism in the face of uncer- tainty) principle. These works show that OFU-based algorithm can learn a good policy with small sample-complexity or regret as long as the value-function class and MDP satisfies general structural assumptions. Those assumptions include bounded Bellman rank [Jiang et al., 2017], low inherent Bellman error [Zanette al., 2020b], small Eluder dimension [Wang et al., 2020] or Bellman- Eluder dimension [Jin et al., 2021]. This raises the question of whether OFU-based algorithms are inherently more suitable for such settings or whether is possible to achieve similar results with a model-free posterior sampling approach. In this work, we answer this question by analyzing posterior sampling algorithm that works with a Q-function class and admits worst-case regret guarantees under general structural assumptions. Our main contributions are:
We derive model-free posterior sampling algorithm for reinforcement learning in general Markov decision processes and value function classes.
We introduce new proof technique for analyzing posterior sampling with optimistic priors.
We prove that this algorithm achieves near-optimal worst-case regret bounds that match the regret of OFU-based algorithms and improve the best known regret bounds for posterior sampling approaches.
1.1 Further Related Work
Several extension of TS have been proposed for non-linear function classes in contextual bandits [Zhang al., 2020, Kveton et al., 2020, Russo and Van Roy, 2014]. For tabular MDPs, Agrawal et al. [2020] improves the regret bounds for RLSVI and Xiong et al. [2021] show that an algorithm with randomized value functions can be optimal. the same setting, Pacchiano et al. [2020] proposed an optimism based algorithm that uses internal noise, which can be interpreted as a posterior sampling method. aafarniaJJhromn et al. [2021] analyzes a posterior sampling algorithm for tabular stochastic shortest path problems. Considering the Bayesian regret, the seminal paper of Osband and Van Roy [2014) provides a general posterior sampling RL method that can be applied to general model classes including linear mixture MDPs
2 Setting and Notation
Episodic Markov decision process. We consider the episodic Markov decision process (MDP) setting where the MDP is defined by the tuple (X,,,, A, H, P, r)) Here, X' and A are state and action spaces. The number H E N is the length of each episode and P = {P*} h= and R (R² ] H are the state transition probability measures and the random rewards. The agent interacts with the MDP in T episodes of length H. In each episode & E [T] = f1, ,,,,
hh
the agent first observes an initial state x! E X' and then, for each time step h E [H]. the agent takes an action af E AA and receives the next state 2 exposition, we assume that the initial states x| = x are identical across episodes. When initial states are stochastic, we can simply add a dummy initial state and increase H by to ensure this. Our approach can also be generalized to adversarial initial states which we discuss in the appendix. We denote by n X x [H] + A the agent's policy in the 1-th episode, that is, af = (x( h). For given policy n, the value functions are defined for all E [H] and state-action pairs (x, a) as
h+1 ph (-|æ,, af") and reward r Rh a²)). To simplify our
(1, a) (z( a) + E. ph (x,a) (+'),
(T( = Q7 π (2, h))
where (1, a) 1M [r*] E [0, 1] is the average immediate reward and V (*+ = 0 for convenience. We further denote by T the Bellman optimality operator that maps any state-action

---

function f to
(T, (x, a) + -E (t,o))
max a'EA
f( a')
The optimal Q-function is given by Qi = Th 1h+1 for all h E [H] where again Qis = 0.
Value function approximation. We assume the agent is provided with a Q-function class Fi x F2 ... x Fu of functions f [ where f": X' x A - R. For convenience, we also consider FH+1 {0} which only contains the constant zero function, and we define (xx)) = max.eA (x, a). Before each episode I, our algorithm selects a Q-function Ja E F and then picks actions in this episode with the greedy policy S w.r.t. this function. That is, at F (a) h) arg max ff (x²;
make the following assumptions on the value-function class: Assumption (Realizabilitty. The optimal Q-function is in the class Q7, Fv, for all h E [H].
Assumption 2 (Boundedness). There exists b 2 1 such that (" |0 for all x, a XxA and f = ( hee(m] E F.
Assumption (Completeness). For all h and pu+1 E FRt1, there is fhh E Fh such that fhh T pl+t1
Additional notation. For any fhh Fr. define the short-hand notation f*(x) max 1 (x, a) and for any f E F, h E [H] and state-action pair x, we define the Bellman residual as
Ef(fiz,a) E(f f az (T (z,
We measure the performance of algorithm that produces sequence of policies 1 ....... ..., by its regret
T R -((())
after T episodes.
3
Conditional Posterior Sampling Algorithm
We derive our posterior sampling algorithm by first defining the prior over the function class and our likelihood model of an episode given value function.
Optimistic prior.
We assume that the prior Po over F has the form
Po(f) exp(Af II (f
where p are distributions over each Fú and À > is parameter. This form assumes that the prior factorizes over time steps and that the prior for the value functions of the first time step prefers large values for the initial state. This optimistic preference helps initial exploration and allows to achieve frequentist regret bounds. A similar mechanism can be found in existing sampling based algorithms in the form of optimistic value initializations [Osband et al., 2018] forced initial exploration by default values [Zanette et al., 2020a).
Temporal difference error likelihood. Consider set of observations acquired in episodes To formulate the likelihood of these observations, we make use of the
S, = f2 a r/ squared temporal difference (TD) error, that for time h.
S.) = 1" pht1, E0 (att a!)) -r (
3

---

For h = H. we can choose Is arbitrarily since by definition (1++1(x) = 0 for all z. We now define the likelihood of S. given value function f as
1++1
H II exp (f p Ph exp( (nn f
p(S.f) x
(2)
where 17 >> O is a parameter. Readers familiar with model-free reinforcement learning methods likely find the use of squared temporal difference error in the numerator natural as it makes transition samples with small TD error more likely. Most popular model free algorithm such as Q-learning [Watkins and Dayan, 1992] rely on the TD error as their loss function. However, the normalization in the denominator of (2) may seem surprising. This term makes those transitions more likely that have small TD error under the specific f², fh+ pair compared to pairs (f, 1 with f is drawn from the prior. Thus, transitions are encouraged to explain the specific choice of f for fh+11 This normalization is one of our key algorithmic innovations. It allows us to related a small loss L to small bellman error and circumvent the double-sample issue [Baird, 1995, Dann et al., 2014] of the square TD error.
Combining the prior in (1) and likelihood in (2), obtain the posterior of our algorithm after t episodes
H a St),
p(f(s)) (xxp (x*))
(3)
1=1
1t exp (-mIL fht, ;
where a(f1)gh ,.)
B B exp( exp(-nIL' fh+t1;
Note that the conditional probability q(f 1f S)) samples f using the data St and the TD error T. T."(J" (Jhh ; St), which mimics the model update process of Q-learning, where fit the model f at each step & to the target computed from fh- The optimistic prior encourages exploration, which needed in our analysis. It was argued that such a term is necessary to achieve the optimal frequentist regret bound for Thompson sampling in the bandit case Zhang [2021]. For the same reason, employ it for the analysis of posterior sampling in episodic RL. The losses L will grow with the number of rounds t and once the effect of the first exp(Af' (z²)) factor has become small enough, the posterior essentially performs Bayesian least-squares regression of ft conditioned on fh+1, We thus call our algorithm conditional posterior sampling. This algorithm, shown in Algorithm simply samples Q-function fo from the posterior before the each episode, follows the greedy policy of fc for one episode and then updates the posterior.
Algorithm 1: Conditional Posterior Sampling Algorithm
Input: value function class FF learning rate 7), prior optimism parameter X, number of rounds T for t 1, 1.2..... do
Draw Q-function ft ~ p(-1S:-1) according to posterior (3)
Play episode using the greedy policy y. and add observations S,
We are not aware of a provably computationally efficient sampling procedure for (3). Since the primary focus of our work is statistical efficiency we leave it as an open problem for future work to investigate the empirical feasibility of approximate samplers or to identify function classes that allow for efficient sampling, Another potential improvement is to derive a conditional sampling rule that allows to sample (J. ( iteratively instead of jointly from a single posterior.
4 Regret of Conditional Posterior Sampling
We will now present our main theoretical results for Algorithm 1. As is common with reinforcement learning algorithms that work with general function classes and Markov decision processes, we express our regret bound terms of two main quantities: the effective size of the value function class FF and a structural complexity measure of the MDP in combination with F.

---

Function Class Term. In machine learning. the gap between the generalization error and the train- ing error can be estimated by an appropriately defined complexity measure of the target function class. The analyses of optimization- based algorithms often assume finite function classes for simplicity and measure their complexity as |F]] [Jiang et al., 2017] or employ some notion of covering number for F [Wang et al., 2020, Jin et al., 2021]. J. Since our algorithm is able to employ a prior Po over F which allows us to favor certain parts of the function space, our bounds instead depend on the complexity of F through the following quantity:
Definition 1. For any function f' E Fnt1. define the set File, f') {f E Fn: sups,a [f: fzx S e) of functions that have small Bellman envor with f for all state-action pairs. Using this set, we define
H
sup <(c)
Σ SEF
In Po (htll)
The quantity (e, f)) is the probability assigned by the prior to functions that approximately satisfy the Bellman equation with any state-action pair. Thus, the complexity x(e) small the prior is high for any / and k(() represents an approximate completeness assumption. In fact, Assumption 3 holds we expect x<(c) < co for all > O. In the simplest case where F is finite, [Ful is uniform and completeness holds exactly, we have
(f)
H |n
<<C)) S
Σ h=1
In F
Ve 2 0.
For parametric models, where each f 1 can be parameterized by a dddimensional parameter E 9r C TRdd then prior pà (0) on Ω4 induces prior p0 (f) on Fu(e, f). If Qn is compact, then we can generally assume that the prior satisfies sup, In PB((0:100' #1 Sc]] ddIn(c//c) for appropriate
constant d' that depends on the prior. If further f f& is Lipschitz in then we can assume that In po ( S. end In(ci/e) for constants og and eı > 0 that depend on the prior and the Lipschitz constants. This implies the following bound for d dimensional parameteric models
<<<) S Hddl(e///)).
(4)
Structural Complexity Measure In our regret analysis, we need to investigate the trade-off be- tween exploration and exploitation. The difficulty of exploration is measured by the structure complexity of the MDP. Similar to other complexity measures such as Bellman rank [Jiang et al., 2017], inherent Bellman error [Zanette et al., 2020b] or Fullder-FFuuer dimension [Jin et al., 2021] ], we use a complexity measure that depends on the Bellman residuals of the functions E F in our value function class. Our measure online decoupling coefficient quantifies the rate at which the average Bellman residuals can grow in comparison to the cumulative squared Bellman residuals:
(Online decoupling coefficient). For given MDP M, value function class F, time horizon T and parameter μ E Rt, we define the online decoupling coefficient dc(F, M, T, p) as the smallest number K so that for any sequence of functions (Ji and their greedy policies f Jee
Definition 2
H
Bay, (Ea(S ab))
H
T
B (En(sia" a
K 4p
t=1
A=1
t=1
The online decoupling coefficient can be bounded for various common settings, including tabular MDPs (by (T) and linear MDPs (by dHO((n where is the dimension). We defer detailed discussion of this measure with examples and its relation with other complexity notions to later.
Main Regret Bound. We are now ready state the main result of our work, which is frequentist (or worst-case) expected regret bound for Algorithm 1:
5

---

Theorem 1. Assume that parameter S 0.4b- is set sufficiently small and that Assumption 2 holds. Then for any O, the expected regret after I episodes of Algorithm on any MDP M bounded as
[T)) -c d TT 4X =1
2T x
6
À + 6T
where the expectation is over the samples drawn from the MDP and the algorithm's ' internal randomness. Let dc(F, T) be any bound suppe1 do(F, MT, p)) and df 1/40? and
TR(b/T2) F'de
Xb? 2 1, then our bound becomes
[[)) =0 (D (TM.)
V
(5)
For the simpler form of our regret bound in Equation (5), we chose specific À (the condition Ab2 2 1 easy to satisfy for large 7). However, we may also use that dc M, T, n/ (4X)) is an increasing function of to set À differently and achieve better tuned bound. To instantiate the general regret bound in Theorem I to specific settings, we first derive bounds on the decoupling coefficient in Section 4.1 and then state and discuss Theorem I for those settings in Section 4.2.
4.1 Decoupling Coefficient and its Relation to Other Complexity Measures
We present several previously studied settings for which the decoupling coefficient provably small.
Linear Markov decision processes. We first consider the linear MDP setting [Bradtke and Barto, 1996, Melo and Ribeiro, 2007] which was formally defined by Jin al. [2020] as:
Definition 3 (Linear MDP ) An MDP with feature map Φ X A - Rd is linear, if for any (1)
[H), there exist d unknown (signed) measures 14y- = (11 ...... Ph (d) over X and an unknown vector 0, Rd. such that for any (x.a) E X A. we have
(= (0(x, a), pn) (((x,) = (Ó(x, (e,,a),0))
We assume further [0 a)ll I 1 for all (x, E & x A. and (1 [10,1]) S for all E [H].
Since the transition kernel and expected immediate rewards are linear in given features 6. it is well known that the Q-function of any policy is also linear function in [Jin et al., 2020]. We further show in the following proposition that the decoupling coefficient is also bounded by O(dH In:;
Proposition 1. In linear MDPs, the linear function class F = ( -) If RI < (H + 1 - hi) h))d) satisfies Assumptions 1-3, and the decoupling coefficient for S 1 is bounded by
de(F, M,T,pi S 21 + In(2HT)).
Notably, since tabular MDPs are linear MDPs with dimension at most [ Proposition I implies that dc(F, M, T,, μ4) < 2 | (1t/((11Inn2111) +I(HHT)) in tabular MDPs. As compared to other complexity measures such as Eluder dimension, the bound of the decoupling coefficient generally exhibits an additional factor of H. This factor appears because the decoupling coefficient defined for the sum of all time steps [H] instead of the maximum. We chose the formulation with sums because it is advantageous when the complexity of the MDP of function class varies with h.
Generalized linear MDPs. Linear functions admit a straightforward generalization to include rich class of non-linear functions which have previously been studied by Wang et al. [2019, 2020] in the RL setting.
Definition 4 (Generalized linear models). For a given link function a: [-1,1] + [-1, such that lo' (x)) [k, K] Lipschitz constants the class of generalized linear models is
< K < oc, and a known feature map Φ : X x + Rd
::= ((x, - (((((,))) 10

---

As the following result shows, we can readily bound the decoupling coefficient for generalized linear Q-functions.
Proposition 2. (Fr))== are generalized linear models with Lipschitz constants k. K, and bounded
norm || S VdH for all h and all f E Fh, then the decoupling coefficient for any p S 1 is bounded by
K² (1 In(2HT)).
dc(F, (, - 2dH
R2
Bellman-Eludes Dimension. Finally in more generality, our decoupling coefficient small for instances with low Bellman- Eluder dimension [Jin et al., 2021]. Problems with low Bellman-Elue dimension include in decreasing order of generality: small Eluder dimension [Wang et al., 2020], generalized linear MDPs [Wang al., 2019], linear MDPs [Bradtke and Barto, 1996, Melo and Ribeiro, 2007], and tabular MDPs. Before stating our reduction of Bellman Eluder dimension to decoupling coefficient formally, we first restate the definition of Bellman Eluder dimension in the following three definitions:
Definition 5 (e-independence between distributions). Let G be a function class defined on X, and v, Mi...... Un. be probability measures over X. We say V/ is E --independent of (1 ... pn) with respect to G if there exists g E 9 such that VEi= (E (g)² Σ E, but [E > E.
Definition 6 ((Distributional Eluder (DE) dimension). Let G be a function class defined on X and be a family of probability measures over X. The distributional Eluder dimension dimpE II,)) is the length of the longest sequence {p1,....Pr Pn C. 11 such that there exists e' E where pi is -independent of , for all [n]]
Definition (Bellman Eluder (BE) dimension [Jin et al., 2021D. Let E == 8 (E : f
F} be the set of Bellman residuals induced by F at step h, and II = {
1H be a collection of H
probability measure families over X x A. The E-Bellman Eluder dimension of F with respect to II is defined as
dimBe [F, F,,1,))= == max dimpa(E, (E,11,)).
KE(H]
We show that the decoupling coefficient is small whenever the Bellman-Eludee dimension is small: Proposition Let IT y be the set of probability measures over X x at any step obtained by following the policy y for F. for all E >>
dimar(F,IL.e) Eln
then the decoupling coefficient for any μ S 1 is bounded by dc(F, M, T. p) S II)))(T))EH.
Bellman-rank, Another general complexity measure sufficient for provably efficient algorithms is the low Bellman-rank [Jiang al., 2017], which includes reactive POMDPs. As discussed in Jin et al. [2021]. a certain type of Bellman rank ("Q-type") implies bounded Bellman Eluder dimension (as defined above) and is thus also bounded decoupling coefficient. However, it is an open question if low Bellman-rank in the original definition [Jiang et al., 2017] implies a small decoupling coefficient. The main difference is that Bellman-rank considers measures induced by ~ TT TT,, whereas the decoupling coefficient always samples state and action from the same policy.
4.2 Interpretation of Theorem
We can instantiate Theorem I with all bounds on the decoupling coefficients derived in the previous section. To illustrate the results, we will present two specific cases. The first one is for finite function classes that are often considered for simplicity [e.g. Jiang et al., 2017J.
Corollary (Regret bound for finite function classes with completeness). Assume a finite function class F that satisfies Assumptions 1, 2 and 3 with range b = 2. Assume further that the stagewise prior
uniform (f) 1/1Fx), and FF = I [F,le Set parameters 1) = 0.1 and X v M.TF Then the expected regret of Algorithm after T episodes is bounded any MDP M as
T
E[Reg(T)] = O (Vac(F. M, Tln Iln
7

---

Note that this result can be generalized readily to infinite function-classes when we replace In |F| by an appropriate covering number (F, for small enough. In addition to finite function classes, we also illustrate Theorem 1 for linear Markov decision processes:
Corollary 2. Assume Algorithm is run on d-dimensional linear MDP with the function class from
Proposition 1. Assume further learning rate of n = 0.4H and X = V (HS(L4b(2HTT))
Tx(H/T²) Then the
expected regret after T episodes is bounded as
E Reg(T)) S
If the stage-wise priors pa are chosen uniformly, then n(c) = H Hd as in (4), and thus
E Reg((T) & <((F
Our regret bound improves the regret bound of 0(H2 VT + H for the sampling method OPT-RLSVI [Zanette et al., 2020a] factor of HH. It also improves the (dd H²VT) regret of UCB-LSVI [Jin et al., 2020] by factor of Vd. However, these algorithms are known to be computationally efficient in this setting, while the computational tractability of our method an open problem. Our regret bound also matches the bound of Zanette et al. [2020b] without misspecification once we account for the different boundedness assumption (b = 2 instead of b H 1) in this work.
would like to remark that
5 Proof Overview of Theorem 1
We provide detailed proof of Theorem in the appendix and highlight the main steps in this section. We start by presenting an alternate way to write the posterior in (3) that lends itself better to our analysis. To that end, we introduce some helpful notations.
We denote by Çu (2r at r TE[H the trajectory collected in the s-th episode. The notation E equivalent to T Moreover, in the following, the symbol S; at episode t contains all historic observations up to episode which include both { and {fa)eete]- These observations are generated in the order fI ~ po(-), Çi ~ Th J2 ~ p(-[Si); S2 ~ fa:....
We further define the TD error difference at episode as
AL ; :6)== (
(" d
-ha (x (1)
-(T) a r p
The term we subtract from the TD error is the sampling error of this transition for the Bellman error. With (x!(x))= (x') - (x ) defined as the error of and
k/(() 1m + Σ A
(htt;
1=1
+ In E Pamw
exp
Σ
ATM g
we can equivalently rewrite the posterior distribution (3) in the following form:
p(f[S(-1) oc exp (- Σ +t +
Note that in the definition of क. we have replaced (-) by (T) Although we do not need to know the Bellman operator T in the actual algorithm, in our theoretical analysis, it is equivalent to knowing the operator via the use A (.). This equivalence is possible with the temporal difference emror likelihood which we introduce in this paper, and this is the main technical reason why we choose this conditional posterior sampling distribution. the key observation that allows us to circumvent the double-sample issue discussed earlier.

---

With the new expression of posterior distribution, we can start the proof of Theorem I by using the following decomposition, referred the value-function enror decomposition in Jiang al. [2017].
H Exg (f)
-
We now write the expected instantaneous regret of episode t (scaled by X) using this decomposition as
SE
E (esppp((
(V](x*) (x")(
H Σ
1-1 Bng (Ex(fi:a)aa)) 22)
- Bf--p(118--
A =f att) -
- s=1
+ Es, pepp Sc-1)
ET (E ([(===/,,)))) (x
By summing over I,..., T, we obtain the following expression of cumulative expected regret
AE Reg(T) = Σ Es. 1I
(2')(x))))))))
pde
F..
(6)
To bound the first term on the RHS, we can use the definition of decoupling coefficient which gives that
X² _dc dc F,M,T, 71 4x
Σre ree
7
To complete the proof is remains to upper-bound the Fr terms in (6). To do start with the following bounds (Lemma and Lemma 4 in the appendix) which requires the realizability assumption:
E ()p((118-_1)
Σ $C xA)' +
inf E 5
Σ
$ ()(()) (fff))>'''6 (2') Imp(f))
hm1
<Ac + 4n(t - 1) + k(c).
(8)
The occurrence of the term x(E) here implicitly corresponds to the realizability assumption. It can also be shown (see Lemma 10) that
"
In pr exp -1) ( (L ph+1 (Mtt(,, (oHt..o) 6o
Σ Es. E Ex-p(-18-_.)
1=1
s=1
2 (2b + ( 1)H--(( - =((c),
which means that the expected log-partition function in the definition of conditional posterior distribution is small, and its effect is under control. The proof requires the completeness assumption, and the occurrence of the term ni() here implicitly corresponds the completeness assumption. By combining this incquality with (8), and by using the definition of é we obtain the following inequality
H t-1 AL" 6+1 (C) - (x)) -x) + In p()(S(-1)
Es, BBs-p(-1s-_n)
ΣΣ 4=1
II p/: (f
<Ac + n(t - 1)Hc(5c + 26) + 2x(c).
(9)

---

In this bound, we have removed the effect of pegrtttiioonn function in the definition of the conditional posterior probability, and the inequality bounds the expected cumulative squared TD error.
One can further establish a connection between squared TD error and Bellman residual, by showing (Lemmaa 5 and Lemma 8) that
H
,,)+,,,,++++ A 1ht (.) +.)++ + In D(f(S(-1)
Es, By-p(-19--1)
1
II P& (Pt))
H
AL ghtt + 0.5ln pls, p
2
Es.-
Bs-p((((-1))
7
h=1
t-1
20.250
Bs,-1
()) Bag, (Gl(fi="aa)))
==1Æ=1
By combining this bound with (9), we obtain
Fr =0.25m) ΣΣ Es... B) Buy, (Er(ftt at))² Brenpt
==1h=
Se + m1( 1)He(5e 26) + 2x(e).
This implies the following bound for the sum of FY term in (6):
Σ Fr S AeT + nlt 1)He(5e + 2b)T + 2x(c)T.
By combining this estimate with (7) and (6), we obtain
X² dd de (F,M,T, 7 4X
XE Aege((T) <
AeT - m((-1)HHell - 2b)T + 2x(c)T.
17
The choice of b/T implies the first bound of Theorem 1.
Conclusion
This paper proposed new posterior sampling algorithm for episodic reinforcement learning using conditional sampling with a temporal difference error likelihood. We show that posterior sampling methods achieve the same frequentist regret guarantees as algorithms based optimism in the face of uncertainty (OFU) in a wide range settings with general value function approximation. Our results thus suggest that there is statistical efficiency gap between OFU and posterior sampling algorithms. While our results are stated in expectation, it is possible to derive high probability bounds with slightly more complicated analysis.
One of the key open questions for provably efficient reinforcement learning under general assumptions such as low Bellman-Eluder dimension or Bellman rank is that of computational efficiency. No computationally tractable algorithm is known for such general settings. Although the computational complexity of sampling from the posterior in our algorithm is unknown, we hope that the addition of a sampling- based algorithm to the pool of sample-efficient algorithms this setting may provide additional tools to design statistically and computationally tractable algorithms.
10

---

References
Priyank Agrawal, Jinglin Chen, and Nan Jiang. Improved worst-case regret bounds for randomized least-squares value iteration. arXiv preprint 2Xxv:20100121633 2020.
Shipra Agrawal and Randy Jia.
Optimistic posterior sampling for reinforeement learn- ing: worst-case regret bounds. In Advances in Neural Information Processing Sys- tems, volume 30, 2017. URL https: https://ppooettee /ttpc//eeooee....pe/ee
approach exploration in reinforcement learning. arXiv preprint httpr/sss.c/ppppe/2/1///////////
3621f 1591111ffcccc9555005555555a55
Paper pdf.
John Asmuth, Lihong Li, Michael L Littman, Ali Nouri, and David Wingate, A bayesian sampling
2012.
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learning Proceedings 1995, pages 30-37, Elsevier, 1995.
Steven J Bradtke and Andrew Barto. Linear least-squares algorithms for temporal difference learning. Machine learning, 22(1):33-57, 1996.
Christoph Dann, Gerhard Neumann, Jan Peters, et al. Policy evaluation with temporal differences: survey and comparison. Journal of Machine Learning Research, 15:809-883, 2014.
Meire Fortunato, Mohammad Gheshlaghi Azar, Bilal Piot, Jacob Menick, Ian Oshand, Alex Graves, Vlad Mnih, Remi Munos, Demis Hassabis, Olivier Pietquin, et al. Noisy networks for exploration. arXiv preprint arXiv: 1706. 10295, 2017.
Mehdi Jafarnia-Jahromi, Liyu Chen, Rahul Jain, and Haipeng Luo. Online learning for stochastic shortest path model via posterior sampling. arXiv preprint arXiv:2106.00 00.30000053,,, 2021.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contex- tual decision processes with low bellman rank are pac-lcarnable. In International Conference Machine Learning, pages 7704-1713. PMLR, 2017.
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.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of problems, and sample-efficient algorithms. arXiv preprint arXiv:2102.0088 2021.
Emilie Kaufmann, Nathaniel Korda, and Rémi Munos. Thompson sampling: An asymptotically optimal finite-time analysis. In International conference on algorithmic learning theory, pages 199-213. Springer, 2012.
Branislav Kveton, Manzil Zaheer, Csaba Szepesvari. Lihong Li, Mohammad Ghavamzadeh, and Craig Boutilier. Randomized exploration in generalized linear bandits. International Conference on Artificial Intelligence and Statistics, pages 2066-2076 PMLR, 2020.
Lihong Li. Wei Chu, John Langford, and Robert Schapire. A contextual-bandee approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pages 661-670. 2010.
Francisco S Melo and M Isabel Ribeiro. Q-learnin with linear function approximation. In Interna- tional Conference on Computational Learning Theory, pages 308-322. Springer, 2007.
Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. arXiv preprint arXiv:/4066 1853, 2014.
Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. arXiv preprint arXiv: 2013.
Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn, arXiv preprint 162.02160..04621, 2016a.

---

Ian Osband, Benjamin Van Roy. and Zheng Wen. Generalization and exploration via randomized value functions. In International Conference on Machine Learning, pages 2377-2386. PMLR, 2016b.
Ian Osband, John Aslanides, and Albin Cassirer. Randomized prior functions for deep reinforcement learning. arXiv preprint 1rXiv:1806.03333 2018.
Aldo Pacchiano, Philip Ball, Jack Parker- Parker-Holder, Krzysztof Choromanski, and Stephen Roberts. On optimism in model-based reinforcement learning. arXiv preprint arXiv:2006. /991,, 2020.
Daniel Russo. Worst-case regret bounds for exploration via randomized value functions. arXiv preprint urXiv:1906.02870 2019.
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 39(4):1221-1244 2014.
Malcolm Strens. A bayesian framework for reinforcement learning. In ICML, volume 2000, pages 943-950. 2000.
William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4)2285-29) 294, 1933.
Ruosong Wang. Ruslan Salakhutdinov, and Lin F Yang. Provably efficient reinforcement learning with general value function approximation. arXiv preprint w:Xi::2005.10804 2020.
Yining Wang. Ruosong Wang. Simon S Du, and Akshay Krishnamurthy. Optimism reinforcement learning with generalized linear function approximation. arXiv preprint 19/2.4443 2019.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4):279-292, 1992.
Zhihan Xiong, Ruoqi Shen, and Simon S Du. Randomized exploration is near-optimal for tabular mdp. arXiv preprint arXiv:2102.09703 2021.
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro I Lazaric. Frequentist regret bounds for randomized least-squares value iteration. International Conference on Artificial Intelligence and Statistics, pages 1954-1964. PMLR, 2020a.
Andrea Zanette, Alessandro Lazaric. Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent bellman error. International Conference on Machine Learning, pages 1
PMLR, 2020b.
Tong Zhang. Data dependent concentration bounds for sequential prediction algorithms. In Interna- tional Conference on Computational Learning Theory, pages 173-187. Springer, 2005.
Tong Zhang. Feel-good thompson sampling for contextual bandits and reinforcement learning, 2021.
Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. arXiv preprint arXiv:2010.00827, 2020.
12


Reviews:
[{"review_id": "g0xL-W3CcpI", "reviewer": "Reviewer_JTUW", "summary": "This work introduces a conditional posterior sampling algorithm that is a model-free posterior sampling reinforcement learning algorithm and can be applied to general Markov decision processes and value function classes. Authors provide theoretical guarantees for the proposed algorithm.  Actually, it has been proved that the worst-case regret of the proposed algorithm is near-optimal and that improves the best known regret bounds for posterior sampling approaches (OPT-RLSVI, UCB-LSVI). The key component of the proposed algorithm is the definition of the likelihood over the collected samples (observations - state, action, reward) given a value function. To conclude, it is a theoretical work that shows that there is no statistical efficiency gap between OFU and posterior sampling algorithms. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Strengths**\n- This work introduces a conditional posterior sampling algorithm that is a model-free posterior sampling reinforcement learning algorithm that can be applied to general Markov decision processes.\n- Theoretical guarantees for the proposed algorithm are provided. The worst-case regret of the proposed algorithm is near-optimal\n- The worst-case regret of the algorithm improves the best known regret bounds for posterior sampling approaches, such as OPT-RLSVI, UCB-LSVI. Apart from that, it has been shown that a posterior sampling method can achieve the same guarantees with the OFU based algorithms.\n\n**Weaknesses**\n\n- The main limitation of this work is the lack of any empirical analysis. It would be of high importance for the reader to be able to check that the theoretical findings are aligned with those of the experiments (even on toy environments). \n- Another open question is if the proposed algorithm is actually applicable in practice.  As mentioned by the authors, the sampling of the posterior is not computationally tractable in its current form (Eq. 3).\n\nTo conclude, despite the theoretical guarantees of the proposed conditional posterior sampling algorithm, authors should make clear if this algorithm could be also applied in practice. \n\n**Minor comments/typos**\n- l. 150 pairs. -> pair,\n- l. 160: in comparison the the", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think that the limitations of this work have been adequately addressed by the authors", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "cJRyLlYQoN", "reviewer": "Reviewer_f4DA", "summary": "In this paper, the authors study the model-free posterior sampling algorithm for the episodic RL problem. A novel algorithm and analysis are proposed. The regret guarantee is proved, and specifically it depends on a term related to the function class, a term related to the structural complexity measure (decoupling coefficient), and other parameters. The authors also show the decoupling coefficient is small for linear MDPs, generalized linear MDPs, and Bellman-Eluder Dimension. When specialized to linear MDP, the regret bound matches Zanette et al. [2020b], thus statistically efficient. However, the algorithm suffers from computationally inefficiency.\n\n\n-----\nI have read the response and other reviews. I'll keep my original rating.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I really enjoy reading the paper and would like to thank the authors. As we know that most TS related algorithms are restricted to the linear MDP setting, this paper makes significant contribution by extending the framework to the more general settings. The definition of the prior and the likelihood function, and the analysis are new to me. Though the regret bound in Theorem 1 is hard to parse, the authors then instantiate that to the linear MDP setting and compare them with the existing results. Overall, the main text is easy to follow. The technical part is dense. I don’t have time to check the proof, so I am not able to evaluate the correctness of the result.\n\n-\tRecently, we have seen a boom of paper beyond the linear MDP setting in theoretical RL research. However, most algorithms are not related to TS. The authors propose a new algorithm that can handle the more general setting. They also introduce new quantities about the function class and the structural complexity measures and bring new analysis to the community. I think this initial step may boost the research in the related subarea.\n-\tI notice that the optimistic prior is not symmetric for all level h since it only includes $\\exp(\\lambda f^1(x^1))$. Can you comment on why this special definition is helpful for the analysis?\n-\tTheorem 1 itself is hard to parse, since we generally don’t know how large the $\\kappa$ terms and the decompiling coefficient terms are. I think the magnitude of $\\kappa$ is only investigated for the linear MDP case. Is it possible to obtain similar bounds of $\\kappa$ for other settings?\n-\tOne limitation of the algorithm is the computationally inefficiency. Besides, I think the algorithm requires the know ledge of $\\kappa$ and decompiling coefficient terms. Is this true? If so, is it possible to extend to the unknown case?\n-\tIn Corollary 2, it seems that the priors are assumed to chosen uniformly so that a bound on $\\kappa$ can be achieved. Is there any difficulty to extend it to more general priors?\n-\tThe regret bounds are the expected regret bounds. It is generally believed that the high-probability regret bound is stronger. Have you thought about proving high-probability regret bounds?\n-\tProbably because I didn’t check the proof in appendix carefully, I personally don’t find the proof sketch in Section 5 to be very helpful. It is still hard for me to digest the high-level idea of the proof after reading it. Maybe the authors can think about reorganizing this part or cutting some part of this section (for example some detail about how to bound $F_t^\\kappa$ term) and leave the space for other discussions.\n-\tRegarding the related literature, [1] and [2] are also quite related recent TS type algorithms. And currently there might be some technical issues in Xiong et al. [2021] as claimed by the authors.\n-\tIt would be better to discuss the tightness of the bound when specialized to the linear MDP setting. I think there are a few results about the lower bound in linear MDP, e.g. [3].\n\n[1] Agrawal, Priyank, Jinglin Chen, and Nan Jiang. \"Improved Worst-Case Regret Bounds for Randomized Least-Squares Value Iteration.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 8. 2021.\n[2] Jafarnia-Jahromi, Mehdi, et al. \"Online Learning for Stochastic Shortest Path Model via Posterior Sampling.\" arXiv preprint arXiv:2106.05335 (2021).\n[3] Zhou, Huozhi, et al. \"Nonstationary reinforcement learning with linear function approximation.\" arXiv preprint arXiv:2010.04244 (2020).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "NA", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "IMp_0BJ9NmH", "reviewer": "Reviewer_6qxa", "summary": "The authors propose a posterior-sampling algorithm for RL on a family of MDPs and value-function classes. Although an efficient sampling procedure is not given, the authors derive regret bounds for this family of MDPs that match (or improve) the existing bounds in expectation.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the presentation is clear and readable. Although the contribution is mainly theoretical and an efficient implementation of the algorithm is missing, I believe the work is significant enough for publication in NeurIPS.\n\nI did not check the proofs but the results and the arguments seem believable. In comparison with existing results (e.g. UCB-LSVI), it should probably be noted that the regret bound for posterior-sampling presented here is in expectation whereas the bounds in many existing works are with high-probability.\n\nSome minor glitches can be found here and there. I urge the authors to double-check everything. For example, in Line-69 P^h is defined for h=1...H whereas the definition of Q (Line-78) uses P^{h+1} so apparently P is needed for h=2....(H+1). This is distracting for the astute reader.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "6rglaFS0vNP", "reviewer": "Reviewer_ESrm", "summary": "The work proposes a new Thompson-sampling inspired exploration algorithm for exploration with general function approximation.", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is written clearly and nicely organized.\n\nThe TS-inspired algorithm examined in this work can function on most of the recently proposed settings, i.e., Bellman completeness, Bellman Eluder dimension etc.. A new complexity measure (Online decoupling coefficient) is introduced and connects nicely with other definitions.\n\nA Thompson sampling algorithm, when designed correctly, has 3 major benefits beyond ofter superior empirical performance:\n\n- it is computationally efficient, as it requires sampling instead of solving a potentially non convex optimization problem \n- it avoids the construction of confidence intervals, which can be an issue with complex approximators\n- a similar algorithmic structure generalizes across different settings\n\nThe current proposal here is not computationally efficient. In my opinion, this is a major dealbreaker.\n\nTo my understanding, all optimization based works (e.g., Zanette et al ‘20, Jin et al. '21 etc) that are computationally intractable admit an easy randomized version which is also computationally intractable: simply sample from the feasible set until a near-optimal solution is found. One can check, that a good enough solution is normally found after exponentially (in d,H for the simple linear case) many samples.\n\nIn this light, I'm not sure how this work differs from those that are intractable and do not explicitly introduce randomization; randomization here seems to be an ineffective way to solve a complex problem and does not bring advantages compared to non-randomized methods. I think the work looses the spirit of TS algorithms and does not make significant algorithmic or analytical contribution into the correct design and use of randomization to tackle complex reinforcement learning problems.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "not applicable", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a well-written and interesting paper.  However, as multiple reviewers pointed out, its not clear whether the approach considered is computationally viable.  As one of the reviewers suggests, this could be a dealbreaker.  At the same time, I do appreciate that the work in sorting out sample complexity for value function sampling under these idealized conditions.  After thinking about this some, I am inclined to recommend accepted.
Decision: Accept (Poster)