Efficient Reinforcement Learning in Factored MDPs with Application to Constrained RL
Authors: Xiaoyu Chen
Jiachen Hu
Lihong Li
Liwei Wang
Venue: ICLR 2021 Poster (2021)
Keywords: reinforcement learning
factored MDP
constrained RL
learning theory

Abstract: Reinforcement learning (RL) in episodic, factored Markov decision processes (FMDPs) is studied. We propose an algorithm called FMDP-BF, which leverages the factorization structure of FMDP.  The regret of FMDP-BF is shown to be exponentially smaller than that of optimal algorithms designed for non-factored MDPs, and improves on the best previous result for FMDPs~\citep{osband2014near} by a factor of $\sqrt{nH|\mathcal{S}_i|}$, where $|\mathcal{S}_i|$ is the cardinality of the factored state subspace, $H$ is the planning horizon and $n$ is the number of factored transition. To show the optimality of our bounds, we also provide a lower bound for FMDP, which indicates that our algorithm is near-optimal 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, known as RL with knapsack constraints (RLwK), and provides the first sample-efficient algorithm based on FMDP-BF.

Published as a conference paper at ICLR 2021
EFFICIENT REINFORCEMENT LEARNING IN FACTORED MDPs WITH APPLICATION TO CONSTRAINED RL
Xiaoyu Chen Jiachen Hu
Key Laboratory of Machine Perception, MOE, School of EECS, Peking University {cxy30, nickH)@pku edu.cn
Lihong Li
Amazon
11h@amazon.com
Liwei Wang
Key Laboratory of Machine Perception, MOE, School of BECS, Peking University Center for Data Science, Peking University wanglw@ cis pku. edu.cr en
ABSTRACT
Reinforcement learning (RL) in episodic, factored Markov decision processes (FMDPs) 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[Ond & Van (2014b) by a factor of VnH[S, where |S;] is the cardinality of the factored state sub- space, H is the planning horizon and 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, application, we study new formulation of constrained RL, RL with knap- sack constraints (RLwK), and provide the first sample-efficient algorithm based FMDP-BF.
INTRODUCTION
Reinforcement learning (RL) is concerned with sequential decision making problems where agent interacts with stochastic environment and aims to maximize its cunulative rewards. The environ- ment is usually modeled function are unknown to the agent. A main challenge of the agent is efficient exploration in the MDP, so to minimize its regret, or the related sample complexity of exploration.
Markov Decision Process (MDP) whose transition kernel and reward
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 al.) 2017 Jin al. 2018 Dong et al. 2019 Zanette & Brunskill, 2019 Moreover, matching lower bounds re.gg.Jakscr et al. 2010) imply that these results cannot be improved without additional assumptions. On the other hand, many RI. 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 the state may evolve independently of others, and only depend on low- dimensional subspace of the previous state. Formally, these problems
be described factored MDPs (Boutilier et al. 2000 Kearns & Koller 1999] Guestrin et al. (003). Most relevant to the present work Osband & Van Roy (2014h), who proposed posterior sampling algorithm and

---

Published as a conference paper at ICLR 2021
UCRL-like algorithm that both enjoy vT 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 de- veloping corresponding lower bounds for episodic FMDPs. We propose sample- and computation- efficient 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 algorithm is near-optimal with respect to the timestep T, the planning horizon H and factored state-action sub- space cardinality [2|2.]]
As an application, we study a novel formulation of constrained RL, known as RL with knapsack constraints (RLwK), which we believe is natural capture many scenarios in real-life applications. We apply FMDP-BF to this setting, to obtain a statistically efficient algorithm with regret bound that is opar-optimal terms of 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 previ- ous result of Osband & Van Roy 2014b) by factor of /nH S.
2. We prove regret lower bound for FMDP, which implies that our regret bound is near- optimal in terms of timestep T, horizon H and factored state-action subspace cardinality.
3. We apply FMDP-BF in RLwK, novel constrained RL setting with knapsack constraints, and prove a regret bound that is near-optimal in terms of T, S, A and H.
PRELIMINARIES
We consider the setting of a tabular episodic Markov decision process (MDP), (S, 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 taken on state and R(s, a) is the reward distribution of taking action on state with support [0, 1]. We use R(s a) to denote the expectation E (((ss.a)) a)].
In each episode, the agent starts from an initial state 81 that may be arbitrarily selected. At each step E [H], the agent observes the current state 8, E S, takes action up E A, receives a reward rn sampled from R(s,, an), and transits to state 8h+1 with probability P(s++ an). The episode ends when + is reached.
A policy is collection of Il policy functtion {TH S + ALHEAH We use VØT - R to de- note the value function at step under policy म, which gives the expected sum remaining rewards received under policy π starting from $p. i.c V E
En'= R(sw, (sw)) sh. s) Accordingly, we define (5, as the expected Q-value function at step h: (s,a) E R(sh, an) ER= R(sw, (sw)) 5h s, an a] We use Vū and Qi to denote the optimal value and Q-functions under optimal policy xt' at step h.
The agent interacts with the environment for K episodes with policy T { : S A)EE(H) determined before the k-th episode begins. The agent's 's goal is to maximize its cumulative rewards ΣK Ei Fk. over T = KH steps, or equivalently, to minimize the following expected regret:
K
Reg(K)
del' Σ (V. (st,1))
1=1
where 81,1 is the initial state of episode k.
2.1 FACTORED MDPs
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 al.) 2000 Osband & Van Roy/ 2014b Xu & Tewari 2020 Lu & Van Roy 2019). Let PPX, denote the set of functions
that map X to the probability distribution on
2

---

Published as a conference paper at ICLR 2021
Definition 1. (Factored set) Let X X1 x... x Xa be factored set. For any subset of indices Z S {1, d]. we define the scope set X == B,eZ Further, for any x E X. define the scope variable z|Z] Z to be the value of the variables 2; X; with indices i E Z. If Z is singleton, we will write z:ii for x[((]].
Definition 2. (Factored reward) The reward function class R P(X R) is factored over S Sx A X' = 21 x- ... x Kd with scopes Zi.-.. Zm if for all R E R. I E X, there exist functions {R, P(X [2.] 10, 1)] such that r R(z) is equal m Ei=1 T4 with each T ~ (,(x(Z,))
individually observed. We use R. to denote the expectation E(R,)
Definition& 3. (Factored transition) The transition function class P C PPX is factored over x A = X = X1 x .... x Xa and S1 X X Sn with scopes Zi.... Zn if and only if. for all P E P.EEN. X, s E S, there exist functions {P, E P (X [2,] S,) such that P(s r)
m P3 (s()) (7,)).
A factored MDP is an MDP with factored rewards and transitions. A factored MDP is fully m )=z [[R:)== ; }==
(z,"),=11 { 11 where X' = S x A. (2R) m and {2,) 33=1 are the scopes for the reward and transition functions, which we assume to be known to the agent.
characterized by M- ((&) {z,
An excellent example of factored MDP is given by Osband & Van Roy (2014), about large produc- tion line with d machines in sequence with S; possible states for machine i. Over single time-step each machine can only be influenced by its direct neighbors. For this problem, the scopes Z and 7f of machine i { and machine are {1, 2) and {d - 1, d] respectively. Another possible example to explain factored MDP is about robotics. For 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.
..... d 1) can be defined {i 1, i 1}, and the scopes of machine
For notation simplicity, we use X1i 5] and Sli .l to denote X'UR= Zn] and 8/_, re- spectively. Similarly, We use (o .]] I 8, a,a) to denote [I [k) (8, a) (zf.) For every : + R R and the right- linear operators P. we define aV) def Eves P(s' a.)) A state-action pair can be represented as (s.a) a) or x. We also use (s, [2] to denote the corresponding x [ for notation convenience. We mainly focus on the case where the total time step T K is the dominant factor, and assume that T' 2 [ 2 H during the analysis.
3 RELATED WORK
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 al. 2017 Azar et al. 2017 Jin et al.] 2018 Zanette & Brunskill 2019), linear RL (e.g.. Jiang et al.
2017 Yang & Wang 2019:0im Jin al. |0200 2020teZaeette Zanette al. 20200, and RL with general function ap-
proximation (e.g..(Oshee Osband & Van Roy [2014a] Ayoub et al. 2020 Wang et al. 2020). For algorithms in tabular setting, the regret bounds inevitably depend
the cardinality of state-action space, which may be excessively large. Based on the concept of cluder 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 most O -== 2 K Σn |x(2, it is possible to apply their
algorithms and regret bounds to our setting, though the direct application of their algorithms leads to loose regret bound.
Factored MDP Episodic FMDP was studied by Osband & Van Roy (014b), in which they pro- posed 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 Os- band & 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 e'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 more refined variance
3

---

Published as a conference paper at ICLR 2021
decomposition theorem for factored Markov chains (Theorem D which results in better regret by a factor of vn; the theorem is also of independent interest with potential use in other problems in factored MDPs. Furthermore, formulate the RLwK problem. and provide a sample-cfficient 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- diyuru et al.) 2013] Agrawal et al. 2016). This setting may be viewed as a special case of RLwK with H In constrained RL, there is line of works that focus on soft constraints where the con- straints are satisfied in expectation or with high probability (Brantley et al.
algorithms (Badani-
2020: Zheng & Ratliff 2020), or violation bound established (Efroni et al., 2020; Ding et al. 2020p. RLwK requires stronger constraints that is almost surely satisfied during the execution of the agents. A more related setting is proposed by Brantlyy et al. (020), which studies sample-efficient algorithm for knap- sack episodic setting with hard constraints on all K episodes. However, we require the constraints to 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.
4 MAIN RESULTS
In this section, we introduce our FMDP-BF algorithm, which uses empirical variance to construct Bernstein-type confidence bound for value estimation. Besides FMDP-BF, we also propose 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
4.1 ESTIMATION ERROR DECOMPOSITION
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 opti- mistic and pessimistic estimates of state values to yield an improved regret bound. We use V A. and Ki,h to denote the optimistic estimation and pessimistic estimation of Vir respectively. To guarantee optimism, we need add confidence bonus the estimated value function VA, each step, so that (s) 2 (x) holds for any k E [K], h E [H] and s S. Suppose Ri., and Pk, denote the estimated value of each expected factored reward R, and factored transition prob- ability P, before episode respectively. By the definition of the reward R and the transition P. use At def Ei= Re. and P. def I1 PA.j as the estimation of R and IP. Following the vn previous framework, this confidence bonus needs tightly characterize the estimation error of the one-step backup R(s, a) + +V,, (8, a); in other words, it should compensate for the estimation errors, [Rx Rt (s, a) and (Px= - TP) Vi a). respectively.
For the estimation error of rewards (fL - (SK,D, aR.)), 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 eтror of each factored rewards. In that case, we separately construct the confidence bonus of each factored reward Rg Suppose CB k.2R (s, a) is the confidence bonus that compensates
for the estimation error RRs R., then we have CB (s, a) def 1 Em CB (z,.)((s..).
For the estimation error of transition (Pa- - 12) Vi (Sk,A, ap.)), the main difficulty is that IPx is the multiplication of n estimated transition dynamics Pr..- In that case, the estimation error (Ph- (Px-P) PP) Vi++1 (Sk,h, (k.h) may be calculated as the multiplication of n estimation error for each factored transition PR... which makes the analysis much more difficult. Fortunately, we have the following lemma address this challenge.
4

---

Published as a conference paper at ICLR 2021
Lemma 4.1. (Informal) Let the transition function class P E S) be factored over X' X1 x... x the estimation error of one-step value x IP) (s, a)l can be decomposed by:
Na. and = S₁ x ... x Sn with scopes ZP.... Zn. For a given function V : R,
1( - P)V(ss S
(P P.))
P3 (iij=1
II
((s,a) + (x,(ss
Here, (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 (fxx - IP)
(k.a)
into additive form, P3 separately. Let CB
can construct the confidence bonus for each factored transition k. (s, a) be the confidence bonus for the estimation error (Pkk
P2) (Tits,e-PP) a)) Then, (s,
ΣE= (z,pp(,,) + (s,n(s,),, where
& 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: (B) CB (s,a) + CBf (s,a).
4.2 VARIANCE FACTORED MARKOV CHAINS
After the analysis in Section 4.1 the remaining problem is how to define the confidence bonus CBR (s,a) a) and CB 22 (s,a). In this subsection, we tackle this problem by deriving the vari-
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 define the empirical variance in the confidence bonus for factored MDP and gives an upper bound on the summation of per-step variance (Corollary I.I.
In the Markov chain setting, the reward defined to be a mapping from S to R. Suppose Jt (8) denotes the total rewards the agent obtains from step & to step t2 (inclusively), given that the agent starts from state s in step t1. Jt is a random variable depending on the randomness of the trajectory from step 1 to 12, and stochastic rewards therein. Following this definition of Jty we define JI:H to be the total reward obtained during one episode. We use to denote the random state
that the agent encounters at step t. We define w def the variance of the total gain after step h. given that 8/.- = S.
(Jh.H (8k) Vi((n))) |Sn = to be
We define (s) given that the current state 8. Given the current state 8, we define the variance of the next-state value function w.r.t. the i-th factored transition as: ()) der
to be the variance of the i-th factored reward,
Em-- (an+ilt [Bn+ili+ism) (9++)() 8n = =s That is, for each given s'[1 i]. we firstly take expectation over possible values of 8'li + 1 n) w.r.t P1e+1o]- Then, we calculate the variance of transition s' s'[i] ~ P.(- a) (2,")) given fixed s'1 i - 1]. Finally, we take the expectation of this variance w.r.t. s'[
1] Pp---1j.
Theorem 1. For any horizon h E [H. we have (s) = E. ((ss (s) E (s)+
EE (s).
Theorem I generalizes the analysis of Munos & Moore 1999), which deals with non-factored MDPs and deterministic rewards. From the Bellman equation of variance, can give an upper bound to the expected summation of per-step variance.
Corollary 1.1. Suppose the agent takes policy n during an episode. Let wn wn(s, a) denote the proba- bility of entering state and taking action in step h. Then we have the following inequality:
m Σ
Σ
Σ
wh (s,
Σ (V 1.8, 8,
S SH²
h=1 (3.0)EX
5

---

Published as a conference paper at ICLR 2021
where ( def (r,(s,,)ls=&,55- is the variance of i-th sac- tored reward given the current stale-action pair (s,a), and o.. Ben-n[1i--]] [V a [ (1++imm [ 8h =| s) the variance of i-th factored transition given current state
This corollary makes it possible construct confidence bonus with variance for each factored wards and transition separately. Please refer to Section F.2 for the detailed proof of Theorem Tand Corollary
4.3 ALGORITHM
Our algorithm is formally described in Alg. I with a more detailed explanation in Section C De- note by Ns,((s, [)] the number of steps that the agent encounters (s, a)[2] during the first episodes. In episode k, we estimate the mean value of each factored reward R4 and each fac- tored transition P, with empirical mean value Rg.; and PR., of the previous history data L respec- tively. After that, we construct the optimistic MDP MM based the estimated rewards and transi- tion functions. For a certain (s, a) pair, the transition function and reward function are defined as Ra(s,a) E Re,(((s,)) (2))) and Px(s') (, = I[i= PR. (o'[i] (s, a) [2f]).
Algorithm FMDP-BF
Input: 5
C initialize N [(ss, (2.) for any factored set Z4 and any (s. e x[Z]
for episode k = 2, do
Set V (s) VA,H f (s) = 0 for all a.
5: Estimate the empirical mean Rg and PAx with history data L.
for horizon h = H, H I,.... do
for E S do
for a E A do QR. a) min (H, (s( (B,(s, +
10:
end for
T (s) arg max, (s,
V (s) = max.e. (s)
V (s) = max 0. (s, (s) - CB&(s, (x)((s) + P (8,
end for 15: end for
Take action according to Ta.s for H steps in this episode.
Update L = LSkkk 4k,h, Pk, Sk,4+1 1...2.... and update counter (Z,))
end for
Following the analysis in Section 4.1 we separately construct the confidence bonus of each factored
reward R3 with the empirical variance: CB (s,a))
i [m], where I def log (18mT x|z /5), and 0%, the empirical variance of the i-th fac-
k.z.
(x-1((a.))22)) + (Na
28 2 (e
8L."
tored reward RG i.e. o (8, No Ne-1(190) ΣiA (k-1) 1 [[*,, a, [2,]] = (s, [2] rf,
(Rn.o((s, ((n.(((,))((Z31)) a)(2,11)
We define T.P log (18nTSA/0) for short. Following the idea of Lemma 4.1 sepa- rately construct the confidence bonus of scope 2 for transition estimation: CB (k,pp(s,a)) =
482 48% (VA- No (==1((s.))2
V (e..(( (,,
2ua 2us.nc(sa))LF
[n], where (p.,;(s,)) a) and
(s,,, a) are defined later. (s, a) collects the additional bonus terms that do not affect the order of the final regret. The precise expression of n, (8, a) is deferred Section

---

Published as a conference paper at ICLR 2021
corresponds to (V a) in Corollary The definition of T. (V,,,, k,4+1,
1.1 which
can be regarded as the empirical variance of transition Fk. ob.,, (V K.4+1,5, = E pe To guarantee optimism, we need to use the empirical variance 8 P.A. 8, a, to upper bound the estimation error in the proof. Since we do know V beforehand, we use 0 P.A.A (V...VVK,n VK,,+,, 8,0) a) as 8, a) is upper
(10= (B (B
V V
a surrogate in the confidence bonus. However, we cannot guarantee that 0Z. bounded by T. (V,, ,,h+1,,,00 To compensate for the error due to the difference between Vi+1 and V VR,++1. we add V 2u NR. ((=a((()))
to the confidence bonus, where uk,,, is defined as:
uk,h,i a) = E "las ~ (1
(w (i (VRA++ - Ks,,+2) (6
4.4 REGRET
Theorem 2. Suppose ||| & JR, |||,,| & JP for i [m],] E [n]. then with prob. 1 - 6, the regret of Alg. I is O ( (VJKT Jo.Tlooogmm log(mml (aannIJJ/// (K log + / A/0( logT)
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 By leverag- ing 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 setting, it becomes O lo + nH TT log(nTT)+))) where I' is an upper bound of Sy). This worse than our results by factor of VnHT. Concurrent
results, Tian et al. (2020) also pro- pose efficient algorithms for episodic factored MDP. When transformed to our setting, their regret bound Ô (VJRT + ny HVH)TT) Compared with their bounds, we further improve the regret by factor of /n with a more refined variance decomposition theorem (Theorem
4.5 LOWER BOUND
In this subsection, propose the regret lower bound for factored MDP. The proof of Theorem is deferred to [ection[G
Theorem 3. Suppose loga ([S+)) < H 7 for any E [n]]. the regret of any algorithm on the factored
MDP problem is lower bounded by Ω m Σm / | T E | HT
The lower bound of Tian et al. (000)) is Ω maxx max; v X| T. maxj / | 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 | = J and | x2 = J the
lower bound turns out to be VJRT + VHJTT). which matches the upper bound in Theorem except for a factor of vr and logarithmic factors.
5
RL WITH KNAPSACK CONSTRAINTS
In this section, we study RL with Knapsack constraints, or RLwK, as an application of FMDP-BF.
5.1 PRELIMINARIES
We generalize bandit with knapsack constraints or BwK (Budanidiyuru et al, 2013 Agrawal et al.] 2016) episodic MDPs. We consider the setting of tabular episodic Markov decision process,

---

Published as a conference paper at ICLR 2021
(S, (...H.H..R, which adds to an episodic MDP with d-dimensional stochastic cost vector, a)) We use Ci(s, a) to denote the i-th cost in the cost vector C(s, . If the agent takes action in state s, it receives reward sampled from R(s, a), together with cost before transitioning to the next state s' with probability P(s' 8, a). In each episode, the agent's total budget is B. We also use B, to denote the total budget of i-th cost. Without loss of generality, we assume B; B for all i. An episode terminates after H steps, or when the cumulative cost >, Ch. of any dimension exceeds the budget B,, whichever occurs first. The agent's goal to maximize its cumulative reward Σ E Fk, in K episodes.
5.2 COMPARISON WITH OTHER SETTINGS
While RLwK might appear similar to episodic constrained RL (Efroni et al. 2020 Brantley 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 cat- egories. A line of works focus on soft constraints where the constraints are satisfied in expectation, i.e. Σx= h= E(CA.A] < B. The expectation is taken over the randomness of the trajectories and the random sample the costs. Another line of work focuses on hard constraints K episodes. To be more specific, they assume that the total costs in K episodes cannot exceed a constant vector B, i.e.
H h= Ck.b S B. Once this is violated before episode K₃ K, the agent will not obtain any rewards in the remaining K- - K₁ 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 policy to carry out certain task. The interaction in each episode 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 poli- cies that map states to actions. Instead, in RLwK, need to define the policy mapping from states and remaining budget to actions. Section H Hivess further details, including two examples for illustrating the difference between these settings.
Σ
5.3 ALGORITHM
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 B; 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 1 m. Assumption 2. The stochastic cost C,(s, has finite support. That is, the random variable C,(s. a) can only take 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 HK
From the above discussion, we know that we need to find policy that 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)). Directly applying UCBVI algorithm (Azar al. 2017 will lead to a regret of order O (BS)T(Bm)d) Our key observation that the constructed state representation can be represented as product of subspaces. Each subspace is rela- tively 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. and Theorem 2 to RLwK, we can reduce the regret to the order of of [H5A(1 + dBmm)T roughly, which is exponentially smaller. However, the regret still de-
8

---

Published as a conference paper at ICLR 2021
pends the total budget B and the discretization precision m, which may be very large for contin- uous budget and cost. Another observation to tackle the problem is that the cost taking action a on state 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 b = by Ch. where b₁ is the remaining budget at step h, and C₁ the cost suffered in step h. As result,
further reduce the regret to roughly
O HddS AT by estimating the distribution of cost function. A similar model has been discussed in Brunskill et al. (2009). which named as noisy offset model.
Our algorithm, which is called FMDP-BF for RLwK. follows the same basic idea of Alg. [ defer the detailed description to Section H to avoid redundance. The regret can be upper bounded by the following theorem:
We
Theorem 4. With prob. at least 1 - 8, the regret of Alg. is upper bounded by
(v daHSAT (log( + dllo((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.
should be noted that, though we achieve a near-optimal regret for RLwK, the computational com- plexity is high, scaling polynomially with the maximum budget B, and exponentially with the num- ber of constraints d. This a consequence of the NP-hardness of knapsack problem with multiple constraints (Martello 1990, Kellerer al.) 2004). However, since the policy is defined on the state and budget space with cardinality SB", this computational complexity seems unavoidable. How to tackle this problem, such as with approximation algorithms, an interesting future work.
CONCLUSION
We propose novel RL algorithm for solving FMDPs with near optimal regret guarantee. It im- proves the best previous regret bound by factor of VnH.S. We also derive regret lower bound for FMDPs based on the minimax lower bound of multi- aallid bandits and episodic tubular MDPs (Jaksch et al. 2010p. Further, we formulate the RL with Knapsack constraints (RLwK) setting, and establish the connections between our results for FMDP and RLwK by providing 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 vn, where n is the number transition factors. For RLwK, 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.
ACKNOWLEDGEMENTS
This work was supported by Key-Area Research and Development Program of Guangdong Province (No. 2019B121
National Key R&D Program of China (2018YFB (2018YFB1402600) BJNSF (L172037) and Beijing Academy of Artificial Intelligence.
REFERENCES
Shipra Agrawal, Nikhil R Devanur, and Lihong Li. An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives. In Conference Learning Theory, pp.
4-18, 2016.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pp. 463-474. PMLR, 2020.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. arXiv preprint arXiv: 1703.004444 2017.

---

Published as a conference paper at ICLR 2021
Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knapsacks. In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 207-216. IEEE, 2013.
Craig Boutilier, Richard Dearden, and Moisés Goldszmidt. Stochastic dynamic programming with factored representations. Artificial intelligence, 121(1-2):49-107, 2000.
Kianté Brantley, Miroslav Dudik, Thodoris I Lykouris, Sobhan Miryoosefi, Max Simchowitz, Alek- sandrs Slivkins, and Wen Sun. Constrained episodic reinforcement learning concave-convex and knapsack settings, arXiv preprint arXiv:2006.0500 05001, 2020.
Emma Brunskill. Bethany R. Leffler, Lihong Li. Michael L. Littman, and Nicholas Roy. Provably efficient learning with typed parametric models. Journal of Machine Learning Research, 10(68); 1988,1988, 2009, URLhttp: 3mmr org wwwp:/pwwp..///////op/t/// http/////bbb/uuuetet 100a htmll
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform PAC bounds for episodic reinforcement learning. In Advances in Neural Information Processing Sys- tems, pp. 5713-5723, 2017.
Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill, Policy certificates: Towards accountable reinforcement learning. In International Conference on Machine Learning, pp. 1507-1516, 2019.
Dongsheng Ding, Xiaohan Wei, Zhuoran Yang, Zhaoran Wang, and Mihailo R Jovanović. Provably efficient safe exploration via primal-dual policy optimization. arXiv preprint arXiv:2003.00534, 2020.
Kefan Dong, Yuanhao Wang, Xiaoyu Chen, and Liwei Wang. Q-learning with UCB exploration is sample efficient for infinite-horizon MDP. arXiv preprint arXiv: 2019.
Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exploitation in constrained MDPs.
arXiv preprint 1rXxi:2003.02/880 2020.
Carlos Guestrin, Daphne Koller, Ronald Parr, and Shobha Venkataraman. Efficient solution algo- rithms for factored MDPs. Journal of Artificial Intelligence Research, 19:399-468, 2003.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11:1563-1600, 2010.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. Con- textual decision processes with low Bellman rank PAC-lcarnable. In International Conference on Machine Learning, pp. 1704-1713, 2017.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is Q-learnigg provably effi- cient? In Advances Neural Information Processing Systems, pp. 4863-4873, 2018
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference Learning Theory, pp. 2137-2143. PMLR, 2020.
Michael Kearns and Daphne Koller. Efficient reinforcement learning in factored MDPs. IJCAI, volume 16, pp. 740-747, 1999.
Hans Kellerer, Ulrich Pferschy, and David Pisinger. Multidimensional knapsack problems. In Knap- sack problems, pp. 235-283. Springer, 2004.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Lihong Li. A unifying framework for computational reinforcement learning theory. PhD thesis, Graduate School-New Brunswick, 2009.
Rutgers Uraauut
Xiuyuan Lu and Benjamin Van Roy. Information-theorede confidence bounds for reinforcement learning. Advances in Neural Information Processing Systems, pp. 2461-2470, 2019.
Silvano Martello. Knapsack problems: algorithms and computer implementations. Wiley-
Interscience series in discrete mathematics and optimiza tion, 1990.
10

---

Published as a conference paper at ICLR 2021
Rémi Munos and Andrew Moore. Influence and variance of Markov chain: Application to adaptive discretization in optimal control. In Proceedings of the 38th IEEE Conference on Decision and Control (Cat. No. 99CH36304), volume 2. pp. 1464-1469. IEEE, 1999.
lan Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. arXiv preprint arXiv:1406. 1853, 2014a.
lan Osband and Benjamin Van Roy. Near-optimal reinforcement learning in factored MDPs. In Advances in Neural Information Processing Systems, pp. 604 612, 2014b.
Daniel Russo and Benjamin Van Roy. Eluder dimension and the sample complexity of optimistic exploration. In NIPS, pp. 2256-2266 Citeseer, 2013.
Rahul Singh, Abhishek Gupta, and Ness B Shroff. Learning in Markov decision processes under constraints. arXiv preprint arXiv:2002.12435, 2020.
Alexander L. Strehl, Lihong Li, and Michael L. Littman. Reinforcement learning in finite MDPs: PAC analysis. Journal of Machine Learning Research, 10:2413-2444, 2009.
Yi Tian, Jian Qian, and Suvrit Sra. Towards minimax optimal reinforcement learning factored Markov decision processes. arXiv preprint arXiv:2006. 2020.
Ruosong Wang, Russ Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33, 2020.
Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger. In- equalities for the L1 deviation of the empirical distribution. Hewlett-Pacc Packard Labs, Tech. Rep, 2003.
Ziping Xu and Ambuj Tewari. Near-optimal reinforcement learning in factored MDPs: Oracle- efficient algorithms for the non-episodic setting. arXiv preprint arXiv2200..02302, 2020.
Lin F Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive fea- tures. arXiv preprint arXiv:1902.0m
2019.
Andrea Zanette and Emma Brunskill. Tighter learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pp. 7304-7312. PMLR, 2019.
regret bounds in reinforcement
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning optimal policies with low inherent bellman error. arXiv preprint vrXiv:2003.00153 2020.
Liyuan Zheng and Lillian J Ratifff Constrained upper confidence reinforcement learning. arXiv preprint XrXiv:2007.00 200.0000000 2020.

---

Published as a conference paper at ICLR 2021
A
NOTATIONS
Before presenting the proof, we restate the definition of the following notations.
Symbol
Explanation
Sk,b, Ok.h LP
The state and action that the agent encounters in episode & and step h
log (187TSA/5)
I.R
log (18m7 x R /8)
X
x
X
x
Na((s,)) 0))
the number of steps that the agent encounters (s, a) [2] during the first & episodes
A shorthand of E s, (
(s,
L| V ((-1(1s.) ((t_0(+
4|8, L
(s,
The empirical variance of reward R; the next state variance of PV for the transition IP:
(V,,
i.e. [e([LiiI)-FFpaa(eea the empirical next state variance of Ipx for the transition PR.
V V=(())).. [Ba)(tt (1s,a) v(s))]
OP,,,((Vs,,a
iec E (a
V (1 [E
V (s'))
Pknh
The optimism and pessimism event for k h: V. 2 V 2 van The optimism and pessimism events for all
S K, S H. i.e. Jk,
(s,
The probability of entering (s at step h in episode k
(x,
Σ WR,A., (8,
(s,n(s,a)
The probability of entering (s, a) at step h in episode k, ie. wk,,,2(s, a) with Z {1, ..., d}
wR wx(s, a)
Σ Wh. Wh,n
B OMITTED DETAILS FOR FMDP-CH
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 UCBVI- CH algorithm (Azar et al. 2017), in the sense that Algorithm reduces to UCBVI-CH if we consider a flat MDP with m n d=
Let Na((s, a) [Z) denote the number of steps that the agent encounters (s, [s, during the first episodes, and N=((s,a)\Zz):. denotes the number of steps that the agent transits to a state with s[j] 8, after encountering (s,a)[Z,) during the first & episodes. In episode k we estimate the mean value each factored reward R, and each factored transition P, with empirical mean value Rr, and PR.Y respectively. To be more specific, Re, a) (2(1)
Eicik nu No-1 ((]1)
where Tt,s denotes the reward R3 sampled in step 4, and _==1((s.a)
PRU (s)i)((s Ne- ((sa))2)))))) After that, we construct the optimistic MDP M based
on the estimated rewards and transition functions. For certain (s, a) pair, the transition func- tion and reward function are defined as (s, = 1 m Em R (2 and PA(s' s,a) = IT Pko (s/ (8,a) [z
We define L.
log (18mT x(2 /8), LP 418.IL ([sai['
log (18nTSA/8) and (s,
No. 4JS, LP
We separately construct the confidence bonus of each fac-
((
12

---

Published as a conference paper at ICLR 2021
Algorithm 2 FMDP-CH
Input:
history data C = 0, initialize ((ss, a))l = 0 for any factored set Z; and [s,a)[Z,] E X[Z]
for episode 1, 2.... do
Set 1I,
for all 8.
5: Estimate ; a) with empirical mean value if N ((5, (2,1)) (x, a) = 1, then calculate a(s,a)= - (,, a) (2,5)
> 0, otherwise
Let KCp {(s, a) E S A, Uie(n) (t<,))))(((s > 0)
Estimate Px((Iss.4) a) with empirical mean value for all (s,4) a) E Erp for horizon h = H. H - -,..., do for all (s E S x A do
if (s.a) Kp then
(s, = min (H, as(s, + CBa(s,a) + (
else
Qu,n(s,a)= H
end if
15:
(s) = maxaE (s,
end for
end for for step h 1
do Take action aR,h arg max, QR,h a) 20: end for
Update history trajectory Cs Ou, Tki Sk, 11m1,2.......... and update history counter ( (2.)) end for
tored reward R2 and factored transition P. in the following way:
2T
CB (B, -1
iE [m]
(1)
N VV-1((sa)\Zz"1)
2H²L"
CB. ( (a-1((s,a)(Z?))
+ (o,
Σ (s, i [n]
(2)
j=1,jşi
We define the confidence bonus as the summation of all confidence bonus for rewards and transition, ie. CB,(s, a) Em CBR k. (s, a) + Σラ= CB. 2 (s,a) a).
R.
We propose the following regret upper bound for Alg. 2
Theorem 5. With prob. 1 - 8, the regret of Alg. 2 is upper bounded by
1 /
Reg(K)= O
X107 +
H1 [
Here O hides the lower order terms with respect to T.
C OMITTED DETAILS IN SECTION 4
In this section, we clarify the omitted details in Section The detailed algorithm is described Alg. 3 we denote Na((s, Z)) as the number of steps that the agent encounters (s, [) during the first & episodes, and N&((s, s)),)),;)) as the number of steps that the agent tran- sits to a state with slj] = s, after encountering (s, [),) during the first & episodes. In episode k estimate the mean value of each factored reward R, and each factored transition P, with empirical mean value Re. and Pr.s respectively. To be more specific, (t.,(((s)))2f)))
13

---

Published as a conference paper at ICLR 2021
Lasa- uur ((..0))))= where rt, denotes the reward R; sampled in step t, and N₂ (({,a)(7;)))
PkJ (+[i](s, a) [2
Ne-1 ((.0(().012 Nu 1(
The formal definition of the confidence bonus for Alg Dis:
20 R (s, L NK-1( ((5, a) (2,71)
CB (s
(3)
3N ((s, (z,1)
40 (V (V..V kAt,,, 8,
(s,
C (8, -V
(4)
NR- ((s, (2(")
Nx, (2,"))
1
4|5
L|
+ NR- ((s, (2,,"))
+
3. (s,, a2
(5)
(8, ())),)))))))
(6)
where (s,
4|8,1LP
4|8,1LP 3N 3(=-1((s.))
The definition of mk. (s, a) is
N2-1((s.0)155))
+
16
415
+
(3,
N ((,)((s,a)) (2,1)
(1-1((s.a)\2,71)
as)
Theorem 6. (Refined Statement of Theorem 2) With prob. least 1- the regret of Alg. is upper
bounded by
O 1
m Σ
[xiz [ (8) log
Σ H x[Z Tlog log T
For clarity, also present cleaner single-term regret bound under symmetric problem setting. Suppose M is a set of factored MDP with m = n, [S = 5,, |x|] S,A, and |z.51 | =
for i = 1,..., m and 1,..., n, we write X; = (S;A,) and assume that X; S J and S S.
Corollary 6.1. Suppose M e M. with prob. - 5, the regret of FMDP-BF is upper bounded by (ntHJTooo((TSAA8)
The minimax regret bound for non non-factored MDP is O logAloogSTAT/5)) 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 (nll [TJTlog(nJ]]) Our results is better by factor of VnHT.
D HIGH PROBABILITY EVENTS
In this section, we discuss the high-prob. events, and assume that these events happen during the proof.
14

---

Published as a conference paper at ICLR 2021
Algorithm 3 FMDP-BF (Detailed Description of Alg. 1
Input: ò
L V. initialize [(s, a) Z,]) Z.))
0 for any factored set Z₁ and any (s, a)(Z)] E [
for episode k 1,2,.... do
Set VR, = - (s) = 0 for all s.a.
5: Let {(,,a) E 8 A: M No. (() (Z.f)) > 0]
Estimate [x, a) as the empirical mean N ((x, a) (2 > 0. and otherwise
R(s, a) = - Σ Ri((s, [[([s,a][2]] (2."))
Estimate (x(-|s,a) a) with empirical mean value for all (s,4) a) E K
for horizon h = H, 1, do
10:
for s E S do
for E A do if (s. E IC then
(s,n( = min(H, Rs( CB,(s, + (
else
15:
Q (s, =H
end if
end for
TK.A (s) = arg max, (s,(
VR, (8) = max.e (s,
R, (s) max {0, R2 (s)) - (x((s) + P.V. 18
20:
end for end for
for step -, H do
Take action Ag,A - arg maxa QR (s 25: end for Update history trajectory = C88Kk, Uk Tki Sk, 1=1,,, Hy and update history counter Nx-1((s,a)(2)) end for
Lemma D.1. (High prob. event) With prob. at least 26/3, the following events hold for any k, h,, 8,8,0
2T.
((s Ra((s, (2, S
i i [m]
Na-1((s,, ((,
2H²IP
PP..
Pk. (s, II P. (I. j=1
d
V
Nk-1 (s,a)(?!))
171
|S.LLP
I(PA, Ps, s //
ie [m]
(9)
NN-1((5,a) (ss)a)]??]))
3N ((s,
3N
a)(2F1)) (S'
L.
(( (s.
i [n] (10)
(1 (2,"))
3N (88-((()a)(22)))
IP (iih41 Vitti (sk an.))
(Ve.641-1 - V (sn.at1)) S
2HT log (1SAAT)
(11)
K H
ΣΣ
IP (Ve,N41
Vintz) (Sp,A, ap.))
(Ve,041 Viett (shAt1)) I / 22H LogTTlo((115)) (18SAT)
(12)
We define the above events A1, and assume it happens during the proof.
15

---

Published as a conference paper at ICLR 2021
Proof. By Hoeffding's inequality and union bounds over all i [m], step k [K] and (s.a)
X[z,"), know that Inq. 7 holds with prob. 1 - o for any i E [m]] k [K] (s. E x Similarly, by Hoeffding'ss ss incquality and union bounds over all i E [n]. step and (5, a) E X,
Inq. 88 also holds with prob. 1 & for any i, a, a. k. Inq. is the high probability bound on the L norm of the Maximum Likelihood Estimate, which is proved by Weissman al. (2003). Inq. I0 can be proved with the use of Bernstein inequality and union bound (See Azar et al. (2017) for similar derivation). Inq. and Inq. [2 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 A holds with prob. at least 25/3. L
For the proof of Thm. 2 we also need to consider the following high-prob. events. We define the following events as Ag. During the proof of Thm. 2 we assume both A1 and A2 happen.
Lemma D.2. With prob. at least - 6/3, the following events hold for any k, h, 8,
28 (s.
8L
Aa. -
((, - SV (N_
i [m]
(13)
20 (V (V+
2HL
(PPK. - -P.) PIs S
i [n]
(14)
N a) (2
3N (()
jØi
Na((s, (2(1
Σ jck
(s,
H 18n (18)) |m)
(15)
be proved directly by empirical Bernstein inequality. Now mainly focus Inq. 14 By Bernstein's 's inequality and union bounds over all s, a, k, h. we know that the following
Proof. Inq. 13
inequality holds with prob. at least
(IKK, P.) I[PrVE+11ssa)
Σ
P(s'L1 :i a)
(Pnni--p -P.)
II f=++1
P. Viin (s,
8'In [1-11
2 (aTT11)) (P s'1 :i -
11) Lr
Σ
P(8'1 :1 101i-11l3 -1]]s,a)
N a)("
8(11: 1a-1]
2HL
+
Σ
P(8 1]|5, a) 3N ((8, (2,')
[|:
20 (V LL
2HL
N No-1((s, a) (2,P))
3N (0--1((s00))) als,))
The last inequality is due to Jensen's inequality. That is,
C1
C)p(' 11) *(1:-11] (o-1((s,a(2,71)
Σ P( v
(Z-((s,
11=-1
20 (, N (,,'1)
where P(s'[1 i 1]) is a shorthand of P(s [1:i[[ii- : 1][s, a), and C1 here denotes
s.0) V(s') s( :1 11) I.P
[Er Vaar:
Inq. 15 follows the same proof of the failure event FN in section B.1 of Dann al. 2019
16

---

Published as a conference paper at ICLR 2021
E PROOF OF THEOREM 5
E.1 ESTIMATION ERROR DECOMPOSITION
Lemma E.1. The estimation error be decomposed in the following way:
((Px P)((s,)))1 -
I(PR. P.)(((s,a)(z,1))
(16)
I(px - PVV Σ
(PAA P.)
II P,
V(s,a)
j
Σ
1100
(P.. (-1ss, (1(3)))1211) I IP;) (1(5))))2f1))
1=1 -+ijj=1
(17)
here V denotes any value function mapping from R. e.g. Vi+1 or Vi,t41 Vit+
Proof. Inq. 16 has the same form of Lemma 32 in Li 2009 and Lemma in Osband & Van Roy
2014b). We mainly focus on Inq. 17 We can decompose the difference in the following way:
(1xx (s)
12
n-1
<
(PP.m Fw.
(s, a)
P.
PAA
II
(s,
(PPnn Pr)
PR.
II
P.) (s,a)
(18)
For the last term of Inq.
18 we have
k.n P
PRAE
II (s)
n-1
n-1
< (Pkm Pn) (-1(s,a)
II Pr.l--s,
II
P. P. a(z,")) |V
$ (PA.. 1h.n-Pa) PP) (-1(s, ()(2
Σ (PP.:- - P.) (-1(s, (((ss))))))))
1V
Where the last inequality is due to Inq. T6
For the second part of Inq. 18
we can further decompose the term as:
72
n
P
R
a(
n2
n-
<
Pn
P P - PPn-1
II (s, a)
PnPPn-
II
Px.s
II P.
v(s,a)
n-2
n-2
+ Pn (P -P Pa-1)
II
PK.S
II TP 1=1
v(s
(19)
Following the same decomposition technique, can prove Inq. second term over all possible n::
17 by recursively decomposing the
((px - PVV (s,
(K - P.)
II Py j+1.j=1
a)
1=1
Σ
Σ
(PA.. - P.) (-1(s (((s,))/2( a)(
: -P,) (((ss,))2z))) |V
1=1 j
17

---

Published as a conference paper at ICLR 2021
Lemma F.2. Under event A1, then the following Inequality holds:
[R)(s, - -R(s, a)l v 1
2
(20)
==1
4|8: L
4|8:/L"
I(Px P) 2
Σ
(21)
Nk-
((,,a)
3N 1 a) (Z,7)
2H2IPP
1(fx - (s.) -
Nk-1((s,0) a(), 1z
i=1
(V
4.S.LL
4|8.1L"
(V ((.)
4|5,|L0
4|5,|L"
+Σ H
((,,a
((),
1=1 jfij=1
(22)
Proof.
Inq. 20 can be proved by Lemma D.1
1
1 m
21
Rs(s, R(s,a)) S m
Rs R(s, a)l
N Ne-1((s,
Inq. 21 follows directly by applying Lemma D.I to Lemma
4|S.|ILP
4|S
I(px - P))( a)l1 S Σ I(PPA.. - P.((((s, S
+
3N,-1($s,a) (z-
Similarly, Inq can be proved by:
[Ppx - -P -s,)as
a
(PA, P.))
II P, (*(saa)
(Ph. - P. (-1(s. -
(Bes (lag-P,)) (1(s,,))2]1
H
jiij==
2
N (z))))
L.P
L
4|S,ITP
4|S,[TP
H
(v
(0-1((s,))ZzP))
(N.-1((s. (1),T)
(V-
(2)-1((s.o((291)
j=ijj=l
E.2 OPTIMISM
Lemma F.3. (Optimism) Under event N1, V 2 for any k. h.
Proof. We prove the Lemma by induction. Firstly, for = H + 1, the inequality holds trivially since (s) = (s) = O.
(s,((s) (s)
2ic(s, mi)()) + CB, (x)) + P. (( - ((()) - (8,
-Ra(s, (x))) - R(s, + CBa(s, (z) + Pa(V..t (s, + (Prx
Re, (h)) R(s, + CB (T) (Pr (s,
20
18

---

Published as a conference paper at ICLR 2021
The first inequality is due to (s) 2 (s, The second inequality follows by induction
(s)). condition that I (s) 2 Vi+1(6, (s) for all s. The last inequality is due Inq. 20 and Inq. 22 in
Lemma
E.3 PROOF OF THEOREM 5
Now we are ready to prove Thm.
Proof. (Proof of Thm. 5
(sp.h) - 1/2t ($k,A)
<VanhSs,,N) V/a²t (s
= RA Th (8k,h)) ) + Pr V (s,()))))) + CB To.h
R(SKKK (8k.).) - PV h4t (SL,N. (k.(k)h)))
-VeAtI(9HN+1) V (8R,0+1) Re(s, (8,,))))))) R(s, (k, + CBa
+ +P (Vin+i - -Va+1) (Suyns TR,
(Ve,A+1 - Vitts) (su,n+1)
+ (Pr (P&-P) -P) Vi++1 (R.AA.)
+ PP -P) (VE,ttI (SR,A (s.())))))
The first inequality is due to optimism (e,n(K, V7 The first equality is due to Bellman equation for V/tT and VE,n-
For notation simplicity, we define
62 lx, (.. - R(s, ((,(aN
0% P (Ve.411 W111 (SRAATTA((RRE))) - (Vhn441 V (sn,441)
kkh (Px= -PP) IP)
Firstly we focus on the upper bound of (Pa, - PP) (Ve,tiI-iise (on,h (88,))))))) We bound
this term following the idea of Azar al. (017).
(Px- - P) (Ven+1-- - -Vitt) (Sk,A.
7
7
< 2 (P, P.). II
Py (Vennt1Viitt) - (sk ax.1)
1=1
H -P.) (11(8,,,, (x. ((P))))))))) (-I(s,,, 1123/1))
1=1
j=1
P. P
LP
12
Σ
II
P. (VR,4t1- Victs) (sk.);0)h))
NR- ((+, (Z,")
3N ((5 ()((")
J=1,44
3N, ((8, ()(T ) (V
4
Σ
(V
3N
(
a
n
|
II Py (VeAt1 - Vittt) (sk,n, (B,h) +
(1, a) (2(T)
1N,
j=1,
\ 4|S,ILP
4|S
4|S,ILP
3Σ
+
(1
((-1((s,))2F)))
+ 3N (N,=I((sa))(2))
(==1((s.a)\22)))
+
(N.-,((..))2,7)
19

---

Published as a conference paper at ICLR 2021
The first inequality is due to Lemma E.1 The second inequality is because of Lemma D.I and the last inequality is due to the fact that V1,A+1
Vi++1
S H.
For each E [nd]. we consider those s'[o satisfying Na-1 ((s, a) [2 2n2 and N a) ( (
(x,))) 2
I 2n TT separately.
ax,)) 2 H² the first term can be For those s'[i] satisfying N Ni-1((s..) bounded by
P(("(1)12(2?")) ((.
Σ
Σ
II P, (VeNt1 - Vi+1) (KE,) j=1,iii
LP P ((er
Σ P,(s(1|)((Z!1)
II Py (Vant1 Vitti) (sKn akc)) jm jm1.i
(Ve.At11 - Viita) (Su,b, (k.b.
H (VE,++1 - Vieta) (su,041,
+ H (P (Van-t - Vo+1) (SK,A, ap.) (VAn+1 - Vieti (sk (x,+1))
where the second term can be regarded as a martingale difference sequence, and we denote as 81
k.h'
For those s'[i] satisfying Na-1((s, a) a) (ft an, s 2n² the summation can be bounded by
N ((s,)))
For notation simplicity, we define 2 as:
4SS.LPP +
4|S./PP
) (N=-1(s,.0)2,"))
4|S,|LP +
4|S,
L H
3N,-1(s..))2,'1)
2nH I.P
N (ZF1)
To sum up, by the above analysis, we prove that
(PA. P) (Ve,A41-12 - -v ((.L (Ves+1 Vioni) (s,,4+1,08,444)) +5
6k + Sh.n
Now we are ready to summarize all the terms in the regret. Firstly, we recursively calculate the regret for all h E [H].
(Sk.1 1k.1) ViTh (Sk.1, .x.1) Va ( ak.1) V (st.1.
1
SCB(sI,1, (n.)) + 1/,1 + 82, 82,1 tt.1 8h. (1 + H (V,.2 - (88,2, (k.2))
h-1 H
1 +
(CBB(Bh, + o + 62, + 5h + 8t,n + -
#=1
H
(CBa(sh, an) + t -6, + +22, + 5h, + (
l=1
20

---

Published as a conference paper at ICLR 2021
Then sum up the regret over & episodes,
Reg(K)
(V1 (s,,
K
H
e (C, + ot + 8h.4 + Sh + 8h + 62,,)
k=1k=1
Re and R. can be regarded martingale difference sequence, the summation of which can be bounded by O (TggT)))( by Lemma E.2 while 6h,n, and 62, can also be bounded by Lemma E.2 The summation of different terms in 6 k. 8% k. o and of be separated into the following categories. In the following proof, we use C' to denote the dependence of other pa- rameters except the counters N& ((5,,,, (z,))
For those terms of the form /aallennnmhN have
Nx(x
ΣΣ
C
SHC+ +
Σ
Σ
C
Vc
=|Zijex(Zz]
=HC +
Σ
CVNx(T[()))
SHC + C' CVZZIII
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 Ne((on.a:E,,))2))) we have
C
Nx((12211)
C
ΣΣ Mu((SH,)O4AA)
SHC+ E
Σ
SHC+
Σ
Cln (Nx (x(Z,))
<HC + C| In?,
which has only logarithmic dependence on T.
For those terms of the form (N, [Z:]) ((
define
No ((s, a)(2g] (z,y)) as the number of times that agent has encountered (s.a)[Z,
and (s, a) [Z,] simultaneously for the first k episodes. It is not hard to find that
(* a) Z+)) 2 NN((s, a) (s, a)]) and Na((s, a)(s)) 2 (s,
C
ΣΣ
Ne((SK, OK
N (4))
C
ΣΣ
Na((sn,n, On (z)),
<HC +
Σ
C'n ((,N (Sk.h. a4.h) (2,))
<HC + C|XIZ, UIIZ,ZZZ]11 In
which also has only logarithmic dependence on T. For other terms with the form of summation of these terms has no dependence on T, which negligible since is the dominant factor.
(1.. and Na [Z.l) a... the
21

---

Published as a conference paper at ICLR 2021
By bounding these different kinds of terms with the above methods, finally show that
/ m
Reg(K) (K) o
+ Σ
m
j=1
Here O hides the lower-order factors w.r.t T.
F PROOF OF THEOREM 2
F.1 ESTIMATION ERROR DECOMPOSITION
Lemma F.1. Under event A1 and A2, we have
20 (s,
8L
(s a) -((ssaa))))))) a)) <
+
(b_1((,a)\(z
3 a(
1(12 (s,
209 (V (
2HL
((, ()(
3N 3N ( 1) (2!7)
(V (o.
4/8.ILP
4|8:|LP
(V NN- (),5))
1|S
+ 4|S
+
((s
((x=)((s,))(2"")
Proof. The first inequality follows directly by the definition that R(s,a) 1 E R&(s,a) a) and
Lemma D.2
We now prove the second inequality. By Lemma E.1
we have
|(Px P)V (s,
(PA, P.))
II
P,
(s,))
+
H (PES- -P: P.) (1((, ((((1)
( -P;) (1((s (1ff1)
14 +
By Inq. in Lemma D.I and Inq.
Lemma D.2, we have
|(P
VIV (8, a)l
20 (Vi+i 8, LP
2HL
N () + ((3 a (2."))
(V (
+ 4 a)(2(T)
) (v
4
Σ Σ 1=1 fドij=1
( [2(1]]]
(N,,1((..)(2,1))
F.2 OMITTED PROOF IN SECTION 4.2
Proof. (Proof of Theorem.
(s)
=E (J 2 8/ = 8]
Σ P[ (Jh+1: + Th (i(())) ss, =, sy
Σ P(s'|s)E ( + 1/2 (sa)) (SN) 8t s, 8h+1 = ss]
Σ
V(()))) (3 8,41 =
22

---

Published as a conference paper at ICLR 2021
Given 8h 8,8441 5', The Vh((h) and ($ conditionally independent, thus have
(S (sh)) 8/ 8,8 = ==
8h 8, 8h+1 = =
((2)) Sh = 8, s' =2VV)+(())++))(())) sh 8, =s'
Therefore, we have ())(s)
P(s (
+ (sn) 8h= = 5, = =]
[E [2R(s:) (s((s))) (8 |sh s,4t11 = =s]
8A = Σ P( (s [R+tH (Va(sn) - R(sa))) 8h -8, =5] =B [r R
-E
rr 12
(st)))
8h =s| Σ
P(5'|s) J (h+I:( Σ ((o")s)Vn+1(("))
8% 5, sh+1 5s
[rh (s(s)) sn =s] =]+ Σ P(s ((s) ( [((s"ss)hh+111")) )²
=E
8''
E( [J [J++ - V (86+1) 18h+1 = =6]
(23)
The second equality is due to the fact that V/((s R(s) + E. P(d'ss) For the factored rewards, since the rewards Th, are conditionally independent give s, we have
m
E 1r (sh) 8h s)
(s)
For the factored transition, decompose the variance in the following way:
Σ ((s))s)V2n111)> - Σ I(s"|s)Va
oz (s)
2 P2: (s" mnls))++1(5"))
Σ P(s))s)V2H1(1)) -
Σ [1)
Σ 5'[2:n]
EP(s' s) Σ *'I1
Pzn (s'(2 : (
Σ [2(2
I2 (s" nl]s) nl+ ([s'[L),, s ni]))
((2mm]
Here ([s'[L) s rı]] denotes the vector s" with [ replaced with s'[1]. By subtracting &.P.A. (s) for 2,..., the above way, we can show that
Σ P(sils) - Σ (Pss" (()s())) - ()) =
(24)
Plugging Eqn. 24 back to Eqn. 23 we have
n
m
wi((s) = Σ P( F(s')s)wh+1(s} (s')
Σ
2 p.
Σ
0 R (s),
m2
23

---

Published as a conference paper at ICLR 2021
Proof.
(Proof of Corollary 1.1
We can regard the MDP with given policy Markov chain. By
Theorem we have
(1) = Σ 1( T (8) + Σ o (V 8,
a)+
m Σ
o (8,
By recursively decomposing the variance until step H, we have:
n
m o. s, Σ Rn
wh((s)) Σ
wh(s, a)
Σ
h= (s.a)EX
Since (x1) E (J(JnN((s))) (o)) 8hh s) sion.
H²2 can immediately reach the conclu-
F.3 THE "GOOD" SET CONSTRUCTION
The construction of the "good" set similar with that in Dann et al. (217)) and Zanette Brunskill 2019), though we modify it to handle this more complicated factored setting. The idea 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 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 Lu. for factored transition PP is defined as:
L def
(112f)) e x(zz):
Σ 5 (z) 2 H log( + H
j<k
The following two Lemmas follow the same idea of Lemma 6 and Lemma 7 in Zanette & Brunskill 2019). Lemma F.2. Under event A₁ and A2. (s, l)!) Li we have
Ne((s, ((((x,))lzP)) 2
Σ
22 (8,
j<k
Proof. By Lemma D.2 we have
Na((s,a) 2 Σ
(()((s))) log(18nXfHH/)
jck
Since (s, ())F) E Tikk, we have
$ Ejet 22 (x) 2 Hlog(18nX H/8) H. That is.
(t((s,))(2;
>
1
Σ
(,)(s,
[2!)) H log(118 H/0)
2
jck
1
Σ ()((s,))(2?]) JKk
2
j<k
1
Σ
wy (ss, ((
4
Jkk
Lemma E.3. It holds that
K H
ΣΣ
Σ
2k. & &HHXP log(10nX,HH/)
k= A= (L)
24

---

Published as a conference paper at ICLR 2021
Proof. For those (s, (z,) Lk, have 1E 2H log (10 H/ That is,
(z)2((x) I H1/) + H 1
K
H
Σ
(x,,, (s.a)[Z?)
Σ 8H 1og(0 < 8HX," log(LOnX; H/0)
1= h=1 (s.))
Lemma F.2 shows that we can lower bound the visiting count of certain (s, [2.) if the visiting probability of (s, [2," is sufficient large. Lemma F.3 shows that those (s, [s.a) with little visiting probability cause little contribution to the final regret.
Lemma F.4.
Wk,h.27(,,00 (s.0) a(((5)))(2;")
ΣΣ
Σ
54 log
h=1 (Ea))
Proof. For those (s,a) E LR we have Na((s, [z( $ Ejen (s,2) Therefore, have
K H
WK.A.zF(s.a) oz((s
K
H
2w (s,
E
Ejer 2/ (8,
Rml Famm
Rm hm ?
W W (8 Σ
Σ
jeck w 2z (8,
<4X; logT
Lemma F.5. For factored set Z of transitiion, we have:
H
())
Σ
S8X, log T
(25)
(o-1((s,a)(277)
(s.a)EX
K
(k,
1=l (ea)EX v ((= <8X log
(26)
wk.n(s,
k= h=1 (R.)e (N-1((0, (N= X8 log
(27)
where = = ||| uz
For factored set Z of rewards, similarly we have:
ΣΣ Σ (s,n
K H
<8X," logT
(28)
k= (e,a)EX No-
K
(8,
<8X. log T
(29)
k= h= (s.a)eX' v ) ()-
H
W (s,)
(x.a)x NN (N S8 T2/4 log
(30)
Jr 1 1=1
where = UZ
25

---

Published as a conference paper at ICLR 2021
Proof. We only prove the inequalities for the factored set of transition. The inequalities for the factored set rewards can be proved the same manner.
For Inq.
{- x x|Z!"] (s, a) (2,)), then have 25 define (i((s,))
K
()))(s,))
Σ
Σ
(
(s
2k (s, a) Σ (1.o))EX "',.
(s
=E
Σ
N Nx-1((s,a) (z.))
k (f
WK,,,zP(s,a)
E
Σ
N (8- (2.1)
R (=a)2[]ER2121)
W Wk (s,
W Wk.n,zP(ssa)
Σ
Σ
Σ E
Nk-1((S, (s)
Nx-1((s.0)(2f)))
(s,a] (zf)E.t)
R, (sa))z(()EE).t
Σ Σ
W (s,
Σ
E
2kA..P((,0))
E
E k.h &
1 N a2(2
N (A-1((s
k. (s.a)
k.h (s.o)
<4x;" log T + (oHX|)oo[1O0XXHH//0
<8X? log T
In the first equality, firstly categorize (s, a) based their value as, and sum up all possible choice of (s, a) [Z,". then we sum up the value in each category in the inner summation. (s1.a))))))
The second equality is due to E(s ((xx
"M..2. 1. The first inequality due to
Cauchy-Schwarz inequality. The second inequality is due to Lemma and Lemma
F33 The last
inequality is due to the assumption that X 2 (g(10n((HH/))
For Inq. and Inq. 27 define Z 7 U Zf. For the factored set Z., similarly have
K
Wk.,, zP,, (s,a)
<4XP, P
logT
Na((s, a) (2P)))
i.j
km
A
K
Σ
WKM,Y, (8,0) S8HX, 1g H/0),
k= (s,0)22
By the definition of Ziz. we know that Ne-1((s, Nk-1((s, a)( 2 N2 N ()))) Therefore, we have
(o.1((s,a)(255)) and
(s,)
Σ (s,)
Nk-1((s,, a) (2?"))
(s,))X V a)). ((s,,))))
(s.)ex
ΣΣΣ
K #
(s,nssa)
wk (s. a)
k= (s,a)EX VNL-i((, (.'') (Na-1((s, (Z)7))
(Na-1((s, a) (?())
(s,a)eX
The following proof of Inq. and Inq. 27 shares the same idea of the proof of Inq. 25
F,4 TECHNICAL LEMMAS ABOUT VARIANCE
In this subsection, we prove several technical lemmas about variance. For notation simplicity, we use E, and Ejsy as a shorthand of (=(s,)=)(((((),))1))))) and PEsses]) (-I(s,)) ((.))) Similarly, we
26

---

Published as a conference paper at ICLR 2021
use V, and Visj shorthand of V "*(((] ((Iia and
For those w.r.
the empirical transition PR., we use E& and V& to denote the corresponding expectation and variance. For example, E (5) ((ee.))22) is denoted as Ex.;-
Lemma F.6. Under event A1, A2, we have:
|S Na- ((s,))
4|S 3Nx=1((s. a) a)12,())
(V, (V, S 4
Σ
2V
where V denotes some given function mapping from to R.
Proof.
[6P,,, (V,
-10 V V 1 [+1] V(s) B V, ++1:]| V(s))
(31)
< [ 1) V, (++ (1+1ms) 1mm] V(s' Eq---1) V. ((s))
(32)
+ 18 p V B. V(s') 1) V(s')
(33)
We bound Equ. 32 and 33 separately.
For equ.
32 we have
B1 ++1ml
( V(s') - B V:B
M1- [15-111111 (Pus-11) - P(aa-11) (s'(1 i []|s, als,,)) s+1m V(s')
Σ
P (sss a) - P -P
Py(-|s,a) -
SS
<H²
2
(34)
N [2,,))
3
The last inequality is due to Lemma D.I
For equ.
33 given fixed s'[1 i 1], we have
"iBeetin/V(8 (55) V. V(s)) < B. (('))))(('') " E, ((+))))(()'))
+ (('))2 (())) (RRmm 2
B. (Witt V E, (#R+1m V(s')) 2
E. (Bet1an) V('')) E, (B ((s))²
(1e V(s'))== (10 (Dirn v(6)))
< E. ( E, (1p4zm ((('))²
(35)
+ E. (B (B(t)om((66)) - E, (E i+ 1:m| V(s'))
(36)
+ 2H Vs')) -
E Ejom V(s')
(37)
27

---

Published as a conference paper at ICLR 2021
The first inequality is due to the definition of variance. The last inequality is due to B(nn)((s) + [(em) V(s') - 2H.
All Equ. 35| 36 and 37 can be bounded with the same manner of Equ. 32 That is, first bound each term with the L1 -diitancce of transition probability multiplying the L -oom of the value function,
then upper bound the L distance by Lemma D.I This leads the following results:
|S
4|S,LLP
V. 1m ((5) v,B V(s')
<4H²
2V
N N ())))))
3N&-1((6 ((s.1(())))
This bound doesn't depend on the given fixed s' : 1----11 1]. By taking expectation over s'll : i 1] ~ P1--11 (-1,, a), we have
B[1--1] (. V(s)
V.E im V(s')
SS
4
E. [ (itt)) E, 1m v(s')2
4H2
2
+ 3N (N,
(1,1(((,a)(25)))
Combining with Equ. 34 we have
S
4|5
(V, (V, S 4H?
2
N ((,
3(xx
Lemma F.7. Under event Mr A2 and Q2 we have
P.. (Viti: - 26 i W.h41. S (s, 4H2 Σ (2 2 (e-1((,,a1227))
L
4|5
3N8-1((8,
where (s,,,((s,)) ) is defined in Section
4.3
(H Bettttm Bat Vatt+1 k1b+1) (s))
(s, E / (.s.a)
Proof. We can decompose the difference in the following way:
o. 8, a) 2. 8, Sop (Vi+ a) - -00 k, + (V s, - PP
By Lemma F.6 we know that
SS,LP
4S
4
2
Nk-1((s, (x_1((s,a)125))) 3N (ssaas](()) I)
Now we only need to bound 2017). we know that for two random variables E R and E IR, we have
s, 209 C...R..VV.. (V k, 8, a). By Lemma 2 of Azar et al.
V(X) < 2 + -(X-Y)
(38)
That is,
P.k. (Vi 8, a) 200 P. (V 5,4+1,5,a)
-EI (. [m] (s') 28 111 V. lmm VENt2(S))
22E -1 -1 V. [1 Vi+ (s') - -B 1mn| V VHint((s'))
-2 (. (Viti (8') - VA.++((8))
220 (Mittzm) (V"+ - (H,K+I(s)))
(s,0)
28

---

Published as a conference paper at ICLR 2021
The first inequality is due to Inq. 38 and the second inequality is due to VX < EX² for any random variable X R.
To sum up. have
Σ 2 S
4|5
CP -5 (VP..i(ENNt....0 S (k.A,((saa) + 8H²
(6_ 3Nk-1((s, ())(s),))2])
Lemma E.8. Under event A1, A2 and Q suppose Reg(K) = Ek=n (s1) 11"h (s1), (s)), we have:
K
H
ΣΣ
Σ
(o - - 2H
h=1 (x.a)xx
K H
ΣΣ Σ
u (VRA+1,, (V a)) S 2H
k= (8.0)xX'
Proof. We only prove the first inequality in detail. By replacing V with V k, we can prove the second inequality in the same manner.
(V a. o²: h-1 (V a) E [V. (Ep+ tm] ( V. (E [++ V (s'))
Given fixed 8'[1 1}, we bound the difference of the variances: V, (B(+1m)) ( V; (B]+ W (s')).
V. (B b+1 (s')) V. (B(+ V (s')
-E, (Be+)m)) h4 (5')) (E(+1m) h+1 (5'))
E [im]
[Vh+ (s'1))
(Em
[V (s))2
<E.
(Bi+imm) h/1 (s'))² (E Wi (b'))²]
<2HE, [B1+I=m] Vitti 1pt (141(s')
[2HB ( - (s']
The first inequality is due to (8') 2 (64),''), and the second inequality is due to
Ej++im] Vitti (8') + E V (s') < 2H.
We then take expectation over all s'11 :1 1). that is
oV - (V ( a) < 2 (Vi+i(s') h4t1 (8')
Plugging the inequality into the former equation, we have
K
H
Σ
(s,n(8, (07, (Vi+))8))))) of h+1. 8, a))
1=
(s,))x
K
Σ
Wk,n a)2HH, [Vi+z(5') - ViT (s')]
1= (s,)Ex
H
2w W ())((V((()) (s)
km
2
2112 (1))
K
<
Σ
2H [v,1($)) - ())(
1=1
Reg(K
29

---

Published as a conference paper at ICLR 2021
For the second inequality, this is because that by lemma E.15 Dann al. (2017), have
Σ wk (s) V/ (s)]
Σ h1=h
Σ
Wkite (s) (R(s) - (x()) + PV, +1 PV,, (1,
H
= (s))
Σ
Σ
whih (s) (R(s, R(s, (x(s)) + PV
(s, 1 PV, 7s
h1=1
This means that E, Wk, (V) VI (s)) & (s - V for any k,
F.5 OPTIMISM AND PESSIMISM
Lemma F.9. Suppose that At, A2 and I41,441 happen, then we have the following inequalities hold for any E A and s S:
1
aRss,))-R( - -R(sa)
$
(B
(39)
m
t=1
(s - (s.4)
(B,(ss
(40)
Proof. The first inequality follows directly by Lemma F1 and the definition of (s, a). For the second inequality, by Lemma F1 have
PPx P)
Vh+ (s,))
207, p.s (V, 1 8, T.P
2HLP
+
Na-1((s, a) (2.1))
3Nx-i((s,a) a)
Ho,,(s,, (s),,
jæi
where (8,)()
LS
18,
The first inequality is due to V.,((s) 2
(e-i((sa)
((x.0(=))))
xs,
By the definition of CB, we have
E CB. - (fe+ -P) (s,
(41)
A67 (V 1,,,t1,8,00 8PP
207 & LP (2-1((8,a) (2P))
(42)
N (
:
n
n a8 N ((_,(()))
16H21.P
" Σ
4|8
4|S
N ((,,
((,
+
(s,
j=l
(43)
30

---

Published as a conference paper at ICLR 2021
We mainly focus the bound of Equ 42
46
P.k.I (V 8,
p (V
1+1. 8,
(44)
N 1 1)l2,()
(x-1((s,a)
20 VV 11. -4 (V
20 (V
(V 8,
otherwise
(45)
For those 209 P.k. (V k, S Spp, (V 8, a), by Lemma F.7 we have
(V+ -2 1,
S,
4|S,|L"
(u + +
2
+ (N,
N a()
(2ff1)
That is.
462 (V kAb+1 &, T.P PIR.i
20 s,
NR. (1, (7("1)
Nk-1((88 a² (Z,"))
(L) +1GHLPP
Ej= 1 No ((saa) + 3Nd (2F)))
18,1E
11
Na-i((8, [2,"1)
(s,
16H2LP
4|S/'L"
4
N N==1((s,4)22)))
NR-1((8, ((= j=1
(2,p)
3N (8,
Combining with Eq. 41 we prove that
Pa (s, (s.4) s Σ (s
The optimism is proved by induction.
Lemma F.10. (Optimism) Suppose that A1, A2 and D4,h+1 happen, then have k. Vi
Proof.
Va.(s) - (s)
=CBa(s, 7" (s)) + P. n, P.V (s)) - PV (8, (8)) + (s,
x (s)) (s,
2CBss x5 (s)) + (ipx - IP) Vitr (s)) + (s *s)) - Rs n (s))
20
The first inequality is due to induction condition that 2 happens. The last inequality is due to Lemma F9
Lemma F.11. (Pessimism) Suppose that A1, A2 and 2g,441 happen, then have bn Vy.
31

---

Published as a conference paper at ICLR 2021
Proof.
(s,)(s)
TR, CB&((, + (2.
<R(s,, TR, (8)) - CBa(s, + (8,
-R(s, TEA (s, (x,
A(s, ((s,
1 m Σ (s.
(s, PV (s,())) Σ CB. (s, (o,
The inequality is due (x) (s') since event S4a,+ happens.
By lemma
F9
we have
1
R(ss, (+))
CB (s, (s))
P To,(())
PViti (s.TH.
Σ
CB, (s, (s))
Therefore, we have
Vun (s)) < RRs,, (s)(s)) + PV, (s,
<R(s, (s)) + (s,
(s,
Lemma F.12. (Optimism and pessimism) Under event An and A2, we have Dk.h holds for all k and h.
By Lemma F.10 Lemmal F.11 Lemma.
Proof.
through induction over all possible k, h, we can prove the
F.6 PROOF OF THEOREM 2
Proof. We decompose Reg K) Reg(K)
(SK.L, VTTh (sk, (x,1)) in the classical way Azar al. 2017 Zanette & Brunskill, 2019 Dann et al., 2019), that
K
K
VRI(S1)= - 1iTh (si))
(46)
Σ Wk.n(Sh, C.)CBBessn.
(47)
k. Shaan
Σ Σ
Wkin and (ixx -P)- PP) Vittissh. an)
(48)
Wk,n (Sh, an) (f&x -P) (Va,tti - Viūi) (s) an)
(49)
k.h 8a.th
Σ
Wk. (sh, an)
[ua an) A(sn, an)
(50)
k. 6% Rh
32

---

Published as a conference paper at ICLR 2021
We bound Equ. 47
48
49 and 50 separately by Lemma F.I3 Lemma F.14
Lemma
F.15
and
Lemma F.16 Combining the results of these Lemmas, we have
1
Reg(K) K) - Ci m
x ( log T + Cz
Σ HTX!"L log + Cs
nHoReg( K)
X."
I
log
(51)
Here C1, C2 C3 denote some constants. Solving the (eg(() in Inq 51 show that
m
Reg(K) So
X.TLR log T
Σ HTX, log
m
where O hides the lower order terms w.r.I.
By the optimism principle (Lemma F.12 we have (1 0k,1) S (KK, This leads to the final result:
m
(V (5R,1, ax.1) V (SKL ax.1)) 50
x l
Σ
HTX L logT
m
F.7 BOUNDING THE MAIN TERMS
Lemma F.13. Under event A1, A2 and Sa, suppose Reg(K) = Ek VR.((1) - (s1), we
have
K
H
(s, ())
1= k=
n
<0
TXRL log
HT Σ XPL log T + HrRRogK)) Σ x²" log T
m
Proof. By the definition of CB&(s, a), we have
Σ (8, (x k.h.aaa
(52)
Σ k.h,aaa
(s))
1 (B + > CBL,(s
(53)
m
(K,n( ,,,,
Σ
1
282 20 n.K. (8, T.
&E 4 (V (
(54)
No- ((s,(((())) [2,11]
No N ((s,))
m
8T,R
+ Σ
Wkih
(55)
3N (18, a) (2.71)
m
k.h.8.0
114
16
1|S
4|5, LP
+
Σ
(k,n(s,a)
Σ
(N-((())))(2)))
(s)
3N (s, (2(2
k,h,3,0
(56)
36H S,
+ Σ
Wk (s,
(57)
k,h,s,a
1=1 j=i
2u,.n,
+ Σ
(s,) Σ
(58)
Nk-1((8,
k.h.s.a
33

---

Published as a conference paper at ICLR 2021
By Lemma F.5 the upper bound of Eqn. 55
56 and 57
( ). which doesn't contribute to the
main factor in the regret. We prove the upper bound of Eqn. 54 and Equ. 58 in detail.
By Lemma F.6 we have
L N Nx-1((8,
L L'
(, o.p o
s 411²
Σ j=1
21
Then Eqn. 54 can be bounded as
2 R L.
P., (V k14+,, 8, LP
NR-1 ((s, a1) (2,7))
NA-1 ((8, a) (2,7)
R (s, L)
20 ( S,
Na-1((s, (2,1))
NA-1((s, () 1(.1)
(107,, (VV. K, 8,0) - o (V.,,VVVV,,, (VR,,,,,, a
N (z)
26 (8, L. Na-I((s,a) (Z
(59)
171
40 k,,,,, 8, T.P ((_1((8,a)(2{)
(60)
1S (M
LP
4|S
+ 8H
N ((s, a) (ZP1)
3N ((x
(61)
Similar with Eqn. 61 Eqn. 59
the summation of Eqn.
61 is upper bounded by O(TL/A) by Lemma
F55 For
we have
20 20 R. (s, (s)
ΣΣ A.
(s.
Nk ((s, (s,aa)()())) (2(")
2L
Nk (s)
k.
102
2w n (s, L NR- ((s, (111)
(s,
ΣΣ
m
102
2wk (s, (s, L.
m
No_1((s, I)
k.h
The first inequality is due to 02 (8, inequality. By Lemma ESS
a) < The second inequality is due to Cauchy-Schwer the summation can be bounded by m Em / V R.RI.TTON T.
34

---

Published as a conference paper at ICLR 2021
For Eqn. 60
we have
20 (V k, L)L
ΣΣ
(s,(
N a2,,))
R,A 8,0
1=1
72
4LP
Σ (H, ④) k.h.s,a
Σ
p (V (,,+1,8,,))
Σ (s,n(s,a)
N ((s, a)l2;")
k,h.s,a
Σ (8,n(8,0) a)
Σ
p.
Σ 4x EXPLPM log
k.h.s.o
i=1
Σ Wn, a)
P. Σ
(V
h+1: 1,118,00,
Σ
4XPLP log
k,h.s.a
:=1
1=1
Σ (8,n(s, a k,b,s,a
(V (V,,h+,,8)))
(v 1 (+11180a)
4X log
2 Σ Wh,n a)
12
n
(V
Σ AXPLP +
2112nReg(K)
x P log T
m
Σ (K,n(s,a) k,h.s.a
R. ( a) Σ
(V s,)))
4xPL LP log
2H²nReg(K)
Σ
X.P L" log
m
1=1
i=1
SVHT.
Σ
4x. L log T+
2HenReg (K)
Σ
x XPIP log
The first inequality is due Cauchy-Schwarn Schwarz inequality. The second inequality is due Lemma
The third inequality is due to Lemma F.8 The forth inequality is due to o R a) 2 0, and the last inequality is because of Corollary
For Eqn. 58 have
28,, N (4-1((,a))Z(11)
Σ k,h,,.a
Wkin
Awre (s,
2TP
Σ
Σ k.h,s,a
(s,
N ( a()
k.his,
n
64XPI,Plog log
Σ
(kA(s,
(62)
k.h.o,a
By Lemma F.20 we know that the summation Ekh,,, Wh,n a) a(up,,,(s,,)) is of order O(T²) )
This means that Equ. 62 of order O) which doesn't it contribute to main term (O(VT)).
35

---

Published as a conference paper at ICLR 2021
Lemma E.14. Under event A1, Ag and 92, suppose Reg(K) Ex= (k,1 -VT (51). we have
k H
(K,((s, (Px (Pa PP (*,
k= ==1h=1 (s.a)EX
( (1IHT + inH (R))(K))
00
EXPL"
i=1
Proof. By Lemma F.T we have
Σ
(K,n (Pa- (s)
k= (s,a)ex
20 20 (V h+1, S.P
Σ Wan(B,a)
Nx-1((s,a) 12,1)
i=1 (s,a)xX
36H|)
Σ
(k,n(s,a)
Σ
al))))
k
(s,a)XX
jøij=1
By Lemma F.5 the second term has only logarithmic dependence on T, which is negligible com- pared with the main factor. We mainly focus on the first term.
(V* 1 L 20
Σ a
Nx-1((S,, 12,
h 1=1 (8.0)EX'
Wannss, a)L Ne-1((s, क (z)))
2wh,
o3 (V. (Vit:1)))))) Σ
Σ
d (s.))xX
h.h (s,a)EX'
Σ Σ
(s,
1
2
R. (s, +
(V Lp (1)+
Σ E ok.n(s,0)LP
h2 (a,0)EX i=1 (e-1((s,775))22)
h. (#.a)E
1=1
HT + +HHlReg(())
Σ XPLP T
The first inequality due to Cauchy-Schwarz Schwarz inequality. The second inequality is due to &R,,((s, a) 2 0. For the last incquality, 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 Σ, E,PLL' L log T by Lemma F5
Lemma F.15. Under event A,, A2 and Qt suppose Reg(K) Ek VR.( ViT* (s1). we have
K H
Σ
(s,n(s, (Px (PP)
1P) (VK,+H) (aaat--Vinnl (s, (s, 50 H Σ TX SXL Σ 2x8X"L' "
k= k=1k=1 (s,a)eX
36

---

Published as a conference paper at ICLR 2021
Proof. By Lemma E.1 can prove that
(px - 1P) (V vi++) ())
(PAii P.) 11 (V (Sknn V/ ask.. acch))
1=1
n
(Pr.: .P.) (-1(s, ((((s)))/211)] (Pr. -P,)
PP)) ()(s)))12f)))
== 1=
P(("
2
Σ
Pna-ipPRttnn (VEn(SR,A)) ak,h) (st,h,
N ((,, a (2,"))
(LP))
36H
3N 3N,=1(ss,a12?7)
V NN ,
E=
The second inequality is due to Lemma
D.I
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.
a) (z)1)) Ne-1((s,
ΣΣ k,
(s,
Σ
Pi-s-11Pu4tm (VL. (sk.h,
e'ijess,
P((*(0)(((5)) (P141m) (VE, - (sk,,,
(aa(ssa)PPI:E
2
Nk- ((s,a)))))))))
R.
*'iEs.
P(o((](e.,)2Z/111 (Pp+im (VR,L (k.A.) Ve, ax,))))
P Pl-i-1
Σ (s
2
Σ
N ( a) [2,"])
Y=1
k,h
8,0
*'ijes
S [:s] (B (Va.(ss') V (s1))
(K, a) 2
N ()(2))
k.h 8,a
(s,)(s,a)
Σ
Σ
(s, (B(+41m) (Vx,hti(s') Ve (s')))
(o-
A.hi,,a
k,b,a,a
2 8X EXPPLPlog T
H²
TXPIS,ILP
The first inequality is due to the fact that VA, Vg > V. The second and the third incquality is due to Cauchy-Schware inequality. The last incquality is because of Lemma F.3 and Lemma F.20
Lemma F.16. Under event Ar, A2 and Q, we have
m Σ
Σ Σ (a.n an) (Re(sn) an) - R(sn, an)) 50
TX Tx R
L
m
ki Sh.as
37

---

Published as a conference paper at ICLR 2021
Proof. By Lemma F.I
we have
Σ E (snn(sn,an) an)
(Ra(ons an) R(sk, (n))
(V
2ō 2 an)
WR,n (on, an)
+
m k, $t:4k
Nx-1((sh, an) (z,")
3N an 12
(v N an) (2,")
2L
8L
Σ
WR.n (8h, an)
as)
3Ng-1((9h: an) (2:4))
m
k Su:
E k Ees.a on (sp, L
8
ΣΣΣ
Wk,n an)
NA- ((sh, an 12,11)
m
3N ((sh, an [2,
1=1 k.h Sh
The second inequality is due to (8, a) s 1. The last inequality is due to Cauchy-Schwarz inequality, By Lemma E.5 we know that the summation is of order
1 E
VTX log T
Lemma F.17. Under event A1 and A2, we have
2H log 1og(
k. VU.N (8) S Etrajn Σ
2C,
Σ
1 88h 8, 7kk
N N Th. ((.
The expectation is over all possible trajectories episode is given 8n = 8 following policy Tk-
Proof.
(V VENN (s) 22BB (., ()) + (P.(Ve.ti())
[x)+i(())
(C + (P&- - (V[VnA+ - (E, + AA11 - ((,
H
=Eeraje
Σ
(x.()) + (P&x P) - (x sh = 3,
The second term can be bounded
(p. 8
(V kit+1 V2,i41 (8)))
P2
V k.i+1
Ve, (s)
<H
Pk, - P312(-182, (..
1=1
2H²LP
N V8-1((8, (s))(()
Lemma F.18.
Under event A and A2, we have
K ΣΣ Σ
Wk.n (B
k= A= (s,)ex
m 2(m + 2) log T
n (28n(m+n))H33
n
> |S 1 log T,
m
Which has only logarithmicc dependence T.
38

---

Published as a conference paper at ICLR 2021
Note that this bound is loose w.r.t parameters such as H, |,, and X, However, is acceptable since we regard T as the dominant parameter. This bound doesn't 't influence the dominant factor in the final regret.
Proof. By the definition of CB)(ss Cs, and CB, a), we have
CB a) 5(m + +n)
Σ
CB (s, a))² + (B.L,
m
m
2H
6A(L,t)2
<2(m + n)
m
N (x_)(())))(
1 a) (2!1))²
1
N ( ( )
2HIPP
4m(m + m))
N ((s,)(())))))) |
4|S
4|S
+n(mm + n))
((s,0(( (2.))
V
(()
((3
The second inequality is due to o (s, a) s 11 1, (K 2 and (s, S H. Now we are ready to bound Σ E ((.jEr a
K
H
Σ
mgn(s,a)CB3(ssd
(s,a)Ex
H
2(m + 2)H
" 128n(m + n) H2 ΣØ= TSP
(s,n
m N²N (2
N N a) (zP))
(s,a)EX
2(m + 2)
X.F
log?
+
128n(m + xn)H2 x
S P logT
m²
The last inequality is due to Lemma
F5
Lemma F.19. Under event A and A2, have
K H1
ΣΣ Σ
Wk,n(s, Beess (Bejitam)-P (Va,h+1 - VENTT) (8))² < O(log T),
k=1
(s,a)xX
Here O hides the dependence on other parameters such as H. X. except T.
Proof. For notation simplicity, we use E, and E(ey] as a shorthand of E=10)-(((().0))2))) and
E [ (ss.a))
Σ as, (Bit+100) (VR,t+I (n.411) (s))²) k.h.s,a
Σ k.h.,,a
(VR,411 Lenti) (s,
Σ
wknh (8, B[
(Ve,t41 V* (s)
K H
wk.b+i(s,a) (V Kan+i) (s) (s,
1= 8.0
39

---

Published as a conference paper at ICLR 2021
Define Us(s, o) 2CCB(s))) Ei=1 V
((,a(()a))2 By Lemma F.17 we have
2HPLP
K H
Wk.h+1 (VK,++I v1 (s.a)
Rm 5.a
H
Σ
(KA+2((,a))
Σ
Σ
Pr(sh100h1 1sht1 = 5, ax+1 a)Ux anr)
k,,,
A1=b+1 Bhg 10h
Σ
WK,At1(s,aHH
Σ
Σ
Pr(sh, ah, 1sh11 8, 8,04+1 a.)Uk (8h1 (Sh, ahh)
R,8,8,0
hu h1=h41
Σ
Σ
Σ
Pr(shi ah s8h+1 8, 3,0411 a)) (U2 ami ))
k,
1 Shy 19k1
Σ
E
Wheh (sh, anh) (Uk (Sh, ))
by hi=h+1 9hg 18s
wk.n an) (UA($): an))
(63)
k,h
Ph.Pk
Plugging the definition of Us(8, a) into Equ. 63 we have:
K
H
(k,4+1(8,a) (VR,t+I ( (s.
(64)
5;a
2
7
2H²1P
Σ
H2 Σ
(sh, 2CBB(s,
(65)
Nn-1((s,a)(27)
k
St, ag
2nH
Σ (sh.(a)aa)))
(BB(s,a)
n
2H
(66)
N N 1212,1))
Sh.ak
f=1
Σ 2nH
Σ WR. (sn, (n + 16mH 16 logT
(67)
k.h
The last inequality is due to Lemma F.5
We can bound Σn,b 2nH Es.,,, (k,b az CC
by Lemma F.18
Summing
up
all terms,
show that
ΣK E E.a Wk.h+i (V WR,++1
V V1,+112 (s, is of order O(1).
Lemma F.20. Under event A1 and A2, for any E [n],we have
K H
ΣΣ
Σ wk.k(s, ()) Σ /XF"S,,L))
s 2(H
1==1 11 (s.0)EX
Here O hides the lower order terms W.E.f. T.
Proof. For notation simplicity, we use E, and Biey as a shorthand of (()()))(((())))))))) and Ee ( alz")) For those expectation w.rt the empirical transition Pr., we use E, to de- note the corresponding expectation.
(k, a) is defined as:
(8, a) = B(uaa) (B) (V Ven+i) (6))²) 27
40

---

Published as a conference paper at ICLR 2021
(B(+tm)) (V V (Rt++1) (6') 27
Σ Wh,n 113] k,h,8.a
(68)
(BB441m0) (VRAII-VV 1- (s)) ?
WK,n(s, a) Ep:d]
(69)
k,h,8,a
+ (s, a) [aj
(B(ctTm) (VAN+1 - ((,+1) (s')
k,h,s,a
[11+1m)) (VR,t+1 vnn++i (8') )
Σ
(8, a)
(70)
k,b,
Σ
(8, ppa]
(Bitzaa) (VR,++1 - kb,++1) (81)
k.b,s,a
Σ k,b,,,a
(s, [1s]
(B(++1m) (V Wkt+1 E.,nti) (6)))
(71)
That is
We can bound Eqn. 70 and Eqn. 71 by Lemma D.1 For Eqn. 70 we have
Σ (k,n B) (Bittaml (V Ke,42)) (6')) k.h.s.o
(BietTon) (V - Vk.+ii (st) 27
(s, E
k.b,s,a
Σ k,h,8,a
(s,n P1s0 Pp:a((10,,)) a) 112
LS
Wkin a)
NR- ((, o)(2 1
k.h.8,a
<8H²
TXPISS log T
1=1
3 The first incquality due to [Bp+1ss) (VR.41 - ME.++) (s)) - H2 for any given s'[1 i]. The
second inequality is due Lemma D.I
The third inequality is due to Lemma E5
41

---

Published as a conference paper at ICLR 2021
For Equ.
71 similarly have
(Bi+tzaal (Vi,h+1 - (xn+t) { 2
Σ (n,n(s, Bp:i
k,,,
Σ
Wk, (s)
(B(441m) (VE,t+I (xn++1) (s'))²
k,h,e,o
<2H Σ
WKAh (s, [1a]] (B(t)lm) (VR,A+1 Ko,a+1) (6') - (B i+ [+1ml (V - Ka (5')
R,b,,,a
<2H Σ (8,
H [k4tm) (14tmm((1s,0
k,h,s,a
S,ILP
<2H²
WK,h (8)
Nk-1 ((s, 12
k.h,s,a
|S
=2H² Σ (s,a
Σ
Nu- (
k,h,s,a
f=++1
<16H²
j=++1
Eqn. 69 be bounded by Lemma F.19 which has only logarithmic dependence T.
G PROOF OF THEOREM
Proof. We consider the following two hard instances.
The first instance 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 22( / AD)A). When transformed to the hard instance for non-factored episodic MDP, it shows a lower bound of order ((VHSAAT) in episodic setting Azar et al. 20 Jin et al. 2018
Consider a factored MDP instance with d = m = n and x = X X; S x A,,
1,..., n. This factored MDP can be decomposed into independent factored MDPs. By simply setting these n. non-factored MDPs to be the construction used in Daksch et al. (2010), the regret for each MDP is 22( H (ZPPTT The total regret is 2( [ our setting, the reward R 1 m R₂ is [0, bo-ududded. Therefore, we need to normalize the reward function in the hard instance by factor of J. This leads to a final lower bound of order 21 E / H HH x[Z."] (T) = ( E / /H|xX2, (2,7)) Similar construction has been used to prove the lower bound for factored conlly-commuicaaiig MDP (Xu & Tewari 2020).
Note that in
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 ky arms in To steps is lower bounded by (KKkkT))). Consider a factored MDP instance with d = m n and x[2 functions, each associated with an independent deterministic transition. For reward function i, There log, ()S levels of states, which form binary tree of depth logz (Ss(()))). There are 2 states in level h, and thus |Sa| - states total. Only those states in level ((,,) have non-zero rewards, the number of which is [S,] After taking actions at state s' in level log, ()S)( [), the agent will transits back to state s' in level (og)((S.)). That is to say, the agent can enter "reward states" at least H - (IS,) 2 H times in one episodes. For each reward function i, the instance can be regarded
x|z,"] X. S; x Ar. = I...., n. There are independent reward
2
MAB problem |S.Ail arms running for KH steps] thus the regret for reward i is
KH steps, since in each episode the H agent will choose state s', and then stay in s' and choose different actions for 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 Szepesvári 2020
'The instance is not exactly MAB with [S,Ad] arms running for 2
42

---

Published as a conference paper at ICLR 2021
2 S.A. KH Q2 D(v In this construction, the total reward function can be regarded the average of independent reward functions of m stochastic MDP. This indicates that the lower bound is Ω
2
| a
[ x|Z?1| T)
To sum up. the regret is lower bounded by
|T v 1IX 1)
Ω max
which is the same order as
VIXIZFI1 + Σ H|x[2f111
Ω
H OMITTED DETAILS IN SECTION
5
H.1 SPECIFIC INSTANCES
4, =
$1
0.5
S3
6 = 0.5
0
auh
1
50
02, =
6,
4/
74 0.8
(0.5 w.p.
ag =
w.p. 0.5
W. P. 0.5
$2
54
0.5
0.5
S3
S5
Figure 1: MDP Instances, Budget Bo 0.5
We further explain the difference with specific examples in Fig. H. No matter which setting the previous work considers, the main idea of the algorithms in Efroni et al. (000);; Brantley et al. (2020) is explore the MDP environment, and then find a near-optimal policy satisfying that the expected cumulative cost less than constant vector Bp, i.c. E he c, < Bo. However, in our setting, the agent has to terminate the interaction once the total costs in this episode exceed budget B. Because this difference, their algorithm will converge to an sub-optimal policy with unbounded regret in our setting, In the first MDP instance (Fig. H.I), ,, the agent starts from state so- After taking action 01, it will transit to 81 with a deterministic cost ei 0.5. After taking action a2, it will transit to $2. The cost of taking d2 is 0 with prob, 0.5, and 1 with prob 0.5. There rewards state sp. In state $1 and 82, the agent will not suffer any costs. The deterministic rewards 0.5 and 0.8 respectively. 83 and 84 termination states. The budget Bo is 0.5. For this MDP instance, the optimal policy is to take action an in 8g, since the agent can receive total rewards 0.5 by taking 01. If taking action ag, the agent will terminate at state 82 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. 22000; Brantley al. (2020), the algorithm will converge the policy that always selects action d2 in since the expected cumulative cost of taking is 0.3 < Bo.
We further show that the policies defined the previous literature are not expressive enough in our setting. In the second instance, the agent starts in state with one action ag. By taking ap. the agent transits to 81 with no rewards. The cost of taking &g with prob. 0.5, and with prob 0.5. 81, the agent needs to decide to take a1 or a2, with deterministic costs of 0 and 0.5 respectively. After taking as the agent will transits to s2, in which it can obtain a reward r3 = 0.5. While by taking d2, the agent can transits to 83, and obtain reward = 1. The budget B 0.5. In this instance, the action taken $ı depends on the remaining budget of the agent. That to say, the policy is mapping from state action. Instead, need to define
not expressive enough if it is defined as mapping from both state and remaining budget to action. However, previous literature only considers policies the state space, which cannot deal with this problem.
43

---

Published as a conference paper at ICLR 2021
H.2 ALGORITHM AND REGRET
We denote V b) as the value function in state at horizon following policy म, and the agent's remaining budget is b. For notation simplicity, define (s, a) cols,a)V(s', - co). We use (c,,(ol to denote the "tran-
Eg Ec, (8 a)P(C(ss sition probability" of budget i, i.. a(C)(s,a) = cols, a). The Bellman Equation of our setting is written as:
(s. b) R(s ((s,,)(s, (P
{
b>0 0 b 25o
(72)
Suppose (s,s, a) denotes the number of times (s, a) has been encountered in the first k episodes. We estimate the mean value r(s, a), the transition matrix Fs and Pc in the following way:
Ra a) = Ex. 1[SKA 8, ak.h a) Tka
Nx-1(8,a)
Nx-1(8,0,88)
(s (s))) (x-1(8,0)
Po (Ci(s,a) = cu (lls,)) ER, [Ctgh.i = Co, 8k, = 0k,h = a)
Nx-1(s,0)
Following the definition in the factored MDP setting, we define the confidence bonus for rewards and transition respectively (for < i d):
20 (s, (s, (2g((AT
8 (og(A
(BB((,0)=1
(73)
(s,
3N (s,
(V
2uR 2uR,n,i ( b)L 1
CB, -V
(74)
(s,a(
32H²L
4nL
4nL
+ 3.Nx-1 (8,
(75)
Wi-1(8,,))
VV-1(8,,0)
(v
4/S.|LP
4|8
4|S
4|8,14
H
+
3N,
(e,
3NNx11(5,
(76)
where L = log (2d(SATT) + dllog(mB)) is the logarithmic factors because of union bounds. The additional d lm is because that we need take union bounds over all possible budget This difference compared with factored MDP is mainly due to the noised offset model.
CB a) is the confidence bonus for rewards, and Ōg(s. a) denotes the empirical variance of reward R(ss a), which is defined as:
R-1 H 1 = a)] (sk,,, -ap---(fRRa (Ra(s,.))
)n(ssa)= = (2-1(s, k=
CBL a) is the confidence bonus for state transition estimation Psss and (CBP, a))i= the confidence bonus for budget transition estimation (PPc,))=i...dd 07, (V k, a) is the empirical variance of corresponding transition:
(V 8, 8, Var Vary " (Fonecu((aa) VRati(s,bbo -)))
0 0% (,,,44,,,,.5b)
=B -B.-
Var Var Varorpeenaalenn E
FRetils, bc))]
44

---

Published as a conference paper at ICLR 2021
where F., I P.
V 2ug Aus.as No 1(,1( is added to compensate the error due to the difference between V441 and V RA++1s
where (s, is defined
uk, a, b) =E, Benttsul s.a) (Eewtensttha)) (V Vx,++1) (s', (s'.b- b )
(s, a, g 2.0) B Cusnneaaaa (P
(s', ))) -))
We calculate the optimistic value function and find the optimal policy via the following value iteration in our algorithm:
max. [ a) + P.P.VV (ss, b
(s(
(77)
0
b 650
Algorithm FMDP-BF for RLwK
Input: 5
Initialize N .) for any (s,0) E X
for episode k = 1,2, ... do
Set V (s, b) #1
for all 8, s,a,b.
5: Let K ES
(s, 0}
for horizon h
do
for s E S and all possible budget b from to do
for a E A do if (s, E then Qu,n(s,,
10:
fu CCB(ss a) + P...PPO
(xni(s,, b)}
else
(s,aa,
end if
end for
T (s. b) arg max Qu, b)
V (., b) = max Qk,
KR b) max {0, Re(ss TR.n) -BB,,,,,,,. b)+ PAVa
h+1 1 (8, Te b)}
end for end for
20:
for step 1
Take action ag,* = arg max, Qu.1 (sk,,,) end for
Update history trajectory f = LU(s;, Ci Pi, 8141 end for
Proof. (Theorem 4) The proof follows almost the same proof framework of Thm. 2 The term log(SAT) + dog Bm) is due to union bound over all possible (T, a) and budget b. This difference is because of the additional union bounds over all budget
H.3 DISCUSSIONS ABOUT ASSUMPTION I AND ASSUMPTION 2
Assumptions D and 2 limit our Algorithm to problems with discrete costs. One may wonder whether it is possible to construct e-net for budget B and possible value of the costs when these assumptions don't 't hold. In that case, only need to estimate the discrete cost distributions the e-net, and then apply Algorithm to tackle the problem. Unfortunately. we find that the e-net construction doesn't 't work for continuous cost distributions, and it is unlikely to achieve efficient
45

---

Published as a conference paper at ICLR 2021
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 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 certain state with remaining budget b. There are three actions to choose, with the cost of b b and b + e, respectively. After suffering the cost, the agent can achieve reward of O, 0.5 and respectively. Note that we can construct such hard instances with extremely small. For these hard instances, of any remaining budget E I 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. 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.
need carefully estimate the value function
There are two possible ways remove these assumptions and apply our algorithm to continuous cost distributions with e-net technique. The first idea to allow the slight violation of the total budget constraints, with the maximum violation threshold 6, or assume that the value of any initial state is lipschiz w.r.t the total budget B a small neighborhood of B (With maximum Lo distance 8). In that case,
tolerate the estimation error of each cost function be at most 8 e-net technique with e = म still works in this case and we can estimate the cost distribution 77
with precision म.. This modification is somewhat reasonable since the agent's policies are always "smooth" w.r.t the total budget a small region near B in many real applications such as games and robotics. The second idea to consider soft constraints. That is, when the budget constraints 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 possible method to remove the non-smoothness w.r. the total budget, which has wide applications in constrained optimization.
46


Reviews:
[{"review_id": "vlzUEh81F-2", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies RL in episodic factored MDPs (FMDPs) in the regret setting. The paper introduces an algorithm called FMDP-BF, which is a model-based algorithm implementing the optimistic principle by maintaining upper and lower confidence bounds derived using empirical Bernstein-type confidence sets.\nThe paper presents a high-probability regret bound for FMDP-BF appearing to be superior than existing results for episodic FMDPs. It also reports a regret lower bound for FMDPs. \n\nThe paper further studies a variant of \"RL under constraints\" in episodic MDPs and the regret setting, and shows that the corresponding problem can be cast as an instance of RL in an associated FMDP. Applying FMDP-BF to this (originally non-factored) RL problem, the paper derives tighter regret bounds than what would be obtained otherwise. \n\n\nMain Comments:\n\nThe paper studies an interesting and timely RL problem, which I believe to be significant in practice. In particular, the studied application to constrained RL is interesting and relevant. While the presented algorithm builds on well-known constructions that are already present in a series of recent works on episodic tabular MDPs, deriving sharp regret bounds like those in the present paper poses additional challenges making the problem non-trivial. To address such challenges, the paper introduces a couple of technical lemmas that sound interesting beyond the scope of this paper. These include in particular, Lemma 4.1 and Theorem 1 stating a Bellman-type result for the variance of factored Markov chains.\n\nThe paper is well-organized and states the results and the setup clearly. While the general writing quality is acceptable, I believe it still requires some polishing. In particular, there are many typos (see a list of them below), and in some cases there are unclear statements. \nThe review of the relevant literature seems adequate. In particular, the authors responsibly mention the parallel work of (Tian et al., 2020), though I urge the authors to provide a deeper technical comparison of their results to those of the latter paper. \n\nBesides the writing quality that could be improved by clarifying some statements and fixing typos, I have the following comments, which I would like to be addressed in the rebuttal:\n\n- While (Tian et al., 2020) is cited in the paper, the authors fail to adequately compare their results to those in (Tian et al., 2020)  -- except for a short discussion in page 3. Specifically, I believe they need to compare Theorem 2 to the regret bounds of (Tian et al., 2020) on page 6. I believe this is the right place for making such a comparison. Currently, there is only comparison against (Osband and Van Roy, 2014). The paper also lacks a comparison between the lower bound in Theorem 3 and those in (Tian et al., 2020). A precise and specific comparison is necessary here. \n\n- The idea of reducing the constrained RL problem to an FMDP is very nice. However, I think Assumption 2 makes the application of such a reduction rather restrictive. Could you please explain whether this can be improved or not?\n\nMinor Comments:\n\n- In Section 2.1, as far as I know (Lu & Van Roy, 2019) is not relevant to factored MDPs.\n\n- In page 7, the authors stated that introducing an $\\epsilon$-net to relax Assumption 2 \"will not influence the regret\". This is not true. This will penalize the regret, but perhaps with the choice of $\\epsilon=1/T$, the penalty does not influence the \\emph{order} of regret bounds ignoring polylogarithmic factors. Please explain.\n\n===== Post Rebuttal =====\n\nThanks for your response and for revising the paper.  I have increased my score accordingly. \n\n\nSome Typos/Mistakes:\n\np. 1: In paragraph 3, introduce $T$.\n\np. 1: Introduce $\\mathcal X[Z_i]$.\n\np. 2: there exists functions -> exist\n\np. 3 (and elsewhere): for factored Markov chain -> … chains\n\np. 3: Knapsack setting -> the knapsack setting\n\np. 3: … is more concise -> are \n\np. 3: We use … estimation of $V^\\star_h$ -> …  estimation of $V^\\star_h$, respectively.\n\np. 4: do not harm to the … -> remove \"to\"\n\np. 4 (and elsewhere): omits higher order factors -> I believe you mean here that $\\eta$ collects some higher order terms in the expression.\n\np. 5: all possible value of -> values \n\np. 6: $X[Z_i]$ -> Did you mean $\\mathcal X[Z_i]$\n\np. 7: for a $\\sqrt{n}$ -> for a factor of $\\sqrt{n}$\n\np. 7: focus -> focuses \n\np. 7: … but counts the cumulative cost … -> \"counts\" has made the statement rather unclear.\n\np. 8: from state to … -> from states and budget to actions (or state-space … to action-space)\n\np. 8: With prob. at least -> shortening probability to \"prob.\" does not seem to provide any gain in the space. \n\np. 8: To be more formally -> formal\n\np. 8: in interesting future work -> an interesting …\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "c0kkpuT9kpg", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper focuses on episodic, factored Markov decision processes and proposes the FMDP-BF algorithm, which is computation efficient and improves the previous result of the FMDP algorithm. The author also provides a theoretical lower bound for the FMDP-BF algorithm and shows that the FMDP-BF algorithm's regret is near-optimal. Besides, this paper applies the FMDP-BF algorithm in RLwK and provides theoretic analyses of regret. However, I still have some suggestions about this paper.\nFirstly, the definition of factor MDPs is complex and challenging to understand. It is better to add some examples for the factor MDP setting.\nSecondly, there is no experimental support for the FMDP algorithm, and it is better to perform some experiments with FMDP-BF, FMDP-CH algorithm.\nFinally, I have a concern about the FMDP algorithm. The UCBVI-CH algorithm, UCBVI-BF algorithm, and FMDP-CH algorithm only maintain one value function V in each episode. The only difference is the form of a bonus term. However, the FMDP-BF algorithm needs to keep two value function V to compute the bonus term, and I wondered whether it is necessary to keep two value functions in each episode.", "extra_scores": {}, "extra_text": {}}, {"review_id": "E0ogezbP3kW", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nMy overall concern about the paper is about the technical novelty of the paper. While I understand that there are quite a lot of technical calculations involved, the improved regret bound compared to Osband & Van Roy (2014) appears to be a direct outcome of replacing the confidence bounds used in Osband & Van Roy (2014)  by the confidence bounds proposed in Azar et al. 2017 on each of the factors in the factored model. In other words, on top of the technical contributions from Osband & Van Roy (2014)  and Azar et al. 2017, the proposed paper's first technical contributions appear to be on how to merge those two papers together.  \n\n### Post Rebuttal ### Thanks for the clarification, I have adjusted my score accordingly\n\nWhile the paper's second contributions allow the incorporation of a more refined resource constraints, it appears to me that the the proposed approach is unlikely to yield a computationally tractable algorithm even in the tabular setting, when the original state space is small. Indeed, the vector of remaining resource levels are embedded into the state, so that it will results in a curse in dimensionality even when the original space is of a manageable size. Overall, based on my evaluation on the theoretical and practical impact of the paper, I find that the contributions fall marginally below the acceptance threshold.  Finally, after the statement of the regret bound in Theorem 2, it is helpful to compare with the regret bound in the recent work by Tian et al. 2020, similarly to how the proposed algorithm is compared to Osband & Van Roy (2014).\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "1zl3w42gLn5", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe proposed method improves the regret order for FMDP by using novel bounds for the estimation error of one-step values (Lemma 4.1) and their variances (Corollary 1.1). A regret lower bound is also provided which matches the upper bound except for a $\\sqrt{n}$ and logarithmic factors. The paper is generally well written, and the proofs in the appendix are basically correct except some minor issues listed below. \n\nSome suggestions:\n\n- Corollary 1.1, likely typo: $V^{\\pi}_{h}$ instead of $V^{\\pi}_{h+1}$.\n- Algorithm 1, line 13, likely typo: $\\hat{R}_k(s, \\pi_{k,h})$.\n- Bottom of page 11, definition of $\\phi_{k,i}$, likely typo in $N_{k-1}(s,a)$ .\n- Through out the proofs, many terms could be replaced by proper notations like $\\phi_{k,i}$ or $CB^R_{k, Z^R_i}(s, a)$. For example, the RHS of (9) is exactly $\\phi_{k,i}$. By properly using the notations, the proofs would be much easier to read and the connection between lemmas would be much clearer.\n- $\\eta_{k, h, i}(s, a)$ is mentioned in Algorithm 1, but the notation is never explicitly defined. Also, it's a bit confusion to have two different sets of definitions for $CB^R, CB^P$ in (1)-(2) and in (3)-(6) for different algorithms. Maybe to use different notations and explicitly define the extra term $\\eta$.\n- Lemma D.1, missing $[Z^R_i]$ in (7). (9) seems like a direct application of (10).\n- Lemma D.2, the failure probability of $F^N$ in Dann et al. is bounded by $SAH\\delta$, which seems to suggests the log term in (15) is not correct.\n- In the proof of Lemma D.2, $V$ should be $V_{h+1}$, and the sentence after the set of equations should be \"The last inequality...\"\n- In (19), $\\mathbb{P}_n$ instead of $\\mathbb{P}_{k, n}$, and there seems to require an additional inequality for the last term to continue the recursion.\n- For Lemma E.2, missing $|S_i|$ in (21), and missing $1/m$ for the first equation in the proof, and $\\hat{\\mathbb{P}}_{i, k}$ in after the first inequality of the second equation.\n- Typo $\\mathbb{P}_h$ in the proof of Lemma E.3.\n- In the proof of Theorem 5, typo $\\hat{\\mathbb{P}}_{k, h}$ in the definition of $\\delta^3_{k, h}$, missing $[Z^P_i]$ in the third paragraph of page 19, and extra a's in the value functions in the last equation of page 19. In page 20, $\\delta^1_{k,h}$ and $\\delta^3_{k,h}$ should be bounded by Lemma E.2. At the end of the proof, the doesn't the big-O notation also hides all lower order terms in $T$?\n- In the proof of Lemma F.2, the constant in the log term is not consistent with Lemma D.2.\n- In the proof of Lemma F.4, the first equality incorrectly swaps the two summation. The result seems to be correct by first applying the inequality.\n- In the proof of Lemma F.5, the second inequality in the first equation seems to miss the last term which might be bounded by $log(T)$.\n- In the proof of Lemma F.10, the two inequalities bounded by $CB^R$ and $CB^P$ terms may be better stated as a lemma.\n- In the proof of Theorem 2, extra actions in the value functions in (44).\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper establishes the currently sharpest regret bounds for reinforcement learning in episodic factored MDP. The result improve the result by Osband and Van Roy 2014. The proposed FMDP-BF is a model-based algorithm that construct confidence sets of the transition distributions using Bernstein  and adapt policies by optimistic planning. The regret bounds holds with high probability. They also provide a lower bound for this class of problems. Reviewers all see merit in the theoretical results of the paper and reach a consensus that this is a good paper. We'd still like to request that the authors make all corrections and clarifications following the reviewers's suggestions, especially to improve the clarity of the formulation and proof sketches.

A separate suggestion: Model-based RL is a long existing approaches. For MDP belongs to a specific family, there exist regret bounds that depend on Eluder dimension of the the MDP family, see eg. https://arxiv.org/abs/1406.1853 and https://arxiv.org/abs/2006.01107. Can these results be applied to the factored MDP family and yield similar regret bounds? It would be necessary to add discussions about these papers, and explain why or why not these general regret bounds can apply to analyze HMDP.
Decision: Accept (Poster)