Rethinking Model-based, Policy-based, and Value-based Reinforcement Learning via the Lens of Representation Complexity

Thank you for taking the time to review our paper. We appreciate your feedback and will address each of your concerns individually.

---

Q1: The authors explicitly call the studied phenomenon a hierarchy, but I am uncertain if this is actually true. It seems intuitive that their should be MDPs in which the situation is reversed: representing the value function is easy, while representing the full model is difficult. This seems especially true if we don't talk about strict error free representation, but allow for errors. One intuitive reason for me to conjecture this is the existence of an arbitrarily complex model (i.e. one that transitions from a 3-SAT formula with a high likelihood to one of two states depending on the formula is satisfiable or not) but with 0 reward and therefore a trivial value function as well. I think this is my biggest problem with the paper so far: the construction implies the existence of one direction for the hierarchy, but does not imply that the other direction cannot exist.

A1: Thank you for your question. We have acknowledged in our paper that our complexity hierarchy does not hold for all MDPs, and provide a detailed discussion in Appendix C.2. For the convenience of the reviewer, we paste Appendix C.2 below:

First, we wish to underscore that our identified representation complexity hierarchy holds in a general way. Theoretically, our proposed MDPs can encompass a wide range of problems, as any $\mathsf{NP}$ or $\mathsf{P}$ problems can be encoded within their structure. More crucially, our thorough experiments in diverse simulated settings support the representation complexity hierarchy we have uncovered. In fact, we have a generalized result establishing a hierarchy between policy-based RL and value-based RL, as stated in the following proposition:

Proposition: Given a Markov Decision Process (MDP) $\mathcal{M}=(\mathcal{S}, \mathcal{A}, H, \mathcal{P}, r)$, where $\mathcal{S}\subset\{0,1\}^n$ and $|\mathcal{A}|=O(\mathsf{poly}(n))$, the circuit complexity of the optimal value function will not fall below the optimal policy under the $\mathsf{TC}^0$ reduction.

However, our representation complexity hierarchy is not valid for all MDPs. For instance, in MDPs characterized by complex transition kernels and zero reward functions, the model's complexity surpasses that of the optimal policy and value function (this aligns with the "counterexample" noted by the reviewer). However, these additional MDP classes may not be typical in practice and could be considered pathological examples from a theoretical standpoint. We leave the fully theoretical characterizing of representation hierarchy between model-based RL, policy-based RL, and value-based RL as an open problem. For instance, it could be valuable to develop a methodology for classifying MDPs into groups and assigning a complexity ranking to each group within our representation framework.

Q2: This also makes the empirical section a bit more difficult: Why should we assume that the Mujoco locomotion environments fall into the category of problems described in the paper and not into the alternative? Empirically this seems to be true. Is there some reason to believe that "realistic" MDPs will exhibit this complexity relationship more, or is this an artifact of the choice of environments?

A2: Thank you for your question. It's difficult to argue that Mujoco environments fall into the category of constructed MDPs for theoretical understanding. However, constructed MDPs and Mujoco environments (or more general real-world applications) share similar features: they encode complex decision-making problems into relatively simple models (reward and transition). Our theoretical framework aims to characterize a broad range of real-world problems by incorporating $\mathsf{P}$ or $\mathsf{NP}$ problems into the transition. This way of study aligns with the theoretical understanding of deep learning, where researchers typically demonstrate or explain phenomena (such as benign overfitting) in ideal theoretical models (such as linear regression or two-layer neural networks). Moreover, we want to emphasize that our work uses a completely new perspective --- the expressive power of neural networks --- to study RL problems, which is highly related to our experiments and can be considered an important step in bridging the gap between theory and practice. Finally, for the reasons stated above, we believe the demonstrated representation hierarchy, although not universal, characterizes a wide range of RL problems and is definitely not an artifact of the choice of environments.

---

We sincerely hope the reviewer will reconsider their rating of our work, which is the first comprehensive study of representation complexity. We are also open to further discussion if the reviewer has any concerns about the correctness of our proof or the contribution of our research.

Thank you for taking the time to review our paper. We appreciate your feedback and will address each of your concerns individually.

---

W1: From the perspective of MLP, using simple 2 or 3-layer MLPs to calculate approximation error to validate conclusions provides limited insights for modern deep RL.

Response: We appreciate the reviewer's point regarding the complexity of MLPs in modern deep RL. However, our experiments are conducted in Mujoco environments where the approximation challenges are relatively modest. In these settings, MLPs with 3 layers and 256 hidden units each have been shown to perform near the state-of-the-art (SOTA) when utilizing algorithms such as TD3 (and SAC...). This indicates that the complexity of the function approximators required for these environments is not high. Consequently, using simple 2 or 3-layer MLPs as our testbed is a reasonable choice for the scope of our study. Moreover, as Mujoco environments are classic and extensively utilized benchmarks within the deep RL community, insights gained from these experiments hold significant relevance.

W2: Although it is a theory paper, I would have liked to see more experiments designed to validate the conclusions.

Response: We recognize the value that additional experiments would bring, particularly in complex environments (such as robotics), to reinforce our conclusions. Unfortunately, due to constraints in resources, extensive experimentation in diverse real-world scenarios was not feasible within the scope of this study. However, we selected Mujoco environments for our experiments because they are classic and widely recognized benchmarks in the deep reinforcement learning community. The experiments are conducted in 4 environments and repeated with 5 random seeds, and the results are therefore fairly sufficient to support our theoretical results and contribute to the general understanding of our theoretical claims. If the reviewer has more concrete suggestions to enhance the experiments, we are happy to incorporate them.

Q1 & Q2: (1) Intuitively, could you explain in detail the fundamental reasons for the different representation complexities of the optimal policy and optimal value function under different settings in Sec. 3 and Sec. 4? (2) Maybe you should describe more examples to intuitively understand the representation complexity of the model, optimal policy, and optimal value function.

Response: Thank you for your question. The fundamental difference in representation complexity for optimal policies and value functions in Sec. 3 and Sec. 4 stems from the nature of the decision-making process in various reinforcement learning (RL) scenarios.

In Sec. 3, we consider environments with long-term dependencies where the optimal policy needs to encapsulate complex strategies due to the high branching factor of possible future state trajectories. Here, the representation complexity of both the policy and the value function is high since they must incorporate information about the consequences of actions over many time steps. This is akin to games like chess, where the policy must be sophisticated enough to navigate a vast tree of possible moves.

In contrast, Sec. 4 addresses environments with shorter planning horizons. The optimal policy in such settings can be less complex because it's more focused on immediate states which is sufficient to make a good decision. However, the optimal value function may still require a complex representation to accurately predict long-term returns from any given state due to the potential variability in future rewards. An example provided is a robotic gripping task where the immediate action (gripping with the correct force) is straightforward, but the long-term implications (successfully gripping various objects without dropping) add complexity to the value function.

In the Mujoco environment(e.g. Ant-v4), the transition kernels and reward functions of these environments are some simple functions containing several rules. However, as for the optimal policy and optimal value function, they are so complex that need a complex neural network to approximate and a well-designed RL algorithm to learn.

In summary, the complexity of the optimal policy and value function representations is intrinsically linked to the depth of foresight required for decision-making in a given RL scenario. We will add more analysis in our paper to illustrate this distinction and its implications for the design of RL algorithms.

---

Please let us know if you have any further questions. If your concern is addressed, we would appreciate it if you would reconsider your score in light of our clarification.

Thank you for taking the time to review our paper. We appreciate your feedback and will address each of your concerns individually.

Q1: While the theoretical insights are significant, the paper does not extensively explore their direct implications for real-world RL applications.

A1: Thank you for recognizing the theoretical insights of our work. In fact, our research empirically demonstrates a consistent representation complexity hierarchy, accompanied by a theoretical understanding from the perspective of deep neural networks (a completely new perspective in RL theory!). Our work also has implications for explaining why model-based RL is more sample-efficient. We view our work as the beginning of a comprehensive understanding of representation complexity in RL; therefore, further direct implications for RL algorithms in real-world applications are left for future work.

Q2: Previous experiments show model-based RL is more sample-efficient than model-free RL, aligning with this paper's finding that representing the dynamic model is easier. However, as training progresses, model-free methods often outperform model-based ones. Could the theories in the paper explain this? While the policy is more challenging to represent initially, it allows model-free methods to optimize more efficiently once learned.

A2: Our theoretical analysis focuses on the representation complexity of RL paradigms, explaining the initial sample efficiency of model-based methods. We recognize that as training advances, the direct policy representation in model-free methods may lead to more efficient optimization, potentially outperforming model-based approaches. This difference primarily stems from the distinct optimization properties of various reinforcement learning algorithms.

We emphasize that representation complexity and optimization properties are two parallel and equally important aspects. Our work fills a gap in understanding representation complexity in RL theory. We fully agree with the reviewer that integrating optimization efficiency with representation complexity to comprehensively understand the performance differences between various RL algorithms is a promising (and challenging) direction for future research. We appreciate the reviewer highlighting this important area of investigation.

Q3: Could the proposed hierarchy of representation complexity be applied to other types of neural network architectures beyond MLPs, such as transformers?

A3: Our hierarchy of representation complexity can be applied to the transformer architecture. Please see the general response for the details.

---

Please let us know if you have any further questions. If your concern is addressed, we would appreciate it if you would reconsider your score in light of our clarification.

We sincerely thank the Reviewer for the positive feedback and appreciation for our work.

Q1: Do the findings regarding the representation complexity hierarchy hold consistently across different task settings, or do they vary significantly with various types of tasks?

Response: Yes, our findings on the representation complexity hierarchy demonstrate consistent behavior across a diverse array of task settings. (i) Theoretically, we can encode any $\mathsf{NP}$ or $\mathsf{P}$ problem into the construction of MDPs and establish the desired representation complexity hierarchy, characterizing a wide range of problems. (ii) Empirically, we have conducted experiments across various simulated environments, each designed to test different aspects of task complexity. These environments range from simple binary classification tasks to more complex structured prediction problems. In all these settings, the hierarchy we have identified remained robust and consistent. Thank you for raising this important question and we will further emphasize this in our revision.

Q2: Can you provide case studies or real-world examples for understanding the representation complexity hierarchy that has led to improved sample efficiency in practical applications?

Response: Thank you for your question. Our research findings indicate that the model typically benefits from the lowest representation complexity, which may explain why model-based reinforcement learning generally achieves better sample efficiency in real-world applications (see Appendix C.1 for more details). Moreover, we'd like to emphasize that our work primarily focuses on providing the first comprehensive theoretical understanding of representation complexity across various reinforcement learning paradigms. We hope this understanding will inspire the following empirical works and lead to practical advancements in sample efficiency.