Introduction
A fundamental question in value-based Reinforcement Learning (RL) is whether the Bellman residual serves as an effective proxy for the true objective: maximizing a policy's expected return. While minimizing the Bellman residual is theoretically appealing due to well-defined error bounds, this paper argues that it is often a poor substitute for direct value maximization. Through a combination of theoretical analysis and controlled experiments on synthetic MDPs, the authors demonstrate that Bellman residuals are dangerously sensitive to distribution mismatch, whereas direct policy search remains remarkably robust.
Methodology: Policy Search vs. Residual Minimization
To facilitate a direct comparison, the authors contrast standard Policy Search (PS), which maximizes the mean value $E[v_\pi]$, with a proposed Residual Policy Search (RPS). RPS is designed to minimize the Bellman residual—the discrepancy between the current value estimate and the target provided by the Bellman operator—directly over the space of policies.
Key technical developments include:
- Subgradient Derivation for RPS: The authors derive a subgradient for the Bellman residual objective, enabling policy optimization via descent methods analogous to standard policy gradients.
- Performance Bounds: A new bound for RPS (Theorem 3) is established, showing a linear dependency on the optimization horizon. This is theoretically superior to the quadratic dependency typically found in value-based bounds.
- Analytical Gradient Framework: To isolate the properties of the objectives from sampling noise, the comparison utilizes analytical gradients to remove confounding factors.
Experimental Framework: Garnet MDPs
The study employs Garnet problems (Generalized Average Reward Non-stationary Elastic Templates), which are randomly generated, abstract Markov Decision Processes. Specifically, the authors tested on $G(30, 4, 2)$ configurations (30 states, 4 actions, branching factor of 2) using random binary state features to simulate function approximation. Garnets provide a controlled environment to study RL dynamics and precisely calculate concentrability coefficients—metrics of distribution mismatch between training samples and the optimal policy's occupancy.
Theoretical vs. Practical Insights
The investigation reveals several critical insights into the relationship between residuals and value:
- The Proxy Paradox: While minimizing the Bellman residual eventually reduces error relative to the optimal value, it is significantly less efficient than direct value maximization.
- Concentrability Sensitivity: The Bellman residual approach relies heavily on the sampling distribution matching the optimal policy's occupancy measure. In the presence of distribution mismatch (high concentrability), the residual becomes a deceptive indicator of policy quality.
- Robustness of Value Maximization: Conversely, PS is surprisingly insensitive to distribution mismatch. It often succeeds in finding high-quality policies even when theoretical bounds suggest potential failure due to high concentrability.
Empirical Results
The empirical evaluation on Garnet MDPs highlights the performance gap between direct value maximization (PS) and residual minimization (RPS).
As illustrated in Figure 6, while both methods aim to improve policy quality, PS exhibits a more direct and robust reduction in error (a). Notably, the Bellman residual for PS (c) does not necessarily decrease monotonically or reach the same low levels as RPS (d), yet it achieves comparable or superior value performance. This decoupling of the residual from actual policy quality in PS underscores the paper's thesis that the Bellman residual can be a deceptive proxy. When a mismatch between the sampling distribution and the ideal distribution is introduced, the error for RPS tends to explode, while the error for PS remains remarkably stable.
Discussion and Limitations
While the results favor direct value maximization, the authors acknowledge several limitations. The study's reliance on small-scale Garnet MDPs was necessary for analytical gradient calculations but leaves open the question of scalability to massive, continuous control tasks. Furthermore, a significant theoretical gap remains: the method that performs best in practice (PS) currently lacks the robust theoretical guarantees associated with residual minimization. The authors call for deeper theoretical work to explain why mean value maximization is so robust despite its weaker theoretical foundations.
Summary updated