研究证明 Success Conditioning 在一类 MDP 上收敛于最优策略
On the Convergence of Success Conditioning for Policy Optimization
如果你做强化学习，这篇把平时凭感觉用的 success conditioning 给了收敛证明和速率，折扣 MDP 和单期 MDP 分别给了 O 界，理论党可以细看。
这篇论文研究强化学习中常用的 Success Conditioning 策略，即在随机环境中提高产生成功结果动作概率的更新方法。作者证明该方法在广泛类别的马尔可夫决策过程（MDP）上收敛到最优策略。针对折扣 MDP，论文给出 O(1/ε^p) 次迭代内达到 ε-最优策略的收敛速率；针对单期 MDP，则为 O(log(1/ε)) 次迭代。
On the Convergence of Success Conditioning for Policy Optimization
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.
