Research map / Reinforcement learning / MDPs and planning

On the Convergence of Success Conditioning for Policy Optimization

NeurIPS 2026 · Reinforcement learning › MDPs and planning · approach: POMDPs and confounded RL · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Analyzes success conditioning (SC), a policy update that reweights actions by their Q-values, proving convergence to the optimal restricted policy in general MDPs and deriving iteration complexities for single-period and discounted MDPs.

Problem

Success conditioning is widely used to improve stochastic policies, but its limiting behavior and convergence rates were not rigorously understood, and convergence was posed as an open question.

Approach

Treats SC as an iterative policy optimization method: the update pi_{k+1}(a|s) = pi_k(a|s)Q_k(s,a)/V_k(s) is shown to monotonically increase values and converge to the optimal restricted value function over initially supported actions; explicit iteration bounds are derived via approximate value iteration analysis.

Key results

• SC value functions converge to the optimal restricted value function V* on MDPs satisfying the assumptions (Theorem on limiting behavior).
• For single-period MDPs, an epsilon-optimal policy is obtained within O(log(1/epsilon)) iterations, with a coefficient that can blow up as the second-best action approaches the best.
• For discounted MDPs, an epsilon-optimal policy is obtained within O(1/epsilon^p) iterations, where p depends on problem data and may be arbitrarily large; a parameter-free corollary gives explicit p_1 or p_2.

Surprising findings

• Discounted-MDP rate recovers only O(1/epsilon) as gamma goes to zero, slower than the O(log(1/epsilon)) single-period rate, suggesting either a loose bound or a true gap between the settings.
• SC converges much more slowly than value or policy iteration, and the authors frame this slowness as conservatism that helps stability.

Limitations

• Convergence rates are worst-case upper bounds and the exponent p can be very large for some instances.
• Analysis assumes exact Q-function computation and positive initial values; no sample-based or function-approximation analysis.
• Converges only to the optimal restricted policy over the support of the initial policy.

Experimental setup

Metrics: optimality gap iteration complexity

Baselines: reward-weighted regression value iteration policy iteration TRPO PPO

Builds on: reward-weighted regression value iteration policy iteration trust-region policy optimization

Closest papers by meaning

• REINFORCE Converges to Optimal Policies with Any Learning Rate (NeurIPS 2025 · similarity 0.91)
• Success-Conditioning as Policy Improvement: The Optimization Problem Solved by Imitating Success (ICML 2026 · similarity 0.91)
• Global Convergence of Policy Gradient in Average Reward MDPs (ICLR 2025 · similarity 0.89)
• Optimistic Planning by Regularized Dynamic Programming (ICML 2023 · similarity 0.89)
• Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs (NeurIPS 2026 · similarity 0.88)
• Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs (NeurIPS 2026 · similarity 0.87)