Towards Minimax Optimal Reinforcement Learningin Factored Markov Decision Processes
Yi Tian*Department of EECSMIT
Cambridge, MA 02139
yitian@mit.edu

Jian Qian∗
Department of EECSMIT
Cambridge, MA 02139
jianqian@mit.edu

Suvrit Sra
Department of EECSMIT
Cambridge, MA 02139
suvrit@mit.edu

Abstract
We study minimax optimal reinforcement learning in episodic factored Markov
decision processes (FMDPs), which are MDPs with conditionally independenttransition components. Assuming the factorization is known, we propose twomodel-based algorithms. The first one achieves minimax optimal regret guarantees
for a rich class of factored structures, while the second one enjoys better computational complexity with a slightly worse regret. A key new ingredient of ouralgorithms is the design of a bonus term to guide exploration. We complement ouralgorithms by presenting several structure-dependent lower bounds on regret for
FMDPs that reveal the difficulty hiding in the intricacy of the structures.

1

Introduction

In reinforcement learning (RL) an agent interacts with an unknown environment seeking to maximize
its cumulative reward. The dynamics of the environment and the agent’s interaction with it are
typically modeled as a Markov decision process (MDP). We consider the specific setting of episodic
MDPs with a fixed interaction horizon. Here, at each step the agent observes the current state of theenvironment, takes an action, and receives a reward. Given the agent’s action, the environment thentransitions to the next state. The interaction horizon is the number of steps in an episode. Both thetransitions and rewards may be unknown to the agent.
The agent’s performance can be quantified using regret: the gap between the expected cumulative
rewards the agent receives and those obtainable by following an optimal policy. An optimal RL
algorithm is then one√that incurs the minimum regret. For episodic MDPs, the minimax regret boundis known to be Õ( HSAT ) [1] (the notation Õ(·) hides log factors), where H, S, A, T denotethe horizon, the size of the state space, the size of the action space, and the total number of steps,
respectively.
√
Background and our focus. In problems with large state and action spaces even the Õ( SA)dependence of the regret is impractical. We focus on problems where one can circumvent thisdependence. Specifically, we focus on problems with conditional independence structure that can bemodeled via factored MDPs (FMDPs) [2, 3]. The state for an FMDP is represented as a tuple, where
each component is determined by a potentially small portion of the state-action space, termed its“scope”. For example, for a home robot, whether the table is clean has nothing to do with whether the
robot vacuums the floor. FMDPs also arise naturally from cooperative RL [15, 32] and constrained
RL [7]; furthermore, they are useful to model subtask dependencies in hierarchical RL [36].
A key benefit of FMDPs is their more compact representation that requires exponentially smaller
space to store state transitions than corresponding nonfactored MDPs. Early works [16, 24, 37, 39]
show that FMDPs can also reduce the sample complexity exponentially, albeit with some higher orderterms. Osband and Van Roy [28] and Xu and Tewari [43] develop near-optimal regret bounds for∗

These authors contributed equally to this work.

34th Conference on Neural Information Processing Systems (NeurIPS 2020), Vancouver, Canada.

FMDPs in the episodic and nonepisodic settings, respectively. For an
FMDP with m conditionallyPm p
independent components, both works bound the regret by Õ( i=1 D2 Si X[Ii ]T ), 2 where D isthe diameter of the MDP [20] and X[Ii ] is the size of the scope of the ith state component.
the above regret bounds from [28, 43] reduce toMain√ difficulty. For (nonfactored) MDPs,√Õ( D2 S 2 AT ), also translated to Õ( H 2 S 2 AT ) in the episodic setting. Either bound has a
gap to the corresponding lower bound, leading one to wonder whether we can adapt the techniquesfrom MDPs to obtain tight bounds for FMDPs. Answering this question turns out to be nontrivial.
Indeed, the key technique that yields a minimax regret bound for MDPs is a careful design of thebonus term that ensures optimism by applying scalar concentration instead of L1 -norm concentration(Lemma 36) on a vector [1]. To adapt the same idea to FMDPs, perhaps the most natural choice
is to estimate the transition of each component separately, and then to sum up the component-wisebonuses to guide overall exploration. With the bonuses derived from L1 -norm concentration, thismethod ensures optimism, leading to the regret bound in [28, 43]. But with the bonuses derived fromscalar concentration (which was key to [1]), it is hard, if not impossible, to show that this naive sumof component-wise bonuses√ ensures optimism (see (5.1)), and thus is the major obstacle towards
removing the suboptimal Si factor from the regret bound.
On the other hand, there is no uniform nondegenerate lower bound that holds for every structure. As
a result, the dependence on structure has to be specified, making the lower bound statements subtle
due to the intricacy of the structure involved.
Our contributions. Our main contribution is to present two provably efficient algorithms for episodic
FMDPs, including one with tight regret guarantees for a rich class of structures. We overcome theabove noted difficulty by introducing an additional bonus term via an inverse telescoping
technique.
Pm p
Our first algorithm F-UCBVI, uses Hoeffding-style bonuses and achieves the Õ( i=1 H 2 X[Ii ]T )regret (Theorem 1). Our second algorithm F-EULER, uses Bernstein-stylebonuses and achieves
Pm pa problem-dependent regret (Theorem 2) that√reduces to Õ( i=1 HX[Ii ]T ) in the worst case(Corollary 3), and thus closes the gap to the√Ω( HSAT ) lower bound (see, e.g., [21]) when reduced
to the nonfactored case. Despite an extra H dependence, F-UCBVI has a much simpler form of
bonus and enjoys a lower computational complexity.
Furthermore, we identify some reasonably general factored structures for which we prove lower
bounds (Propositions 4, 5 and Theorems 6, 7). Our construction builds upon the lower bounds
for multi-armed bandits (MABs)√ [26], in a similar manner to [8, 21]. As a side remark, the JAO
MDP,
used
to
establishtheΩ(
DSAT ) lower bound for nonepisodic MDPs [20], only establishes apΩ( HSAT / log T ) lower bound through a direct extension (Appendix D). This result misses a log
factor resulting from the episodic resetting, and it is not clear whether it can be tightened with thesame construction.
1.1

Related work

Regret bound for episodic MDPs. For episodic√ MDPs, using the principle of optimism in the faceof uncertainty, recent
works
establish
the
Õ(HSAT ) worst-case regret bound [1, 13, 23, 35, 44],√
matching the Ω( HSAT ) lower bound (see,√e.g., [21]) up to log factors. For model-free algorithms,
the state-of-the-art worst-case regret is Õ( H 2 SAT ) [45]. Sharper problem-dependent regretbounds [35, 44] also exist in this setting. Posterior sampling for RL (PSRL) [30] offers an alternative
to optimism-based methods and can perform√ well empirically [29]. The best existing Bayesian regretbound of PSRL for episodic MDPs is Õ( H 2 SAT ) [29]. Among these works, our work is mostly
motivated by [1, 44]. Specifically, for nonfactored MDPs, F-UCBVI and F-EULER reduce to the
UCBVI-CH [1] and EULER [44] algorithms, respectively, after which we name our algorithms.
Planning in FMDPs. For nonepisodic FMDPs, various works exploit the factored structure todevelop efficient (approximate) dynamic programming methods [4, 14, 17, 25, 34]. See [10] for an
overview. For episodic FMDPs, however, efficient approximate planning is yet to be understood.
Planning is a subroutine of model-based RL algorithms. The focus of this work is the sample
efficiency, and we adopt a value iteration procedure that has the same computational complexity asthat for a nonfactored MDP.
2

The dependence on reward factorization is omitted here and below, unless otherwise stated. The omission
also corresponds to the case of known rewards.

2

Reinforcement learning in FMDPs. To efficiently find the optimal policy assuming known factorization yet unknown state transitions or rewards, early works aim to develop algorithms with
PAC guarantees[16, 24, 37, 39]. More recent works focus on the regret analysis and establish
Pm p 2Õ( i=1 D Sp
X[Ii ]T ) regret in either the episodic or nonepisodic setting [28, 43], also translatPm i
ing to Õ( i=1 H 2 Si X[Ii ]T ) in terms of horizon H for episodic problems. Our work
considersPm pminimax optimal regret guarantees in the episodic setting. It provides the first Õ( i=1 HX[Ii ]T )regret bound and the first formal treatment of lower bounds, by which we show that our algorithm isminimax optimal fora rich class of factored structures. Subsequently, Chen et al. [7] improve thepPmupper bound to Õ(i=1 HX[Ii ]T ) by a more delicate√ variance decomposition. Their bound istighter than that of our F-EULER algorithm by at most m, a log factor in the size of the state space.
Structure learning in FMDPs. Assuming unknown structure except for known state factorization,
various structure learning algorithms exist in the literature, e.g., SPITI [11], SLF-Rmax [38], MetRmax [12] and LSE-Rmax [6]. See [5, Chapter 7] for an overview of these methods. More recent
works include [18, 19, 33], among which Rosenberg and Mansour [33] provide the first regret analysis
for nonepisodic FMDPs in this setting.

2

Preliminaries and problem formulation

2.1

Learning in episodic MDPs

An episodic MDP is described by the quintuple (S, A, P, r, H), where S is the state space, A is theaction space, P : S × A × S → [0, 1] is the transition function such that P (·|s, a) is in the probability
simplex on S, denoted by ∆(S), r : S × A → [0, 1] is the reward function, and H is the horizonor the length of an episode. The focus in this paper is the stationary case, where both the transition
function P and the reward function r remain unchanged across steps or episodes.
An RL agent interacts episodically with the environment starting from arbitrary initial states. The
role of the agent is abstracted into a sequence of policies. For any natural number n, we use [n] todenote the set {1, 2, · · · , n}. Then for finite-horizon MDPs, the policy π : S × [H] → A maps astate and a time step to an action. Let πk denote the policy in the kth episode. An RL algorithm,
therefore, specifies the updates of the sequence {πk }. Our algorithms use deterministic policies,
while the lower bounds hold for the more general class of stochastic policies.
The Q-value function Qπh and state-value function Vhπ measure the goodness of a state-action pairand of a state following the policy π starting from the hth step in an episode, respectively. For states ∈ S and action a ∈ A, these functions are defined byihXH
Qπh (s, a) = Er(st , at ) sh = s, ah = a , Vhπ (s) = Qπh (s, π(s, h)).
t=h∗There exists an optimal policy π ∗ such that Vhπ (s) ≥ Vhπ (s) for all s ∈ S, h ∈ [H] [31]. Let Vh∗∗denote the optimal state-value function Vhπ , and let sk,1 be the initial state at the kth episode; wethen define the regret over K episodes (T = KH steps) as
XK
Regret(K) :=(V1∗ (sk,1 ) − V1πk (sk,1 )) .
k=1

2.2

Factored MDPs

Episodic FMDPs inherit the above definitions, but we also need additional notation that we adopt
mainly from [28] to describe the factored structure. Let X := S × A be the state-action space, sothat x = (s, a) ∈ X denotes a state-action pair. Let m, n, l be natural numbers. The state space isfactorized as S = S1 × · · · × Sm , using which we write a state s ∈ S as the tuple (s[1], · · · ,Ns[m]).
Similarly, the state-action space is factorized as X = X1 × · · · × Xn . Below we also use “ ” todenote Cartesian products, as needed.
Definition
N1n (Scope operation). For any natural number
Nn, any index set I ⊂ [n] and any factored
set X = i=1 Xi , define the scope operation X [I] := i∈I Xi , where the indices in the Cartesian
product are in ascending order by default. Correspondingly, define the scope variable x[I] ∈ X [Ii ]as the tuple of xi where i ∈ I.
The transition factored structure refers to the conditional independenceof the transitions of the m state
Qmcomponents. Mathematically, P (s0 |s, a) = P (s0 |x) = i=1 Pi (s0 [i]|x), where Pi (·|x) ∈ ∆(Si ).
3

Moreover, the transition of the ith state component is determined only by its scope, a subset of thestate-action components. Let Ii ⊂ [n] be the scope index set for i ∈ [m]. Then, with a slight abuse
0of notation, Pi (s0 [i]|x)Qm≡ Pi (s [i]|x[Ii ]) where “≡” denotes identity, and the factored transition is
given by P (s0 |x) = i=1 Pi (s0 [i]|x[Ii ]).
The reward function r is stochastic and unknown in general, and can also be factored. Let Ji ⊂ [n]be the reward scope index set for i ∈ [l]. The factored reward is the sum of l independent componentsPlri (x) ≡ ri (x[Ji ]), given by r(x) =i=1 ri (x[Ji ]). Let R := E[r] and Ri := E[ri ] be theirPl
expectations. Then R = i=1 Ri : X → [0, 1] is deterministic. With the above notation, an FMDP
model is described in general bynml
M = {Xi }i=1 , {Si , Ii , Pi }i=1 , {Ji , ri }i=1 , H .
(2.1)
In this paper, we assume unknown transition with a known factorization and consider two cases
about the knowledge of reward: (1) the reward r is unknown with a known factorization and theagent receives the factored rewards {ri }li=1 [28, 43]; or (2) the reward r is known and not necessarily
factored, in which case the expected reward R is also known [1].
Notation. Throughout the paper, we use S, A, X, Si , X[I]Q
to denote the finite cardinalities of themcorresponding S, A, X , Si , X [I], respectively. Then S = i=1 Si and X[I] ≤ X = SA for any
I ⊂ [n]. Since the abstraction of a state component s[i] is meaningful only if Si ≥ 2, the number ofstate components m is at most log2 S , which is treated as a negligible log factor whenever necessary.
For x = (s, a) ∈ X , we use Q(s, a) and Q(x) interchangeably to denote a function Q defined on
X := S × A. A function V : S → R is also seen as a real vector indexed by S, denoted by V ∈ RS .
For vectors in RS , let | · |, (·)2 denote entrywise absolute values and squares, respectively.
Define P (x) := P (·|x) ∈ ∆(S). Moreover, for Pi (x) ≡ Pi (x[Ii ]) := Pi (·|x[Ii ]) ∈ ∆(Si ) andQb
Nb
Qm
natural numbers a ≤ b, define Pa:b (x) := i=a Pi (x) ∈ ∆( i=a Si ). In particular,
i=1 Pi (x) =PP (x) ∈ ∆(S). For P ∈ ∆(S), V ∈ RS , define their inner product hP, V i := s∈S P (s)V (s) =EP [V (s)] ≡ EP [V ]. The inner product of two elements in ∆(Si ) and RSi respectively takes sum
over Si . For Pi ∈ ∆(Si ) and V ∈ RS , their inner product takes P
sum over S. In this case, notethat hPi , V i 6= EPi [V ], which is given by EPi [V ] ≡ EPi [V (s)] = s[i]∈S Pi (s[i])V (s) ∈ RS[−i] ,Nmwhere S[−i] := j=1,j6=i Sj .

3

Factored UCBVI and regret bounds

We are now ready to present the two algorithms for solving FMDPs that we propose. In this section,
We introduce the general procedures (Algorithms 1 and 2) and discuss an instantiation called factored
UCBVI (F-UCBVI) using Hoeffding-style optimism. In the next section, we use a Bernstein-styleinstantiation called factored EULER (F-EULER) that obtains better regret guarantees. The general
optimistic model-based RL framework for FMDPs is described in F-OVI (Algorithm 1), which
maintains an empirical estimate of the transition function, typically the maximum likelihood (ML)estimate. For FMDPs, although a direct ML estimate of the overall transition is still possible, theproduct of the ML estimates of component-wise transition functions is preferable to exploit thefactored structure. The same argument applies to the empirical expected reward function.
As a subroutine of F-OVI (Algorithm 1), VI_Optimism (Algorithm 2) ensures an upper confidencebound (UCB) on the optimal state-value function, achieved by introducing bonuses derived fromconcentration inequalities. The L1 -norm concentration (Lemmap 36) on the transition estimationP
leads to the UCRL-Factored algorithm, achieving the Õ( i=1 D2 Si X[Ii ]T ) regret [28]. Scalar
concentration on the transition estimation leads to the two new algorithms proposed in this work.
In the case of known rewards, there is no need to estimate the reward R̂ or to collect the reward
history Hr in F-OVI (Algorithm 1). Neither is there the need to introduce the reward bonus β in
VI_Optimism (Algorithm 2). In both procedures, the empirical R̂ is replaced by the true R.
Hoeffding-style bonus. Let L = log(16mlSXT /δ) be a log factor. With a slight abuse of notation,
let Ni (x) ≡ Ni (x[Ii ]). The transition bonus of F-UCBVI is given by
q
q
Xm
Xm Xm
Si Sj
H 2NLi (x) +b(x) :=
2HL Ni (x)N
,
(3.1)
j (x)
i=1

i=1

4

j=i+1

Algorithm 1 F-OVI (Factored Optimistic Value Iteration)nmlRequire: Factored structure {Xi }i=1 , {Si , Ii }i=1 , {Ji }i=1 , and horizon H
1: Initialize counters Ni (x[Ii ]) = Ni0 (x[Ii ], s[i]) = 0, ∀(i ∈ [m], x[Ii ] ∈ X [Ii ], s[i] ∈ Si )2: Initialize counters Mi (x[Ji ]) = Mi0 (x[Ji ]) = 0, ∀(i ∈ [l], x[Ji ] ∈ X [Ji ]) and history Hr = ∅3: for episode k = 1, 2, · · · , K do
N 0 (x[I ],s[i])4:iiEstimate transitions P̂i (s[i]|x[Ii ]) = max{1,N, ∀(i ∈ [m], x[Ii ] ∈ X [Ii ], s[i] ∈ Si )i (x[Ii ])}5:ii, ∀(i ∈ [l], x[Ji ] ∈ X [Ji ])Estimate expected rewards R̂i (x[Ji ]) = max{1,Mi (x[Ji ])}Pl
Estimate expected overall reward R̂(x) = i=1 R̂i (x[Ji ]), ∀x ∈ X

6:

M 0 (x[J ])ml7:
Obtain policy π = VI_Optimism({P̂i }mi=1 , R̂, {Ni }i=1 , {Mi }i=1 , Hr )8:
Observe initial state s1 from environment
9:
for step h = 1, 2, · · · , H do
10:
Take action ah = π(sh , h) and let xh = (sh , ah )11:
Receive reward {ri,h }li=1 and observe next state sh+1
12:
Update transition counters Ni (xh [Ii ]) += 1 and Ni0 (xh [Ii ], sh+1 [i]) += 1, ∀i ∈ [m]13:Update reward counters Mi (xh [Ji ]) += 1 and Mi0 (xh [Ji ]) += ri,h , ∀i ∈ [l]14:Update reward history Hr = Hr ∪ {(xh , {ri,h }li=1 )}15:
end for
16: end for

Algorithm 2 VI_Optimism (Value Iteration with Optimism)m
Require: Empirical transitions {P̂i }mi=1 , empirical expected reward R̂, transition counters {Ni }i=1 ,lreward counters {Mi }i=1 , reward history Hr
Qm
1: Initialize UCB and LCB V H+1 (s) = V H+1 (s) = 0, ∀s ∈ S; let P̂ (x) = i=1 P̂i (x), ∀x ∈ X
2: for step h = H, H − 1, · · · , 1 do
3:for state s ∈ S do
4:
for action a ∈ A, withn x = (s, a) doDEoQh (x) = min H − h + 1, R̂(x) + P̂ (x), V h+1 + b(x) + β(x)5:6:end for7:
Let π(s, h) = argmaxa∈A Qh (s, a) and x = (s, π(s, h))8:Update UCB V h (s) = Qh (x)nDEoUpdate LCB V h (s) = max 0, R̂(x) + P̂ (x), V h+1 − b(x) − β(x)10:end for
11: end for
12: return policy π
9:which consists of both a component-wise bonus term and a cross-component bonus term. Intuitively,
since the transition and reward factorizations in an FMDP may differ arbitrarily, the sum of componentwise transition bonuses alone may not suffice to ensure optimism. It turns out that combining thecross-component transition bonuses suffices. In the case of unknown rewards, the reward bonus of
F-UCBVI is given byXl qLβ(x) :=(3.2)
2Mi (x) .
i=1

For the transition and reward bonuses here and below, zero-valued Ni (x) and Mi (x) in the denominators are replaced by 1 to prevent zero division, as in F-OVI (Algorithm 1). For F-UCBVI, thereward history Hr and the lower confidence bound (LCB) V h are redundant and the related updates
are removable. F-UCBVI has the following regret guarantees.
Theorem 1 (Worst-case regret bounds of F-UCBVI). For an FMDP specified by (2.1), in the case of
unknown rewards, with probability 1 − δ, the regret of F-UCBVI in K episodes is upper bounded by
Xm p

Xl p
Õ
H 2 X[Ii ]T +X[Ji ]T .
(3.3)
i=1
i=1
p
Pl
In the case of known rewards, the term i=1 X[Ji ]T can be dropped.
5

√
In Theorem 1 (and Theorem 2, Corollary 3 below), the T terms dominate the upper bounds under
the assumption that T ≥ poly(m, l, maxi Si , maxi X[Ii ], H), which can be exponentially smaller
than poly(S, A, H), required in general by nonfactored algorithms [1, 13, 22, 23, 35, 44, 45]. This
weaker requirement on T is also true for [28] and can be viewed as another benefit from the factored
structure. The lower-order terms in Section 5 are also under this assumption.
In (3.3), the regret bound consists of a transition-induced term and a reward-induced term, whichcorrespond to the sum over time of the component-wise transition bonus term in (3.1) and the reward
bonus (3.2), respectively. The cross-component transition bonus term in (3.1) diminishes fast andits sum over time turns out to be negligible. Nevertheless, this bonus term plays a significant roleby stablizing early-stage exploration, when it dominates the transition bonus due to the dependence
on Si . Concretely, initially, the cross-component transition bonus term encourages exploration of
the ith and jth components with large Si Sj . Then as the counters of some components (say, theith) grow fasterits cross-component transition bonuses (say, with the jth)p such that Ni (x) ≥ Si , psatisfy HL Si/Ni (x) · Sj/Nj (x) ≤ HL Sj/Nj (x), which prioritize exploration of underexploredcomponents until all counters satisfy Ni (x) ≥ Si . In the next stage this bonus term balances the
exploration among different components until all counters satisfy max{Ni (x), Nj (x)} ≥ Si Sj andthe component-wise transition bonus term takes over to dominate the overall bonus.
Note that the cross-component form is not absolutely necessary, e.g., by the AM-GM inequality,
q
Xm Xm
Xm
Si Sj
Si
2HL Ni,k (x)N≤ (m − 1)HL
Ni,k (x) .
j,k (x)
i=1

j=i+1

i=1

In this work, we use the cross-component form, as it is tighter and implies an intertwined behavior
among the state components.
The component-wise transition bonus term in (3.1) is exactly the bonus in the UCBVI-CH algorithm [1]. It may also be feasible to derive a factored version of UCBVI-BF [1], but we switch to an
upper-lower bound exploration strategy like EULER [44] for the Bernstein-style optimism, due inpart to its problem-dependent regret.

4

Factored EULER and regret bounds

To describe the Bernstein-style bonus, we first add
convenient notation. We omit the dependence
Qsomemof Pi (x) and P (x) on x; for Pi ∈ ∆(Si ), P = i=1 Pi ∈ ∆(S) and V ∈ RS , define√ qgi (P, V ) := 2 L VarPi EP−i [V ],(4.1)
where EP−i [V ] := EP1:i−1 Pi+1:m [V ] ∈ RSi takes expectation over the m − 1 components. With thepnotation from [44], let kXk2,P = EP [X 2 ] be the L2 -norm on the equivalence classes of almost
surely the same random variables.
Bernstein-style bonus. The transition bonus of F-EULER is defined by
Xm g (P̂ (x),V ) Xm √2LkV h+1 −V h+1 k
2,P̂ (x)
i
h+1
√
√
+
b(x) :=Ni (x)Ni (x)
i=1
i=1
q
Xm Xm
Xm
Si Sj
5HL
11HL Ni (x)N++Ni (x) .
j (x)
i=1

j=i+1

(4.2)

i=1

In the case of unknown rewards, the reward bonus of F-EULER is defined by
Xl q 4S[r̂ (x)]L Xl
14Liβ(x) :=Mi (x) +3Mi (x) ,
i=1

i=1

(4.3)

where S[r̂i (x)] is sample variance of the reward component, calculated using the history Hr . Online
algorithms like Welford’s method [42] can efficiently compute R̂i and S[r̂i (x)] jointly. F-EULER
has the following problem-dependent regret guarantees.
Theorem 2 (Problem-dependent regret bounds of F-EULER). For an FMDP specified by (2.1), let∗Qi := max
VarPi (x) EP−i (x) [Vh+1] , Ri := max {Var[ri (x)]} .
x∈Xx∈X ,h∈HPH
Let G be the upper bound of h=1 R(xh ) for any initial state and any policy. In the case of unknown
rewards, with probability 1 − δ, the regret of F-EULER in K episodes is upper bounded byXm p
 Xm p
min Õ
Qi X[Ii ]T , Õ
G 2 X[Ii ]K
(4.4)
i=1
i=1
Xl p
 Xl p+ min ÕRi X[Ji ]T , Õ
G 2 X[Ji ]K .
(4.5)
i=1

i=1

6

In the case of known rewards, the term (4.5) is dropped.
F-EULER does not assume knowledge of the actual Qi , Ri and G and its regret bounds (Theorem 2)
enjoy the same problem-dependent advantages as discussed in the nonfactored case [44]. r(·) ∈ [0, 1]
yields G ≤ H and Ri ≤ 1 for all i ∈ [l]. Hence, Theorem 2 implies the following worst-case regret.
Corollary 3 (Worst-case regret bounds of F-EULER). For an FMDP specified by (2.1), if the rewards
are unknown, with probability 1 − δ, the regret of F-EULER in K episodes is upper bounded by

X
Xl p
m p
HX[Ii ]T +X[Ji ]T .
(4.6)
Õ
i=1

i=1

Pl

p

It the rewards are known, the term i=1 X[Ji ]T is dropped.
In (4.6), the regret bound again consists of a transition-induced term and a reward-induced term,
resulting from the sum over time of the first term√in (4.2) and the first term in (4.3), respectively. For
nonfactored
MDPs, the reward-induced term Õ( SAT ) is absorbed into the transition-induced term√Õ( HSAT ), while for FMDPs, these two terms depend on their factorization structures, and do notabsorb each other in general.
Corollary 3 indicates that F-EULER improves the transition-induced√
term of F-UCBVI by a H factor. On the other hand, F-EULER has a worse computational complexity than F-UCBVI. Even if neglecting the computation on the reward bonus (since efficient methods
exist), in each run of the VI_Optimism subroutine, F-EULER has O(mS 2 AH) computational
complexity, m times more than F-UCBVI.

5

Proof sketch

We present here the proof ideas of F-UCBVI in the case of known rewards, which sheds lighton our main new techniques. The full proof is deferred to Appendix A. We add a subcript k toP̂i , P̂ , Ni , Mi , V h , b in Algorithms 1 and 2 to denote the corresponding quantities in the kth episode.
ππ
For inductive purpose, let VH+1(s) = 0 for all π ∈ Π, s ∈ S, so that Vhπ (s) = R(x) + P (x), Vh+1
with x = (s, π(s, h)) for all π ∈ Π, s ∈ S, h ∈ [H], where Π is the set of all deterministic policies.
The mechanism of optimism. The purpose of the bonus is to ensure optimism, which means
obtaining an entrywise UCB V k,h on Vh∗ for all k ∈ [K], h ∈ [H].
For h = H + 1, this is certainly the case, since they are both entrywise 0. For h ∈ [H], ∀s ∈ S, withx∗h = (s, π ∗ (s, h)),∗∗V k,h (s) − Vh∗ (s) ≥ P̂k (x∗h ), Vk,h+1 − Vh+1
+ P̂k (x∗h ) − P (x∗h ), Vh+1
+bk (x∗h ).
|
{z
} |
{z
}
≥ 0 by inductive assumption

transition estimation error

To form a valid backward induction argument, we expect the bonus to be a UCB of the absolute valueof the transition estimation error. For nonfactored MDPs, with Nk (x) being the number of visits to x
before the kth episode, a direct application of Hoeffding’s inequality (Lemma 37) yields that for any
x ∈ X,q∗P̂k (x) − P (x), Vh+1
≤ H 2NL,k (x)which determines the transition bonus. For FMDPs, a natural extension is to expect
q
Xm
? Xm
∗
∗
L
P̂k (x) − P (x), Vh+1≤
P̂i,k (x) − Pi (x), Vh+1≤
H 2Ni,k
(x) ,
i=1

i=1

(5.1)

which can then be used as the transition bonus. Although it holds thatXm∗∗P̂k (x) − P (x), Vh+1≤
P̂i,k (x) − Pi (x) , Vh+1,
i=1

the inequality in question in (5.1) fails to hold (e.g., using Si = m = 2 one obtains a quick
contradiction). To address this difficulty, we adopt an inverse telescopingDtechnique. OmittingtheE∗
dependence of the transitions P̂k (x), P (x), P̂i (x), Pi (x) on x, we rewrite P̂k − P, Vh+1 as
Ym
Ym
Xm
∗
∗
P̂i,k −Pi , Vh+1=(P̂i,k − Pi )P1:i−1 P̂i+1:m,k , Vh+1
i=1
i=1
i=1
Xm
∗
=
P̂i,k − Pi , EP1:i−1 EPi+1:m [Vh+1
]
(5.2)
i=1
Xm
∗
+
P̂i,k − Pi , EP1:i−1 (EP̂i+1:m,k − EPi+1:m )[Vh+1
] ,
(5.3)
i=1

7

where the first equality is referred to as the “inverse telescoping” technique, and the second equality
adds then subtracts the same term (5.2), which can be bounded by scalar concentration, leading to thecomponent-wise bonus term in (3.1). (5.3) is bounded by L1 -norm concentration (Lemma 36) withanother use of the inverse telescoping technique, leading to the cross-component bonus term in (3.1).
Regret bound. In the sequel, we use “., ≈” to represent “≤, =” hiding constants and lower-orderterms. Let wk,h (x) denote the visit probability of x ∈ X at step h ∈ [H] following policy πk during
the interaction. Then the optimism ensures that the regret in K episodes is upper bounded by
XK
V k,1 (sk,1 ) − V1πk (sk,1 )
≈

k=1
K
H X
XX


∗
∗
wk,h (x) bk (x) + P̂k (x) − P (x), Vh+1
+ P̂k (x) − P (x), V k,h+1 − Vh+1
,
|
|
{z
}
{z
}
k=1 h=1 x∈Lktransition estimation error

correction, sum is lower-order (Lemma 22)

where the “good” set Lk is a notion of sufficient visits before the kth episode and the sum out of Lk
is a lower-order term (Lemma 13). The cumulative transition estimation error is upper bounded by
K X
H X
X

wk,h (x)mnX

k=1 h=1 x∈Lk

H

q

L

2Ni,k (x) +

i=1

m X
m
X

2HL

q

Si Sj
Ni,k (x)Nj,k (x)

o

H

p

X[Ii ]T L.

i=1

i=1 j=i+1

|

.

m
X

{z

sum is lower-order (Lemma 16)}

The upper bound of the cumulative transition bonus takes exactly the same form. Thus, we obtain
Xm p
Xm
p
H 2 X[Ii ]T ).
Regret(K) .
H X[Ii ]T L = Õ(
i=1

i=1

Extension to other conditions. The treatment of unknown rewards is standard [44]. The samemechanism of optimism applies to F-EULER, except that the scalar concentration uses Bernstein’s
inequality (Lemma 38). Please see Appendix B for a complete proof.

6

Lower bounds

In this section, we present some information theoretic lower bounds for different factored structuresof FMDPs, which illustrate the structure-dependent nature of the lower bounds. Even in the mostgeneral lower bound (Theorem 7), we assume a normal factored structure (Definition 2); a fullcharacterization is still an open problem.
Recall the formal statement of the lower bound for MDPs that for any given natural numbers
S, A, H, there is an MDP that has S states, A actions and horizon H with unknown transition P
and√possibly known rewards R, such that the expected regret of any algorithm in K episodes isΩ( HSAT ). Ideally, the lower bound of FMDPs should be stated in the same way, specified for anynmlnatural numbers
m, n, l, H and p
any factored structure {Si }m
i=1 , {Xi }i=1 , {Ii }i=1 , {Ji }i=1 . A simple
Pm pPlΩ( i=1 HX[Ii ]T + i=1 X[Ji ]T ) lower bound is tempting, yet far from the truth. To avoid
excessive subtlety, our lower bound discussion is restricted to the following normal factored structure,
where the state-action factorization is an extension to the state factorization.
Definition
2 (Normal factored structure).
Nm
Nn−m For natural numbers m < n, let the state space S =
S
and
the
action
space
A
=
i
i=1
i=1 Ai . The factored structure of an FMDP is normal if theNnstate-action space X = i=1 Xi where Xi = Si for i ∈ [m] and Xm+i = Ai for i ∈ [n − m].
We now state the lower bounds for two degenerate structures.
Proposition 4 (Degenerate case 1). For any algorithm, under the assumption of unknown rewards,
for the normal factored structure that satisfies Ii ⊂ [m] for all i ∈ [m] and any Ji for i ∈ [l], there
is an FMDP with the specified
p structure such that for some initial states, the expected regret in K
episodes is at least Ω(maxi X[Ji 0 ]T ) where Ji 0 = Ji ∩ {m + 1, · · · , n}.
Proposition 5 (Degenerate case 2). For any algorithm, under the assumption of unknown rewards,
for the normal factored structure that satisfies Ji ⊂ {m + 1, · · · , n} for all i ∈ [l], there is an FMDP
with the specified
p structure such that for some initial states, the expected regret in K episodes is atleast Ω(maxi X[Ji ]T ).
8

Proposition 4 considers the degenerate case where the transitions do not depend on the action spaceat all. Furthermore, the regret is always 0 if the rewards do not depend on the action space either(Ji 0 = ∅ for all i ∈ [l]). Proposition 5 considers the degenerate case where the rewards have nodependence on the state space, and X[Ii ] vanishes in the lower bound for this MAB problem. The
following theorem identifies some nondegenerate constraints on the factored structures.
Theorem 6 (Lower bound, a nondegenerate case). For any algorithm, under the assumption of known
rewards, for the normal factored structure that satisfies Si ≥ 3, i ∈ Ii , ∃j ∈ {m + 1, · · · , n} suchthat j ∈ Ii for all i ∈ [m] and H ≥ 2, there is an FMDP with the specified
p structure such that forsome initial states, the expected regret in K episodes is at least Ω(maxi HX[Ii ]T ).
The regret achieved by F-EULER is minimax optimal up to log factors for the structures specified in
Theorem 6. The main assumption here is that the transition of each state component depends on itself
and at least one action component. A major obstacle to show the lower bound for a general factored
structure is that some structures lack the self-loop property, i.e., the transition of a state component
depends on itself so that we can say it stays in the same state with a certain probability, which is key
to the lower bound constructions for nonfactored MDPs [8, 20, 21]. By generalizing the self-loop
property to the loop property, we can show a more general version of the nondegenerate lower bound.
For an FMDP with the normal factored structure, for i, j ∈ [m], if i ∈ Ij , then we say the jth statecomponent depends on the ith state component, or the ith state component influences the jth statecomponent, denoted by Si → Sj . We say the ith state component has the loop property if the ith
state component influences itself either directly (Si → Si , self-loop) or through some intermediate
state components (Si → · · · → Sj → · · · → Si for some j’s ∈ [m]). The loop is referred to as an
influence loop. Let I be the set of the indices of the state components that have the loop property andsome action dependence, i.e.,
I := {i ∈ [m] : Si has the loop property, and there exists j ∈ {m + 1, · · · , n} such that j ∈ Ii } .
Then we have the following theorem that subsumes Theorem 6.
Theorem 7 (Lower bound, normal factored structure with known rewards). For any algorithm, under
the assumption of known rewards, for the normal factored structure that satisfies Si ≥ 3, ∀i ∈ [m]and H ≥ 2, there is an FMDP with the specified pstructure such that for some initial states, theexpected regret in K episodes is at least Ω(maxi∈I HX[Ii ]T ).
Theorem 7 indicates that for a rich class of factored structures satisfying maxi∈I X[Ii ] =maxi∈[m] X[Ii ], F-EULER is minimax optimal up to log factors. We defer to Appendix C the
proofs of Propositions 4, 5 and Theorems 6, 7, relying on the lower bounds for MABs [26] and theconstruction of MAB-like FMDPs (FMDPs whose cumulative rewards depend only on the action in
the first step), similar to the MAB-like MDPs in [8, 21].

7

Conclusion

In this paper, we study reinforcement learning in the tabular episodic setting of FMDPs, that is,
MDPs which enjoy a factored structure in their dynamics. Such a factorization is typically derived
via conditional independence structures in the transition, and by using it effectively one can greatly
reduce the complexity of learning. However, a straightforward adaptation of the usual minimax
optimal regret analysis for MDPs turns out not to be possible. We uncover the difficulties posed bysuch an adaptation, and subsequently develop two new algorithms (called F-UCBVI and F-EULER,
both motivated by their known nonfactored analogues) that carefully exploit the factored structure toobtain minimax optimal regret bounds for a rich class of factored structures. The key algorithmic
technique that we develop is a careful design of a “cross-component” bonus term to ensure optimismand guide exploration.
We present the lower bounds for FMDPs under certain structure constraints. The problem of characterizing lower bounds for FMDPs with arbitrary structures turns out to be more subtle, and remains
an open problem. In addition, our methods are model-based, and the computational accelerationof planning in episodic FMDPs is a practical direction; on the other hand, developing efficientmodel-free algorithms for FMDPs is also worth exploring.
9

Broader impact
This work focuses on a theoretical problem about efficient learning in factored MDPs. The work
itself is ethically neutral. Future societal consequences heavily depend on the specific domain of
application. For example, applications to home robots can potentially alleviate the housework in a
middle-class family and contribute to the harmony therein.

Acknowledgments and Disclosure of Funding
YT acknowledges partial support from an MIT Presidential Fellowship and a graduate research
assistantship from the NSF BIGDATA grant (number 1741341). SS acknowledges partial support
from NSF-BIGDATA (1741341) and NSF-TRIPODS+X (1839258).

References[1] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds forreinforcement learning. In Proceedings of the 34th International Conference on Machine
Learning-Volume 70, pages 263–272. JMLR. org, 2017.
[2] Craig Boutilier, Richard Dearden, and Moises Goldszmidt. Exploiting structure in policy
construction. In IJCAI, volume 14, pages 1104–1113, 1995.
[3] Craig Boutilier, Thomas Dean, and Steve Hanks. Decision-theoretic planning: structural
assumptions and computational leverage. Journal of Artificial Intelligence Research, 11:1–94,
1999.
[4] Craig Boutilier, Richard Dearden, and Moisés Goldszmidt. Stochastic dynamic programmingwith factored representations. Artificial intelligence, 121(1-2):49–107, 2000.
[5] Doran Chakraborty. Sample efficient multiagent learning in the presence of Markovian agents.
Springer, 2014.
[6] Doran Chakraborty and Peter Stone. Structure learning in ergodic factored MDPs without
knowledge of the transition function’s in-degree. In Proceedings of the 28th International
Conference on Machine Learning (ICML-11), pages 737–744. Citeseer, 2011.
[7] Xiaoyu Chen, Jiachen Hu, Lihong Li, and Liwei Wang. Efficient reinforcement learning infactored MDPs with application to constrained RL. arXiv preprint arXiv:2008.13319, 2020.
[8] Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed-horizon reinforcement learning. In Advances in Neural Information Processing Systems, pages 2818–2826,
2015.
[9] Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: towards
accountable reinforcement learning. arXiv preprint arXiv:1811.03056, 2018.
[10] Thomas Degris and Olivier Sigaud. Factored Markov decision processes. In Olivier Sigaud andOlivier Buffet, editors, Markov Decision Processes in Artificial Intelligence, chapter 4, pages
99–126. Wiley Online Library, 2013.
[11] Thomas Degris, Olivier Sigaud, and Pierre-Henri Wuillemin. Learning the structure of factored
Markov decision processes in reinforcement learning problems. In Proceedings of the 23rd
international conference on Machine learning, pages 257–264, 2006.
[12] Carlos Diuk, Lihong Li, and Bethany R Leffler. The adaptive k-meteorologists problem and its
application to structure learning and feature selection in reinforcement learning. In Proceedingsof the 26th Annual International Conference on Machine Learning, pages 249–256, 2009.
[13] Yonathan Efroni, Nadav Merlis, Mohammad Ghavamzadeh, and Shie Mannor. Tight regretbounds for model-based reinforcement learning with greedy policies. In Advances in Neural
Information Processing Systems, pages 12203–12213, 2019.
10

[14] Carlos Guestrin, Daphne Koller, and Ronald Parr. Max-norm projections for factored MDPs. In
IJCAI, volume 1, pages 673–682, 2001.
[15] Carlos Guestrin, Daphne Koller, and Ronald Parr. Multiagent planning with factored MDPs. In
Advances in neural information processing systems, pages 1523–1530, 2002.
[16] Carlos Guestrin, Relu Patrascu, and Dale Schuurmans. Algorithm-directed exploration formodel-based reinforcement learning in factored MDPs. In ICML, pages 235–242. Citeseer,
2002.
[17] Carlos Guestrin, Daphne Koller, Ronald Parr, and Shobha Venkataraman. Efficient solution
algorithms for factored MDPs. Journal of Artificial Intelligence Research, 19:399–468, 2003.
[18] Zhaohan Daniel Guo and Emma Brunskill. Sample efficient learning with feature selection forfactored MDPs. In Proceedings of the 14th European Workshop on Reinforcement Learning.
EWRL, 2018.
[19] Assaf Hallak, François Schnitzler, Timothy Mann, and Shie Mannor. Off-policy model-basedlearning under unknown factored dynamics. In International Conference on Machine Learning,
pages 711–719, 2015.
[20] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement
learning. Journal of Machine Learning Research, 11(Apr):1563–1600, 2010.
[21] Chi Jin. Lecture 12: Lower bound for MDP. Lecture notes in ELE524: foundations ofreinforcement learning, Princeton University, 2020. Spring Semester.
[22] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is Q-learning provably
efficient? In Advances in Neural Information Processing Systems, pages 4863–4873, 2018.
[23] Sham Kakade, Mengdi Wang, and Lin F Yang. Variance reduction methods for sublinear
reinforcement learning. arXiv preprint arXiv:1802.09184, 2018.
[24] Michael Kearns and Daphne Koller. Efficient reinforcement learning in factored MDPs. In
IJCAI, volume 16, pages 740–747, 1999.
[25] Daphne Koller and Ron Parr. Policy iteration for factored MDPs. In Proceedings of the 17th
Conference on Uncertainty in Artificial Intelligence, pages 326–334, 2000.
[26] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. preprint, page 28, 2018.
[27] Andreas Maurer and Massimiliano Pontil. Empirical Bernstein bounds and sample variancepenalization. arXiv preprint arXiv:0907.3740, 2009.
[28] Ian Osband and Benjamin Van Roy. Near-optimal reinforcement learning in factored MDPs. In
Advances in Neural Information Processing Systems, pages 604–612, 2014.
[29] Ian Osband and Benjamin Van Roy. Why is posterior sampling better than optimism forreinforcement learning? In Proceedings of the 34th International Conference on Machine
Learning-Volume 70, pages 2701–2710. JMLR. org, 2017.
[30] Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via
posterior sampling. In Advances in Neural Information Processing Systems, pages 3003–3011,
2013.
[31] Martin L Puterman. Markov decision processes: discrete stochastic dynamic programming.
John Wiley & Sons, 2014.
[32] Julia Radoszycki, Nathalie Peyrard, and Régis Sabbadin. Solving F3 MDPs: collaborative
multiagent Markov decision processes with factored transitions, rewards and stochastic policies.
In International Conference on Principles and Practice of Multi-Agent Systems, pages 3–19.
Springer, 2015.
[33] Aviv Rosenberg and Yishay Mansour. Oracle-efficient reinforcement learning in factored MDPs
with unknown structure. arXiv preprint arXiv:2009.05986, 2020.
11

[34] Dale Schuurmans and Relu Patrascu. Direct value-approximation for factored MDPs. In
Advances in Neural Information Processing Systems, pages 1579–1586, 2002.
[35] Max Simchowitz and Kevin G Jamieson. Non-asymptotic gap-dependent regret bounds fortabular MDPs. In Advances in Neural Information Processing Systems, pages 1151–1160, 2019.
[36] Sungryull Sohn, Hyunjae Woo, Jongwook Choi, and Honglak Lee. Meta reinforcement learningwith autonomous inference of subtask dependencies. In International Conference on Learning
Representations, 2020.
[37] Alexander L Strehl. Model-based reinforcement learning in factored-state MDPs. In 2007 IEEE
International Symposium on Approximate Dynamic Programming and Reinforcement Learning,
pages 103–110. IEEE, 2007.
[38] Alexander L Strehl, Carlos Diuk, and Michael L Littman. Efficient structure learning infactored-state MDPs. In AAAI, volume 7, pages 645–650, 2007.
[39] István Szita and András Lőrincz. Optimistic initialization and greediness lead to polynomial
time learning in factored MDPs. In Proceedings of the 26th annual international conference on
machine learning, pages 1001–1008, 2009.
[40] Martin J Wainwright. High-dimensional statistics: a non-asymptotic viewpoint, volume 48.
Cambridge University Press, 2019.
[41] Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger.
Inequalities for the L1 deviation of the empirical distribution. Hewlett-Packard Labs, Tech. Rep,
2003.
[42] BP Welford. Note on a method for calculating corrected sums of squares and products. Technometrics, 4(3):419–420, 1962.
[43] Ziping Xu and Ambuj Tewari. Near-optimal reinforcement learning in factored MDPs: oracleefficient algorithms for the non-episodic setting. arXiv preprint arXiv:2002.02302, 2020.
[44] Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. arXiv preprint
arXiv:1901.00210, 2019.
[45] Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learning
via reference-advantage decomposition. arXiv preprint arXiv:2004.10019, 2020.

12