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:
- Explicit (Model-Free): A neural network or other function approximator maps states directly to value estimates.
- 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.
- 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
maxoperator (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