Abstract: This paper aims at theoretically and empirically comparing two standard optimization criteria for Reinforcement Learning: i) maximization of the mean value and ii) minimization of the Bellman residual. For that purpose, we place ourselves in the framework of policy search algorithms, that are usually designed to maximize the mean value, and derive a method that minimizes the residual $\|T_* v_π- v_π\|_{1,ν}$ over policies. A theoretical analysis shows how good this proxy is to policy optimization, and notably that it is better than its value-based counterpart. We also propose experiments on randomly generated generic Markov decision processes, specifically designed for studying the influence of the involved concentrability coefficient. They show that the Bellman residual is generally a bad proxy to policy optimization and that directly maximizing the mean value is much better, despite the current lack of deep theoretical analysis. This might seem obvious, as directly addressing the problem of interest is usually better, but given the prevalence of (projected) Bellman residual minimization in value-based reinforcement learning, we believe that this question is worth to be considered.
Introduction
The fundamental goal of Reinforcement Learning (RL) is to find a policy $\pi$ that maximizes the expected return, often referred to as the "value." However, because the optimal value function is typically unknown, many algorithms—particularly those in the Approximate Dynamic Programming (ADP) family—rely on minimizing the Bellman residual as a proxy.
The Bellman residual acts as a "consistency check": in an ideal scenario, the current value of a state should equal the immediate reward plus the discounted value of the subsequent state. While minimizing this error is mathematically convenient and provides a clear optimization target, it remains a proxy for the true objective of value maximization. This research investigates whether this proxy is reliable, specifically focusing on how the sampling distribution (the data used for training) impacts the performance of residual-based methods compared to direct value maximization.
Methodology: Policy Search vs. Residual Minimization
To ensure a rigorous comparison, the authors utilize a Policy Search framework for both optimization criteria, isolating the objective function as the primary variable.
- Policy Search (PS): This is the standard approach that directly maximizes the mean value $E_\nu[v_\pi(S)]$ for a given state distribution $\nu$.
- Residual Policy Search (RPS): The authors derive a novel method that minimizes the Bellman residual $\|T_* v_\pi - v_\pi\|_{1,\nu}$ over the space of policies.
By deriving a subgradient for the RPS objective, the researchers can employ gradient descent to minimize the residual. This setup maintains constant policy parameterization (using Gibbs/Softmax policies) and environment settings, allowing for a direct "apples-to-apples" comparison between maximizing value and minimizing the Bellman error.
Experimental Setup: Garnet Problems
The study employs Garnet problems (Generalized Average Reward Non-stationary Environments) to test these methods. These are abstract, randomly generated Markov Decision Processes (MDPs) defined by the number of states, actions, and a "branching factor" (the number of possible next states for each action). Garnets are ideal for fundamental RL research because they lack the specific structural biases found in common benchmarks like Cartpole or Atari, allowing for precise control over mathematical properties such as the concentrability coefficient.
The Proxy Paradox and Concentrability
A central finding of the research is the impact of the concentrability coefficient, which measures the mismatch between the sampling distribution (where the agent learns) and the optimal occupancy distribution (where the optimal policy actually spends time).
The experiments reveal a "Proxy Paradox": RPS is highly fragile to distribution mismatches. If the sampling distribution does not align well with the optimal policy's path, the Bellman residual can be successfully minimized while the actual policy performance remains poor. In some cases, the Bellman residual and actual policy error are not even positively correlated; improving the policy's value can actually result in an increase in the Bellman residual.
Empirical Results
In head-to-head tests across 100 different Garnet problems, Policy Search (PS) consistently outperformed Residual Policy Search (RPS). PS demonstrated remarkable robustness to distribution shifts; even when the sampling distribution was moved away from the ideal, the performance of PS remained stable. In contrast, the performance of RPS degraded significantly as the concentrability coefficient increased.
Visualizing the learning paths (as seen in Figure 4) confirms that while RPS effectively minimizes the residual, it does not reliably minimize the relative value error. PS often ignores the Bellman residual entirely, yet consistently finds policies with higher actual value.
Conclusion and Future Work
While Bellman residuals are mathematically elegant and support strong theoretical proofs, this research suggests they are often a poor proxy for finding optimal policies in practice. Direct value maximization (PS) is empirically superior and more robust, despite currently lacking the same level of deep theoretical analysis as residual-based methods. Future work is needed to tighten the theoretical bounds for PS to better explain its empirical success. For practitioners, the takeaway is clear: if the goal is a high-performing policy, maximizing value directly is generally more effective than relying on the Bellman residual proxy.
Summary updated