Monotonic Policy Improvement in Reinforcement Learning

47 concepts33 papers1 proposal

In reinforcement learning (RL), the ultimate goal is to find a policy that maximizes expected long-term rewards. A classic way to achieve this is through policy gradient methods, which compute local gradients and update policy parameters iteratively. However, as Vaswani notes in A general class of surrogate functions for stable and efficient reinforcement learning, these standard updates often lack theoretical guarantees for monotonic improvement when paired with complex function approximators like deep neural networks.

The core issue stems from a fundamental feedback loop: when an agent's policy changes, the distribution of states it visits also changes. A policy update that looks promising based on data collected by the old policy might shift the agent into entirely unfamiliar, low-reward regions of the state space. This distribution shift can cause catastrophic performance drops during training.

To prevent these drops, a rich body of research focuses on monotonic policy improvement—mathematical frameworks ensuring that every single policy update is guaranteed to improve, or at least maintain, the agent's true performance.

The Engine: Minorization-Maximization and Lower Bounds

How can we guarantee improvement if we cannot predict exactly how a policy change will alter the state distribution? The answer lies in the Minorization-Maximization (MM) algorithmic design pattern. Instead of optimizing the true, complex objective directly, we construct a simpler surrogate objective that acts as a local lower bound.

To be an effective safeguard, this surrogate must satisfy two conditions:

  1. It must match the true objective's value exactly at the current policy.
  2. It must be a global lower bound, meaning its value is less than or equal to the true objective everywhere else.

If we find a new policy that maximizes this surrogate, the true performance is mathematically guaranteed to increase.

Performance
    ^
    |         True Objective
    |           _--~--_
    |          /       \     <- Guaranteed Gain
    |         /  _---_  \
    |________/_/_______\_\________> Policy Space
            |  \       /
            |   `-___-' <- Surrogate Lower Bound
        Old Policy  New Policy

Ghosh et al. demonstrate in An operator view of policy gradient methods that utilizing global lower bounds offers a far more robust theoretical foundation for policy updates than the local approximations typically used in heuristic trust-region methods. By maximizing a tighter mathematical lower bound on the performance difference between policies, Metelli et al. show in Safe Policy Iteration: A Monotonically Improving Approximate Policy Iteration Approach how to optimally balance the trade-off between the current policy and a greedy target policy, enabling larger, more stable update steps without performance oscillations.

This lower-bound perspective can also be framed statistically. For example, Ueno et al. show in Weighted Likelihood Policy Search with Model Selection that policy optimization can be treated as a weighted maximum likelihood problem. This formulation optimizes a lower bound of the expected reward in a manner analogous to the Expectation-Maximization (EM) algorithm, ensuring a non-decreasing performance trend across iterations.

To bridge the gap between theory and real-world deployment, we must also account for the variance inherent in empirical data collection. Papini et al. address this in Adaptive Batch Size for Safe Policy Gradients by incorporating statistical concentration bounds (such as Chebyshev or Empirical Bernstein bounds) directly into the lower bound. This mechanism dynamically adjusts step and batch sizes, guaranteeing monotonic improvement with high probability even when gradient estimates are noisy.

The Geometry of Updates: Drift and Mirror Descent

To ensure that the surrogate lower bound remains a valid proxy for the true objective, the updated policy must not stray too far from the current policy. If the step is too large, the state distribution shifts excessively, and the lower bound collapses. This proximity constraint is typically enforced using a penalty or a geometric distance metric.

In Mirror Learning: A Unifying Framework of Policy Optimisation, Grudzien Kuba et al. provide a unifying mathematical framework for popular algorithms like TRPO and PPO. They show that policy updates can be generalized by subtracting a drift functional—a penalty for moving away from the current policy. As long as this drift functional is non-negative and has a zero gradient at the current policy, strict monotonic improvement is guaranteed.

This geometric regularization frequently takes the form of Mirror Descent. The choice of distance metric dictates the behavior of the updates:

Remarkably, optimizing these regularized objectives does not always require iterative inner loops. Li et al. derive a closed-form analytical update rule in An Analytical Update Rule for General Policy Optimization that directly calculates the new policy by weighting the old policy with an exponential function of the advantage, achieving guaranteed monotonic improvement in a single step.

Distilling Planning into Reactive Policies

The guarantees of monotonic improvement are not restricted to model-free gradient updates; they also serve as a bridge between computationally heavy online planning and fast, reactive policy networks.

When an agent plans into the future (e.g., using lookahead trees or world models), it generates high-quality behavioral trajectories. "Distillation" is the process of training a neural network policy to mimic these planning results. Monotonic improvement frameworks ensure that this distillation process does not lose performance along the way.

Li et al. prove in Theoretically Guaranteed Policy Improvement Distilled from Model-Based Planning that by extending maximum entropy RL to a multi-step optimization problem, distilling a multi-step lookahead plan into a single-step policy network preserves the monotonic improvement property. Similarly, Danihelka et al. introduce a principled sampling framework using Gumbel noise in Policy improvement by planning with Gumbel, establishing a mathematical guarantee that the search results will consistently outperform the root policy, even when the search depth or simulation budget is severely constrained.

This principle operates across various scales of decision-making:

Data-Driven Regimes: Offline, Transfer, and Autoregressive Learning

Monotonic safeguards are equally vital when agents must learn from fixed historical datasets or transfer knowledge from existing policies, where out-of-distribution actions pose a severe risk.

Offline and Imitation Learning

In offline settings, an agent cannot interact with the environment to correct errors. Wang et al. address this in Exponentially Weighted Imitation Learning for Batched Historical Data by exponentially re-weighting standard imitation learning based on the estimated advantage (the MARWIL algorithm). This framework provides a theoretical guarantee of monotonic improvement relative to the data-generating behavior policy. To prevent the agent from taking ungrounded out-of-distribution actions, Mao et al. introduce Supported Value Regularization for Offline Reinforcement Learning, leveraging importance sampling bias to guarantee monotonic convergence to the optimal policy strictly within the support of the historical dataset.

Policy Reuse and Curriculums

When transferring knowledge from a library of source policies to a new target policy, Zhang et al. (CUP: Critic-Guided Policy Reuse) and Li et al. (IOB: Integrating Optimization Transfer and Behavior Transfer for Multi-Policy Reuse) demonstrate that regularizing the target policy toward a guidance policy selected by the critic provides a strict monotonic improvement guarantee. This ensures that incorporating external knowledge never degrades performance, even if the critic's value function contains approximation errors.

Similarly, Bajaj et al. leverage this concept for curriculum learning in Task Phasing: Automated Curriculum Learning from Demonstrations. By blending control and reward signals from a sub-optimal demonstrator to the agent within a maximum entropy framework, they guarantee that the agent's performance on the target task increases monotonically, preventing the sudden performance drops common when task difficulty scales up.

Suffix-Closed Policy Sets

A critical structural insight for multi-policy operations is uncovered by Borsa in Generalised Policy Improvement with Geometric Policy Composition. For policy improvement guarantees to remain valid when an agent dynamically switches between multiple candidate behaviors, the set of available policies must be suffix-closed.

$$\text{If } (a_1, a_2, \dots, a_n) \in \Pi, \text{ then } (a_2, \dots, a_n) \in \Pi$$

This means that if a sequence of actions is available for evaluation, every tail-end sub-sequence of that trajectory must also be a valid candidate in the policy set. Without this property, switching behaviors mid-trajectory can invalidate the performance lower bounds, breaking the improvement guarantee.

Autoregressive Coherence

This distribution alignment also explains why iterative fine-tuning works for sequence-modeling approaches to RL (like Decision Transformers). As Karwowski et al. show in Incoherence in goal-conditioned autoregressive models, goal-conditioned autoregressive models often suffer from "incoherence" because they select actions based on how a random agent would perform in the future rather than how they themselves will perform. They prove that repeated cycles of training on a model's own self-generated trajectories monotonically resolve this mismatch, steadily driving expected returns toward the optimum.

Formal Verification: Ironclad Guarantees

Because monotonic policy improvement forms the mathematical bedrock of safe and reliable decision-making, researchers have sought the highest possible level of certainty through formal verification.

In CertRL: Formalizing Convergence Proofs for Value and Policy Iteration in Coq, Shinnar et al. provide the first machine-checked formalization of the Policy Improvement Theorem within the Coq proof assistant. By utilizing category theory and metric coinduction, they explicitly prove that local, state-wise greedy updates to a policy monotonically increase the global value function.

This formal verification moves the field beyond pen-and-paper proofs, establishing an ironclad, machine-checked guarantee that the core iterative mechanics driving modern policy optimization will consistently and monotonically converge to a globally optimal strategy.

Key Foundational Work

Suboptimality Bounds for Stochastic Shortest Path Problems (2011) — contributed 1 concept elements to this direction.
Flexible Policy Construction by Information Refinement (1996) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_monotonic_policy_improvement_cf90b69d,
  title = {monotonic policy improvement},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/monotonic-policy-improvement/rdr_cf90b69d8b4c4642bd86825046ab2f46},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_monotonic_policy_improvement_cf90b69d_v1,
  title = {monotonic policy improvement},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/monotonic-policy-improvement/rdr_cf90b69d8b4c4642bd86825046ab2f46/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake