PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Convergence of Success Conditioning for Policy Optimization

Matthew Brun, Xu Andy Sun

arXiv:2610.03642v1cs.LGmath.OC

TL;DR

Success conditioning's convergence behavior and rates were not rigorously established. The paper analyzes it as an iterative policy optimization method and proves convergence to a restricted optimum, with explicit iteration bounds for single-period and discounted MDPs.

  • Problem

    SC had been treated mainly as a heuristic, leaving its limiting behavior and convergence rates without rigorous analysis.

    Source: §1 · pp. 1–2

  • Method

    The paper analyzes repeated success-conditioning updates for MDP policies and establishes their convergence under stated assumptions.

    Source: §1 · p. 2, §6 · p. 12

  • Results

    SC converges to a restricted optimal policy; it reaches ε-optimality in O(log(1/ε)) iterations for single-period MDPs and O(1/ε^p) for discounted MDPs, with p instance-dependent.

    Source: §1 · p. 2, §6 · p. 12

  • Takeaways & Limitations

    The results provide upper bounds on SC's worst-case performance, addressing open questions about its convergence behavior.

    Source: §6 · p. 12

    The convergence rates are worst-case upper bounds; SC may converge faster on typical instances.

    Source: §6 · p. 12

Abstract

from arXiv · show

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.

1 Introduction

Success conditioning (SC) is a policy update strategy, but its convergence behavior and rates had not been rigorously established. This work proves convergence to a restricted optimum and gives iteration bounds for single-period and discounted MDPs.

1 Introduction

  • SC had mainly been treated as a heuristic, and its convergence had remained an open question.Prior analysis of an equivalent update established asymptotic linear convergence for discounted MDPs but did not determine when that rate begins to apply.Source: §1 · pp. 1–2
  • The paper treats SC as an iterative policy optimization method and proves convergence to an optimum over actions supported by the initial policy.The limit is a restricted optimum: it is optimal on the set of actions supported in the initial policy.Source: §1 · p. 2
  • O(log(1/ε)) iterations suffice for single-period MDPs, while discounted MDPs require at most O(1/ε^p), with p depending on the instance.The paper gives explicit iteration complexities parametrized by the initial policy.Source: §1 · p. 2

2 Problem Description

The paper formulates policy optimization for finite MDPs, then defines and analyzes iterative success conditioning. It relates the update to conditional action distributions in a restricted binary-reward setting and defines the supported-action optimum toward which the values converge.

2 Problem Description

  • The MDP objective is to maximize expected cumulative reward, under assumptions that ensure finite, unique value-function solutions.The initial policy supplies the starting point for success conditioning; states with zero initial value can be removed, which prohibits optimizing the policy at those states.Source: §2 · pp. 2–3

2.1 The Success Conditioning Update

  • Success conditioning increases the probability of above-average-reward actions and decreases that of below-average actions; values and Q-values do not decrease under the update.The update requires positive state value, which follows from Assumption 1.Source: §2.1 · pp. 3–4

2.2 Motivation by Conditional Probability under Binary Rewards

  • With undiscounted binary terminal rewards, the updated policy is the action distribution conditioned on successful trajectories; general MDPs do not retain this conditional-distribution interpretation.Here success means receiving reward 1 at termination.Source: §2.2 · p. 4

2.3 Optimal Restricted Value Functions

  • The optimal restricted value functions optimize only over actions supported by the initial policy, and the SC value functions converge to these functions.Actions unsupported initially remain unavailable to every iterate.Source: §2.3 · p. 4

3 Limiting Behavior of Success Conditioning

Success conditioning converges in value to the optimal value functions over actions supported by the initial policy. Under Assumption 1, the limiting values satisfy the Bellman equations and equal the unique restricted optimum.

3 Limiting Behavior of Success Conditioning

  • The average of the ratios of value functions to value-iteration steps converges to one as the iteration count increases.The section analyzes these ratios as part of establishing convergence.Source: §3 · p. 5
  • The value sequences are increasing and bounded above by the optimal values, so they have limits.The proof also establishes that the relevant value and value-iteration-step sequences have limits.Source: §3 · pp. 5–6
  • Under Assumption 1, the limiting values satisfy the Bellman equations and are the unique restricted optimal value functions.The proof uses the Bellman equations to identify the limit with the unique solution.Source: §3 · p. 6
  • SC-generated policies converge in value to the optimal value functions over actions supported by the initial policy.The paper establishes this limiting behavior and then derives rates for particular MDP structures.Source: §3 · p. 6

4 Convergence Rate for Single-Period MDPs

For single-period MDPs, the paper derives convergence rates for success conditioning, a setting where the first action determines the infinite-horizon reward. It gives a logarithmic rate and an alternative reciprocal rate whose coefficient depends only on the initial policy.

4 Convergence Rate for Single-Period MDPs

  • A single-period MDP is a setting where the first action entirely determines the infinite-horizon reward.The paper identifies this structure with multi-armed bandit problems whose arm rewards are known exactly.Source: §4 · p. 6
  • O(log(1/ε)) iterations suffice for an ε-optimal policy in single-period MDPs.The coefficient can become arbitrarily large as the second-best action's value approaches the best action's value.Source: §4 · p. 6
  • O(1/ε) iterations also suffice, with a coefficient that depends only on the initial policy.This alternative rate avoids the coefficient's dependence on how close the second-best action is to the best.Source: §4 · p. 6

5 Convergence Rate for Discounted MDPs

For discounted MDPs, the paper derives an ε-optimality bound using approximate value iteration to analyze success-conditioning iterates. The iteration complexity is O(1/ε^p), with the exponent determined by problem data and a tunable parameter.

5 Convergence Rate for Discounted MDPs

  • O(1/ε^p) iterations suffice for an ε-optimal policy in discounted MDPs, with p determined by problem data and a tunable parameter.The theorem assumes Assumptions 1 and 2; the analysis also uses value functions in (0, 1], achievable by rescaling rewards.Source: §5 · pp. 7, 9
  • The rate proof treats blocks of SC iterations as approximate value-iteration steps and bounds the SC-to-AVI errors.The errors at selected indices are bounded before the overall error is controlled.Source: §5 · pp. 8–9
  • The exponent varies with discount factor γ and lower bound Φ: it increases with γ and decreases with Φ.The paper reports O(1/ε^p1) when γ is near 1 and Φ near 0, and O(1/ε^p2) when γ is small and Φ large.Source: §5 · p. 12
  • As γ approaches zero, the discounted-MDP rate tends to O(1/ε), slower than the single-period O(log(1/ε)) rate.The paper notes this may reflect key differences between the settings or a loose Theorem 3 rate near γ = 0.Source: §5 · p. 12

6 Discussion and Conclusion

The paper establishes convergence guarantees for success conditioning (SC), while emphasizing that its rates are worst-case bounds and can be slow. SC converges to an optimal solution within the actions supported by the initial policy, retaining stochastic policies and avoiding large changes in action distributions.

6 Discussion and Conclusion

  • For single-period MDPs, SC reaches an ε-optimal policy within O(log(1/ε)) iterations.For comparison, selecting the largest-reward action recovers an exact optimal policy in one iteration.Source: §6 · p. 12
  • For discounted MDPs, SC reaches an ε-optimal policy within O(1/ε^p) iterations, where p ≥ 1 depends strongly on problem data and may be arbitrarily large.The rates are upper bounds; typical instances may converge faster.Source: §6 · p. 12
  • SC is conservative: its policy changes correspond to performance improvements, while avoiding drastic changes in the action distribution.This conservatism can inhibit efficient convergence while permitting stability in learning.Source: §6 · p. 12
  • SC converges to a restricted optimal solution and cannot produce policies that take actions absent from the initial policy.Its convergence rates address open questions about SC, but are slow relative to comparable policy-optimization algorithms.Source: §6 · p. 12
  • SC retains non-zero probabilities on actions supported initially, so enough on-policy trajectories can visit all supported state-action pairs and permit Q-function estimates.Stochastic policies are desirable in some applications, including generative AI.Source: §6 · p. 12
  • Designing on-policy SC variants that estimate Q-functions from trajectory samples and studying their sample complexity remain open directions.The paper notes that such variants could be compared with TRPO and PPO, which require parameter tuning and generally lack well-understood convergence rates.Source: §6 · pp. 12–13

A Comparison to Reward-Weighted Regression

Prior work establishes a connection between reward-weighted regression (RWR) and success conditioning (SC), including equivalent updates and convergence under assumptions. This paper contrasts its explicit iteration-complexity bounds with an earlier asymptotic result whose threshold and coefficient are not characterized.

A Comparison to Reward-Weighted Regression

  • RWR and SC have equivalent updates, and RWR converges in the limit to an optimal policy under assumptions including strictly positive rewards and initial support for all state-action pairs.The comparison identifies these results as corresponding to SC convergence under a modified set of assumptions.Source: A Comparison to Reward-Weighted… · p. 15
  • The earlier RWR result gives a geometric bound only after iteration n, chosen when the incumbent-to-optimal Q-function gap is sufficiently small.The result does not characterize how large n must be, and its coefficient F may grow arbitrarily large with n.Source: A Comparison to Reward-Weighted… · p. 15
  • In contrast, this paper's Theorems 2 and 3 give explicit iteration complexities that quantify how many iterations guarantee an optimality-gap bound.The paper states that its complexities are parametrized by the initial policy.Source: A Comparison to Reward-Weighted… · p. 15
  • The earlier geometric rate depends on the ratio between the best and second-best action values, paralleling a ratio in the proof of Theorem 2.For single-period MDPs, Q-functions equal rewards and indicate the optimal actions at every iteration.Source: A Comparison to Reward-Weighted… · p. 15

Proof of Lemma 1

The proof uses monotonicity of the Bellman operator and a fixed-point property to establish monotonicity of the value and action-value sequences.

Proof of Lemma 1

  • Under Assumption 1, a fixed point of Bπ is the unique solution Vπ to the Bellman equations.The operator preserves component-wise monotonicity over states.Source: Proof of Lemma 1 · p. 16
  • Jensen’s inequality gives Bk+1Vk ⪰ Vk, and preservation of monotonicity extends this comparison to iterates.The proof also uses that the iterated sequence is bounded and non-decreasing, so it has a limit.Source: Proof of Lemma 1 · p. 16
  • The limit is a fixed point of Bk+1 and equals Vk+1, yielding Vk+1 ⪰ Vk and Qk+1(s, a) ≥ Qk(s, a).The stated action-value comparison applies for all s ∈ S′.Source: Proof of Lemma 1 · p. 16

Proof of Lemma 2

The proofs invoke Bellman-operator contractivity and assumptions to obtain a bound, while the Lemma 3 proof uses logarithm inequalities and Jensen’s inequality.

Proof of Lemma 2

  • Under Assumptions 1 and 2, V*(s) − V0(s) ≤ 1 for all s ∈ S, giving the stated result.The proof invokes standard Bellman-operator contractivity analysis.Source: Proof of Lemma 2 · p. 17

Proof of Lemma 3

  • When c > 0, define b′ := min{b, c} ∈ (0, 1); concavity of log(1 − x) bounds it by its tangent at x = 0, yielding log(1 − a) ≤ −a.Source: Proof of Lemma 3 · p. 17
  • The proof writes b′ as a convex combination of c and 0, then applies Jensen’s inequality.At x = 0, it takes log(1/(1 − x))/x = 1.Source: Proof of Lemma 3 · p. 17

Proof of Corollary 1

The proof handles two parameter regimes for B and uses the resulting bounds to establish an ε error bound for states in S′.

Proof of Corollary 1

  • In the case where 2γ ≥ Φ2(1 − γ), with B = (1 − γ)/2, the bound V*(s) − Vj(s) ≤ ε holds for all s ∈ S′ by Theorem 3.Source: Proof of Corollary 1 · p. 18
  • When 2γ < Φ2(1 − γ), the proof sets B = γ/Φ2 and C = 1.It again concludes V*(s) − Vj(s) ≤ ε for all s ∈ S′ by Theorem 3.Source: Proof of Corollary 1 · p. 18
  • In the second regime, the proof gives p = 1 − log(2) log(γ + γ/Φ2) = p2.It also invokes log(x) ≤ x − 1 for x ∈ R>0.Source: Proof of Corollary 1 · p. 18
Loading 2610.03642v1…