Abstract
This paper aims at theoretically and empirically comparing two standard optimization criterion for Reinforcement Learning: i) maximization of the mean value (predominant approach in policy search algorithms) and ii) minimization of the Bellman residual (mainly used in approximate dynamic programming). For doing so, we introduce a new policy search algorithm based on the minimization of the residual $\|T_* v_\pi - v_\pi\|_{1,\nu}$. We prove that it enjoys a performance bound that is better than the sole known bound for maximizing the mean value and that matches the best known bounds in approximate dynamic programming. We also conduct experiments on randomly generated generic Markov decision processes to compare both approaches empirically. It turns out that the Bellman residual is a good optimization proxy only if there is a good match between the sampling distribution and the discounted state occupancy distribution induced by the optimal policy, while maximizing the mean value is rather insensitive to this issue.
Introduction
In Reinforcement Learning (RL), the ultimate goal is to find a policy $\pi$ that maximizes the expected return, or mean value. Traditionally, two distinct paradigms have emerged: Policy Search, which directly maximizes the mean value, and Approximate Dynamic Programming (ADP), which minimizes the "Bellman residual"—the discrepancy between the current value function and the Bellman optimality target. While the Bellman residual is a popular theoretical proxy due to its elegant mathematical guarantees, this paper investigates whether it is a reliable indicator of policy quality in practice.
Methodology: Residual Policy Search
To facilitate a rigorous "head-to-head" comparison, the authors introduce Residual Policy Search (RPS). Unlike standard Policy Search (PS) which maximizes value, RPS operates within the same policy-space framework but optimizes for the minimization of the residual $\|T_* v_\pi - v_\pi\|_{1,\nu}$.
Theoretical Analysis and Datasets
The authors derive a new performance bound for RPS that improves upon existing ADP bounds, showing a linear rather than quadratic dependency on the horizon. To isolate the effect of the optimization criterion, experiments are conducted in an idealized setting using analytical gradients on Garnet problems—randomly generated, abstract Markov Decision Processes (MDPs) that allow for precise control over environment complexity without the confounding variables of complex simulators.
The Concentrability Trap
A central finding of the research is the sensitivity of the Bellman residual to the sampling distribution $\nu$. The "concentrability coefficient" measures the mismatch between the training data distribution and the distribution induced by the optimal policy.
Experiments demonstrate that the Bellman residual is a "lying proxy" when distribution mismatch is high. An agent might successfully minimize the residual on the training distribution, but this does not translate to improved policy performance if the training data does not cover the states visited by the optimal policy. Conversely, direct value maximization (PS) proves remarkably robust to such mismatches.
Empirical Results
The empirical results highlight a significant theory-practice gap. As seen in the comparison of value error and residuals, the Bellman residual can be deceptive; in some cases, the residual actually increases while the policy performance is improving.
In scenarios with poor sampling distributions, RPS fails to significantly improve the policy. In contrast, PS reaches near-optimal performance regardless of the distribution quality, as illustrated by the rapid convergence of relative value error.
Conclusion and Future Work
The study concludes that while residual-based methods have more mature theoretical foundations, value-maximization methods are more effective in practice. This suggests that the RL community's theoretical focus on residuals might be misplaced. Future work is needed to develop deeper theoretical analyses for direct value maximization and to explore how these criteria interact with stochastic gradient estimates and complex function approximators like neural networks.
Summary updated