On the Convergence of Success Conditioning for Policy Optimization
Abstract
Success conditioning is a strategy for improving decision-making policies in stochastic environments; it updates a policy by increasing the probability of taking actions that yield successful outcomes. Success conditioning is common to many reinforcement learning applications, yet its limiting behavior and convergence rates are not well understood. In this work, we demonstrate that success conditioning converges to an optimal policy on a broad class of Markov decision processes (MDPs). We also derive convergence rates in some common settings. For discounted MDPs, we prove convergence within 𝒪(1/εp) iterations to an ε-optimal policy, where the exponent p depends on problem data. For single-period MDPs, such a policy is obtained within 𝒪(log(1/ε)) iterations.
Related
- The Effect of Quadrature on the Convergence of Policy Iteration for Hamilton-Jacobi-Bellman Equations
- Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs
- Continuous-Time Policy Gradient from Discrete Data: Convergence Analysis and Model-Free Algorithms
- Objective Selection in Many-Objective Optimization via Conditioning-Based Analysis of Objective Redundancy
- Bellman Policy Optimization
BibTeX
@misc{brun2026convergence,
title = {{On the Convergence of Success Conditioning for Policy Optimization}},
author = {Matthew Brun and Xu Andy Sun},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03642},
eprint = {2610.03642},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03642},
}
RIS
TY - UNPB
TI - On the Convergence of Success Conditioning for Policy Optimization
AU - Matthew Brun
AU - Xu Andy Sun
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.03642
UR - https://arxiv.org/abs/2610.03642
AB - Success conditioning is a strategy for improving decision-making policies in stochastic environments; it updates a policy by increasing the probability of taking actions that yield successful outcomes. Success conditioning is common to many reinforcement learning applications, yet its limiting behavior and convergence rates are not well understood. In this work, we demonstrate that success conditioning converges to an optimal policy on a broad class of Markov decision processes (MDPs). We also derive convergence rates in some common settings. For discounted MDPs, we prove convergence within 𝒪(1/ε^p) iterations to an ε-optimal policy, where the exponent p depends on problem data. For single-period MDPs, such a policy is obtained within 𝒪(log(1/ε)) iterations.
ER -