Success Conditioning as Policy Improvement: The Optimization Problem Solved by Imitating Success

Technical Summary: Success Conditioning as Policy Improvement

Problem Statement
Success conditioning is a widely adopted heuristic in reinforcement learning (RL) and post-training pipelines for large language models (LLMs). The method involves collecting trajectories, filtering for those that achieve a desired outcome (success), and updating a policy to imitate the actions taken along these successful trajectories. Despite its prevalence under various names—such as rejection sampling with supervised fine-tuning (SFT), goal-conditioned RL, and Decision Transformers—the theoretical optimization problem it solves has remained unclear. Unlike standard RL methods, success conditioning does not explicitly estimate value functions or compute policy gradients. Previous analyses suggested fundamental limitations, particularly in stochastic environments where it fails to recover optimal policies, yet it continues to be used effectively. The central question addressed is: If success conditioning does not recover optimal policies, what optimization problem does it actually solve, and what are its guarantees and failure modes?

Methodology and Formalization
The paper formalizes success conditioning within the framework of episodic Markov Decision Processes (MDPs).

• Setup: Trajectories $\tau$ are generated by a behavior policy $\pi_0$. Success is defined as a binary event $R(\tau)=1$.
• Target Policy: The success-conditioned policy $\pi^+$ is defined via Bayesian conditioning:
  $$\pi^+(a | s) = P_{\pi_0}(A_t = a | S_t = s, R(\tau) = 1)$$
  This policy represents the distribution of actions taken given that the trajectory eventually succeeded.
• Learning: In practice, $\pi^+$ is approximated by minimizing the next-action prediction loss (cross-entropy) on a dataset of successful trajectories.

Key Contributions and Theoretical Results

1. The Trust-Region Equivalence
The primary theoretical contribution is the proof that success conditioning is the exact solution to a specific trust-region policy optimization problem.

• Objective: It maximizes the first-order policy improvement term $L_{\pi_0}(\pi)$ (the expected advantage under the behavior policy).
• Constraint: The optimization is subject to a constraint on the $\chi^2$ divergence between the new policy and the behavior policy, weighted by the success-conditioned occupancy measure $d^+_{\pi_0}$.
• Radius: The radius of this trust region is not a hyperparameter chosen by the user but is automatically determined by the data. Specifically, the constraint radius equals the aggregate action-influence of the behavior policy.
• Geometry: Unlike Trust Region Policy Optimization (TRPO) or Proximal Policy Optimization (PPO), which use Kullback-Leibler (KL) divergence, success conditioning uses $\chi^2$ divergence. This geometry is more conservative: it heavily penalizes assigning probability to actions that were rare under the behavior policy (exploration is "expensive"), but it permits concentrating probability mass on actions that were already well-supported (forgetting is "cheap").

2. The Action-Influence Identity
The paper establishes a remarkable identity linking three quantities at every state $s$:

1. Relative Advantage: The relative improvement in success probability provided by $\pi^+$.
2. Policy Change: The magnitude of the policy shift measured by $\chi^2$ divergence.
3. Action-Influence ($I_{\pi_0}(s)$): A metric measuring the variability in success rates induced by the stochastic action selection of the behavior policy.

Mathematically, for the success-conditioned policy $\pi^+$:
$$\frac{A_{\pi_0}(s, \pi^+)}{V_{\pi_0}(s)} = \chi^2(\pi^+(\cdot|s) \| \pi_0(\cdot|s)) = I_{\pi_0}(s)$$
This identity implies that the extent of policy change is exactly equal to the potential for improvement. If the behavior policy's action selection does not significantly influence the outcome (low action-influence), the policy will not change.

3. Characterization of Failure Modes
The paper reinterprets the known limitations of success conditioning.

• Conservative Improvement: Success conditioning is a conservative operator. It cannot degrade performance or induce dangerous distribution shifts because it is constrained by the observed data's action-influence.
• Observable Failure: When success conditioning "fails" to find an optimal policy (e.g., in the two-armed bandit example where success rates are nearly identical), it does so by barely updating the policy at all. The failure is one of over-conservatism, not instability. The policy remains close to the behavior policy because the data provides no signal that changing actions would improve success rates.

4. Dense Rewards and Proxy Criteria
The paper extends the analysis to settings with dense rewards via return thresholding (defining success as $Y > \theta$).

• Faithful vs. Proxy: A "faithful" binary reduction preserves the expected return objective. However, common practices like return thresholding act as proxy rewards.
• Trade-off: Conditioning on a proxy reward can amplify action-influence (and thus potential improvement) if the proxy is highly discriminative. However, if the threshold is set too high, the proxy may select for "lucky" trajectories with volatile outcomes rather than reliable actions. This leads to a misalignment between the proxy objective and the true evaluation objective, potentially degrading performance.

5. Relationship to Policy Gradients
The paper connects success conditioning to standard RL algorithms:

• REINFORCE: If the behavior policy is refreshed after every single update step ($N=1$ in an iterative scheme), the gradient of the success-conditioning loss is equivalent to the REINFORCE policy gradient.
• Off-Policy Nature: Standard success conditioning (training on a fixed dataset of successful trajectories) is off-policy. It defines a target policy based on a frozen behavior policy and fits it via supervised learning, rather than performing incremental gradient steps on the current policy.

Significance and Claims
The paper claims to provide a principled understanding of success conditioning, placing it in the same family as trust-region methods (TRPO, PPO) but with distinct geometric properties ($\chi^2$ vs. KL) and automatic radius determination.

• Safety: The theory guarantees that exact success conditioning will not degrade performance; its failure mode is benign (no change) rather than dangerous (distribution shift).
• Diagnostic Utility: The $\chi^2$ divergence between the learned policy and the behavior policy serves as a direct, ex-ante diagnostic for the magnitude of achievable improvement, requiring no new rollouts or reward labels.
• Limitations: The authors note that their analysis characterizes exact success conditioning under a fixed behavior policy. It does not address finite data effects, function approximation errors, or the convergence of iterated success conditioning, which are left as open directions.

In summary, the paper reframes success conditioning from a heuristic that "guesses" optimal actions to a rigorous, conservative optimization operator that maximizes improvement subject to the information content (action-influence) present in the observed data.