Reliable Critics: Monotonic Improvement and Convergence Guarantees for Reinforcement Learning
Eshwar S. R, Gugan Thoppe, Aditya Gopalan, Gal Dalal · 2025
Read Reliable Critics: Monotonic Improvement and Convergence Guarantees for Reinforcement Learning by Eshwar S. R, Gugan Thoppe, Aditya Gopalan, Gal Dalal (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-07134.txt.
Introduction
Eshwar and co-authors restore classic guarantees for reinforcement learning methods in a 2025 paper. In such learning, an agent improves a strategy step by step. Textbook methods carry proofs of steady improvement when values sit in a table, but those proofs break when values are estimated by flexible functions, as in real systems.
The team design new variants whose value estimates always improve and never overshoot the true return. One variant updates the strategy with a cautious bound that counts estimation error. The other shares that evaluation but moves more boldly. Early simulations beat the classic methods. Popular deep learning methods descend from the cautious classic, so firming its base matters for practice.
Catalog record
| CREATOR | Eshwar S. R, Gugan Thoppe, Aditya Gopalan, Gal Dalal |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 56 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-07134
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Reliable Critics: Monotonic Improvement and Convergence Guarantees for Reinforcement Learning Eshwar S. R, Gugan Thoppe, Aditya Gopalan, Gal Dalal Abstract Despite decades of research, it remains challenging to correctly use Reinforcement Learning (RL) algorithms with function approximation. A prime example is policy iteration, whose fundamental guarantee of monotonic improvement collapses even under linear function approximation. To address this issue, we introduce Reliable Policy Iteration (RPI). It replaces the common projection or Bellman-error minimization during policy evaluation with a Bellman-based constrained optimization. We prove that not only does RPI confer textbook monotonicity on its value estimates but these estimates also lower bound the true return. Also, their limit partially satisfies the unprojected Bellman equation, emphasizing RPI’s natural fit within RL. RPI is the first algorithm with such monotonicity and convergence guarantees under function approximation. For practical use, we provide a model-free variant of RPI that amounts to a novel critic. It can be readily integrated into primary model-free PI implementations such as DQN and DDPG. In classical control tasks, such RPI-enhanced variants consistently maintain their lower-bound guarantee while matching or surpassing the performance of all baseline methods. 1 Introduction Function Approximation (FA) in Reinforcement Learning (RL) creates a fundamental challenge: while necessary for handling large state-action spaces, it also makes learning unreliable [ 1 ] . The risk is most evident in Policy Iteration (PI) [ 2 ] , a foundational RL algorithm that alternates between policy evaluation and a greedy policy update. In the tabular setting, the successive policies generated by PI improve monotonically and converge to the optimal one. However, with FA, the approximation errors during policy evaluation often mislead the greedy policy updates [ 3 , 4 , 5 ] . In particular, FA methods tend to overestimate some state–action values and underestimate others, offering no consistent signal for reliable policy improvement [ 6 , 7 , 8 ] . Prior work primarily addresses this challenge by limiting the magnitude of policy updates. Conservative PI (CPI) [ 9 ] , for instance, bounds policy degradation by cautiously combining the existing policy with the one that is greedy with respect to the latest value estimate. Similarly, Trust Region Policy Optimization (TRPO) [ 10 ] uses KL divergence to maintain proximity to previous policies, while Proximal Policy Optimization (PPO) [ 11 ] achieves a similar goal via clipping. In this work, we instead target the root cause: policy evaluation. While tabular PI calculates exact value functions, standard FA variants typically settle for either a mean-squared projection [ 4 , 12 ] , the Bellman-residual minimizer [ 3 ] , the projected Bellman fixed-point [ 12 ] , or their bootstrapped extensions [ 13 , 14 , 15 ] . Despite their widespread adoption, these approaches fundamentally fail to preserve the theoretical guarantees that ensure PI’s stability and consistent improvement [ 1 ] . We propose a new PI paradigm to address the above issues. Our key contributions include: 1. Algorithm: We introduce Reliable Policy Iteration (RPI) in Algorithm 1 . It uses the standard greedy policy update, but adopts a novel idea for policy evaluation: it finds a value estimate that is farthest from the previous estimate while satisfying a Bellman inequality constraint. 2. Theoretical Guarantees: In Section 3 , we show that RPI recovers the classical PI guarantees of per-step improvement and convergence in the FA setting—where these properties, so far, were out of reach. Specifically, we prove that RPI’s value estimates are non-decreasing and lower bound the true policy values, thereby safeguarding performance even when intermediate policies momentarily degrade. Moreover, RPI’s value estimates converge to a vector that partially satisfies the unprojected Bellman equation, demonstrating natural alignment with fundamental RL objectives. We also bound the performance gap between RPI’s terminal policy and the optimal policy. Separately, we establish RPI as a true generalization of classical PI and show that, with an \ell_{1} -type norm, its policy evaluation step admits a constrained projection interpretation. 3. Practical Implementation: In Section 5 , we develop a model-free realization of RPI’s policy-evaluation step. We embed the constraints as penalties in the objective and then invoke Jensen’s inequality to get a tractable function. This serves as a new critic loss (in the actor-critic paradigm) that seamlessly integrates into popular deep RL algorithms such as Deep Q-Network (DQN) [ 15 ] and Deep Deterministic Policy Gradient (DDPG) [ 16 ] . 4. Empirical Results : Our experiments in Section 6 show that RPI and its deep-RL variants consistently maintain their lower-bound property across diverse benchmarks—from discrete Inventory Control to classical continuous control tasks such as CartPole and Inverted Pendulum. Crucially, RPI-enhanced DQN and DDPG outperform their vanilla versions and meet or surpass competitive baselines such as PPO [ 11 ] and TD3 [ 8 ] in reaching performance thresholds. 2 Related Work PI for finite, tabular Markov Decision Processes (MDPs) was introduced by Bellman [ 17 ] and formalized by Howard [ 2 ] . Since the Bellman operator is both a contraction and monotone, PI produces an increasing sequence of value estimates that converges to the optimum. There also are tabular extensions, such as modified [ 18 ] and asynchronous PI [ 19 ] , that retain these guarantees while allowing for incomplete policy evaluations and partial policy updates. Given this flexibility, a natural question is whether PI can be adapted to the FA setting while still preserving these guarantees. The earliest use of dynamic programming with FA can be traced to Samuel’s checkers program [ 20 , 21 ] , which selected moves via multistage lookahead while evaluating positions with a value function expressed as a linear combination of handcrafted features. Since then, different attempts have been made to extend PI to the FA setting, which can be categorized and summarized as follows: 1. Policy Iteration with Approximate Evaluation. A large body of work is based on changing only the policy evaluation step, leaving the greedy policy update unchanged. During evaluation, these methods typically take one of three paths: (i) minimize mean-squared projection error, as in TD(1) [ 12 ] ; (ii) solve for the projected Bellman fixed point, as in LSPI and TD( \lambda ) [ 22 , 12 ] ; or (iii) minimize the Bellman residual, as in Fitted Q-Iteration, DQN, and AMPI-Q [ 14 , 15 , 23 ] . However, to paraphrase Bertsekas 2011 , “these methods assume that a more accurate value approximation will yield a better policy—a reasonable but by no means self-evident hypothesis.” These methods are often known to diverge, oscillate between worse policies, or exhibit unreliability in learning good policies, leading to weak performance bounds [ 1 , 24 , 25 , 26 ] . An approach that can address these concerns under a greedy actor has remained elusive thus far. 2. Policy Iteration with Cautious Actor. A complementary research line has focused on making policy updates cautious either by (i) bounding the KL divergence between successive policies or (ii) forming a convex mixture between the current and the full greedy policies. This idea dates back to Conservative PI (CPI) [ 9 ] and underpins several influential algorithms, including TRPO [ 10 ] , PPO [ 11 ] , and Safe PI (SPI) [