Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: summary: This paper proposes a theoretical framework to analyze model-based end-to-end reinforcement learning. In particular, the authors focus on the MBRL with a linear approximation of the value function, and within the Markov reward chain setting (with singleton action). Theoretical results show that MBRL in an end-to-end way is actually doing implicit parameterization and convergence analysis.

main_review: ### Originality

The main contribution of this paper is to provide a theoretical analysis of MBRL. With the implicit differentiation theorem, the authors link the implicit parameterization of the learned model and the linear feature weights, which looks interesting to me. The most interesting result of this paper, in my opinion, is that introducing reward and transition models is an implicit way of preconditioning in the gradient flow.

### Quality

As claimed by the authors, all main results in this paper are derived under the Markov reward chain framework. However, what I can see in the main part, e.g., Theorem 1 and Corollary 1/2, they're all analyzed under finite-sum square-error and no direct link to the common reinforcement learning scenario. For example, how the value function is estimated and updated? How does the agent update/improve the policy? What's the end-to-end MBRL algorithm the agent is performing? Based on this, I cannot agree with the authors' conclusion that

> ..., we believe our results are likely to generalize to the full MDP setting since ...

I would like to explain this point with a few more details, which lead to my concerns regarding the quality of this paper. 

1. The constraint Eq. 2 appears quite confusing to me. I'd like to see more justification on why this constraint can hold. It seems to me that it can be derived from the Bellman equation, but it leads to another problem: the optimality of $\hat{\theta}$ is not identical to that of $\psi$ when $g()$ is non-linear. For example, when the image of $g()$ is a subset of $\hat{\theta}$, the optimal $\psi$ may not be obtained. For this reason, I'm not convinced by the proof of Corollary 1 (and 2). 

2. Another issue on implicit differentiation is about the assumption on $\frac{\partial g}{\partial \psi}$: it should exist, but may not hold in many cases, e.g., when linear piece-wise activations like ReLU are involved in a neural network.

3. The analysis of finite-sum square error (Eq. 3) is not clear in MBRL. Does this equation apply at each timestep $t$, or at the end of each episode? For either case, how does the agent collect the datapoints (from the real environment or the model)? ... I think such ambiguity comes from the clarity issue of presentation. See the *Clarity* section for more details.
    * I'm trying to understand this in two cases: a) when the gradient updates in Eq. (4) are performed once per timestep; b) when the steps in Eq. (4) are performed until converging in each step. 
    * In case a), the loss function $L$ and the datapoints should change along the time, which vanishes the assumption of the proof (a finite-sum result). 
    * In case b), we can still conclude that the value prediction converges to a global minimum at the step, but it relies on the fact that such value prediction can apply on all timesteps, which is not discussed in the paper. 
    * Note that this also holds for the Markov reward chain discussed in the paper: the datapoints collected at step $t$ could be different from that in other steps. 

4. I'm also confused about the explicit parameterization scheme in the paper. One reason might be from the above point of clarity issue, and the other one is: it seems to me that explicit parameterization is not using any models, so it's actually a model-free RL (MFRL)? Considering the fact that MBRL takes more calculations (planning steps) during training, it's not surprising to me that the implicit parameterization converges faster than explicit parameterization.

### Clarity

This paper has some issues with writing and organization. For example:

1. This paper doesn't have a clear formal definition of the Markov reward chain that can be usually found in the RL literature. As a result, readers would find it hard to understand why such a model can help for MBRL analysis.
2. The authors don't provide a clear context on the gradient steps, especially when the steps are performed. As discussed in the *Quality* section, this would result in many confusions and weakens the conclusions of this paper.
3. Given the results from the finite-sum minimization, the authors should provide clarifications on how this relates to MBRL.

### Significance
 
The authors provide a convergence analysis to understand the learning of MBRL. However, as discussed above, the results are mostly derived from finite-sum with unknown sampling methods, it's hard for readers and other researchers to use the results for the MBRL study, either in theory or in practice.
limitations_and_societal_impact: This paper only has results based on a simplified model, Markov reward chains (MRC), which is different from the MDP in the RL literature in the sense that, MRC doesn't involve the action selection. In the meanwhile, the obscureness of gradient updates in this paper makes the readers hard to understand the significance of the work, neither using nor applying the results in other researches. In particular, how to sample the datapoints is not discussed in the paper, therefore I'm convinced by the results can explain the dynamic nature of RL.
review_title: null

final_score: rating: 3: Clear rejection
review_content: summary: This paper presents a theoretical analysis of two different ways of parameterising a linear value function approximator. They consider an 'explicit' parameterisation, in which the weights connecting the state features to value estimate are parameterised directly, and an implicit parameterisation, which attempts to use knowledge of the properties of a Markov process to inform a more structured parameterisation. 

The authors analyse the learning dynamics of these two parameterisations under stochastic gradient descent, and draw some conclusions about the properties of RL environments that might favour the implicit parameterisation. Finally, they carry out some empirical investigations on offline datasets of trajectories from several different environments.

main_review: The authors attempt to motivate their work as a theoretical investigation into model-based methods that model transition probabilities and rewards. In particular, they attempt to draw a close parallel to "value iteration networks", which is a particular form of model-based method. 

Despite the undoubted importance of investigations into model-based planning, I am not convinced that this is really what this work achieves. In particular, their method is really a different parameterisation of a purely model-free method - as far as I can see there is no internal policy improvement or value iteration step based on a model, which is what a model-based method would be aiming to achieve. For example, value iteration networks use repeated applications of a convolutional network with max pooling as a form of differentiable "end-to-end" value iteration in order to inform an improved policy.

Additionally, their implicit parameterisation seems really most applicable to a discrete-state Markov process (relying on a vector of rewards and an explicit transition matrix as components of its parameterisation), which is not typically the case in more complex environments.  

Their theoretical analysis provides some interesting insights into how environments with reward offsets can impact learning in this setting. However, I am unconvinced that this would be an issue for modern algorithms that use temporal differences and baselines, in part precisely to help improve learning in such contexts. In the setting with no reward offset, it seems that both parameterisations perform similarly well in their empirical results.

In summary, despite an admirable intention to investigate an important area, I am not convinced this paper makes sufficient contributions to the community in its current form. 

limitations_and_societal_impact: There are no anticipated negative societal impacts from this work.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: This paper focuses on the area of theoretical reinforcement learning, where the authors consider the form of parameterization for the value function.  Specifically, the authors consider the case of a Markov decision process with a linear value function, and compare the explicit and implicit way of parameterizing the weights of the value function. The authors prove that using gradient descent, the implicit parameterization is equivalent to the explicit parameterization with a gradient preconditioner, which converges to the global minima. The authors then extend this result to stochastic gradient descent, and then compare the condition in which implicit parameterization gives better convergence speed. The authors provide empirical evidence in several discrete MDP environments.
main_review: Overall I think this paper presents an interesting study of the implicit parameterization of value functions for a Markov decision process. However, I believe that there are also some limitations that need to be addressed.


Pros:

The paper is well written. The structure of the paper is well organized and the authors present the theoretical results in a step-by-step way, which makes it easy for the reader to grasp the motivation behind the theoretical results.

Being a theoretical paper, the paper also includes empirical studies in several MDP environments, making the results more intuitive.


Cons:

The choice of the specific implicit parameterization (equation 2) requires more justification. We know that setting equation 2 to zero gives us the Bellman equation for the tabular Markov reward process with rewards $w$, discount factor $\eta$ and transition probability $\sigma(F)$. The authors suggest that the internal discount factor $\eta$ is different from the true discount factor $\gamma$. Under this assumption it is clear that the ground truth transition matrix and reward vector cannot be a good fit for parameters $\sigma(F)$ and $w$. It is then unclear what the learned $\sigma(F)$ and $w$ represent. Are we looking for a different MDP dynamics and rewards with discount $\eta$ such that the value function happens to be the same as our ground truth MDP?

Moreover, the authors claim that “this implicit formulation allows us to analyze how $\psi$ and $\hat{\theta}$ relate without needing to consider the algorithm used to compute $\hat{\theta}$”. I believe this is not valid for this particular implicit parameterization, since it is well known that $\hat{\theta} = (I - \eta \sigma(F))^{-1} w$, which suggests that this implicit parameterization can be considered as just another form of explicit parameterization.



One important aspect that prevents implicit parameterization to be used in practice is the computation complexity of the implicit gradient, which the authors fail to consider in this paper. Computing the inverse Jacobian product in the implicit gradient has complexity $kd + d^2$, for each step where $d$ is the dimension of $\hat{\theta}$ and $k$ is the batch size. On the other hand normal stochastic gradient descent only has complexity $kd$. Since $d$ is usually larger than $k$, it is unclear that implicit SGD would have much advantage compared to explicit SGD given the same computation budget. Furthermore, under the one hot encoding assumption in the paper, it is not clear why SGD is even necessary if the data takes the form of empirical discounted sum of rewards, as one can obtain the exact minima of equation 3 by simply averaging all the data points of each state.


Given these concerns, it is hard to recommend the acceptance of this paper before they are addressed.


limitations_and_societal_impact: See main review for limitations, and N/A for social impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper does some theoretical study to explain the fast convergence of end-to-end model-based RL in some domains. Specifically, the authors prove global optimal convergence for the linear approximation case and study the convergence rate under certain conditions that stochastic gradient descent (SGD) with implicit representation converges substantially faster than its explicit counterpart. The authors also provide empirical results in some simple environments to back up their theory.

main_review: Originality, quality, clarity of the paper:
The paper studies an observation with little formal justification in RL literature: End-to-end model-based methods are heuristically shown to be capable of better generalization in some RL domains.
There are substantial theoretical results (but I have not checked the proof carefully, since I have no prior experience in working with gradient descent dynamics). Overall, the derivation is smooth and has good logic flow, with relatively enough explanation. The definitions and quantities introduced show the thoughtfulness of the authors. Thus I think this paper is of relatively good quality.

Significance of the paper:
There are 2 main theoretical contributions. The first is showing the implicitly parameterized linear weights in the model still converges to a unique global optimal. The second is finding conditions under which the implicit parameterization exhibits significantly better properties than explicit parameterization. Besides, the empirical results seem to support the second theoretical claim. Therefore I think this paper does provide some novel insight on the principle of end-to-end model-based RL methods. 

*post-rebuttal*:
 Thanks for your reply. I have read your response and my review keeps the same.
limitations_and_societal_impact: The empirical results are conducted on toy environments and have some disparity to the actual implementation of recent model-based RL algorithms. Meanwhile, if to supplement the empirical results, the authors could do similar experiments on more complex domains, such as the Atari or Mujoco environments, and with deep RL algorithms. Though this might introduce unknown factors that affect the final convergence, any implication in such a setting might be more helpful to algorithmic works in the community.
One last concern is that the authors could have spent more paragraphs discussing related literature (both empirical and theoretical) and summarize their implications. 

I don’t see any potential negative societal impact of this work.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper provides a theoretical analysis of learning value functions in a Markov reward chain by SGD. They propose to analyze these methods as indirectly parameterizing weights of a linear function (with fixed features) and compare to explicitly learning the linear weights. The authors prove that, under certain assumptions, the implicit parameterization converges to the global minimum. The authors note that the gradient updates differ because the implicit parameterization preconditions the gradient. The authors then characterize the conditions under which this implicit parameterization performs better (as measured  by the variance-to-mean-square ratio) by analyzing the dynamics of the primary component of this preconditioning matrix and find that this occurs when the sign of the components all point in the same direction. The authors corroborate this theory with a series of experiments on toy environments.
main_review: This paper studies an interesting question regarding the dynamics of V-learning in RL.

My main concern of this paper is that it is unclear how relevant this analysis is to end-to-end RL algorithms. In particular, the premise that value-based learning methods learn linear weights of fixed features requires more justification. The restriction to Markov reward chain, rather than an MDP also greatly limits the scope of the analysis.

For example, the statement, “Note that any insight in this simpler framework is likely relevant to the state-dependent model setting since the gradients differ only by the Jacobian relating model parameters’ differentials to learned parameters’ differentials, i.e., the chain rule.” seems to sweep aside the fact that this Jacobian can be arbitrarily complex for deep neural networks. Similarly, it would be useful to explain why analysis on a Markov reward chain would translate to VIN, which internally takes a max over actions.
As another example, what are the restrictions or assumptions on the constraint h and why are those assumptions realistic?

Moreover, does O(alpha^2) include terms that depend on F? If so, the abstract statement “We prove that, for a linear parametrization, gradient descent converges to global optima despite non-linearity and non-convexity introduced by the implicit representation” seems misleading as it misses an important condition. In particular, the paper proves that there is a global minimum, but I believe it requires the strong assumption that all second order terms are dominated by a quadratic. Given this strong assumption, the global convergence results are not as universal as the statement implies and are more limited in significance.

Overall, although the paper performs interesting analysis, tying this analysis back to RL algorithms and justifying the simplifying assumptions made would greatly improve the impact of this paper.

typos:
abstract: “Estimating the per-state expected cumulative rewards is a critical aspect of reinforcement learning approaches, however the experience is obtained, but standard deep neural-network function-approximation methods are often inefficient in this setting.”
limitations_and_societal_impact: N/A as this paper provides mainly theoretical analysis of V-learning in Markov reward chains, which is too generic to warrant discussing societal impact
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper studies value estimation in end-to-end model-based RL methods.
The setting is simplified for analysis. They consider action-less MDP. The form of the value is assumed to be a linear combination of fixed state features \phi(s) with constant coefficients \theta. If \phi is one-hot, \theta would correspond to a vector of state values.
The implicit rep. for \theta is a log Transition matrix + reward vector and \theta is defined to satisfy the bellman condition.
The paper then studies gradient and gradient descent of regression for implicit and explicit representation.
The first main result is to show the similarity between explicit update and implicit update save for a ‘preconditioning’ matrix P (and higher order terms). They prove P positive definite and obtain global convergence from that.
In the next part they decompose the transition matrix and show how the preconditioner P behaves in the limit \eta -> 1 and its consequences (preconditioner favors 1 component).
Finally they present some experiments on toy tasks where they are showing that the 1 component of the residual is increased by a reward offset and that the final performance is less sensitive to this in the case of implicit compared to explicit.

main_review: Strengths:
1. Using this analytic implicit representation for analysis is a neat idea.
2. Decomposing the transition matrix in terms of the stationary distribution is also very neat and I didn’t expect the arising form of the preconditioner.
3. The writing presents the ideas quite clearly.

Issues:
1. I believe there might be an error in corollary 3. The sum of $r_i^2$ shouldn’t cancel with the denominator which is sum of squares: $||\sum_i r_i \phi(x_i)||_2^2$ (same as in implicit case). Actually I think in this case, implicit and explicit should have the same variance/mean ratio (except for $O(1-\eta)$ term).
2. Parallel residual convergence is a main result and is the only one that is tested experimentally. However, I’m not sure why the convergence rate for the sum of residuals is important? Can’t you get 0 sum of residual by overestimating some examples and underestimating others?
3. Related to above, in Theorem 4 the authors claim faster convergence for the parallel residual by comparing the rates. This is an apples to oranges comparison though since in theorem 3 they are talking about convergence rate of loss and theorem 4 they are talking about convergence rate of sum of residual. Wouldn’t you want to compare to the rate for $\sum_i (<r_i \phi_i,1>^2$) instead?
4. Experiments: Since the theoretical results mainly regard convergence rates, it would have been good to also show learning curves wrt # of iterations.
5. The additional figures in the appendix are hard to read (why are there some learning rate runs missing for the implicit case?). There also seem to be graphical glitches on a few of them.
6. Introducing implicit differentiation seems kind of superfluous here, since the actual “implicit” rep for \theta can be easily expressed explicitly.
7. There are a few syntactic typos in the proofs (f.e. on line 95 the brackets, on line 106 duplicate $\sum_i$, line 108/109 there’s an extra 1/n out of nowhere that then disappears later)
8. This might be obvious but I think you should still state if/when the implicit rep will be as expressive as the explicit one since this affects the minima.
9. I believe you should state the $O(\alpha^2)$ term in theorem 4 as well.
10. In proof of theorem 3, near line 102, why is there no 1/n from the loss? Isn’t loss defined to have $1/|D_t|$?

Novelty/Impact:
I will first admit that optimization theory is not my area of expertise.
I think studying end-to-end model-based RL is interesting. However, I think generally the benefit that people in the broader community are more interested in when using these methods is generalization and sample efficiency rather than optimization convergence rate.
Furthermore, the simplifications used in this work are rather strong. I feel without TD learning, structural assumptions about the value targets and action selection the setting essentially reduces to supervised regression with a particular parameterization. 
That being said, the paper does present some interesting results about the gradient of implicit param itself that could be built upon.

Rating:
I think the work could be an alright theoretical analysis. However, I am giving a lower rating and also lower confidence primarily because I question some of the main contributions claimed: Specifically I question the validity of corollary 3 and don’t feel like theorem 4 warrants the interpretation it is given as well as a couple technical deficiencies and sloppy writing in the proofs. But I’d be willing to raise my score if these can be clarified.

Edit:
After rebuttal, authors clarified my doubts about corollary 3 and I increased my rating to 5.
I still think the significance of the results are somewhat limited with the simplified setting.
limitations_and_societal_impact: Yes
review_title: null

Meta-review: The paper aims at presenting a theoretical investigation of the gradient dynamics and the convergence properties of model-based RL methods. In order to make the analysis theoretically tractable, the authors analyze these methods by looking at a simplified setting: training a linear value function approximator using two formulations, an implicit one, i.e. parameterizing weights of a linear function with fixed features, and explicitly learning the linear weights.

The first contribution of the paper is providing proof that under some assumptions the implicit parameterization converges to the global minimum, and showing that the gradient updates differ in the two settings because the implicit parameterization induces a preconditioning on the gradients. A second contribution is in further analysing the properties of the preconditioning. The theoretical findings are finally verified experimentally on small scale problems using offline datasets, rendering the theoretical contributions easier to understand.

Whilst the paper attempts to address a very interesting and relevant problem in the field, and the submission indeed presents a stimulating study, all six reviewers have struggled to find a clear and strong connection between the insights proposed by the authors and "a theoretical account of the performance of end-to-end model-based methods" and lamented lack of substantial (practical) results. Therefore, I fear the paper in the current format will have limited impact at NeruIPS, and draw little follow up from this audience.

I hope that the authors will not give up on this work, and will consider either submitting to a venue with a more specialist audience, or acting on the specific recommendations some of the reviewers have provided, e.g. reframing the work to make it easier for the readers to draw connections between its results and the model-based methods discussed in the introduction.
Decision: Accept (Poster)