On Representation Complexity of Model-based and Model-free Reinforcement Learning

Thanks for reviewing our work and providing helpful and insightful comments. Below are our responses.

The theoretical nature of the Majority MDP might limit its direct applicability to practical problems.

We discussed in the global response that many MDPs in real-world applications are actually equivalent (or close) to the majority MDP class. Also, our experimental results further validate that our results can be applied to general RL problems.

A minor point is that the experiment section only includes a limited set of small scale gym environments.

We emphasize that our use of the Mujoco environments aligns with the standard benchmarks prevalent in the reinforcement learning community, as corroborated by multiple studies ([1][2][3]). This alignment not only substantiates our theoretical findings but also ensures their relevance in practical settings. To further fortify the credibility of our experimental results, we provided additional results depicted in Figures 4-7 on pages 20-21 of the revised supplementary material. These enhancements serve to provide a more comprehensive and robust demonstration of our research's applicability.

How might these insights inspire the design and development of improvements to RL algorithms?

The main message conveyed by our paper that “MDPs with simple model structure and complex Q-function are common’ could inspire researchers to use the knowledge of the model (either using a model-based learning algorithm or boosting existing model-free algorithms using the knowledge of the model or by planning) to achieve better performance than a purely model-free algorithm (as also empirically validated by [4]).

Also, when choosing an appropriate function to learn and deploying function approximation, it is worth thinking about whether the chosen function is simple or complex since to learn a complex function, one either needs a complicated function class or suffers a large approximation error. This is not only important for RL algorithm design but also important for a broader scope of general machine learning settings.

References

[1] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference on machine learning, pp. 1861–1870. PMLR, 2018

[2] Ching-An Cheng, Tengyang Xie, Nan Jiang, and Alekh Agarwal. Adversarially trained actor critic for offline reinforcement learning. In Proceedings of the 39th International Conference on Machine Learning, volume 162, 2022

[3] Hanlin Zhu, Paria Rashidinejad, and Jiantao Jiao. Importance weighted actor-critic for optimal conservative offline reinforcement learning. arXiv preprint arXiv:2301.12714, 2023

[4] Kefan Dong, Yuping Luo, and Tengyu Ma. On the expressivity of neural networks for deep reinforcement learning. In International Conference on Machine Learning (ICML), 2020.

Thanks for your effort in reviewing our work and providing helpful and insightful comments. Below are our responses to your questions.

1. What are the approximation errors of the optimal Q-function calculated exactly in the experiments? Fitting the Q-values given by the learned SAC critics or fitting the monte carlo returns of the learned policy (i.e., the actor)?

In the experiments displayed in Section 4, the approximation errors are calculated by fitting the Q-values given by the learned SAC critics. The Q-values learned by SAC are good approximations to the optimal Q-values. In SAC training, the critic loss (average l2 Bellman error) is consistently bounded by 0.005 in InvertedPendulum-v4, by 0.01 in Ant-v4, HalfCheetah-v4, Hopper-v4, and by 0.1 in Walker-v4 respectively. These small Bellman errors suggest that the Q-functions calculated by the SAC experiments are able to fit the optimal Q-functions quite well. Moreover, we note that the critic losses are all smaller than the (un-normalized) approximation errors in the Q-function, which are about 10X the relative approximation errors in the Q-function plotted in Figure 3.

2. How will the experimental results change when varying the size of neural network used? I think only one configuration (i.e., d=2,w=32) is insufficient.

Thank you for the valuable suggestion to make the experimental result more solid. As stated in the global response, we conducted further experiments on different configurations of neural networks, and the same result that the approximation errors of the Q-functions are greater than those of the model and reward functions consistently holds under different configurations:

1. d=1 w=16
2. d=2 w=64
3. d=2 w=128
4. d=3 w=64

The plots for the experimental results are shown in Figure 4-7, pages 20-21 in the updated supplementary material pdf.

3. How can the circuit representation complexity be in visual-input MDPs (or POMDP) and stochastic-transition MDPs?

It would definitely be an interesting and important future direction to extend our theories to stochastic MDP and POMDP. Below we briefly discuss possible approaches of generalizing to POMDP and stochastic MDP:

POMDP: For POMDP, we can additionally assume a function $O(s) = o$ (or $O(s,a) =o$), which maps a state s (or a state-action pair (s,a)) to a corresponding observation o. One possible choice of $O$ could be a substring of the state s, which still has low representation complexity. In POMDPs, the Q-function is often defined on a sequence of past observations or certain belief states that reflect the posterior distribution of the hidden state. As a result, the Q-functions in POMDPs often have higher complexity. Since the Q-function is proven to possess high circuit complexity for the majority MDP, the representation complexity for value-based quantities of a partially observable version could be even higher. We thank the reviewer for raising this very interesting question, and a more formal and rigorous analysis would be a fascinating direction for future research.

Stochastic-transition MDP: As discussed in the global response, our framework can be extended to stochastic MDP. Here we discuss a natural extension of our majority MDP: After applying a = 1, if C(s[r]) = 1 (i.e., the condition is satisfied), instead of deterministically flipping the s[c]-th bit of representation bits, in the stochastic version, the s[c]-th bit will be flipped with probability 1/2, and nothing happens otherwise. This resembles the real-world scenario where an action might fail with some failure probability. The representation complexity of the transition kernel $P$ still remains polynomial. For the optimal $Q$ function, if we change $H=2^b + 2n$, since in expectation each flipping will cost two steps, the representation complexity of the $Q$ function is still lower bounded by the majority function, which is exponentially large. Note that our deterministic majority MDP can be viewed as an embedded chain of a more ‘lazy’ MDP, and the failure probability can also be arbitrary. Hence, our conclusion can be generalized to this natural class of stochastic-transition MDPs.

In conclusion, our framework can be extended to more complex settings such as stochastic MDP and POMDP, but the main message of this paper can be effectively and more intuitively conveyed through our majority MDP class. We will add these discussions in the revision. Thank you again for the valuable suggestion.

Thanks for your support of our work and your time reviewing our paper and providing helpful and insightful comments. Below are our responses.

While the majority MDPs is broad, it fails to see if common MDPs are in this class or close to this class such that in many real life applications the circuit complexity of the Q-value function class is higher than that of the model class.

We discussed in the global response that many MDPs in real-world applications are actually equivalent (or close) to the majority MDP class. Of course, it is true that we can also construct MDPs of which the model complexity is high while the Q-function is simple, but the main message we aim to convey is that MDPs with simple model structure but complex Q-function are common, and thus using the knowledge of the model (either using a model-based learning algorithm or boosting existing model-free algorithms using the knowledge of the model or by planning) could achieve better performance than a purely model-free algorithm (as also empirically validated by [1]).

While the circuit complexity is a good starting point to study the representation complexity, is it possible that there are other quantities or metrics such that the representation complexity might behave differently?

We believe that there exist other quantities that can be used to measure the representation complexity, but circuit complexity is one of the most fundamental metrics as the operations in computers are represented by circuits, and this notion is also widely used in TCS.

Note that many complexity measures, such as VC dimension, can be only applied to a function class instead of a single function, and previous attempts, such as using the number of segments of a piecewise linear function [1], are not applicable to more general functions. Instead, the circuit complexity is applicable to a general function (with bounded precision, which is reasonable and actually necessary in practice).

Proposing other reasonable representation complexity measures and studying whether this phenomenon might be different under that measure are definitely interesting future questions for study (We conjecture that the same behavior still happens even under different measures since our experimental results validate this phenomenon using neural networks instead of circuits). We thank the reviewer for raising this point.

References

[1] Kefan Dong, Yuping Luo, and Tengyu Ma. On the expressivity of neural networks for deep reinforcement learning. In International Conference on Machine Learning (ICML), 2020.