acceptodds
Under review as a conference paper at ICLR 2027

Nash Rejection Sampling: From Max–Min Games to On-Policy Optimization for Nash Learning from Human Feedback

Abstract

Reinforcement learning from human feedback (RLHF) is successful for large language models alignment, but the approaches commonly assume that human preferences admit a transitive Bradley–Terry representation. This assumption may fail for non-transitive preferences. Nash learning from human feedback (NLHF) addresses such general preferences by seeking a Nash equilibrium of the two-player constant-sum game induced by the preference relation. Existing approaches typically either require costly alternating updates, or adopt identity preference optimization (IPO)-style objectives. We introduce Nash Rejection Sampling (Nash-RS), an on-policy optimization framework that reduces NLHF to a standard RLHF-style policy-gradient problem. At each iteration, Nash-RS uses current-policy responses and preference feedback to rejection-sample opponents from a reference policy, yielding a distribution that provide implicit scalar rewards for the same on-policy rollouts. Consequently, Nash-RS can directly reuse existing on-policy RLHF algorithms, including PPO, while avoiding a max–min optimizer and its associated nested game updates. Compared with IPO-style approaches, Nash-RS performs on-policy updates. Theoretically, we establish linear last-iterate convergence of the exact update to the regularized Nash equilibrium, while the practical implementation approximates this update using finite rejection samples and neural policy optimization. Experiments across multiple preference datasets and language-model families compare Nash-RS with method-native NLHF baselines, demonstrating competitive performance.

Primary area:
reinforcement learning
Keywords:
NLHF, Policy Optimization

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_ZGMGOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper proposes Nash rejection sampling (Nash-RS) for Nash learning from human feedback (NLHF) that accommodates potentially non-transitive preferences without assuming a Bradley–Terry reward model. Theoretically, it shows that the KL-regularized two-player max–min preference game can be reduced to a single concave maximization problem by analytically proving that the opponent's optimal response takes the form of a Gibbs distribution. The gradient of the resulting objective can then be expressed as a standard policy gradient with an implicit scalar reward. The author(s) next proposes to use rejection sampling to approximate the Gibbs opponent, allowing standard on-policy optimization algorithms such as PPO to be applied without training a separate adversarial policy. They further establish linear convergence guarantees to the Nash equilibrium. Experiments on UltraFeedback and PKU-SafeRLHF show that Nash-RS outperforms the several baselines algorithms in pairwise preference comparisons.

Critical strengths

I see three main strengths of this paper: (i) a novel rejection-sampling procedure for implementing Nash learning from human feedback, together with its integration into PPO; (ii) linear convergence guarantees for the policy update; and (iii) promising empirical results demonstrating the proposal's competitive performance against existing state-of-the-art algorithms.

Critical weaknesses

The theoretical results are mathematically elegant. However, the paper does not adequately clarify what is genuinely new over existing NLHF theory. For instance, EGPO already exploits the Gibbs fixed-point characterization of the regularized Nash equilibrium, raising questions about the novelty of the Gibbs best-response characterization derived in this paper. As another example, EGPO already establishes linear last-iterate convergence to the same regularized Nash equilibrium, as the author(s) acknowledges. Although the paper establishes linear convergence for a different update rule, it is not sufficiently clear what theoretical advantages it offers. In fact, it seems EGPO's convergence guarantee has a more favorable dependence on the regularization parameter as it approaches zero.

For the experiments, some of the improvements are quite small. On UltraFeedback, Nash-RS achieves an average win rate of 0.523±0.0050.523\pm0.005, compared with 0.518±0.0050.518\pm0.005 for Reward-PPO. Its direct win probability against Reward-PPO is only 0.5040.504. Similarly, the pairwise win rate against EGPO are 0.5230.523 on UltraFeedback and 0.5200.520 on PKU-SafeRLHF.

Moreover, the experiments do not adequately isolate the contribution of rejection sampling. It is true that the author(s) compare against EGPO and Nash-MD, but these algorithms differ in several other aspects beyond their opponent-sampling strategies. For instance, Nash-RS uses PPO, whereas EGPO uses IPO in the implementation.

Finally, I would encourage the authors to include comparisons with DPO-based methods, such as rDPO and Dr. DPO, which are omitted from the experiments.

Questions for authors

Please refer to Weaknesses.

2 comments

We thank the reviewer for the questions and comments.

W1. the paper does not adequately clarify what is genuinely new over existing NLHF theory … it seems EGPO’s convergence guarantee has a more favorable dependence on the regularization parameter as it approaches zero.

A. The main theoretical contribution is linear convergence for a different type of algorithms. As it it stated, both NashRS and EGPO provide linear convergence for NLHF, but EGPO establishes linear convergence for IPO-type algorithms, and Nash-RS establishes linear convergence for RL-type algorithms. These are different optimization frameworks, and EGPO’s guarantee does not directly apply to our update. Similar to RL/DPO for RLHF, guarantee of RL/IPO for NLHF are both important for NLHF theory.

As for the use of Gibbs, the only similarity is that both NashRS and EGPO use the Gibbs map. However, their role differs. EGPO uses a damped predictor within an extragradient update, whereas Nash-RS uses the full Gibbs best response as the opponent defining the gradient of the reduced scalar objective. Rejection sampling makes this opponent accessible for implicit-reward RL updates. Our contribution is this connection between the Gibbs response, scalar-reward policy optimization, and sampling.

W2. some of the improvements are quite small. On UltraFeedback, Nash-RS achieves an average win rate of 0.523 ± 0.005, compared with 0.518 ± 0.005 for Reward-PPO. Its direct win probability against Reward-PPO is only 0.504. Similarly, the pairwise win rate against EGPO are 0.523 on UltraFeedback and 0.520 on PKU-SafeRLHF.

A. We ran two new sets of experiments for this concern; the table are provided in our response to Reviewer k2oa, Q3.

  • Independent evaluators (reward models not used in training):
    • On UltraFeedback (paper seed 47), Nash-RS has the highest average win rate under both Skywork-V2-8B (0.547) and ArmoRM-8B (0.551), and is the only method with worst-case win rate above 0.5.
    • In that seed, the head-to-head win rate against Reward-PPO rises from 0.504 under the training oracle to 0.525 (Skywork) and 0.577 (ArmoRM). Against EGPO it is 0.538 (Skywork) and 0.550 (ArmoRM).
    • On PKU-SafeRLHF, the independent Beaver cost model gives the same ranking as the training oracle.
  • Multiple seeds:
    • On PKU-SafeRLHF, Nash-RS has the highest average win rate in all 3 seeds: 0.518 ± 0.001, versus 0.501 ± 0.002 for Nash-MD and 0.493 ± 0.002 for EGPO. It beats Nash-MD (0.512) and EGPO (0.519) head-to-head in every seed. Given a seed-to-seed std of 0.001–0.003, these small-looking gaps are highly consistent.
    • On UltraFeedback, Nash-RS beats EGPO and MPO in both seeds where they were trained (0.517–0.530).
    • Against Reward-PPO, we are explicit that the comparison is close to a tie. Across 3 seeds × 3 evaluators, Nash-RS wins 6 of 9 head-to-head comparisons (mean 0.519; 0.496 under the training oracle, 0.506 under Skywork, 0.554 under ArmoRM). The consistent difference is elsewhere: Nash-RS improves on the initial policy in all 9 seed × evaluator cells, whereas Reward-PPO falls below the initial policy under ArmoRM in 2 of 3 seeds (k2oa-3).

Context for the effect sizes. Win rates in the 0.52–0.53 range are typical for this evaluation protocol: all policies are close to the same reference policy with KL regularization at τ = 0.5, and the comparison is pairwise against strong baselines. On PKU-SafeRLHF, the independent Beaver cost model gives the same ranking as the training oracle (k2oa-3).

W3. the experiments do not adequately isolate the contribution of rejection sampling ... For instance, Nash-RS uses PPO, whereas EGPO uses IPO in the implementation.

A. Thanks for the question. First, we would like to clarify the role of rejection sampling in Nash-RS. Unlike standard RS that was used for selecting training-data, our rejection sampling step are used to provide an unbiased implicit reward in our RL formulation. Then, “PPO+RS” are coupled in the designed of algorithms.

For ablation, an “IPO + RS” variant would not be well-defined. When using IPO, we don’t have an implicit reward, thus we don’t need to use RS to estimate the reward. On the other hand, an “PPO+non-RS” would be well-defined, but not theoretical grounded. It is because it will not provided an unbiased estimation of implicated reward. Nevertheless, the non-RS variant is an informative control for the reviewer’s question: does the Gibbs-opponent construction provide an additional benefit when the PPO pipeline is held fixed?

We ran a controlled ablation (Qwen2.5-3B / UltraFeedback). We only change the opponent distribution.

  • Reference opponent: πref\pi_{\mathrm{ref}}, all accepted (no rejection step).
  • Current-policy opponent: πϕ\pi_\phi (PPO self-play).
  • Gibbs opponent (Nash-RS): πG\pi^{\mathrm G} via Algorithm 1.
Opponent (same PPO pipeline)avg. win rateworst-case win rateNash-RS wins head-to-headvs initial
Reference samples (no rejection)0.503 ± 0.0050.4830.5170.510
Current-policy samples (PPO self-play)0.516 ± 0.0050.4960.5040.522
Gibbs / rejection sampling (Nash-RS)0.521 ± 0.0050.504—0.526

With PPO held fixed, removing rejection lowers the average win rate from 0.521 to 0.503, and Nash-RS wins their direct comparison at 0.517. The gain over PPO self-play is smaller: 0.521 versus 0.516, with a head-to-head win rate of 0.504. These results support an additional contribution from the Gibbs-opponent construction in this run.

The PPO self-play variant also substantially outperforms the TRL self-play baseline, which scores 0.489 in the same evaluation population. This supports the reviewer’s concern that the training pipeline contributes to the cross-method differences. We will therefore avoid attributing the entire advantage over the original baselines to rejection sampling.

Computational cost. This ablation matches training steps and opponent counts, not compute. The reference-opponent variant requires 8.2K preference-model calls and 6.95 sampling GPU-hours, compared with 52K calls and 13.1 GPU-hours for Nash-RS. The measured improvement therefore comes with additional sampling cost.

W4. I would encourage the authors to include comparisons with DPO-based methods, such as rDPO and Dr. DPO, which are omitted from the experiments.

A. We added DPO, rDPO (Chowdhury et al., 2024) and Dr. DPO (Wu et al., 2024) on Qwen2.5-3B / UltraFeedback.

Setup,

  • All three methods use full-parameter training, β = 0.1, learning rate 5e-7, 2 epochs and batch size 32. They differ only in the loss:
    • rDPO uses label-noise rate ε = 0.1;
    • Dr. DPO uses β′ = 1.
  • They are evaluated in the same population, with the same protocol and test prompts.
Methodavg. win rate (13-policy population)Nash-RS wins head-to-head
DPO0.494 ± 0.0030.525
rDPO0.491 ± 0.0030.528
Dr. DPO0.488 ± 0.0040.531
Nash-RS0.521 ± 0.005—

With the same prompts and the same preference oracle, Nash-RS beats each of them head-to-head (0.525–0.531).

  • These methods are offline and learn from one fixed pair per prompt. Nash-RS instead queries the oracle on fresh on-policy samples throughout training.
  • Because of time limits, we used a single standard hyperparameter setting for each method and did not tune them further.

Conceptual difference. DPO-type methods assume a Bradley–Terry-style link between preferences and an implicit reward, with added robustness to label noise (rDPO) or to pairwise-data perturbations (Dr. DPO). Nash-RS targets the Nash equilibrium of a general, possibly intransitive, preference model.

The revision adds these baselines to the new experiments appendix (they are evaluated in a different, 13-policy population, so we keep them out of Table 2) and discusses them in the related-work appendix (Appendix G).

Reviewer_k2oaOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes Nash Rejection Sampling (Nash-RS) for KL-regularized Nash Learning from Human Feedback (NLHF). By deriving the closed-form Gibbs best response of the inner opponent, the authors reduce the original max-min problem to a single-policy concave optimization problem. The resulting gradient admits a standard score-function representation with an implicit reward, allowing the use of existing on-policy RLHF algorithms such as PPO. In practice, Nash-RS approximates the Gibbs opponent through rejection sampling from the reference policy. The authors establish linear last-iterate convergence for the exact policy-space update and evaluate the method on UltraFeedback with Qwen2.5-3B and PKU-SafeRLHF with Gemma-2-2B. The reported results show competitive pairwise win rates against several NLHF baselines.

Critical strengths
  1. The reduction to single-policy optimization is a useful contribution. The closed-form Gibbs best response provides a clear interpretation of the implicit reward and enables the use of standard policy-gradient methods for NLHF. This offers a relatively simple way to optimize an otherwise more complicated game-theoretic objective (pp. 4–5).
  2. The theoretical analysis provides a useful convergence guarantee. The authors prove linear last-iterate convergence in KL divergence to the unique regularized Nash equilibrium for the exact policy-space mirror update. The analysis is supported by relative smoothness and relative strong-convexity arguments in the appendix (pp. 4–5, 18–19).
  3. The empirical results are encouraging across different preference settings. The experiments cover two datasets and two language model families. In the reported pairwise comparisons, Nash-RS is the only method whose worst-case win rate exceeds 0.5 against all other baselines, with more noticeable improvements on PKU-SafeRLHF (p. 9).
Critical weaknesses
  1. The theoretical analysis does not fully cover the practical rejection-sampling procedure. In Algorithm 1, the acceptance probability depends on a finite-sample estimate of P(π≻y′)P(\pi \succ y'), which is subsequently exponentiated. Because of this nonlinear transformation, the distribution of accepted samples is generally not identical to the Gibbs distribution in Eq. (3.2) for finite B1B_1. Appendix B considers stochastic gradient errors under assumed bias and variance bounds, but it does not establish that the proposed estimator satisfies these assumptions. In particular, no explicit error bounds in terms of B1B_1 and B2B_2 are provided. This leaves an important gap between the convergence analysis and the implemented algorithm (pp. 6, 19).
  2. Some of the empirical gains are small, and their robustness is not sufficiently established. On UltraFeedback, Nash-RS achieves a win rate of only 0.504 against Reward-PPO, while their average win rates are 0.523 ± 0.005 and 0.518 ± 0.005, respectively. Without multiple training runs or further uncertainty analysis, it is difficult to determine whether these differences are consistent. The reported zero empirical exploitability may also be sensitive to evaluation noise, particularly when the same preference oracle is used for evaluation (p. 9).
  3. The computational cost of rejection sampling requires further investigation. The acceptance rate can become small as the temperature parameter τ\tau decreases, potentially increasing the number of samples required. However, the temperature and sampling-cost ablation is conducted only on a 0.5B model. It remains unclear how this trade-off affects the efficiency of Nash-RS at the model scales used in the main experiments (p. 21).
Questions for authors
  1. Can the authors characterize the bias introduced by exponentiating the finite-sample estimate of P(π≻y′)P(\pi \succ y')? In particular, is it possible to derive an error bound between the accepted-sample distribution and the target Gibbs distribution as a function of B1B_1?
  2. How do the bias and variance assumptions in Appendix B relate to the rejection-sampling estimator used in Algorithm 1? Are there conditions under which the stochastic convergence results remain applicable to the practical implementation?
  3. How stable are the reported pairwise win rates across different training seeds or independent preference evaluators? This is particularly relevant to the relatively small improvement over Reward-PPO on UltraFeedback.
  4. What is the rejection acceptance rate, and how does the total sampling cost vary with τ\tau for the 2B and 3B models used in the main experiments?
4 comments

We thank the reviewer for the questions and comments.

W1, Q1. In Algorithm 1, the acceptance probability depends on a finite-sample estimate of P(π ≻ y′)… In particular, is it possible to derive an error bound between the accepted-sample distribution and the target Gibbs distribution as a function of B1B_1?

A. We give an explicit bound, an exact variant that removes the bias with the same expected number of preference queries, and direct measurements at our model scales.

Fix a prompt and policy, and write g(y′)=P(π≻y′)g(y')=\mathcal P(\pi\succ y'). Algorithm 1 shares one batch of B1B_1 policy samples across proposals. Conditional on this batch, accepted opponents follow

q^(y′)∝πref(y′)e−g^(y′)/τ,\hat q(y')\propto\pi_{\mathrm{ref}}(y')e^{-\hat g(y')/\tau},

with marginal distribution q=E[q^]q=\mathbb E[\hat q]. Proposition B.4 establishes

\leq \mathbb{E}\left[\mathrm{KL}(\hat{q} \Vert \pi^{\mathrm{G}})\right] \leq \frac{1}{2 B_1 \tau^2}.$$ Consequently, for fixed $y$, or a scored response generated independently of the sampler’s policy batch, $$\left|\mathbb E[\hat r'(y)]-r'(y)\right| \le\frac{1}{2\tau^2\sqrt{B_1}}.$$ Increasing $B_2$ reduces Monte Carlo variance but does not remove finite-$B_1$ bias. With exact independent Gibbs opponents, the per-response reward variance is at most $1/(4\tau^2B_2)$. With Algorithm 1, this bound applies conditionally on the shared policy batch; variation across batches remains. Exact alternative. For each proposal $y'$, draw $N\sim\mathrm{Poisson}(1/\tau)$, $N$ fresh responses $y_k\sim\pi$, and independent coins $Z_k\sim\mathrm{Bernoulli}(\mathcal P(y_k\succ y'))$. Accept iff all coins are zero. Then $$\Pr(\mathrm{accept}\mid y') =\mathbb E[(1-g(y'))^N] =e^{-g(y')/\tau}.$$ This gives exact Gibbs samples. At $\tau=0.5$, it uses two preference queries per proposal in expectation, matching $B_1=2$, but requires additional policy generations. We include it as Algorithm $1'$. **Measured bias.** We constructed (32\$\times\$32) preference matrices from policy/reference responses. We computed the Gibbs target on this finite response model and estimated (q) using 4,000 draws of the shared policy batch. Results below use (B_1=2,\tau=0.5), where the theoretical KL upper bound is 1. | Model / data | Policy | $\mathrm{KL}(q \Vert \pi^{\mathrm{G}})$ | $\mathbb{E}[\mathrm{KL}(\hat{q} \Vert \pi^{\mathrm{G}})]$ | TV | Relative implicit-reward bias | | --- | --- | --- | --- | --- | --- | | Gemma-2-2B / PKU | SFT initialization | $6.0\times10^{-5}$ | 0.028 | 0.004 | 0.36% | | Gemma-2-2B / PKU | Trained Nash-RS | $6.4\times10^{-5}$ | 0.029 | 0.004 | 0.33% | | Qwen2.5-3B / UF | Initialization | $5.8\times10^{-9}$ | $2.1\times10^{-5}$ | $<10^{-4}$ | <0.01% | | Qwen2.5-3B / UF | Trained Nash-RS | $4.6\times10^{-9}$ | $1.7\times10^{-5}$ | $<10^{-4}$ | <0.01% | Bias is small in this probe at the training setting. It becomes substantial at smaller temperatures: on Gemma with (\tau=0.1,B_1=2), KL is 0.049 and relative reward bias is 22%. > *Q2. “How do the bias and variance assumptions in Appendix B relate to the rejection-sampling estimator used in Algorithm 1? Are there conditions under which the stochastic convergence results remain applicable to the practical implementation?”* A. For the policy-space update, the gradient error is $$e_t(y)=-(\hat r'_t(y)-r'_t(y)).$$ Since both rewards lie in $[0,1/\tau]$, $V_t\le1/\tau^2$. Let $L=1+\tau^{-2}$ and $D_0=\mathrm{KL}(\pi^\star|\pi_0)$. Exact sampler: $b_t=0$. With $\gamma_t=2/(t+c)$, $c\ge4L$, Proposition B.3 gives $$\mathbb {E}\left[\mathrm{KL}(\pi^\star|\pi_T)\right] \le \frac{\max\\{(c-1)D_0,4/\tau^2\\}}{T+c-1}.$$ Algorithm 1 with finite $B_1$: Proposition B.4 gives $b_t\le1/(2\tau^2\sqrt{B_1})$. For constant $0<\gamma\le(2L)^{-1}$, $$\mathbb{E}\left[\mathrm{KL}(\pi^\star|\pi_T)\right] \le (1-\gamma)^T D_0 +\frac{1}{\tau^2\sqrt{B_1}} +\frac{\gamma}{\tau^2}.$$ Thus the bound contracts geometrically to a neighborhood controlled by sampling bias and step size. These results assume fresh sampler randomness at each iteration. The sampled-response reward bound additionally requires independence from the sampler’s policy batch. The guarantees concern the policy-space update; they do not establish convergence of neural PPO.

W2, Q3. “Some of the empirical gains are small, and their robustness is not sufficiently established. On UltraFeedback, Nash-RS achieves a win rate of only 0.504 against Reward-PPO … The reported zero empirical exploitability may also be sensitive to evaluation noise, particularly when the same preference oracle is used for evaluation.”“How stable are the reported pairwise win rates across different training seeds or independent preference evaluators?”

A. We used three training seeds and evaluations using models not used in training. We distinguish prompt-bootstrap uncertainty from variation across training seeds.

Independent evaluators.

On UltraFeedback, we rescored the same greedy responses on test prompts. Parentheses show worst-case win rates.

EvaluatorNash-RS avg. (worst)Reward-PPO avg. (worst)Nash-RS vs. Reward-PPOBest other avg.
Training oracle0.523 (0.504)0.518 (0.496)0.5040.496 (EGPO)
Skywork-Reward-V2-Llama-3.1-8B0.547 ± 0.023 (0.525)0.530 ± 0.024 (0.475)0.5250.505 (Nash-MD)
ArmoRM-Llama3-8B0.551 ± 0.024 (0.538)0.462 ± 0.023 (0.423)0.5770.510 (initial)

Nash-RS ranks first under both independent evaluators in this seed. We treat zero empirical exploitability as a point estimate within the tested population, not a certificate of equilibrium.

On PKU-SafeRLHF, Beaver-7B also ranks Nash-RS first: average win rate (0.516\pm0.007), worst-case 0.513, and head-to-head win rates 0.513–0.521. This score improvement does not imply uniformly better safety: its Beaver unsafe rate is 4.83%, versus 4.16% for the initial policy ((p<0.001)); we report this trade-off separately.

Training seeds. Seeds 47, 101, and 211 vary prompt order, rollout sampling, and oracle answer-order randomization. Comparisons use matched policy populations.

PKU-SafeRLHF / Gemma-2-2B:

MetricSeed 47Seed 101Seed 211Mean ± std
Nash-RS avg. win rate0.5180.5160.5190.518 ± 0.001
Nash-MD avg. win rate0.5010.5030.4990.501 ± 0.002
EGPO avg. win rate0.4930.4910.4950.493 ± 0.002
Initial avg. win rate0.4880.4900.4880.489 ± 0.001
Nash-RS worst-case win rate0.5110.5090.5150.512 ± 0.003
Nash-RS vs. Nash-MD0.5110.5090.5150.512
Nash-RS vs. EGPO0.5200.5190.5170.519

Nash-RS ranks first and has head-to-head point estimates above 0.5 against every comparator in all three seeds.

UltraFeedback / Qwen2.5-3B:

ComparisonSeed 47Seed 101Seed 211Mean ± std
Nash-RS vs. initial0.5260.5160.5220.522 ± 0.005
Reward-PPO vs. initial0.5230.5100.5420.525 ± 0.016
Nash-RS vs. Reward-PPO0.5040.5060.4790.496 ± 0.015

The comparison with Reward-PPO is mixed: the small seed-47 advantage does not persist across all seeds.

UltraFeedback; separate five-policy:

MetricSeed 47Seed 101
Nash-RS avg. win rate (rank)0.521 (1st)0.514 (1st)
Reward-PPO avg. win rate0.5160.506
EGPO / MPO avg. win rate0.492 / 0.4830.493 / 0.493
Nash-RS vs. EGPO / MPO0.523 / 0.5300.517 / 0.517
Nash-RS worst-case win rate0.5040.505

Nash-RS outperforms EGPO and MPO under the training oracle in both tested seeds. This is not uniform across evaluators: on seed 101, Skywork slightly favors EGPO over Nash-RS (0.508).

Independent evaluation across all three seeds.

ComparisonEvaluatorSeed 47Seed 101Seed 211Mean
Nash-RS vs. Reward-PPOTraining oracle0.5040.5060.4790.496
Skywork-V2-8B0.5250.5090.4850.506
ArmoRM-8B0.5770.4950.5900.554
Nash-RS vs. initialTraining oracle0.5260.5160.5220.522
Skywork-V2-8B0.5580.5040.5530.538
ArmoRM-8B0.5380.5190.5470.535
Reward-PPO vs. initialTraining oracle0.5230.5100.5420.525
Skywork-V2-8B0.5280.4990.5540.527
ArmoRM-8B0.4590.5050.4730.479

Nash-RS improves over the initial policy in all nine seed–evaluator point estimates, while its comparison with Reward-PPO depends on both seed and evaluator.

W3, Q4. “The computational cost of rejection sampling requires further investigation… and how does the total sampling cost vary with τ for the 2B and 3B models used in the main experiments?”

A. We report actual training counts and an offline temperature sweep on both model scales. Sampling cost is quantified by reference-proposal counts and preference-model calls.

Actual training runs. All runs use B1=B2=2B_1=B_2=2. Acceptance is pooled over acceptance tests. Proposals per retained opponent include unused responses generated in proposal batches, so this quantity need not equal the reciprocal acceptance rate.

Runτ\tauAcceptance rateReference proposals per retained opponentPreference-model calls, total
Qwen2.5-3B / UF, seed 470.50.373.452K
Qwen2.5-3B / UF, seed 1010.50.383.363K
Qwen2.5-3B / UF, seed 470.250.157.6132K
Gemma-2-2B / PKU, seed 1010.50.394.6657K

For Qwen seed 47, halving τ\tau from 0.5 to 0.25 increases preference-model calls by 2.54×2.54\times. At the default τ=0.5\tau=0.5, measured acceptance is 0.37–0.39 across these runs, above the lower bound e−2≈0.135e^{-2}\approx0.135.

Offline temperature sweep. Using the finite-response probe described in Q1, we hold trained checkpoints fixed and vary only the sampling temperature. Acceptance is computed using the implemented rule e−g^/τe^{-\hat g/\tau}, with B1=2B_1=2.

τ\tau0.10.250.512
Acceptance, Gemma-2-2B / PKU0.150.270.430.620.78
Acceptance, Qwen2.5-3B / UF0.0060.120.340.580.76
Lower bound e−1/τe^{-1/\tau}4.5×10−54.5\times10^{-5}0.0180.1350.370.61
Expected proposals per prompt, Gemma157.74.73.22.6
Expected proposals per prompt, Qwen378175.93.42.6

Proposal counts estimate the cost of collecting two opponents without batching overhead. Expected cost averages the reciprocal acceptance rate over prompts and policy batches; it need not equal two divided by the mean acceptance. These are fixed-checkpoint sampling estimates, not measurements from retraining at every temperature. At τ=0.1\tau=0.1, this probe requires approximately 378 proposals per prompt for Qwen, versus 15 for Gemma.

Finally, τ\tau also changes the target equilibrium. In the seed-47, 13-policy evaluation of the actual Qwen training runs, τ=0.25\tau=0.25 achieves an average win rate of 0.509±0.0050.509\pm0.005, versus 0.521±0.0050.521\pm0.005 at τ=0.5\tau=0.5 (95% prompt-bootstrap half-widths). Its head-to-head win rate against the τ=0.5\tau=0.5 policy is 0.489. Thus, in this run, the smaller temperature incurs more preference queries without improving the win-rate estimate.

I appreciate the authors' response which help clarify some concerns and maintain my positive rating.

Reviewer_k7DLOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper introduces Nash-RS a new algorithm for preference optimization with general preferences oracle, that is without assuming a scalar reward based model such as Bradley-Terry which forces the preferences to be transitive. Their algorithmic idea is simple and elegant at the same time: the minmax problem can be reduced to a single maximization problem by exploiting the fact that for one player a closed form solution is available. This method Nash-RS has favourable convergence properties: when the gradient is known, a linear rate of order (1+τ2)−T(1 + \tau^2)^{-T} for the KL towards the unique equilibrium and a rate of (1+τ−2)(1+τ2)−T(1 + \tau^{-2})(1 + \tau^2)^{-T} for the Nash gap (suboptimality in function values) and a 1/T1/T rate for KL when the gradients are unbiased but with bounded variance.

While the closed form solution can be computed exactly in the tabular analysis, the same it is not true when looking at an implementation with neural networks. In this setting the authors suggest to use a rejection sampling routine to sample from the opponent best response. It is guaranteed that the rejection sampling routine outputs a valid sample within e1/τe^{1/\tau} attempts in expectation.

Finally, the experiments show that NAsh-RS achieve the highest winrates against the base model and other preference optimization methods such as Nash-MD, EGPO and MPO.

Critical strengths
  1. The algorithm is extremely elegant, the derivation is well explained.

  2. The empirical results are convincing and compare Nash-RS with a vast range of recent baselines.

Critical weaknesses

Presentation There are some presentation issues:

  1. the function F appears for the first time at line 207 without having been previous defined (unless I have missed it).
  2. In Table 2, the authors label Nash-MD as their algorithm while it is in fact Nash-RS.

Theory with noisy gradients Your result with noisy gradients require unbiased gradients. I think that unbiased gradients can be obtained following the steps of Algorithm 2 but this still require perfect knowledge of the preference model P\mathcal{P}. However, how does the estimation happens in practice in which the full preference matrix P\mathcal{P} is likely not known?

Missing related works I think that there are several recent work that are missing. I suggest the authors to make an additional pass looking for related work. I am here listing some out of my memory.

[1] Beyond Pessimism: Offline Learning in KL-regularized Games, Zhang et al. 2026

[2] Offline Two-Player Zero-Sum Markov Games with KL Regularization, Chen at al. 2026

[3] Multi-step alignment as markov games: An optimistic online mirror descent approach with convergence guarantees, Wu et al., 2025

[4] Direct Nash Optimization: Teaching Language Models to Self-Improve with General Preferences, Rosset et al. 2024

Questions for authors

Sometimes one might be interested in guaranteeing small Nash gap for the unregularized game. Can you comment on which is the rate for finding an approximate equilibrium for the unregularized game with your approach? I think it can be done by setting τ=ϵ\tau=\epsilon. This would give L=O(ε−2)L = \mathcal{O}(\varepsilon^{-2}) which seems to be the optimal rate.

2 comments

We thank the reviewer for the questions and comments.

W1. the function F appears for the first time at line 207 without having been previous defined.

A. Thank you for catching this. We now define the reduced objective F(π):=Z(π)−KL(π∥πref)F(\pi):=\mathcal Z(\pi)-\mathrm{KL}(\pi\Vert\pi_{\mathrm{ref}}) immediately after Theorem 2.1, before its first use.

W2. In Table 2, the authors label Nash-MD as their algorithm while it is in fact Nash-RS.

A. We now fixed the typo.

W3. Your result with noisy gradients require unbiased gradients. ... However, how does the estimation happens in practice in which the full preference matrix is likely not known?

A. Query access, rather than the full matrix, is sufficient. Algorithms 1–2 query preferences only for sampled pairs: the B1B_1 policy responses against each proposal, and the actor response against B2B_2 accepted opponents. Our experiments use the EGPO pair classifier on PKU-SafeRLHF and a reward-model mixture on UltraFeedback.

An exact alternative using noisy binary labels. Suppose fresh label queries satisfy E[Z∣y,y′]=P(y≻y′).\mathbb E[Z\mid y,y']=\mathcal P(y\succ y'). Given exact independent Gibbs opponents, replacing preference probabilities in Algorithm 2 by these labels preserves the unbiasedness of the implicit-reward estimate. Algorithm 1′1' in Appendix B.4 produces exact Gibbs opponents using the Poisson acceptance construction and independent binary-label queries.

With these sampling conditions, actor responses independent of the sampler’s auxiliary draws, and the step sizes specified in Proposition B.3, we obtain bt=0b_t=0, Vt≤1/τ2V_t\le1/\tau^2, and the O(1/T)O(1/T) expected-KL guarantee for the policy-space update. The original finite-B1B_1 sampler remains biased; Proposition B.4 quantifies this error. These results do not establish convergence of neural PPO. Preference-model misspecification. Assume that P^\widehat{\mathcal{P}} is a valid constant-sum preference model satisfying

\leq \varepsilon.$$ Let $\widehat{\pi}_{\star}$ and $\pi_{\star}$ denote the corresponding regularized equilibria. Since $$\sup_{\pi} \left\lvert F_{\widehat{\mathcal{P}}}(\pi)-F_{\mathcal{P}}(\pi) \right\rvert \leq \frac{\varepsilon}{\tau},$$ optimality and the objective-gap identity give $$\mathrm{KL}(\widehat{\pi}_{\star}\Vert\pi_{\star}) \leq F_{\mathcal{P}}(\pi_{\star}) - F_{\mathcal{P}}(\widehat{\pi}_{\star}) \leq \frac{2\varepsilon}{\tau}.$$ This quantifies the equilibrium shift caused by model error. Appendix B.4, Remark B.6, states these distinctions explicitly. > *W4. [1] Beyond Pessimism: Offline Learning in KL-regularized Games, Zhang et al. 2026; [2] Offline Two-Player Zero-Sum Markov Games with KL Regularization, Chen et al. 2026; [3] Multi-step alignment as markov games: An optimistic online mirror descent approach with convergence guarantees, Wu et al., 2025; [4] Direct Nash Optimization, Rosset et al. 2024.”* A. We have expanded the related-work discussion and clarify the connections. > *Q1. Can you comment on which is the rate for finding an approximate equilibrium for the unregularized game with your approach? I think it can be done by setting τ = ε. This would give L = 𝒪(ε⁻²) which seems the optimal rate.* A. Thank you for this helpful observation. You are correct that choosing the regularization parameter proportional to the target accuracy yields an $\widetilde{O}(1/\varepsilon^2)$ exact-iteration bound for the unregularized game. Below, we make the dependence on the reference policy explicit.The regularized guarantee can be converted into an unregularized guarantee by balancing regularization bias and optimization error. For a finite response space and a full-support reference policy, define $$D:=\max_y\log\frac{1}{\pi_{\mathrm{ref}}(y)}, \qquad \mathcal E_0(\pi):=\frac12-\min_{\pi'}\mathcal P(\pi\succ\pi').$$ Here $\mathcal E_0$ is unilateral exploitability; the conventional symmetric duality gap is $2\mathcal E_0$. Since $\mathrm{KL}(\pi'\Vert\pi_{\mathrm{ref}})\le D$, $$\mathcal E_0(\pi)\le\mathcal E_\tau(\pi)+\tau D.$$ With initialization $\pi_0=\pi_{\mathrm{ref}}$, Eq. (2.7) gives $$\mathcal E_\tau(\pi_T)\le\frac{L\kappa^T}{2}, \qquad L=1+\tau^{-2}, \qquad \kappa=(1+\tau^2)^{-1}.$$ Choosing $\tau=\varepsilon/(2D)$ and step size $1/L$ therefore ensures $\mathcal E_0(\pi_T)\le\varepsilon$ after $$T=O\left(L\log\frac{L}{\varepsilon}\right) =\widetilde O\left(\frac{D^2}{\varepsilon^2}\right)$$ exact policy-space iterations. For a uniform reference, $D=\log|\mathcal Y|$.

Thank you for your response.

I am happy to keep my (very) positive score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.