Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: Summary: This paper studies a theoretical aspect of the expressivity of policy, Q functions and dynamics. Based on theoretical and empirical analysis, the authors propose a new model-based RL algorithm that said to improve task performance. Final evaluations are demonstrated on MuJoCo benchmark tasks. 

Overall, the paper pursues an interesting and ambitious problem on the interplay between model-based and model-free approaches, and the expressivity of the representation of dynamics, policy and value functions. However, the results in the theory part is drawn based on analysis on a very simple and special task. Therefore the theoretical results can not be considered general for all MDP cases. In addition, these results are not surprising.

- Theorem 4.3 states a general theoretical result that holds for neural networks, the proof does not look like it can hold with a universal representation power of a neural network. 

- The idea of using Q-functions estimate as Boostrapping is just an idea of using on-planning to improve action selection at every decision step. This is just a recurring idea of many model-based RL approaches. BOOTS consumes more computations as planning, hence would perform better than the baselines. BOOTS should be compared to other model-based approaches that also use planning at Testing, assume all are given the same budget of testing time.
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: The paper highlights an interesting issue regarding approximability of function approximators (neural networks). The paper provides cases where the action value function is difficult to approximate and is much more difficult than the dynamics of a model. The author conducts some experiments to claim that even with a large NN, DQN still finds a suboptimal policy. Theorems regarding the appoximability of the action value function are presented. Then the paper proposes that rollout-based search should be preferred for planning and conducts some experiments to verify this. Although the paper points out interesting issues of approximating action-value function, both the motivation and the suggestion regarding MBRL are not convincing.

1. In term of the motivation, those cases listed in the paper are interesting, but they are not representative. In fact, the Dynamics can be far more complicated and it is still an open problem regarding how to learn the Dynamics. Furthermore, the proposed method is to simply combine MCTS and bootstrap value estimates. The method itself is not novel and it basically down weights the bootstrap estimate. It is very intuitive that some appropriate combination between the two can yield better performance. However, in model-based setting, the reward sequence can be highly variant and non-stationary, there is no solid reason to believe this can be always better. The motivating experiments in figure 3 are not persuasive. There can be many reasons for a deep RL algorithm to find a suboptimal policy: boostrap target interference, overestimation, difficulty of optimization, etc. It is quite confusing which factor leads to suboptimal performance of DQN.
 
2. Theorem 4.3 does not make sense to me. What does it mean by “no constant depth NN can approximate the optimal policy with near optimal rewards?” Notice that, in machine learning community, people rarely pursue perfect approximation (equality). As long as the approximation error can be reasonably small, the approximator should be still useful. Does “no constant depth NN can approximate the optimal policy” mean the approximation error is unbounded? I believe we can still expect a large NN to approximate the action-value function very well. 

A minor issue. In page 2, the paper writes “model-free RL or MB policy optimization suffer from …, whereas MB planning … ”. MB planning is not a separate category of MB policy optimization. Such statement is not accurate. 

review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: This paper presents a mainly theoretical argument comparing the expressivity of model-free and model-based RL methods contrary to analysis in the past which usually relies on sample complexity. They construct a family of MDPs, where the true dynamics belong to a simple function class (in terms of the number of linear pieces needed to define the function), but the corresponding optimal Q-function belongs to a function class not necessarily expressible by a simple function. The paper then builds a similar case for randomly/semi-randomly generated MDPs. Finally, they propose to bootstrap the Q-function with n-step returns to boost the expressivity exponentially. 

I would lean towards accepting this paper, as this paper looks at an interesting problem and their analysis seems to be rigorous and valuable for the community to build upon. My questions/comments are as follows:

1. Previous work, for example [1], also talks about bootstrapping a neural net Q-function using an n-step approximation so as to improve the efficiency of a pure model-free algorithm. I think this paper should be cited.

2. In terms of the experiments, it is hard to understand the significance and connection to the theory. The theory talks about the expressive power of Q-functions, which suggests that we should look at only the asymptotic performance on these tasks, but most of the results are similar to MBPO or SAC in terms of asymptotic performance, although with a different learning speed, which could have to do with different factors.

3. This paper shows the existence and provides a constructive proof for a family of MDPs where expressing optimal Q-functions is exponentially harder than expressing dynamics. But how likely is such a setting to arise in MDPs in practice? For example, on the gym benchmarks, we would expect fairly not so complicated Q-functions -- although they might take longer to learn. 

4. There is also a divide between learning Q*, and learning a policy that optimizes Q* reasonably well. Further, the requirement for the Q-function is only to get relative ordering between Q-values for different actions at states visited by the optimal policy right, which might not be the same as the Q-function landscape across state-action pairs. So, I am not sure if the expressivity of the optimal Q-function, in general, is the right metric to answer this question, but I also completely agree that this is a good starting point. 

5. I think when applying RL to the current benchmarks or problems we have, the main problem could be linked to optimization of a neural-net Q-function via bootstrapping (in the sense of approximate dynamic programming) as compared to the expressive power of optimal Q-functions. But I agree that the problem being looked at in the paper would also exist.

References:
[1] Plan Online, Learn Offline: Efficient Learning and Exploration via Model-Based Control, Lowrey et.al.


review_title: Official Blind Review #3

Meta-review: The paper provides some insight why model-based RL might be more efficient than model-free methods. It provides an example that even though the dynamics is simple, the value function is quite complicated (it is in a fractal). Even though the particular example might be novel and the construction interesting, this relation between dynamics and value function is not surprising, and perhaps part of the folklore. The paper also suggests a model-based RL methods and provides some empirical results.

The reviewers find the paper interesting, but they expressed several concerns about the relevance of the particular example, the relation of the theory to empirical results, etc. The authors provided a rebuttal, but the reviewers were not convinced. Given that we have two Weak Rejects and the reviewer who is Weak Accept is not completely convinced, unfortunately I can only recommend rejection of this paper at this stage.
Decision: Reject