Self-Play with Adversarial Critic: Provable and Scalable Offline Alignment for Language Models

1 Introduction

• Popular alignment methods can fail to converge to the optimal policy when offline preference data has sparse coverage.Distribution shift in training data has also been identified as a factor in reward hacking.Source: §1 · pp. 1–2
• Existing pessimistic methods offer guarantees under single-policy concentrability, but prior approaches rely on linear assumptions or are computationally hard for general function approximation.Single-policy concentrability requires data coverage only where an optimal policy can visit.Source: §1 · p. 2
• SPAC formulates offline preference optimization as a Stackelberg game between a policy learner and a critic that maintains an on-average pessimistic reward estimate.The method is designed to converge under single-policy concentrability and scale to general function classes such as LLMs.Source: §1 · p. 2
• A change-of-variable trick yields a single-timescale direct preference optimization implementation that can be built on existing RLHF codebases.The implementation is closely connected to DPO.Source: §1 · p. 2
• The authors evaluate SPAC-aligned 7B models against popular baselines on Open LLM Benchmarks.The introduction describes the performance as competitive.Source: §1 · p. 2

Related Work

• Related work includes online alignment, self-play methods for LLM alignment, and offline RL approaches using adversarial critics and function approximation.Online alignment can request newly annotated preferences during training, a costly requirement in practice.Source: Related Work · p. 3

Offline RL

• For LLM alignment, the offline RL problem can be represented as a contextual bandit with prompts as states, responses as actions, and an unknown latent reward.A policy specifies response-selection probabilities for each prompt.Source: §2 · p. 4

Offline preference optimization

• The standard offline preference pipeline estimates reward from preferred and rejected response pairs, assuming preferences follow the Bradley-Terry model.The preference data are sampled from a reference policy, and reward estimation uses maximum likelihood over a function class.Source: §2 · p. 4
• Policy optimization maximizes the learned reward while KL regularization limits deviation from the reference policy.The regularizer can reduce exploitation of reward misestimation, but also restricts the policy from reaching the actual optimum.Source: §2 · p. 4
• DPO uses an analytical solution to combine reward learning with the RL optimization step.It is presented as an alternative to the standard two-step approach.Source: §2 · p. 4

3 Self-Play with Adversarial Critic (SPAC)

• The learner acts as Stackelberg leader, maximizing value predicted by the critic, while the critic acts as follower and performs on-average pessimistic evaluation relative to the learner’s policy.The critic also maximizes its log likelihood on the preference dataset.Source: §3 · p. 5
• An iterative self-play algorithm replaces the policy step with mirror descent to solve the bilevel formulation and is guaranteed to converge under single-policy concentrability.The actor and critic play simultaneously.Source: §3 · p. 5
• The theoretical algorithm has higher memory cost, an exponential weighting that cannot be computed exactly for language models, and potential two-timescale stability difficulties.It requires keeping a reward model alongside the policy at every iteration.Source: §3 · p. 5
• A change-of-variable rewrite produces an equivalent, more practical SPAC algorithm by expressing the update in a DPO-like form.The practical implementation no longer refers explicitly to the reward function class; that class is implicit in the policy class.Source: §3 · p. 6
• SPAC is closely related to DPO and SPIN and can be implemented in RLHF codebases that already support either method.The authors report that SPAC can outperform state-of-the-art alignment methods on LLMs.Source: §3 · p. 6

4 Theoretical Guarantees of SPAC

• SPAC’s guarantee is analyzed under realizable, bounded rewards and single-policy concentrability, a coverage condition focused on the optimal policy’s visitation over the induced function space.The paper notes that realizability is assumed for simplicity and that its theory can be modified for unrealizable settings.Source: §4 · pp. 6–7
• Popular preference optimization methods lack guarantees of finding the optimal policy without full data coverage, and KL regularization can keep the policy from reaching that optimum.The paper describes reward hacking as a phenomenon believed to be related to optimization exploiting poorly covered regions of the learned reward function.Source: §4 · p. 7
• The proof separates statistical error from policy-optimization error, bounding the former with concentration and the latter with regret analysis using reverse KL regularization.The statistical-error argument uses a change of measure and the mean value theorem; the optimization analysis is similar to Follow the Regularized Leader.Source: §4 · pp. 7–8
• Pointwise pessimism is computationally hard for neural networks and LLMs, whereas SPAC uses an on-average lower bound on reward under the learner’s policy.The paper presents this on-average approach as scalable to general function classes.Source: §4 · p. 8
• SPAC connects DPO and SPIN: its one-iteration, large-λ limit reduces to DPO, while λ approaching zero recovers SPIN.The paper says the DPO trick handles no-regret policy optimization without extra assumptions.Source: §4 · p. 8

5.1 Experimental Setup

• SPAC uses mistral-7b-sft-beta and 60K UltraFeedback Binarized prompt–chosen–rejected triplets, with preferences judged by GPT-4 for response quality.The base model is a SFT version of Mistral-7B-v0.1 trained on Ultrachat200k.Source: §5.1 · p. 9
• SPAC is run for three iterations, splitting UltraFeedback into equal subsets and generating one response per prompt in each iteration.The policy is optimized for two epochs per iteration.Source: §5.1 · p. 9
• The evaluation uses six Open LLM Leaderboard tasks to assess models across multitask, commonsense reasoning, inference, and subject-specific questions.The table caption identifies evaluations of SPAC and baselines based on mistral-7b-sft-beta.Source: §5.1 · p. 9, Table 1 · p. 9

5.2 Results and Analysis

• 4.37% average improvement over the base SFT model; SPAC’s improvement exceeds other baselines by a considerable margin across Open LLM Leaderboard tasks.The reported result follows three iterations; improvement becomes incremental and loss is near zero at the third iteration.Source: §5 · pp. 8–9, Table 1 · p. 9, §5.2 · p. 10
• SPAC improves over its initial SFT model by 2.95% on average after iteration one and performs better than or on par with DPO on five tasks, with a larger advantage on GSM8k.SPAC and SPIN are each reported to outperform DPO after iteration one while using one-third of the training data; SPIN’s performance then wavers or decreases across tasks, while SPAC generally continues improving with a few task-specific declines.Source: §5.2 · p. 10

6 Conclusion

• SPAC is presented as the first offline preference optimization method with provable convergence under single-policy concentrability and a scalable implementation for general function approximation.The conclusion attributes its single-timescale iterative self-play implementation to a change-of-variable trick.Source: §6 · p. 10
• Under single-policy concentrability, SPAC’s suboptimality decays at eO(1/T), ignoring logarithmic and constant factors.Source: §6 · p. 10
• The authors report competitive empirical performance after finetuning a 7B LLM and evaluating it on Open LLM Leaderboard.Source: §6 · p. 10

A Experiment Details

• Finetuning used four 80GB Nvidia A100s, batch size 32, sequence length 1024, bfloat16, and RMSProp with a peak learning rate of 5e-7.The evaluation appendix specifies six tasks and their shot counts and metrics, including 25-shot Arc with acc_norm and zero-shot TruthfulQA with mc2.Source: A Experiment Details · p. 16

B Additional Notation

• Additional notation covers total variation, KL and Bregman divergences, matrix-induced seminorms, and the comparison notation f(X) ≲ g(X).Source: B Additional Notation · p. 16

C Supporting Lemmas

• The supporting lemmas introduce martingale concentration results, including the Azuma-Hoeffding inequality.Source: C Supporting Lemmas · pp. 16–17

• Each SubOpt(πt) is decomposed into terms involving π⋆, πt, πref, and ft, and the proof bounds each term separately.Source: D Proof of Theorem 1 · p. 17
• The It,1 bound uses the coverage assumption and controls the reward-difference error between π⋆ and πref.Source: D Proof of Theorem 1 · p. 17
• The proof handles the remaining It,2 terms separately, using the algorithm’s minimization objective and concentration bounds.Source: D Proof of Theorem 1 · pp. 18–19
• log |F| and log |Π| differ only by a constant factor and are of the same order, yielding the advertised bound.Source: D Proof of Theorem 1 · p. 20

• The It,1 upper bound is controlled by MLE regularization in the algorithm’s objective.The subsection adapts results from Bhardwaj et al. (2023) and Zhan et al. (2024) to this setting.Source: §D.1 · p. 20
• Lemma 1 assumes every function in F is uniformly bounded by R > 0 and states a guarantee with probability at least 1 − δ.Source: §D.1 · p. 20
• A mean value argument for the sigmoid introduces the factor κ2 = 1/(infz∈[−R,R] σ′(z))2 in the bound.The argument compares preference probabilities under f with those under the true reward.Source: §D.1 · p. 20

• Lemma 2 gives a probability guarantee that holds for all f ∈ F simultaneously.Source: §D.1.1 · p. 21
• The proof follows a standard MLE argument, citing van de Geer (2000).Source: §D.1.1 · p. 21
• The proof uses sample independence, the Tower property, Markov’s inequality, and a union bound over the function class to reach the advertised bound.Source: §D.1.1 · p. 21

D.1.2 Lemma 3 and Its Proof

• Lemma 3’s guarantee holds simultaneously for all f ∈ F.Source: §D.1.2 · p. 21
• The Lemma 3 proof applies a Chernoff bound and a union bound over F to obtain its advertised probability bound.Source: §D.1.2 · p. 22

D.2 Bounding It,2 in Eq. (18)

• The sum of It,2 terms coincides with online-learning regret, whose bound depends on the no-regret policy update and follows policy mirror descent analysis.The lemma modifies Xie et al. (2021a) to accommodate an arbitrary initial policy in this setting.Source: §D.2 · pp. 22–23

D.2.1 Lemma 4 and Its Proof

• Lemma 4 is proved by induction, with the KL-divergence base case minimized when the distributions match.The inductive step invokes the hypothesis for the preceding value of T.Source: §D.2.1 · p. 23
• The proof identifies the policy as a global maximizer and notes a route paralleling FTRL, with DPO's analytical policy solution as the base case.The text says this argument can also be proven inductively following the FTRL proof.Source: §D.2.1 · p. 23

D.2.2 Lemma 5 and Its Proof

• Lemma 5's bound uses Lemma 4 and the non-positivity of ℓx(·).The passage identifies these as the justifications for the penultimate and final steps, respectively.Source: §D.2.2 · p. 24

D.2.3 Lemma 6 and Its Proof

• Lemma 6 uses Bregman-divergence properties and the global-maximizer condition to establish an inequality.The proof also notes that adding the linear term Lx,t(π) + ℓx(π) does not change the Bregman divergence.Source: §D.2.3 · p. 24
• The Lemma 6 derivation applies Taylor expansion, the mean value theorem, generalized Cauchy–Schwarz, Eq. (44), Eq. (45), and Assumption 1.It then invokes Lemma 5 and Eq. (47) in the remaining steps.Source: §D.2.3 · pp. 24–25