A Provably Efficient Model-Free Posterior Sampling Method for Episodic Reinforcement Learning
Year: 2022

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.

text: 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.

heading: 1 Introduction
text: A key challenge in reinforcement learning problems is to balance exploitation and exploration. The goal is to make decisions that are 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 is 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 a 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 et al., 2010], as well as 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 of Thompson sampling to 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 et al., 2012], which maintain a 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 a 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 to small-scale problems where a realizable model class of moderate size is available and where computing the optimal policy of a model is 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 (NeurIPS 2021).
There are also model-free posterior sampling algorithms that are inspired by Thompson sampling. These aim to overcome the limitation of model-based algorithms by only requiring a value-function class and possibly weaker assumptions on the MDP model. Several algorithms have been proposed [e.g. Osband et al., 2016a, Fortunato et al., 2017, Osband et al., 2018] with good empirical performance 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 uncertainty) 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 et 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 it is possible to achieve similar results with a model-free posterior sampling approach. In this work, we answer this question by analyzing a 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 a model-free posterior sampling algorithm for reinforcement learning in general Markov decision processes and value function classes.
• We introduce a 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.

heading: 1.1 Further Related Work
text: Several extension of TS have been proposed for non-linear function classes in contextual bandits [Zhang et 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. In 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. Jafarnia-Jahromi 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.

heading: 2 Setting and Notation
text: 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 ∈ N is the length of each episode and P = {Ph}Hh=1 and R = {Rh}Hh=1 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 t ∈ [T ] = {1, 2, . . . , T}, the agent first observes an initial state x1t ∈ X and then, for each time step h ∈ [H], the agent takes an action aht ∈ A and receives the next state xh+1t ∼ Ph(·|xht , aht ) and reward rht ∼ Rh(·|xht , aht ). To simplify our exposition, we assume that the initial states x1t = x
1 are identical across episodes. When initial states are stochastic, we can simply add a dummy initial state and increase H by 1 to ensure this. Our approach can also be generalized to adversarial initial states which we discuss in the appendix. We denote by πt : X × [H] → A the agent’s policy in the t-th episode, that is, aht = πt(xht , h). For a given policy π, the value functions are defined for all h ∈ [H] and state-action pairs (x, a) as
Qπh(x, a) = r h(x, a) + Ex′∼Ph(x,a) [ V πh+1(x ′) ] , V πh (x) = Q π h(x, π(x, h)) ,
where rh(x, a) = Erh∼Rh(x,a)[rh] ∈ [0, 1] is the average immediate reward and V πH+1(x) = 0 for convenience. We further denote by T ?h the Bellman optimality operator that maps any state-action
function f to
[T ?h f ] (x, a) = rh(x, a) + Ex′∼Ph(x,a) [ max a′∈A f(x′, a′) ] .
The optimal Q-function is given by Q?h = T ?h Q?h+1 for all h ∈ [H] where again Q?H+1 = 0.
Value function approximation. We assume the agent is provided with a Q-function class F = F1 × F2 × · · · × FH of functions f = {fh}h∈[H] where fh : X × A → R. For convenience, we also consider FH+1 = {0} which only contains the constant zero function, and we define fh(x) = maxa∈A f
h(x, a). Before each episode t, our algorithm selects a Q-function ft ∈ F and then picks actions in this episode with the greedy policy πft w.r.t. this function. That is, aht = πft(x h t , h) ∈ arg maxa∈A fht (xht , a).
We make the following assumptions on the value-function class: Assumption 1 (Realizability). The optimal Q-function is in the class Q?h ∈ Fh for all h ∈ [H]. Assumption 2 (Boundedness). There exists b ≥ 1 such that fh(x, a) ∈ [0, b−1] for all x, a ∈ X×A and f = {fh}h∈[H] ∈ F . Assumption 3 (Completeness). For all h and fh+1 ∈ Fh+1, there is a fh ∈ Fh such that fh = T ?h fh+1.
Additional notation. For any fh ∈ Fh, we define the short-hand notation fh(x) = maxa∈A f
h(x, a) and for any f ∈ F , h ∈ [H] and state-action pair x, a, we define the Bellman residual as
Eh(f ;x, a) = E(fh, fh+1;x, a) = fh(x, a)− T ?h fh+1(x, a) . We measure the performance of an algorithm that produces a sequence of policies π1, π2, . . . , by its regret
Reg(T ) = T∑ t=1 (V ?1 (x 1)− V πt1 (x1))
after T episodes.

heading: 3 Conditional Posterior Sampling Algorithm
text: We derive our posterior sampling algorithm by first defining the prior over the function class and our likelihood model of an episode given a value function.
Optimistic prior. We assume that the prior p0 over F has the form
p0(f) ∝ exp(λf1(x1)) H∏ h=1 ph0 (f h) (1)
where ph0 are distributions over each Fh and λ > 0 is a 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 us 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] or forced initial exploration by default values [Zanette et al., 2020a].
Temporal difference error likelihood. Consider a set of observations acquired in t episodes St = {xhs , ahs , rhs }s∈[t],h∈[H]. To formulate the likelihood of these observations, we make use of the squared temporal difference (TD) error, that for time h, is
Lh(f ;St) = L h(fh, fh+1;St) = t∑ s=1 (fh(xhs , a h s )− rhs − fh+1(xh+1s ))2 .
For h = H , we can choose xH+1s arbitrarily since by definition f H+1(x) = 0 for all x. We now define the likelihood of St given a value function f ∈ F as
p(St|f) ∝ H∏ h=1
exp ( −ηLh(fh, fh+1;St) ) Ef̃h∼ph0 exp(−ηL h(f̃h, fh+1;St)) , (2)
where η > 0 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 fh, fh+1 pair compared to pairs (f̃ , fh+1) with f̃ is drawn from the prior. Thus, transitions are encouraged to explain the specific choice of fh for fh+1. This normalization is one of our key algorithmic innovations. It allows us to related a small loss Lh to a 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), we obtain the posterior of our algorithm after t episodes
p(f |St) ∝ exp(λf1(x1)) H∏ h=1 q(fh|fh+1, St), (3)
where q(fh|fh+1, St) = ph0 (f
h) exp ( −ηLh(fh, fh+1;St) ) Ef̃h∼ph0 exp(−ηL h(f̃h, fh+1;St)) .
Note that the conditional probability q(fh|fh+1, St) samples fh using the data St and the TD error Lh(fh, fh+1;St), which mimics the model update process of Q-learning, where we fit the model fh at each step h to the target computed from fh+1. The optimistic prior encourages exploration, which is 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, we employ it for the analysis of posterior sampling in episodic RL. The losses Lh will grow with the number of rounds t and once the effect of the first exp(λf1(x1)) factor has become small enough, the posterior essentially performs Bayesian least-squares regression of fh conditioned on fh+1. We thus call our algorithm conditional posterior sampling. This algorithm, shown in Algorithm 1 simply samples a Q-function ft from the posterior before the each episode, follows the greedy policy of ft for one episode and then updates the posterior.
Algorithm 1: Conditional Posterior Sampling Algorithm Input: value function class F , learning rate η, prior optimism parameter λ, number of rounds T
1 for t = 1, 2, . . . , T do 2 Draw Q-function ft ∼ p(·|St−1) according to posterior (3) 3 Play episode t using the greedy policy πft and add observations to St
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 (fht ) H h=1 iteratively instead of jointly from a single posterior.

heading: 4 Regret of Conditional Posterior Sampling
text: 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 in terms of two main quantities: the effective size of the value function class F 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 training 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]. Since our algorithm is able to employ a prior p0 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 ′ ∈ Fh+1, we define the set Fh( , f ′) ={ f ∈ Fh : supx,a |Eh(f, f ′;x, a)| ≤ } of functions that have small Bellman error with f ′ for all state-action pairs. Using this set, we define
κ( ) = sup f∈F H∑ h=1 ln 1 ph0 (Fh( , fh+1)) .
The quantity ph0 (Fh( , f)) is the probability assigned by the prior to functions that approximately satisfy the Bellman equation with f in any state-action pair. Thus, the complexity κ( ) is small if the prior is high for any f and κ( ) represents an approximate completeness assumption. In fact, if Assumption 3 holds we expect κ( ) < ∞ for all > 0. In the simplest case where F is finite, ph0 (f) = 1 |Fh| is uniform and completeness holds exactly, we have
κ( ) ≤ H∑ h=1 ln |Fh| = ln |F| ∀ ≥ 0 .
For parametric models, where each fh = fhθ can be parameterized by a d-dimensional parameter θ ∈ Ωh ⊂ Rd, then a prior ph0 (θ) on Ωh induces a prior ph0 (f) on Fh( , f). If Ωh is compact, then we can generally assume that the prior satisfies supθ ln
1 ph0 ({θ′:‖θ′−θ‖≤ }) ≤ d ln(c′/ ) for an appropriate constant c′ > 0 that depends on the prior. If further fh = fhθ is Lipschitz in θ, then we can assume that ln 1
ph0 (Fh( ,fh+1)) ≤ c0d ln(c1/ ) for constants c0 > 0 and c1 > 0 that depend on the prior and
the Lipschitz constants. This implies the following bound for d dimensional parameteric models
κ( ) ≤ c0Hd ln(c1/ ). (4)
Structural Complexity Measure In our regret analysis, we need to investigate the trade-off between 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 Bellman-Eluder dimension [Jin et al., 2021], we use a complexity measure that depends on the Bellman residuals of the functions f ∈ 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:
Definition 2 (Online decoupling coefficient). For a given MDP M , value function class F , time horizon T and parameter µ ∈ R+, we define the online decoupling coefficient dc(F ,M, T, µ) as the smallest number K so that for any sequence of functions {ft}t∈N and their greedy policies {πft}t∈N
H∑ h=1 T∑ t=1 [ Eπft [Eh(ft;x h, ah)] ] ≤ µ H∑ h=1 T∑ t=1 [ t−1∑ s=1 Eπfs [Eh(ft;x h, ah)2] ] + K 4µ .
The online decoupling coefficient can be bounded for various common settings, including tabular MDPs (by |X ||A|HO(lnT )) and linear MDPs (by dHO(lnT ) where d is the dimension). We defer a detailed discussion of this measure with examples and its relation with other complexity notions to later.
Main Regret Bound. We are now ready to state the main result of our work, which is a frequentist (or worst-case) expected regret bound for Algorithm 1:
Theorem 1. Assume that parameter η ≤ 0.4b−2 is set sufficiently small and that Assumption 2 holds. Then for any β > 0, the expected regret after T episodes of Algorithm 1 on any MDP M is bounded as
E[Reg(T )] ≤λ η
dc ( F ,M, T, η
4λ
) + 2T
λ κ(b/T β) +
6HT 2−β
λ + bT 1−β ,
where the expectation is over the samples drawn from the MDP and the algorithm’s internal randomness. Let dc(F ,M, T ) be any bound on supµ≤1 dc(F ,MT, µ) and set η = 1/4b2 and λ = √
Tκ(b/T 2) b2dc(F,M,T ) . If λb 2 ≥ 1, then our bound becomes
E[Reg(T )] =O ( b √ dc (F ,M, T )κ(b/T 2)T + dc (F ,M, T ) + √ H ) . (5)
For the simpler form of our regret bound in Equation (5), we chose a specific λ (the condition λb2 ≥ 1 is easy to satisfy for large T ). However, we may also use that λ2dc(F ,M, T, η/(4λ)) is an increasing function of λ to set λ differently and achieve a better tuned bound. To instantiate the general regret bound in Theorem 1 to specific settings, we first derive bounds on the decoupling coefficient in Section 4.1 and then state and discuss Theorem 1 for those settings in Section 4.2.

heading: 4.1 Decoupling Coefficient and its Relation to Other Complexity Measures
text: We present several previously studied settings for which the decoupling coefficient is 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 et al. [2020] as: Definition 3 (Linear MDP ). An MDP with feature map φ : X × A → Rd is linear, if for any h ∈ [H], there exist d unknown (signed) measures µh = (µ(1)h , . . . , µ (d) h ) over X and an unknown vector θh ∈ Rd, such that for any (x, a) ∈ X ×A, we have
Ph(· |x, a) = 〈φ(x, a), µh(·)〉, rh(x, a) = 〈φ(x, a), θh〉 .
We assume further ‖φ(x, a)‖ ≤ 1 for all (x, a) ∈ X ×A, and max{‖µh(X )‖, ‖θh‖} ≤ √ d for all h ∈ [H].
Since the transition kernel and expected immediate rewards are linear in given features φ, it is well known that the Q-function of any policy is also a linear function in φ [Jin et al., 2020]. We further show in the following proposition that the decoupling coefficient is also bounded by O(dH lnT ):
Proposition 1. In linear MDPs, the linear function class F = ⊗H
h=1{〈φ(·, ·), f〉 | f ∈ Rd, ‖f‖ ≤ (H + 1− h) √ d} satisfies Assumptions 1-3, and the decoupling coefficient for µ ≤ 1 is bounded by
dc(F ,M, T, µ) ≤ 2dH(1 + ln(2HT )).
Notably, since tabular MDPs are linear MDPs with dimension at most |X ||A|, Proposition 1 implies that dc(F ,M, T, µ) ≤ 2|X ||A|H(1 + ln(2HT )) 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 is 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 a 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 σ : [−1, 1]→ [−1, 1] such that |σ′(x)| ∈ [k,K] for Lipschitz constants 0 < k ≤ K <∞, and a known feature map φ : X×A → Rd, the class of generalized linear models is
G := {(x, a)→ σ(〈φ(x, a), θ〉 | θ ∈ Θ ⊂ Rd} .
As the following result shows, we can readily bound the decoupling coefficient for generalized linear Q-functions. Proposition 2. If (Fh)Hh=1 are generalized linear models with Lipschitz constants k,K, and bounded norm ‖f‖ ≤ √ dH for all h and all f ∈ Fh, then the decoupling coefficient for any µ ≤ 1 is bounded by
dc(F ,M, T, µ) ≤ 2dHK 2
k2 (1 + ln(2HT )).
Bellman-Eluder Dimension. Finally in more generality, our decoupling coefficient is small for instances with low Bellman-Eluder dimension [Jin et al., 2021]. Problems with low Bellman-Eluder dimension include in decreasing order of generality: small Eluder dimension [Wang et al., 2020], generalized linear MDPs [Wang et 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 (ε-independence between distributions). Let G be a function class defined on X , and ν, µ1, . . . , µn be probability measures over X . We say ν is ε-independent of {µ1, µ2, . . . , µn} with respect to G if there exists g ∈ G such that √∑n i=1(Eµi [g])2 ≤ ε, but |Eν [g]| > ε. 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 dimDE(G,Π, ε) is the length of the longest sequence {ρ1, . . . , ρn} ⊂ Π such that there exists ε′ > ε where ρi is ε′-independent of {ρ1, . . . , ρi−1} for all i ∈ [n]. Definition 7 (Bellman Eluder (BE) dimension [Jin et al., 2021]). Let E := ⊗H h=1{Eh(f ;x, a) : f ∈ F} be the set of Bellman residuals induced by F at step h, and Π = {Πh}Hh=1 be a collection of H probability measure families over X ×A. The ε-Bellman Eluder dimension of F with respect to Π is defined as
dimBE(F ,Π, ε) := max h∈[H] dimDE(E ,Π, ε) .
We show that the decoupling coefficient is small whenever the Bellman-Eluder dimension is small: Proposition 3. Let Π = DF be the set of probability measures over X ×A at any step h obtained by following the policy πf for f ∈ F . If for all ε > 0
dimBE(F ,Π, ε) ≤ E ln 1
ε ,
then the decoupling coefficient for any µ ≤ 1 is bounded by dc(F ,M, T, µ) ≤ 4(1 + ln(T ))EH .
Bellman-rank. Another general complexity measure sufficient for provably efficient algorithms is the low Bellman-rank [Jiang et 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 a 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 x ∼ πf , a ∼ πf ′ , whereas the decoupling coefficient always samples state and action from the same policy.

heading: 4.2 Interpretation of Theorem 1
text: We can instantiate Theorem 1 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., 2017]. Corollary 1 (Regret bound for finite function classes with completeness). Assume a finite function classF that satisfies Assumptions 1, 2 and 3 with range b = 2. Assume further that the stagewise prior is uniform ph0 (f) = 1/|Fh|, and |F| = ∏H h=1 |Fh|. Set parameters η = 0.1 and λ = √ T ln |F|
dc(F,M,T ) . Then the expected regret of Algorithm 1 after T episodes is bounded on any MDP M as
E[Reg(T )] = O (√ dc(F ,M, T )T ln |F| ) .
Note that this result can be generalized readily to infinite function-classes when we replace ln |F| by an appropriate covering number N∞(F , ) for small enough. In addition to finite function classes, we also illustrate Theorem 1 for linear Markov decision processes: Corollary 2. Assume Algorithm 1 is run on a d-dimensional linear MDP with the function class from Proposition 1. Assume further a learning rate of η = 0.4H−2 and λ = √ Tκ(H/T 2)
dH3(1+ln(2HT )) . Then the expected regret after T episodes is bounded as
E[Reg(T )] ≤ O(H3/2 √ dTκ(H/T 2) ln(HT )) .
If the stage-wise priors ph0 are chosen uniformly, then κ( ) = HdO(ln(Hd )) as in (4), and thus
E[Reg(T )] ≤ O(H2d √ T ln(dHT )) .
Our regret bound improves the regret bound of Õ(H2.5d2 √ T +H5d4) for the posterior-sampling method OPT-RLSVI [Zanette et al., 2020a] by a factor of √ Hd. It also improves the Õ(d3/2H2 √ T ) regret of UCB-LSVI [Jin et al., 2020] by a factor of √ d. However, we would like to remark that these algorithms are known to be computationally efficient in this setting, while the computational tractability of our method is 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.

heading: 5 Proof Overview of Theorem 1
text: We provide a detailed proof of Theorem 1 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 ζs = {xhs , ahs , rhs }h∈[H] the trajectory collected in the s-th episode. The notation Eπfs is equivalent to Eζs∼πfs . Moreover, in the following, the symbol St at episode t contains all historic observations up to episode t, which include both {ζs}s∈[t] and {fs}s∈[t]. These observations are generated in the order f1 ∼ p0(·), ζ1 ∼ πf1 , f2 ∼ p(·|S1), ζ2 ∼ πf2 , . . .. We further define the TD error difference at episode s as
∆Lh(fh, fh+1; ζs) = ( f h(xhs , a h s )− rhs − fh+1(xh+1s ))2
−(T ?h fh+1(xhs , ahs )− rhs − fh+1(xh+1s ))2.
The term we subtract from the TD error is the sampling error of this transition for the Bellman error. With ∆f1(x1) = f1(x1)−Q?1(x1) defined as the error of f1 and
Φ̂ht (f) =− ln ph0 (fh) + η t−1∑ s=1 ∆Lh(fh, fh+1; ζs)
+ lnEf̃h∼ph0 exp ( − η t−1∑ s=1 ∆Lh(f̃h, fh+1; ζs) ) ,
we can equivalently rewrite the posterior distribution (3) in the following form: p(f |St−1) ∝ exp ( − H∑ h=1 Φ̂ht (f) + λ∆f 1(x1) ) .
Note that in the definition of Φ̂, we have replaced Lh(·) by ∆Lh(·). Although we do not need to know the Bellman operator T ?h in the actual algorithm, in our theoretical analysis, it is equivalent to knowing the operator via the use of ∆Lh(·). This equivalence is possible with the temporal difference error likelihood which we introduce in this paper, and this is the main technical reason why we choose this conditional posterior sampling distribution. It is 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 1 by using the following decomposition, referred to the value-function error decomposition in Jiang et al. [2017],
V ?1 (x 1)− V πft1 (x1) = H∑ h=1 Eπft [Eh(ft, x h t , a h t )]−∆f1t (x1).
We now write the expected instantaneous regret of episode t (scaled by λ) using this decomposition as
λESt−1Eft∼p(·|St−1)[V ? 1 (x 1)− V πft1 (x1)]
=ESt−1Eft∼p(·|St−1) H∑ h=1 [ λEπftEh(ft, x h t , a h t )− η 4 t−1∑ s=1 Eπfs (Eh(ft;x h s , a h s )) 2 ] ︸ ︷︷ ︸
Fdct + ESt−1Eft∼p(·|St−1) [ H∑ h=1 η 4 t−1∑ s=1 Eπfs (Eh(ft;x h s , a h s )) 2 − λ∆f1t (x1) ]
︸ ︷︷ ︸ Fκt
.
By summing over t = 1, . . . , T , we obtain the following expression of cumulative expected regret
λEReg(T ) = λ T∑ t=1 ESt−1Eft∼p(·|St−1)[V ? 1 (x 1)− V πft1 (x1)] = T∑ t=1 F dct + T∑ t=1 Fκt . (6)
To bound the first term on the RHS, we can use the definition of decoupling coefficient which gives that
T∑ t=1 F dct ≤ λ2 η dc ( F ,M, T, η 4λ ) . (7)
To complete the proof is remains to upper-bound the Fκt terms in (6). To do so we start with the following bounds (Lemma 1 and Lemma 4 in the appendix) which requires the realizability assumption:
Ef∼p(·|St−1) ( H∑ h=1 Φ̂ht (f)− λ∆f1(x1) + ln p(f |St−1) )
= inf p Ef∼p(·) ( H∑ h=1 Φ̂ht (f)− λ∆f1(x1) + ln p(f) )
≤λ + 4η(t− 1)H 2 + κ( ). (8)
The occurrence of the term κ( ) here implicitly corresponds to the realizability assumption. It can also be shown (see Lemma 10) that
H∑ h=1 ESt−1 Ef∼p(·|St−1) [ lnEf̃h∼ph0 exp ( −η t−1∑ s=1 ∆Lh(f̃h, fh+1, ζs) )] ≥− η (2b+ )(t− 1)H − κ( ),
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 κ( ) here implicitly corresponds to the completeness assumption. By combining this inequality with (8), and by using the definition of Φ̂, we obtain the following inequality
ESt−1Ef∼p(·|St−1) ( η H∑ h=1 t−1∑ s=1 ∆Lh(fh, fh+1, ζs)− λ∆f1(x1) + ln p(f |St−1)∏H h=1 p h 0 (f h) ) ≤λ + η(t− 1)H (5 + 2b) + 2κ( ). (9)
In this bound, we have removed the effect of log-partition 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 (Lemma 5 and Lemma 8) that
ESt−1 Ef∼p(·|St−1)
[ η
H∑ h=1 t−1∑ s=1 ∆Lh(fh, fh+1, ζs) + ln p(f |St−1)∏H h=1 p h 0 (f h)
]
≥ H∑ h=1 ESt−1 Ef∼p(·|St−1)
[ η
t−1∑ s=1 ∆Lh(fh, fh+1, ζs) + 0.5 ln p(fh, fh+1|St−1) ph0 (f h)ph+10 (f h+1)
]
≥0.25η t−1∑ s=1 H∑ h=1 ESt−1 Eft∼p(·|St−1) Eπfs (Eh(f ;x h s , a h s )) 2.
By combining this bound with (9), we obtain
Fκt =0.25η t−1∑ s=1 H∑ h=1 ESt−1 Eft∼p(·|St−1) Eπfs (Eh(ft;x h s , a h s )) 2 − λESt−1Eft∼p(·|St−1)∆f 1 t (x 1)
≤λ + η(t− 1)H (5 + 2b) + 2κ( ).
This implies the following bound for the sum of Fκt term in (6):
T∑ t=1 Fκt ≤ λ T + η(t− 1)H (5 + 2b)T + 2κ( )T.
By combining this estimate with (7) and (6), we obtain
λEReg(T ) ≤ λ 2
η dc
( F ,M, T, η
4λ
) + λ T + η(t− 1)H (5 + 2b)T + 2κ( )T.
The choice of = b/T β implies the first bound of Theorem 1.

heading: 6 Conclusion
text: This paper proposed a new posterior sampling algorithm for episodic reinforcement learning using conditional sampling with a temporal difference error likelihood. We show that posterior sampling methods can achieve the same frequentist regret guarantees as algorithms based on optimism in the face of uncertainty (OFU) in a wide range of settings with general value function approximation. Our results thus suggest that there is no 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 a 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 in this setting may provide additional tools to design statistically and computationally tractable algorithms.

Review summaries:
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.   ----- I have read the response and other reviews. I'll keep my original rating.

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.