PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust Nash Alignment under Preference Uncertainty

Shihab Ahmed, Debamita Ghosh, David Tang, Yudan Wang, Alvaro Velasquez, Yue Wang

arXiv:2610.00715v1cs.AI

TL;DR

Preference-based alignment often relies on a fixed estimated preference kernel, even though preferences may be noisy, heterogeneous, or shift after deployment. Robust Nash Alignment optimizes worst-case performance over an ambiguity set and uses a four-player proxy game to address computational difficulty. The paper reports improved robustness across tabular and LLM settings while maintaining strong nominal performance.

  • Problem

    General-preference methods can represent cyclic and heterogeneous preferences, but treating an estimated preference kernel as fixed leaves alignment vulnerable to estimation errors and deployment shifts.

    Source: §1 · p. 2

  • Method

    Robust Nash Alignment optimizes worst-case game value over a divergence-based ambiguity set and uses a four-player primal-dual proxy for the hard-constrained objective.

    Source: §1 · p. 2

  • Results

    Experiments report improved robustness to preference perturbations across tabular and LLM settings while maintaining strong nominal performance.

    Source: §7 · p. 10

  • Takeaways & Limitations

    The robust objective lower-bounds alignment performance against every preference kernel in the ambiguity set.

    Source: §1 · p. 2

    The ambiguity set couples pairwise comparisons, making the problem computationally challenging; the analysis also assumes a floor-truncated policy simplex.

    Source: §3 · p. 4, §4 · p. 5

Abstract

from arXiv · show

Preference-based alignment methods typically optimize against a single preference model, and can therefore be brittle when pairwise preferences are uncertain: noisy, heterogeneous, or shift after deployment. To address these issues, we propose Robust Nash Alignment, a game-theoretic framework for alignment to uncertain pairwise preferences. Our formulation has a major learner seeking a policy with a large worst-case win rate against both an adversarial competitor and any preference kernel lying in an ambiguity set around a nominal preference. When the ambiguity set captures the uncertainty in preferences, the resulting robust objective of the game directly yields a certified lower bound on worst-case performance. However, we note this problem is computationally challenging to optimize, and to address this, we introduce a four-player primal-dual proxy game involving the leader policy, follower policy, adversarial kernel, and dual variable, and develop a single-loop optimistic mirror descent-ascent algorithm for it. We show that the proxy always lower-bounds the truncated hard-constrained objective, quantify the proxy-to-hard gap, and characterize an exactness condition under which the proxy recovers the robust objective. We then prove an \(\mathcal{O}(1/\sqrt{T})\) average-iteration convergence for the proxy-game duality gap, which implies a near-optimal robust policy for the original robust objective. Experiments on controlled tabular games and LLM alignment with uncertain preference further validate the convergence theory and show improved performance over nominal baselines.

1 Introduction

Pairwise preferences can be cyclic or heterogeneous, while finite, noisy, or shifting feedback makes a fixed preference kernel brittle. Robust Nash Alignment optimizes worst-case performance over plausible kernels and introduces a four-player proxy; experiments report improved robustness while maintaining strong nominal performance.

1 Introduction

  • Preferences may be cyclic or heterogeneous, and finite, noisy, biased, or shifting feedback can make a policy optimized for one estimated kernel brittle.A small kernel perturbation can reverse the dominance ordering when a policy's apparent advantage rests on margins indistinguishable from noise.Source: §1 · p. 2
  • The robust formulation maximizes worst-case game value over kernels in a divergence ball, lower-bounding win rates against every plausible kernel.Unlike standard NLHF, which uses one nominal kernel, the guarantee applies to kernels within the prescribed ambiguity set.Source: §1 · p. 2
  • A four-player primal-dual proxy avoids directly solving the hard-constrained problem and is analyzed for exactness, approximation, and convergence.Under stated exactness conditions, its convergence yields a certified worst-case game-value guarantee.Source: §1 · p. 2
  • Across tabular and LLM settings, the robust policy improves robustness to preference perturbations while maintaining strong nominal performance.The experiments also report better worst-case win rates than non-robust NashMD, better generalizability to external LLM judges on summarization, and better alignment under perturbed IMDb preferences.Source: §1 · p. 2

2 Preliminaries

The preliminaries contrast reward-based alignment, which models preferences through a latent scalar reward, with general-preference alignment, which treats pairwise probabilities directly. NLHF formulates the latter as a regularized minimax game.

2 Preliminaries

  • Bradley-Terry preference modeling represents pairwise preferences through an underlying scalar reward, which can be learned from comparison data and optimized with a KL-regularized RLHF objective.The passage identifies this formulation as underlying direct preference optimization.Source: §2 · p. 3
  • General-preference alignment treats pairwise preference probabilities as primitive rather than assuming they arise from a latent reward.Its preference oracle returns a Bernoulli outcome indicating which response is preferred.Source: §2 · p. 3
  • NLHF models general-preference alignment as a regularized minimax game whose max- and min-player policies are both regularized toward the reference policy.The described symmetric convex-concave game has a unique symmetric Nash equilibrium, which NLHF seeks as the alignment policy.Source: §2 · p. 3

3 Robust Game Formulation for Uncertain Preference Alignment

The robust game lets an adversary choose both a competitor and a preference kernel from a Bernoulli-KL ambiguity set centered on a nominal kernel. This worst-case objective lower-bounds performance across plausible kernels, while the coupled uncertainty set complicates optimization.

3 Robust Game Formulation for Uncertain Preference Alignment

  • The ambiguity set contains preference kernels within a Bernoulli-KL radius of a nominal kernel, with the radius quantifying uncertainty.The set is intended to represent uncertainty associated with finite, noisy, or heterogeneous preference data.Source: §3 · p. 4
  • The set couples all pairwise comparisons rather than decoupling across components, which significantly complicates optimization.The passage identifies this non-rectangular structure as a key source of computational hardness.Source: §3 · p. 4
  • The adversary chooses a competitor and a kernel, so the robust policy's value lower-bounds its win rate against any competitor under any kernel in the ambiguity set.The stated lower-bound interpretation ignores the regularizer.Source: §3 · p. 4

4 Four-Player Proxy Game

The robust problem is hard because the adversarial policy and preference kernel are coupled, and the kernel ambiguity set couples comparisons. A four-player proxy makes the optimization more tractable while providing lower bounds and, under stronger conditions, exact recovery of the truncated hard-constrained objective.

4 Four-Player Proxy Game

  • The coupled adversarial policy and preference kernel make the inner robust value difficult to compute, while the non-rectangular ambiguity set and non-monotone game structure challenge standard optimization methods.Even after fixing the leader policy, minimizing over the coupled policy and kernel is difficult; optimizing the concave reduced objective over the uncertainty set can be NP-hard.Source: §4 · p. 5
  • The truncated hard objective restricts preference-kernel probabilities to an interior box, and its truncation error is explicitly and uniformly controlled when p⋆ lies in that box.The leader policy is also restricted to a floor-truncated simplex, with ϵ selectable arbitrarily small to approximately recover the probability simplex.Source: §4 · p. 5
  • Under conditions (1)–(3) of Assumption 2, for every leader policy π ∈ Πϵ, the proxy value always lower-bounds the hard-constrained value.Source: §4 · p. 6
  • The proxy-to-hard gap can be made small by choosing δ and γmin appropriately; Assumption 3 gives exact equivalence when the maximizer γ⋆ has a uniform positive lower bound.The supplied result states an error up to δ + ργmin, with the ργmin term diminishing under the stronger exactness condition.Source: §4 · p. 6
  • Reordering the dual-variable maximization and adversarial-policy minimization turns the proxy into a bilevel max-min problem that can be treated as a two-player zero-sum game.The hard-constrained formulation has four optimization layers after maximizing over the leader policy.Source: §4 · p. 6

5 Algorithm Design and Convergence Analysis

The paper solves the proxy as a four-player saddle problem using single-loop optimistic mirror descent/ascent. Its averaged iterate converges to a proxy saddle point and yields a near-optimal policy for the robust objective.

5 Algorithm Design and Convergence Analysis

  • Restricting the opponent policy from the full simplex to Nβ does not affect the optimal solution.The algorithm returns an averaged iterate of all four blocks.Source: §5 · pp. 6–7
  • A single-loop optimistic mirror descent/ascent method solves the proxy max-min problem by treating the leader policy, dual variable, follower policy, and preference kernel as player blocks.The grouped problem maximizes over the policy and dual variable and minimizes over the follower policy and kernel.Source: §5 · pp. 6–7
  • The coordinate updates use entropy geometry for simplex blocks, Euclidean geometry for the dual variable, and binary entropy geometry for the preference kernel.The policy and follower blocks use KL divergences; the kernel uses Bernoulli-KL geometry.Source: §5 · p. 7
  • The averaged OGDA iterate converges to a saddle point of the proxy game and provides a near-optimal solution to the robust objective.The reported guarantee is for the averaged main policy; under Assumption 3, the guarantee improves.Source: §5 · p. 7

6 Experiment

The experiments test four-player OGDA across tabular games, heterogeneous-preference reranking, and LLM summarization. Across these settings, the reported results favor robust policies over nominal NashMD as preferences differ from training preferences.

6.1 Tabular Game

  • At every positive evaluation radius, tabular OGDA policies dominate NashMD, with the advantage growing as the radius increases.At training radius 0.2, OGDA converges close to the optimal robust value; training radii 0.1 and 0.4 finish below that optimum.Source: §6.1 · p. 8, Figure 1 · p. 8

6.2 Best-of-m IMDb Continuation Task

  • The robust IMDb policy uniformly outperforms NashMD under sampled perturbed kernels across the tested training and evaluation radii.The comparison averages over 8,000 prompts with eight candidate continuations; Table 1 reports win rates by training and evaluation radius.Source: Table 1 · p. 9, §6.2 · p. 9

6 Experiment

  • Across all three settings, four-player OGDA produces policies reported as more robust than nominal NashMD when preferences differ from training preferences.The experiments cover tabular games, IMDb continuation reranking, and LLM summarization.Source: §6 · p. 7, §6.3 · p. 9

6.3 Summarization Task with LLMs

  • Five of six external-judge configurations yield a win rate above 0.50 over NashMD on TL;DR summaries.The evaluation uses a non-BT PairRM nominal kernel and 1,000 TL;DR prompts.Source: §6.3 · p. 9, Table 2 · p. 10

7 Conclusion

The conclusion presents Robust Nash Alignment as a way to optimize worst-case performance across plausible preference kernels, using a tractable proxy game with approximation and convergence analysis. The related work distinguishes this kernel-level uncertainty from methods that optimize against fixed preference estimates or robustify other objects.

7 Conclusion

  • Robust Nash Alignment optimizes worst-case win rate over a divergence-based ambiguity set and provides a robustness guarantee.The conclusion says a four-player primal-dual proxy game addresses the hard-constrained objective's computational challenge, with approximation properties and convergence established using single-loop optimistic mirror descent-ascent.Source: §7 · p. 10

A Related Work

  • Unlike prior general-preference games that assume an exact learned game, this work optimizes against the worst kernel in an ambiguity set.Related work also distinguishes the approach from robust methods targeting prompt distributions, training examples, or nominal pairwise losses.Source: A Related Work · p. 16

B.1 Algorithm Update Rules

  • Assumption 3 is named Dual-optimum inclusion and applies to every (π, ν) in Πϵ × Nβ.The supplied passage begins its condition by referring to the scalar dual problem but does not include the full condition.Source: §B.1 · p. 17

B.2 Proof of Theorem 1

  • The proof bounds the proxy-to-hard objective gap by δ, yielding 0 ≤ Vδ(ρ) − V(ρ) ≤ δ.The proof also uses a feasible-set comparison and coordinatewise clipping to establish the bound.Source: §B.2 · pp. 17–18

B.3 Proof of Theorem 2

The proof of Theorem 2 establishes convexity and minimax properties, then identifies assumptions for exactness. The following theorem is titled as providing convergence and a robust guarantee for four-player OGDA with explicit δ-dependence.

B.3 Proof of Theorem 2

  • The proof establishes convexity in ν after minimizing over p and applies Sion’s minimax theorem on convex compact domains.It also labels an exactness step on Γ under Assumptions 2 and 3.Source: §B.3 · pp. 20–21

B.4 Proof of Theorem 3

  • Theorem 4 is stated as giving convergence and a robust guarantee for four-player OGDA with explicit δ-dependence.The supplied theorem passage does not include the full guarantee statement.Source: §B.4 · p. 21

Run Algorithm 1 with the constant step size

Then the duality gap of the averaged iterate

The averaged-iterate analysis transfers proxy-game guarantees to the hard robust objective, while identifying structural conditions needed for convergence. The surrounding comparisons, lemmas, and experiment setup explain the optimization challenges and the four-player approach.

Then the duality gap of the averaged iterate

C Comparisons with Standard NLHF

  • Unlike nominal NLHF, the hard robust objective lacks a clean convex-concave structure and is generally hard to optimize directly.Eliminating the follower gives concave minimization over the kernel set; retaining it makes the inner minimization jointly nonconvex.Source: C Comparisons with Standard NLHF · p. 25
  • The four-player game needs γmin > 0 and τγmin ≥ 1/4 so kernel-block curvature can dominate the mixed policy-kernel interaction.Without this condition, the grouped game need not be convex-concave, so the standard optimistic mirror-descent analysis does not apply.Source: C Comparisons with Standard NLHF · p. 25

D Auxiliary Lemmas

E.1 Nominal Preference and Annotator Groups

  • The IMDb setup uses 8,000 prompts, eight generated continuations per prompt, and three annotator groups whose preference kernels are mixed and perturbed.Dirichlet perturbations of the mixture weights produce group-shift kernels in the convex hull of the group kernels.Source: §E.1 · pp. 29–30

E.2 Optimization Algorithms

  • NashMD trains against a fixed nominal kernel, whereas the robust variant alternates follower best-response and kernel updates before its outer policy-dual update.The robust procedure uses K = 8 inner steps and outer step sizes (ηπ, ηγ) = (0.25, 0.15).Source: §E.2 · p. 30

E.3 Hyperparameters

  • Table 3 lists hyperparameters for the IMDb continuation experiments.Source: Table 3 · p. 30

E.4 Results

The controlled experiments show that robust training can outperform its nominal baseline across preference perturbations, with performance depending on the training radius and regularization temperature. The accompanying passages describe the preference proxy, adversary, and training losses.

E.4 Results

  • At τ = 0.05, the robust policy wins with probability above 97% for ρeval ≤ 0.30.At very small τ the nominal baseline is already concentrated, while at large τ both policies approach the uniform distribution.Source: §E.4 · p. 30
  • At τ = 0.05, training radii ρtrain ≤ 0.10 are statistically tied across evaluation radii, while ρtrain = 0.15 is significantly worse, increasingly so as ρeval grows.The figure compares win-rate curves across training radii.Source: §E.4 · p. 31, Figure 2 · p. 31

F.2 Nominal Preference Proxy

  • The nominal preference proxy is a DistilBERT-based scalar judge trained with Bradley–Terry cross-entropy on 83,573 TL;DR comparison pairs.After three epochs, it achieves 72% validation accuracy.Source: §F.2 · p. 32

F.3 Adversary Proxy

  • The adversary perturbs nominal preference logits with an antisymmetric head initialized to zero, preserving complementary pairwise probabilities at every iterate.The logit shift is clipped before the sigmoid to prevent probability saturation and stabilize dual ascent.Source: §F.3 · p. 32

F.4 Losses.

  • The losses use sampled leader-follower responses, clipped KL proxies, variance-reduction baselines, and clipped projected ascent for the dual variable.Each outer step interleaves K adversary updates; K = 3 is the default because K = 1 leaves the constraint far from active.Source: §F.4 · pp. 32–33

F.5 Evaluation with LLM Judges

With external LLM judges, the four-player policies retain nominal performance and improve the pairwise objective over NashMD. The paper also constructs and diagnoses a non-Bradley–Terry preference kernel for a TL;DR experiment.

F.5 Evaluation with LLM Judges

  • Across pairwise judges and evaluation criteria, four-player policies preserve strong nominal performance against NashMD and improve the nominal pairwise objective.The evaluation uses 1,000 TL;DR prompts; the reported worst-case 95% confidence half-width is approximately ±0.032.Source: §F.5 · p. 33

F.6 Non-BT Nominal Kernel: Construction and Diagnostic

  • The non-BT nominal kernel uses PairRM, whose opponent-conditioned candidate representations are not restricted to scalar-reward Bradley–Terry form.Antisymmetrizing the order-dependent logit difference makes the two directional preference probabilities sum to one.Source: §F.6 · p. 33
  • On 1,000 output triples, the kernel has a mean best-BT projection error of 0.384 logits per edge, while 1.4% of triples are cyclic.The reported diagnostic concludes that departures from BT are present in nearly every triple despite cycles being rare.Source: §F.6 · pp. 33–34

F.7 Additional Results with a Bradley-Terry Nominal Kernel

The additional results report robust-policy win rates against NashMD for a Bradley–Terry nominal kernel. The table covers external LLM judges and two fine-tuning backbones, complementing a non-BT-kernel experiment.

F.7 Additional Results with a Bradley-Terry Nominal Kernel

  • Table 7 reports robust-policy win rates against NashMD under a Bradley–Terry nominal kernel, using three external judges and 1,000 TL;DR prompts.The stated Clopper–Pearson half-width is approximately ±0.032 at n = 1,000.Source: §F.7 · p. 34, Table 7 · p. 34
  • The results cover Qwen-1.5B and add Gemma-2B as a second fine-tuning backbone.Source: §F.7 · p. 34
  • Table 7 uses a BT nominal kernel, unlike Table 2, which uses a non-BT kernel.Source: Table 7 · p. 34, §F.7 · p. 34

G LLM Judge Reasoning Examples

LLM judges disagree on which summary is better, balancing concision against contextual completeness and factual restraint. Across the examples, verdicts vary with which of those qualities the judge prioritizes.

Example 1

  • For the first example, Nemotron favored A for concision, while Gemma and DeepSeek favored B for explaining the poster’s motivation and experience.Nemotron judged A more concise and direct; Gemma and DeepSeek valued B’s additional context.Source: Example 1 (prompt_id 57) · p. 35

Example 2

  • In the relationship-rekindling example, Nemotron, Gemma, and DeepSeek favored B for preserving the reasons for lost interest and the advice-seeking narrative.Nemotron noted the passive messaging pattern; Gemma and DeepSeek emphasized the cause of the woman’s disengagement and B’s more complete narrative.Source: Example 2 (prompt_id 125) · p. 36

Example 3

  • For the postponed-date example, Nemotron and Gemma favored B’s account of the postponement and the poster’s uncertainty, while DeepSeek preferred A’s factual restraint.Gemma also noted that B identifies the woman—not the poster—as repeatedly postponing the date.Source: Example 3 (prompt_id 114) · p. 37

Example 4

  • In the household-conflict example, Nemotron and Gemma rejected A’s claim that the poster wanted to break up, while DeepSeek treated that inference as reasonable.The source says the boyfriend suggested breaking up; DeepSeek nevertheless viewed A’s inference as conveying the seriousness of the poster’s frustration.Source: Example 4 (prompt_id 71) · p. 38

Related papers

Loading 2610.00715v1…