Demystifying Linear MDPs and Novel Dynamics Aggregation Framework
Authors: Joongkyu Lee
Min-hwan Oh
Venue: ICLR 2024 poster (2024)
Keywords: linear MDPs
hierarchical reinforcement learning
linear function approximation
aggregation
Primary area: reinforcement learning
TL;DR: We first provide a rigorous analysis of the limitations of existing algorithms under linear MDPs and then propose a provably efficient HRL algorithm in linear function approximation.

Abstract: In this work, we prove that, in linear MDPs, the feature dimension $d$ is lower bounded by $S/U$ in order to aptly represent transition probabilities, where $S$ is the size of the state space and $U$ is the maximum size of directly reachable states.
Hence, $d$ can still scale with $S$ depending on the direct reachability of the environment.  To address this limitation of linear MDPs, we propose a novel structural aggregation framework based on dynamics, named as the *dynamics aggregation*.
    For this newly proposed framework,
    we design a provably efficient hierarchical reinforcement learning algorithm in linear function approximation that leverages aggregated sub-structures. Our proposed algorithm exhibits statistical efficiency, achieving a regret of $\tilde{O} \big( d_{\psi}^{3/2} H^{3/2}\sqrt{ NT} \big)$, where $d_{\psi}$ represents the feature dimension of *aggregated subMDPs* and $N$ signifies the number of aggregated subMDPs. 
    We establish that the condition $d_{\psi}^3 N \ll d^{3}$ is readily met in most real-world environments with hierarchical structures, enabling a substantial improvement in the regret bound compared to LSVI-UCB, which enjoys a regret of $\tilde{O}(d^{3/2} H^{3/2} \sqrt{ T})$.
    To the best of our knowledge, this work presents the first HRL algorithm with linear function approximation that offers provable guarantees.

Published as a conference paper at ICLR 2024
DEMYSTIFYING LINEAR MDPS AND NOVEL DYNAMICS AGGREGATION FRAMEWORK
Joongkyu Lee
Min-hwan Oh
Graduate School of Data Science Scoul National University
Graduate School of Data Science Scoul National University minoh@snu. kc.kr
jklee07170smu ac. kr
ABSTRACT
In this work, prove that, in linear MDPs, the feature dimension d is lower bounded by S/U in order to aptly represent transition probabilities, where is the size of the state space and U the maximum size of directly reachable states. Hence, d can still scale with S depending on the direct reachability of the envi- ronment. To address this limitation of linear MDPs, we propose novel structural aggregation framework based on dynamics,, named as the dynamics aggregation. For this newly proposed framework, we design provably efficient hierarchical reinforcement learning algorithm in linear function approximation that leverages aggregated sub-structures. Our proposed algorithm exhibits statistical efficiency, achieving a regret of Ö (d / /NT). where de represents the feature dimen- sion of aggregated subMDPs and N signifies the number of aggregated subMDPs. We establish that the condition d N d is readily met in most real-world environ- ments with hierarchical structures, enabling substantial improvement in the regret bound compared LSVI-UCB, which enjoys a regret of (dd 33/2 (Jin et al. 2020). To the best of our knowledge, this work presents the first HRI. algorithm with linear function approximation that offers provable guarantees.
INTRODUCTION
Recent theoretical research in reinforcement learning (RI.) has seen surge in studies focusing on function approximation. Such a research direction seeks to address the generalization problem faced
in tabular Markov Decision Processes (MDPs) (Jiang et al. 2017] Yang & Wang 2019 2020 Din
cct al. 2020 Zanette et al., 2020 Modi et al. 2020 Du et al. 2020 Cai et al. [002 Ayoub et al. 2020
Wang et al. 2020 Weisz et al. He et al. 202 Zhou et al.) 2022 la bj Ishlaq et al. 222 Hu
jt al. 2022). The linear MDP (Bradtke & Barto 1996, et al., (0220) serves as a foundational model P(s' s. 6(s, a) uus')
for function approximation, modeling the transition probability with known features & E IRd and unknown measures (u(s'))<'s. Numerous prior studies have demonstrated regret bounds that are not dependent on the size of the state space S (or the action space size A), but instead on the feature dimension d. (Jin et al. 2020 Zanette et al. 2020 Du al. 2020 Cai al. 2020 Weisz al., 2021 He al. 202 Zhou al. 202 la b Ishfaq et al.
2021. Consequently, many of these algorithms proposed for linear MDPs are proven to achieve
regret bounds independent of the size of the state space, and depend only on the intrinsic complexity measure of the feature space, d, once the parameterization is applied. However, whether such replacement of the state space dependence with the dependence on feature dimension induces learning independently of the state space entirely for all MDPs still requires investigation. Hence, we pose a critical research question:
Q1: Does the linear MDP invariably yield regrets that are independent of the state space size S?
In this paper, we rigorously investigate the conditions under which linear MDPs induce learning that is independent of the state space and the conditions under which they do not. Our findings, as detailed in Section 4 prove that the feature dimension d is lower bounded by S/U in order to aptly represent the probability space, where U is the maximum size of directly reachable states (see Definition 2). Thus, if the cardinality directly reachable states does not grow with the entirety of the state space, that is, U o(S) condition that holds true in most real-world situations and

---

Published as a conference paper at ICLR 2024
becomes more pronounced as S expands the feature dimension d has to grow proportionally with to properly encode the probability distribution over next states. Hence, unless the size of reachable states scales with the entire state space, regret bounds under linear MDPs still implicitly have S dependence through the dependence of d on s To the best of our knowledge, our study presents the first comprehensive exposition of the fundamental limitations of the linear MDP, particularly its intrinsic dependence on state space.
Our results on the limitations of linear MDPs suggest that simply because function approximation is employed, it may not necessarily enable efficient learning where the feature dimension d is independent of the state space. However, should additional structures, such as hierarchies, be present within linear MDPs - facilitating the decomposition of the MDP into smaller sub sub-problems - it paves the way for the development of a refined framework, possibly enabling efficient learning. Ideally, well-constructed learning algorithm should then leverage such structures for more efficient learning. Yet, to the best of our knowledge, there is no existing model or algorithm for hierarchical reinforcement learning (HRL) with function approximation that provides regret guarantees. Therefore, the following research question arises:
Q2: Can we formulate new hierarchical frumework for linear MDPs that enables provably efficient learning independent of state space?
To answer this question, we first introduce the framework of dynamics aggregation, which clusters similar sub-structures based on their dynamics of MDPs. Notably, this concept not only includes the extensively studied notion of state aggregation (or state abstraction) (Singh et al. 1994 Van Roy 2006 Li et al. 2006 Abel et al.) 2020 Dong et al. (019)) but also integrates the equivalence mapping proposed in Wen al. (2020). key benefit of dynamies aggregation lies in its reusability for similar problems. This new notion of aggregation not only allows efficient learning in technical perspectives but also is very natural in practical perspectives. Then, we propose linear transition models for aggregated subMDPs, a generalized approach that extends both non hieraarcrhh linear MDPs (Jiang
al. 2017 Jin et al. 2020) and tabular MDPs with equivalent subMDPs (Wen et al. 2020
Under this newly proposed model, we design model-based HRL algorithm that leverages the hierarchical structure of MDPs and employs optimistic planning. This algorithm is provably efficient and, to our knowledge, is the first HRL algorithm that offers provable guarantees with function approximation. In numerical experiments, our proposed method consistently outperforms existing algorithms by significant margins. Our main contributions can be summarized as follows:
We establish that the feature dimension d is lower bounded by S/U, where U represents the maximum size of directly reachable states (Theorem[[]. We also provide examples of various environments where d does not scale with S. Consequently, in such scenarios, the regret bound can indeed depend on the size of the state space despite function approximation. To the best of our knowledge, this is the first work to provide a rigorous proof showing how the feature dimension d relates to the state space size linear MDPs. We strongly believe that this finding provides significant implications and will be of independent interest to the broader RL community.
To address this fundamental issue of the vanilla linear MDP framework, we introduce a new comprehensive framework of dynamics aggregation, encompassing both state aggregation and equivalence mapping (Wen et al.) 2020). One of the key benefits of this framework lies in its inherent ability to be reused for similar sub-prubil aub-problems.
Under this newly proposed framework, we present statistically efficient algorithm that exploits the hierarchical structure of the problem, thereby reducing dependency on the size of the entire state space. Then, we establish a regret bound of Ö(d% ////2/ + THCp) (Theorem 2). where de represents the feature dimension of aggregated SubMDPS, N denotes the number of aggregated subMDPs, and 6p is the aggregation error. If an MDP adheres to the conditions of Corollary ( common circumstance) and exhibits a hierarchical structure, the condition d N < d can be readily fulfilled, dramatically reducing the regret upper
bound compared LSVI-UCB (Jin al., 2020). which enjoys a regret of ( 13322213312
Itt is important to note that our results do not contradict the previously known S- S-inddpendent regret bounds of the algorithms for linear MDPs (Jin et al. 2020). Rather, we focus on the representation ability of linear MDPs and its feature dimension d's potential dependence S.
2

---

Published as a conference paper at ICLR 2024
We also conduct numerical experiments in environments with suitable hierarchical structures and show that our proposed framework enables our algorithm to leverage the structure and consistently outperform the existing RL algorithms with provable guarantees.
2 RELATED WORK
Reinforcement Learning with Linear Function Approximation. In recent years, there has been a surge in research on function approximation with provable guarantees (Jiang et al. 2017 Yang & Wang 2019 2020; Jin et al., Zanottenette Zanctte et al. 2020 Modi et al. [0200] Du al. 2020; Cai cet al., 2020; Ayoub et al. 2020: Wang et al., 2020; Weisz et al. 2021 He et al., 2021 Zhou et al. 2021a sshaa et al. 2021p. All of these works assume certain linear structures of underlying MDP
and appear to handle large state spaces effectively, as their regret scales only polynomially in d and not S. However, it remains unclear how d is related S in linear MDPs. In Theorem [ we provide proof showing that d is lower bounded by S/U, where U represents the maximum size of directly reachable states. And in Corollary majority of real-world environments.
and establish that d can be proportional to S in the
State Aggregation The study of state aggregation (or state abstraction) in RL has long and rich history, dating back to early works on approximating dynamic programs and the identification of 1973; Whitt 1978 Bean et al., 1987 Dean & Givan 1997, Bertsekas et al. 1988). In a similar vein, Li et al. (2066) introduced a unified framework for state aggregation MDPs, examining the conditions under which such aggregations can preserve optimal behavior and affect the existing convergence guarantees of well-known RL algorithms. However, unlike our proposed dynamics aggregation which embraces a hierarchical structure, these past studies did not explicitly leverage this concept.
states that exhibit similar behaviors (Fox)
Hierarchical Reinforcement Learning (HRL). Several studies have explored the decomposition of MDP into sub-problems (Dean & Lin 1995 Singh & Cohn 1997 Meuleau et al., 1998) and then solved independently under the weakly coupled resource constraints. The concept of HRL. which allows agent to act and plan at various levels of temporal abstraction, was established by bySutton et al. (1999); Barto & Mahadevan (2003). However, there has been limited research quantifying the theoretical benefits of HRI. The work most closely related ours is by Wen al. (2020), who introduced a -hased tabular HRL algorithm designed to leverage repeating sub-structures. Nevertheless, their research focused solely on tabular MDPs when utilizing hierarchical structures, leaving the development of an efficacious HRL algorithm for linear MDPs an open question.
3 PROBLEM SETTING
3.1 NOTATIONS
We denote by [n] the set (1,2....,n) for positive integer n. For real-valued matrix A, ||Al|2 = SUPa:|la|a=1 |Axl| to denote the maximum singular value of A. With a positive definite matrix A, we denote | 3 T Aa. We denote | the cardinality of set.
3.2 INHOMOGENEOUS, EPISODIC MDPs
We consider inhomogeneous episodic Markov decision processes (MDPs) denoted by M(S. H, |P (r)))-)), where S is a measurable space, potentially with an infinite num- ber of elements, and has a cardinality of S, A is finite set with cardinality A, H E Z, is the length of each episode, IP the collection of transition probability distributions, and rı is reward function. We assume that every state is accessible from at least one other state, i.e. Vs', "Y Pn(s' | ss
In each episode, an initial state 81 is picked arbitrarily by an adversary. Then, for every h [H] in an episode, an agent takes action a4 E A for state 8 E S and receives reward rh (8h, ax) E [0, 1]. Then, the next state + is is drawn from the transition probability distribution IP Sh, ax) and repeats its interactions until the end of the episode.
IIf a specific is accessible, we can exclude without losing generality.
3

---

Published as a conference paper at ICLR 2024
The agent aims to find policy π S x [H] A that maximizes its expected cumulative reward starting from every state s. We define the value function of policy オ, V S - R as the expected sum of rewards under the policy until the end of the episode when starting from Sy 8, ie.. (s) == Ex -n- policy n, Q% S x A I as the expected sum of rewards when following x starting from step h until the end of the episode after taking action in state s; that is, (x(8,a) == (s + Em
sy, = s We also denote the action-value function of
> Sh-++1 Th (SH,, h()) Sn an
A policy nt is said to be an optimal policy it achieves the maximal possible value at every state-step
pair hs, S [H]. Then, we define the optimal value and action-value functions V (s)
VI (s) = sup, VI (s) and (s, a) == 0% (s. a) = sup, Q7 a). For a simple notation, by (y [Vi+1 (s'],, both Q and Q* can be conveniently written as the result of the Bellman equations (s, a) (ra + Pr, V ().+)))(s) a) and (7 a) (rk +
denoting PA. Vi++ (s,
PA V 1++1 (s, a), where, for all E S, (s) V #+1 (s) 0 and V (s) maXaa (s)
LIMITATIONS OF LINEAR MDPS
There exists a large amount literature on function approximation in which linear MDPs serve as foundational model (Yang & Wang 2019; Jin et al. 2020 Zanette et al. 2020 Hu et al. 2022). Despite the growing body of research, the limitations associated with linear MDPs have not been adequately addressed. In this section, provide comprehensive analysis of inherent limitations in linear MDPs. First, linear transition models of linear MDPs are defined as follows:
Definition 1 (Linear transition model). Let there exist a known feature map 6 b: S:Sx -SXA- TRd and unknown [M S - Rdd Then, the transition operator Ih 8 A A(5) is defined follows: for all 8,8' E S. a A. Ps 8,a) = σ(s,a) (s(()).
The linear structure of the transition probabilities offers the advantage of reducing the number of parameters that need to be estimated, subsequently decreasing the statistical and computational complexity of learning and planning algorithms. However, it is crucial to acknowledge that the set of MDPs that be accurately represented using linear transition models with small d relative the size of the state space is notably limited.
For linear MDP, generally expect that the transition kernel P- | -.-) E SSAx has low- dimensional structure, i.e., d < S. However, the following statements show that the feature dimension closely related the size of the state space, highlighting the inherent limitations associated with linear transition models.
Definition 2 (Directly reachable states). For each (s, a) S x A, "directly reachable states" of (s. a) defined be the set of all states which can be reached by taking action a in state within single transition, Sa,a == {s' to be the maximum size of directly reachable states.
Pn(s' a) > 0}. Also, we denote U == (ax x (S
Theorem 1. For an MDP M with a finite state space, the feature dimension d lower bonded by
d (S/UJ,
where U the maximum size of directly reachable states (Defitiontion 2
Corollary 1. If the maximum size of directly reachable states U does not scale with the entire state space by constant factor, i.e., U = =(( <D, where 0 p 1, then d ' Q(SS-P)..
Theorem I and Corollary | limply that unless the size of directly reachable states (one-step transitable states) scales with the entire state space S - a scenario rarely true in most real-world cases - the feature dimension d would eventually scale with the size of the entire state space polynomially. Consequently, the learning efficiency (e.g.. regret) would still depend on S even when function approximation is employed. Furthermore, Theorem can be generalized to infinite (or even continuous) state space.
Corollary 2 (Infinite S & finite U). For an MDP M with a state space that is either countably infinite or normed, compact, and uncountably infinite, and with finite U, d is infinite.
4

---

Published as a conference paper at ICLR 2024
(a) Gridworld
(b) First-person Navigation
(c) Board Games
(d) Robot Control
000
Figure 1: Various environments where the feature dimension scales with the size of the state space.
Corollary 3 (Euclidean continuous state space). Consider an MDP M with state space in the p-dimensional Euclidean space. Let Vol(.) represent the volume of set. Denote the set of directly reachable states with the maximum volume l arg maxs, S,a Vol(S,,a) and assume that Vol(U) > 0. Then, we have 2P. Vol(S)/ Vol(U)- -1
One can observe that most real-world environments, well many simulation environments, have a small U compared to the size of the state space. This implies that the statement in Corollary [] widely applicable and persuasive. Identifying environments that do not meet the condition of Corollary i rather a challenging endeavor. The following examples, which are widely studied in the RL literature, fulfill the condition:
Example (Gridworld). In Figure (a). the agent is allowed to move neighboring states (left, right, up, down, or stay in the same state), resulting in U 5. Thus, by Theorem 7 d > [S/5]. In special case where the transitions
deterministic (U 1), get d= S.
Example 2 (First-person navigation). In Figure (b), although the entire state space is extremely large, the agent can only move to the neighboring states, resulting in a constant U. Thus, d > S2(S).
Example (Board games), Board games like Go, depicted in Figure (c), have immenss state space, approximately 10400 but the number of directly reachable states is relatively feaer than 192. Hence, ž 2.5 10397.
Example 4 (Control problems). The state spaces in control problems, as depicted in Figure 7 (d), are continuous (uncountable). The volume of sets of directly reachable states is typically much smaller-esse especially in cases with minimal stochasticity-tiee -thn the volume of the full state space. Therefore, d > ((Vo((S)).
To up, many existing studies that assume linear MDPs establish regret bounds that depend on the embedding dimension rather than the size of the state space S. However, most practical environments, d is often proportional S. Consequently, it crucial take the state space size into account when employing linear MDPs in real-world applications, as the assumption of linear transition model may (and often does) fail yield significant improvements in computational or statistical complexity. Motivated by these findings, in the following sections, we study approaches where additional structure may alleviate the limitations vanilla linear MDPs.
HIERARCHICAL STRUCTURE
In the context of MDPs, introduce notion of modularity (Wen al.] 2020). which divides large problem into smaller ones. Modularity could be addressed separately and solved independently. Then, sub-problem solutions could be stitched together solve the original problem. This approach can lead to statistically efficient learning if sub-problems are reasonably small and recurring.
Definition 3 (Sub-problems, Wen al. 2020). Assume that the state space S is divided into L disjoint subgroups {S") Then, induced subMDPs (S &E,A, (P 1h Ari,
1 Et) are defined as:
The internal state set St is disjoint subset of S and the action space is still A.
The exit state set 3. = {c :),85:3(s,a) S x s.t. ('(e 8, 0, 0).
The state space of M is S o
5

---

Published as a conference paper at ICLR 2024
The supports of Pj and ri, are restricted to St x A.
The subMDP M¹ terminates once the agent reaches an exit state, i.e. s E E
Given a partition of M, we examine the collection of induced subMDPs, represented as {M*) If these sub-problems exhibit similarity identical characteristics, it is possible to solve single instance and apply the derived solution to other equivalent or analogous cases.
Ji-1'
5.1 HIERARCHICAL STRUCTURE VIA DYNAMICS AGGREGATION
To formalize the hierarchical structure, employ a concept of state aggregation (or abstraction) method that groups subMDPs exhibiting "behavioral equivalence" (Singh
(c) Original MDP
(e) Aggnegidd subMDEs
(1-(11)
et 1994 Li al. 2006 Wen & Van Roy
M
M
(.2-22)
Ma
2017 Dong et al. 2019). Employing state
aggregation leads to reduction in state space size complexity, thereby acceler- ating the learning process. Inspired by this concept, propose
pla-(1))
M
M
M
concept called dynamics aggregation, which groups sub- MDPs based on the similarity of their dy- namics. This approach involves dividing the of states into N aggregated subMDPs,
(r4-(2)
Figure 2: Dynamics aggregation
denoted by (S((((") u g(x), AA, {Le ics aggregation, we can efficiently learn and generalize across different sub-problemt with similar dynamics, leading to more effective and faster learning. Formally, we can define an approximate
{p(") 1n (r)
) | ((n) for n E [N]. By employing dynam-
dynamics aggregation as follows:
(0(m) SS uE Definition 4 (Approximate dynamics aggregation). For all h [H, i. [L], let 4h S(x) (n) be a mapping that maps the state space of subMDP S to its corresponding aggregated state space S(n), where n E [N]. Let v/. and vit
(i)) exist. Then, for all states E S', $2 E Si where vs (x1) = v (m)) ( (32) and all a E A, the the following conditions hold:
(s1)
(s1, - r (82, a)l & c,.
( (111110)) -1,. (. 12, Epr
where er: Ep R+ u {0), and / (((a)) R Eierry | |S| and S Eme(N] (8tn)), is kernel that satisfying:
() 5²) TI I o E', 8' s(1) v glm) wit(() =))
where I(-) is an indicator function that maps to I when the condition is true, and 0 otherwise.
Note that Pj (-) a) collapses the transition distribution over S gi into Sin) g(x), and if the dynamics aggregation mapping is exact, then c, and 6p = 0.
Dynamics aggregation partitions the original MDPs into subMDPs and projects these subMDPs into aggregated subMDPs, while explicitly considering repeating structures (see Figure 2). This concept encompasses both state aggregation (refer Definition 3 in Li et al. (2006)) and equivalence mapping introduced by Wen al. (2020). not only aggregates similar (usually neighboring) states like state aggregation but also aggregates subMDPs that have similar dynamics, akin to equivalence mapping This methodology enables a significant simplification of the representation compared to the other two frameworks. For more in-depth comparison with other existing frameworks, please refer to Section D in the Appendix.
Intuitively, if all subMDPs are unique, i.e., there there are SubMDPs have the similar dynamics to each other, i.e., some sub-structures are repeated, N L. Thus, we can expect dramatic improvements over the standard algorithms when MDP M has hierarchical structure such that M N < S, where M max, (S()) U g(") If M is small, the sizes of all aggregated subMDPs are small, making each subMDP relatively easy to solve. If N is small, solution to one aggregated SubMDP be reused in other aggregated subMDPs.
duplicate substructures, then N L. And if

---

Published as a conference paper at ICLR 2024
5.2 LINEAR TRANSITION MODEL UNDER THE HIBRARCHICAL STRUCTURE
We assume that the transition probabilities of aggregated subMDP M(n) are linear.
Assumption 1 (Linear transition models for aggregated SubMDPs). Denote dy as the feature dimension of aggregated subMDPs. For each (s, a) S(n) x A. let known known vector ø(s, a) Rd be given prior. Then, for all n E [N], there exist S unknown d-dimensional measures (n) (1a(1). ................................ (n()) E Rd where Ene[N]] |S(m)), such that 4h
(
p 5, ((3,a) u 1
where each columns of u corresponds to a unknown vector Ph and 0 E Rd for Vz' & Sin) u g(m)
(n) (5') (8') Rd for Vs' E S(n) g())
We make the following bounded assumptions, similar existing literature Yang & Wang 2019 Jin et al. y:20 For all h E [M] (i) sups.o (0(0)
(()))) (s), a))2 v Cø. and (ii) 1 u12 & Cp V dd RS such that |0| & 1. We further assume that the reward function r is known for simplicity Since we consider low-rank linear subMDPs, the dimension of the feature space dg is upper-bounded by the cardinality of the image of the (linear) transition mapping, i.e., dy & max, (S(n) E(7) M.
for any vector
When the aggregated state space is just a subset of the original state space with N = 1, implying the aggregated state space is just the original state space S, this model reduces to classical non- hierarchical linear MDPs Jiang et al. (2017); Jin et al. 2020). Furthermore, when the feature representation is one-hot encoding, Le., de SA, this model corresponds tabular MDPs with equivalence mappings between subMDPs, as indroduced by Wen et al. (2020). Thus, this model generalizes tabular MDPs with the hierarchical structure as well as non-hierarchical linear MDPs.
(") Thanks to dynamics aggregation, we only need to learn (1) In=1 and can reuse them to solve similar sub- problems highlighting the reusability key advantage of this approach.
6 ALGORITHM: UC-HRL
The purpose of the algorithm is to learn the transitions for each aggregated subMDP, denoted by ((())((()) u ggt)), .A, ( 1 (()) )h E(x)). Let th
(+()) St u S(a), g(m) are known
dynamics aggregations. To simplify the presentation, we denote ø = wh ( can be abbreviated as they are determined by the state 8. Specifically, represents the index of the current SubMDP to which the state belongs, while denotes the index of the aggregated subMDP that the current subMDP (i) is mapped to via an aggregation mapping. We can learn each transition pf()) a, 618 a) TT (n) by approximating 1
(s). The indices i and
(n) using data that has been collected so far. as a one-hot vector that has zero everywhere except that the entry corresponding to $ is one. For episode & & K and horizon h & H, let 6 := = (- 5k, ax.x) - 8 (3x,6+1). Then, conditioned on history Ha, all information from the beginning of the learning process up
Denote e e R
and including (Sk.h, a),h). we have E[c(") He, 0 for n [N]. This implies that 5 (5x, an unbiased estimate of (P(") (- $k,n, kx conditioned on (5 (2,a)- Define collection of (3, a, 8') triplet interacted with any aggregated subMDP (1)) until the end episode & - as
k. = {FEt Ow #kCh+1) 8k.h E S SR, = wh (+(1)) (Sw
F-1
Then, for all n [N]. it is reasonable learn p (n) via the following ridge linear regression:
Plu = argmin
Σ ()( -63) T A|
'Note that we do not lose generality since learning is much easier than learning P. This assumption regarding is typical in the literature on model-based RI. (Yang & Wang 2019 2020 Ayoub et al. 2020 Zhou
2021a)
7

---

Published as a conference paper at ICLR 2024
Algorithm 1 Upper Confidence Hierarchical RL with Transition-Targeter Regression (UC-HRL)
1: Inputs: M, K, 6, .N (5(m)) B, A
2: Initialize: 1,4 AI E Id xdo (m) Pi,h = 0 x8, D R Ø.
Rdxxs
3: for episode k = 1, 2, ... K do
4: Set (Qr.) h h- as described in Eq. using P4 (m)
5: for horizon h 1,
H do 6: 0R3h < arg max QiAh ( (1)) (SK,A), a). where 8R,4 E and Rup, (*))))) (1 (8k,h). Ael
7:
Play an action 0R and observe 8k,h+1- end for
8:
Update D(1) 1i+1A by Eq.
9:
10:
Rt1,1 - AI - (3..,)) ((,,))
11:
P "
(E 841. (33.0)0(8)
12:
end for
In convention, in case of ((a) k.h = Ø, the summation over D(m) is zero. The full algorithm is For every episode k, we form an UCB bonus term 8 [Ø[3, a)]l (A(R)
summarized in Algorithm
With that, for 8 E S, a E and h [H]. we construct the optimistic aggregated Q-value functions. Definition 5 (Optimistic aggregated Q-values). For any (8, a) & S x A and E [H], let s e St, (1))(m) (s). Then, for all i E [L]. optimistic aggregated Q-values are defined as: 3v (m)) and U/
(5, == min { ( (3( + a)
Datl) 141 B |0[ a)ll (ME)) ..
(2)
where h+1 e R such that h+1 (t) s' St, 141 (v% (M)) 0 for otherwise.
( (s)) s' E o S and
Note that (-(()) (s) 0 since the agent obtains reward after H'th step. We also point that for any states from different subMDPs 81 E S 12 S where vi (m)
vo. (m) k, (3). Thus, the estimated Q-values in the original state space S are detined as (s, a) Q (1h (n) (s), a) for V(s, St U Ed x A. By choosing proper value for 3, we can prove that, with high probability, the Q-value estimates are always optimistic estimates of the actual Q values. Then, in each (h, k)) E x K, the agent selects ( an action that maximized these Q-values k. 1h-1'
(s1) (*)
(s2) 3, the Q-
value estimates can have different values, i.e., @ (5)
(1)
7 REGRET ANALYSIS
Theorem 2 (Regret upper bound). Let = (TT) be collection of policies over K episodes and 8s,1 be the initial state at episode Denote dhg as the maximum rank of the transition kernels for aggregated subMDPs, and N the number of aggregated subMDPs. Then, under Assumption 7 there exists an absolute constant C. > such that, for any fixed (0, 1). if we set B C. de H (T/) then with probability at least 5, the regret of UC-HRL policy is bounded by
K EvF - -TAA -d N NT + -HH,)
Discussion of Theorem 2 Theorem immplesss that if ep is sufficiently small - that is, if the aggre- gation mapping precise enough our algorithm enjoys favorable provable guarantees on regret performances. For example, if ep Õ(I/TT), the regret is still bounded by O 3/2 33/2 /NT) We show that the hierarchical structure can enable statistically more efficient learning compared to preceding algorithms that do not utilize the hierarchical structure. Specifically, if d N d
8

---

Published as a conference paper at ICLR 2024
Optimal
-
LSV4UGB
LSVIPH
UCMMtiiiRL
UERL-TTA
UC-AAL (N-1)
UC-HELL (ours)
L-4, R-2, S-B,
L-6, 5-14, H-22
L-8. R-6, 5-20, H-29
50
1000
153
200
50
105
150
200
53
303
150
202
Episodies
Episodes
Episodes
Figure 3: Episodic returns over 10 independent runs under the
environment
the regret bound can be significantly improved compared LSVI-UCB (Tin al.; 2020p, which has regret bound of H3/2 /T, where d represents the dimension of the feature vector in the original MDP M. Recall Theorem I and Corollary [ which posit that in the majority of real-world environments, particularly those where the maximum number of directly reachable states U is not proportional to the state space size S, the dimension of the feature vector d is lower bounded by It's always the case that dy & M, as we consider low-rank linear subMDPs. Hence, when MN S (indicative of a hierarchical structure), M S2/U3 (signifying small number of directly reachable states compared to S, common scenario), the inequality di N < d can be easily satisfied. We can show this by the following inequality: N M & SM2 & /3/ < d.
S/U f
NUMERICAL EXPERIMENTS
We run numerical experiments 2008), which repeats the sub-structures called "Block" (refer Appendix for detailed descriptions). Thus, if the agent make use of the repeated sub-structures by re-using the learned solution to other blocks, it can learn the optimal policy efficiently.
Block-RiverSwing variant of RiverSwim (Strehl & Littman
Baselines. We compare our algorithm to other provably efficient RL algorithms with linear func- tion approximation: model-based algorithms such as UC-MatrixRI. (Yang & Wang] 2020) and UCRL-VTR (Ayoub al. 2020), and model-free algorithms such LSVI-UCB (Jin al. (0200) and LSVI-PHE Ishfag et al. (02T). We also included the results of UC-HRL (N=L), which is the variant of UC-HRL that naively learns the transition probabilities without the aggregation mappings, in order to directly verify the effect of leveraging hicrarchical structure.
Results. For a fair comparison, we sweep over the hyper-parametten for each algorithm over certain ranges. Figure 3 depicts learning curves over varying state sizes (and the number of blocks) for UC-HRL and other baseline algorithms. When the size of the state space is small and few sub-structures repeated (e.g., L 4, R 2, 8), our algorithm, as well as other model-based algorithms perform relatively well. However, as the sub-structures repeat more (R increases), our algorithm learns the optimal policy far more quickly than the other algorithms. The results demonstrate that our proposed algorithm is not only provably but also experimentally efficient when the hicrarchical structure is presented in the environment.
CONCLUSION
In this work, first show that in the majority of real-world environments, the regret can be dependent on the size of the state space 5 by showing that the dimension of features, d, can be proportional to S. To mitigate this issue, we formalize hierarchical decomposition in aggregated state space and propose a UC-HRL that can significantly enhance the regret bound if repeated sub-structures are present. However, utilizing known hierarchical structure is not the sole solution. We leave the exploration of other milder methods as a direction for future research. We anticipate that our research will serve as pioneering study in rigorously highlighting the limitations of linear models and in enhancing the understanding of provably efficient hicrarchical RL with function approximation.
*For the Fuclidean continuous state space, d Z Vol(S)/ Vol(().

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENTS
This work was supported by the National Research Foundation of KoRE)(NRF) grant funded by the Korea (SV))) (No. 2022RIC1C10063 and RS-2023-00222663) and by Creative- Pioneering Researchers Program and AI-Bio Research Grant through Scoul National University.
REFERENCES
Yasin Yadkor,, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24:2312 02-21222333 2320, 2011.
David Abel. Nate Umbanhowar, Khimya Khetarpal, Dilip Arumugam, Doina Precup, and Michael Littman. Value preserving state-action abstractions. In International Conference on Artificial Intelligence and Statistics, pp. 1639-1650. PMLR, 2020.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pp. 463 PMLR, 2020.
Andrew G Barto and Sridhar Mahadevan. Recent advances in hierarchical reinforcement learning. Discrete event dynamic systems, 13(1):41-77, 2003.
James C Bean, John Birge, and Robert I. Smith. Aggregation in dynamic programming. Operations Research, 35(2):215-22) 220, 1987.
Dimitri P Bertsekas, David A Castanon, al. Adaptive aggregation methods for infinite horizon dynamic programming. 1988.
Steven J Bradtke and Andrew Barto. Linear squares algorithms for temporal difference learning. Machine learning, 22(1):33-55 57, 1996.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimiza- tion. In International Conference on Machine Learning, pp. 1283-1294. PMLR, 2020.
Thomas Dean and Robert Givan. Model minimization in markov decision processes. In AAAI/IAAI, pp. 106-111, 1997.
Thomas Dean and Shieu- Lin. Decomposition techniques for planning in stochastic domains. In IJCAI, volume 2. pp. 3. Citeseer, 1995.
Shi Dong, Benjamin Van Roy, and Zhengyuan Zhou, Provably efficient reinforcement learning with aggregated states. arXiv preprint arXiv: 2019.
Simon S. Du, Sham M. Kakade, Ruosong Wang. and Lin F. Yang. Is good representation suffi- cient for sample efficient reinforcement learning? In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020, 2020.
Bennett L Fox. Discretizing dynamic programs. Journal of Optimization Theory and Applications, 11:228-221 2244,23,,11 1973.
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Emma Brunskill. Regret minimization mdps with options without prior knowledge. Advances in Neural Information Processing Systems, 30, 2017.
Jiafan Hc, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. In International Conference Machine Learning, pp. 4171-4180 PMLR, 2021.
Pihe Hu, Yu Chen, and Longbo Huang. Nearly minimax optimal reinforcement learning with linear function approximation. In International Conference on Machine Learning, pp. 8971-9019. PMLR, 2022.
Audrey Huang, Jinglin Chen, and Nan Jiang. Reinforcement learning in low-rank mdps with density features. In International Conference Machine Learning, pp. 137 13710-13752. PMLR, 2023.
10

---

Published as a conference paper at ICLR 2024
Tachyun Hwang and Min-hwan Oh. Model-based reinforcement learning with multinomial logistic function approximation. arXiv preprint arXiv:2212.13550, 2022.
Haque Ishfaq, Qiwen Cui, Viet Nguyen, Alex Ayoub, Zhuoran Yang, Zhaoran Wang, Doina Precup, and Lin Yang. Randomized exploration in reinforcement learning with general value function approximation. In International Conference Machine Leurning, volume 139, pp. 4607-4616. PMLR, 2021.
Zeyu Jia, Lin Yang, Csaba Szepesvari, and Mengdi Wang. Model-based reinforcement learning with value-targeted regression. In Learning for Dynamics and Control, pp. 666-686. PMLR, 2020.
Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contex- tual decision processes with low bellman rank are pac-learnable. International Conference on Machine Learning pp. 1704-1713, PMLR, 2017.
Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pp. 2137-2143. PMLR, 2020.
Lihong Li, Thomas Walsh, and Michael Littman. Towards a unified theory state abstraction for mdps. In AI&M, 2006.
Timothy A Mann, Shie Mannor, and Doina Precup. Approximate value iteration with temporally extended actions. Journal of Artificial Intelligence Research, 53:375-438, 2015.
Nicolas Meuleau, Milos Hauskrecht, Kee-Eung Kim, Leonid Peshkin, Leslie Pack Kaelbling, Thomas L. Dean, and Craig Boutilier. Solving very large weakly coupled markov decision processes. In AAAI/AAI,, pp. 165-172, 1998.
Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. International Conference on Artificial Intelligence and Statistics, pp. 2010-2020. PMLR, 2020.
Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free representation learning and exploration in low-rank mdps. Journal of Machine Learning Research, 25(6):1-76, 2024.
Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013.
David Pollard. Empirical processes: theory and applications. Ims, 1990.
Satinder Singh and David Cohn. How to dynamically merge markov decision processes. Advances in neural information processing systems, 10, 1997.
Satinder Singh, Tommi Jaakkola, and Michael Jordan. Reinforcement learning with soft state aggregation. Advances in neural information processing systems, 1994.
Alexander L Strehl and Michael Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 74(8):130--133 2008.
Richard Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: framework for temporal abstraction in reinforcement learning, Artificial intelligence, 11(1122)181--11, 1999.
Masatoshi Uchara, Xuezhou Zhang, and Wen Sun. Representation learning for online and offline in low-rank mdps. arXiv preprint / 10.04652, 2021.
Benjamin Van Roy. Performance loss bounds for approximate value iteration with state aggregation. Mathematics of Operations Research, 31(2):234-244 2006.
Ruosong Wang. Russ R Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33, 2020.
11

---

Published as a conference paper at ICLR 2024
Gellért Weisz, Philip Amortila, and Csaba Szepesvári. Exponential lower bounds for planning in mdps with linearly-realizable optimal action-value functions. In Algorithmic Learning Theory, pp- 1237-1264. PMLR, 2021.
Zheng Wen and Benjamin Van Roy. Efficient reinforcement learning in deterministic systems with value function generalization. Mathemalics of Operations Research, 42(3):762-782, 2017.
Zheng Wen, Doina Precup, Morteza Ibrahimi, Andre Barreto, Benjamin Van Roy, and Satinder Singh. On efficiency in hierarchical reinforcement learning. Advances Neural Information Processing Systems, 33:6708-B 18, 2020.
Ward Whitt. Approximations of dynamic programs, i. Mathematics of Operations Research, 3(3): 231-243, 1978.
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pp. 6995-7004. PMLR, 2019.
Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pp. 10746-10756. PMLR, 2020.
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric Frequentist regret bounds for randomized least-squares value iteration. International Conference on Artificial Intelligence and Statistics, pp.
PMLR, 2020.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pp. 4532-4576. PMLR, 2021a.
Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference Machine Learning, pp. 12793-12802. PMLR, 2021b.
12

---

Published as a conference paper at ICLR 2024
A RELATED WORK
In this section, we provide the expanded version of Section 2
Reinforcement Learning with Linear Function Approximation. In recent years, there has been
surge in research on function approximation with provable guarantees (Jiang et al. 2017; Yang
& Wang 2019 2020; Jin et al. 2020; Zanette et al. 2020; Modi et al. 2020 Du et al., 2020; Cai
ct 2020; Ayoub al., [2020: Wang et al., [020; Weisz al. [021] He et al.. 2021 Zhou et al.
2021a b Ishfaq et al. (021) 1). J. All these works assume certain linear structures of underlying MDP. Jin
et al. (2020) examined linear MDPs and proposed LSVI-UCB, which achieves an (( (2 (T) regret bound. Zanette al.] (2020) proposed an optimistically initialized variant of the randomized least-squares value iteration (RLSVI) algorithm, where exploration is induced by perturbing the estimates of the action-value functions and provided regret bound I(2IVT
In the realm of model- algorithms with linear function approximation, Yang & Wann (2020)
proposed a model-based algorithm under the assumption that the transition probability kernel is bilinearly parameterized by two feature mappings, enjoying regret of (dd3/2 H2 H2VT). Another popular MDP model for RL with linear function approximation is linear mixture model (Modi et al. 2020; Jia et al. 2020 Ayoub et al. 2020). where the transition probability kernel is linear mixture of some basis kernels. Jia et al. (2200) proposed the UCRL-VTA VTR algorithm under the linear mixture model, where the transition probability kernel is a linear mixture of some basis kernels, with O(dH3/2 /T) regret. Zhou et al. (22 proposed a variant of the method proposed by Jia et al. (2020) and proved ÖdHH regret bound with a matching lower bound Mdd vT).
These algorithms seem cope with large state space, their regret scales only polynomially in d. However, it remains unclear the relationship between the feature dimension d and the state space size S in linear MDPs. What known is that in the worst case, d S SA. scenario referred as the tabular MDP (Example 2.1 in Jin et al. (0200). Moreover, Du et al. (2000) showed that there exists family of MDPs where the sample complexity can be lower bounded by even with good representations under linear function approximation. However, they considered only special instances. Furthermore. [wang & Oh (2022) showed that UC-MatrixRL (Yang & Wang 2020) can depend on the size of the state space despite the use of function approximation. However, their analysis is specifically applicable to bilinear models and does not include linear MDPs. In Theorem [ we rigorously examine the relationship between d and S in linear MDPs, establishing that d can be proportional to S in the majority of real-world environments. To the best of our knowledge, this is the first work demonstrate the conditions under which d is large small. In Corollary 2 and 3 we establish that d can be proportional to S in the majority of real-world environments. This implies that the low-rank assumption, as suggested in many existing works (Zanette al. 2020
Uehara et al..
2021 Modi et al. 2024 Huang et al. 2023). often does not hold in the real world.
On the other hand, a key distinction between our algorithm and LSVI-UCB (Jin al. 2020) lies in our approach being model-based. This distinction primarily offers the benefit of reusability. In model-free approaches. Q-values are defined by features and specific parameters, as exemplified by wx in Din et al. (2020). Therefore, when two different states are mapped to the same aggregated state, they become indistinguishable
terms of their Q-values because they share the same feature. However, it's important to note that the actual Q-values for these two states may still differ (refer Appendix D.3). Essentially, model-free approaches fail to effectively leverage the hierarchical structure, even with perfectly learned sub-structured and accurate mapping. Conversely, our model-based approach enables the reuse of learned dynamics of subMDPs (1)) in similar subMDPs. Therefore, it's important to note the fundamental intuition and significance of using a model-based approach to exploit the hierarchical structure.
State A Aggregation The study of state aggregation (or state abstraction) in RL has long and rich history, dating back to early work on approximating dynamic programs (Fox 1973) Whiti 1978 Bean ct al.) 1987; Bertsekas et al. 1988). The pioneering work of Whitt (1978) laid a critical foundation for comprehending the impact of state aggregation on value loss in MDPs. Building upon this, Dean & Givan (1997) devised a method for identifying states with similar behaviors through the application of the bisimulation property. In a similar vein, Li et al. (2006) introduced a unified framework for state aggregation in MDPs, examining the conditions under which such aggregations can preserve optimal behavior and affect existing convergence guarantees of well-known RI. algorithms. More
13

---

Published as a conference paper at ICLR 2024
recent work has continued to clarify the conditions under which state abstractions preserve value in MDPs (Abel et al. 2020). Previous research has also suggested regret or learning time bounds with aggregated states (Wen & Van Roy 2017 Dong et al. 2019). However, unlike our work, these past studies did not explicitly leverage the hierarchical structure, a key component that our research embraces.
Hierarchical Reinforcement Learning. There are several works that addressed the decomposition of MDP into sub-problems (Dean & Lin 1995; Singh & Cohn [997] Meuleau et al.) 1998). [eeueau et al. (1998) decomposed the original MDP into SubMDPs and then solved independently under the weakly coupled resource constraints. The concept of hierarchical RL, defined as an agent's 's ability to
act and plan at multiple temporal abstraction levels, was established by SSutton et al. (1999): Barto Mahadevan (200). However, few works have quantified the henefits of Hierarchical RL (HRL) from theoretical perspective. For instance, Fruit et al. (2017) introduced semi-MDP versions of algorithms, Mann et al. (2015) proposed an algorithm that quickly learns policies and models in new circumstances by solving smaller problems. The closest related to our work is Wen et al. 2020), which proposed a model-based Thompson sampling-style HRL algorithm that exploits repeating subMDP structures. They provided regret bound that shows significant improvement when the maximum size of subMDPs multiplied by the number of equivalent subMDPs much smaller than the state space size. However, their work only considered tabular MDPs for hierarchical structure utilization, leaving the question of designing a provably efficient HRI. algorithm for linear MDPs with sub-structure still unanswered.
inloortiio--xploitanee
B ADDITIONAL EXPLANATION FOR SECTION 4
B.1 PROOF OF THEOREM I
Proof of Theorem For horizon h [H], let PP (.) e SAXS be the transition kernel of an MDP M.
We first show that the feature dimension is greater than or equal to the rank of the transition kernel rank(Px)) J. In the linear MDPs, the transition kernel can be expressed as PA(- 1.-) 4 uh. where [Ø(s1, a1), (811 .2), ... ,0($,, ax] E IRASSA and μ4 [1), ... ..... :..))ssss)....s)) (ns)s)] E Raxs Thus, d cannot be smaller than rank(PP,).
Now, we select any row, which corresponds to a specific atate-action pair (s, a), from the transition kernel PA, and label it as vector U1. By rearranging the columns, we can make 01 have zero probabili- ties for U l,..... 5-th entries and have non-zero probabilities for at least one of I...., U-th entries. This is possible due the condition that the maximum number of directly reachable states is less than equal to U. i.c., for any (s, a), there are non-zero transition probabilitics for transitioning from (s, a) to subset of at most U states.
Furthermore, given the condition that every state is accessible from at least one other state (refer problem setting in Section 3). there exists of + 1,..., 5-th entries. We denote this vector as U2. By reordering the U + 1,..., S-th columns, we can make U2 have zero probabilities for 2U + 1,...., S-th entries and have non-zero probabilities for at least one of U + 1,..., 2U-th entries. Consequently, it is evident that 0 and U2 are linearly independent.
vector that has non-zero probabilities for at least one
Following a similar logic, we can choose a row vector Vs that has zero probabilities for 3U + I,...,,. S- th columns and have non-zero probabilities for least one of 20 + +,,..,, 3U -th entries, by reordering the columns properly. It is also clear that U1, 02, and Uy are linearly independent from one another.
.....,,,.
By recursively applying this logic, we can choose row vectors Ui,..., 2[8U]] that are linearly independent from another. This directly implies that ran) > [S/U]. Therefore, we derive that
d > rank(Ppb) > [S/U].
14

---

Published as a conference paper at ICLR 2024
B.2 EXAMPLE FOR THEOREM
For a better explanation, we provide an example for Theorem {81, .2, 80), A {a), and the transition kernel follows:
1
Consider an MDP where
81
$2
83
81
85
96
87
S8
89
($1, a)
1/3
1/3
1/3
0
0
0
0
0
82, a
0
1/2
1/2
0
0
83,
1/5
1/5
3/5
0
0
0
0
0
84, (
0
0
1/4
0
1/4
1/2
0
PA
85, a)
0
0
0
0
0
0
1
88; a)
0
1/2
1/2
0
0
0
87, a)
0
0
0
2/3
0
1/3
0
022
$8, a
0
0
1/3
1/3
1/3
0
0
8g; a)
1/2
1/2
0
0
0
Note that U S and every state accessible from at least one other state. First, choose any row of the transition kernel. Assume that we choose the first row and denote it as The row vector ei has zero probabilities for ..... 9-th entries and has non-zero probabilities for 1, 2, 3-th entries.
Second, we can choose the seventh row and denote it v2. By switching the columns corresponding to 84 and 5g, we get
82
83
5g
85
96
87
84
89
(81,
1/3
1/3
1/3
0
0
0
0
0
$2, a
0
1/2
1/2
0
0
$3, a)
1/5
1/5
3/5
0
0
0
0
84, a)
0
0
0
1/4
1/2
1/4
0
Pb
85, a)
0
0
0
0
1
88; a
0
1/2
1/2
0
0
0
0
(87, a
0
0
1/3
0
2/3
0
0
02
[88, a)
0
0
1/3
1/3
0
1/3
0
03
(g,, a)
1/2
1/2
0
0
0
Now, the row vector 1/2 has zero probabilities for 7, 8, 9-th columns and has non-zero probabilities for at least one of 4, 5, 6-th columns.
Finally, we choose the eighth row for v3 Since v1, U2 and Vt are linearly independent of one another, the rank of P, is lower bounded by S/U
B.3 PROOF OF COROLLARY 2
Proof of Corollary 2 We provide the proof by examining two cases: 1) when the state space is countably infinite, and when it is normed, compact, and uncountably infinite.
Case 1. countably infinite state space.
We prove this by contradiction. Assume that the feature dimension is finite. Then, the transition kernel possesses a finite number of linearly independent rows and columns. Note that for countably infinite state space, the transition kernel can be viewed as an infinite matrix with both its rows and columns being infinite.
Now, we follow the same logic from the proof of Theorem I We choose any row, which corresponds to specific state-action pair (s, a), from the transition kernel IP, and label it as vector Since the maximum number of directly reachable states less than equal to U, by rearranging the columns of PA properly, probabilities for at least one I,..., U-th entries.
make e1 have zero probabilities for U 1,... -th entries and have non-zero
Furthermore, given the condition that every state is accessible from at least one other state (refer Section 3) there exists a row vector that has non-zero probabilities for at least one of U +......... make 222
entries. We denote this vector U2. By reordering the U + 1.... -th columns, have zero probabilities for 20 + 1,... ..... -th entries and have non- zero probabilities for at least one of U + 1, 1,..., 1,-..22Utth 2U entries. Consequently, it is evident that and vi are linearly independent.
15

---

Published as a conference paper at ICLR 2024
By recursively applying this logic, identify set of linearly independent row vectors I := {0i, 1/2 ... }. Since the cardinality of the state space is infinite, the cardinality the set I is also infinite. This contradicts initial assumption that the transition kernel possesses finite number of linearly independent rows. Therefore, we conclude that must be infinite.
Case 2. normed, compact, and uncountably infinite state space.
For the normed, uncountably infinite (or continuous), and compact state space, we can utilize the e-covering. Let (V(S, e, p) be the the minimal s-covering number of S with respect to a distance metric p. Further, we define $ = S as the set of all center points of the covering balls. Note that $ is a finite space since the state space is compact and (S] = NNS, p). Let 2 = S x AA be the minimum size subset of the state-action space containing every element in S, i.e., 2 2 S, such that every state in S is accessible from at least one state-action pair in 2, i..., {s.,)e (s's' s. > for all s' e S and Σ 2 S. Note that |S] < Σ 2| This is because s' S is not accessible from S A, we only need to add one state-action pair (s, a) 2 that can transition to s' S. Hence, every state is accessible from at least one state-action pair in the reduced form of the transition kernel FA R [
Let Ü be the maximum number of directly reachable states for Fr. Then, by Theorem we can identify linearly independent row vectors every Ü columns. Therefore, we have that
rank ||8//01.
On the other hand, know that d cannot be smaller than rank(Fn); thus, we have rank Hence, for any & >> O, we have that
e PP > [|šا - N(S.s,.
where the third incquality is by the fact that Ü < U. Since N(S, E, p) is non-decreasing as e goes to zero, get
sup
lim N(S, 00, c-0
2>0
where the last inequality holds since U is finite. Therefore, d infinite.
B.4 PROOF OF COROLLARY 3
For the p-dimensional Euclidean state space S RP, we use the e-covering method. Let 1/ represent the set of directly reachable states with the maximum volume, i.e., 2 := Sz.a- where (5, a) arg max Vol(S..a)- Then, denote the minimal e-covering number of 2/
Proof of Corollary 3
with respect to distance metric N ((,,,, p) and define ((E)) as the sets of all center points of the e-covering balls for t4 We further denote the minimal e-covering number of X ;= Si S u U with respect to a distance metric as NV p) p) and define (s) as the sets of all center points of the e-covering balls for X. Note that [((=)) N(,,,, op, (x()) (N( oc, and ({{)) n (E))) Ø since the center points of the e-covering balls are interior points of the corresponding set.
Now we denote W(s) ū(e) E(e.. Let (()) s S A be the minimum size subset of the state-action space containing every element in W(e), i.e., ă(e) 2 W(E), such that every state in W(e) is accessible from at least one state-action pair in ((e), i.e., E(..)) Pa(s' 8,a) > 0 for all s' E S(e). Note that [We) & [5(+) & 2|W(s)) < xo. This is because if s' W(e) is not accessible from W(s) A, we only need to add one state-action pair (s, a) to 2(s) that can transition to W(E). Hence, every state is accessible from at least one state-action pair in the reduced form of the transition kernel (e) R(ž())xx W())
16

---

Published as a conference paper at ICLR 2024
Note that (E) is the set of directly reachable states for (e).). By applying Theorem
identify linearly independent row vectors every [((()) columns. Hence, for all 0, we have
[ieel
rank(Px(s)) >
(B.1)
[=)l
Moreover, by the definition of covering number, we know that
Vol(S) & Vol (eB) (MS & Vel (W(e))
(B.2)
where the operator Vol(-) represents volume of set, B is the unit ball norm; thus eB denotes the norm ball with radius E, E, is the minimal e-covering number of S with respect to distance metric p. and the last inequality holds since E.S,E, & N(,,,, + (x [[(e)] + [e)) = [M(e)--
Furthermore, we have
Vol(U + } Vol(5
ú(s) = N(U,E, & s,)
(B.3)
where is the Minkowski addition, T(4, E, p) the maximal e-packing number with respect a distance metric p. the first inequality holds by Lemma G.3] and the last inequality holds by the definition of e-packing; 2/2 packing norm balls are disjoint.
On the other hand, we know that d cannot smaller than rank(Px(e)); thus, we have
+ (an)()P())).
(B.4)
Combining Eq. B.1
B.2
B.3
and B.4
for all > O, we get
[W(e)
Vol(S)/ Vol(eB) Vol(S)/Vol(eB)
(Bl)))))((B(e)) Vol(U + B) Vol( (
d > rank (c))
[?((s)
[(())
2" Vol(S)
Vol(S)
2"
Vol(U + {)
Vol(u + B))
Hence, by taking supremums over & > 0, we derive that
Vol(S) = 2" lim Vol(S)
d >> 2" sup
=>0 Vol(u B)
Vol(u + {B) Vol(S)
2"
Vol(U))
where the first equality by the fact that Vol(u + B) is non-increasing as decreases. This concludes the proof.
C EXAMPLE ENVIRONMENT: RIVERSWIM
In this section, provide toy example to offer an in-depth explanation of the main point of our paper. First, we validate Theorem in this environment. Subsequently, we demonstrate the benefits of using hierarchical structure by showing that d&. N < d3
The RiverSwim, as illustrated in Figure C.1 is comprised of 5 states arranged sequentially, with each edge value representing the transition probability. From the starting point at the far left state, noted 31, the agent has the option to navigate to the left thereby earning a small reward, i.e., r($1, left) 0.005. Alternatively, the agent can opt to move to the right- an action depicted by the solid lines in each successive state. The objective for the agent is to maximize its total return by attempting to arrive at the far right state, denoted as sg. Here, the agent earn large reward r(sg, right) 1 by choosing navigate the right.
action represented by the dashed lines
17

---

Published as a conference paper at ICLR 2024
0.4
0.6
0.6
0.6
0.35
0.35
0.35
$1
0.05
82
0.05
0.05
1-11
0.4
s8
1
Figure C.I: The "RiverSwim" environment Osband et al. (2013)
The transition kernel of the environment is follows:
(s
$1, left)
Pn(s2
$1, left)
(s 81, left)
(A(sa 81, left)
(x
81, right)
[s
right)
(s
right)
Pa(s4 right)
Pa(#1
82, left)
Px(82
82, left)
Px(53
82, left)
Px(84 82, left)
Pa(s1
$2, right)
(s
right)
Fx
right)
Pn
right)
FA
(1
$3, left)
(s
$3, left)
Pn(ss
83, left)
PA(s1
left)
Pa
$3, right)
(s
$3, right)
(s sighi)
(y si.right)
1
0
0
0.4
0.6
0
1
0
0
0
0.05
0.6
0.35
(C.1)
0
0
0
0.05
0.6
0.35
The agent is allowed to move left, right, stay in the same state. This means the maximum number of directly reachable states is 3, i.c., U 3. Regardless of an increase in the total number of states, U stays fixed at 3. Consequently, that depends on S, which means the learning complexity will proportionally increase with S, even when using linear function approximation.
in this simple example, can't sidestep feature dimension
We will now demonstrate, using the toy example, how our main claim presented in Section 7 specifically that d N < d8 is valid. Let the number of state is 100, i.e., S 100. In this environment, each of the 100 states can be considered as separate subMDP. and consequently, the number subMDPs is equal to the size of the state space, i.e., L = 100. Then, we have
The maximum size of aggregated subMDPs, M One internal state and its neighboring states.
The number of aggregated subMDPs, N = 3: All subMDPs, excluding and $100. which means $2, $3, ........... S99, are grouped into a single aggregated subMDP. Meanwhile, $1 and 8100 each form distinct aggregated subMDPs.
MN = 32 < S.
The maximum size of directly reachable states, = 3.
The feature dimension of aggregated subMDPs, dy < .M = 3: This always holds true.
The feature dimension of the original MDP, S 100: The transition kernel has full rank.
Hence, we get
NN < 34.
SM -3
M = 34.
53/U3 = 1003/3.
Therefore, derive that d&N M SM < S R.
18

---

Published as a conference paper at ICLR 2024
D DYNAMICS AGGREGATION
D.1 COMPARISON TO EXISTING FRAMEWORKS
In this section, we provide a comprehensive description our proposed framework described in Section
Goal
Goal
Goal
Goal
M
M0
M2
It
M
M
M(3
M
Start
Start
Start
Start
a) Original MDP
b) State Aggregation
c) Equivalence Mapping
d) Dynamics Aggregation
Figure D.1: (a) simple Gridworld MDP, (b) the aggregated MDP induced by the state aggregation,
(c) the partitioned subMDPs with equivalence mappings, and (d) the aggregated MDP induced by the dynamics aggregation
As motivating example, agent is placed in wide hallway, and tasked with reaching an exit located the far end of the hall (see FigureD..I, The traditional problem setup might use a Cartesian grid, where the agent's ' location is determined by and y coordinates, and it navigates using up. down, left, and right actions. Please note that the reduced number of states (circles) in Figure D.] does not imply change in the actual MDP structure. Instead, it suggests simplification in terms of learning complexity.
A careful analysis of the problem reveals that the agent's coordinate is irrelevant for achieving optimal behavior. Therefore, a state aggregation in this context would be a function that projects the original state with the same x coordinate belong to the same abstract state, significantly reducing the size of the state space. To intuitively grasp this concept, consider the scenario where you are walking down hallway without obstacles: if your objective is truly to make forward progress toward the exit of the hall, then there little need to pay attention to horizontal movement.
aggregated state that only tracks the y coordinate. This way, all original states
In contrast to state aggregation, equivalence mapping (Wen et al., (020) does not project states into latent space. Instead, partitions the original MDPs into disjoint subMDPs and groups them based on identical or similar structures. In the example, the states in the third row (subMDP M and the fourth row (subMDP M have the same transitions equivalence mapping
reward functions, and therefore, an be established between them. As these subMDPs are indistinguishable in terms their structures, an agent employing a hierarchical structure can treat them as a single subMDP. This also significantly reduces the size of the state space. However, equivalence mapping necessitates that every aspect of the states is identical, even when certain details may not be crucial for discovering the optimal policy. This requirement can potentially constrain the range of scenarios where this framework can be effectively applied.
Our framework, dynamics aggregation, combines the benefits of both state aggregation and equiva- Ience mapping. It operates by partitioning the original MDPs into subMDPs. These subMDPs are then projected into aggregated subMDPs that focus solely on the y coordinate: the subMDP M into (1),, the subMDPs M 3 into (2) (their dynamics
the same), and the subMDP M into (a Notably, framework is explicitly designed to account for repeating structures in the data, enhancing its effectiveness. This approach results in a considerably simplified representation compared the other two frameworks. Moreover, dynamics aggregation only demands that the
19

---

Published as a conference paper at ICLR 2024
aggregated states are identical, not minute details. This broadens its applicability compared to equivalence mapping, making it a more versatile framework for a wide range of scenarios.
D.2 INTUITION BEIIIND THE DYNAMICS AGGREGATION
Dynamics aggregation has practical implications for human learning. For instance, driver who can navigate New York is likely not only to adapt quickly to driving in San Francisco but also to have high probability of being able to drive in Paris. Similarly, a driver who has practiced exclusively within Manhattan and possesses driver's 's license should have no trouble driving to JFK in Queens. This adaptability largely stems from the existence of repeating structures and the mappings between similar structures. Often, such mappings are readily available, and we humans excel at leveraging them. These mappings need not be perfect; approximations are sufficient, as discussed in this paper. We incorporate these insights into our proposed framework.
D.3 COMPARISON TO MISSPECIFIED LINEAR MDP
At first glance, one might think it feasible to learn directly from an aggregated MDP (which includes misspecification error) without employing Dynamics Aggregation, since the misspecified Linear MDP (Jin et al. 2020) also considers the features with a misspecified transition error. However, this approach is not feasible. The critical issue is that the Q-value if they are mapped to the same aggregated (or latent) state. This discrepancy renders direct learning from such an aggregated MDP impossible. Let's provide an example:
differ for two different states, even
Consider an MDP with S = 82), A = {a), and r($1, a) and r(82, a) = O. Let the horizon length H be I. And assume that $1 and 82 are exactly mapped into one aggregated state 31, Then, is clear that ((1 a) = 1 and Q(s2, a) = 0 since H 1.
Therefore, if we consider only the aggregated MDP, we cannot differentiate between Q(si, a) and (s2, a). Note that in our definition of Q-values in Definition 5 we distinctly define the aggregated Q-values depending on the subMDP to which the state belongs. Hence, they have the subMDP index i.
E NOTATION
We offer a Table E. for convenient reference.
We denote H the episode length, K the total number of episodes, and T HK the time elapsed. We denote k E [K] as the current episode and h [H] as the current horizon step. We use subscript k. h to indicate the quantity horizon step h in episode k. We denote L as the number of subMDPs induced by Definition 3 We denote N as the number of aggregated subMDPs defined by Definition 4 and M as the maximum size of the state space of aggregated subMDPs.
For all s S, can always specify one corresponding internal state set ((n) of the aggregated subMDPs M(n), because the entire state space is divided into disjoint subMDPs and each subMDP i has an unique corresponding aggregated subMDPs M("), Therefore, for all E S, if s E St and 3v, (7()) (s), we can simply denote
v (x)) (s). We can abbreviate i or n index, because those indexes are determined by the state s. In this section, for the sake of simplicity, we will use d to
denote the feature dimension of the aggregated state space, i.e., dg.
F PROOF OF THEOREM 2
In this section, we prove the regret bound in Theorem 2 We begin by propose useful lemma:
Lemma F.1. For any (s, a) E S x A and h [H] let s e St, Bej (m) (s), and e = wi (()( Given (n)
any distributions ( (- 3) A(8"), define M(n) u g(m), A, p( rh g.m)) ((m))form [N], where rh (5,a) = E B.npt (rs
(m)
(s, a)), and p (5' s,a) = E, Exppinr [Pj w (8' ss,a]]
Then, we have
(n) In a) r)(s c,,
[P a. P p. (-1 8,aa]l c.
20

---

Published as a conference paper at ICLR 2024
Table E.1: Symbols
8k,h
state encountered in horizon of episode l:
action taken by the algorithm in horizon h of episode A:
th (2(n)
known aggregation mapping from St U Ed to s g(n) in horizon h aggregation mapping kernel satisfying
(n))
V ( = I(s S' ' E'E S(m) u g(m) uh (s) 8)
(s',
M(n)
aggregated subMDPs induced by 1/ ()((m))
h (m) (SE,A) where S4,6 St and 3//h1 (s)
8k,4
8(3)
S-dimensional one-hot vector where the entry corresponding to 8 one
(5a.h, (E,A,,
P/ (. (E.A. (5k,h+1)
D(m)
= {{( (5w. Ow,,, Sk (+1) swi E S", = 4h (i,( (Sw. K=1
k.
regularization parameter
A(x)
-T () a))
k,h
(n)
(A Ei 0(3 ((3)))
P 5,aa
(555, a) T Mk
d
dg. the feature dimension of the aggregated state space
2 (5,
T pe0 min (n((5.)) + ((5.a) P. h+1 + 5 flo(( a) (M2R)
Proof. We only prove for the transition part; the reward part follows from a simi- lar (and easier) argument. Consider any fixed 5 and a. By Definition 4 we have ep for any wh (m)())s)) vi (*) ((())))) (s2). And let (n)
IP; we (.)) a),a) PA (m) (. 82; a)
is the inverse image function of v (xx) Then, we get
[P( (. 8,a) - P v (-) | a))l
Σ
( 3)P (. (3,a) P/ (m)) a)
p
(3) 3) ( (m)) (3,a) - I. w/ (.
(E (n) (3)
Σ
(n) 8) 4
(x)) (- (3,0) - F (m) s s. //1
REV
(8)
Σ
(n)tt(
8)cp cp.
Now, we provide essential lemmas for the proof of the theorem.
Lemma F2 (Difference between jigh and (())), For all k E [K]. h E [H], and n E [N], we have:
(n)
k.h 14 -> (A k,) th
(n)
(A
(n))
Σ
0(3, ()) (s,0,"))
21

---

Published as a conference paper at ICLR 2024
where (n) (8) = p (-1 68)
Proof.
(n) = (k.h))
Σ
(6,,))0(3)
(E,,,"))D (m)
k.
= (A())
-1
Σ
((3,a) (P/ (-13,a) + (5.
kg
(B,, N.h
(n)
Σ
(B,a)) ()(5,a) un (n) t (5,,,)'))
h
(B.0.")) (n)
4.
(A
(n)
Σ
(3,a))(3,a) T1p + (A
Σ
( (n)
(3, (3,
=
k,b
(3,0,")) k.
(n)
-1
(A!m) 21) H/ + (A
(m)
(n)
(m)
Σ
(8,0,,))
k,b
(n)
A
k.h))
[n)
Hh +
(m)
(x0)
k.h)
(x))
Σ
( k.
We conclude the proof by rearranging terms.
Lemma F.3. Fix V S - [0. HJS and 8' (0, 1). For all ls E [K]. h E [H] and n E [N], with probability at least 8', we have
(k- (k-1)03 + 2 1)
1/2
Σ (s. (m) (5,a,)) (Na..")D k.h
d
3H
In
In
8
2
(AD2)
Proof. Denote H4. by all information from the beginning of the learning process up and including (Kg,n, ā.. Then, we first check the noise terms {c), (m) (Sk.A, ak,A, $x,4+1) V) (L..
Note that V is independent of the data because it is fre-fixed. Thus, we have
B[ch
(m) (Sk,h, Ck.h. kk,++1) V He.N =
[c, (Sk,,, aK 5k,4+1) V < 1ch (5x,n. an,h, 54,4+2)l & 2H.
(n)
Therefore, this is martingale difference sequence.
By lemma G.1. all l: [K] and E [N], with probability least 8', we have:
(m)) 1/2 det(Al) -1/2
1/2
Σ 6(3,a)(E) (5,,,))
3/1
In
8'
(3 (n)
(A))))
1
d
(k- In
(k-1) 1)C3 + 1 1
1/2
3H
In
8'
2
where the last inequality is by Eq. F.4
Lemma E.4 (e-covering lemma). For a quadruplet of (n, V, A) where V E H]S, f E Rdxs and | & C₁ Vd, B [o, B), and the minimum eigen value of A satisfying Auin (A) > X, we define O A S - R as follows:
(s) min max (r(s,a) + a(s,a) uV + 810((,,))la-)) .VEE.
VsES.
22

---

Published as a conference paper at ICLR 2024
We also denote the function class O as:
O M. 1|v CN C,H.d. [0, BJ, Amin (A) A}.
Suppose (ō(s.a) Co for all (s.a). Denote e-coerring number of as N₂ with respect to the
distance disl(O, O²) sup, (0(x) (')))) Then, have
1+ 4C + dl In 1+
CB
In([W])) & dln
dg
Proof. Equivalently, we can reparametrize the function class O by defining A -32 Then, we get
Ov.A((s) = min max (r(s, a) + a(s,a) uV + ()((,,))))
(F.I)
where l| 2 & C and ||| & Ba /d/2. Consider any two functions O1, O2 e O taking the form in Eq. F.I. parameterized by (M1, A1) and (u2, V22 A2), respectively. Since both minf-, H) and max, are contraction maps, we have
dist(O1, O2)
< sup (r(p(r())))= ((s u1 (I)() (r(s,a) u(s,u) u2V/2 u2VV 1(0THIV U1 + (0 - (OT 12 [oll
10(s, a))la))))
< sup d
< sup dc
10 1/2 122222+ sup al
(IOT(A1- - -2)d
< <ool((u 12 CoVIA1 A2l1s,
(F.2)
where the third inequality holds due to the fact that for any x, > 0, IVi v we consider the NerKCCT) over {A E Raxdd ||A||F & /dAAA By applying Lemma G.2 we can bound the size
x yl Now
Ne over {uV Rd || & C, H. d and e² 2/C44
of E-net No for O as follows:
In([We) & In In + In (N2
< dln 1+ 4C,CullVd
8B2C2V
+ in 1+
E
Lemma F5. For all (k, h) E [K] x [H] and all n E [N]. we have:
det(A k+11h) det(N/)
C2k +
A
Σ
min 1, 1.16((,a)) (MS2))
< 2
< 2d
A
(le (K, (n)
where yx(x) = {KK, Sw, wa S(m) A /--1
Proof. Since, for any x e [o, 17. holds that x & 21 + x)), we have
Σ min 1, 1, a)l (1() (1))))
Σ
2
1+ [|((5,)))
(1(2)))))) (F3)
(K' (
(W'
( k.
23

---

Published as a conference paper at ICLR 2024
Now, bound the right hand side of Eq.
F.3
Since
K41,
kih +
I (3x,, E s(m)) 0(3k,,, ag h ax,) we have (n) det(A k+1h)
dee((A (m)) det (+ (A "I (5A. E strr) ans) V (MEth
dot(A
(saa E e (0(Sk,, (A(C))
det(A
(m))
SKi E s(r)) 110(5 ox wwllil 1+1 ===1
π
(1
[+ [+]10(3,0))
det(AAg.)) (13)
a)) a)l
(A(t)) )1)
= det(A
1+ (+ a)l
(k', (,)
where (nn) == {K', 3a axa)): B S(m)) /
Note that empty product, in case of (m)
W=1
k.
Ø, is one in convention. Therefore, we have
Σ
min Lim.L11003,.. a)) a)ll (2)))
Σ
21n 1 + (()(,,)))
(1
(A
(
(1)) < 2l
(41.1) det(AT)
which proves the first inequality of the lemma. Next, we consider the second inequality. For the trace of A (n) k+1.k get
tr(A k+1, = tr
AT
Σ
((,,))((,a)T
Ad +
Σ (0(5,a)13 x Cjdk: Ad.
(M
Then, since (n)
1 1 is positive definite, we have
det(A(()) (n) det(AI)
kFLN)
(r((A()) (n)
(FL//) tr(Al/d)
Cak + A A
(F.4)
which concludes the proof.
We now can construct uniform convergence argument for all defined in Lemma F.4 Lemma E.6. Fix 8' (0, 1). Suppose that 8R, E S(n), Then, for all E [K], E [H], and O O, there exists constant C > O such that, if we denote E as the event that
((PP))) k.h - Tp("))(- Bk. (k.n) o
C (.HH (ndT//88)) [| ax (A
then P(F) 8
24

---

Published as a conference paper at ICLR 2024
Proof.
(f - 1. sy,n, am.)) 0
(5k,h ax.b) T ( (f - 1 (1)) (1())) .0
(5kk ak,,) > ( (mm) ph o + (5 axn)
[A(m) k
Σ
(f.
(F.5)
where (5 as.A) first term of Eq. F.5
(5kk, (k,a) and the last inequality by Lemma
F22 First, we bound the
p( a (A (1))
-1 kAh. ph (n) o V akbia) (ag2))
(x) Oll2
CuV AdH | akchl (AS22) (A(
(F.6)
where the first inequality follows the fact that (A (R) term of Eq.
-1
is at most 1/A. Now, we bound the second
F.5
(5kk,k ok.
(A(2)
(n)
Σ
6(3 a)e, (s,0,)
< |1((5k,n OR.N (4))))))))))))
Σ
(s,
(
(A!h))
(F.7)
For arbitrary O E O, by the definition of s-cover. there exists a V E NN., such that |0 - Vl & E. Hence, we get
Σ ((3,0)(c))) (") (8,0,)) -0)
(1/22)
Σ " () A
Σ
+
(A
2ECokH
Σ (( (3,,,))
+
VA
( (o)
(11)) -1
1/2
1 d ln
(k (k- 1)-3 +
2=CskH
3H
In 8
In In/NV
VA
25

---

Published as a conference paper at ICLR 2024
where the second inequality is by the fact that
Σ (3, (6
< 2sH
Σ
p(3,a)
(5,0,3))
(A!:2)
2cH
Σ
((3,a)
VA
(8,,,5))D h.
(n)
2=CakH
V/
and in the last inequality, we use Lemma F3 with applying union bound over all functions in Ne Therefore, by applying Lemma R4.
we have
Σ
(5 (m) (3, (s,a,))) .0)
(E k,6
(A(O))
d
(k- - 1)C 2 + +1
dln ( 1+
4C,CuHVV d2In
( 1+
8B2C
3H,
In
+
In
2
E
Ae
2=CakH
V1
Now, we choose the hyperparameter = = C dH In(dT/8') where C an absolute constant. Set d/k, then there exists a absolute constant C' > 0 such that
Σ (8,,)))
& C dH (n(dT/8)).
(F.8)
Combining the results of Eq. such that
F.6 Eq.
F.7
and Eq.
E.8
together, there exists absolute constant C 0
(p()) k.h -P())) (. 5k an an.
AdH (o(kk (2(33)
1 C² C (HIn(dT/8") | (c,)) (aE22)
C dH In(dT/8)) |0(5k, ap. (1(00)-1 (1)0))
Lemma F.7 (Optimism). Suppose that event E. defined in Lemma F6 and h [H], we have
happens. Then, for all k [K]
Qu.(s, > (s) - H(H + 1 h)cp, Vs, a.
Proof. First, consider fixed episode k. We prove via induction on h. For h H, the statement is true since Qu.tr(s,a a) r(s,a) Q (s, a). Assume the lemma holds for some h + & H. Then, for all s E S, we have
Vi.4+1 (s) max (2, > (+) H(H h))p
26

---

Published as a conference paper at ICLR 2024
For any (s. E 8 A and h e [H]. let St, (/th))))))))))))) (s), and 4/ (((((()) (6). Then, we have
(n(3,a) + P 5,
(1 (A.%)- 0 0)
RA-1 (00)
8
(s)
-8110(5,a)) a)]l (A::)) + pap ( kAtt Pi 8, V
Bll0(5, a)]l (AS:) + Pi 3.
AA441 PA s. a. a H(H c
B (10(5, a) (1(2)
(P - ) 3,a)
2010 k.+1 +P (: (1,,)) -P s, V
-H h)Ep
=B a)]l (42.6)
+ (P()) - ). 3.a) khtt (: (1,)) - up s, k1h+1
-H(H h)cp
> 3 (10(8, ()]l(( (af.1))
a)]l
+ k. - P. 8, 8 kh+t + 11ep +1
> - - +1 h)ppT
H - hp where the first inequality is by the inductive hypothesis that V (s')+ 3 (
for all s' E S, the third equality is by the fact that 1s') = 1 (3') for s' E S u E and
Py (s') [ss a) 0 for s' St U Et, the second inequality is by Lemma Fl and the last inequality is by applying Lemma R.6 with V-((()
O. This concludes the proof.
Lemma E8 (Regret decomposition). On the event E. defined in Lemmal
F.6
we have
K
N
K
(Vi VTTh
&
Σ
23, min 1, 1,110(5,
(A
Sk
(K,3,a)EX K.A.
+ Hpp
K k= Sa where Y(a) = {(k, J2 an,)) : BR,n E ((m))
= El(AAn- - -V | 88,,, 0x,0]
(Vi. (5k,t) and dH Indd (8") for some absolute constant C 0.
Proof. Assume that the event E' holds true. For any & E [K]. without loss of generality, suppose ,k,8 E St ,...,,.."" 8k,1 E Stn), 8R.2 E s(a),.... then we have that
8k,1 E 86,2
(Vi* - VTT & (Vk.1 - Vi*t HH&p
(Qx.1 O (5H,), 02,1) + I12E,
= 3 10(5,,1 an. }ll (161)) -1 + +P//)( 56,1, ax,
De(()) - -P-(-1 86,1, (k,,, 12 + HPPr k.2
= 3 16 ar. )1l (1.:)) + (fPM)) p( 5k,1, ax.1) 14.1) V k,2
+ pp 5k,,1, ax,1) V (00
Pi SK, aB, 112TT + H!&,, pp
& 3 10(52,11 14.1)) )ll
+ (f)(m) p( 8k,1, 0x
+ p ppppptao(( 8k,1 (x.1) D/10 (e00) k22
(nl) (M..1)
k.l
Pi( sk,1, V2 + HH + 1)cz
= 1010 (4.1))
+ (P( p( 5k,1, 1x.1) k.2 + Pi( sk, a v
(A(1))
+ H(H + 1)Ep
< 29 [0((5,11, ak. )l1 (m1) -1 Pi(-1 | sk, ar VTTh) H(II + 1)ep
- 23 (1 ax.1 )ll (A.:)) -1 + B[(VE.2 - ) 88,,1, ac.1) + H(H + 1)(p,
27

---

Published as a conference paper at ICLR 2024
where the first equality is by Lemma by the fact that 2s') v
F.7 the second inequality is by Lemma F.1 the fourth equality
(s') for s' St E and PPj (s' 8k,1, (x,1) for
R22
s' & S' E and the third inequality is by Lemma F6
Define SR,A as E[(VE, V/ (82,at sk,h, CR,A
(Vu,n (x Then, we get
(Vi (8k,1)
& 2B 10(5,;1,, (x,1 (11.)) 1 + Sk. + (Vr.2 12th + H(H + 1)cp
2/]10( 1k.1 ak.1) )| (11))
23 ax.2) (1m7)))
Sk,1 Sk.2 (Vk.3 (5k,)) H(H 2)cp
N
H
Σ (S 23 oRAAal (A(-))-++ -11))1++ (42.h)
Σ
Sk.b + 2122
Further, since we immediately have (VF - (sk,) < H. we derive that
(8K,))
N
H
H
min
Σ
SR.6 E s(m)) 2310(5 ax,)) (1602)
Sa, + 2HH H
N
H
K
H
Σ
Σ
TI
5k. E s(a)) 23 (1632))
Sk.b + 2T
K
SK, E s(m)))
23
1, 1, al min
SA. + 27 2T HEp
(1112)
N
K
K
Σ
Σ
B E s(w))
28
1, 1, all min
+
SA. + HT
(110)
n-1 1=1 1=1
k=1
N
H Sk.b + 2T
Σ
23,
min 1, 1,110(8, a)l?
+
n=1A
(k,3,a)e (m)
where y(n) = 5k, ak,)): : 5k,n s(ni) K
and T KH.. This completes the proof.
Proof of Theorem 2
On the event E defined in Lemma F6 by Lemma E8
have
K
N H
K
(v (Sk,))
&
Σ
28, min 1, 1,110(5, 1)
Sk.h
(1
(1)))=1
72
(K,5,
(n)
R=1
+ HT.
(F.9)
First, we bound the first term of Eq.
F9
Then, we have
N
23
min
10(5, a)l
(MS1))
K.A.
N
& 222KK KH
Σ
Σ
min 1, 1,16(3, a)l?
(A2:)--
(K.8,a)e
C2k + A
& 223KKR KH
NH 2dIn
(F.10)
28

---

Published as a conference paper at ICLR 2024
where the first inequality is by Ctuchy-Schwarze inequality, the last inequality is by Lemma F.5 For the second term of Eq. F.9 since E [Sk. Mx,A-1] = and [Sk. & 2H for all (k, h), SR. is bounded martingale difference sequence. Therefore, by the Azuma- Houma- inequality, for any
t > 0, we have
-12 2T
P
Σ
Σ h-1
kk >1
exp
Hence, with probability at least - 5/2, we have
K
11
Σ
SE
& v 2TH (2/0) & 2/ Tln(2/8))
(F.11)
Finally, combining Eq. F9
Eq. F.10
Eq. F.11 and with choice of B C. dH (2(27/88) for some 5, have
absolute constant C, with probability at least
K
Σ (V/ - (sk,)
C2k + A NH 2d
< 20 . dH In(2dT/0)VKH
+ 2/1 2/ TlI(2/2(2/))) + 2T
A
OLVEH3NT THe))
THpp),
=
where the last equality is by the fact that d = dg. This concludes the proof.
G TECHNICAL LEMMAS
Lemma G.1 neef-normalized process, Abbasi- Yadkori et al. 2011). Let {xe] be real-valued stochastic process over the filtration (FiJi-o- Let xi be conditionally B-subgaussian given Fi-1-
Let 12 with o. Fi-1 be a stochastic process in Ha Assume that Do a d positive definite matrix, and let A = Ao + Σ._1 Φ.0.. Then, for any > with probability at least 6, we have for all I 2 0:
det det((A) 1/2 det(Ao)
Σ P.IZ
2B2 In
The s-covering number of an euclidean ball of radius B in Rd is upper bounded by (I + 2B/ejd.
Lemma G.2 (Covering numbers, Pollard 1990).
Lemma G.3 (Relation between packing and covering numbers, Pollard 1990). Let (G, 1 1) be normed space, and θ = G. Then,
T(0,2E, & N( e, 1) =(
where T(O, e, is the E-packing number and ((,,,, s, | the e-covering number.
H BLOCK-RIVERSWI ENVIRONMENT
this section, we provide detailed explanation of the structure the Block-RiverSwing environment. In our experiments, tabular setting a special case of the linear model (Jin et al. (2220).
the tabular setting it is casy to construct linear transitions. Note that the
Biock-RiverSwim is constituted of S states, including the initial state 81, R blocks each containing 3 states, and a rewarding end state sg. Hence, the equation S = 3R + naturally holds true. Each of these blocks has identical structures: the same transitions and reward functions. Please note that the number of subMDPs L amounts to R + 2 (made up of R blocks, $1, and ss) and the total of aggregated subMDPs N equals to (comprising aggregated block, 81, and sg).
29

---

Published as a conference paper at ICLR 2024
0.4
0.6
DLB
0.6
0.09
B.
0.05
0.7
0.05
0.6
0.d6
0.16
1
0.35
0.35
0.6
Figure H.1: The Block RiverSiiv environment with repeating sub-structures (R) with size (Blocks) and S 14 states. State 81 has small reward of r(s), left) 5/ /0000, while state has a large reward 4, by left actions. And line arrows refer stochastic transitions caused by right actions.
1. The dashed arrows indicate deterministic transitions caused
Starting at the agent can select to move left, an action denoted by the gray dashed lines, and as result, obtain a minor reward, r(s1, left)= 0.005. Alternatively, the agent can choose navigate to the right, an action represented by the black solid lines, in each successive state. The objective for the agent is maximize its total return by attempting arrive at the far right state, denoted ss- and move to the right to earn a large reward r(as, right) 1.
Figure H.T depicts the diagram of Block RiverSii with 6 (4 repeating substructures, i.e., R = 4, and unique substructures, thus N 3) and S = 14. This environment consists of the initial state 81. the big reward state $14, and 4 blocks, each which consists of three states. The goal of the agent is to maximize its return by learning the policy that reaches the rightmost state, where the large reward r(s14, right) = can be obtained, as fast as possible.
30


Reviews:
[{"review_id": "XKs0BWXKb9", "reviewer": "Reviewer_kJCM", "summary": "Recent advancements in reinforcement learning (RL) have spotlighted function approximation to address the generalization challenges in tabular Markov Decision Processes (MDPs). Linear MDP, a cornerstone model, has demonstrated that regret bounds are influenced more by feature dimension rather than state space size. However, the authenticity of this claim is examined in this paper. Researchers found that for appropriate representation of the probability space, the feature dimension is inevitably influenced by the size of the state space. A discrepancy was observed in the relationship between the feature dimension and state space size, especially as the latter expands. It's concluded that linear MDPs might not inherently allow learning detached from state space size. To counter this, the paper presents a new hierarchical framework called dynamics aggregation. It encompasses both state aggregation and equivalence mapping, promoting efficiency and adaptability. A hierarchical reinforcement learning (HRL) algorithm is proposed within this structure, which is statistically efficient and offers a comprehensive regret bound. The algorithm is validated against existing methods, showcasing its superior performance.", "questions": "1.For the proof provided for Theorem 1: suppose that there exists a state-action pair$(s, a)$ for which the transition probabilities are non-zero for more than $U$ states. How would this affect the recursive logic applied in the derivation of $\\operatorname{rank}(\\mathbb{P}_h) \\geqslant\\lfloor S / U\\rfloor$? Would the derived relationship between $d$, the rank of $\\mathbb{P}_h$, and the relationship $\\lfloor S / U\\rfloor$ still hold? \n\n2. Feature Dimension vs. State Space Size: Given that the research reveals a deeper connection between feature dimension and state space size than previously thought. What is potential future work especially in contexts where the state space is vast?\n\n3. Hierarchical Structures in Real-world Scenarios: With the proposed dynamics aggregation framework depending heavily on the hierarchical structure of problems, how feasible is it to identify or establish such hierarchies in complex, real-world scenarios, where the state dynamics might be more intricate and less structured?\n\n4. This paper mentions several examples in section 4. How does this method work and does it perform well in these examples?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper questions the widely accepted belief about linear MDPs, delivering a comprehensive critique of its fundamentals.\n  \n2. The new framework, which fuses state aggregation and equivalence mapping, holds promise for addressing the limitations of linear MDPs, making it a significant contribution to the field.\n\n3. The proposed HRL algorithm not only introduces an innovative approach to RL but is the first of its kind to provide proven guarantees in function approximation.\n\n4. The inclusion of numerical experiments fortifies the theoretical claims, showcasing the algorithm's efficacy against existing counterparts.", "weaknesses": "1. While the new algorithm excels in controlled experiments, its scalability and performance in more complex, real-world scenarios are yet to be determined.\n\n2. While numerical experiments are conducted, this paper mentions several examples in section 4 but does not include experiments and analysis in these examples.", "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": "", "extra_scores": {}}, {"review_id": "VvhGRYIc61", "reviewer": "Reviewer_hMDT", "summary": "The paper focuses on the problem in the linear Markov decision process and its linear representation to the transition probability kernel. It first shows that the current regret results form the literature has the dependency on the state cardinality, which comes from the fact that the dimension of the linear representation for the transition kernel is lower bounded by the rank of the matrix. Then it leverages the technique from the previous works on state aggregation and group mapping to propose a hierarchical version of the linear MDP algorithm, reducing the final regret dependency on the state cardinality to the grouped MDP dimension.", "questions": "The assumption of known dynamic aggregation is strong to me. In reality, how could we extract such information without knowing the transition kernel?\n\n============= After rebuttal  ============\nI really appreciate the author/s effort in addressing my concerns and questions. After checking the author/s response and other reviewers' comments, I would like to increase my score from 3 to 5, since I am still not totally onboard with the additional stronger assumptions about the dynamic aggregation and the very similar algorithmic design as previous works.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper shows that the dimension of the linear representation for probability transition kernel is lower bounded by |S|/|U|, where |S| is the cardinality of the states and |U| is the maximum size of directly reachable states. If |U| is not the order of |S|, the regret would depend on the state cardinality.\n2. The paper develops a hierarchical linear MDP algorithm to reduce the state cardinality dependency in the final regret. It leverages the internal structure of the problem with the state aggregation and mapping from previous works. The final regret and examples show the effect of it.", "weaknesses": "1. The paper makes stronger assumption than previous linear MDP algorithms. For the sub-structure that is explored by the paper, it assumes that the dynamic aggregation is known and has the desired boundedness in Definition 4. \n2. For the final regret proven by the paper, although the regret seems to be improved in terms of the state cardinality theoretically, it also introduces another T-dependent term characterizing the aggregation gap w.r.t the original probability transition kernel. It's not clear to me whether the newly introduced term would cancel out the improvement from the first term in Theorem 2.\n3. The algorithm seems to be a direct extension of the previous works in the tabular case by adding in linear representation and similar analysis.", "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": "", "extra_scores": {}}, {"review_id": "n4OC8cN4pZ", "reviewer": "Reviewer_M46L", "summary": "This paper provides two interesting contributions:\n\n1) It shows a lower bound on the feature dimension in linear MDPs which depends on the inverse of the maximum reachability of the environment.\n\n2) It provides a novel algorithm with sublinear regret for hierarchical RL where each of the subMDP is a linear MDP.", "questions": "1) Can you provide an example of aggregating functions $\\psi$ such that the error $\\epsilon_P \\leq 1/\\sqrt{T}$ ?\n\n2) Another related question is: do you expect $\\epsilon_P$ to decrease as the number of subMDP $N$ increase ? Is it possible in this way to find the value of $N$ which minimizes the regret bound? \n\n3) Could add an example of Linear MDP where the conditions $MN \\leq S$ and $M^2 \\leq S^2/U^3$ hold and therefore the hierarchical algorithm has a clear advantage ?\n\n4) Can the assumption of known aggregating functions $\\psi$ be relaxed ?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "I think that (albeit simple and potentially expected) the lower bound on the feature dimension of Linear MDP is an important result for the RL theory community.\n\nThe algorithm (UC-HRL) seems to be an interesting and novel contribution to hierarchical RL.", "weaknesses": "The regret bound in Theorem 2 has a linear term which can be made sublinear only if $\\epsilon_P$ in Definition 4 is of order $\\mathcal{O}(1 / poly(T))$. However it is not very clear from the paper how big $\\epsilon_P$ can be for common choices of the approximate feature aggregation mappings $\\psi$.\n\nThe fact that the aggregating functions $\\psi$ are required to be known in advance seems rather strong but somehow common in hierarchical RL.\n\nThe discussion after Theorem 2 that justifies that $d^3_{\\psi} N \\leq d^3$ is unclear in my opinion in particular I do not understand why the regime $MN \\leq S$ and $M^2 \\leq S^2/U^3$ is a reasonable one. Maybe the author should consider expanding this discussion in their revision.", "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": "", "extra_scores": {}}, {"review_id": "ZnKbLOSaAc", "reviewer": "Reviewer_JZay", "summary": "This paper provides a new perspective into the low-dimensional representation structures of MDPs. On the one hand, it casts reasonable doubt on the popular linear representation structure via a simple lower bound on the feature dimension $d$, showing that $d$ may actually scale up with $S$ when the direct reachability $U$ of the environment is limited. On the other hand, it proposes a novel dynamics-based hierarchical aggregation framework that leverages *known* mappings to aggregated sub-MDPs (each equipped with linear representation structure), and shows that it achieves a competitive regret *under certain assumptions*.", "questions": "1. Why would people have the aggregation mapping $\\psi^{i \\to (n)}$ in hand *a priori* in modelling?\n2. In what kind of real-world environments would the condition $d_{\\psi}^3 N \\ll d^3$ be met? Please provide concrete examples.\n3. In Algorithm 1, $n$ and $i$ seems to be variables that automatically get their values upon observation of states. Should it be written in a clearer way to show that $n$ and $i$ are actually calculated from the state?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper provides a new angle for researchers to understand the fundamental limit of linear MDPs. The result by itself is technically simple and straightforward, but the valuable part of it is the motivation it provides to reflect upon a popular modelling option that is potentially subject to implementation issues.\n2. The flow and writing of this paper is good. It provides the reader with adequate background knowledge, illustrates the key points clearly with concrete examples and figures, and accompanies the main results with intuitions and discussions.\n3. The mathematical proofs seem correct to the reviewer in the form they are presented in the paper, though results cited from literature are taken for granted.", "weaknesses": "1. The authors claim that the dynamics-based aggregation framework proposed in the second part of the paper *addresses the limitation of linear MDPs*. The reviewer is skeptical about the contribution, in that:\n    * The aggregation framework seems very artificial. There is not enough motivation why people would have the aggregation mapping $\\psi^{i \\to (n)}$ in hand *a priori*. Specifically, why don't people directly consider the aggregated MDP when they model real-world scenarios, but rather introduce a large-scale MDP and identifies the similarity between (unnecessarily differentiated) states in the meantime?\n    * Apart from the novel idea of substructures, the contribution of the second part seems minimal to the reviewer since it looks like a simple application of LSVI-UCB in sub-MDPs. The proof structure is also similar to that of LSVI-UCB with minor changes.\n    * The results will be very interesting if the aggregation structure can be learned (either online or offline) rather than given, but reviewer fails to come up with a quick fix that enables such learning. The reviewer would be more positive about this paper if the authors can, at least, illustrate a potential algorithm design idea to learn the structure.\n2. The comparison against LSVI-UCB seems sketchy. The authors claim in the abstract that $d_{\\psi}^3 N \\ll d^3$ is \"readily met in real-world environments\", but the only discussion about this is a few conjectured inequalities on page 9 without any real-world data. This seems like too much overclaiming to the reviewer, and thus the authors are urged to provide real-world evidence for their claim.\n3. The experiment design can be improved in the following ways:\n    * The source code to reproduce the results is not publicly available.\n    * The environment is designed to be tabular, which is reducible to linear MDPs, but only in a very inefficient way. The comparison is therefore unfair. It would be more convincing if the algorithms can be evaluated and compared in MDPs with intrinsic low-dimensional structures.\n    * The MDPs used in the experiment are very small in size. Experiments are expected to, at least, show adequate scalability of the algorithm.", "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": "", "extra_scores": {}}, {"review_id": "uLaD7PlmBM", "reviewer": "Reviewer_Taww", "summary": "In this paper, the authors prove a lower bound of $d$ for the linear MDP to aptly represent the transition probability. Therefore, they claim that linear MDPs may have regret guarantees dependent of the state space. To address the issue, they propose a novel structural aggregation framework based on dynamics, named as the dynamics aggregation. For this framework, they design a provably efficient hierarchical reinforcement learning algorithm and provide a regret upper bound for this algorithm.", "questions": "Please refer to the weakness section. Generally speaking, I lean towards acceptance of this paper because of the interesting lower bound and its meaningful insights.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The problem of proving lower bounds for $d$ and considering hierarchical structure is very interesting and important.\n\n2. The paper is solid, the proof looks correct to me. \n\n3. The lower bound is meaningful, demonstrating the limitations of the linear MDP. \n\n4. The presentation is clear in general. The simulation is interesting.", "weaknesses": "My main concern is about technical novelty. The dynamics aggregation is very similar to the misspecified linear MDP considered in [1]. Also, the algorithm is adapted from LSVI-UCB. The result can be expected given [1]. \n\n[1] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan. Provably efficient reinforcement learning with linear function approximation.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)