In reinforcement learning (RL), the fundamental goal is to find a policy that maximizes the expected return, or the "value." However, directly maximizing this value can be computationally difficult. To circumvent this, many popular algorithms—especially in Approximate Dynamic Programming (ADP)—instead try to minimize the Bellman residual. This residual represents the error in the Bellman equation; if you have the perfect value function, the residual is zero.
While minimizing the Bellman residual is a mathematically elegant shortcut with strong theoretical bounds, this paper asks a critical question: Is the Bellman residual actually a good stand-in for the true goal of maximizing value?
By comparing these two standard optimization criteria theoretically and empirically, the authors demonstrate that the Bellman residual is often a "bad proxy" in practice because it is hyper-sensitive to how data is sampled. Directly maximizing the mean value of a policy proves to be far more robust and effective.
A Unified Framework for Comparison
To create a fair, "apples-to-apples" comparison, the authors evaluate both approaches within the framework of Policy Search:
- Policy Search (PS): The standard approach that directly maximizes the mean value using gradient ascent.
- Residual Policy Search (RPS): A novel method derived by the authors that uses subgradient descent to minimize the Bellman residual over the space of policies.
By forcing both methods to operate directly on policies rather than value functions, the authors isolate the impact of the objective function itself. They also analyze the concentrability coefficient, a mathematical term measuring the mismatch between the states sampled during training and the states the optimal policy actually visits.
The experiments utilize Garnet problems (Generalized Average Reward Non-stationary Environments)—abstract, randomly generated Markov Decision Processes (MDPs). These controlled environments allow the authors to precisely calculate the ideal sampling distribution and the concentrability coefficient, which would be impossible in complex, real-world datasets.
Key Insights: The Sampling Trap
The core finding of the paper is that the Bellman residual is only a reliable proxy under ideal conditions.
- The Sampling Trap: If your sampling distribution perfectly matches the state occupancy of the optimal policy, both RPS and PS perform similarly well. However, if there is a mismatch (a high concentrability coefficient), minimizing the residual leads to poor policies. When the sampling distribution is skewed, the performance of the Residual approach collapses.
- Robustness of Value Maximization: Directly maximizing the mean value is remarkably "blind" to this sampling mismatch. Even when training data comes from a poor distribution, direct maximization still tends to find a high-quality policy.
- Lack of Correlation: The experiments reveal that a low Bellman residual does not necessarily mean a policy has high value, and vice versa. The two metrics are often poorly correlated during the learning process.
In almost all non-ideal cases, direct Policy Search significantly outperformed Residual Policy Search. The authors conclude that the prevalence of Bellman residual minimization in the literature might be driven more by its mathematical convenience than its empirical superiority.
Theoretical Mystery and Future Work
Interestingly, the paper highlights a fascinating gap between theory and practice. The Bellman residual actually boasts "better" (linear) theoretical bounds regarding the optimization horizon compared to the quadratic bounds of direct value maximization. Yet, the experiments show these bounds are not tight in practice; the theoretically "worse" method (PS) performs substantially better in reality.
The authors call for a deeper theoretical analysis to explain exactly why direct value maximization is so robust to sampling distribution mismatches. Furthermore, while these insights are clear in small, discrete MDPs, testing whether this "proxy problem" scales to high-dimensional Deep RL environments remains an important open challenge for the field.
Summary updated