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

Summary

The paper presents an analysis of the representation complexity, the necessary complexity of a circuit, between different paradigms in reinforcement learning. The authors show, with several reductions to well-known theoretical complexity classes, that MDPs exist in which representing a model is "easy" while representing a value function or policy is "hard".

Strengths

The paper dives deep into an established conjecture in reinforcement learning, that learning a model of an environment can be easier than learning a value function. With a clever reduction to a simple exemplary class of MDPs, the authors show that is "difficulty" is measured by the complexity of a circuit necessary to represent the respective function, then classes of problems exist in which this is indeed true. The mathematical derivations and proofs are straightforward and seem correct to the extent that I am able to verify them, although my expertise lies in RL and not complexity theory. They provide stronger results than previous work in the same direction [1] and seems like a good follow up work. [1] ON REPRESENTATION COMPLEXITY OF MODEL-BASED AND MODEL-FREE REINFORCEMENT LEARNING, Hanlin Zhu, Baihe Huan, Stuart Russell, ICLR 2024

Weaknesses

I have one major confusions which I list under questions since these are hopefully easily addressable in the rebuttal. I think the problem of the "strictness" of the hierarchy should be very carefully addressed. It only weakens the conclusion, all the proofs are correct as far as I was able to verify, but I would encourage the authors to engage carefully. This is my main reason for recommending rejection: I think the works is interesting and meaningful, but the conclusion seems wrong due to the problem outlined below. I am very happy to discuss this point in the rebuttal and raise my scores accordingly if appropriate.

Questions

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. 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? Other, minor issues: - All figures are barely legible at a "reasonable" zoom level, I would encourage the authors to quickly redesign these.

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

See above

Summary

This paper studies three RL paradigms: model-based RL, policy-based RL, and value-based RL from the perspective of representation complexity. The authors demonstrate that representing the model emerges as the easiest task, followed by the optimal policy, with the optimal value exhibiting the highest representation complexity.

Strengths

- The paper is well written. The problem studied in this paper is well-motivated and very interesting. - Analyzing model-based RL, policy-based RL, and value-based RL from the perspective of representation complexity, transitioning from simple scenarios to broader ones, is impressive.

Weaknesses

- 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. - Although it is a theory paper, I would have liked to see more experiments designed to validate the conclusions.

Questions

- 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? - Maybe you should describe more examples to intuitively understand the representation complexity of the model, optimal policy, and optimal value function.

Rating

5

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

The paper is mainly theoretical, and no algorithm is implemented. There is no specific potential negative societal impact of this work.

Summary

This paper delves into understanding the inherent representation complexities associated with three different RL categories: model-based RL, policy-based RL, and value-based RL. By studying computational complexity theory and neural networks, MLP, the paper posits a hierarchy in which representing the underlying model is the simplest, followed by the optimal policy, and finally, the optimal value function, which is the most complex to represent. Theoretical analyses and empirical results support these claims.

Strengths

- The paper gives a new understanding and improves RL algorithms by examining RL paradigms through the lens of representation complexity. - The paper includes deep RL experiments that align with the theoretical findings, offering practical evidence of the proposed hierarchy. -The paper bridges theoretical insights with deep RL by discussing the expressiveness of MLPs.

Weaknesses

- While the theoretical insights are significant, the paper does not extensively explore their direct implications for real-world RL applications. - 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. - Could the proposed hierarchy of representation complexity be applied to other types of neural network architectures beyond MLPs, such as transformers?

Questions

Please answer the points mentioned in the weaknesses.

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

The paper does not discuss their limitations.

Summary

This paper delves into the representation complexity in different RL paradigms. It focuses on the function class needed to represent the underlying model, optimal policy, or optimal value function.

Strengths

1. The study uses time complexity and circuit complexity to theoretically analyze the representation complexity among RL paradigms. It introduces new classes of MDPs (3-SAT MDPs, NP MDPs, CVP MDPs, and P-MDPs) to showcase the differences in complexity. 2. The paper finds that models and policies can often be effectively represented by MLPs, while optimal value functions face limitations, providing insights that may inform future research.

Weaknesses

See questions.

Questions

I apologize for my limited familiarity with the representation complexity area. I have read the paper thoroughly and examined the theorems. I appreciate your work, but I feel I cannot make a solid judgment. So if my questions are off the mark, please correct me. 1. Are the findings regarding the representation complexity hierarchy consistent across a wide range of task settings, or do they vary significantly with different types of tasks? 2. 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? I understand you have provided some explanations in the paper. If this question adds extra burden, feel free to disregard it.

Rating

7

Confidence

2

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors do not have an explicit limitations section or paragraph.

Thank the authors for the rebuttal!

Thank you for the detailed rebuttal! My concerns have been resolved. Apologize again for my limited knowledge in your area. Wish you good luck with this paper!

Answer

Dear authors, thanks for the clarifications. I acknowledge that I missed the discussion in appendix C, I feel like this is a very important point that might deserve some more prominent space in the main paper. I still don't fully agree with the argument: the benchmarks are investigated here are all designed to have little to no task irrelevant features such as distractions. Generalizing from these to RL problems in general seems like it can mislead the community. The results also violate a lot of commonly held intuition: in many cases predicting the exact consequences of your actions is very hard, i.e. how many blades of grass are crushed by a step on the lawn, but from the perspective of any task, this is irrelevant. I wish I could provide a nice reference here, but I can't find one at the moment. I don't have a problem at all with your formal statements and I do applaud the novel and insightful technique. My whole problem is with the nuance of the framing, which I do think is very important to get right to frame your (very interesting results) in the right way. I am willing to increase my score provided you can give the nuance of this discussion some space in the main paper. Since I want to be an optimistic and constructive reviewer, I have updated my score to recommend acceptance, I hope you follow my concerns.