On the Convergence of Success Conditioning for Policy Optimization
Paper proves success conditioning converges to optimal policies on broad MDP classes, with O(1/ε^p) iterations for discounted MDPs and O(log(1/ε)) for single-period settings.
The paper analyzes success conditioning, a strategy that updates policies by increasing the probability of actions yielding successful outcomes, common in reinforcement learning. The authors prove convergence to an optimal policy on a broad class of Markov decision processes and derive convergence rates. For discounted MDPs, an ε-optimal policy is reached within O(1/ε^p) iterations where exponent p depends on problem data; single-period MDPs achieve this within O(log(1/ε)) iterations.
- Success conditioning proven to converge to optimal policy on broad MDP classes
- Discounted MDPs reach ε-optimality in O(1/ε^p) iterations
- Single-period MDPs reach ε-optimality in O(log(1/ε)) iterations
- First limiting-behavior and rate analysis for this common RL strategy
Full article110 words · extracted from arxiv.org · click to collapse
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 $\mathcal{O}(1/\varepsilon^p)$ iterations to an $\varepsilon$-optimal policy, where the exponent $p$ depends on problem data. For single-period MDPs, such a policy is obtained within $\mathcal{O}(\log(1/\varepsilon))$ iterations.
Text extracted automatically; images, tables and formatting may be missing. Original: https://arxiv.org/abs/2610.03642