Oracle-Efficient Regret Minimization in Factored MDPs with Unknown Structure
Authors: Aviv Rosenberg
Yishay Mansour
Venue: NeurIPS 2021 Poster (2021)
Keywords: regret minimization
factored MDP
online learning
reinforcement learning theory
reinforcement learning
learning theory

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].

Oracle-Efficient Regret Minimization in Factored MDPs with Unknown Structure
Aviv Rosenberg Tel-Aviv University avivros007@gmail.cmm com
Yishay Mansour Tel-Aviv University and Google Research, Tel Aviv mansour@tau. ac.
Abstract
We study regret minimization in non-episodic factored Markov decision processes (FMDPs), where 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 the optimism in face of uncertainty principle, combined with a simple statistical method for structure learning, and can be implemented efficiently given pracle-access give a variant of our algorithm that remains efficient even when the oracle is limited non-factored actions, which the case with almost all existing approximate planners. Finally, we leverage our techniques to prove novel lower bound for the known structure case, closing the gap the regret bound of Chen al. [2021].
an FMDP planner. Moreover,
Introduction
Reinforcement learning (RL) considers an agent interacting with an unknown stochastic environment with the aim of maximizing its expected cumulative reward. This usually modeled by Markov decision process (MDP) with finite number of states. The vast majority of provably provably-effiiien effficient 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. [017 Fruit jet al.) 2018 Jin et al. 2018 Zanette and Brunskill 2019 Efroni al., 2019]. Unfortunately, many real-world RI. applications involve problems with 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 model additional knowledge about the structure of the environment is by factored MDPs (FMDPs; Boutilier et al. [1995 1999). The state of an FMDP composed of components, called factors, and each component determined by only m other factors, called its scope. FMDPs arise naturally in many applications like games, robotics, image-based 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 factor and 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 only exponential in m (which is much smaller) and polynomial in d. Early works [Kearns and Koller 1999 Guestrin et al.) 2002 [ttrhl 2007 Szita and Lörinez 2009 show that FMDPs also reduce the sample complexity exponentially, thus avoiding polynomial dependence on the number of states. Recently, this was further extended algorithms with near-optimal regret bounds OSband and Van Roy [014 [u and Tewari 2020 (Tian et al. [2000] Chen et al. 2021 Talebi et al.) 2021]. However, all these works make
strong assumption that the underlying FMDP structure fully known to the learner advance.
35th Conference on Neural Information Processing Systems (NcurIPS 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 VT 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-efiiciency 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, 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 Sttehl et al. 20077] Diuk et al. 2009 Chakraborty and Hallak et al. 2015) Guo and Brunskill [017]. none of them provide regret guarantees.
Stone 201
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 factor of vd and closes the gap to the sfate-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 repre- sented 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 Xu and Tewari [020]. all previous algorithms run in time exponential in d even with access to 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]
2 Preliminaries
An infinite-horizon average-reward MDP is described by a tuple M = (S, R), where S and A are finite state and action spaces, respectively, P: S x A + As is the transition functior and R: S x A + 1 is the reward function with expectation r(s, a) B[R(s, a)).
The interaction between the MDP and the learner proceeds as follows. The learner starts in an arbitrary initial state s E S. For t. = 1,,,.... the learner observes the current state s E S, picks an action at E A and earns a reward xf sampled from R(st,a²), Then, the environment draws the next state s1+ ~ P(- s², a') and the process continues.
policy क: : S > A is mapping from states to actions, and its gain is defined by the average-reward
criterion: X(M, n, 8) del
lim H E ((s,,(m(m(>')) (s*)) s7 = } where gh+1 P(. 8 (s*)).
In order to derive non-trivial regret bounds, one must constrain the connectivity of the MDP [Bartlet] and Tewari 2009]. We focus on communicating MDPs, i.e., MDPs with finite diameter D < 30. Definition 1. Let T(s' M,, 8) 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 del defined as D(M) max min EE[((') | M, s)]-
For communicating MDPs, neither the optimal policy nor its gain depend on the initial state s We denote them by π² (M) arg max X(M, π., s s') and X (M) X(M, n²,,"" r"'s)), respectively.
Ax denotes the of distributions over 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. ie., (M) def (A=(A>(M - r"), where pe R(s' a²) and a' is chosen by the learner.
2.1 Factored MDPs
Factored MDPs inherit the above definitions, but also possess some conditional independence structure that allows compact representation. We follow the factored MDP definition of afOband 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 it can be written as product of n sets XI...., .,,.................. i... X x x ... x Xn. For any subset of indices Z = {ii..... } S (1..... n). define the scope set [ = X1, x .... x Xi pi Further, for any x E X define the scope variable x [2] E X [2] to be the value of the variables xa E X; with indices i E Z. For singleton sets we write xr| for 2 zf{i)]-
Next, we define the factored reward and transition functions. We use the notations X = S A for the state-action space, for the number of state factors and n for the number of state-action factors.
Definition 3. A reward function R is called factored over X = X Xn, with scopes Z ...., Zi if there exist functions { RR3 [[3]] - A == with expectations ry (x()));) = [x such that for all x E X: R(x) = & ンラ [z(r(2])) Note that when a reward r = Σ rjy is sampled from R(x), the learner observes every ry individually.
Definition 4. A transition function P is called factored over X = Xxx...xxxXX and S S XS with scopes Zf,,... 2 if there exist functions {P: x[Z,'] + As, J such that for all x E X That is, given a state-action pair x. factor of s' is independent of its other factors, and is determined only by x[
and s' S: P(s' x)) IT (s ==(z))).
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 {x,); (S Z,P P. P.M. {Zj R, 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, this paper the learner does not have any prior knowledge of the scopes .i...., Zi or 2i,... Zý. and they need to be learned from experience.
However, the learner has a bound m on the size of the scopes, i.e., |z,²| < m and |z S m Vi,
See remarks unknown scope size and variable scope sizes in [Appeddxx B
Remark (FMDP encoding size). Let the action factorization = As+1 X X An, factor size W = max maax/maxe mmxx (s,), maxa+1gign [Ail) and L. = max mm |X The encoding size is Oddl L + fL + (d+ f)m n). Importantly, the encoding is only polynomial in d while the number of states Wd is exponential. It is however exponential in the (much smaller) scope size as L R m
3 Structure Learning in FMDPs
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 2 ,..., 2 and Zi...., Z.. 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 /ttrhl et al. [0077] Since the i-th factor of the next state depends only on the scope Z!" an empirical estimate of P. should remain relatively similar whether it is computed using z or 2,P U 7 for any other scope Z S nn..
Formally, define the empirical transition function for factor i based scope Z at time step t as (v.a0)
(1,2(W) v) max(N5(0).17 for every (v, w) E x x S;, where N (v) is the number of times we have visited a state-action pair x such that æ [Z] = v up to time step f, and N N (v, w) is the number of times this visit was followed by transition to state s' such that s'ii] = w. Regardless of the additional scope Z, the expected value of P iZzFuz (s((i) x 2 U Z)) remains P: (s((()) x (
3

---

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 21] and w E S.,
Pi,z (w/[ S 2. (wlo),
(I)
where <1,2(w | v) def V
1887 (w)e)r( (M5 max (v).T) is the radius of the confidence set, 7²
187
log(6dWLt/6) is a logarithmic factor and 5 is the confidence parameter.
There are two important properties that hold by simple application of Hoeffding inequality. First, the actual scope Z will always be consistent with high probability. Second, if a different scope Z is consistent, then the empirical estimates P ", and Pi,z must be close, since both are close to Pr Lzzfzz
P.. 1.zuZ. Therefore, they are close to the true transition function P. 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 F/ (e) m Ex r3 I[(s", a²) [Z] e} for every E x[Z], where If-} is the indicator. Similarly to the transitions, a scope Z of size m reward consistent for reward factor j
for every other scope Z' of size m and v E eXZUZZZ
(2)22 - (3,2((((1)) 2 22. def 2 . /18T hoff/mx(NN/ (U), 1}.
4 The SLF-UCRL Algorithm
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 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 E X U Z'] is doubled, where Z * 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. (2100). i.c., 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 obtaín tighter regret bound that depends on the different sizes of all the factors, and not just the biggest one L R W
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 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 Σ/ of its consistent scopes up to episode k (we keep a similar set R3 for every reward factor j). In the beginning of the episode we construct optimistic MDP A out of all possible configurations of consistent scopes. We then compute the optimal policy / of M extract the optimistic policy œ² and play it throughout the episode. In what follows, we denote by tx the first time step of episode k. and slightly abuse notation by using p& ek 2 for pta, e²x '
Remark (Computational complexity). The computational complexity of our algorithm scales expo- nentially with the scope size m. but polynomially with the number of factors n. d, f. This dependence is unavoidable [Abbeel et al. 2006 Strehl et al. 2007 since the number of possible scopes is (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, l.

---

Algorithm SLF-UCRL Sketch
Input: 6, m. S = ( S x A X {X;]
Initialize visit counters and sets of consistent scopes.
for k = 1,2,... do
Start episode k, and compute empirical transition function pe and confidence bounds e Eliminate inconsistent scopes (Algorithm 2). and construct optimistic MDP M²
Compute optimal policy n of M using oracle, and extract optimistic policy **
Execute policy x² until there are scopes Z o Z' of size and X U Z'I such that the number of visits to some state-action pairs x with z J z 0, is doubled.
end for
Algorithm 2 Eliminate Inconsistent Scopes Sketch
for i = I,...,d and Z E 2 do for Z' C (I,...,, n of size m and E x 2'] and S; do
if PR 1,uuz (w | P (w |||)) 2 .e,,zuz (w) u) then
Eliminate inconsistent scope: Σ! Σ (Z). and BREAK. end if end for end for Inconsistent reward scopes eliminated from R2. similarly, for every j I.....l.
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 some scopes known have known compact representation (e.g.. decision trees). The algorithm's ''s complexity and regret scale naturally with the level structure knowledge, making it extremely useful when specific domain knowledge available (e.g.. dynamics of some physical systems in robotics).
4.1 Constructing the Optimistic MDP M
As our construction generalizes the of Xu and Tewari [2020] to the 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 extended action space A x S, where playing action (a, 3') in state corresponds to playing action a and using transition function that puts all the uncertainty in the direction of state s', such that for each factor the L1 distance between the empirical and optimistic transition functions is bounded by Ewes, ( (s, (s.") OiVis..///
((..))2(")) [1.))//(((...)12
Formally, let 2 v) min(e,, (w v), Pi (w | u)} and then the probability that in the optimistic MDP the i-th factor of the next state is after playing (a, s') in state is
(w
pk 1, (w)) (s. l) ( (w | (2,)) + Hw = d(D))
Σ Wi (w' (s, as))) w'ES.
The j-th reward factor of this action is the empirical estimate plus an additional optimistic bonus, i.e.,
min 1,
1 1/,3 ((s, ()111) + 2z3 (lz3))
Notice that this optimistic MDP is factored, that the number of state-action factors increased by and that the scope size increased by only 1. Thus, this method indeed keeps oracle-efficiency.
The naive way to extend this idea unknown structure to compute the optimistic MDP for every configuration of consistent scopes, and pick the most optimistic one, i.e., the sonfiguration in which the optimal gain is the biggest. However, this requires exponential number 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 A x S ., Zd; 21, ze) in state s corresponds to playing action a, using a reward function according scopes 21, .,, Zg. and using transition function according to
Σ ..... .. x Σ R ... x R
and playing action ă (a, 2,,,,, Z1,...,

---

scopes Zi.....Zz Za that puts all the uncertainty in the direction of s'. Formally, for every reward factor j define 14 (z) min Fh ((s, (1,)) + ciy ((s,a)]2;1)) }. where ā (s, a). For every factor i
and w E St define
(wll))
1,2 del pt (w (s, (2.) - W (w (3,))
+ +I = s'ii) : Σ W W (w' (s, (Z.)).
(2)
w'ES,
Unfortunately, although this elegant construction looks like factored MDP, 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.c., 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 slightly larger MDP that has the same optimal policy and gain, while being factored with small scopes.
4.2 From Optimistic MDP M to Optimistic Factored MDP M¹
We construct a factored MDP M² that simulates exactly the dynamics of the optimistic MDP M The idea is to stretch each time step to 2 + llg steps. In the first step the policy chooses combined action ä as described in [Section 4.1] in the next log n steps relevant factors are extracted according to the policy's 's choices, and in the last step the transition is performed according to pk (Eq. (2). Since the relevant factors for the transition were already extracted, this time the scope size remains small.
For M we keep the extended action space A A and extend the state space S to contain the state, steps counter, the policy's ' picked scopes and optimistic assignment state, and a "temporary" work space. Formally, S* = S (0, 1.... log n + x Σt x...x x Z x R4 x... x R2 x k(d++)m where S keeps the state, {0, 1. ........ log n- + 1} a counter of the current step within the actual time step, and S 2 x .... x Z x Rt X ..... x R2. keeps the policy's picked scopes and optimistic assignment state. For each factor i (also for each reward factor j) and index e E {1....: ] have a separate "temporary" work space f wn w² x X w² x w that allows extracting the e-th element of the scope for the transition of factor while maintaining small scope sizes. Here, w = ( S,) U (Ui=d+1 A:) keeps one factor (state or action), so |w|| W.
A state in M is mapped to (s, 0, - 1 and taking action à = (a, Zi...., Za. 21... 21....,2 in deterministic transition to (s, 1, s', Zi...., Le. 21...., ,,..,,,,,,, T), where 7 = -Tr,c) ) E (dd+))m The sate-action pair (s, a) is copied to each of the work spaces, i.e., Ti.e = (s, a, 1). 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 ei. we eliminate half of Ti, in each step according to its chosen scope Z. until we are left with the e-th factor of (s, a) [Z.]. 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 Z; chosen by the policy and the counter). The final step performs the transition according to Pk but notice that now it only requires scopes of size m + 3. The reason is that now (s, a) [Z,] has a fixed location within the state, i.e., (s, a) [i][e]] is in the last factor of Ti. (in addition, the counter, s'ii] and s[i] need to be taken into consideration). At this point the agent also gets the reward pk whereas the reward in all other time steps is O. Similarly to the transitions, the reward scopes are of size m + because (s, a)(z] has fixed location (and the counter should also be considered). For more details see Appendixx A
24) results
It is easy to see that M simulates M exactly, because every 2 + log n steps are equivalent one step in M². In terms of computational complexity, any planner that is able to solve M can also solve A7 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 + E+ 1 + 2nm (d + E) (compared to d), the number of action factors is n + d + E (compared to n d), the size of each state factor is bounded by max(W: (*)) } (compared to W), and finally the size L is replaced by max(L, (*) JW + log n). Given the optimal policy k for M we can easily extract the optimal policy #*)) **((s, 0, 1)) for M and the optimistic policy n² (s) = #* (s) A* ((s,
((s,0, 0, L)][1] for the original MDP M.
We use T to indicate that the rest of the state is irrelevant.

---

4.3 Avoiding Large Factors
One shortcoming the above construction is that the factor size may be significantly larger, i.e., (m) instead of W in the original FMDP. As mentioned before, 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 x S x {l...., mmmdd+())) which has m(( + E) factors of size max ( [W n... Similarly, we can view the state space as 2d + 1 + m(d + f) + 2nem(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 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 to only consistent scopes by adding 2(d + E) 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 if the chosen scope for factor 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 + E) 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 + f), log n + 1 instead of log n + 1. Finally, when giving a reward the last step, the reward function also considers the extracted bit and gives reward if it is O. Since it cannot turn back to 1, this bit ensures that policy that uses an inconsistent scope has a gain of O.
4.4 Regret Analysis
In Appendix 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 probabil- ity at least -, 5,
d
RegT(M) = δ Σ Σ s u T
Σ UXIZ 2:12=m
2:12|=m
In the worst-ease regret, this regret bound becomes Regr O WT.T)). ) comparison to the regret bound of Xu and Tewari [2020] for the known structure case, our bound is worse by only a factor of (m)) VL. While the exponential dependence in m (hidden already in L) is unavoidable, it an important open problem whether the multiplicative dependence in (*) 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 VL factor can be avoided with methods such as the meteorologist algorithm of Diuk et al. 2009 since it comes from comparing all pairs of scopes Z * Z' of size m. Still, it is highly unelear how to incorporate these methods 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.
simple structure learning method, i.e.,
Proof sketch. Regret analysis for optimistic algorithms has two main parts: (1) optimism show that the optimal gain in the optimistic model M² is at least as large as X XMM for all episodes & with high probability; (2) deviation bound the difference between the optimistic policy's gains in M and Mr
Optimism follows directly from the consistent scopes definition and standard concentration inequali- ties. Specifically, since the true scopes are always consistent with high probability, the optimistic policy 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
P(-|==))l [I to the confidence radius ex, where ***s") (a', S" Zi,.. Zy #1 ... = x² (s",a* and
along the trajectory visited in each episode k. That is, we need to relate A, = ||
j' = (s', ***)). Then, we can sum the confidence radii over t 1, 1,... ... T and get the final bound.
7

---

To that end, we utilize the transition factorization to bound A S Ea=ll P. (-13*)
P.(- 11-12- (2,"
Then, for each we can use the definition of the optimistie transition function jo (Eq. (2) to get
A S Σ 1 2l(Z - P.(- > IZ + Σ P 1.2!! |+
P. 1.2p x xz(2,11) l1:
The first term measures the difference between the empirical and true dynamics on the correct scopes 2 and can therefore be bounded with standard concentration inequalities. For the second term we utilize the fact that the chosen scopes Z must be consistent. Therefore, we can bound it using Eq. (1)
by = Ei= c G.zzuzg (w =1| U z & E v / up (x (z))2)
5 Factored MDPs with Non-Factored Actions
So far assumed that both the state and action spaces 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. Morcover, 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 and Tewari [2020). The FMDP definition we adopt assumes that the state space is factored S = S1 ... x Sa 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 function P is called factored over S = SI. XSa with scopes 7P: 7P.....2 zi if there exist functions (P: SiZ x A - As, H s.t. P(s' (s,0) II (s' [d]
s 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 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 x 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 + 1 performs the i-th factor optimistic transition, and the last step completes the move.
Formally, the state space of M is S = S x {0, 1,...,,.. d + 1} x x S x {0, 1}. where S keeps the state, {0, 1,... d }} is counter of the current step within the actual time step, A keeps the policy's 's chosen action, another helps perform the transition, and the last bit validates that the chosen actions
are legal. The action space of M is Ā = A U (U S.). The size of À 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, 1) and action a E A deterministically transitions to (s, 1, a, 1),
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, L), legal actions are St, and action w E S; transitions to state (s, 2 + 1, a, w.,..., Wi 1, wi, 1) with probability
pk
s|z?], - 2F (w; 8 =|Z]), a) + (w; = =w]- T. (1,2p(us (ws
Σ Wh.2 (w' s(ZP1,a).
w'ES.
Finally, (s, d + 1, a, Wi...., Wa b) transitions deterministically to (s', 0, 1) for = (wi... wa).
Similarly to /ecciion 4.1, one can see that the scope size is now m +33 the number of factors is 2d + the size of each factor is bounded by (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" - chooses the uncertainty direction for factor after the realizations for factors 1,... .,....t i 1 of the next state are already revealed. Next, we show that it can still 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 + steps).
8

---

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 and taking action E A in state (s, O, L) transitions to state (s, 1, a, L). Then, the policy has no effect for d + 1 steps and the action is embedded in the state. For every i and wy E S the probability of transitioning from (s. a, W1, simply (wxx s|Z;", a), and finally, (s, a, wi,... Wd, 6) transitions to (W1,.... Wa, 0, 1).
wi w;-1; 1) (s, + 1, a, W1,.. W; we 1) is
Clearly, playing policy in M is equivalent playing policy n' in M' such that x ((ss 0, 1)) = (s))
(M) and we can analyze the regret in M' to obtain a similar regret bound to Therefore, X (M') = d+22
Xu and Tewari [020]. The full algorithm which we call fon-Factored Actions DORL (NFA-DORL)
is found in Appendix Cand the full proof of the following regret bound is found in Inpppeddix D
Theorem 2. Running NEA-DORL. on a factored MDP with non non-factored actions and known structure ensures with probability 1 8, Reg = DV1. + E, V1SIZ2I1AATT)
6 Lower Bound
In Appendix F we prove the following lower bound for regret minimization in factored MDPs.
Theorem 3. Let d > m > O. For any algorithm there exists an FMDP with 3d log d state factors of size at most max (W + log d + 23, non-factored action space of size [A], and scope size 1 + max (, log d). such that TE. [[ResT(MM) = (2( log
d
mm ([T).
The proof leverages our techniques (e.g.. propagating rewards through multi-step factored transitions) in order to embed dm multi-arm bandit (MAB) problems into a factored MDP, and make sure that they must be solved sequentially and not in parallel. features a sophisticated construction utilize connections between factors in such way that in each step the learner gets information on just single MAB, forcing her to solve all the MABs one by one. Our construction also the first to feature arbitrary scope size m. while previous constructions simply take d unrelated factors with scope size 1. As 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, improves on previous lower bounds (Tian al.] [2020] Chen et al. [021] by a factor of yd, and matches the state-of-the-arr regret bound of Chen 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 Chen et al. [2021] runs in exponential time, and achieving the same regret with an oracle-efficicee 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) - network of servers con- nected by some topology, where failing servers af- fect 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-UCRI [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 com- pletely ignores the factorization. Figure 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-UCRL"" refers to i factors whose scope needs to be learned, so SIF-UCRIA 4 has no knowledge of the structure.
ELP UOALS
EL LAONLS
10.0
X2.5
18714
Figure 1: SLF-UCRL performance on eircular topology SysAdmin with 4 state factors.
For implementation details and more experiments on different topologies and sizes, see Appendix G

---

Acknowledgements
This project has received funding from the European Research Council (ERC) under the European Union's sHorizon 2020 research and innovation program (grant agreement No. 882396), by the Israel Science Foundation grant number 993/17), Tel Aviv University Center for Al and Data Science (TAD), and the Yandex Initiative for Machine Learning Tel Aviv University
References
Pieter Abbeel, Daphne Koller, and Andrew Y Ng. Learning factor graphs in polynomial time and sample complexity. Journal of Machine Learning Research, 7(Aug):1743-17888 2006.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforce- ment learning. In Proceedings of the 34th International Conference on Machine Learning Volume 70, pages 263-272. JMLR. org, 2017.
Peter L Bartlett and Ambuj Tewari. Regal: A regularization based algorithm for reinforcement learning in weakly communicating mdps. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, pages 35-42. AUAI Press, 2009.
Craig Boutilier, Richard Dearden, Moises Goldszmidt, al. Exploiting structure in policy construc- tion. In IJCAI, volume 14, pages 1 110--111,, 1995.
Craig Boutilier, Thomas Dean, and Steve Hanks. Recision-theoree planning: Structural assumptions and computational leverage. Journal of Artificial Intelligence Research, 11:1-94, 1999.
Craig Boutilier, Richard Dearden, and Moisés Goldszmidt. Stochastic dynamic programming with factored representations. Artificial intelligence, 121(1-2):49-107, 2000.
Doran Chakraborty and Peter Stone. Structure learning in ergodic factored mdps without knowledge of the transition function's 's in-degree. In Proceedings of the 28th International Conference Machine Learning (ICML-11), pages 737-744. Citesecr, 2011.
Xiaoyu Chen, Jiachen Hu, Lihong Li, and Liwei Wang. Efficient reinforcement learning in factored mdps with application to constrained rl. International Conference on Learning Representations, 2021.
Karina Valdivia Delgado, Scott Sanner, and Leliane Nunes De Barros. Efficient solutions to factored mdps with imprecise transition probabilities. Artificial Intelligence, 17509-00):498-15555 201 1.
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 Proceedings of the 26th Annual International Conference on Machine Learning, pages 249-256, 2009.
Yonathan Efroni, Nadav Merlis, Mohammad Ghavamzadeh, and Shie Mannor. Tight regret bounds for model-based reinforcement learning with greedy policies. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, 8-14 December 2019, Vancouver, BC. Canada, pages 12203-12213. 2019.
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner. Efficient bias- bias-span-constrale constrained -itoraatoon-eploiaaatiinn in reinforcement learning. In ICML 2018-The 35th International Confer- ence on Machine Learning, volume 80, pages 1578-1586, 2018
Judy Goldsmith, Michael L Littman, and Martin Mundhenk. The complexity of plan existence and evaluation in robabilistic domains. In Proceedings of the Thirteenth conference on Uncertainty in artificial intelligence, pages 182-189. Morgan Kaufmann Publishers Inc., 1997.
Carlos Guestrin, Daphne Koller, and Ronald Parr. Max-norm projections for factored mdps. IJCAI, volume 1, pages 673 2001.
10

---

Carlos Guestrin, Relu Patrascu, and Dale Schuurmans. Algorithm-dirent directed exploration for model- based reinforcement learning in factored mdps. In ICML, pages 235-242. Citeseer, 2002.
Carlos Guestrin, Daphne Koller, Ronald Parr, and Shobha Venkataraman. Efficient solution algorithms for factored mdps. Journal of Artificial Intelligence Research,
2003.
Zhaohan Daniel Guo and Emma Brunskill. Sample efficient feature selection for factored mdps. arXiv preprint arXiv: /ee./ 2017.
Assaf Hallak, François Schnitzler, Timothy Mann, and Shie Mannor. Off-policy model-based learning under unknown factored dynamics. In International Conference on Machine Learning, pages 711-719, 2015.
Thomas Jaksch, Ronald Ormer, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(Apr):1563-166)) 2010.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is q-learning provably efficient? In Advances Neural Information Processing Systems, pages 4863 4873, 2018
Michael Kearns and Daphne Koller. Efficient reinforcement learning in factored mdps. In Thomas Dean, editor, Proceedings of the Sixteenth Intermational Joint Conference on Artificial Intelligence, IJCAI 99, Stockholm, Sweden, July August 6, 1999. 2 Volumes, 1450 pages, pages 740-747. Morgan Kaufmann, 1999.
Daphne Koller and Ronald Parr. Policy iteration for factored mdps. In Proceedings of the Sixteenth conference on Uncertainty artificial intelligence, pages 326-334. Morgan Kaufmann Publishers Inc., 2000.
Michael L Littman. Probabilistic propositional planning: Representations and complexity. In AAAI/IAA,, pages 748-754, 1997.
lan Osband and Benjamin Van Roy. Near-optimal reinforcement learning in factored mdps. In Advances in Neural Information Processing Systems, pages 604 604-612,70 2014.
Martin I.. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, Inc., New York, NY, USA, 1st edition, 1994. ISBN 0471619779.
Aviv Rosenberg, Alon Cohen, Yishay Mansour, and Haim Kaplan. Near-optimal regret bounds for stochastic shortest path. In International Conference on Machine Learning, pages 8210-8219. PMLR, 2020.
Scott Sanner and Craig Boutilier. Approximate linear programming for first-order mdps. In Pro- ceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence, pages 509-517, 2005.
Dale Schuurmans and Relu Patrascu. Direct valoe-appro for factored mdps. Advances in Neural Information Processing Systems, 14:1579-1586 2001.
Alexander I. Strehl. Model-based reinforcement learning in factored-state mdps. In 2007 IEFE International Symposium on Approximate Dynamic Programming and Reinforcement Learning, pages (10-110. IEEE, 2007.
Alexander L Strehl, Carlos Diuk, and Michael L Littman. Efficient structure learning in factored-state mdps. In AAAI, volume 7, pages 645-650, 2007.
István Szita and András Lörinez. Optimistic initialization and greediness lead to polynomial time learning in factored mdps. In Proceedings of the 26th annual international conference machine learning, pages 1001-1008, 2009.
Mohammad Sadegh Talebi, Anders Jonsson, and Odalric Maillard. Improved exploration in factored average-reward mdps. In International Conference Artificial Intelligence and Statistics, pages 3988-3996. PMLR, 2021.
Yi Tian, Jian Qian, and Suvrit Sra. Towards minimax optimal reinforcement learning factored markov decision processes. Advances in Neural Information Processing Systems, 33, 2020.
11

---

Ziping Xu and Ambuj Tewari. Reinforcement learning in factored mdps: Oracle-efficient algorithms and tighter regret bounds for the non-episodic setting. Advances in Neural Information Processing Systems, 33, 2020.
Andrea Zanette and Emma Brunskill. Tighter problem-dependen regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 3304-7312, 2019.
12


Reviews:
[{"review_id": "ZfFWCm_0gCC", "reviewer": "Reviewer_xFpj", "summary": "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. \n", "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": "Learning in FMDPs constitutes an interesting and important probelm in RL. FMDP models were introduced more than two decades ago and some relevant RL algorithms have been around since the early days of FMDPs. Nonetheless, regret minimization in FMDPs dates back to only a few years ago. It has recently re-gained attention by the research community, in both episodic and average-rewad settings. To my knowledge, this work is the first studying regret minimization in FMDPs without the knowledge of factorization structure. Although the key algorithmic idea for learning the structure is from existing literature, I believe combining that with the optimistic principle and deriving a rate-optimal regret is non-trivial and challenging. The derived regret bound is significant as it avoids an exponential dependence on $d$ (albeit exponentially dependent on $m$). \n\nThe paper is written very well, typo-free, and is well-structured. There are however a few minor comments and suggestions to further improve the writing (see below). The paper is also written mostly clearly and precisely. I was unable to check the proofs in details in this limited review period, but they appear correct to me. Below, I provide some detalied comments, which seem crucial to be addressed. \n\nDetailed Comments:\n\n1- The presented lower bound is interesting and informative, and in my opinion, it improves our understanding about the true difficulty of FMDP learning. A missing piece here is the absence of $D$-dependencies, which is not discussed much in the main text. I may ask the authors to remark this clearly and precisely in the main text, in both the introduction and Section 6, though lengthy discussions could be provided in the appendix. \n\n2- Although the paper is mostly clearly written, I found part of the description of SLF-UCRL in Section 4.2 a bit confusing. I understand the procedure is difficult to explain, but tend to think that there might be alternative ways to present that would be easier to follow. Also, providing some illustration or exemplifying on a toy FMDP could prove very helpful. \n\n3- I may also ask the authors to further elaborate on the notion of “stretched steps” introduced in Section 4.2. \n\n4- Simulation results: The figures are not legible unfortunately. This also applies to those reported in Appendix G, although there is no space limit for the supplementary. I may ask the authors to also consider reporting the corresponding confidence intervals. \n\n5- Simulation results: In all experiments, UCRL2 suffers from a linear regret (for the chosen horizons $T$). If this is due to rather short time horizon, why not running the experiments for large enough horizons (at least for some experiment if it is time consuming)? Otherwise, the reason could be emphasized. \n\nOverall I found the presented algorithms and results of enough significance, and assuming that the authors will address the above comments, vote for a score of 7. \n\nMinor Comments and Suggestions:\n\nLine 44 (and elsewhere): factored MDPs => FMDPs  --- The acronym FMDP is already introduced in page 1, and could be used in the rest. \n\nLine 87: the expected gain => the gain --- By definition (e.g., in line 79), the gain considers expected cumulative reward (as opposed to, e.g., the high probability notion, which is rather uncommon). \n\nLine 119: Note that $W^d$ is not the actual size of state-action space, but rather an upper bound on that, which could be tight in some cases. \n\nLine 150: UCRL => UCRL2 --- The algorithm in Jaksch et al. (2010) is UCRL2 and not UCRL. More precisely, UCRL is a different algorithm, an earlier version of UCRL2, presented in (Ortner & Auer, 2007).\n\nLine 245: … is replaced with => is replaced by (because of passive form. Otherwise “with” is correct)\n\nLine 238: Similarly to the transitions, … are … => Similar to … (because of “are”)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "See above. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5 hours"}, "extra_text": {}}, {"review_id": "GZQGiGtsdu5", "reviewer": "Reviewer_nfbV", "summary": "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.\nIn 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.\n\nIn 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.\n\nAn 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.\n\nThe 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)\n", "questions": "", "limitations": "", "rating": 7, "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": "The lower bound is probably more significant than the upper bound, and I wish more detail on this had been included in the body of the paper. I see that it is using the ideas developed for the upper bounds, but I would have liked the construction to be sketched in some detail.\n\nThe ideas underlying the algorithm are similar to those underlying the earlier works that gave sample complexity bounds rather than regret bounds, just invoked in the context of Xu and Tewari's construction. So there actually is not a ton of novelty there, and the algorithm simply represents all of the n choose m possible dependency sets explicitly. The analysis of dependency sets is similar to the reasoning used by Strehl et al. in one of the early works in this direction. The novelty essentially lies in converting it back to a factored MDP, since allowing the planner to choose the scope creates dependencies with all of the possible scopes. This is accomplished by a second transformation involving an augmented state space that collects the selected scope by a series of local transitions.\n\nI do appreciate that the work includes an experimental evaluation of this algorithm, as otherwise I would worry about the effect of the reduction on the planners. Just because the planners are adequate for the handful of benchmarks doesn't imply that they can solve arbitrary FMDPs efficiently. For example, when SAT-solvers are run on the CNFs obtained by reducing from hard problems, suddenly they aren't so \"effective in practice.\" I wish the plot were large enough that it could be read on a printed page, though. Also, I assume that the reason that the comparison is given to Osband and Van Roy is that the factored action set constructed by Xu and Tewari's algorithm can't be handled by the available planners. But then I also wonder how the structure learning algorithm would compare to the result of the second transformation (the algorithm NFA-DORL described in Theorem 2). \n\nIn summary, although the \"main result\" here seems to be largely a straightforward combination of existing techniques, the state-space transformation that underpins it, as well as the reduction to non-factored actions and the lower bound does seem to be interesting and yields some interesting results. I'd honestly have preferred a paper that didn't treat the unknown structure problem in such detail, in favor of a more thorough presentation of the lower bound.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is fine.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "A_ZLYON85vi", "reviewer": "Reviewer_v8hf", "summary": "\nThis work studies the regret minimization problem of non-episodic factored stochastic MDPs with unknown structure, where the state and action space can be factored as products of several sets. With assumptions on the transition and reward function based on the unknown structure of state-action space (unknown factorization), the authors propose the first oracle efficient algorithm which achieves sqrt(T) regret, and prove a lower bound of learning factored MDPs with known transition. ", "questions": "", "limitations": "", "rating": 7, "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": "\n1. Contribution (Strengths)\n\nThe main technical contribution is the novel reduction method described in Section 4.1 and 4.2. First, the authors follow the idea of the framework of optimism in face of uncertainty, that is, the learner computes the confidence width which constructed based on the concentration inequalities on the transition and reward function. Then, the learner constructs an optimistic factored MDP with extended state action space, and embeds the optimistic selection of transition functions into the action space, that is, the action now decides both the transition and the true action. Note that, since the constructed instance is factored MDP with bounded scope size, the policy can be computed by the oracle solver. \n\nThe authors also propose the first lower bound for regret minimization of factored MDPs, following similar ideas of Rosenberg et al (2020) which constructs a lower bound for stochastic shortest path. \n\nThough I don't acknowledge that the pure theoretical results should be validated by experiments, the authors perform experiments on SysAdmin domain and show that the proposed algorithm is practical, in the sense that it achieves comparable performance with the state of the art (that is, Factored-UCRL with known structure). \n\n2. Weaknesses\n\nOther than the reduction method, the other designs such as sequentially removing inconsistent scopes (strucuture, factorization) are standard and expected. \n\n3. Writing Issues\n\n423, robabilistic->probabilistic\n\n693, regert->regret ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is pure theoretical and does not have any potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "48"}, "extra_text": {}}, {"review_id": "AM7dIZml_ka", "reviewer": "Reviewer_shHj", "summary": "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.\n\n", "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": "This paper is well written and the authors clearly discussed related works. The SLF-UCRL algorithm is the first algorithm that achieves \\sqrt{T} regret in factored MDPs with unknown structure. The concept of consistent scopes is novel and intuitive. Ignoring the computation complexity, introducing consistent scopes already gives a \\sqrt{T} regret algorithm, whose analysis is simple and easy-to-follow. Overall, I believe the theoretical results are sound.\n\nThe SLF-UCRL algorithm addresses the difficulty of structure learning – deciding the scope of each variable – by enumerating all possible scopes and checking consistency. The key observation is that the number of possible scopes is bounded by n^m, which is in the same order as the encoding size (W^m). The n^m dependence appears not only in the computation complexity but also in the regret. On the other hand, the regret lower bound is W^m (although the lower bound doesn’t characterize the hardness of unknown structure). When n>>W the regret bound could be suboptimal. It is unclear whether this dependence is an artifact of the algorithm (or the analysis), or unavoidable for Alg. 2.\n\nRegarding the computation complexity, the algorithm heavily relies on the computation oracle. In fact, the oracle needs to “pick the scopes as well as the actions”. Since computing the optimal policy of a given factored MDP is already hard, it is unclear to me whether the reduction increases the hardness of planning furthermore. During the reduction, some of the nice properties that may guarantee efficient planning could be lost. In other words, it seems to me that the authors essentially sweep all the computation tasks into the planning oracle. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors adequately addressed limitations and potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents the first oracle-efficient algorithm for reinforcement learning factored MDPs when the factored structure is unknown. This is a nice addition to the literature on reinforcement learning with large state spaces, and all reviewers were positive on the paper, so I recommend acceptance. Please incorporate any comments from the discussion period into the final manuscript. 
Decision: Accept (Poster)