Understanding End-to-End Model-Based Reinforcement Learning Methods as Implicit Parameterization

Clement Gehring, Kenji Kawaguchi, Jiaoyang Huang, Leslie Pack KaelblingNeurIPS 2021 · OpenReview

Introduction

Estimating the per-state expected cumulative rewards—the value function—is a critical aspect of reinforcement learning (RL). While standard deep neural-network function-approximation methods are common, they are often inefficient. An alternative approach, exemplified by Value Iteration Networks (VIN), is to learn transition and reward models of a latent Markov decision process whose value predictions fit the data.

Empirically, this "end-to-end" model-based approach converges faster to more robust solutions than direct model-free methods. However, the theoretical reasons behind this success have remained largely unexplored. This paper provides a theoretical foundation for this phenomenon, demonstrating that by viewing these models as an implicit parameterization of a value function, they act as a natural preconditioner for gradient descent. This drastically accelerates convergence—especially when errors are systemic across states—despite the non-convexity of the optimization landscape.

The Problem: Explicit vs. Implicit Value Estimation

In RL, agents must estimate the expected cumulative reward of being in a specific state. There are two primary paradigms for this:

  1. Explicit (Model-Free): A neural network or other function approximator maps states directly to value estimates.
  2. Implicit (End-to-End Model-Based): The agent learns a "latent" model (transition probabilities and rewards) and solves that model to derive the value estimates.

While explicit methods are straightforward, they are often slow to converge. Conversely, implicit methods like VINs have shown great empirical success but introduce complex, non-linear optimization dynamics. This paper aims to bridge the gap by analyzing why learning a model to fit values is often superior to learning the values directly.

Methodology: Implicit Parameterization and Gradient Dynamics

To make the mathematical analysis tractable, the authors simplify the problem to a linear function approximation setting.

  • Implicit Parameterization: Instead of learning value weights $\theta$ directly, the method learns model parameters $\psi$ (rewards $w$ and transition log-probabilities $F$). The value function is then defined implicitly by the solution to a Bellman-like constraint: $h(\hat{\theta}; \psi) = 0$.
  • Implicit Differentiation: To train this architecture, the authors use the implicit function theorem to propagate gradients from the value error back through the "solver" to the underlying model parameters.
  • Gradient Dynamics Analysis: By comparing the "gradient flow" (the continuous path weights take during training) of the explicit versus implicit versions, they prove that the implicit update is mathematically equivalent to a preconditioned version of the explicit update.

Key Insights: Preconditioning and the "1" Direction

The theoretical analysis yields several profound insights into the optimization landscape of implicit RL methods:

  • Global Convergence in a Non-Convex Landscape: Even though the implicit mapping makes the optimization problem non-linear and non-convex, gradient descent is proven to converge to a global optimum from any initialization.
  • Natural Preconditioning: The structure of the Markov Reward Chain acts as a natural preconditioner. In optimization, a good preconditioner warps the loss surface to make it "rounder," allowing gradient descent to take a more direct, efficient path to the solution.
  • The "1" Direction Speedup: The most striking finding is that the implicit method is exceptionally fast at correcting errors that are consistent across all states (represented mathematically as the "1" vector). If an agent overestimates the value of every state by the same constant amount, the implicit method corrects this systemic bias much faster than an explicit model.

Empirical Validation and Results

The authors evaluate their theory on three classic RL benchmark domains—Chain MDP, Four Rooms, and Mountain Car—modified to test specific types of errors. They specifically manipulate reward offsets (adding a constant to all rewards) to create systemic errors and observe how each method responds.

Effect of reward offsets on residual components across environments.
  • Theoretical Convergence Rate: The authors derive that the convergence rate along the "1" direction for the implicit method is $O(1/(1-\eta)^2)$, where $\eta$ is an internal discount factor. This is substantially faster than the standard $O(1/n)$ rate of explicit stochastic gradient descent (SGD).
  • Robustness to Systemic Bias: Because the implicit method converges faster along the "1" direction, it is far less sensitive to the scale and skew of rewards. As seen in the experiments, as the reward offset increases (making the "1" component of the error larger), the explicit method's performance degrades severely. In contrast, the implicit method remains robust, maintaining low residual error across various offsets.

Limitations and Future Work

While this paper provides a strong theoretical step forward, it notes a few limitations:

  • Singleton Actions: The current theoretical analysis is restricted to a Markov Reward Chain (an MDP with only one action). While the authors argue this generalizes to the "optimal policy" case, the mathematics for a full MDP with multiple actions and the max operator (Bellman Optimality) are significantly more complex.
  • Linearity: The proofs rely on linear function approximation. Modern deep RL uses highly non-linear architectures, which may introduce additional dynamics.
  • Internal Discount Factor: The results show that the choice of the internal discount factor $\eta$ (used in the latent model) is crucial, but it does not necessarily have to match the true environment discount factor $\gamma$. Determining how to choose the optimal $\eta$ remains an open question for future research.

Summary updated

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. An alternative approach, exemplified by value iteration networks, is to learn transition and reward models of a latent Markov decision process whose value predictions fit the data. This approach has been shown empirically to converge faster to a more robust solution in many cases, but there has been little theoretical study of this phenomenon. In this paper, we explore such implicit representations of value functions via theory and focused experimentation. We prove that, for a linear parametrization, gradient descent converges to global optima despite non-linearity and non-convexity introduced by the implicit representation. Furthermore, we derive convergence rates for both cases which allow us to identify conditions under which stochastic gradient descent (SGD) with this implicit representation converges substantially faster than its explicit counterpart. Finally, we provide empirical results in some simple domains that illustrate the theoretical findings.
BibTeX
@inproceedings{gehring2021understanding,
  author = {Clement Gehring and Kenji Kawaguchi and Jiaoyang Huang and Leslie Pack Kaelbling},
  title = {{Understanding End-to-End Model-Based Reinforcement Learning Methods as Implicit Parameterization}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=xj2sE--Q90e},
}
Figure