Demystifying Linear MDPs and Novel Dynamics Aggregation Framework

We sincerely thank you for your time to review our paper and for your positive and valuable feedback. As you pointed out, the findings of Theorem 1 are of great importance. We anticipate that these results will significantly influence the RL community.

Regarding the second part of our paper, we emphasize the broad impact of our dynamics aggregation framework, particularly its seamless integration into existing algorithms. This indicates that our framework can be readily applied to a wide range of Linear MDP algorithms, thereby improving their efficiency. Additionally, we believe that investigating methods with higher versatility – those that can easily adapt to existing algorithms – is a crucial research direction.

Here are our response to your question:

1. Dynamics aggregation vs misspecified Linear MDP

If we have understood your question correctly, it appears that you are inquiring about the distinction between employing dynamics aggregation and directly learning from an aggregated MDP that contains a misspecification error. However, we cannot directly consider the aggregated MDP since the Q-value may differ for two states that are mapped to the same aggregated (or latent) state. Let's provide an example:

Consider an MDP with $\mathcal{S} = \{s_1, s_2\}$, $\mathcal{A} = \{a\}$, and $r(s_1, a) =1$ and $r(s_2, a) =0$. Let the horizon length $H$ be 1 for simplicity. And assume that $s_1$ and $s_2$ are mapped into one aggregated state $\bar{s}_1$. Then, it is clear that $Q(s_1, a) = 1$ and $Q(s_2, a) = 0$ since $H=1$.

Therefore, if we consider only the aggregated MDPs, we cannot differentiate between $Q(s_1, a)$ and $Q(s_2, a)$. Note that in our definition of Q-values (Definition 5), we distinctly define the aggregated Q-values depending on the subMDP to which the state $s$ belongs. Hence, they have the subMDP index $i$.

2. Comparison to LSVI-UCB

The key distinction of our algorithm compared to LSVI-UCB lies in its model-based nature. This primarily brings the advantage of reusability. In model-free approaches, Q-values are defined by the aggregated feature and specific parameters ($w_h^{\pi}$ in Jin et al., 2020). Thus, it's impossible to distinguish the Q-values for two states mapped to the same aggregated state $\bar{s}$. As mentioned above, the Q-value may differ for two states mapped to the same aggregated state. In essence, model-free approaches fail to effectively leverage the hierarchical structure, even with perfectly learned sub-structures and accurate mapping. On the other hand, our model-based approach enables the reuse of learned dynamics of subMDPs ($\hat{\mu}^{(n)}$) 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.

We sincerely appreciate the time and effort you have invested in reviewing our paper. Thank you for your feedback, and we are more than happy to address your comments and questions. Below, we address each point raised in your review with the aim of clarifying and further enriching our research.

1. Motivation for dynamics aggregation

We cannot directly consider the aggregated MDP since the Q-value may differ for two states that are mapped to the same aggregated (or latent) state. Let's provide an example:

Consider an MDP with $\mathcal{S} = \{s_1, s_2\}$, $\mathcal{A} = \{a\}$, and $r(s_1, a) =1$ and $r(s_2, a) =0$. Let the horizon length $H$ be 1 for simplicity. And assume that $s_1$ and $s_2$ are mapped into one aggregated state $\bar{s}_1$. Then, it is clear that $Q(s_1, a) = 1$ and $Q(s_2, a) = 0$ since $H=1$.

Therefore, if we consider only the aggregated MDPs, we cannot differentiate between $Q(s_1, a)$ and $Q(s_2, a)$. Note that in our definition of Q-values (Definition 5), we distinctly define the aggregated Q-values depending on the subMDP to which the state $s$ belongs. Hence, they have the subMDP index $i$.

We acknowledge that our initial explanation of the motivation lacked sufficient detail. Thank you for bringing this to our attention. We will ensure to provide a more detailed explanation in the revised version of our paper.

2. Contribution of the second part

The core contribution of our paper extends far beyond the introduction of a new algorithm. Our work provides critical and previously overlooked insights into linear function approximation (the fundamental limitation of Linear MDP that no previous works have addressed), insights that have the potential to fundamentally redirect the trajectory of future research in this area. This novel perspective, presented in the first part of our paper, represents a significant implication on the current theoretical RL research. Therefore, we respectfully suggest that the evaluative focus should not solely be on the latter sections of our work. The first part of our paper, which lays the theoretical groundwork for the second part, is deserving of particular attention. It is here that we challenge and expand upon the established norms, offering a fresh lens through which to view and understand the field. We firmly believe in the substantial impact our paper can have on the academic community.

2-1. Versatility of dynamics aggregation

We believe that the ability to seamlessly integrate our dynamics aggreagtion framework into existing algorithms indeed indicates its extensive impact, rather than suggesting a minimal contribution. This implies that dynamics aggregation can be easily applied to various Linear MDP algorithms, enhancing their efficiency. We also think that exploring methods with greater versatility, ones that can easily adapt to existing algorithms, is an essential avenue for research.

2-2. Comparison to LSVI-UCB

Compared to LSVI-UCB, the most salient feature of our algorithm is that it is model-based, which notably offers the advantage of reusability. As previously mentioned in 1, re-using aggregated Q-values is not feasible in model-free approaches because the Q-values for two states mapped to the same aggregated state can differ. This limitation means that model-free approaches are unable to effectively utilize the hierarchical structure, even with perfectly learned sub-structures and accurate mapping. In contrast, our model-based approach allows for the reuse of learned dynamics of subMDPs ($\hat{\mu}^{(n)}$) in similar subMDPs. Although the proof structure appears similar, the underlying intuition and significance of the model-based approach in leveraging the hierarchical structure are crucial.

3. Learning dynamics aggregation

While it is not our focus to deal with learning mapping, we believe that the known dynamics aggregation assumption can be relaxed through the use of model selection techniques, as proposed in [4] and [5]. At each episode, the agent selects one of the base mappings to play and receives the rewards associated with the (low level) policy deployed by that base mapping. Then, it updates the (high level) policy for selecting the base mapping. However, this is currently unclear and beyond the scope of our work. We will leave such research directions for future work.

However, more importantly, we highlight that the assumption of a known hierarchical structure is actually common in hierarchical RL (for example, Wen et al., 2020 [3], also assumed a known equivalence mapping).Furthermore, in real-life scenarios, humans often utilizes the (approximately) known mapping between two similar environments, even if they don't know the transitions. Take, for instance, playing different versions of video games such as Super Mario. Despite variations in each game, the core gameplay mechanics stay the same -- a fact that players often grasp intuitively or through prior knowledge.

Therefore, especially in scenarios typical of human learning, knowledge of dynamics aggregation is quite common. We suggest that the RL community should focus more on HRL frameworks. Doing so could lead to the development of algorithms that approach the efficiency seen in human learning.

Furthermore, it is important to recognize that the presence of an additional structure, or a seemingly stronger assumption, in a research framework should NOT lead to its immediate dismissal. On the contrary, when such structures are well-justified and relevant, they can be pivotal in advancing efficient learning methodologies. For example, in the study of LinearMDPs, initial efforts concentrated on cases with known features. Only in more recent times have researchers started to develop techniques for learning these features. Similarly, in HRL, the long-standing assumption has been the presence of known options. Very recently, the focus has shifting towards the emerging field of option learning. This principle is at the core of our approach. Our assumptions regarding dynamics aggregation are not just theoretical ideas; they are based on observable phenomena in actual learning environments (refer Appendix C.2). We are convinced that our discoveries about the fundamental limits of Linear MDPs are vital. Our proposed framework lays the groundwork for future research. It creates opportunities for a balanced approach that combines theoretical thoroughness with practical applicability.

[1] Cutkosky, Ashok, Abhimanyu Das, and Manish Purohit. "Upper confidence bounds for combining stochastic bandits." arXiv preprint arXiv:2012.13115 (2020).

[2] Cutkosky, Ashok, et al. "Dynamic balancing for model selection in bandits and rl." International Conference on Machine Learning. PMLR, 2021.

[3] Wen, Zheng, et al. "On efficiency in hierarchical reinforcement learning." Advances in Neural Information Processing Systems 33 (2020): 6708-6718.

4. Additional explanations about $d_\psi^3 N \ll d^3$

In the abstract, we claimed that the inequality $d_\psi^3 N \ll d^3$ is valid in most real-world environments with hierarchical structures. By most real-world environments, we refer to scenarios where the size of directly reachable states $U$ is much smaller than $S$ (for continuous state space, consider $U$ as $Vol(\mathcal{U})$ and $S$ as $Vol(\mathcal{S})$). The real-world examples where this condition holds are extensively discussed in Section 4. Examples 1, 2, 3, and 4 all meet the condition that $U$ does not scale with $S$. On the other hand, since $M$ represents the maximum cardinality of subMDPs, $M \ll S$ is true if a hierarchical structure exists (with small sub-structures repeating). Consequently, the inequality $M^2 \leq S^2/U^3$ is satisfied (as $U$ is negligible), leading to the desired result.

5. Experiment design

5.1 Source code

We have attached the source code as supplementary material.

5.2 Desigining low-dimensional features

We appreciate your question as it allows us to clarify our main claims and what we aim to emphasize in Theorem 1: it is impossible to design low-dimensional Linear MDP structures. The transition kernel of the RiverSwim environment is fully ranked, i.e., $rank(\mathbb{P}) = S$ (refer Appendix B.5). In this scenario, can any method decompose $\mathbb{P}$ into two matrice $\mathbb{P} = \Phi \mu$ without an approximation error, where the column dimension of $\Phi$ and the row dimension of $\mu$ are significantly smaller than $S$? The answer is NO. In linear algebra, particularly in methods like SVD, the column dimension of $\Phi$ and the row dimension of $\mu$ are required to be $S$. This is exactly what we claim in Theorem 1! Unless directly reachable states (by single-step transition) scale with the entire state space by constant factor, (i.e., $U = \Theta(S)$) the feature dimension $d$ should scale with $S$ in Linear MDP.

5.3 Size of experimental environment

Since designing low-dimensional Linear MDP structures is impossible, implementation of algorithms in Linear MDPs confines us to a (nearly) tabular setting ($d \approx S$). A major challenge with all existing Linear MDP algorithms is the necessity to compute the inverse of the Gram matrix, incurring a computational cost of $O(d^2) \approx O(S^2)$. This is intractable when $S$ is very large. This limitation hinders the expansion of the state space size. It is important to note that all existing Linear MDP algorithm experiments have been conducted in a tabular setting ([4] and [5]). And in this work, we have provided a theoretical proof explaining why they couldn't (Theorem 1).

Please not that, this issue is a common challenge encountered in all Linear MDP algorithms. However, in the case of an MDP with a hierarchical structure, where small sub-structures repeat ($MN \ll S$), our algorithm can be effectively implemented since $d_{\psi}\leq M \ll S$, requiring only a

We sincerely appreciate the time and effort you have invested in reviewing our paper. Thank you for overall positive evaluation of our paper. Below, we address each point raised in your review with the aim of clarifying and further enriching our research.

1. Dynamics aggregation misspecification error

The term $\epsilon_p$ represents the model misspecification error allowing that our modeling assumption may be imperfect. Model misspecification is very common in real life and has been often considered in many previous works in Linear MDP. For example, in [1] (Theorem 3.2), [2] (Theorem 1) and [3] (Theorem 1), the authors proposed regret bounds that also involve the term $T \epsilon$, where $\epsilon$ is the model misspecification error. Therefore, the term $\epsilon_p$ represents the effect of model misspecification on regret, rather than implying that regret is directly proportional to $T$. Now, there are many works that assume there is no misspecification error, namely assuming that their modeling assumption perfectly reflects the environment. We could also do so and not deal with the misspecification error if we desired. Yet, we wanted our framework to be more inclusive when presenting the problem formulation, allowing for possible model misspecification. In essense, this is just a matter of problem setting by our choice. That is, if you wish, we can certainly consider problem setting without model misspecification. We strongly believe that this should not be any disadvantage on this part. We will make this much clearer in our revision.

Furthermore, the relationship between $N$ and $\epsilon_p$ is not clear to us. The model misspecification error $\epsilon_p$ is generally not within our control, as it is primarily determined by the specific model (or mapping) we select.

[1] Jin, Chi, et al. "Provably efficient reinforcement learning with linear function approximation." Conference on Learning Theory. PMLR, 2020.

[2] Zanette, Andrea, et al. "Frequentist regret bounds for randomized least-squares value iteration." International Conference on Artificial Intelligence and Statistics. PMLR, 2020.

[3] Zanette, Andrea, et al. "Learning near optimal policies with low inherent bellman error." ICML, 2020.

2. Additional explanations about $d_\psi^3N \ll d^3$

2-1. $MN \leq S$

Note that $M$ denotes the maximum number of states within a subMDP, and $N$ indicates the number of aggregated subMDPs. Therefore, $MN \leq S$ suggests the presence of a hierarchical structure characterized by repeating small sub-structures. Our experimental setup, Block-RiverSwim, exhibits this hierarchical pattern (see Appendix G and Figure G.1 for details). Figure G.1 illustrates the Block-RiverSwim structure with $S=14$ and $L = 6$ (representing the number of subMDPs). Each substructure, or 'Block', is comprised of 3 states with identical dynamics, resulting in 3 distinct aggregated subMDPs, thus, $N = 3$: $\\{s_1\\}, \\{s_{14}\\}$ and Blocks.

2-2. $M^2 \leq S^2/U^3$

This condition is satisfied in most real-world environments with hierarchical structures. By most real-world environments, we refer to scenarios where the size of directly reachable states $U$ is much smaller than $S$ (for continuous state space, consider $U$ as $Vol(\mathcal{U})$ and $S$ as $Vol(\mathcal{S})$). The real-world examples where this condition holds are extensively discussed in Section 4. Examples 1, 2, 3, and 4 all meet the condition that $U$ does not scale with $S$. Since $M$ represents the maximum cardinality of subMDPs, $M \ll S$ is true if a hierarchical structure exists (with small sub-structures repeating). Consequently, the inequality $M^2 \leq S^2/U^3$ is satisfied (as $U$ is negligible), leading to the desired result.

3. Relaxing known mapping assumption

While it is not our focus to deal with learning mapping, we believe that the known dynamics aggregation assumption can be relaxed through the use of model selection techniques, as proposed in [4] and [5]. At each episode, the agent selects one of the base mappings to play and receives the rewards associated with the (low level) policy deployed by that base mapping. Then, it updates the (high level) policy for selecting the base mapping. However, this is currently unclear and beyond the scope of our work. We will leave such research directions for future work.

However, more importantly, we highlight that the assumption of a known hierarchical structure is actually common in hierarchical RL (for example, Wen et al., 2020 [6], also assumed a known equivalence mapping). Furthermore, in real-life scenarios, humans often utilizes the (approximately) known mapping between two similar environments, even if they don't know the transitions. Consider the example of playing various versions of video games like Super Mario. Despite the differences in each game, the underlying gameplay mechanics remain consistent, and this is something we often know.

We sincerely appreciate the time and effort you have invested in reviewing our paper. Thank you for overall positive evaluation of our paper. Below, we address each point raised in your review with the aim of clarifying and further enriching our research.

1. Large-scale experiment

We appreciate your question as it allows us to clarify our main claims and what we aim to emphasize in Theorem 1: designing large-scale environments in Linear MDPs is extremely challenging due to expensive computational costs. As stated in Section 4, in most real-world scale problems, $U$ is minimal compared to $S$, leading to an enormously large $d \approx S$ in Linear MDPs (by Collorary 1). A major challenge with all existing Linear MDP algorithms is the necessity to compute the inverse of the Gram matrix, incurring a computational cost of $O(d^2) \approx O(S^2)$. This becomes intractable when $S$ is very large. Similarly, in response to Q4, this is the reason we could not include experiments for examples $(b)$, $(c)$, and $(d)$ (Riverswim is an example of $(a)$ Gridworld). Please note that, this issue is a common challenge encountered in Linear MDP algorithms. Whereas, in the case of an MDP with a hierarchical structure, where small sub-structures repeat ($MN \ll S$), our algorithm can be effectively implemented since $d_{\psi}\leq M \ll S$. Note that our approach requires only a computational cost of $O(d_{\psi}^2)$.

2. What happens if a state-action pair that can trasit to more than $U$ states exists?

Before addressing your question, we would like to clarify that according to the definition of $U$, a state-action pair $(s,a)$ cannot have non-zero transition probabilities across more than $U$ states. Nonetheless, if your query relates to a situation in which there exists a state-action pair $(s,a)$ has non-zero transition probabilities for almost all states (which means $U = \Theta(S)$), we can provide an explanation. However, please note, as discussed in Section 4, that such a scenario is generally unrealistic.

The existence of a state-action pair $(s,a)$ with non-zero transition probabilities for almost all states has little impact on the result of Theorem 1. Let's reconstruct the transition kernel by excluding the state $s$. And let $U'$ be the maximum number of directly reachable states of this new transition kernel. Now, we can then apply Theorem 1 to the new transition kernel. Consequently, we obtain a similar bound $d \geq \lfloor(S-1)/U' \rfloor$. Hence, our main claim remains valid.

3. Potential future work

We believe there are two possible directions for future work. The first involves utilizing hierarchical structures, as proposed in this paper. A future direction could be to develop more practical methods for leveraging these hierarchical structures.

The second direction is focused on minimizing or completely removing the dependence on $d$ in the regret bound. Although this may entail some concessions in terms of the $H$ or $T$ terms, achieving a reduction in $d$ could prove to be a significant advancement in our research.

4. Hierarchical structures in real-world scenarios

Firstly, we would like to highlight that the assumption of a known hierarchical structure is actually common in hierarchical RL (for example, Wen et al., 2020 [1], also assumed a known equivalence mapping). Furthermore, in real-life scenarios, humans often know the (approximate) mapping between two similar environments, even if they don't know the transitions. Consider the example of playing various versions of video games like Super Mario. Despite the differences in each game, the underlying gameplay mechanics remain consistent, and this is something we often know. Therefore, in common scenarios, particularly in human learning, knowledge of dynamics aggregation is prevalent. We advocate that the RL community should place greater emphasis on these hierarchical RL frameworks to develop algorithms that mimic human-level efficiency.

Our assumption of known dynamics aggregation in the proposed framework is a strategic starting point rather than a limitation. It is logical to first demonstrate efficiency in scenarios with a known dynamics aggregation before feasibly extending our approach to cases involving unknown dynamics aggregation. This step-by-step progression ensures a solid foundation for future explorations as did numerous previous researches. In the field of Linear MDPs, the research initially focused on scenarios with known features. Only recently has there been a shift towards developing methods to learn these features. Similarly, in hierarchical RL, specifically within the option framework [2, 3], the assumption of known options has been a standard for an extended period. It is only relatively recently that the theory RL community has ventured into the problem of option learning. Yet, this area, especially in the context of learning options for regret guarantees, still remains

where $\epsilon$ is the model misspecification error. Therefore, the term $\epsilon_p$ represents the effect of model misspecification on regret, rather than implying that regret is directly proportional to $T$. Now, there are many works that assume there is no misspecification error, namely assuming that their modeling assumption perfectly reflects the environment. We could also do so and not deal with the misspecification error if we desired. Yet, we wanted our framework to be more inclusive when presenting the problem formulation, allowing for possible model misspecification. In essense, this is just a matter of problem setting by our choice. That is, if you wish, we can certainly consider problem setting without model misspecification. We strongly believe that this should not be any disadvantage on this part.

[4] Jin, Chi, et al. "Provably efficient reinforcement learning with linear function approximation." Conference on Learning Theory. PMLR, 2020.

[5] Zanette, Andrea, et al. "Learning near optimal policies with low inherent bellman error." ICML, 2020.

3. Comparison to the tabular case

Dynamics aggregation is a more general framework than the equivalence mapping in the tabular case proposed by Wen et al. (2020). The equivalence mapping does not project states into a latent space. Instead, it partitions the original MDPs into disjoint subMDPs and groups them based on identical or similar structures. Therefore, their mapping is defined as a bijection. However, our dynamics aggregation is a surjection: given the aggregated state, we cannot identify the exact states mapped to it. Since all bijective functions are surjective, our framework is more general.

Furthermore, equivalence mapping necessitates that every aspect of the states be identical, even when certain detailed information of the states 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 equivalence mapping. Thus, it results in a considerably simplified representation compared to the other two frameworks. For more details, we provieded a comprehensive description of dynamics aggregation with an example in Appendix C.

1-2. Intuition behind the dynamics aggregation

In the second part of our paper (Section 5, 6), we aims to offer a possible solution to overcome the limitation of Linear MDPs. While the structural assumption might appear stylistic, it provides meaningful insights. Merely employing function approximation is insufficient; instead, effectively utilizing hierarchical structures can prove beneficial.

Moreover, the dynamics aggregation carries the practical implications for human learning (refer Appendix C.2). For example, a driver who can drive in New York will be able to drive immediately in San Francisco and would highly likely be able to drive in Paris as well. This is possible mainly due to the existence of repeating structures and mappings between different structures. Often such mappings are readily available, and we humans are good at exploiting them. Mappings do not have to be perfect, but they could be approximate, as we consider in our work. The decompositions we consider in our work incorporate such intuition into Linear MDPs.

1-3. Known dynamics aggregation

In response to your question, it's important to emphasize that learning transitions and knowing dynamics aggregation are entirely separate concepts. We can learn transitions regardless of our knowledge of dynamics aggregation. Knowledge of dynamics aggregation enables us to leverage the hierarchical structure, which in turn makes the learning process more efficient. However, it's important to note that this knowledge, while beneficial, is not essential for learning transitions.

Furthermore, in real-life scenarios, humans often utilizes the (approximately) known mapping between two similar environments, even if they don't know the transitions. Take playing different versions of video games such as Super Mario as an example. Although each game has its unique features, the fundamental gameplay mechanics stay largely the same, and this is something players tend to be aware of. Therefore, in common scenarios, particularly in human learning, knowledge of dynamics aggregation is prevalent. Based on this observation, we think that the RL community should give more attention to HRL frameworks. Doing so could lead to the creation of algorithms that emulate the efficiency of human learning.

Our assumption of known dynamics aggregation in the proposed framework is a strategic starting point rather than a limitation. We believe it's sensible to first establish efficiency in situations where dynamics aggregation is known before moving on to scenarios with unknown dynamics aggregation. This gradual progression lays a solid groundwork for future research, as seen in many prior studies. In Linear MDPs, for instance, the initial focus was on scenarios with known features. The shift towards developing methods to learn these features is a more recent development. Similarly, in HRL, particularly within the 'option' framework [2, 3], relying on known options has been a long-standing practice. Only in recent times has the community begun exploring option learning. Yet, this area, especially in the context of learning options for regret guarantees, still remains underexplored and presents a fertile ground particularly for functiona approximation.

The models studied in theoretical RL research are mostly still distant from the real world, to start with. Take the widely used Linear MDPs and linear mixture MDPs, for example. Is it reasonable to assume a transition probability is linear in real life? Probably not. However, the RL research community is making concerted efforts to tackle settings that are more aligned with practical applications. We are confident that our work contributes to this endeavor, even though it may not be entirely perfect yet. We hope that this work serves as an important step toward solving RL with function approximation more efficiently, as evidenced by the numerical experiments as well as the theoretical guarantees.

[1] Wen, Zheng, et al. "On efficiency in hierarchical reinforcement learning." Advances in Neural Information Processing Systems 33 (2020): 6708-6718.

[2] Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A framework for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):181–211, 1999.

[3] Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Emma Brunskill. Regret minimization in mdps with options without prior knowledge. Advances in Neural Information Processing Systems, 30, 2017.

2. Dynamics aggregation misspecification error

The term $\epsilon_p$ represents the model misspecification error allowing that our modeling assumption may be imperfect. Model misspecification is very common in real life and has been often considered in many previous works in Linear MDP. For example, in [4] (Theorem 3.2) and [5] (Theorem 1), the authors proposed regret bounds that also involve the term $T \epsilon$,

We sincerely appreciate the time and effort you have invested in reviewing our paper. Thank you for your feedback, and we are more than happy to address your comments and questions. Below, we address each point raised in your review with the aim of clarifying and further enriching our research.

1. The assumption of known dynamics aggregation stronger?

The reviewer raises a concern about our assumption of known dynamics aggregation being "stronger" than those used in Linear MDPs. We appreciate this perspective, but our analysis suggests a more nuanced understanding is required. In Linear MDPs, for algorithms to achieve an $S$-independent regret bound, a critical yet implicit assumption is that the size of directly reachable states scales with the entire state space. This assumption, as we rigorously show in the paper, is quite stringent and often unrealistic in practical scenarios.

In contrast, our approach, while indeed assuming known dynamics aggregation, does not necessitate such extensive reachability. This difference is pivotal. Our assumption of dynamics aggregation being known, or at least approximable, is not only less restrictive but also more aligned with real-world learning scenarios, as detailed in our paper (refer Appendix C.2). Such dynamics aggregation can often be observed or inferred in various practical contexts, unlike the far-fetched assumption of reachability scaling with the entire state-space, although not explicitly stated (since we are the first to show), required by Linear MDPs.

Therefore, while it might initially appear that our assumptions are stronger, a closer examination reveals that they are, in fact, more grounded in real-world applicability. This distinction is crucial in evaluating the relative "strength" of these assumptions. Hence, it is not straightforward to deem one set of assumptions categorically stronger than the other without considering their practical implications and feasibility.

Moreover, it is important to recognize that the presence of an additional structure, or a seemingly stronger assumption, in a research framework should NOT lead to its immediate dismissal. On the contrary, when such structures are well-justified and relevant, they can be pivotal in advancing efficient learning methodologies. This principle is at the core of our approach. The assumptions we make about dynamics aggregation, far from being mere theoretical constructs, are grounded in observable phenomena in real-world learning environments. We believe that our new findings of the fundamental limits of the Linear MDPs is crucial and our proposed framework sets the stage for future research, opening new avenues that blend theoretical rigor with practical relevance.

Let us emphasize that the primary contribution of our paper lies not just in introducing a new algorithm, but in providing a critical and new insight that all exisitng works in linear function approximation overlooked and offering newer direction for future research. In this regard, we sincerely ask you to reconsider the broader impact that the first part of the paper (on the limitation of Linear MDPs) provides and how it connects to the second part.

1-1. Reemphasize Theorem 1

To begin with, we want to reiterate the importance of Theorem 1. Let us rephrase the key implications of Theorem 1 and Corollary 1.

Unless directly reachable states (by single-step transition) scale with the entire state space by constant factor, (i.e., $U = \Theta(S)$) the feature dimension $d$ should scale with $S$ in Linear MDP.

In the vast majority of practical environments, by a single transition, it is impossible that the entire state space or the constant factor of the entire state space (especially for large state spaces) is reachable, as we discussed in Section 4. Then, our Theorem 1 establishes that the feature dimension $d$ should scale with $S$ to properly express the transition probability in Linear MDP. This result is absolutely crucial, and even serves as a counter-example to the assertion that Linear MDP automatically can induce efficient learning for large state space or even infinite state space (without further assumptions on reachability).

In other words, all existing works in Linear MDPs that claim $S$-independent regret are only efficient under a very strong and impractical assumption that $U = \Theta(S)$ (once again, this was an aspect overlooked in all existing papers.). Compared to this, we believe our assumption of known dynamics aggregation is not as strong. As another reviewer mentioned, the assumption of a known hierarchical structure is actually common in hierarchical RL: [1] Wen et al., 2020, for instance, also assumed a known equivalence mapping.

Dear Reviewer hMDT,

As we approach the conclusion of the discussion period, we want to ensure that all your questions and comments have been comprehensively addressed. Should there be any outstanding concerns or points of clarification, please let us know. Otherwise, we sincerely and respectfully ask you to consider re-evaluating our work.

We would like to highlight the potential far-reaching impact of our findings on the fundamental limitations of linear MDPs. The first part of our paper, in particular, presents critical insights that we believe are imperative to share with the broader RL research community. This contribution alone, we feel, has significant implications for the field.

Moreover, the second part of our work lays a crucial foundation for addressing RL with a hierarchical structure under function approximation. This represents not only the first formal attempt to provide a rigorous theoretical framework for hierarchical structure in conjunction with function approximation but also includes empirical validation of its effectiveness. Such empirical demonstration and theoretical guarantee, especially within RL theory literature, is relatively uncommon.

Importantly, our approach achieves these results without relying on the impractical assumption of direct reachability to a large portion of the MDP, a necessity in conventional linear MDPs for state-space independent performances as shown in Section 4. We earnestly hope that the value and novelty of our work, as reflected in both theoretical, intuitive, and empirical facets, are recognized. Your support in disseminating these findings is crucial for fostering further research and dialogue within the community.