Oracle-Efficient Regret Minimization in Factored MDPs with Unknown Structure

Abstract:
We study regret minimization in non-episodic factored Markov decision processes (FMDPs), where all existing algorithms make the strong assumption that the factored structure of the FMDP is known to the learner in advance. In this paper, we provide the first algorithm that learns the structure of the FMDP while minimizing the regret. Our algorithm is based on the optimism in face of uncertainty principle, combined with a simple statistical method for structure learning, and can be implemented efficiently given oracle-access to an FMDP planner. Moreover, we give a variant of our algorithm that remains efficient even when the oracle is limited to non-factored actions, which is the case with almost all existing approximate planners. Finally, we leverage our techniques to prove a novel lower bound for the known structure case, closing the gap to the regret bound of Chen et al. [2021].

heading: 1 Introduction
text: Reinforcement learning (RL) considers an agent interacting with an unknown stochastic environment with the aim of maximizing its expected cumulative reward. This is usually modeled by a Markov decision process (MDP) with a finite number of states. The vast majority of provably-efficient RL has focused on the tabular case, where the state space is assumed to be small. Starting with the UCRL2 algorithm [Jaksch et al., 2010], near-optimal regret bounds were proved [Azar et al., 2017, Fruit et al., 2018, Jin et al., 2018, Zanette and Brunskill, 2019, Efroni et al., 2019]. Unfortunately, many real-world RL applications involve problems with a huge state space, yielding the tabular MDP model impractical as it requires the regret to unavoidably scale polynomially with the number of states.
In many practical scenarios, prior knowledge about the environment can be leveraged in order to develop more efficient algorithms. A popular way to model additional knowledge about the structure of the environment is by factored MDPs (FMDPs; Boutilier et al. [1995, 1999]). The state of an FMDP is composed of d components, called factors, and each component is determined by only m other factors, called its scope. FMDPs arise naturally in many applications like games, robotics, image-based applications and production lines (where only neighbouring machines affect one another). The common property of all these examples is the huge state space exponential in d, but the very small scope size m (e.g., in images each pixel is a factor and it depends only on neighboring pixels).
The key benefit of FMDPs is the combinatorial state space that allows compact representation. That is, although the number of states is exponential in d, the FMDP representation is only exponential in m (which is much smaller) and polynomial in d. Early works [Kearns and Koller, 1999, Guestrin et al., 2002, Strehl, 2007, Szita and Lőrincz, 2009] show that FMDPs also reduce the sample complexity exponentially, thus avoiding polynomial dependence on the number of states. Recently, this was further extended to algorithms with near-optimal regret bounds [Osband and Van Roy, 2014, Xu and Tewari, 2020, Tian et al., 2020, Chen et al., 2021, Talebi et al., 2021]. However, all these works make the strong assumption that the underlying FMDP structure is fully known to the learner in advance.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
In this paper we provide the first regret minimization algorithm for FMDPs with unknown structure, thus solving an open problem from Osband and Van Roy [2014]. Our algorithm is built on a novel concept of consistent scopes and guarantees near-optimal √ T regret that scales polynomially with the FMDP encoding and is therefore exponentially smaller than the number of states (and the regret in tabular MDPs). Moreover, our algorithm features an innovative construction that can incorporate elimination of inconsistent scopes into the optimistic regret minimization framework, while maintaining computational efficiency given oracle-access to an FMDP planner. Keeping computational oracle-efficiency is a difficult challenge in factored MDPs and especially hard when structure is unknown, since the number of possible structure configurations is highly exponential. Furthermore, our algorithm easily accommodates any level of structure knowledge, and is therefore extremely useful when additional prior domain knowledge is available. We note that while structure learning in FMDPs was previously studied by Strehl et al. [2007], Diuk et al. [2009], Chakraborty and Stone [2011], Hallak et al. [2015], Guo and Brunskill [2017], none of them provide regret guarantees.
To make our algorithms compatible with existing approximate FMDP planners, we also study FMDPs with non-factored actions. To the best of our knowledge, existing planners require small non-factored action space which is not compatible with the FMDP regret minimization literature. To mitigate this gap, we show that even when the oracle is limited to non-factored actions, a variant of our algorithm can still be implemented efficiently and achieve similar near-optimal regret bounds.
Finally, we leverage the techniques presented in this paper to prove a novel lower bound for regret minimization in FMDPs with known structure. This is the first lower bound to show that the regret must scale exponentially with the scope size m, and the first to utilize connections between different factors in a non-trivial way (i.e., with scope size larger than 1). Furthermore, it improves previous lower bounds by a factor of √ d and closes the gap to the state-of-the-art regret bound of Chen et al. [2021], thus establishing the minimax optimal regret in this setting.
Our algorithms make oracle use of FMDP planners. However, even where an FMDP can be represented concisely, solving for the optimal policy may take exponentially long in the most general case [Goldsmith et al., 1997, Littman, 1997]. Our focus in this paper is upon the statistical aspect of the learning problem, and we therefore assume oracle-access to an FMDP planner. We emphasize that the oracle assumption appears in all previous regret minimization algorithms. Furthermore, except for the DORL algorithm of Xu and Tewari [2020], all previous algorithms run in time exponential in d even with access to a planning oracle (and known structure). We stress that in many cases of interest, effective approximate planners do exist [Boutilier et al., 2000, Koller and Parr, 2000, Schuurmans and Patrascu, 2001, Guestrin et al., 2001, 2003, Sanner and Boutilier, 2005, Delgado et al., 2011].

heading: 2 Preliminaries
text: An infinite-horizon average-reward MDP is described by a tuple M = (S,A, P,R), where S and A are finite state and action spaces, respectively, P : S ×A→ ∆S is the transition function1, and R : S ×A→ ∆[0,1] is the reward function with expectation r(s, a) = E[R(s, a)]. The interaction between the MDP and the learner proceeds as follows. The learner starts in an arbitrary initial state s1 ∈ S. For t = 1, 2, . . . , the learner observes the current state st ∈ S, picks an action at ∈ A and earns a reward rt sampled from R(st, at). Then, the environment draws the next state st+1 ∼ P (· | st, at) and the process continues. A policy π : S → A is a mapping from states to actions, and its gain is defined by the average-reward
criterion: λ(M,π, s) def= limT→∞ 1T E [∑T t=1 r(s t, π(st)) | s1 = s ] , where st+1 ∼ P (· | st, π(st)).
In order to derive non-trivial regret bounds, one must constrain the connectivity of the MDP [Bartlett and Tewari, 2009]. We focus on communicating MDPs, i.e., MDPs with finite diameter D <∞. Definition 1. Let T (s′ | M,π, s) be the random variable for the first time step in which state s′ is reached when playing a stationary policy π in an MDP M with initial state s. The diameter of M is defined as D(M) def= maxs6=s′∈S minπ:S→A E[T (s′ |M,π, s)].
For communicating MDPs, neither the optimal policy nor its gain depend on the initial state s1. We denote them by π?(M) = arg maxπ:S→A λ(M,π, s
1) and λ?(M) = λ(M,π?, s1), respectively. 1∆X denotes the set of distributions over a set X .
We measure the performance of the learner by the regret. That is, the difference between the expected gain of the optimal policy in T steps and the cumulative reward obtained by the learner up to time T , i.e., RegT (M) def = ∑T t=1 ( λ?(M)− rt ) , where rt ∼ R(st, at) and at is chosen by the learner.

heading: 2.1 Factored MDPs
text: Factored MDPs inherit the above definitions, but also possess some conditional independence structure that allows compact representation. We follow the factored MDP definition of Osband and Van Roy [2014], which generalizes the original definition of Boutilier et al. [2000], Kearns and Koller [1999] to allow a factored action space as well. We start with a definition of a factored set and scope operation.
Definition 2. A set X is called factored if it can be written as a product of n sets X1, . . . , Xn, i.e., X = X1 × · · · ×Xn. For any subset of indices Z = {i1, . . . , i|Z|} ⊆ {1, . . . , n}, define the scope set X[Z] = Xi1 × · · · ×Xi|Z| . Further, for any x ∈ X define the scope variable x[Z] ∈ X[Z] to be the value of the variables xi ∈ Xi with indices i ∈ Z. For singleton sets we write x[i] for x[{i}].
Next, we define the factored reward and transition functions. We use the notations X = S ×A for the state-action space, d for the number of state factors and n for the number of state-action factors.
Definition 3. A reward functionR is called factored overX = X1×· · ·×Xn with scopesZr1 , . . . , Zr` if there exist functions {Rj : X[Zrj ] → ∆[0,1]}`j=1 with expectations rj(x[Zrj ]) = E[Rj(x[Zrj ])] such that for all x ∈ X: R(x) = 1` ∑` j=1Rj(x[Z r j ]). Note that when a reward r = 1 ` ∑` j=1 rj is sampled from R(x), the learner observes every rj individually.
Definition 4. A transition functionP is called factored overX = X1×· · ·×Xn and S = S1×· · ·×Sd with scopes ZP1 , . . . , Z P d if there exist functions {Pi : X[ZPi ]→ ∆Si}di=1 such that for all x ∈ X
and s′ ∈ S: P (s′ | x) = ∏d i=1 Pi(s
′[i] | x[ZPi ]). That is, given a state-action pair x, factor i of s′ is independent of its other factors, and is determined only by x[ZPi ].
Thus, a factored MDP (FMDP) is defined by an MDP whose reward and transition functions are both factored, and is fully characterized by the tuple M = ( {Xi}ni=1, {Si, ZPi , Pi}di=1, {Zrj , Rj}`j=1 ) .
As opposed to previous works [Osband and Van Roy, 2014, Xu and Tewari, 2020, Tian et al., 2020, Chen et al., 2021] that assume known factorization, in this paper the learner does not have any prior knowledge of the scopes ZP1 , . . . , Z P d or Z r 1 , . . . , Z r ` , and they need to be learned from experience. However, the learner has a bound m on the size of the scopes, i.e., |ZPi | ≤ m and |Zrj | ≤ m ∀i, j. See remarks on unknown scope size and variable scope sizes in Appendix B.
Remark (FMDP encoding size). Let the action factorization A = Ad+1 × · · · × An, factor size W = max{max1≤i≤d |Si|,maxd+1≤i≤n |Ai|} and L = maxZ:|Z|=m |X[Z]|. The encoding size is O(dWL+ `L+(d+ `)m log n). Importantly, the encoding is only polynomial in d while the number of states W d is exponential. It is however exponential in the (much smaller) scope size as L ≈Wm.

heading: 3 Structure Learning in FMDPs
text: In order to keep sample efficiency even when the structure of the FMDP is unknown, the learner must be able to detect the actual scopes ZP1 , . . . , Z P d and Z r 1 , . . . , Z r ` . Let’s focus on learning the scopes for the transition function first, as the technique for the reward function is similar. Our structure learning approach is based on a simple yet powerful observation by Strehl et al. [2007]. Since the i-th factor of the next state depends only on the scope ZPi , an empirical estimate of Pi should remain relatively similar whether it is computed using ZPi or Z P i ∪ Z for any other scope Z ⊆ {1, . . . , n}.
Formally, define the empirical transition function for factor i based on scope Z at time step t as P̄ ti,Z(w | v) = Nti,Z(v,w)
max{NtZ(v),1} for every (v, w) ∈ X[Z]× Si, where N tZ(v) is the number of times we
have visited a state-action pair x such that x[Z] = v up to time step t, and N ti,Z(v, w) is the number of times this visit was followed by a transition to a state s′ such that s′[i] = w. Regardless of the additional scope Z, the expected value of P̄ t i,ZPi ∪Z ( s′[i] | x[ZPi ∪ Z] ) remains Pi ( s′[i] | x[ZPi ] ) .
We leverage this observation to define consistent scopes. A scope Z of size m is consistent for factor i if for every other scope Z ′ of size m, v ∈ X[Z ∪ Z ′] and w ∈ Si,∣∣P̄ ti,Z∪Z′(w|v)− P̄ ti,Z(w|v[Z])∣∣ ≤ 2 · ti,Z∪Z′(w|v), (1) where ti,Z(w | v) def = √ 18P̄ ti,Z(w|v)τt
max{NtZ(v),1} + 18τ
t
max{NtZ(v),1} is the radius of the confidence set, τ t =
log(6dWLt/δ) is a logarithmic factor and δ is the confidence parameter.
There are two important properties that hold by a simple application of Hoeffding inequality. First, the actual scope ZPi will always be consistent with high probability. Second, if a different scope Z is consistent, then the empirical estimates P̄ t
i,ZPi and P̄ ti,Z must be close, since both are close to
P̄ t i,ZPi ∪Z = P̄ t i,Z∪ZPi . Therefore, they are close to the true transition function Pi with high probability.
Thus, our approach for structure learning is to eliminate inconsistent scopes. In the next section we show how this idea can be combined with the method of optimism in face of uncertainty for regret minimization in FMDPs. This approach works similarly for learning the scopes of the reward function. Formally, define the empirical reward function for reward factor j based on scope Z at time t as r̄tj,Z(v) =
1 max{NtZ(v),1}
∑t−1 h=1 r h j · I{(sh, ah)[Z] = v} for every v ∈ X[Z], where I{·} is the
indicator. Similarly to the transitions, a scope Z of size m is reward consistent for reward factor j if for every other scope Z ′ of size m and v ∈ X[Z ∪ Z ′],∣∣r̄tj,Z∪Z′(v)− r̄tj,Z(v[Z])∣∣ ≤ 2 · tZ∪Z′(v) def= 2 ·√18τ t/max{N tZ∪Z′(v), 1}.

heading: 4 The SLF-UCRL Algorithm
text: Our algorithm Structure Learn Factored UCRL (SLF-UCRL) follows the known framework of optimism in face of uncertainty while learning the structure of the FMDP. A sketch is given in Algorithm 1 and the full algorithm can be found in Appendix A. Similarly to the UCRL2 algorithm [Jaksch et al., 2010], we split the time into episodes. In the beginning of every episode we compute an optimistic policy and play it for the entire episode. The episode ends once the number of visits to some v ∈ X[Z ∪ Z ′] is doubled, where Z 6= Z ′ are two scopes of size m. That is, the number of times we visited a state-action pair x with x[Z ∪ Z ′] = v is doubled. Note that the standard doubling technique of Jaksch et al. [2010], i.e., when the number of visits to some state-action pair is doubled, will result in regret that depends polynomially on the size of the state-action space, which is exponentially larger than the size of its factors. Moreover, our doubling scheme is different than Xu and Tewari [2020], where the episode size grows arithmetically. This allows us to obtain tighter regret bound that depends on the different sizes of all the factors, and not just the biggest one L ≈Wm. While optimism is a standard framework for regret minimization, our algorithm features two novel techniques to handle unknown structure. First, we show how structure learning can be combined with optimism through the concept of consistent scopes. This already gives an algorithm with bounded regret, but requires exponential running time and space complexity. Second, in Sections 4.1 and 4.2 we present a novel construction that allows to compute the optimistic policy in an oracle-efficient and space efficient manner, although the number of consistent factored structures is clearly exponential.
For every factor i we maintain a set Z̃ki of its consistent scopes up to episode k (we keep a similar set R̃kj for every reward factor j). In the beginning of the episode we construct an optimistic MDP M̃k out of all possible configurations of consistent scopes. We then compute the optimal policy π̃k of M̃k, extract the optimistic policy πk and play it throughout the episode. In what follows, we denote by tk the first time step of episode k, and slightly abuse notation by using P̄ k, k, Nk for P̄ tk , tk , N tk . Remark (Computational complexity). The computational complexity of our algorithm scales exponentially with the scope size m, but polynomially with the number of factors n, d, `. This dependence is unavoidable [Abbeel et al., 2006, Strehl et al., 2007] since the number of possible scopes is ( n m
) and the size of the FMDP encoding is also exponential in m. In fact, the complexity of all previous regret minimization algorithms (except Xu and Tewari [2020]) is exponential even in the number of factors d and not just in the scope size m. Since FMDPs with large scope size are not practical (their representation is huge), one should think of m as very small compared to n, d, `.
Algorithm 1 SLF-UCRL Sketch Input: δ,m, S = {Si}di=1, S ×A = X = {Xi}ni=1. Initialize visit counters and sets of consistent scopes. for k = 1, 2, . . . do
Start new episode k, and compute empirical transition function P̄ k and confidence bounds k. Eliminate inconsistent scopes (Algorithm 2), and construct optimistic MDP M̃k. Compute optimal policy π̃k of M̃k using oracle, and extract optimistic policy πk. Execute policy πk until there are scopes Z 6= Z ′ of size m and v ∈ X[Z ∪ Z ′] such that the number of visits to some state-action pairs x with x[Z ∪ Z ′] = v, is doubled.
end for
Algorithm 2 Eliminate Inconsistent Scopes Sketch
for i = 1, . . . , d and Z ∈ Z̃k−1i do for Z ′ ⊆ {1, . . . , n} of size m and v ∈ X[Z ∪ Z ′] and w ∈ Si do
if |P̄ ki,Z∪Z′(w | v)− P̄ ki,Z(w | v[Z])| > 2 · ki,Z∪Z′(w | v) then Eliminate inconsistent scope: Z̃ki ← Z̃ki \ {Z}, and BREAK.
end if end for
end for # Inconsistent reward scopes are eliminated from R̃kj similarly, for every j = 1, . . . , `.
Remark (Partial structure knowledge). The SLF-UCRL algorithm easily accommodates any level of knowledge regarding the structure. That is, the consistent scopes sets can be adjusted if some scopes are known or have a known compact representation (e.g., decision trees). The algorithm’s complexity and regret scale naturally with the level of structure knowledge, making it extremely useful when specific domain knowledge is available (e.g., dynamics of some physical systems in robotics).

heading: 4.1 Constructing the Optimistic MDP M̃k
text: As our construction generalizes the one of Xu and Tewari [2020] to the case of unknown structure, we start with a brief overview of their method. With known structure, their optimistic MDP keeps the same state space S but has an extended action space A× S, where playing action (a, s′) in state s corresponds to playing action a and using a transition function that puts all the uncertainty in the direction of state s′, such that for each factor i the L1 distance between the empirical and optimistic transition functions is bounded by ∑ w∈Si k i,ZPi (w | (s, a)[ZPi ]) = Õ (√ |Si|/Nk ZP i ( (s,a)[ZPi ] )) .
Formally, let Wki,Z(w | v) = min{ ki,Z(w | v), P̄ ki,Z(w | v)} and then the probability that in the optimistic MDP the i-th factor of the next state is w after playing (a, s′) in state s is
P̄ ki,ZPi
( w | (s, a)[ZPi ] ) −Wki,ZPi ( w | (s, a)[ZPi ] ) + I{w = s′[i]} · ∑ w′∈Si Wki,ZPi ( w′ | (s, a)[ZPi ] ) .
The j-th reward factor of this action is the empirical estimate plus an additional optimistic bonus, i.e., min {
1, r̄kj,Zrj ( (s, a)[Zrj ] ) + kZrj ( (s, a)[Zrj ] )} .
Notice that this optimistic MDP is factored, that the number of state-action factors increased by d, and that the scope size increased by only 1. Thus, this method indeed keeps oracle-efficiency.
The naive way to extend this idea to unknown structure is to compute the optimistic MDP for every configuration of consistent scopes, and pick the most optimistic one, i.e., the configuration in which the optimal gain is the biggest. However, this requires exponential number of calls to the oracle.
Instead, we propose to extend the action space even further so the policy can pick the scopes as well as the actions. That is, the extended action space is Ãk = A×S × Z̃k1 × · · · × Z̃kd ×R̃k1 × · · · × R̃k` , and playing action ã = (a, s′, Z1, . . . , Zd, z1, . . . , z`) in state s corresponds to playing action a, using a reward function according to scopes z1, . . . , z`, and using a transition function according to
scopes Z1, . . . , Zd that puts all the uncertainty in the direction of s′. Formally, for every reward factor j define r̃kj (x̃) = min { 1, r̄kj,zj ( (s, a)[zj ] ) + kzj ( (s, a)[zj ] )} , where x̃ = (s, ã). For every factor i and w ∈ Si define P̃ ki (w|x̃) def = P̄ ki,Zi(w | (s, a)[Zi])−W k i,Zi(w | (s, a)[Zi])
+ I{w = s′[i]} · ∑ w′∈Si Wki,Zi(w ′ | (s, a)[Zi]). (2)
Unfortunately, although this elegant construction looks like a factored MDP, it is in fact not factored. Specifically, the transition and reward functions become non-factored because each factor can now depend on all the factors of the state-action space (this is determined by the policy choosing the scopes), i.e., the scope size is now n. Nevertheless, in the following section we show that the optimal policy of this optimistic MDP can still be computed by the oracle. To that end, we construct a slightly larger MDP that has the same optimal policy and gain, while being factored with small scopes.

heading: 4.2 From Optimistic MDP M̃k to Optimistic Factored MDP M̂k
text: We construct a factored MDP M̂k that simulates exactly the dynamics of the optimistic MDP M̃k. The idea is to stretch each time step to 2 + log n steps. In the first step the policy chooses a combined action ã as described in Section 4.1, in the next log n steps relevant factors are extracted according to the policy’s choices, and in the last step the transition is performed according to P̃ k (Eq. (2)). Since the relevant factors for the transition were already extracted, this time the scope size remains small.
For M̂k, we keep the extended action space Âk = Ãk and extend the state space Ŝk to contain the state, steps counter, the policy’s picked scopes and optimistic assignment state, and a “temporary” work space. Formally, Ŝk = S×{0, 1, . . . , log n+1}×S×Z̃k1×· · ·×Z̃kd×R̃k1×· · ·×R̃k`×Ω(d+`)m, where S keeps the state, {0, 1, . . . , log n+ 1} is a counter of the current step within the actual time step, and S × Z̃k1 × · · · × Z̃kd × R̃k1 × · · · × R̃k` keeps the policy’s picked scopes and optimistic assignment state. For each factor i (also for each reward factor j) and index e ∈ {1, . . . ,m}, we have a separate “temporary” work space Ω = ωn × ωn/2 × · · · × ω2 × ω that allows extracting the e-th element of the scope for the transition of factor i while maintaining small scope sizes. Here, ω = ( ⋃d i=1 Si) ∪ ( ⋃n i=d+1Ai) keeps one factor (state or action), so |ω| = W .
A state s in M is mapped to (s, 0,⊥)2 and taking action ã = (a, s′, Z1, . . . , Zd, z1, . . . , z`) results in a deterministic transition to (s, 1, s′, Z1, . . . , Zd, z1, . . . , z`, τ), where τ = (τi,e) ∈ Ω(d+`)m. The state-action pair (s, a) is copied to each of the work spaces, i.e., τi,e = (s, a,⊥). The next log n steps are used to extract the relevant scopes. The policy has no effect in these steps since a, s′ and the chosen scopes are now encoded into the state. In these log n steps, for each (i, e), we eliminate half of τi,e in each step according to its chosen scope Zi, until we are left with the e-th factor of (s, a)[Zi]. The elimination steps require scopes of size only 4 since each factor of the next step needs to choose between two factors from the previous step (while considering the scope Zi chosen by the policy and the counter). The final step performs the transition according to P̃ k, but notice that now it only requires scopes of size m+ 3. The reason is that now (s, a)[Zi] has a fixed location within the state, i.e., (s, a)[Zi][e] is in the last factor of τi,e (in addition, the counter, s′[i] and s[i] need to be taken into consideration). At this point the agent also gets the reward r̃k, whereas the reward in all other time steps is 0. Similarly to the transitions, the reward scopes are of size m+ 1 because (s, a)[zj ] has a fixed location (and the counter should also be considered). For more details see Appendix A.
It is easy to see that M̂k simulates M̃k exactly, because every 2 + log n steps are equivalent to one step in M̃k. In terms of computational complexity, any planner that is able to solve M can also solve M̂k, since it is factored and polynomial in size when compared to M . Indeed, the scope size is m+ 3 (compared to m), the number of state factors is 3d+ `+ 1 + 2nm(d+ `) (compared to d), the number of action factors is n+ d+ ` (compared to n− d), the size of each state factor is bounded by max{W, ( n m ) } (compared to W ), and finally the size L is replaced by max{L, ( n m ) }W 2(2 + log n). Given the optimal policy π̂k for M̂k, we can easily extract the optimal policy π̃k(s) = π̂k((s, 0,⊥)) for M̃k, and the optimistic policy πk(s) = π̃k(s)[1] = π̂k((s, 0,⊥))[1] for the original MDP M .
2We use ⊥ to indicate that the rest of the state is irrelevant.

heading: 4.3 Avoiding Large Factors
text: One shortcoming of the above construction is that the factor size may be significantly larger, i.e., ( n m ) instead of W in the original FMDP. As mentioned before, m is considered to be small, and yet one might prefer to keep the factor size small at the expense of adding a few extra factors and increasing the reward scope size by 1. In what follows, we show that this is indeed possible because each action factor we added for choosing a consistent scope is already factored internally into m factors of size n.
We view the extended action space as A× S × {1, . . . , n}m(d+`) which has n+m(d+ `) factors of size max{W,n}. Similarly, we can view the state space as 2d+ 1 +m(d+ `) + 2nm(d+ `) factors of the same size. Luckily we can still keep the same m+ 3 scope size, since the consistent scopes are used only in the log n intermediate steps in which the scope size was 4 and now becomes m+ 3. However, this gives rise to a new problem: now the policy might choose inconsistent scopes because the action space is not restricted to consistent scopes anymore. To overcome this issue, we enforce the optimal policy in M̂k to use only consistent scopes by adding 2(d + `) binary factors. These factors make sure that any policy that uses an inconsistent scope will never earn a reward.
All the new binary factors start as 1, and we refer to them as bits. When the counter is 0, the i-th bit becomes 0 if the chosen scope for factor i is inconsistent. Similarly, the (d + j)-th bit checks the chosen scope for reward factor j. This requires them to have scope size m + 2, and in the next log(d + `) steps we extract out of them one bit that says if an inconsistent scope was chosen. This is done similarly to the extraction of relevant scopes and requires the counter to reach max{log(d+ `), log n}+ 1 instead of log n+ 1. Finally, when giving a reward in the last step, the reward function also considers the extracted bit and gives 0 reward if it is 0. Since it cannot turn back to 1, this bit ensures that a policy that uses an inconsistent scope has a gain of 0.

heading: 4.4 Regret Analysis
text: In Appendix B we prove the following regret bound for SLF-UCRL. Here we review the main ideas.
Theorem 1. Running SLF-UCRL on a factored MDP with unknown structure ensures, with probability at least 1− δ,
RegT (M) = Õ ( d∑ i=1 ∑ Z:|Z|=m D √ |Si||X[ZPi ∪ Z]|T + 1 ` ∑̀ j=1 ∑ Z:|Z|=m √ |X[Zrj ∪ Z]|T ) .
In the worst-case regret, this regret bound becomes RegT (M) = Õ( ( n m ) dD √ WL2T ). In comparison to the regret bound of Xu and Tewari [2020] for the known structure case, our bound is worse by only a factor of ( n m )√ L. While the exponential dependence in m (hidden already in L) is unavoidable, it
is an important open problem whether the multiplicative dependence in ( n m ) is necessary (note that it directly stems from the level of structure knowledge and may be much smaller with some domain knowledge). We believe that the √ L factor can be avoided with methods such as the meteorologist algorithm of Diuk et al. [2009], since it comes from our simple structure learning method, i.e., comparing all pairs of scopes Z 6= Z ′ of size m. Still, it is highly unclear how to incorporate these methods in a regret minimization algorithm. Finally, we stress that ignoring the unknown factored structure leads to regret polynomial in the number of states, which is exponential compared to ours.
Proof sketch. Regret analysis for optimistic algorithms has two main parts: (1) optimism - show that the optimal gain in the optimistic model M̃k is at least as large as λ?(M) for all episodes k with high probability; (2) deviation - bound the difference between the optimistic policy’s gains in M and M̃k.
Optimism follows directly from the consistent scopes definition and standard concentration inequalities. Specifically, since the true scopes are always consistent with high probability, the optimistic policy in the optimistic model maximizes its gain while choosing scopes from a set that contains the true scopes. For the deviation, we need to bound the distance between the true and optimistic dynamics along the trajectory visited in each episode k. That is, we need to relate ∆t = ‖P̃ k(·|x̃t)−P (·|xt)‖1 to the confidence radius k, where π̃k(st) = (at, s′t, Zt1, . . . , Z t d, z t 1, . . . , z t `), x
t = (st, at) and x̃t = (st, π̃k(st)). Then, we can sum the confidence radii over t = 1, . . . , T and get the final bound.
To that end, we utilize the transition factorization to bound ∆t ≤ ∑d i=1 ∥∥P̃ ki (·|x̃t)− Pi(·|xt[ZPi ])∥∥1. Then, for each i we can use the definition of the optimistic transition function P̃ k (Eq. (2)) to get
∆t . d∑ i=1 ∥∥P̄ ki,ZPi (· | xt[ZPi ])− Pi(· | xt[ZPi ])∥∥1 + d∑ i=1 ∥∥P̄ ki,Zti (· | xt[Zti ])− P̄ ki,ZPi (· | xt[ZPi ])∥∥1. The first term measures the difference between the empirical and true dynamics on the correct scopes ZPi and can therefore be bounded with standard concentration inequalities. For the second term we utilize the fact that the chosen scopes Zti must be consistent. Therefore, we can bound it using Eq. (1) by ≈ ∑d i=1 ∑ w∈Si k i,ZPi ∪Zti (w | xt[ZPi ∪ Zti ]) . ∑d i=1 √ |Si|/Nk ZP i ∪Zt i (xt[ZPi ∪Z t i ]).

heading: 5 Factored MDPs with Non-Factored Actions
text: So far we assumed that both the state and action spaces are factored. While this model is very general, it also requires an oracle that can solve it. However, almost all existing approximate FMDP planners do not address factored action spaces. Moreover, implicitly they assume that the action set is small (or with very unique structure), as they pick a greedy policy with respect to some Q-function estimation.
To make our algorithm more compatible with approximate planners, in this section we do not assume that the action space is factored, and our oracle is limited to such FMDPs. We show that a variant of our algorithm can still achieve similar regret bounds and maintain computational efficiency. This makes our algorithm much more practical than the DORL algorithm of Xu and Tewari [2020]. The FMDP definition we adopt assumes that the state space is factored S = S1 × · · · × Sd, and that the transition function is factored, only with respect to the state space, in the following manner. The factored reward function is defined similarly, but to simplify presentation, we assume it is known. Definition 5. Transition functionP is called factored over S = S1×· · ·×Sd with scopesZP1 , . . . , ZPd if there exist functions {Pi : S[ZPi ]×A→ ∆Si}di=1 s.t. P (s′ | s, a) = ∏d i=1 Pi(s ′[i] | s[ZPi ], a).
We focus on known structure to convey the main ideas, but in Appendix E we show that the methods presented here can be extended to handle unknown structure. The DORL algorithm [Xu and Tewari, 2020] highly relies on the factored action space, because the optimistic MDP is defined using the huge (yet factored) action space A× S that allows incorporating an optimistic estimate of the dynamics. Instead, we propose to spread the transition across 2 + d steps. In the first step the policy picks an action, step i+ 1 performs the i-th factor optimistic transition, and the last step completes the move.
Formally, the state space of M̃k is S̃ = S × {0, 1, . . . , d+ 1} ×A× S × {0, 1}, where S keeps the state, {0, 1, . . . , d+1} is a counter of the current step within the actual time step, A keeps the policy’s chosen action, another S helps perform the transition, and the last bit validates that the chosen actions are legal. The action space of M̃k is Ã = A ∪ ( ⋃d i=1 Si). The size of Ã is max{|A|,W} which is exponentially smaller compared to |A|W d in the original construction of Xu and Tewari [2020]. A state s in M is mapped to (s, 0,⊥) and action a ∈ A deterministically transitions to (s, 1, a,⊥), while the other actions are not legal at this state. Picking an illegal action turns the last bit to 0 (it starts as 1), canceling all rewards similarly to Section 4.3. In state (s, i, a, w1, . . . , wi−1,⊥), legal actions are Si, and action w ∈ Si transitions to state (s, i+ 1, a, w1, . . . , wi−1, wi,⊥) with probability
P̄ ki,ZPi (wi | s[ZPi ], a)−Wki,ZPi (wi | s[Z P i ], a) + I{wi = w} · ∑ w′∈Si Wki,ZPi (w ′ | s[ZPi ], a).
Finally, (s, d+ 1, a, w1, . . . , wd, b) transitions deterministically to (s′, 0,⊥) for s′ = (w1, . . . , wd). Similarly to Section 4.1, one can see that the scope size is now m+ 3, the number of factors is 2d+ 3, the size of each factor is bounded by max{W, |A|, d+ 2}, and that the number of actions remains small. Thus we can use the limited oracle in order to solve the optimistic MDP. As for the regret bound, it is easy to verify that optimism still holds, but it is not clear that we can still bound the deviation because now the policy in the optimistic model has significantly more “power” – it chooses the uncertainty direction for factor i after the realizations for factors 1, . . . , i− 1 of the next state are already revealed. Next, we show that it can still be bounded similarly since the actual action of the policy is chosen before the realizations are revealed (the action is chosen in the first of d+ 1 steps).
To see that, consider an MDP M ′ that models the exact same process as M but resembles our optimistic MDP as each time step is stretched over d + 2 steps. The state space of M ′ is S̃ like M̃k, and taking action a ∈ A in state (s, 0,⊥) transitions to state (s, 1, a,⊥). Then, the policy has no effect for d + 1 steps and the action is embedded in the state. For every i and wi ∈ Si, the probability of transitioning from (s, i, a, w1, . . . , wi−1,⊥) to (s, i + 1, a, w1, . . . , wi−1, wi,⊥) is simply Pi(wi | s[ZPi ], a), and finally, (s, i, a, w1, . . . , wd, b) transitions to (w1, . . . , wd, 0,⊥). Clearly, playing policy π inM is equivalent to playing policy π′ inM ′ such that π′((s, 0,⊥)) = π(s). Therefore, λ?(M ′) = λ
?(M) d+2 and we can analyze the regret in M ′ to obtain a similar regret bound to Xu and Tewari [2020]. The full algorithm which we call Non-Factored Actions DORL (NFA-DORL) is found in Appendix C and the full proof of the following regret bound is found in Appendix D. Theorem 2. Running NFA-DORL on a factored MDP with non-factored actions and known structure ensures with probability 1− δ, RegT (M) = Õ( ∑ iD √ |Si||S[ZPi ]||A|T + 1` ∑ j √ |S[Zrj ]||A|T ).

heading: 6 Lower Bound
text: In Appendix F we prove the following lower bound for regret minimization in factored MDPs. Theorem 3. Let d > m > 0. For any algorithm there exists an FMDP with 3d + log d state factors of size at most max{W + 1, log d+ 2}, non-factored action space of size |A|, and scope size 1 + max{m, log d}, such that E[RegT (M)] = Ω (√ d log dW m|A|T ) .
The proof leverages our techniques (e.g., propagating rewards through multi-step factored transitions) in order to embed dWm multi-arm bandit (MAB) problems into a factored MDP, and make sure that they must be solved sequentially and not in parallel. It features a sophisticated construction to utilize connections between factors in such a way that in each step the learner gets information on just a single MAB, forcing her to solve all the MABs one by one. Our construction is also the first to feature arbitrary scope size m, while previous constructions simply take d unrelated factors with scope size 1. As a result, our construction highlights the unique hardness that factored structure might introduce.
This is the first lower bound to show that the regret must scale exponentially with the scope size m. Moreover, it improves on previous lower bounds [Tian et al., 2020, Chen et al., 2021] by a factor of√ d, and matches the state-of-the-art regret bound of Chen et al. [2021] in the known structure case. Thus, our lower bound is tight, proving that this is indeed the minimax optimal regret for FMDPs with known structure. Yet, two intriguing question are left open. First, the optimal regret algorithm of Chen et al. [2021] runs in exponential time, and achieving the same regret with an oracle-efficient algorithm seems like a difficult challenge. Second, extending our lower bound to the unknown structure case is another challenging future direction that can advance us towards discovering whether unknown structure indeed introduces additional hardness in terms of optimal regret.
7 Experiments
We test our algorithm on the SysAdmin domain [Guestrin et al., 2003] – a network of servers connected by some topology, where failing servers affect the probability of their neighbors to fail and the admin chooses which server to reboot at each time step. Our experiments show that the performance of SLF-UCRL is comparable to that of Factored-UCRL [Osband and Van Roy, 2014] that knows the factored structure in advance, and significantly better than the performance of UCRL [Jaksch et al., 2010] that completely ignores the factorization. Figure 1 shows that,
for circular topology with 4 servers (i.e., 4 state factors and scope size 3), SLF-UCRL eliminates the wrong scopes (right figure), and has similar regret to Factored-UCRL (left figure). “SLF-UCRLi” refers to i factors whose scope needs to be learned, so SLF-UCRL4 has no knowledge of the structure.
For implementation details and more experiments on different topologies and sizes, see Appendix G.

heading: Acknowledgements
text: This project has received funding from the European Research Council (ERC) under the European Union’sHorizon 2020 research and innovation program (grant agreement No. 882396), by the Israel Science Foundation(grant number 993/17), Tel Aviv University Center for AI and Data Science (TAD), and the Yandex Initiative for Machine Learning at Tel Aviv University

Review summaries:
This paper studies regret minimization in Factored MDPs (FMDPs) under the average-reward criterion, and without assuming prior knowledge on the factorization structure. The authors present the SLF-UCRL algorithm, a UCRL2-style algorithm that borrows some elements from DORL, and analyze its regret. The authors also study the case of FMDPs with non-factored action-space and present an algorithm for this setup. This is important to ensure compatibility with most known approximate efficient planners for FMDPs. Yet another worth noting contribution of the paper is to present a regret lower bound for the case of known structure, which improves upon existing ones in the literature and matches recent regret upper bounds in the episodic setting.  

This paper studies regret minimization in factored MDPs with unknown structure. The algorithm combines optimism in the face of uncertainty principle and a structure learning approach. With planning oracles, both the sample and computation complexity depend polynomially on the problem size. This paper also provides a regret lower bound and empirical evaluations.  

This work concerns reinforcement learning in factored MDPs. The first part of the work combines previous work on regret minimization in FMDPs using a planning oracle (following prior work by Osband and Van Roy and Xu and Tewari) with work on structure learning in FMDPs. In this context, structure learning means the following: in order for FMDPs to possess compact transition and reward functions, one typically assumes they are represented by graphical models in which each factor depends on a limited number of factors from the previous step; the structure learning problem is essentially to identify these dependencies. Here, Xu and Tewari's algorithm is modified so that it identifies the structure during learning, while maintaining its regret bound. The previous works in this area provided sample complexity bounds rather than regret bounds. In addition to the regret bounds, experiments are provided, demonstrating that the algorithm is somewhat competitive with the algorithm of Osband and Van Roy that is provided with the dependency structure.  In more detail, as in the algorithm of Xu and Tewari, this algorithm uses the idea of augmenting the actions that originally appeared in Jaksch et al.; essentially, in addition to allowing the planner to select an action in the actual MDP, Xu and Tewari allow the planner to select one of the extremal transition functions. Here, the possible dependency structures are added to the options presented to the planner.  An additional transformation is proposed that converts the resulting large action space to a sequence of moves in an augmented state space. The same transformation could be applied to the algorithm of Xu and Tewari as well as the unknown structure algorithm, so this could be considered a second, separate part of the work.  The final part of the work is an improved lower bound that in particular shows that regret must depend exponentially on the scope sizes, and asymptotically matches the regret obtained by some recent works (e.g., Tian et al. 2020)