Year: 2021

Abstract:
Reinforcement learning (RL) in episodic, factored Markov decision processes (FMDPs) is studied. We propose an algorithm called FMDP-BF, whose regret is exponentially smaller than that of optimal algorithms designed for non-factored MDPs, and improves on the previous FMDP result of Osband & Van Roy (2014b) by a factor of √ nH|Si|, where |Si| is the cardinality of the factored state subspace, H is the planning horizon and n is the number of factored transitions. We also provide a lower bound, which shows near-optimality of our algorithm w.r.t. timestep T , horizon H and factored state-action subspace cardinality. Finally, as an application, we study a new formulation of constrained RL, RL with knapsack constraints (RLwK), and provide the first sample-efficient algorithm based on FMDP-BF.

text: √ nH|Si|, where |Si| is the cardinality of the factored state sub-
space, H is the planning horizon and n is the number of factored transitions. We also provide a lower bound, which shows near-optimality of our algorithm w.r.t. timestep T , horizon H and factored state-action subspace cardinality. Finally, as an application, we study a new formulation of constrained RL, RL with knapsack constraints (RLwK), and provide the first sample-efficient algorithm based on FMDP-BF.

heading: 1 INTRODUCTION
text: Reinforcement learning (RL) is concerned with sequential decision making problems where an agent interacts with a stochastic environment and aims to maximize its cumulative rewards. The environment is usually modeled as a Markov Decision Process (MDP) whose transition kernel and reward function are unknown to the agent. A main challenge of the agent is efficient exploration in the MDP, so as to minimize its regret, or the related sample complexity of exploration.
Extensive study has been done on the tabular case, in which almost no prior knowledge is assumed on the MDP dynamics. The regret or sample complexity bounds typically depend polynomially on the cardinality of state and action spaces (e.g., Strehl et al., 2009; Jaksch et al., 2010; Azar et al., 2017; Dann et al., 2017; Jin et al., 2018; Dong et al., 2019; Zanette & Brunskill, 2019). Moreover, matching lower bounds (e.g., Jaksch et al., 2010) imply that these results cannot be improved without additional assumptions. On the other hand, many RL tasks involve large state and action spaces, for which these regret bounds are still excessively large.
In many practical scenarios, one can often take advantage of specific structures of the MDP to develop more efficient algorithms. For example, in robotics, the state may be high-dimensional, but the subspaces of the state may evolve independently of others, and only depend on a lowdimensional subspace of the previous state. Formally, these problems can be described as factored MDPs (Boutilier et al., 2000; Kearns & Koller, 1999; Guestrin et al., 2003). Most relevant to the present work is Osband & Van Roy (2014b), who proposed a posterior sampling algorithm and a
UCRL-like algorithm that both enjoy √ T regret, where T is the maximum timestep. Their regret bounds have a linear dependence on the time horizon and each factored state subspace. It is unclear whether this bound is tight or not.
In this work, we tackle this problem by proposing algorithms with improved regret bounds, and developing corresponding lower bounds for episodic FMDPs. We propose a sample- and computationefficient algorithm called FMDP-BF based on the principle of optimism in the face of uncertainty, and prove its regret bounds. We also provide a lower bound, which implies that our algorithm is near-optimal with respect to the timestep T , the planning horizon H and factored state-action subspace cardinality |X [Zi]|. As an application, we study a novel formulation of constrained RL, known as RL with knapsack constraints (RLwK), which we believe is natural to capture many scenarios in real-life applications. We apply FMDP-BF to this setting, to obtain a statistically efficient algorithm with a regret bound that is near-optimal in terms of T , S, A, and H .
Our contributions are summarized as follows:
1. We propose an algorithm for FMDP, and prove its regret bound that improves on the previous result of Osband & Van Roy (2014b) by a factor of √ nH|Si|. 2. We prove a regret lower bound for FMDP, which implies that our regret bound is nearoptimal in terms of timestep T , horizon H and factored state-action subspace cardinality. 3. We apply FMDP-BF in RLwK, a novel constrained RL setting with knapsack constraints, and prove a regret bound that is near-optimal in terms of T, S, A and H .

heading: 2 PRELIMINARIES
text: We consider the setting of a tabular episodic Markov decision process (MDP), (S,A, H,P, R), where S is the set of states, A is the action set, H is the number of steps in each episode. P is the transition probability matrix so that P(·|s, a) gives the distribution over states if action a is taken on state s, and R(s, a) is the reward distribution of taking action a on state s with support [0, 1]. We use R̄(s, a) to denote the expectation E[R(s, a)].
In each episode, the agent starts from an initial state s1 that may be arbitrarily selected. At each step h ∈ [H], the agent observes the current state sh ∈ S, takes action ah ∈ A, receives a reward rh sampled from R(sh, ah), and transits to state sh+1 with probability P(sh+1|sh, ah). The episode ends when sH+1 is reached.
A policy π is a collection of H policy functions {πh : S → A}h∈[H]. We use V πh : S → R to denote the value function at step h under policy π, which gives the expected sum of remaining rewards received under policy π starting from sh = s, i.e. V πh (s) = E [∑H h′=hR(sh′ , πh′(sh′)) | sh = s ] . Accordingly, we define Qπh(s, a) as the expected Q-value function at step h: Q π h(s, a) =
E [ R(sh, ah) + ∑H h′=h+1R(sh′ , πh′(sh′)) | sh = s, ah = a ] . We use V ∗h and Q ∗ h to denote the optimal value and Q-functions under optimal policy π∗ at step h.
The agent interacts with the environment for K episodes with policy πk = {πk,h : S → A}h∈[H] determined before the k-th episode begins. The agent’s goal is to maximize its cumulative rewards∑K k=1 ∑H h=1 rk,h over T = KH steps, or equivalently, to minimize the following expected regret:
Reg(K) def = K∑ k=1 [V ∗1 (sk,1)− V πk 1 (sk,1)] ,
where sk,1 is the initial state of episode k.

heading: 2.1 FACTORED MDPS
text: A factored MDP is an MDP whose rewards and transitions exhibit certain conditional independence structures. We start with the formal definition of factored MDP (Boutilier et al., 2000; Osband & Van Roy, 2014b; Xu & Tewari, 2020; Lu & Van Roy, 2019). LetP(X ,Y) denote the set of functions that map x ∈ X to the probability distribution on Y .
Definition 1. (Factored set) Let X = X1 × · · · × Xd be a factored set. For any subset of indices Z ⊆ {1, 2, . . . , d}, we define the scope set X [Z] := ⊗i∈ZXi. Further, for any x ∈ X , define the scope variable x[Z] ∈ X [Z] to be the value of the variables xi ∈ Xi with indices i ∈ Z. If Z is a singleton, we will write x[i] for x[{i}]. Definition 2. (Factored reward) The reward function classR ⊂ P(X ,R) is factored over S ×A = X = X1 × · · · × Xd with scopes Z1, · · · , Zm if for all R ∈ R, x ∈ X , there exist functions {Ri ∈ P (X [Zi] , [0, 1])}mi=1 such that r ∼ R(x) is equal to 1 m ∑m i=1 ri with each ri ∼ Ri(x[Zi]) individually observed. We use R̄i to denote the expectation E[Ri]. Definition 3. (Factored transition) The transition function class P ⊂ P(X ,S) is factored over S × A = X = X1 × · · · × Xd and S = S1 × · · · × Sn with scopes Z1, · · · , Zn if and only if, for all P ∈ P , x ∈ X , s ∈ S, there exist functions {Pj ∈ P (X [Zj ] ,Sj)}nj=1 such that P(s | x) =∏n j=1 Pj (s[j] | x [Zj ]) .
A factored MDP is an MDP with factored rewards and transitions. A factored MDP is fully characterized by M = ( {Xi}di=1 ; { ZRi }m i=1 ; {Ri}mi=1 ; {Sj} n j=1 ; { ZPj }n j=1 ; {Pj}nj=1 ;H ) , where X = S × A, {ZRi }mi=1 and {ZPj }nj=1 are the scopes for the reward and transition functions, which we assume to be known to the agent.
An excellent example of factored MDP is given by Osband & Van Roy (2014), about a large production line with d machines in sequence with Si possible states for machine i. Over a single time-step each machine can only be influenced by its direct neighbors. For this problem, the scopes ZRi and ZPi of machine i ∈ {2, ..., d − 1} can be defined as {i − 1, i, i + 1}, and the scopes of machine 1 and machine d are {1, 2} and {d− 1, d} respectively. Another possible example to explain factored MDP is about robotics. For a robot, the transition dynamics of its different parts (e.g. its legs and arms) may be relatively independent. In that case, the factored transition can be defined for each part separately.
For notation simplicity, we use X [i : j] and S[i : j] to denote X [∪k=i,...,jZk] and ⊗jk=iSk respectively. Similarly, We use P[i:j](s′[i : j] | s, a) to denote ∏j k=i P(s′[k]|(s, a)[ZPk ]). For every
V : S → R and the right-linear operators P, we define PV (s, a) def= ∑ s′∈S P(s′ | s, a)V (s′). A state-action pair can be represented as (s, a) or x. We also use (s, a)[Z] to denote the corresponding x[Z] for notation convenience. We mainly focus on the case where the total time step T = KH is the dominant factor, and assume that T ≥ |Xi| ≥ H during the analysis.

heading: 3 RELATED WORK
text: Exploration in Reinforcement Learning Recent years have witnessed a tremendous of work for provably efficient exploration in reinforcement learning, including tabular MDP (e.g., Dann et al., 2017; Azar et al., 2017; Jin et al., 2018; Zanette & Brunskill, 2019), linear RL (e.g., Jiang et al., 2017; Yang & Wang, 2019; Jin et al., 2020; Zanette et al., 2020), and RL with general function approximation (e.g., Osband & Van Roy, 2014a; Ayoub et al., 2020; Wang et al., 2020). For algorithms in tabular setting, the regret bounds inevitably depend on the cardinality of state-action space, which may be excessively large. Based on the concept of eluder dimension (Russo & Van Roy, 2013), many recent works proposed efficient algorithms for RL with general function approximation (Osband & Van Roy, 2014a; Ayoub et al., 2020; Wang et al., 2020). Since eluder dimension of the function class for factored MDPs is at mostO (∑m i=1 |X [ZRi ]|+ ∑n i=1 |X [ZPi ]| ) , it is possible to apply their algorithms and regret bounds to our setting, though the direct application of their algorithms leads to a loose regret bound.
Factored MDP Episodic FMDP was studied by Osband & Van Roy (2014b), in which they proposed both PSRL and UCRL style algorithm with near-optimal Bayesian and frequentist regret bound. In non-episodic scenarios, Xu & Tewari (2020) recently generalizes the algorithm of Osband & Van Roy (2014b) to the infinite horizon average reward setting. However, both their results suffer from linear dependence on the horizon (or the diameter) and factored state space’s cardinality.
Concurrent with our work is the recent paper by Tian et al. (2020), which also applies UCBVI and EULER to factored MDPs. Compared with their results, we propose a more refined variance
decomposition theorem for factored Markov chains (Theorem 1), which results in a better regret by a factor of √ n; the theorem is also of independent interest with potential use in other problems in factored MDPs. Furthermore, we formulate the RLwK problem, and provide a sample-efficient algorithm based on our FMDP algorithm.
Constrained MDP and knapsack bandits The knapsack setting with hard constraints has already been studied in bandits with both sample-efficient and computational-efficient algorithms (Badanidiyuru et al., 2013; Agrawal et al., 2016). This setting may be viewed as a special case of RLwK with H = 1. In constrained RL, there is a line of works that focus on soft constraints where the constraints are satisfied in expectation or with high probability (Brantley et al., 2020; Zheng & Ratliff, 2020), or a violation bound is established (Efroni et al., 2020; Ding et al., 2020). RLwK requires stronger constraints that is almost surely satisfied during the execution of the agents. A more related setting is proposed by Brantley et al. (2020), which studies a sample-efficient algorithm for knapsack episodic setting with hard constraints on all K episodes. However, we require the constraints to be satisfied within each episode, which we believe can better describe the real-world scenarios. The setting of Singh et al. (2020) is closer to ours since they are focusing on “every-time” hard constraints, although they consider the non-episodic case.

heading: 4 MAIN RESULTS
text: In this section, we introduce our FMDP-BF algorithm, which uses empirical variance to construct a Bernstein-type confidence bound for value estimation. Besides FMDP-BF, we also propose a simpler algorithm called FMDP-CH with a slightly worse regret, which follows the similar idea of UCBVI-CH (Azar et al., 2017). The algorithm and the corresponding analysis are more concise and easy to understand; details are deferred to Section B.

heading: 4.1 ESTIMATION ERROR DECOMPOSITION
text: Our algorithm will follow the principle of “optimism in the face of uncertainty”. Like ORLC (Dann et al., 2019) and EULER (Zanette & Brunskill, 2019), our algorithm also maintains both the optimistic and pessimistic estimates of state values to yield an improved regret bound. We use V k,h and V k,h to denote the optimistic estimation and pessimistic estimation of V ∗ h , respectively. To guarantee optimism, we need to add confidence bonus to the estimated value function V k,h at each step, so that V k,h(s) ≥ V ∗h (s) holds for any k ∈ [K], h ∈ [H] and s ∈ S. Suppose R̂k,i and P̂k,j denote the estimated value of each expected factored reward Ri and factored transition probability Pj before episode k respectively. By the definition of the reward R and the transition P, we use R̂ def= 1m ∑m i=1 R̂k,i and P̂k def = ∏n j=1 P̂k,j as the estimation of R̄ and P. Following the previous framework, this confidence bonus needs to tightly characterize the estimation error of the one-step backup R̄(s, a)+PV ∗h (s, a); in other words, it should compensate for the estimation errors,( R̂k − R̄ ) (s, a) and ( P̂k − P ) V ∗h (s, a), respectively.
For the estimation error of rewards ( R̂k − R̄ ) (sk,h, ak,h), since the reward is defined as the average
of m factored rewards, it is not hard to decompose the estimation error of R̄(s, a) to the average of the estimation error of each factored rewards. In that case, we separately construct the confidence bonus of each factored reward R̄i. Suppose CBRk,ZRi (s, a) is the confidence bonus that compensates for the estimation error R̂k,i − R̄i, then we have CBRk (s, a) def = 1m ∑m i=1 CB R k,ZRi (s, a).
For the estimation error of transition ( P̂k − P ) V ∗h+1(sk,h, ak,h), the main difficulty is that P̂k is the multiplication of n estimated transition dynamics P̂k,i. In that case, the estimation error( P̂k − P ) V ∗h+1(sk,h, ak,h) may be calculated as the multiplication of n estimation error for each
factored transition P̂k,i, which makes the analysis much more difficult. Fortunately, we have the following lemma to address this challenge.
Lemma 4.1. (Informal) Let the transition function class P ∈ P(X ,S) be factored over X = X1 × · · · ×Xd, and S = S1 × · · · × Sn with scopes ZP1 , · · · , ZPn . For a given function V : S → R, the estimation error of one-step value |(P̂k − P)V (s, a)| can be decomposed by:
|(P̂k − P)V (s, a)| ≤ n∑ i=1 ∣∣∣∣∣∣(P̂k,i − Pi)  n∏ j 6=i,j=1 Pj V (s, a) ∣∣∣∣∣∣+ βk,h(s, a)
Here, βk,h(s, a), formally defined in Lemma E.1, are higher order terms that do not harm the order of the regret. This lemma allows us to decompose the estimation error ( P̂k − P ) V ∗h+1(sk,h, ak,h)
into an additive form, so we can construct the confidence bonus for each factored transition Pj separately. Let CBPk,ZPj (s, a) be the confidence bonus for the estimation error (P̂k,j −
Pj) (∏n t 6=j,t=1 Pt ) V (s, a). Then, CBPk (s, a) def = ∑n j=1 CB
P k,ZPj (s, a) + ηk,h(s, a), where
ηk,h(s, a) collects higher order factors that will be explicitly given later.
Finally, we define the confidence bonus as the summation of all confidence bonuses for rewards and transition: CBk(s, a) = CBRk (s, a) + CB P k (s, a).

heading: 4.2 VARIANCE OF FACTORED MARKOV CHAINS
text: After the analysis in Section 4.1, the remaining problem is how to define the confidence bonus CBR
k,ZRi (s, a) and CBP k,ZPj (s, a). In this subsection, we tackle this problem by deriving the variance decomposition formula for factored MDP. To begin with, we consider Markov chains with stochastic factored transition and stochastic factored rewards, and deduce the Bellman equation of variance for factored Markov chains. The analysis shows how to define the empirical variance in the confidence bonus for factored MDP and gives an upper bound on the summation of per-step variance (Corollary 1.1).
In the Markov chain setting, the reward is defined to be a mapping from S to R. Suppose Jt1:t2(s) denotes the total rewards the agent obtains from step t1 to step t2 (inclusively), given that the agent starts from state s in step t1. Jt1:t2 is a random variable depending on the randomness of the trajectory from step t1 to t2, and stochastic rewards therein. Following this definition of Jt1:t2 , we define J1:H to be the total reward obtained during one episode. We use st to denote the random state that the agent encounters at step t. We define ω2h(s) def = E [ (Jh:H(sh)− Vh(sh))2 |sh = s ] to be
the variance of the total gain after step h, given that sh = s.
We define σ2R,i(s) def = V [Ri(ξ)|ξ = s] to be the variance of the i-th factored reward, given that the current state is s. Given the current state s, we define the variance of the next-state value function w.r.t. the i-th factored transition as: σ2P,i,h(s) def =
Esh+1[1:i−1] [ Vsh+1[i] [ Esh+1[i+1:n] [Vh+1(sh+1)] ] | sh = s ] . That is, for each given s′[1 : i], we firstly take expectation over all possible values of s′[i+ 1 : n] w.r.t. P[i+1:n]. Then, we calculate the variance of transition s′[i] ∼ Pi(·|(s, a)[ZPi ]) given fixed s′[1 : i − 1]. Finally, we take the expectation of this variance w.r.t. s′[1 : i− 1] ∼ P[1:i−1]. Theorem 1. For any horizon h ∈ [H], we have ω2h(s) = ∑ s′ P(s′|s)ω2h+1(s′) + ∑n i=1 σ 2 P,i,h(s) +
1 m2 ∑m i=1 σ 2 R,i(s).
Theorem 1 generalizes the analysis of Munos & Moore (1999), which deals with non-factored MDPs and deterministic rewards. From the Bellman equation of variance, we can give an upper bound to the expected summation of per-step variance. Corollary 1.1. Suppose the agent takes policy π during an episode. Let wh(s, a) denote the probability of entering state s and taking action a in step h. Then we have the following inequality:
H∑ h=1 ∑ (s,a)∈X wh(s, a) ( n∑ i=1 σ2P,i(V π h+1, s, a) + 1 m2 m∑ i=1 σ2R,i(s, a) ) ≤ H2,
where σ2R,i(s, a) def = V [ri(ξ, ζ)|ξ = s, ζ = a] is the variance of i-th factored reward given the current state-action pair (s, a), and σ2P,i(V π h+1, s, a) =
Esh+1[1:i−1] [ Vsh+1[i] [ Esh+1[i+1:n] [ V πh+1(sh+1) ]] | sh = s ] is the variance of i-th factored transition given current state s.
This corollary makes it possible to construct confidence bonus with variance for each factored rewards and transition separately. Please refer to Section F.2 for the detailed proof of Theorem 1 and Corollary 1.1.

heading: 4.3 ALGORITHM
text: Our algorithm is formally described in Alg. 1, with a more detailed explanation in Section C. Denote by Nk((s, a)[Z]) the number of steps that the agent encounters (s, a)[Z] during the first k episodes. In episode k, we estimate the mean value of each factored reward Ri and each factored transition Pi with empirical mean value R̂k,i and P̂k,i of the previous history data L respectively. After that, we construct the optimistic MDP M̂ based on the estimated rewards and transition functions. For a certain (s, a) pair, the transition function and reward function are defined as R̂k(s, a) = 1 m ∑m i=1 R̂k,i((s, a)[Z R i ]) and P̂k(s′ | s, a) = ∏n j=1 P̂k,j ( s′[j] | (s, a) [ ZPj ]) .
Algorithm 1 FMDP-BF Input: δ L = ∅, initialize N((s, a)[Zi]) = 0 for any factored set Zi and any (s, a)[Zi] ∈ X [Zi] for episode k = 1, 2, · · · do
Set V k,H+1(s) = V k,H+1(s) = 0 for all s, a. 5: Estimate the empirical mean R̂k and P̂k with history data L.
for horizon h = H,H − 1, ..., 1 do for s ∈ S do
for a ∈ A do Qk,h(s, a) = min{H, R̂k(s, a) + CBk(s, a) + P̂kV k,h+1(s, a)}
10: end for πk,h(s) = arg maxaQk,h(s, a)
V k,h(s) = maxa∈AQk,h(s, a) V k,h(s) = max { 0, R̂k(s, πk,h(s))− CBk(s, πk,h(s)) + P̂kV k,h+1(s, πk,h(s)) }
end for 15: end for
Take action according to πk,h for H steps in this episode. Update L = L ⋃ {sk,h, ak,h, rk,h, sk,h+1}h=1,2,...,H , and update counter Nk−1((s, a)[Zi]).
end for
Following the analysis in Section 4.1, we separately construct the confidence bonus of each factored
rewardRi with the empirical variance: CBRk,ZRi (s, a) =
√ 2σ̂2R,k,i(s,a)L R i
Nk−1((s,a)[ZRi ]) + 8LRi 3Nk−1((s,a)[ZRi ]) , i ∈
[m], where LRi def = log
( 18mT ∣∣X [ZRi ]∣∣ /δ), and σ̂2R,k,i is the empirical variance of the i-th factored reward Ri, i.e. σ̂2R,k,i(s, a) =
1 Nk−1((s,a)[ZPi ])
∑(k−1)H t=1 1 [ (st, at)[Z R i ] = (s, a)[Z R i ] ] · r2t,i −(
R̂k,i((s, a)[Z R i ]) )2 .
We define LP = log (18nTSA/δ) for short. Following the idea of Lemma 4.1, we separately construct the confidence bonus of scope ZPi for transition estimation: CB
P k,ZPi (s, a) =√ 4σ̂2P,k,i(V k,h+1,s,a)L P Nk−1((s,a)[ZPi ]) + √ 2uk,h,i(s,a)LP Nk−1((s,a)[ZPi ]) + ηk,h,i(s, a), i ∈ [n], where σ̂P,k,i(s, a) and uk,h,i(s, a) are defined later. ηk,h,i(s, a) collects the additional bonus terms that do not affect the order of the final regret. The precise expression of ηk,h,i(s, a) is deferred to Section C.
The definition of σ̂2P,k,i(V k,h+1, s, a) corresponds to σ 2 P,i(V π h , s, a) in Corollary 1.1, which can be regarded as the empirical variance of transition Pk,i: σ̂2P,k,i(V k,h+1, s, a) = Es′[1:i−1]∼P̂k,[1:i−1](·|s,a) [ Vs′[i]∼P̂k,i(·|(s,a)[ZPi ]) ( Es′[i+1:n]∼P̂k,[i+1:n](·|s,a)V k,h+1(s ′) )] .
To guarantee optimism, we need to use the empirical variance σ̂2P,k,i(V ∗, s, a) to upper bound the estimation error in the proof. Since we do not know V ∗ beforehand, we use σ̂2P,k,i(V k,h+1, s, a) as a surrogate in the confidence bonus. However, we cannot guarantee that σ̂2P,k,i(V
∗, s, a) is upper bounded by σ̂2P,k,i(V k,h+1, s, a). To compensate for the error due to the difference between V ∗ h+1
and V k,h+1, we add √ 2uk,h,i(s,a)LP
Nk−1((s,a)[ZPi ]) to the confidence bonus, where uk,h,i(s, a) is defined as:
uk,h,i(s, a) = Es′ [1:i] ∼P̂k,[1:i](·|s,a)
[( Es′
[i+1:n] ∼P̂k,[i+1:n](·|s,a)
( V k,h+1 − V k,h+1 ) (s′) )2] .

heading: 4.4 REGRET
text: Theorem 2. Suppose ∣∣X [ZRi ]∣∣ ≤ JR, ∣∣X [ZPj ]∣∣ ≤ JP for i ∈ [m], j ∈ [n], then with prob. 1 − δ,
the regret of Alg. 1 is O (√ JRT log(mTJR/δ) log T + √ nHJPT log(nTSA/δ) log T ) .
Note that the regret bound does not depend on the cardinalities of state and action spaces, but only has a square-root dependence on the cardinality of each factored subspace X [Zi]. By leveraging the structure of factored MDP, we achieve regret that scales exponentially smaller compared with that of UCBVI (Azar et al., 2017). The best previous regret bound for episodic factored MDP is achieved by Osband & Van Roy (2014b). When transformed to our setting, it becomes O (√ JRT log(mTJR/δ) + nH √ ΓJPT log(nTJP /δ) )
, where Γ is an upper bound of |Sj |. This is worse than our results by a factor of √ nHΓ. Concurrent to our results, Tian et al. (2020) also propose efficient algorithms for episodic factored MDP. When transformed to our setting, their regret bound is Õ (√ JRT + n √ HJPT ) . Compared with their bounds, we further improve the regret by a factor of √ n with a more refined variance decomposition theorem (Theorem 1).

heading: 4.5 LOWER BOUND
text: In this subsection, we propose the regret lower bound for factored MDP. The proof of Theorem 3 is deferred to Section G.
Theorem 3. Suppose log2 (|Si|) ≤ H2 for any i ∈ [n], the regret of any algorithm on the factored MDP problem is lower bounded by Ω ( 1 m ∑m i=1 √∣∣X [ZRi ]∣∣T + 1n∑ni=1√∣∣X [ZPi ]∣∣HT) . The lower bound of Tian et al. (2020) is Ω ( max { maxi
√∣∣X [ZRi ]∣∣T ,maxj√∣∣X [ZPi ]∣∣HT}), which is derived from different hard instance construction. Their lower bound is of the same order with ours, while our bound measures the dependence on all the parameters including the number of the factored transition n and the factored rewards m. If
∣∣X [ZRi ]∣∣ = JR and ∣∣X [ZPi ]∣∣ = JP , the lower bound turns out to be Ω (√ JRT + √ HJPT ) , which matches the upper bound in Theorem 2 except for a factor of √ n and logarithmic factors.

heading: 5 RL WITH KNAPSACK CONSTRAINTS
text: In this section, we study RL with Knapsack constraints, or RLwK, as an application of FMDP-BF.

heading: 5.1 PRELIMINARIES
text: We generalize bandit with knapsack constraints or BwK (Badanidiyuru et al., 2013; Agrawal et al., 2016) to episodic MDPs. We consider the setting of tabular episodic Markov decision process,
(S,A, H,P, R,C), which adds to an episodic MDP with a d-dimensional stochastic cost vector, C(s, a). We use Ci(s, a) to denote the i-th cost in the cost vector C(s, a). If the agent takes action a in state s, it receives reward r sampled from R(s, a), together with cost c, before transitioning to the next state s′ with probability P(s′|s, a). In each episode, the agent’s total budget is B. We also use Bi to denote the total budget of i-th cost. Without loss of generality, we assume Bi ≤ B for all i. An episode terminates after H steps, or when the cumulative cost ∑ h ch,i of any dimension i exceeds the budget Bi, whichever occurs first. The agent’s goal is to maximize its cumulative reward ∑K k=1 ∑H h=1 rk,h in K episodes.

heading: 5.2 COMPARISON WITH OTHER SETTINGS
text: While RLwK might appear similar to episodic constrained RL (Efroni et al., 2020; Brantley et al., 2020), it is fundamentally different, so those algorithms cannot be applied here.
As discussed in Section 3, the episodic constrained RL setting can be roughly divided into two categories. A line of works focus on soft constraints where the constraints are satisfied in expectation, i.e. ∑H h=1 E[ck,h] ≤ B. The expectation is taken over the randomness of the trajectories and the random sample of the costs. Another line of work focuses on hard constraints in K episodes. To be more specific, they assume that the total costs in K episodes cannot exceed a constant vector B, i.e.∑K k=1 ∑H h=1 ck,h ≤ B. Once this is violated before episode K1 < K, the agent will not obtain any rewards in the remaining K − K1 episodes. Though both settings are interesting and useful, they do not cover many common situations in constrained RL. For example, when playing games, the game is over once the total energy or health reduce to 0. After that, the player may restart the game (starting a new episode) with full initial energy again. In robotics, a robot may episodically interact with the environment and learn a policy to carry out a certain task. The interaction in each episode is over once its energy is used up. In these two examples, we cannot just consider the expected cost or the cumulative cost across all episodes, but calculate the cumulative cost in every individual episode. Moreover, in many constrained RL applications, the agent’s optimal action should depend on its remaining budget. For example, in robotics, the robot should do planning and take actions based on its remaining energy. However, previous results do not consider this issue, and use policies that map states to actions. Instead, in RLwK, we need to define the policy as a mapping from states and remaining budget to actions. Section H gives further details, including two examples for illustrating the difference between these settings.

heading: 5.3 ALGORITHM
text: We make the following assumptions about the cost function for simplicity. Both of them hold if all the stochastic costs are integers with an upper bound. Assumption 1. The budget Bi as well as the possible value of costs Ci(s, a) of any state s and action a is an integral multiple of the unit cost 1m . Assumption 2. The stochastic cost Ci(s, a) has finite support. That is, the random variable Ci(s, a) can only take at most n possible values.
The reason for Assumption 2 is that we need to estimate the distribution of the cost, instead of just estimating its mean value. We discuss the necessity of the assumptions and the possible methods for continuous distribution in Section H.3.
From the above discussion, we know that we need to find a policy that is a mapping from state and budget to action. Therefore, it is natural to augment the state with the remaining budget. It follows that the size of augmented state space is S · (Bm)d. Directly applying UCBVI algorithm (Azar et al., 2017) will lead to a regret of order O (√ HSAT (Bm)d ) . Our key observation is that the
constructed state representation can be represented as a product of subspaces. Each subspace is relatively independent. For example, the transition matrix over the original state space S is independent of the remaining budget. Therefore, the constructed MDP can be formulated as a factored MDP, and the compact structure of the model can reduce the regret significantly. By applying Alg. 1 and Theorem 2 to RLwK, we can reduce the regret to the order of O (√ HSA(1 + dBm)T ) roughly, which is exponentially smaller. However, the regret still de-
pends on the total budget B and the discretization precision m, which may be very large for continuous budget and cost. Another observation to tackle the problem is that the cost of taking action a on state s only depends on the current state-action pair (s, a), but has no dependence on the remaining budget B. To be more formal, we have bh+1 = bh − ch, where bh is the remaining budget at step h, and ch is the cost suffered in step h. As a result, we can further reduce the regret to roughly O (√ HdSAT )
by estimating the distribution of cost function. A similar model has been discussed in Brunskill et al. (2009), which is named as noisy offset model.
Our algorithm, which is called FMDP-BF for RLwK, follows the same basic idea of Alg. 1. We defer the detailed description to Section H to avoid redundance. The regret can be upper bounded by the following theorem: Theorem 4. With prob. at least 1− δ, the regret of Alg. 4 is upper bounded by
O (√ dHSAT (log(SAT ) + d log(Bm)) )
Compared with the lower bound for non-factored tabular MDP (Jaksch et al., 2010), this regret bound matches the lower bound w.r.t. S, A, H and T . There may still be a gap in the dependence of the number of constraints d, which is often much smaller than other quantities.
It should be noted that, though we achieve a near-optimal regret for RLwK, the computational complexity is high, scaling polynomially with the maximum budget B, and exponentially with the number of constraints d. This is a consequence of the NP-hardness of knapsack problem with multiple constraints (Martello, 1990; Kellerer et al., 2004). However, since the policy is defined on the state and budget space with cardinality SBd, this computational complexity seems unavoidable. How to tackle this problem, such as with approximation algorithms, is an interesting future work.

heading: 6 CONCLUSION
text: We propose a novel RL algorithm for solving FMDPs with near optimal regret guarantee. It improves the best previous regret bound by a factor of √ nH|Si|. We also derive a regret lower bound for FMDPs based on the minimax lower bound of multi-armed bandits and episodic tubular MDPs (Jaksch et al., 2010). Further, we formulate the RL with Knapsack constraints (RLwK) setting, and establish the connections between our results for FMDP and RLwK by providing a sample efficient algorithm based on FMDP-BF in this new setting. A few problems remain open. The regret upper and lower bounds have a gap of approximately √ n, where n is the number of transition factors. For RLwK, it is important to develop a computationally efficient algorithm, or find a variant of the hard-constraint formulation. We hope to address these issues in the future work.

heading: ACKNOWLEDGEMENTS
text: This work was supported by Key-Area Research and Development Program of Guangdong Province (No. 2019B121204008)], National Key R&D Program of China (2018YFB1402600), BJNSF (L172037) and Beijing Academy of Artificial Intelligence.

heading: A NOTATIONS
text: Before presenting the proof, we restate the definition of the following notations.
Symbol Explanation sk,h, ak,h The state and action that the agent encounters in episode k and step h LP log (18nTSA/δ) LRi log ( 18mT
∣∣X [ZRi ]∣∣ /δ) XPi
∣∣X [ZPi ]∣∣ XRi
∣∣X [ZRi ]∣∣ Nk((s, a)[Z]) the number of steps that the agent encounters (s, a)[Z] during the first k episodes PV (s, a) A shorthand of ∑ s′∈S P(s′|s, a)V (s′)
φk,i(s, a)
√ 4|Sj |LP
Nk−1((s,a)[ZPj ]) +
4|Sj |LP
3Nk−1((s,a)[ZPj ])
σ̂2R,i(s, a) The empirical variance of reward Ri σ2P,i(V, s, a) the next state variance of PV for the transition Pi,
i.e. Es′[1:i−1]∼P[1:i](·|s,a) [ Vs′[i]∼Pi(·|(s,a)[ZPi ]) ( Es′[i+1:n]∼P[i+1:n](·|s,a)V (s ′) )]
σ̂P,k,i(V, s, a) the empirical next state variance of P̂kV for the transition P̂k,i, i.e. Es′[1:i−1]∼P̂k,[1:i](·|s,a) [ Vs′[i]∼P̂k,i(·|(s,a)[ZPi ]) ( Es′[i+1:n]∼P̂k,[i+1:n](·|s,a)V (s ′) )]
Ωk,h The optimism and pessimism event for k, h: { V k,h ≥ V ∗h ≥ V k,h } Ω The optimism and pessimism events for all 1 ≤ k ≤ K, 1 ≤ h ≤ H , i.e. ∪k,hΩk,h
wk,h,Z(s, a) The probability of entering (s, a)[Z] at step h in episode k wk,Z(s, a) ∑H h=1 wk,h,Z(s, a)
wk,h(s, a) The probability of entering (s, a) at step h in episode k, i.e. wk,h,Z(s, a) with Z = {1, 2, ..., d}
wk(s, a) ∑H h=1 wk,h(s, a)

heading: B OMITTED DETAILS FOR FMDP-CH
text: In this section, we introduce our algorithm with Hoeffding-type confidence bonus and present the corresponding regret bound. Our algorithm, which is described in Algorithm 2, is related to UCBVICH algorithm (Azar et al., 2017), in the sense that Algorithm 2 reduces to UCBVI-CH if we consider a flat MDP with m = n = d = 1.
Let Nk((s, a)[Z]) denote the number of steps that the agent encounters (s, a)[Z] during the first k episodes, and Nk((s, a)[Zj ], sj) denotes the number of steps that the agent transits to a state with s[j] = sj after encountering (s, a)[Zj ] during the first k episodes. In episode k, we estimate the mean value of each factored reward Ri and each factored transition Pi with empirical mean value R̂k,i and P̂k,i respectively. To be more specific, R̂k,i((s, a)[ZRi ]) =∑
t≤(k−1)H 1[(st,at)[Z R i ]=(s,a)[Z R i ]]·rt,i
Nk−1((s,a)[ZRi ]) , where rt,i denotes the reward Ri sampled in step t, and P̂k,j ( s[j]|(s, a)[ZPj ] ) = Nk−1((s,a)[Z P j ],s[j])
Nk−1((s,a)[ZPj ]) . After that, we construct the optimistic MDP M̂ based
on the estimated rewards and transition functions. For a certain (s, a) pair, the transition function and reward function are defined as R̂k(s, a) = 1m ∑m i=1 R̂k,i((s, a)[Z
R i ]) and P̂k(s′ | s, a) =∏n j=1 P̂k,j ( s′[j] | (s, a) [ ZPj ]) .
We define LRi = log ( 18mT ∣∣X [ZRi ]∣∣ /δ), LP = log (18nTSA/δ) and φk,i(s, a) =√ 4|Si|LP
Nk−1((s,a)[ZPi ]) + 4|Si|L 3Nk−1((s,a)[ZPi ]) . We separately construct the confidence bonus of each fac-
Algorithm 2 FMDP-CH Input: δ, history data L = ∅, initialize N((s, a)[Zi]) = 0 for any factored set Zi and (s, a)[Zi] ∈ X [Zi] for episode k = 1, 2, ... do
Set V̂k,H+1(s) = 0 for all s. 5: Estimate R̂k,i(s, a) with empirical mean value if Nk−1((s, a)[ZRi ]) > 0, otherwise R̂k,i(s, a) = 1, then calculate R̂(s, a) = 1m ∑m i=1 R̂i((s, a)[Z R i ])
Let KP = { (s, a) ∈ S ×A,∪i∈[n]Nk((s, a)[ZPi ]) > 0 } Estimate P̂k(·|s, a) with empirical mean value for all (s, a) ∈ KP for horizon h = H,H − 1, ..., 1 do
for all (s, a) ∈ S ×A do 10: if (s.a) ∈ KP then
Q̂k,h(s, a) = min{H, R̂k(s, a) + CBk(s, a) + P̂kV̂k,h+1(s, a)} else
Q̂k,h(s, a) = H end if

heading: 15: V̂k,h(s) = maxa∈A Q̂k,h(s, a)
text: end for
end for for step h = 1, · · · , H do
Take action ak,h = arg maxa Q̂k,h(sk,h, a) 20: end for Update history trajectory L = L ⋃ {sk,h, ak,h, rk,h, sk,h+1}h=1,2,...,H , and update history
counter Nk−1((s, a)[Zi]). end for
tored reward Ri and factored transition Pi in the following way:
CBRk,ZRi (s, a) =
√ 2LRi
Nk−1((s, a)[ZRi ]) , i ∈ [m] (1)
CBPk,ZPi (s, a) =
√ 2H2LP
Nk−1((s, a)[ZPi ]) +Hφk,i(s, a) n∑ j=1,j 6=i φk,j(s, a), i ∈ [n] (2)
We define the confidence bonus as the summation of all confidence bonus for rewards and transition, i.e. CBk(s, a) = 1m ∑m i=1 CB R k,ZRi (s, a) + ∑n j=1 CB P k,ZPj (s, a).
We propose the following regret upper bound for Alg. 2.
Theorem 5. With prob. 1− δ, the regret of Alg. 2 is upper bounded by
Reg(K) = O  1 m m∑ i=1 √∣∣X [ZRi ]∣∣T log(mT |X [ZRi ]|/δ) + n∑ j=1 H √∣∣X [ZPj ]∣∣T log(nTSA/δ)  Here O hides the lower order terms with respect to T .

heading: C OMITTED DETAILS IN SECTION 4
text: In this section, we clarify the omitted details in Section 4. The detailed algorithm is described in Alg. 3. we denote Nk((s, a)[Z]) as the number of steps that the agent encounters (s, a)[Z] during the first k episodes, and Nk((s, a)[Zj ], sj) as the number of steps that the agent transits to a state with s[j] = sj after encountering (s, a)[Zj ] during the first k episodes. In episode k, we estimate the mean value of each factored reward Ri and each factored transition Pi with empirical mean value R̂k,i and P̂k,i respectively. To be more specific, R̂k,i((s, a)[ZRi ]) =
∑ t≤(k−1)H 1[(st,at)[Z R i ]=(s,a)[Z R i ]]·rt,i
Nk−1((s,a)[ZRi ]) , where rt,i denotes the reward Ri sampled in step t, and P̂k,j ( s[j]|(s, a)[ZPj ] ) = Nk−1((s,a)[Z P j ],s[j])
Nk−1((s,a)[ZPj ]) .
The formal definition of the confidence bonus for Alg. 1 is:
CBRk,ZRi (s, a) =
√ 2σ̂2R,k,i(s, a)L R i
Nk−1((s, a)[ZRi ]) + 8LRi 3Nk−1((s, a)[ZRi ])
(3)
CBPk,ZPi (s, a) =
√ 4σ̂2P,k,i(V k,h+1, s, a)L P
Nk−1((s, a)[ZPi ]) +
√ 2uk,h,i(s, a)LP
Nk−1((s, a)[ZPi ]) (4)
+
√ 16H2LP
Nk−1((s, a)[ZPi ]) n∑ j=1 ( 4|Sj |LP Nk−1((s, a)[ZPj ]) ) 1 4 + √ 4|Sj |LP 3Nk−1(s, a)[ZPj ]  (5)
+ n∑ j=1 Hφk,i(s, a)φk,j(s, a), (6)
where φk,i(s, a) = √
4|Sj |LP Nk−1((s,a)[ZPj ]) + 4|Sj |LP 3Nk−1((s,a)[ZPj ]) . The definition of ηk,h,i(s, a) is
√ 16H2LP
Nk−1((s, a)[ZPi ]) n∑ j=1 ( 4|Sj |LP Nk−1((s, a)[ZPj ]) ) 1 4 + √ 4|Sj |LP 3Nk−1(s, a)[ZPj ] + n∑ j=1 Hφk,i(s, a)φk,j(s, a).
Theorem 6. (Refined Statement of Theorem 2) With prob. at least 1− δ, the regret of Alg. 1 is upper bounded by
O  1 m m∑ i=1 √∣∣X [ZRi ]∣∣T log(mT ∣∣X [ZRi ]∣∣ /δ) log T + √√√√ n∑ i=1 H ∣∣X [ZPi ]∣∣T log(nTSA/δ) log T  . For clarity, we also present a cleaner single-term regret bound under a symmetric problem setting. SupposeM is a set of factored MDP with m = n, |Si| = Si, |Xi| = SiAi and |ZRi | = |ZPj | = ζ for i = 1, ...,m and j = 1, ..., n, we write Xi = (SiAi)ζ and assume that Xi ≤ J and Si ≤ Γ. Corollary 6.1. Suppose M∗ ∈ M, with prob. 1 − δ, the regret of FMDP-BF is upper bounded by O (√ nHJT log(nTSA/δ) ) . The minimax regret bound for non-factored MDP is O (√ HSAT log(SAT/δ) )
. Compared with this result, our algorithm’s regret is exponentially smaller when n and ζ are relatively small. Under this problem setting, the regret of Osband & Van Roy (2014b) is O ( nH √ ΓJT log(nJT ) ) . Our results is better by a factor of √ nHΓ.

heading: D HIGH PROBABILITY EVENTS
text: In this section, we discuss the high-prob. events, and assume that these events happen during the proof.
Algorithm 3 FMDP-BF (Detailed Description of Alg. 1) Input: δ L = ∅, initialize N((s, a)[Zi]) = 0 for any factored set Zi and any (s, a)[Zi] ∈ X [Zi] for episode k = 1, 2, · · · do
Set V k,H+1(s) = V k,H+1(s) = 0 for all s, a. 5: Let K = { (s, a) ∈ S ×A : ∩i=1,...,nNk((s, a)[ZPi ]) > 0 } Estimate R̂k,i(s, a) as the empirical mean if Nk−1((s, a)[ZRi ]) > 0, and 1 otherwise R̂(s, a) = 1m ∑m i=1 R̂i((s, a)[Z R i ])
Estimate P̂k(·|s, a) with empirical mean value for all (s, a) ∈ K for horizon h = H,H − 1, ..., 1 do
10: for s ∈ S do for a ∈ A do
if (s, a) ∈ K then Qk,h(s, a) = min{H, R̂k(s, a) + CBk(s, a) + P̂kV k,h+1(s, a)}
else 15: Qk,h(s, a) = H
end if end for πk,h(s) = arg maxaQk,h(s, a)
V k,h(s) = maxa∈AQk,h(s, a) 20: V k,h(s) = max { 0, R̂k(s, πk,h(s))− CBk(s, πk,h(s)) + P̂kV k,h+1(s, πk,h(s)) }
end for end for for step h = 1, · · · , H do
Take action ak,h = arg maxaQk,h(sk,h, a) 25: end for Update history trajectory L = L ⋃ {sk,h, ak,h, rk,h, sk,h+1}h=1,2,...,H , and update history
counter Nk−1((s, a)[Zi]). end for
Lemma D.1. (High prob. event) With prob. at least 1 − 2δ/3, the following events hold for any k, h, s, a:
|R̂k,i((s, a)[ZRi ])− R̄i((s, a)[ZRi ])| ≤
√ 2LRi
Nk−1((s, a)[ZRi ]) , i ∈ [m] (7)
|P̂k,i ∏ j 6=i Pk,jV ∗h (s, a)− n∏ j=1 PjV ∗h (s, a)| ≤
√ 2H2LP
Nk−1((s, a)[ZPi ]) , i ∈ [n] (8)
|(P̂k,i − Pk,i)(·|(s, a)[ZPi ])|1 ≤ 2
√ |Si|LP
Nk−1((s, a)[ZPi ]) +
4|Si|LP
3Nk−1((s, a)[ZPi ]) i ∈ [n] (9)
|(P̂k,i − Pk,i)(s′|(s, a)[ZPi ])| ≤ √ 2Pi(s′[i]|(s, a)[ZPi ])LP Nk−1((s, a)[ZPi ]) + LP 3Nk−1((s, a)[ZPi ]) i ∈ [n] (10)
K∑ k=1 H∑ h=1 ( P ( V̂k,h+1 − V πkh+1 ) (sk,h, ak,h)− ( V̂k,h+1 − V πkh+1 ) (sk,h+1) ) ≤ √ 2HT log(18SAT ) (11) K∑ k=1 H∑ h=1 ( P ( V̂k,h+1 − V ∗h+1 ) (sk,h, ak,h)− ( V̂k,h+1 − V ∗h+1 ) (sk,h+1) ) ≤ √ 2HT log(18SAT )
(12)
We define the above events as Λ1, and assume it happens during the proof.
Proof. By Hoeffding’s inequality and union bounds over all i ∈ [m], step k ∈ [K] and (s, a) ∈ X [ZRi ], we know that Inq. 7 holds with prob. 1 − δ9 for any i ∈ [m], k ∈ [K], (s, a) ∈ X [Z P i ]. Similarly, by Hoeffding’s inequality and union bounds over all i ∈ [n], step t and (s, a) ∈ X , Inq. 8 also holds with prob. 1 − δ9 for any i, s, a, k. Inq. 9 is the high probability bound on the L1 norm of the Maximum Likelihood Estimate, which is proved by Weissman et al. (2003). Inq. 10 can be proved with the use of Bernstein inequality and union bound (See Azar et al. (2017) for a similar derivation). Inq. 11 and Inq. 12 can be regarded as the summation of martingale difference sequences, which can be derived with the application of Azuma’s inequality. Finally, we take union bounds over all these inequalities, which indicates that Λ1 holds with prob. at least 1− 2δ/3.
For the proof of Thm. 2, we also need to consider the following high-prob. events. We define the following events as Λ2. During the proof of Thm. 2, we assume both Λ1 and Λ2 happen. Lemma D.2. With prob. at least 1− δ/3, the following events hold for any k, h, s, a:∣∣∣R̂k,i((s, a)[ZRi ])− R̄k,i((s, a)[ZRi ])∣∣∣ ≤ √ 2σ̂2R,i(s, a)L R i
Nk−1((s, a)[ZRi ]) + 8LRi 3Nk−1((s, a)[ZRi ]) , i ∈ [m]
(13)∣∣∣∣∣∣(P̂k,i − Pi) ∏ j 6=i PjV ∗h+1(s, a) ∣∣∣∣∣∣ ≤ √ 2σ2P,i(V ∗ h+1, s, a)L P Nk−1((s, a)[ZPi ])) + 2HLP 3Nk−1((s, a)[ZPi ]) , i ∈ [n] (14)
Nk((s, a)[Z P i ]) ≥
1
2 ∑ j<k wj,ZPi (s, a)−H log(18nX P i H/δ), i ∈ [n] (15)
Proof. Inq. 13 can be proved directly by empirical Bernstein inequality. Now we mainly focus on Inq. 14. By Bernstein’s inequality and union bounds over all s, a, k, h, we know that the following inequality holds with prob. at least 1− δ9 .∣∣∣∣∣∣(P̂k,i − Pi) ∏ j 6=i PjV ∗h+1(s, a)
∣∣∣∣∣∣ =
∑ s′[1:i−1]∈X [1:i−1] P(s′[1 : i− 1]|s, a) ∣∣∣∣∣∣ ( P̂k,i − Pi ) n∏ j=i+1 PjV ∗h+1(s, a) ∣∣∣∣∣∣ ≤
∑ s′[1:i−1]∈X [1:i−1] P(s′[1 : i− 1]|s, a) √√√√2 Vars′[i]∼Pi(·|(s,a)[ZPi ]) (Es′[i+1:n]∼P[i+1:n](·|s,a)Vh+1(s′) | s′[1 : i− 1])LP Nk−1((s, a)[ZPi ])
+ ∑
s′[1:i−1]∈X [1:i−1]
P(s′[1 : i− 1]|s, a) 2HL P
3Nk−1((s, a)[ZPi ])
≤
√ 2σ2(V ∗h+1, s, a)L P
Nk−1((s, a)[ZPi ])) +
2HLP
3Nk−1((s, a)[ZPi ])
The last inequality is due to Jensen’s inequality. That is,∑ s′[1:i−1] P(s′[1 : i− 1]) √ C1 Nk−1((s, a)[ZPi ]) ≤ √√√√ ∑ s′[1:i−1] C1P(s′[1 : i− 1]) Nk−1((s, a)[ZPi ])
= √ 2σ2(V ∗h+1, s, a)L
P · 1 Nk−1((s, a)[ZPi ])
where P(s′[1 : i− 1]) is a shorthand of P(s′[1 : i− 1]|s, a), and C1 here denotes
2 Vars′[i]∼Pi(·|(s,a)[ZPi ]) ( Es′[i+1:n]∼P[i+1:n](·|s,a)V (s ′) | s′[1 : i− 1] ) LP .
Inq. 15 follows the same proof of the failure event FN in section B.1 of Dann et al. (2019).

heading: E PROOF OF THEOREM 5

heading: E.1 ESTIMATION ERROR DECOMPOSITION
text: Lemma E.1. The estimation error can be decomposed in the following way: |(P̂k − P)(·|s, a)|1 ≤ n∑ i=1 |(P̂k,i − Pi)(·|(s, a)[ZPi ])|1 (16) |(P̂k − P)V (s, a)| ≤ n∑ i=1 ∣∣∣∣∣∣(P̂k,i − Pi)  n∏ j 6=i,j=1 Pj V (s, a) ∣∣∣∣∣∣
+ n∑ i=1 n∑ j 6=i,j=1 |V |∞ ∣∣∣(P̂k,i − Pi) (·|(s, a)[ZPi ])∣∣∣ 1 · ∣∣∣(P̂k,j − Pj) (·|(s, a)[ZPj ])∣∣∣ 1 ,
(17)
here V denotes any value function mapping from S to R, e.g. V ∗h+1 or V̂k,h+1 − V ∗h+1.
Proof. Inq. 16 has the same form of Lemma 32 in Li (2009) and Lemma 1 in Osband & Van Roy (2014b). We mainly focus on Inq. 17. We can decompose the difference in the following way:∣∣∣(P̂k − P)V (s, a)∣∣∣ ≤
∣∣∣∣∣(P̂k,n − Pn) n−1∏ i=1 PiV (s, a) ∣∣∣∣∣+ ∣∣∣∣∣Pn( n−1∏ i=1 P̂k,i − n−1∏ i=1 Pi)V (s, a) ∣∣∣∣∣+ ∣∣∣∣∣(P̂k,n − Pn)( n−1∏ i=1 P̂k,i − n−1∏ i=1 Pi)V ∗(s, a) ∣∣∣∣∣ (18)
For the last term of Inq. 18, we have∣∣∣∣∣(P̂k,n − Pn)( n−1∏ i=1 P̂k,i − n−1∏ i=1 Pi)V (s, a) ∣∣∣∣∣ ≤ ∣∣∣(P̂k,n − Pn) (·|(s, a)[ZPn ])∣∣∣
1 · ∣∣∣∣∣ n−1∏ i=1 P̂k,i(·|s, a[ZPi ])− n−1∏ i=1 Pi(·|s, a[ZPi ]) ∣∣∣∣∣ 1 · |V |∞
≤ ∣∣∣(P̂k,n − Pn) (·|(s, a)[ZPn ])∣∣∣
1 n−1∑ i=1 ∣∣∣(P̂k,i − Pi) (·|(s, a)[ZPi ])∣∣∣ 1 · |V |∞,
Where the last inequality is due to Inq. 16. For the second part of Inq. 18, we can further decompose the term as:∣∣∣∣∣Pn ( n−1∏ i=1 P̂k,i − n−1∏ i=1 Pi ) V (s, a) ∣∣∣∣∣ ≤
∣∣∣∣∣Pn (P̂k,n−1 − Pn−1) n−2∏ i=1 PiV (s, a) ∣∣∣∣∣+ ∣∣∣∣∣PnPn−1 ( n−2∏ i=1 P̂k,i − n−2∏ i=1 Pi ) V (s, a) ∣∣∣∣∣ +
∣∣∣∣∣Pn (P̂k,n−1 − Pn−1) ( n−2∏ i=1 P̂k,i − n−2∏ i=1 Pi ) V (s, a) ∣∣∣∣∣ (19) Following the same decomposition technique, we can prove Inq. 17 by recursively decomposing the second term over all possible n: |(P̂k − P)V ∗(s, a)| ≤ n∑ i=1 ∣∣∣∣∣∣(P̂k,i − Pi)  n∏ j 6=i,j=1 Pj V (s, a) ∣∣∣∣∣∣
+ n∑ i=1 n∑ j 6=i,j=1 ∣∣∣(P̂k,i − Pi) (·|(s, a)[ZPi ])∣∣∣ 1 · ∣∣∣(P̂k,j − Pj) (·|(s, a)[ZPj ])∣∣∣ 1 · |V |∞
Lemma E.2. Under event Λ1, then the following Inequality holds:
|R̂k(s, a)− R̄(s, a)| ≤ 1
m m∑ i=1
√ 2LRi
Nk−1((s, a)[ZRi ]) (20)
|(P̂k − P)(·|s, a)|1 ≤ n∑ i=1
(√ 4|Si|LP
Nk−1((s, a)[ZPi ]) +
4|Si|LP
3Nk−1((s, a)[ZPi ])
) (21)
|(P̂k − P)V ∗(s, a)| ≤ n∑ i=1
√ 2H2LP
Nk−1((s, a)[ZPi ])
+ n∑ i=1 n∑ j 6=i,j=1 H
(√ 4|Si|LP
Nk−1((s, a)[ZPi ]) +
4|Si|LP
3Nk−1((s, a)[ZPi ])
)(√ 4|Sj |LP
Nk−1((s, a)[ZPj ]) +
4|Sj |LP
3Nk−1((s, a)[ZPj ]) ) (22)
Proof. Inq. 20 can be proved by Lemma D.1:
|R̂k(s, a)− R̄(s, a)| ≤ 1
m m∑ i=1 |R̂k(s, a)− R̄(s, a)| ≤ 1 m m∑ i=1
√ 2LRi
Nk−1((s, a)[ZRi ])
Inq. 21 follows directly by applying Lemma D.1 to Lemma E.1. |(P̂k − P)(·|s, a)|1 ≤ n∑ i=1 |(P̂k,i − Pi)(·|(s, a)[ZPi ])|1 ≤ n∑ i=1 (√ 4|Si|LP Nk−1((s, a)[ZPi ]) +
4|Si|LP
3Nk−1((s, a)[ZPi ])
)
Similarly, Inq 22 can be proved by:
|(P̂k − P)V ∗(s, a)|
≤ n∑ i=1 ∣∣∣∣∣∣(P̂k,i − Pi)  n∏ j 6=i,j=1 Pj V ∗(s, a) ∣∣∣∣∣∣
+ n∑ i=1 n∑ j 6=i,j=1 H ∣∣∣(P̂k,i − Pi) (·|(s, a)[ZPi ])∣∣∣ 1 · ∣∣∣(P̂k,j − Pj) (·|(s, a)[ZPj ])∣∣∣ 1
≤ n∑ i=1
√ 2H2LP
Nk−1((s, a)[ZPi ])
+ n∑ i=1 n∑ j 6=i,j=1 H
(√ 4|Si|LP
Nk−1((s, a)[ZPi ]) +
4|Si|LP
3Nk−1((s, a)[ZPi ])
)(√ 4|Sj |LP
Nk−1((s, a)[ZPj ]) +
4|Sj |LP
3Nk−1((s, a)[ZPj ])
)

heading: E.2 OPTIMISM
text: Lemma E.3. (Optimism) Under event Λ1, V̂k,h(s) ≥ V ∗h (s) for any k, h, s.
Proof. We prove the Lemma by induction. Firstly, for h = H + 1, the inequality holds trivially since V̂k,H+1(s) = V ∗H+1(s) = 0.
V̂k,h(s)− V ∗h (s) ≥R̂k(s, π∗h(s)) + CBk(s, π∗h(s)) + P̂kV̂k,h+1(s, π∗h(s))− R̄(s, π∗h(s))− PV ∗h+1(s, π∗h(s)) =R̂k(s, π ∗ h(s))− R̄(s, π∗h(s)) + CBk(s, π∗h(s)) + P̂k(V̂k,h+1 − V ∗h+1)(s, π∗h(s)) + (P̂k − P)V ∗h+1(s, π∗(s)) ≥R̂k(s, π∗h(s))− R̄(s, π∗h(s)) + CBk(s, π∗h(s)) + (P̂k − P)V ∗h+1(s, π∗(s)) ≥0
The first inequality is due to V̂k,h(s) ≥ Q̂k,h(s, π∗h(s)). The second inequality follows by induction condition that V̂k,h+1(s) ≥ V ∗h+1(s) for all s. The last inequality is due to Inq. 20 and Inq. 22 in Lemma E.2.

heading: E.3 PROOF OF THEOREM 5
text: Now we are ready to prove Thm. 5.
Proof. (Proof of Thm. 5)
V ∗h (sk,h)− V πk h (sk,h)
≤V̂k,h(sk,h)− V πkh (sk,h) =R̂k(sk,h, πk,h(sk,h)) + P̂kV̂k,h+1(sk,h, πk,h(sk,h)) + CBk(sk,h, πk,h(sk,h)) − R̄(sk,h, πk,h(sk,h))− PV πkh+1(sk,h, πk,h(sk,h)) =V̂k,h+1(sk,h+1)− V πkh+1(sk,h+1) + R̂k(s, πk,h(sk,h))− R̄(s, πk,h(sk,h)) + CBk(sk,h, π ∗ h(s))
+ P ( V̂k,h+1 − V πkh+1 ) (sk,h, πk,h(sk,h))− ( V̂k,h+1 − V πkh+1 ) (sk,h+1)
+ ( P̂k − P ) V ∗h+1(sk,h, πk,h(sk,h))
+ ( P̂k − P )( V̂k,h+1 − V ∗h+1 ) (sk,h, πk,h(sk,h))
The first inequality is due to optimism V̂k,h(sk,h) ≥ V ∗h (sk,h). The first equality is due to Bellman equation for V πkh and V̂k,h.
For notation simplicity, we define
δ1k,h = R̂k(s, πk,h(sk,h))− R̄(s, πk,h(sk,h) δ2k,h = P ( V̂k,h+1 − V πkh+1 ) (sk,h, πk,h(sk,h))− ( V̂k,h+1 − V πkh+1 ) (sk,h+1)
δ3k,h = ( P̂k − P ) V ∗h+1(sk,h, πk,h(sk,h))
Firstly we focus on the upper bound of ( P̂k,h − P )( V̂k,h+1 − V ∗h+1 ) (sk,h, πk,h(sk,h)). We bound this term following the idea of Azar et al. (2017).( P̂k − P )( V̂k,h+1 − V ∗h+1 ) (sk,h, ak,h) ≤ n∑ i=1 (P̂i − Pi) n∏ j=1,j 6=i Pj ( V̂k,h+1 − V ∗h+1 ) (sk,h, ak,h)
+ n∑ i=1 n∑ j=1 H ∣∣∣(P̂i − Pi) (·|(sk,h, ak,h)[ZPi ])∣∣∣ 1 ∣∣∣(P̂j − Pj) (·|(sk,h, ak,h)[ZPj ])∣∣∣ 1
≤ n∑ i=1  ∑ s′[i]∈S[i] √ 2 Pi(s′[i]|X [ZPi ])LP Nk−1((s, a)[ZPi ]) + LP 3Nk−1((s, a)[ZPi ])  n∏ j=1,j 6=i Pj ( V̂k,h+1 − V ∗h+1 ) (sk,h, ak,h)
+ n∑ i=1 n∑ j 6=i,j=1 H
(√ 4|Si|LP
Nk−1((s, a)[ZPi ]) +
4|Si|LP
3Nk−1((s, a)[ZPi ])
)(√ 4|Sj |LP
Nk−1((s, a)[ZPj ]) +
4|Sj |LP
3Nk−1((s, a)[ZPj ])
)
≤ n∑ i=1 ∑ s′[i]∈S[i] √ 2 Pi(s′[i]|X [ZPi ])LP Nk−1((s, a)[ZPi ]) n∏ j=1,j 6=i Pj ( V̂k,h+1 − V ∗h+1 ) (sk,h, ak,h) + n∑ i=1
|Si|HLP
3Nk−1((s, a)[ZPi ])
+ n∑ i=1 n∑ j 6=i,j=1 H
(√ 4|Si|LP
Nk−1((s, a)[ZPi ]) +
4|Si|LP
3Nk−1((s, a)[ZPi ])
)(√ 4|Sj |LP
Nk−1((s, a)[ZPj ]) +
4|Sj |LP
3Nk−1((s, a)[ZPj ])
)
The first inequality is due to Lemma E.1. The second inequality is because of Lemma D.1, and the last inequality is due to the fact that ∣∣∣V̂k,h+1 − V ∗h+1∣∣∣∞ ≤ H . For each i ∈ [n], we consider those s′[i] satisfying Nk−1((s, a)[ZPi ])Pi(s′[i]|(sk,h, ak,h)[ZPi ]) ≥ 2n2H2LP and Nk−1((s, a)[ZPi ])Pi(s′[i]|(sk,h, ak,h)[ZPi ]) ≤ 2n2H2LP separately.
For those s′[i] satisfying Nk−1((s, a)[ZPi ])Pi(s′[i]|sk,h, ak,h) ≥ 2n2H2LP , the first term can be bounded by
n∑ i=1 ∑ s′[i]∈S[i] √ 2 Pi(s′[i]|X [ZPi ])LP Nk−1((s, a)[ZPi ]) n∏ j=1,j 6=i Pj ( V̂k,h+1 − V ∗h+1 ) (sk,h, ak,h)
= n∑ i=1 ∑ s′[i]∈S[i] Pi(s′[i]|X [ZPi ])
√ 2
LP
Pi(s′[i]|X [ZPi ])Nk−1((s, a)[ZPi ]) n∏ j=1,j 6=i Pj ( V̂k,h+1 − V ∗h+1 ) (sk,h, ak,h)
≤ 1 H
P ( V̂k,h+1 − V ∗h+1 ) (sk,h, ak,h)
= 1
H
( V̂k,h+1 − V ∗h+1 ) (sk,h+1, ak,h+1)
+ 1
H
( P ( V̂k,h+1 − V ∗h+1 ) (sk,h, ak,h)− ( V̂k,h+1 − V ∗h+1 ) (sk,h+1, ak,h+1) ) where the second term can be regarded as a martingale difference sequence, and we denote it as δ4k,h.
For those s′[i] satisfying Nk−1((s, a)[ZPi ])Pi(s′[i]|sk,h, ak,h) ≤ 2n2H2LP , the summation can be bounded by
n∑ i=1
nH2|Si|LP
Nk−1((s, a)[ZPi ])
For notation simplicity, we define δ5k,h as:
δ5k,h = n∑ i=1 n∑ j 6=i,j=1 H
(√ 4|Si|LP
Nk−1((s, a)[ZPi ]) +
4|Si|LP
3Nk−1((s, a)[ZPi ])
)(√ 4|Sj |LP
Nk−1((s, a)[ZPj ]) +
4|Sj |LP
3Nk−1((s, a)[ZPj ])
)
+ n∑ i=1 2nH2|Si|LP Nk−1((s, a)[ZPi ])
To sum up, by the above analysis, we prove that( P̂k,h − P )( V̂k,h+1 − V ∗h+1 ) (sk,h, πk,h(sk,h)) ≤ 1
H
( V̂k,h+1 − V ∗h+1 ) (sk,h+1, ak,h+1) + δ 4 k,h + δ 5 k,h
Now we are ready to summarize all the terms in the regret. Firstly, we recursively calculate the regret for all h ∈ [H].
V ∗1 (sk,1, ak,1)− V πk 1 (sk,1, ak,1) ≤ V̂k,1(sk,1, ak,1)− V πk(sk,1, ak,1)
≤CB(sk,1, ak,1) + δ1k,1 + δ2k,1 + δ3k,1 + δ4k,1 + δ5k,1 + (1 + 1
H ) (Vk,2(sk,2, ak,2)− V πk2 (sk,2, ak,2))
· · ·
≤ H∑ h=1 ( 1 + 1 H )h−1 ( CBk(sh, ah) + δ 1 k,h + δ 2 k,h + δ 3 k,h + δ 4 k,h + δ 5 k,h ) ≤
H∑ h=1 e ( CBk(sh, ah) + δ 1 k,h + δ 2 k,h + δ 3 k,h + δ 4 k,h + δ 5 k,h )
Then we sum up the regret over k episodes,
Reg(K) ≤ K∑ k=1 (V ∗1 (s1, a1)− V πk 1 (s1, a1))
≤ K∑ k=1 H∑ h=1 e ( CBk(sh, ah) + δ 1 k,h + δ 2 k,h + δ 3 k,h + δ 4 k,h + δ 5 k,h ) δ2k,h and δ 4 k,h can be regarded as martingale difference sequence, the summation of which can
be bounded by O(H √ T log(T )) by Lemma E.2, while δ1k,h and δ 3 k,h can also be bounded by Lemma E.2. The summation of different terms in δ1k,h, δ 3 k,h, δ 4 k,h and δ 5 k,h can be separated into the following categories. In the following proof, we use C to denote the dependence of other parameters except the counters Nk((sk,h, ak,h)[Zi])
For those terms of the form C√ Nk((sk,h,ak,h)[Zi]) , we have
∑ k ∑ h C√ Nk((sk,h, ak,h)[Zi]) ≤HC + ∑
x[Zi]∈X [Zi]
NK(x[Zi])∑ c=1 C√ c
=HC + ∑
x[Zi]∈X [Zi]
C √ NK(x[Zi])
≤HC + C √ |X [Zi]|T
The last inequality is due to Cauchy-Schwarz inequality. This term influence the main factors in the final regret.
For those terms of the form CNk((sk,h,ak,h)[Zi]) , we have
∑ k ∑ h
C
Nk((sk,h, ak,h)[Zi]) ≤HC + ∑ x[Zi]∈X [Zi] NK(x[Zi])∑ c=1 C c
≤HC + ∑
x[Zi]∈X [Zi]
C ln (NK(x[Zi]))
≤HC + C|X [Zi]| lnT,
which has only logarithmic dependence on T .
For those terms of the form C√ Nk((sk,h,ak,h)[Zi])Nk((sk,h,ak,h)[Zj ]) . we define Nk((s, a)[Zi], (s, a)[Zj ]) as the number of times that agent has encountered (s, a)[Zi] and (s, a)[Zj ] simultaneously for the first k episodes. It is not hard to find that Nk((s, a)[Zi]) ≥ Nk((s, a)[Zi], (s, a)[Zj ]) and Nk((s, a)[Zj ]) ≥ Nk((s, a)[Zi], (s, a)[Zj ]).∑
k ∑ h C√ Nk((sk,h, ak,h)[Zi])Nk((sk,h, ak,h)[Zj ])
≤ ∑ k ∑ h
C
Nk((sk,h, ak,h)[Zi], (sk,h, ak,h)[Zj ]) ≤HC + ∑
x[Zi∪Zj ]∈X [Zi∪Zj ]
C ln (Nk((sk,h, ak,h)[Zi], (sk,h, ak,h)[Zj ]))
≤HC + C|X [Zi ∪ Zj ]| lnT,
which also has only logarithmic dependence on T .
For other terms with the form of C (Nk((sk,h,ak,h)[Zi])) 2 and C Nk((sk,h,ak,h)[Zi]) √ Nk((sk,h,ak,h)[Zj ]) , the summation of these terms has no dependence on T , which is negligible since T is the dominant factor.
By bounding these different kinds of terms with the above methods, we can finally show that
Reg(K) = O  1 m m∑ i=1 √ |X [ZRi ]|T log(10mT |X [ZRi ]|/δ) + n∑ j=1 H √ |X [ZPj ]|T log(10nTSA/δ)  Here O hides the lower-order factors w.r.t T .

heading: F PROOF OF THEOREM 2

heading: F.1 ESTIMATION ERROR DECOMPOSITION
text: Lemma F.1. Under event Λ1 and Λ2, we have∣∣∣R̂k(s, a)− R̄(s, a)∣∣∣ ≤ 1 m m∑ i=1 √ 2σ̂2R,i(s, a)L R i Nk−1((s, a)[ZRi ]) + 1 m m∑ i=1 8LRi 3Nk−1((s, a)[ZRi ])
|(P̂k − P)V ∗h+1(s, a)|
≤ n∑ i=1 √2σ2P,i(V ∗h+1, s, a)LP Nk−1((s, a)[ZPi ])) + 2HLP 3Nk−1((s, a)[ZPi ])  +
n∑ i=1 n∑ j 6=i,j=1 H
(√ 4|Si|LP
Nk−1((s, a)[ZPi ]) +
4|Si|LP
3Nk−1((s, a)[ZPi ])
)(√ 4|Sj |LP
Nk−1((s, a)[ZPj ]) +
4|Sj |LP
3Nk−1((s, a)[ZPj ])
)
Proof. The first inequality follows directly by the definition that R(s, a) = 1m ∑m i=1Ri(s, a) and Lemma D.2. We now prove the second inequality. By Lemma E.1, we have |(P̂k − P)V ∗h+1(s, a)| ≤ n∑ i=1 ∣∣∣∣∣∣(P̂k,i − Pi)  n∏ j 6=i,j=1 Pj V ∗h+1(s, a) ∣∣∣∣∣∣
+ n∑ i=1 n∑ j 6=i,j=1 H ∣∣∣(P̂k,i − Pi) (·|(s, a)[ZPi ])∣∣∣ 1 · ∣∣∣(P̂k,j − Pj) (·|(s, a)[ZPj ])∣∣∣ 1 ,
By Inq. 9 in Lemma D.1 and Inq. 14 in Lemma D.2, we have
|(P̂− P)V ∗h+1(s, a)|
≤ n∑ i=1 √2σ2P,i(V ∗h+1, s, a)LP Nk−1((s, a)[ZPi ])) + 2HLP 3Nk−1((s, a)[ZPi ])  +
n∑ i=1 n∑ j 6=i,j=1 H
(√ 4|Si|LP
Nk−1((s, a)[ZPi ]) +
4|Si|LP
3Nk−1((s, a)[ZPi ])
)(√ 4|Sj |LP
Nk−1((s, a)[ZPj ]) +
4|Sj |LP
3Nk−1((s, a)[ZPj ])
)

heading: F.2 OMITTED PROOF IN SECTION 4.2
text: Proof. (Proof of Theorem. 1) ω2h(s)
=E [ (Jh:H(sh)− Vh(sh))2 | sh = s ] = ∑ s′ P(s′|s)E [ (Jh+1:H(sh+1) + rh − Vh(sh))2 | sh = s, sh+1 = s′
] = ∑ s′ P(s′|s)E [ J2h+1:H(sh+1) + r 2 h + V 2 h (sh) | sh = s, sh+1 = s′
] + ∑ s′ P(s′|s)E [2rh(Jh+1:H(sh+1)− Vh(sh))− 2Jh+1:H(sh+1)Vh(sh) | sh = s, sh+1 = s′]
Given sh = s, sh+1 = s′, rh, Vh(sh) and Jh+1:H(sh+1) are conditionally independent, thus we have
E[2rh(Jh+1:H(sh+1)− Vh(sh)) | sh = s, sh+1 = s′] = E[2R̄(sh)(Vh+1(sh+1)− Vh(sh)) | sh = s, sh+1 = s′] E[2Jh+1:H(sh+1)Vh(sh) | sh = s, sh+1 = s′] = E[2Vh+1(sh+1)Vh(sh) | sh = s, sh+1 = s′]
Therefore, we have
ω2h(s) = ∑ s′ P(s′|s)E [ J2h+1:H(sh+1) + r 2 h + V 2 h (sh) | sh = s, sh+1 = s′ ] + ∑ s′ P(s′|s)E [ 2R̄(sh)(Vh+1(sh+1)− Vh(sh))− 2Vh+1(sh+1)Vh(sh) | sh = s, sh+1 = s′
] =E [ r2h − R̄2(sh) | sh = s
] + ∑ s′ P(s′|s)E [ J2h+1:H(sh+1)− (Vh(sh)− R̄(sh))2 | sh = s, sh+1 = s′ ] =E [ r2h − R̄2(sh) | sh = s
] + ∑ s′ P(s′|s)E
J2h+1:H(sh+1)− (∑
s′′
P(s′′|s)Vh+1(s′′) )2 | sh = s, sh+1 = s′  =E [ r2h − R̄2(sh) | sh = s
] + ∑ s′ P(s′|s)V 2h+1(s′)− (∑ s′′ P(s′′|s)Vh+1(s′′) )2 + ∑ s′ P(s′|s)E [ J2h+1:H(sh+1)− V 2h+1(sh+1) | sh+1 = s′ ] (23)
The second equality is due to the fact that Vh(s) = R̄(s) + ∑ s′ P(s′|s)Vh+1(s′).
For the factored rewards, since the rewards rh,i are conditionally independent give s, we have
E [ r2h − R̄2(sh) | sh = s ] = 1
m2 m∑ i=1 σ2R,i(s)
For the factored transition, we decompose the variance in the following way:
∑ s′ P(s′|s)V 2h+1(s′)− (∑ s′′ P(s′′|s)Vh+1(s′′) )2 − σ2P,1,h(s)
= ∑ s′ P(s′|s)V 2h+1(s′)− ∑ s′′[1] P(s′′[1] | s)  ∑ s′′[2:n] P2:n(s′′[2 : n]|s)Vh+1(s′′) 2 = ∑ s′[1] P(s′[1] | s)  ∑ s′[2:n] P2:n(s′[2 : n]|s)V 2h+1(s′)−  ∑ s′′[2:n] P2:n(s′′[2 : n]|s)Vh+1([s′[1], s′′[2 : n]]) 2 
Here ([s′[1], s′′[2 : n]] denotes the vector s′′ with s′′[1] replaced with s′[1]. By subtracting σ2P,i,h(s) for i = 2, ..., n in the above way, we can show that
∑ s′ P(s′|s)V 2h+1(s′)− (∑ s′′ P(s′′|s)Vh+1(s′′) )2 − n∑ i=1 σ2P,i,h(s) = 0 (24)
Plugging Eqn. 24 back to Eqn. 23, we have
ω2h(s) = ∑ s′ P(s′|s)ω2h+1(s′) + n∑ i=1 σ2P,i,h(s) + 1 m2 m∑ i=1 σ2R,i(s),
Proof. (Proof of Corollary 1.1) We can regard the MDP with given policy π as a Markov chain. By Theorem 1, we have
ω2h(s) = ∑ s′ P(s′|s, π(s))ω2h+1(s′) + n∑ i=1 σ2P,i(V π h , s, a) + 1 m2 m∑ i=1 σ2R,i(s, a)
By recursively decomposing the variance until step H , we have:
ω2h(s1) = H∑ h=1 ∑ (s,a)∈X wh(s, a) ( n∑ i=1 σ2P,i(V π h , s, a) + 1 m2 m∑ i=1 σ2R,i(s, a) )
Since ω2h(s1) = E [ (Jh:H(sh)− Vh(s))2 |sh = s ] ≤ H2, we can immediately reach the conclusion.

heading: F.3 THE ”GOOD” SET CONSTRUCTION
text: The construction of the ”good” set is similar with that in Dann et al. (2017) and Zanette & Brunskill (2019), though we modify it to handle this more complicated factored setting. The idea is to partition each factored state-action subspace at each episode into two sets, the set of state-action pairs that have been visited sufficiently often (so that we can lower bound these visits by their expectations using standard concentration inequalities) and the set of (s, a) that were not visited often enough to cause high regret. That is: Definition 4. (The Good Set) The set Lk,i for factored transition Pi is defined as:
Lk,i def = (x[ZPi ]) ∈ X [ZPi ] : 14 ∑ j<k wj,ZPi (x) ≥ H log(18nX P i H/δ) +H  The following two Lemmas follow the same idea of Lemma 6 and Lemma 7 in Zanette & Brunskill (2019). Lemma F.2. Under event Λ1 and Λ2, if (s, a)[ZPi ] ∈ Li,k, we have
Nk((s, a)[Z P i ]) ≥
1
4 ∑ j<k wj,ZPi (s, a).
Proof. By Lemma D.2, we have
Nk((s, a)[Z P i ]) ≥
1
2 ∑ j<k wj((s, a)[Z P i ])−H log(18nXPi H/δ).
Since (s, a)[ZPi ] ∈ Li,k, we have 14 ∑ j<k wj,ZPi (x) ≥ H log(18nX P i H/δ) +H . That is,
Nk((s, a)[Z P i ]) ≥
1
2 ∑ j<k wj((s, a)[Z P i ])−H log(18nXPi H/δ)
≥ 1 2 ∑ j<k wj((s, a)[Z P i ])− 1 4 ∑ j<k wj((s, a)[Z P i ])
= 1
4 ∑ j<k wj((s, a)[Z P i ])
Lemma F.3. It holds that K∑ k=1 H∑ h=1 ∑ (s,a)[ZPi ]/∈Lk,i wk,h,ZPi (s, a) ≤ 8HX P i log(10nX P i H/δ).
Proof. For those (s, a)[ZPi ] /∈ Lk,i, we have 14 ∑ j<k wj,ZPi (x) ≤ H log(10nX P i H/δ) + H ≤ 2H log(10nXPi H/δ). That is,
K∑ k=1 H∑ h=1 ∑ (s,a)[ZPi ]/∈Lk,i wk,h,ZPi (s, a) ≤ ∑ (s,a)[ZPi ] 8H log(10nXPi H/δ) ≤ 8HXPi log(10nXPi H/δ)
Lemma F.2 shows that we can lower bound the visiting count of a certain (s, a)[ZPi ] if the visiting probability of (s, a)[ZPi ] is sufficient large. Lemma F.3 shows that those (s, a)[Z P i ] with little visiting probability cause little contribution to the final regret.

heading: Lemma F.4.
text: K∑ k=1 H∑ h=1 ∑ (s,a)[ZPi ]∈Lk,i wk,h,ZPi (s, a) Nk((s, a)[ZPi ]) ≤ 4XPi log T. Proof. For those (s, a)[ZPi ] ∈ Lk,i, we have Nk((s, a)[ZPi ]) ≥ 14 ∑ j<k wj,ZPi (s, a). Therefore, we have K∑ k=1 H∑ h=1 ∑ (s,a)[ZPi ]∈Lk,i wk,h,ZPi (s, a) Nk((s, a)[ZPi ]) ≤ K∑ k=1 H∑ h=1 ∑ (s,a)[ZPi ]∈Lk,i 4wk,h,ZPi (s, a)∑ j<k wj,ZPi (s, a)
≤ ∑
(s,a)[ZPi ]∈XPi
K∑ k=1 wk,ZPi (s, a)∑ j<k wj,ZPi (s, a)
≤4XPi log T
Lemma F.5. For factored set ZPi of transition, we have:
K∑ k=1 H∑ h=1 ∑ (s,a)∈X
wk,h(s, a)
Nk−1((s, a)[ZPi ]) ≤8XPi log T (25)
K∑ k=1 H∑ h=1 ∑ (s,a)∈X wk,h(s, a)√ Nk−1((s, a)[ZPi ])Nk−1((s, a)[Z P j ]) ≤8XPi log T (26)
K∑ k=1 H∑ h=1 ∑ (s,a)∈X wk,h(s, a)√ Nk−1((s, a)[ZPi ]) ( Nk−1((s, a)[ZPj ]) ) 1 4 ≤8 √ XPi,jT 1/4 log T (27)
where XPi,j = |X[ZPi ∪ ZPj ]|.
For factored set ZRi of rewards, similarly we have:
K∑ k=1 H∑ h=1 ∑ (s,a)∈X
wk,h(s, a)
Nk−1((s, a)[ZRi ]) ≤8XRi log T (28)
K∑ k=1 H∑ h=1 ∑ (s,a)∈X wk,h(s, a)√ Nk−1((s, a)[ZRi ])Nk−1((s, a)[Z R j ]) ≤8XRi log T (29)
K∑ k=1 H∑ h=1 ∑ (s,a)∈X wk,h(s, a)√ Nk−1((s, a)[ZRi ]) ( Nk−1((s, a)[ZRj ]) ) 1 4 ≤8 √ XRi,jT 1/4 log T (30)
where XRi,j = |X[ZRi ∪ ZRj ]|.
Proof. We only prove the inequalities for the factored set of transition. The inequalities for the factored set of rewards can be proved in the same manner.
For Inq. 25, we define Xi((s, a)[ZPi ]) = {x ∈ X | x[ZPi ] = (s, a)[ZPi ]}, then we have K∑ k=1 H∑ h=1 ∑ (s,a)∈X wk,h(s, a) Nk−1((s, a)[ZPi ]) = ∑ k,h ∑ (s,a)[ZPi ]∈X [ZPi ] wk,h,ZPi (s, a) ∑ (s1,a1)∈Xi((s,a)[ZPi ]) wk,h(s1,a1) w k,h,ZP i (s,a) Nk−1((s, a)[ZPi ])
= ∑ k,h ∑ (s,a)[ZPi ]∈X [ZPi ] wk,h,ZPi (s, a) Nk−1((s, a)[ZPi ])
= ∑ k,h ∑ (s,a)[ZPi ]∈Lk,i wk,h,ZPi (s, a) Nk−1((s, a)[ZPi ]) + ∑ k,h ∑ (s,a)[ZPi ]/∈Lk,i wk,h,ZPi (s, a) Nk−1((s, a)[ZPi ])
≤ ∑ k,h ∑ (s,a)[ZPi ]∈Lk,i wk,h,ZPi (s, a) Nk−1((s, a)[ZPi ]) + √√√√∑ k,h ∑ (s,a)[ZPi ]/∈Lk,i wk,h,ZPi (s, a) ∑ k,h ∑ (s,a)[ZPi ]/∈Lk,i
1
Nk−1((s, a)[ZPi ])
≤4XPi log T + √ 8HXPi log(10nX P i H/δ)
≤8XPi log T
In the first equality, we firstly categorize (s, a) based on their value (s, a)[ZPi ] and sum up over all possible choice of (s, a)[ZPi ], then we sum up the value in each category in the inner summation. The second equality is due to ∑ (s1,a1)∈Xi((s,a)[ZPi ]) wk,h(s1,a1) w
k,h,ZP i (s,a) = 1. The first inequality is due to
Cauchy-Schwarz inequality. The second inequality is due to Lemma F.4 and Lemma F.3. The last inequality is due to the assumption that XPi ≥ H log(10nXPi H/δ).
For Inq. 26 and Inq. 27, we define ZPi,j = Z P i ∪ ZPj . For the factored set ZPi,j , similarly we have
K∑ k=1 H∑ h=1 ∑ (s,a)[ZPi,j ]∈Lk,i wk,h,ZPi,j (s, a) Nk((s, a)[ZPi,j ]) ≤4XPi,j log T
K∑ k=1 H∑ h=1 ∑ (s,a)[ZPi,j ]/∈Lk,i wk,h,ZPi,j (s, a) ≤8HX P i,j log(10nX P i,jH/δ),
By the definition of ZPi,j , we know that Nk−1((s, a)[Z P i ]) ≥ Nk−1((s, a)[ZPi,j ]) and Nk−1((s, a)[Z P j ]) ≥ Nk−1((s, a)[ZPi,j ]). Therefore, we have
K∑ k=1 H∑ h=1 ∑ (s,a)∈X wk,h(s, a)√ Nk−1((s, a)[ZPi ])Nk−1((s, a)[Z P j ]) ≤ K∑ k=1 H∑ h=1 ∑ (s,a)∈X
wk,h(s, a)
Nk−1((s, a)[ZPi,j ])
K∑ k=1 H∑ h=1 ∑ (s,a)∈X wk,h(s, a)√ Nk−1((s, a)[ZPi ]) ( Nk−1((s, a)[ZPj ]) ) 1 4 ≤ K∑ k=1 H∑ h=1 ∑ (s,a)∈X wk,h(s, a)( Nk−1((s, a)[ZPi,j ]) ) 3 4
The following proof of Inq. 26 and Inq. 27 shares the same idea of the proof of Inq. 25.

heading: F.4 TECHNICAL LEMMAS ABOUT VARIANCE
text: In this subsection, we prove several technical lemmas about variance. For notation simplicity, we use Ei and E[i:j] as a shorthand of Es′[i]∼Pi(·|(s,a)[ZPi ]) and Es′[i:j]∼P[i:j](·|(s,a)[ZP[i:j]]). Similarly, we
use Vi and V[i:j] as a shorthand of Vs′[i]∼Pi(·|(s,a)[ZPi ]) and Vs′[i:j]∼P[i:j](·|(s,a)[ZP[i:j]]). For those w.r.t the empirical transition P̂k, we use Êk and V̂k to denote the corresponding expectation and variance. For example, Es′[i]∼P̂k,i(·|(s,a)[ZPi ]) is denoted as Êk,i.
Lemma F.6. Under event Λ1, Λ2, we have:∣∣σ̂2P,k,i(V, s, a)− σ2P,i(V, s, a)∣∣ ≤ 4H2 n∑ j=1 ( 2 √ |Sj |LP Nk−1((s, a)[ZPj ]) +
4|Sj |LP
3Nk−1((s, a)[ZPj ])
) ,
where V denotes some given function mapping from S to R.

heading: Proof.
text: |σ̂2P,k,i(V, s, a)− σ2P,i(V, s, a)| =|Ê[1:i−1]V̂iÊ[i+1:n]V (s′)− E[1:i−1]ViE[i+1:n]V (s′)| (31)
≤|Ê[1:i−1]V̂iÊ[i+1:n]V (s′)− E[1:i−1]V̂iÊ[i+1:n]V (s′)| (32)
+ |E[1:i−1]V̂iÊ[i+1:n]V (s′)− E[1:i−1]ViE[i+1:n]V (s′)| (33)
We bound Equ. 32 and 33 separately.
For equ. 32, we have
|Ê[1:i−1]V̂iÊ[i+1:n]V (s′)− E[1:i−1]V̂iÊ[i+1:n]V (s′)|
= ∣∣∣∣∣∣ ∑
s′[1:i−1]∈S[1:i−1]
( P̂[1:i−1] − P[1:i−1] ) (s′[1 : i− 1]|s, a)V̂iÊ[i+1:n]V (s′) ∣∣∣∣∣∣ ≤ ∣∣∣P̂[1:i−1](·|s, a)− P[1:i−1](·|s, a)∣∣∣ 1 · ∣∣∣V̂iÊi+1:nV (s′)∣∣∣ ∞
≤H2 i−1∑ j=1 ∣∣∣P̂j(·|s, a)− Pj(·|s, a)∣∣∣ 1 ≤H2 i−1∑ j=1 ( 2 √ |Sj |LP Nk−1((s, a)[ZPj ]) +
4|Sj |LP
3Nk−1((s, a)[ZPj ])
) (34)
The last inequality is due to Lemma D.1.
For equ. 33, given fixed s′[1 : i− 1], we have∣∣∣V̂iÊ[i+1:n]V (s′)− ViE[i+1:n]V (s′)∣∣∣ ≤ ∣∣∣∣Êi (Ê[i+1:n]V (s′))2 − Ei (E[i+1:n]V (s′))2∣∣∣∣ +
∣∣∣∣(E[i:n]V (s′))2 − (Ê[i:n]V (s′))2∣∣∣∣ ≤ ∣∣∣∣Êi (Ê[i+1:n]V (s′))2 − Ei (Ê[i+1:n]V (s′))2∣∣∣∣ +
∣∣∣∣Ei (Ê[i+1:n]V (s′))2 − Ei (E[i+1:n]V (s′))2∣∣∣∣ +
∣∣∣∣(E[i:n]V (s′))2 − (Ê[i:n]V (s′))2∣∣∣∣ ≤ ∣∣∣∣Êi (Ê[i+1:n]V (s′))2 − Ei (Ê[i+1:n]V (s′))2∣∣∣∣ (35) +
∣∣∣∣Ei (Ê[i+1:n]V (s′))2 − Ei (E[i+1:n]V (s′))2∣∣∣∣ (36) + 2H ∣∣∣E[i:n]V (s′)− Ê[i:n]V (s′)∣∣∣ (37)
The first inequality is due to the definition of variance. The last inequality is due to E[i:n]V (s′) + Ê[i:n]V (s′) ≤ 2H . All Equ. 35, 36 and 37 can be bounded with the same manner of Equ. 32. That is, we first bound each term with the L1-distance of transition probability multiplying the L∞-norm of the value function, then we upper bound the L1-distance by Lemma D.1. This leads to the following results:∣∣∣V̂iÊ[i+1:n]V (s′)− ViE[i+1:n]V (s′)∣∣∣ ≤4H2 n∑
j=i
( 2 √ |Sj |LP
Nk−1((s, a)[ZPj ]) +
4|Sj |LP
3Nk−1((s, a)[ZPj ]) ) This bound doesn’t depend on the given fixed s′[1 : i−1]. By taking expectation over s′[1 : i−1] ∼ P[1:i−1](·|s, a), we have
E[1:i−1] ∣∣∣V̂iÊ[i+1:n]V (s′)− ViE[i+1:n]V (s′)∣∣∣
≤ ∣∣∣∣Êi (Ê[i+1:n]V (s′))2 − Ei (E[i+1:n]V (s′))2∣∣∣∣ ≤ 4H2 n∑
j=i
( 2 √ |Sj |LP
Nk−1((s, a)[ZPj ]) +
4|Sj |LP
3Nk−1((s, a)[ZPj ]) ) Combining with Equ. 34, we have∣∣σ̂2P,k,i(V, s, a)− σ2P,i(V, s, a)∣∣ ≤ 4H2 n∑
j=1
( 2 √ |Sj |LP
Nk−1((s, a)[ZPj ]) +
4|Sj |LP
3Nk−1((s, a)[ZPj ])
)
Lemma F.7. Under event Λ1, Λ2 and Ω, we have
σ2P,i(V ∗ h+1, s, a)− 2σ̂2P,k,i(V k,h+1, s, a) ≤ uk,h,i(s, a) + 4H2 n∑ j=1
( 2 √ |Sj |LP
Nk−1((s, a)[ZPj ]) +
4|Sj |LP
3Nk−1((s, a)[ZPj ])
) ,
where uk,h,i(s, a) is defined in Section 4.3:
uk,h,i(s, a) = Es′ [1:i] ∼P̂k,[1:i](·|s,a)
[( Es′
[i+1:n] ∼P̂k,[i+1:n](·|s,a)
( V k,h+1 − V k,h+1 ) (s′) )2] .
Proof. We can decompose the difference in the following way:
σ2P,i(V ∗ h+1, s, a)− 2σ̂2P,k,i(V k,h+1, s, a)
≤σ̂2P,k,i(V ∗h+1, s, a)− 2σ̂2P,k,i(V k,h+1, s, a) + σ2P,i(V ∗h+1, s, a)− σ̂2P,k,i(V ∗h+1, s, a) By Lemma F.6, we know that∣∣σ̂2P,k,i(V ∗h+1, s, a)− σ2P,i(V ∗h+1, s, a)∣∣ ≤ 4H2 n∑
j=1
( 2 √ |Sj |LP
Nk−1((s, a)[ZPj ]) +
4|Sj |LP
3Nk−1((s, a)[ZPj ]) ) Now we only need to bound σ̂2P,k,i(V ∗ h+1, s, a)− 2σ̂2P,k,i(V k,h+1, s, a). By Lemma 2 of Azar et al. (2017), we know that for two random variables X ∈ R and Y ∈ R, we have V(X) ≤ 2[V(Y ) + V(X − Y )] (38)
That is,
σ̂2P,k,i(V ∗ h+1, s, a)− 2σ̂2P,k,i(V k,h+1, s, a)
=Ê[1:i−1]V̂iÊ[i+1:n]V ∗h+1(s′)− 2Ê[1:i−1]V̂iÊ[i+1:n]V k,h+1(s′) ≤2Ê[1:i−1]V̂i ( Ê[i+1:n]V ∗h+1(s′)− Ê[i+1:n]V k,h+1(s′) ) =2Ê[1:i−1]V̂iÊ[i+1:n] ( V ∗h+1(s ′)− V k,h+1(s′) )
≤2Ê[1:i] [( Ê[i+1:n] ( V ∗h+1(s ′)− V k,h+1(s′) ))2]
=uk,h,i(s, a)
The first inequality is due to Inq. 38, and the second inequality is due to VX ≤ EX2 for any random variable X ∈ R. To sum up, we have
σP,i(V ∗ h+1, s, a)− 2σ̂P,k,i(V k,h+1, s, a) ≤ uk,h,i(s, a) + 8H2 n∑ j=1
( 2 √ |Sj |LP
Nk−1((s, a)[ZPj ]) +
4|Sj |LP
3Nk−1((s, a)[ZPj ])
)
Lemma F.8. Under event Λ1, Λ2 and Ω, suppose R̃eg(K) = ∑K k=1 V k,1(s1)−V πk 1 (s1), we have:
K∑ k=1 H∑ h=1 ∑ (s,a)∈X wk,h(s, a) ( σ2P,i(V ∗ h+1, s, a)− σ2P,i(V πk h+1, s, a) ) ≤ 2H2R̃eg(K) K∑ k=1 H∑ h=1 ∑ (s,a)∈X wk,h(s, a) ( σ2P,i(V k,h+1, s, a)− σ2P,i(V πk h+1, s, a) ) ≤ 2H2R̃eg(K)
Proof. We only prove the first inequality in detail. By replacing V ∗h+1 with V k,h+1, we can prove the second inequality in the same manner. σ2P,i(V ∗ h+1, s, a)− σ2P,i(V πk h+1, s, a) = E[1:i] [ Vi ( E[i+1:n]V ∗h+1(s′) ) − Vi ( E[i+1:n]V πkh+1(s ′) )]
Given fixed s′[1 : i − 1], we bound the difference of the variances: Vi ( E[i+1:n]V ∗h+1(s′) ) −
Vi ( E[i+1:n]V πkh+1(s′) ) .
Vi ( E[i+1:n]V ∗h+1(s′) ) − Vi ( E[i+1:n]V πkh+1(s ′) )
=Ei [( E[i+1:n]V ∗h+1(s′) )2 − (E[i+1:n]V πkh+1(s′))2]− (E[i:n] [V ∗h+1(s′)])2 + (E[i:n] [V πkh+1(s′)])2 ≤Ei [( E[i+1:n]V ∗h+1(s′)
)2 − (E[i+1:n]V πkh+1(s′))2] ≤2HEi [ E[i+1:n]V ∗h+1(s′)− E[i+1:n]V πk h+1(s ′) ]
=2HE[i:n] [ V ∗h+1(s ′)− V πkh+1(s ′) ]
The first inequality is due to V ∗h+1(s ′) ≥ V πkh+1(s′), and the second inequality is due to E[i+1:n]V ∗h+1(s′) + E[i+1:n]V πk h+1(s ′) ≤ 2H .
We then take expectation over all s′[1 : i− 1]. that is σ2P,i(V ∗ h+1, s, a)− σ2P,i(V πk h+1, s, a) ≤ 2HE[1:n] [ V ∗h+1(s ′)− V πkh+1(s ′) ]
Plugging the inequality into the former equation, we have K∑ k=1 H∑ h=1 ∑ (s,a)∈X wk,h(s, a) ( σ2P,i(V ∗ h+1, s, a)− σ2P,i(V πk h+1, s, a) ) ≤
K∑ k=1 H∑ h=1 ∑ (s,a)∈X wk,h(s, a)2HEs′∼P(·|s,a) [ V ∗h+1(s ′)− V πkh+1(s ′) ]
= K∑ k=1 H∑ h=2 ∑ s∈S 2wk,h(s)H [V ∗ h (s)− V πk h (s)]
≤ K∑ k=1 2H2 [V ∗1 (s1)− V πk 1 (s1)]
≤ K∑ k=1 2H2 [ V k,1(s1)− V πk1 (s1) ] =2H2R̃eg(K)
For the second inequality, this is because that by lemma E.15 of Dann et al. (2017), we have∑ s wk,h(s) [V ∗ h (s)− V πk h (s)]
= H∑ h1=h ∑ s wk,h1(s) ( R̄(s, π∗(s))− R̄(s, πk(s)) + PV ∗h1+1(s, π ∗(s))− PV ∗h1+1(s, π k(s)) )
V ∗1 (s1)−V πk 1 (s1) = H∑ h1=1 ∑ s wk,h1(s) ( R̄(s, π∗(s))− R̄(s, πk(s)) + PV ∗h1+1(s, π ∗(s))− PV ∗h1+1(s, π k(s)) ) This means that ∑ s wk,h(s) [V ∗ h (s)− V πk h (s)] ≤ V ∗1 (s1)− V πk 1 (s1) for any k, h.

heading: F.5 OPTIMISM AND PESSIMISM
text: Lemma F.9. Suppose that Λ1, Λ2 and Ωk,h+1 happen, then we have the following inequalities hold for any a ∈ A and s ∈ S:
∣∣∣R̂(s, a)− R̄(s, a)∣∣∣ ≤ 1 m m∑ i=1 CBRi (s, a) (39)
∣∣∣P̂kV ∗h+1(s, a)− PV ∗h+1(s.a)∣∣∣ ≤ n∑ i=1 CBPi (s, a) (40)
Proof. The first inequality follows directly by Lemma F.1 and the definition of CBRi (s, a). For the second inequality, by Lemma F.1, we have∣∣∣(P̂k − P)V ∗h+1(s, a)∣∣∣
≤ n∑ i=1 √2σ2P,i(V ∗h+1, s, a)LP Nk−1((s, a)[ZPi ])) + 2HLP 3Nk−1((s, a)[ZPi ])  +
n∑ i=1 n∑ j 6=i,j=1 Hφk,i(s, a)φk,j(s, a),
where φk,i(s, a) = √
4|Si|LP Nk−1((s,a)[ZPi ]) + 4|Si|L P 3Nk−1((s,a)[ZPi ]) . The first inequality is due to V k,h(s) ≥
Qk,h(s, π ∗(s)).
By the definition of CBPi (s, a), we have∑ i CBPi (s, a)− ∣∣∣(P̂k − P)V ∗h+1(s, a)∣∣∣ (41) ≥ n∑ i=1 √4σ̂2P,k,i(V k,h+1, s, a)LP Nk−1((s, a∗)[ZPi ]) − √ 2σ2P,i(V ∗ h+1, s, a ∗)LP Nk−1((s, a)[ZPi ])
 (42) +
n∑ i=1
√ 2uk,h,i(s, a)LP
Nk−1((s, a)[ZPi ]) + n∑ i=1
√ 16H2LP
Nk−1((s, a)[ZPi ]) n∑ j=1 ( 4|Sj |LP Nk−1((s, a)[ZPj ]) ) 1 4 + √ 4|Sj |LP 3Nk−1(s, a)[ZPj ]  (43)
We mainly focus on the bound of Eqn 42.√ 4σ̂2P,k,i(V k,h+1, s, a)L P
Nk−1((s, a)[ZPi ]) −
√ 2σ2P,i(V ∗ h+1, s, a)L P
Nk−1((s, a)[ZPi ]) (44)
≥  − √ 2σ2P,i(V ∗ h+1,s,a)L P−4σ̂2P,k,i(V k,h+1,s,a)LP Nk−1((s,a)[ZPi ])) 2σ̂2P,k,i(V k,h+1, s, a) ≤ σ2P,i(V ∗h+1, s, a)
0 otherwise (45)
For those 2σ̂2P,k,i(V k,h+1, s, a) ≤ σ2P,i(V ∗h+1, s, a), by Lemma F.7, we have
σ2P,i(V ∗ h+1, s, a)− 2σ̂2P,k,i(V k,h+1, s, a)
≤uk,h,i(s, a) + 8H2 n∑ j=1
( 2 √ |Sj |LP
Nk−1((s, a)[ZPj ]) +
4|Si|LP
3Nk−1((s, a)[ZPj ])
)
That is,√ 4σ̂2P,k,i(V k,h+1, s, a)L P
Nk−1((s, a)[ZPi ]) −
√ 2σ2P,i(V ∗ h+1, s, a)L P
Nk−1((s, a∗)[ZPi ])
≥− √√√√2uk,h,i(s, a)LP + 16H2LP ∑nj=1 (2√ |Sj |LPNk−1((s,a)[ZPi ]) + 4|Si|LP3Nk−1((s,a∗)[ZPi ])) Nk−1((s, a∗)[ZPi ])
≥−
√ 2uk,h,i(s, a)LP
Nk−1((s, a)[ZPi ]) −
√ 16H2LP
Nk−1((s, a)[ZPi ]) n∑ j=1 ( 4|Sj |LP Nk−1((s, a)[ZPj ]) ) 1 4 + √ 4|Sj |LP 3Nk−1(s, a)[ZPj ]  Combining with Eq. 41, we prove that∣∣∣P̂kV ∗h+1(s, a)− PV ∗h+1(s.a)∣∣∣ ≤ n∑
i=1
CBPi (s, a)
The optimism is proved by induction.
Lemma F.10. (Optimism) Suppose that Λ1, Λ2 and Ωk,h+1 happen, then we have V k,h ≥ V ∗h .

heading: Proof.
text: V k,h(s)− V ∗h (s) =CBk(s, π ∗(s)) + P̂kV k,h+1(s, π∗(s))− PV ∗h+1(s, π∗(s)) + R̂k(s, π∗(s))− R̄k(s, π∗(s))
≥CBk(s, π∗(s)) + ( P̂k − P ) V ∗h+1(s, π ∗(s)) + R̂k(s, π ∗(s))− R̄k(s, π∗(s))
≥0
The first inequality is due to induction condition that Ωk,h+1 happens. The last inequality is due to Lemma F.9.
Lemma F.11. (Pessimism) Suppose that Λ1, Λ2 and Ωk,h+1 happen, then we have V k,h ≤ V ∗h .

heading: Proof.
text: V k,h(s)
=R̂k(s, πk,h(s))− CBk(s, πk,h(s)) + P̂kV k,h+1(s, πk,h(s))
≤R̂(s, πk,h(s))− CBk(s, πk,h(s)) + P̂kV ∗h+1(s, πk,h(s)) =R̄(s, πk,h(s)) + PV ∗h+1(s, πk,h(s))
+ ( R̂(s, πk,h(s))− R̄(s, πk,h(s))− 1
m m∑ i=1 CBRi (s, πk,h(s))
)
+ ( P̂kV ∗h+1(s, πk,h(s))− PV ∗h+1(s, πk,h(s))− n∑ i=1 CBPi (s, πk,h(s)) )
The inequality is due to V k,h+1(s ′) ≤ V ∗h+1(s′) since event Ωk,h+1 happens.
By lemma F.9, we have ∣∣∣R̂k(s, πk,h(s))− R̄(s, πk(s))∣∣∣ ≤ 1 m m∑ i=1 CBRi (s, πk,h(s))
∣∣∣P̂kV ∗h+1(s, πk,h(s))− PV ∗h+1(s.πk,h(s))∣∣∣ ≤ n∑ i=1 CBPi (s, πk,h(s))
Therefore, we have
V k,h(s, πk,h(s)) ≤R̄(s, πk,h(s)) + PV ∗h+1(s, πk,h(s)) ≤R̄(s, π∗h(s)) + PV ∗h+1(s, π∗h(s)) ≤V ∗h (s, a)
Lemma F.12. (Optimism and pessimism) Under event Λ1 and Λ2, we have Ωk,h holds for all k and h.
Proof. By Lemma F.10 and Lemma F.11, through induction over all possible k, h, we can prove the Lemma.

heading: F.6 PROOF OF THEOREM 2
text: Proof. We decompose R̃eg(K) = ∑K k=1 ( V k,1(sk,1, ak,1)− V πk1 (sk1 , ak,1) ) in the classical way (Azar et al., 2017; Zanette & Brunskill, 2019; Dann et al., 2019), that is
K∑ k=1 ( V k,1(s1)− V πk1 (s1) ) (46)
≤ ∑ k,h ∑ sh,ah wk,h(sh, ah)CBk(sh, ah) (47)
+ ∑ k,h ∑ sh,ah wk,h(sh, ah) ( P̂k − P ) V ∗h+1(sh, ah) (48)
+ ∑ k,h ∑ sh,ah wk,h(sh, ah) ( P̂k − P ) ( V k,h+1 − V ∗h+1 ) (sh, ah) (49)
+ ∑ k,h ∑ sh,ah wk,h(sh, ah) ( R̂k(sh, ah)− R̄(sh, ah) ) (50)
We bound Equ. 47, 48, 49 and 50 separately by Lemma F.13, Lemma F.14, Lemma F.15 and Lemma F.16. Combining the results of these Lemmas, we have
R̃eg(K) ≤ C1 1
m m∑ i=1 √ XRi TL R i log T + C2 √√√√ n∑ i=1 HTXPi L P log T + C3 √√√√nH2R̃eg(K) n∑ i=1 XPi L P log T
(51)
Here C1, C2, C3 denote some constants. Solving the R̃eg(K) in Inq 51, we can show that
R̃eg(K) ≤ O  1 m m∑ i=1 √ XRi TL R i log T + √√√√ n∑ i=1 HTXPi L P log T  , where O hides the lower order terms w.r.t T .
By the optimism principle (Lemma F.12), we have V ∗1 (sk,1, ak,1) ≤ V k,1(sk,1, ak,1). This leads to the final result: K∑ k=1 (V ∗1 (sk,1, ak,1)− V πk 1 (sk1 , ak,1)) ≤ O  1 m m∑ i=1 √ XRi TL R i log T + √√√√ n∑ i=1 HTXPi L P log T  .

heading: F.7 BOUNDING THE MAIN TERMS
text: Lemma F.13. Under event Λ1, Λ2 and Ωk,h, suppose R̃eg(K) = ∑K k=1 V k,1(s1) − V πk 1 (s1), we have K∑ k=1 H∑ h=1 ∑ s,a wk,h(s, a)CBk(s, a)
≤O  1 m m∑ i=1 √ TXRi L R i log T + √√√√HT n∑ i=1 XPi L P log T + √√√√H2nR̃eg(K) n∑ i=1 XPi L P log T  Proof. By the definition of CBk(s, a), we have∑ k,h,s,a wk,h(s, a)CBk(s, a) (52)
= ∑ k,h,s,a wk,h(s, a)
( 1
m m∑ i=1 CBRk,i(s, a) + n∑ i=1 CBPk,i(s, a)
) (53)
= ∑ k,h,s,a wk,h(s, a)  1 m m∑ i=1 √ 2σ̂2R,k,i(s, a)L R i Nk−1((s, a)[ZRi ]) + n∑ i=1 √ 4σ̂2P,k,i(V k,h+1, s, a)L P Nk−1((s, a)[ZPi ])  (54) + ∑ k,h,s,a wk,h(s, a) 1 m m∑ i=1 8LRi 3Nk−1((s, a)[ZRi ]) (55)
+ ∑ k,h,s,a wk,h(s, a) n∑ i=1 √ 16H2LP Nk−1((s, a)[ZPi ]) n∑ j=1 ( 4|Sj |LP Nk−1((s, a)[ZPj ]) ) 1 4 + √ 4|Sj |LP 3Nk−1(s, a)[ZPj ]  (56)
+ ∑ k,h,s,a wk,h(s, a) n∑ i=1 n∑ j 6=i,j=1 36H|Si||Sj |(LP )2√ Nk−1((s, a)[ZPi ])Nk−1((s, a)[Z P j ])
(57)
+ ∑ k,h,s,a wk,h(s, a) n∑ i=1
√ 2uk,h,i(s, a)LP
Nk−1((s, a)[ZPi ]) (58)
By Lemma F.5, the upper bound of Eqn. 55, 56 and 57 is O(T 1 4 ), which doesn’t contribute to the main factor in the regret. We prove the upper bound of Eqn. 54 and Eqn. 58 in detail.
By Lemma F.6, we have
∣∣σ̂2P,k,i(V k,h+1, s, a)− σ2P,i(V k,h+1, s, a)∣∣ ≤ 4H2 n∑ j=1
( 2 √ |Sj |LP
Nk−1((s, a)[ZPj ]) +
4|Sj |LP
3Nk−1((s, a)[ZPj ])
) ,
Then Eqn. 54 can be bounded as
1
m m∑ i=1
√ 2σ̂2R,k,i(s, a)L R i
Nk−1((s, a)[ZRi ]) + n∑ i=1
√ 4σ̂2P,k,i(V k,h+1, s, a)L P
Nk−1((s, a)[ZPi ])
≤ 1 m m∑ i=1
√ 2σ̂2R,k,i(s, a)L R i
Nk−1((s, a)[ZRi ]) + n∑ i=1
√ 4σ2P,i(V k,h+1, s, a)L P
Nk−1((s, a)[ZPi ])
+ n∑ i=1
√ 4|σ2P,i(V k,h+1, s, a)− σ̂2P,k,i(V k,h+1, s, a)|LP
Nk−1((s, a)[ZPi ])
≤ 1 m m∑ i=1
√ 2σ̂2R,k,i(s, a)L R i
Nk−1((s, a)[ZRi ]) (59)
+ n∑ i=1
√ 4σ2P,i(V k,h+1, s, a)L P
Nk−1((s, a)[ZPi ]) (60)
+ 8H n∑ i=1
√ LP
Nk−1((s, a)[ZPi ]) n∑ j=1 ( |Sj |LP Nk−1((s, a)[ZPj ]) ) 1 4 + √ 4|Sj |LP 3Nk−1((s, a)[ZPj ])  (61)
Similar with Eqn. 61, the summation of Eqn. 61 is upper bounded by O(T 1/4) by Lemma F.5. For Eqn. 59, we have
∑ k,h ∑ s,a wk,h(s, a) 1 m m∑ i=1
√ 2σ̂2R,k,i(s, a)L R i
Nk−1((s, a)[ZRi ])
≤ ∑ k,h ∑ s,a wk,h(s, a) 1 m m∑ i=1
√ 2LRi
Nk−1((s, a)[ZRi ])
≤ 1 m m∑ i=1 √∑ k,h ∑ s,a wk,h(s, a) √√√√∑ k,h ∑ s,a 2wk,h(s, a)LRi Nk−1((s, a)[ZRi ])
≤ 1 m m∑ i=1 √ T √√√√∑ k,h ∑ s,a 2wk,h(s, a)LRi Nk−1((s, a)[ZRi ])
The first inequality is due to σ̂2R,k,i(s, a) ≤ 1. The second inequality is due to Cauchy-Schwarz inequality. By Lemma F.5, the summation can be bounded by 1m ∑m i=1 √ XRi L R i T log T .
For Eqn. 60, we have
∑ k,h ∑ s,a wk,h(s, a) n∑ i=1
√ 4σ2P,i(V k,h+1, s, a)L P
Nk−1((s, a)[ZPi ])
≤ √√√√ ∑ k,h,s,a wk,h(s, a) n∑ i=1 σ2P,i(V k,h+1, s, a) · √√√√ ∑ k,h,s,a wk,h(s, a) n∑ i=1
4LP
Nk−1((s, a)[ZPi ])
≤ √√√√ ∑ k,h,s,a wk,h(s, a) n∑ i=1 σ2P,i(V k,h+1, s, a) √√√√ n∑ i=1 4XPi L P log T
= √√√√ ∑ k,h,s,a wk,h(s, a) n∑ i=1 σ2P,i(V πk h+1, s, a) √√√√ n∑ i=1 4XPi L P log T
+ √√√√ ∑ k,h,s,a wk,h(s, a) n∑ i=1 ( σ2P,i(V k,h+1, s, a)− σ2P,i(V πk h+1, s, a) )√√√√ n∑ i=1 4XPi L P log T
≤ √√√√ ∑ k,h,s,a wk,h(s, a) n∑ i=1 σ2P,i(V πk h+1, s, a) √√√√ n∑ i=1 4XPi L P + √√√√2H2nR̃eg(K) n∑ i=1 XPi L P log T
≤ √√√√ ∑ k,h,s,a wk,h(s, a) ( 1 m2 m∑ i=1 σ2R,i(s, a) + n∑ i=1 σ2P,i(V πk h+1, s, a) )√√√√ n∑ i=1 4XPi L P log T + √√√√2H2nR̃eg(K) n∑ i=1 XPi L P log T
≤ √ HT · √√√√ n∑ i=1 4XPi L P log T + √√√√2H2nR̃eg(K) n∑ i=1 XPi L P log T
The first inequality is due to Cauchy-Schwarz inequality. The second inequality is due to Lemma F.5. The third inequality is due to Lemma F.8. The forth inequality is due to σ2R,k,i(s, a) ≥ 0, and the last inequality is because of Corollary 1.1.
For Eqn. 58, we have
∑ k,h,s,a wk,h(s, a) n∑ i=1
√ 2uk,h,i(s, a)LP
Nk−1((s, a)[ZPi ])
≤ n∑ i=1 √√√√√2LP  ∑ k,h,s,a
4wk,h(s, a)
Nk−1((s, a)[ZPi ])  ∑ k,h,s,a wk,h(s, a)uk,h,i(s, a) 
≤ n∑ i=1 √√√√√64XPi LP log T  ∑ k,h,s,a wk,h(s, a)uk,h,i(s, a)  (62) By Lemma F.20, we know that the summation ∑ k,h,s,a wk,h(s, a)uk,h,i(s, a) is of order O(T 1 2 ). This means that Equ. 62 is of order O(T 1 4 ), which doesn’t contribute to the main term (O( √ T )).
Lemma F.14. Under event Λ1, Λ2 and Ω, suppose R̃eg(K) = ∑K k=1 V k,1(s1)−V πk 1 (s1), we have
K∑ k=1 H∑ h=1 ∑ (s,a)∈X wk,h(s, a) ( P̂k − P ) V ∗(s, a)
≤O √√√√(HT + nH2R̃eg(K)) n∑ i=1 XPi L P 
Proof. By Lemma F.1, we have
k1∑ k=1 H∑ h=1 ∑ (s,a)∈X wk,h(s, a) ( P̂k − P ) V ∗(s, a)
≤ ∑ k ∑ h n∑ i=1 ∑ (s,a)∈X wk,h(s, a)
√ 2σ2P,i(V ∗ h+1, s, a)L P
Nk−1((s, a)[ZPi ])
+ ∑ k ∑ h n∑ i=1 ∑ (s,a)∈X wk,h(s, a) n∑ j 6=i,j=1 36H|Si||Sj |(LP )2√ Nk−1((s, a)[ZPi ])Nk−1((s, a)[Z P j ])
By Lemma F.5, the second term has only logarithmic dependence on T , which is negligible compared with the main factor. We mainly focus on the first term.
∑ k ∑ h n∑ i=1 ∑ (s,a)∈X wk,h(s, a)
√ 2σ2P,i(V ∗ h+1, s, a)L P
Nk−1((s, a)[ZPi ])
≤ √√√√∑ k,h ∑ (s,a)∈X 2wk,h(s, a) n∑ i=1 σ2P,i(V ∗ h+1, s, a) · √√√√∑ k,h ∑ (s,a)∈X n∑ i=1
wk,h(s, a)LP
Nk−1((s, π(s))[ZPi ])
≤ √√√√∑ k,h ∑ (s,a)∈X 2wk,h(s, a) ( 1 m m∑ i=1 σ2R,i(s, a) + n∑ i=1 σ2P,i(V ∗ h+1, s, a) ) · √√√√∑ k,h ∑ (s,a)∈X n∑ i=1
wk,h(s, a)LP
Nk−1((s, π(s))[ZPi ])
≤ √( HT + nH2R̃eg(K) )√√√√8 n∑
i=1
XPi L P log T
The first inequality is due to Cauchy-Schwarz inequality. The second inequality is due to σ2R,k,i(s, a) ≥ 0. For the last inequality, the first part is the summation of the variance, which can be bounded by Lemma 1.1 and Lemma F.8, while the second part can be bounded as ∑ iX P i L
P log T by Lemma F.5.
Lemma F.15. Under event Λ1, Λ2 and Ω, suppose R̃eg(K) = ∑K k=1 V k,1(s1)−V πk 1 (s1), we have
K∑ k=1 H∑ h=1 ∑ (s,a)∈X wk,h(s, a) ( P̂k − P ) ( V k,h+1 − V ∗h+1 ) (s, a) ≤ O
H √√√√ n∑
i=1
√ TXPj |Sj |LP n∑ i=1 2 √ 8XPi L P log T

Proof. By Lemma E.1, we can prove that( P̂k − P ) ( V k,h+1 − V ∗h+1 ) (s, a)
≤ n∑ i=1 (P̂k,i − Pi)P[1:i−1]P[i+1:n] ( V k,h(sk,h, ak,h)− V ∗h (sk,h, ak,h) ) +
n∑ i=1 n∑ j=1 H ∣∣∣(P̂k,i − Pi) (·|(s, a)[ZPi ])∣∣∣ 1 ∣∣∣(P̂k,j − Pj) (·|(s, a)[ZPj ])∣∣∣ 1
≤ n∑ i=1 2 ∑ s′[i]∈Si √ Pi(s′[i]|X [ZPi ])LP Nk−1((s, a)[ZPi ]) P[1:i−1]P[i+1:n] (V k,h(sk,h, ak,h)− V ∗h (sk,h, ak,h)) +
n∑ i=1 n∑ j 6=i,j=1 36H |Si||Sj |(LP )2√ Nk−1((s, a)[ZPi ])Nk−1((s, a)[Z P j ]) + n∑ i=1
|Si|LP
3Nk−1((s, a)[ZPi ])
The second inequality is due to Lemma D.1.
We only focus on the summation of the first term, since the summation of other terms has only logarithmic dependence on T by Lemma F.5.
∑ k,h ∑ s,a wk,h(s, a) n∑ i=1 2 ∑ s′[i]∈Si √ Pi(s′[i]|(s, a)[ZPi ])LP Nk−1((s, a)[ZPi ]) P[1:i−1]Pi+1:n (V k,h(sk,h, ak,h)− V ∗h (sk,h, ak,h))
= n∑ i=1 ∑ k,h ∑ s,a wk,h(s, a)P1:i−1 2 ∑ s′[i]∈Si √√√√Pi(s′[i]|X [ZPi ])LP (P[i+1:n] (V k,h(sk,h, ak,h)− V ∗h (sk,h, ak,h)))2 Nk−1((s, a)[ZPi ])  ≤
n∑ i=1 ∑ k,h P1:i−1 ∑ s,a wk,h(s, a) 2 ∑ s′[i]∈Si √√√√Pi(s′[i]|(s, a)[ZPi ])LP (P[i+1:n] (V k,h(sk,h, ak,h)− V k,h(sk,h, ak,h)))2 Nk−1((s, a)[ZPi ])  ≤
n∑ i=1 ∑ k,h ∑ s,a wk,h(s, a)
2 √√√√ |Si|LPE[1:i] (E[i+1:n] (V k,h(s′)− V k,h(s′)))2
Nk−1((s, a)[ZPi ])  ≤
n∑ i=1 2 √√√√√  ∑ k,h,s,a
wk,h(s, a)
Nk−1((s, a)[ZPi ])  ∑ k,h,s,a wk,h(s, a)E[1:i] ( E[i+1:n] ( V k,h+1(s′)− V k,h+1(s′) ))2 ≤
n∑ i=1 2 √ 8XPi L P log T √√√√H2 n∑ i=1 √ TXPj |Sj |LP
The first inequality is due to the fact that V k,h ≥ V ∗h ≥ V k,h. The second and the third inequality is due to Cauchy-Schwarz inequality. The last inequality is because of Lemma F.5 and Lemma F.20.
Lemma F.16. Under event Λ1, Λ2 and Ω, we have
∑ k,h ∑ sh,ah wk,h(sh, ah) ( R̂k(sh, ah)− R̄(sh, ah) ) ≤ O
( 1
m m∑ i=1 √ TXRi L R i log T
)
Proof. By Lemma F.1, we have∑ k,h ∑ sh,ah wk,h(sh, ah) ( R̂k(sh, ah)− R̄(sh, ah) )
≤ 1 m n∑ i=1 ∑ k,h ∑ sh,ah wk,h(sh, ah) (√ 2σ̂R,k,i(sh, ah)LRi Nk−1((sh, ah)[ZRi ]) + 8LRi 3Nk−1((sh, ah)[ZRi ]) )
≤ 1 m m∑ i=1 ∑ k,h ∑ sh,ah wk,h(sh, ah)
(√ 2LRi
Nk−1((sh, ah)[ZRi ]) + 8LRi 3Nk−1((sh, ah)[ZRi ])
)
≤ 1 m m∑ i=1
√∑ k,h ∑ sh,ah 2wk,h(sh, ah)LRi
Nk−1((sh, ah)[ZRi ]) +
1
m m∑ i=1 ∑ k,h ∑ sh,ah wk,h(sh, ah) 8LRi 3Nk−1((sh, ah)[ZRi ])
The second inequality is due to σ̂R,k,i(s, a) ≤ 1. The last inequality is due to Cauchy-Schwarz inequality. By Lemma F.5, we know that the summation is of orderO ( 1 m ∑m i=1 √ TXRi L R i log T ) .
Lemma F.17. Under event Λ1 and Λ2, we have ( V k,h − V k,h ) (s) ≤ Etrajk  H∑ i=h 2CBk(s, πk,i(s)) + n∑ j=1 √ 2H2 log(18nT |X [ZPj ]|/δ) Nk−1((s, πk,j(s))[ZPj ])  | sh = s, πk 
The expectation is over all possible trajectories in episode k given sh = s following policy πk.
Proof.( V k,h − V k,h ) (s)
=2CBk(s, πk,h(s)) + P̂k(V k,h+1(s)− V k,h+1(s))
=2CBk(s, πk,h(s)) + (P̂k − P)(V k,h+1 − V k,h+1)(s, πk,h(s)) + P(V k,h+1 − V k,h+1)(s, πk,h(s)) · · ·
=Etrajk [ H∑ i=h ( 2CBk(s, πk,i(si)) + (P̂k − P)(V k,i+1 − V k,i+1)(si, πk,i(si)) ) | sh = s, πk ] The second term can be bounded as:
(P̂k − P)(V k,i+1 − V k,i+1)(si, πk,i(si))
≤|P̂k − P|1|V k,i+1 − V k,i+1|∞(si, πk,i(s))
≤H n∑ i=1 |P̂k,i − Pi|1(·|si, πk,i(si))
≤ n∑ j=1
√ 2H2LP
Nk−1((s, πk,j(s))[ZPj ])
Lemma F.18. Under event Λ1 and Λ2, we have K∑ k=1 H∑ h=1 ∑ (s,a)∈X wk,h(s, a)CB 2 k(s, a)
≤ m∑ i=1 2(m+ 2)H2LRi X R i log T m2 + n∑ i=1 128n(m+ n)H2XPi L P n∑ j=1 |Sj |LP log T,
Which has only logarithmic dependence on T .
Note that this bound is loose w.r.t parameters such asH , |Sj |,XPi andXRi . However, it is acceptable since we regard T as the dominant parameter. This bound doesn’t influence the dominant factor in the final regret.
Proof. By the definition of CBk(s, a), CBRk,i(s, a) and CB P k,i(s, a), we have
CB2k(s, a) ≤(m+ n) ( m∑ i=1 1 m2 ( CBRk,i(s, a) )2 + n∑ i=1 ( CBPk,i(s, a) )2)
≤2(m+ n) m∑ i=1 1 m2 ( 2H2LRi Nk−1((s, a)[ZRi ]) +
64(LRi ) 2
9(Nk−1((s, a)[ZRi ])) 2
)
+ 4n(m+ n) n∑ i=1 ( 4H2LP Nk−1((s, a)[ZPi ]) +
2HLP
Nk−1((s, a)[ZPi ]) )
)
+ 4n(m+ n) n∑ i=1  32H2LP Nk−1((s, a)[ZPi ]) n∑ j=1 (√ 4|Sj |LP Nk−1((s, a)[ZPj ]) +
4|Sj |LP
3Nk−1((s, a)[ZPj ]) ) The second inequality is due to σ̂2R,i(s, a) ≤ 1, σ̂2P,i(V k,h+1, s, a) ≤ H2 and uk,h,i(s, a) ≤ H .
Now we are ready to bound ∑K k=1 ∑H h=1 ∑ (s,a)∈X wk,h(s, a)CB 2 k(s, a):
K∑ k=1 H∑ h=1 ∑ (s,a)∈X wk,h(s, a)CB 2 k(s, a)
≤ K∑ k=1 H∑ h=1 ∑ (s,a)∈X wk,h(s, a) ( m∑ i=1 2(m+ 2)H2LRi m2Nk−1((s, a)[ZRi ]) + n∑ i=1 128n(m+ n)H2LP ∑n j=1 |Sj |LP Nk−1((s, a)[ZPi ]) )
≤ m∑ i=1 2(m+ 2)H2LRi X R i log T m2 + n∑ i=1 128n(m+ n)H2XPi L P n∑ j=1 |Sj |LP log T
The last inequality is due to Lemma F.5.
Lemma F.19. Under event Λ1 and Λ2, we have K∑ k=1 H∑ h=1 ∑ (s,a)∈X wk,h(s, a)Es′[1:i]∼P[1:i](·|s,a) ( Es′[i+1:n]∼P[i+1:n](·|s,a) ( V k,h+1 − V k,h+1 ) (s′) )2 ≤ O(log T ),
Here O hides the dependence on other parameters such as H,XPi , X R i except T .
Proof. For notation simplicity, we use Ei and E[i:j] as a shorthand of Es′[i]∼Pi(·|(s,a)[ZPi ]) and Es′[i:j]∼P[i:j](·|s,a). ∑
k,h,s,a
wk,h(s, a)E[1:i] [( E[i+1:n] ( V k,h+1 − V k,h+1 ) (s′) )2]
≤ ∑ k,h,s,a wk,h(s, a)E[1:i]E[i+1:n] ( V k,h+1 − V k,h+1 )2 (s, a)
= ∑ k,h,s,a wk,h(s, a)E[1:n] ( V k,h+1 − V k,h+1 )2 (s, a)
= K∑ k=1 H∑ h=1 ∑ s,a wk,h+1(s, a) ( V k,h+1 − V k,h+1 )2 (s, a)
Define Uk(s, a) = 2CBk(s, a) + ∑n j=1 √ 2H2LP
Nk−1((s,a)[ZPj ]) . By Lemma F.17, we have
K∑ k=1 H∑ h=1 ∑ s,a wk,h+1(s, a) ( V k,h+1 − V k,h+1 )2 (s, a)
≤ ∑ k,h,s,a wk,h+1(s, a)  H∑ h1=h+1 ∑ sh1 ,ah1 Pr(sh1 , ah1 |sh+1 = s, ah+1 = a)Uk(sh1 , ah1) 2 ≤ ∑ k,h,s,a wk,h+1(s, a)H H∑ h1=h+1  ∑ sh1 ,ah1 Pr(sh1 , ah1 |sh+1 = s, ah+1 = a)Uk(sh1 , ah1) 2
≤ ∑ k,h,s,a wk,h+1(s, a)H H∑ h1=h+1 ∑ sh1 ,ah1 Pr(sh1 , ah1 |sh+1 = s, ah+1 = a) (Uk(sh1 , ah1)) 2
= ∑ k,h H H∑
h1=h+1 ∑ sh1 ,ah1 wk,h1(sh1 , ah1) (Uk(sh1 , ah1)) 2
≤ ∑ k,h H2 ∑ sh,ah wk,h(sh, ah) (Uk(sh, ah)) 2 (63)
Plugging the definition of Uk(s, a) into Equ. 63, we have:
K∑ k=1 H∑ h=1 ∑ s,a wk,h+1(s, a) ( V k,h+1 − V k,h+1 )2 (s, a) (64)
≤ ∑ k,h H2 ∑ sh,ah wk,h(sh, ah) 2CBk(s, a) + n∑ j=1 √ 2H2LP Nk−1((s, a)[ZPj ]) 2 (65) ≤ ∑ k,h 2nH2 ∑ sh,ah wk,h(sh, ah) CB2k(s, a) + n∑ j=1 2H2LP Nk−1((s, a)[ZPj ])
 (66) ≤ ∑ k,h 2nH2 ∑ sh,ah wk,h(sh, ah)CB 2 k(s, a) + 16nH 4XPi L P log T (67)
The last inequality is due to Lemma F.5. We can bound ∑ k,h 2nH 2 ∑ sh,ah wk,h(sh, ah)CB 2 k(s, a) by Lemma F.18. Summing up over all terms, we can show that∑K k=1 ∑H h=1 ∑ s,a wk,h+1(s, a) ( V k,h+1 − V k,h+1 )2 (s, a) is of order O(1).
Lemma F.20. Under event Λ1 and Λ2, for any i ∈ [n],we have
K∑ k=1 H∑ h=1 ∑ (s,a)∈X wk,h(s, a)uk,h,i(s, a) ≤ O(H2 n∑ j=1 √ TXPj |Sj |LP ),
Here O hides the lower order terms w.r.t. T .
Proof. For notation simplicity, we use Ei and E[i:j] as a shorthand of Es′[i]∼Pi(·|(s,a)[ZPi ]) and Es′[i:j]∼P[i:j](·|(s,a)[ZPi ]). For those expectation w.r.t the empirical transition P̂k, we use Êk to denote the corresponding expectation.
uk,h,i(s, a) is defined as: uk,h,i(s, a) = Ê[1:i] [( Ê[i+1:n] ( V k,h+1 − V k,h+1 ) (s′) )2] .
∑ k,h,s,a wk,h(s, a)Ê[1:i] [( Ê[i+1:n] ( V k,h+1 − V k,h+1 ) (s′) )2]
(68)
= ∑ k,h,s,a wk,h(s, a)E[1:i] [( E[i+1:n] ( V k,h+1 − V k,h+1 ) (s′) )2]
(69)
+ ∑ k,h,s,a wk,h(s, a)Ê[1:i] [( Ê[i+1:n] ( V k,h+1 − V k,h+1 ) (s′) )2]
− ∑ k,h,s,a wk,h(s, a)E[1:i] [( Ê[i+1:n] ( V k,h+1 − V k,h+1 ) (s′) )2]
(70)
+ ∑ k,h,s,a wk,h(s, a)E[1:i] [( Ê[i+1:n] ( V k,h+1 − V k,h+1 ) (s′) )2]
− ∑ k,h,s,a wk,h(s, a)E[1:i] [( E[i+1:n] ( V k,h+1 − V k,h+1 ) (s′) )2]
(71)
That is
We can bound Eqn. 70 and Eqn. 71 by Lemma D.1. For Eqn. 70, we have
∑ k,h,s,a wk,h(s, a)Ê[1:i] [( Ê[i+1:n] ( V k,h+1 − V k,h+1 ) (s′) )2]
− ∑ k,h,s,a wk,h(s, a)E[1:i] [( Ê[i+1:n] ( V k,h+1 − V k,h+1 ) (s′) )2]
≤ ∑ k,h,s,a wk,h(s, a) ∣∣∣P̂[1:i](·|s, a)− P[1:i](·|s, a)∣∣∣ 1 H2 ≤ ∑ k,h,s,a wk,h(s, a) i∑ j=1 √ |Sj |LP Nk−1((s, a)[ZPj ]) H2 ≤8H2 i∑
j=1
√ TXPj |Sj |LP log T
The first inequality is due to ( Ê[i+1:n] ( V k,h+1 − V k,h+1 ) (s′) )2 ≤ H2 for any given s′[1 : i]. The
second inequality is due to Lemma D.1. The third inequality is due to Lemma F.5.
For Eqn. 71, similarly we have∑ k,h,s,a wk,h(s, a)E[1:i] [( Ê[i+1:n] ( V k,h+1 − V k,h+1 ) (s′) )2]
− ∑ k,h,s,a wk,h(s, a)E[1:i] [( E[i+1:n] ( V k,h+1 − V k,h+1 ) (s′) )2]
≤2H ∑ k,h,s,a wk,h(s, a)E[1:i] [( Ê[i+1:n] ( V k,h+1 − V k,h+1 ) (s′) ) − ( E[i+1:n] ( V k,h+1 − V k,h+1 ) (s′) )]
≤2H ∑ k,h,s,a wk,h(s, a)E[1:i] [ H ∣∣∣P̂[i+1:n](·|s, a)− P[i+1:n](·|s, a)∣∣∣ 1 ] ≤2H2 ∑ k,h,s,a wk,h(s, a)E[1:i]  n∑ j=i+1 √ |Sj |LP Nk−1((s, a)[ZPj ])
 =2H2
∑ k,h,s,a wk,h(s, a) n∑ j=i+1
√ |Sj |LP
Nk−1((s, a)[ZPj ])
≤16H2 n∑
j=i+1
√ TXPj |Sj |LP log T
Eqn. 69 can be bounded by Lemma F.19, which has only logarithmic dependence on T .

heading: G PROOF OF THEOREM 3
text: Proof. We consider the following two hard instances.
The first instance is an extension of the hard instance in Jaksch et al. (2010). They proposed a hard instance for non-factored weakly-communicating MDP, which indicates that the lower bound in that setting is Ω( √ DSAT ). When transformed to the hard instance for non-factored episodic MDP, it shows a lower bound of order Ω( √ HSAT ) in episodic setting Azar et al. (2017); Jin et al. (2018). Consider a factored MDP instance with d = m = n and X [ZRi ] = X [ZPi ] = Xi = Si ×Ai, i = 1, ..., n. This factored MDP can be decomposed into n independent non-factored MDPs. By simply setting these n non-factored MDPs to be the construction used in Jaksch et al. (2010), the regret for each MDP is Ω( √ H|X [ZPi ]|T ). The total regret is Ω( ∑n i=1 √ H|X [ZPi ]|T ). Note that in
our setting, the reward R = 1m ∑m i=1Ri is [0, 1]-bounded. Therefore, we need to normalize the reward function in the hard instance by a factor of 1m . This leads to a final lower bound of order Ω( 1m ∑n i=1 √ H|X [ZPi ]|T ) = Ω( 1n ∑n i=1 √ H|X [ZPi ]|T ). Similar construction has been used to prove the lower bound for factored weakly-communicating MDP (Xu & Tewari, 2020).
The second hard instance is an extension of the hard instance for stochastic multi-armed bandits. The lower bound of stochastic multi-armed bandits shows that the regret of a MAB problem with k0 arms in T0 steps is lower bounded by Ω( √ k0T0). Consider a factored MDP instance with d = m = n and X [ZRi ] = X [ZPi ] = Xi = Si × Ai, i = 1, ..., n. There are m independent reward functions, each associated with an independent deterministic transition. For reward function i, There are log2(|Si|) levels of states, which form a binary tree of depth log2(|Si|). There are 2h−1 states in level h, and thus |Si| − 1 states in total. Only those states in level log2(|Si|) have non-zero rewards, the number of which is |Si|2 . After taking actions at state s
′ in level log2(|Si|), the agent will transits back to state s′ in level log2(|Si|). That is to say, the agent can enter ”reward states” at least H − log2(|Si|) ≥ H2 times in one episodes. For each reward function i, the instance can be regarded as an MAB problem |SiAi|2 arms running for KH 2 steps 1, thus the regret for reward i is
1The instance is not exactly an MAB with |SiAi| 2 arms running for KH 2
steps, since in each episode the agent will choose a state s′, and then stay in s′ and choose different actions for H
2 steps. However, this is a
mild difference and we can still follow the same proof idea of the lower bound for MAB (See e.g. Theorem 14.1 in Lattimore & Szepesvári (2020))
Ω( √ |SiAi|
2 KH 2 ) = Ω( √ |X [ZRi ]|T ). In this construction, the total reward function can be regarded
as the average ofm independent reward functions ofm stochastic MDP. This indicates that the lower bound is Ω (
1 m ∑m i=1 √∣∣X [ZRi ]∣∣T) ≥ Ω( 1m∑mi=1√∣∣X [ZRi ]∣∣T). To sum up, the regret is lower bounded by
Ω max  1m m∑ i=1 √ |X [ZRi ]|T , 1 n n∑ j=1 √ H|X [ZPj ]|T   ,
which is of the same order as
Ω  1 m n∑ i=1 √ |X [ZRi ]|T + 1 n n∑ j=1 √ H|X [ZPj ]|T  .

heading: H OMITTED DETAILS IN SECTION 5

heading: H.1 SPECIFIC INSTANCES
text: We further explain the difference with two specific examples in Fig. H.1. No matter which setting the previous work considers, the main idea of the algorithms in Efroni et al. (2020); Brantley et al. (2020) is to explore the MDP environment, and then find a near-optimal policy satisfying that the expected cumulative cost less than a constant vector B0, i.e. E[ ∑ h∈[H] ch] ≤ B0. However, in our setting, the agent has to terminate the interaction once the total costs in this episode exceed budget B. Because of this difference, their algorithm will converge to an sub-optimal policy with unbounded regret in our setting. In the first MDP instance (Fig. H.1), the agent starts from state s0. After taking action a1, it will transit to s1 with a deterministic cost c1 = 0.5. After taking action a2, it will transit to s2. The cost of taking a2 is 0 with prob. 0.5, and 1 with prob 0.5. There are no rewards in state s0. In state s1 and s2, the agent will not suffer any costs. The deterministic rewards are 0.5 and 0.8 respectively. s3 and s4 are termination states. The budget B0 is 0.5. For this MDP instance, the optimal policy is to take action a1 in s0, since the agent can receive total rewards 0.5 by taking a1. If taking action a2, the agent will terminate at state s2 with no rewards with prob. 0.5, which leads to an expected total rewards of 0.4. However, if we run the algorithm in Efroni et al. (2020); Brantley et al. (2020), the algorithm will converge to the policy that always selects action a2 in s0, since the expected cumulative cost of taking a2 is 0.5 ≤ B0. We further show that the policies defined in the previous literature are not expressive enough in our setting. In the second instance, the agent starts in state s0 with one action a0. By taking a0, the agent transits to s1 with no rewards. The cost of taking a0 is 0 with prob. 0.5, and 1 with prob 0.5. In s1, the agent needs to decide to take a1 or a2, with deterministic costs of 0 and 0.5 respectively. After taking a1, the agent will transits to s2, in which it can obtain a reward r3 = 0.5. While by taking a2, the agent can transits to s3, and obtain a reward r4 = 1. The budget B = 0.5. In this instance, the action taken in s1 depends on the remaining budget of the agent. That is to say, the policy is not expressive enough if it is defined as a mapping from state to action. Instead, we need to define it as a mapping from both state and remaining budget to action. However, previous literature only considers policies on the state space, which cannot deal with this problem.

heading: H.2 ALGORITHM AND REGRET
text: We denote V πh (s, b) as the value function in state s at horizon h following policy π, and the agent’s remaining budget is b. For notation simplicity, we define PSPCV (s, a) =∑ s′ ∑ c0 P(s′|s, a)P(C(s, a) = c0|s, a)V (s′, b − c0). We use PC,i(c0|s, a) to denote the ”transition probability” of budget i, i.e. P(Ci(s, a) = c0|s, a). The Bellman Equation of our setting is written as:
V πh (s, b) = { R̄(s, πh(s, b)) + PSPCV πh+1(s, πh(s, b), b) b > 0 0 b ≤ 0 (72)
Suppose Nk(s, a) denotes the number of times (s, a) has been encountered in the first k episodes. We estimate the mean value of r(s, a), the transition matrix PS and PC in the following way:
R̂k(s, a) =
∑ k,h 1[sk,h = s, ak,h = a] · rk,h
Nk−1(s, a)
P̂S,k(s′|s, a) = Nk−1(s, a, s
′)
Nk−1(s, a) P̂C,k,i (Ci(s, a) = c0|s, a) = ∑ k,h 1[ck,h,i = c0, sk,h = s, ak,h = a]
Nk−1(s, a)
Following the definition in the factored MDP setting, we define the confidence bonus for rewards and transition respectively (for 0 ≤ i ≤ d):
CBRk (s, a) =
√ 2σ̂2R(s, a) log(2SAT )
Nk−1(s, a) +
8 log(2SAT ) 3Nk−1(s, a) (73)
CBPk,i(s, a, b) =
√ 4σ̂2P,i(V k,h+1, s, a, b)L
Nk−1(s, a) +
√ 2uk,h,i(s, a, b)L
Nk−1(s, a) (74)
+
√ 32H2L
Nk−1(s, a) n∑ j=1
(( 4nL
Nk−1(s, a)
) 1 4
+
√ 4nL
3Nk−1(s, a)
) (75)
+ n∑ j=1 H (√ 4|Si|LP Nk−1(s, a) + 4|Si|L 3Nk−1(s, a) )(√ 4|Sj |LP Nk−1(s, a) + 4|Sj |L 3Nk−1(s, a) ) ,
(76)
where L = log(2dSAT ) + d log(mB) is the logarithmic factors because of union bounds. The additional d log(mB) is because that we need to take union bounds over all possible budget b. This difference compared with factored MDP is mainly due to the noised offset model.
CBRk (s, a) is the confidence bonus for rewards, and σ̂R(s, a) denotes the empirical variance of reward R(s, a), which is defined as:
σ̂R(s, a) = 1
Nk−1(s, a) k−1∑ k=1 H∑ h=1 1 [(s, a)k,h = (s, a)] · (rk,h(sk,h, ak,h))2 − ( R̂k(s, a) )2 CBPk,0(s, a) is the confidence bonus for state transition estimation P̂S , and {CBPk,i(s, a)}i=1,...,d is the confidence bonus for budget transition estimation {P̂C,i}i=1,...,d. σ̂2P,i(V k,h+1, s, a) is the empirical variance of corresponding transition:
σ̂20(V k,h+1, s, a, b) = Vars′∼P̂S,k(·|(s,a)[ZPi ]) ( Ec∼P̂C,k(·|s,a)V k,h+1(s ′, b− c) )
σ̂2P,i(V k,h+1, s, a, b) =Es′∼P̂S,k(·|s,a)Ec[1:i−1]∼P̂C,k,[1:i−1](·|s,a) [ Varci∼P̂C,k,i(·|s,a) ( Ec[i+1:n]∼P̂C,k,[i+1:d](·|s,a)V k,h+1(s ′, b− c) )] ,
where P̂C,k,[d1:d2] = ∏d2 i=d1
P̂C,k,i.√ 2uk,h,i(s,a,b) Nk−1(s,a)
is added to compensate the error due to the difference between V ∗h+1 and V k,h+1, where uk,h,i(s, a) is defined as:
uk,h,0(s, a, b) = Es′∼P̂S,k(·|s,a) [( Ec∼P̂C,k(·|s,a) ( V k,h+1 − V k,h+1 ) (s′, b− c) )2] uk,h,i(s, a, b) = Es′∼P̂S,k(·|s,a)Ec[1:i]∼P̂C,k,[1:i](·|s,a) [( Ec[i+1:n]∼P̂C,k,[i+1:d](·|s,a) ( V k,h+1 − V k,h+1 ) (s′, b− c) )2] .
We calculate the optimistic value function and find the optimal policy π via the following value iteration in our algorithm:
V h(s, b) =
{ maxa {[ R̂(s, a) + CB(s, a) + P̂sP̂cV h+1(s, a, b) ]} b > 0
0 b ≤ 0 (77)
Algorithm 4 FMDP-BF for RLwK Input: δ Initialize N(s, a) = 0 for any (s, a) ∈ X for episode k = 1, 2, · · · do
Set V k,H+1(s, b) = V k,H+1(s, b) = 0 for all s, a, b. 5: Let K = {(s, a) ∈ S ×A : Nk(s, a) > 0}
for horizon h = H,H − 1, ..., 1 do for s ∈ S and all possible budget b from 0 to B do
for a ∈ A do if (s, a) ∈ K then
10: Qk,h(s, a, b) = min{H, R̂k(s, a) +CBk(s, a) + P̂S,kP̂C,kV k,h+1(s, a, b)} else
Qk,h(s, a, b) = H end if
end for 15: πk,h(s, b) = arg maxaQk,h(s, a, b)
V k,h(s, b) = maxa∈AQk,h(s, a, b) V k,h(s, b) = max { 0, R̂k(s, πk,h)− CBk(s, πk,h, , b) + P̂kV k,h+1(s, πk,h, b) }
end for end for
20: for step h = 1, · · · , H do Take action ak,h = arg maxa Q̂k,h(sk,h, a)
end for Update history trajectory L = L ⋃ {si, ai, ri, si+1}i=1,2,...,tk
end for
Proof. (Theorem 4) The proof follows almost the same proof framework of Thm. 2. The term log(SAT ) + d log(Bm) is due to a union bound over all possible (T, s, a) and budget b. This difference is because of the additional union bounds over all budget b.

heading: H.3 DISCUSSIONS ABOUT ASSUMPTION 1 AND ASSUMPTION 2
text: Assumptions 1 and 2 limit our Algorithm 4 to problems with discrete costs. One may wonder whether it is possible to construct -net for budget B and possible value of the costs when these assumptions don’t hold. In that case, we only need to estimate the discrete cost distributions on the -net, and then apply Algorithm 4 to tackle the problem. Unfortunately, we find that the -net construction doesn’t work for continuous cost distributions, and it is unlikely to achieve efficient
regret guarantee without further assumptions and the modification of the basic setting. If the cost distributions are continuous and the remaining budget can take any value in R, a small perturbation on the remaining budget may totally change the policy in the following steps and the optimal value. To be more specific, suppose the agent enters a certain state with remaining budget b. There are three actions to choose, with the cost of b− , b and b+ , respectively. After suffering the cost, the agent can achieve reward of 0, 0.5 and 1 respectively. Note that we can construct such hard instances with extremely small. For these hard instances, we need to carefully estimate the value function of any remaining budget b ∈ R and the density functions of the costs, after which we can calculate the value through Bellman backup and find the optimal policy. However, estimating the density functions requires infinite number of samples and makes the problem intractable. In other words, the “non-smoothness” of the value and the policy w.r.t the remaining budget makes the problem difficult for continuous value distribution without further assumptions. This “non-smoothness” phenomenon also happens in the classical knapsack problem.
There are two possible ways to remove these assumptions and apply our algorithm to continuous cost distributions with -net technique. The first idea is to allow the slight violation of the total budget constraints, with the maximum violation threshold δ, or we assume that the value of any initial state is lipschiz w.r.t the total budget B in a small neighborhood of B (With maximum L∞ distance δ). In that case, we can tolerate the estimation error of each cost function to be at most δ H . -net technique with = δ H still works in this case and we can estimate the cost distribution with precision δH . This modification is somewhat reasonable since the agent’s policies are always “smooth” w.r.t the total budget in a small region near B in many real applications such as games and robotics. The second idea is to consider soft constraints. That is, when the budget constraints are violated, the agent will suffer a loss that is linear w.r.t the violation of the constraints. We assume the linear coefficient is relatively large compared with other parameters. This is also a possible method to remove the non-smoothness w.r.t the total budget, which has wide applications in constrained optimization.

Review summaries:
The authors study the factor MDP problem in an online and episodic setting. They provide two main contributions on this question. First, they propose an OFU type algorithm which enjoys a better regret bound than Osband & Van Roy (2014) by a factor of  $\sqrt{nH \Gamma}$. The improvement is brought about by a refined consideration on the confidence radius' dependence on the variances of the rewards, which carries a similar idea to the design of UCBVI-CH by Azar et al. 2017 for the tabular case.  The second contribution is on the generalization to an episodic FMDP with knapsacks problem, where the authors generalize the approach in the first contribution to provide a regret bound. 

This paper proposes a reinforcement learning algorithm FMDP-BF for episodic Factored MDPs. Similar to previous works, FMDP-BF follows the principle of "optimism in the face of uncertainty" to efficiently explore to achieve low regret. Compared to algorithms for general MDPs, FMDP-BF leverages the factorization structure of FMDP and results in exponential regret reduction in the size of the sate space. Compared to previous results for FMDP, the proposed algorithm utilizes Bernstein-type confidence bounds and new bounds on the factored transitions to reduce the regret order. The paper also connects a class of constrained RL to FMDP and  provide a sample efficient for the constrained RL problem.