- Rating
- 3
- Confidence
- 2
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper proposes Robust Nash Learning from Human Feedback (NLHF), which accounts for uncertainty in preference models. The key technique is to reformulate the objective as a convex-concave saddle-point problem by introducing a joint distribution over preference scenarios and opponent responses. The authors develop a Mirror-Prox-based algorithm and prove convergence rates of for finite uncertainty sets and for continuous uncertainty sets. Experiments demonstrate improvements over a nominal NLHF baseline in settings where distributions over fixed candidate responses are optimized.
Critical strengths
- The paper is well-written: reading introduction made me grasp the key contributions and the structure easily.
- The proposed reformulation of the robust NLHF into convex-concave problem by introducing joint distribution is simple and generalizable technique.
- The theoretical analysis is solid, providing convergence guarantees for both finite and continuous uncertainty sets.
Critical weaknesses
This is a theory-oriented paper, so the following points are not major weaknesses. However, I have several concerns about the gap between theory and practice.
- The convergence analysis for continuous uncertainty sets assumes exact integration, whereas the experiments rely on numerical approximation. The impact of approximation errors on the convergence guarantees is not discussed.
- The paper assumes that the ambiguity set is given. Although the authors suggest constructing it from multiple fitted preference models, the experiments do not investigate how to estimate a reliable ambiguity set from finite and noisy preference data.
Questions for authors
- Does authors have some insights on how to estimate the reliable ambiguity set in the LLM experiment setting? For example, how to determine the number of preference models to fit and how to ensure that the resulting ambiguity set adequately captures the underlying preference uncertainty?
- Could the authors give some guarantee or insights on the effect to the convergence rate O(logT/T) if the integration over the uncertainty parameter is approximated by finite quadrature points?
6 comments
Weakness 1 & Question 2 (continued)
Refinement study. To measure the approximation error on its own, we ran EJMP on six grids at on 48,000 problems: 4,000 prompts, two references and six radii (Table 11, Appendix D.2.6). Selected rows follow; all errors are means in units of .
| Grid | Nodes | Node-game gap | Grid overestimate | A priori bound on |
|---|---|---|---|---|
| 24 | 4.54 | 6.81 | 30.91 | |
| (submitted) | 288 | 6.10 | 0.80 | 4.00 |
| 960 | 6.51 | 0.30 | 1.40 | |
| 2,304 | 6.61 | 0.20 | 0.79 |
At the submitted grid, the grid overestimate is already smaller than the node-game gap on average and in nearly every problem. Refinement reduces the overestimate substantially, but the continuous gap changes only from to , because the node-game gap at fixed rises as falls. This is consistent with the larger initial radius of finer grids. Solving the node games to a certified gap of leaves a mean robust-value loss of , against for the fixed-budget runs. At , most of the error therefore comes from optimization rather than quadrature.
The numerical comparison uses interval enclosures of the continuous worst case: outer-polygon vertices give a lower bound by concavity, and feasible scenarios give an upper bound. For any feasible output , a certified lower bound and upper bound give the stopping test , which certifies a robust-value error of at most regardless of how the output was obtained. We use this test with for the main results of the revision.
Weakness 2 & Question 1: Constructing a reliable ambiguity set from data
We thank you for this question. Constructing ambiguity set through concentration inequality is standard in statistical learning, and we now added Appendix E, which builds the set from the comparison likelihood as a split likelihood-ratio confidence region with finite-sample coverage, and fits our model. The number of components is chosen by held-out likelihood on a separate data split, and a transfer bound states what the set guarantees for the true preferences. Consider reciprocal component kernels with entries in and their mixtures , . No Bradley–Terry representation is required. Once the components are supplied, their mixture weights can be estimated from binary comparisons without evaluator-group labels.
We split the data into a pilot sample and an independent validation sample . All component fitting, the selection of and the pilot estimate use only, and these choices are frozen before is examined. For comparison , let and . For , define
\widehat{\mathcal U}=\left\\{w\in\Delta_K: \sum_{t\in D_0}\log\frac{p_t(\hat w_1)}{p_t(w)} \le\log\frac1\delta\right\\}.
This is a split likelihood-ratio set (Wasserman, Ramdas and Balakrishnan, 2020). It contains , and it is compact and convex because each validation log-likelihood is continuous and concave in .
Weakness 2 & Question 1 (continued)
Coverage. What the set covers depends on whether the family contains the truth. If , the set contains with probability at least for every sample size. Conditional on the pilot sample and an exogenous query design, the validation likelihood ratio has expectation one, and independence and Markov's inequality give coverage.
Under misspecification, suppose the validation observations are independent and identically distributed, with queried pairs drawn from , and that some mixture has finite risk
Then the set covers any fixed minimizer of this risk with probability at least : convexity of the mixture family gives the likelihood-ratio expectation bound that the same argument needs. Finite risk is automatic for a finite query space with positive component probabilities, or when the components are uniformly bounded away from zero and one. Appendix E gives the proof.
What the set implies for the true preferences. The second guarantee covers the KL projection, not an arbitrary true kernel outside the family. Define
\varepsilon &= \sup_{x,y,y'} |P^\star_x(y\succ y')-A_x(w^\dagger)(y\succ y')|, \\\\ \Delta_A(\widehat{\mathcal U}) &= \sup_{w,v\in\widehat{\mathcal U}}\sup_{x,y,y'} |A_x(w)(y\succ y')-A_x(v)(y\succ y')|. \end{aligned}$$ On the coverage event, for each evaluation prompt, the returned policy satisfies $$\begin{aligned} g^\star(\pi) &\ge V^\star_{\widehat{\mathcal U}}-\mathrm{Gap}(\pi,Q)-\varepsilon, \\\\ \max_{\pi'}g^\star(\pi')-g^\star(\pi) &\le \Delta_A(\widehat{\mathcal U})+\mathrm{Gap}(\pi,Q)+2\varepsilon \\\\ &\le \tfrac12\operatorname{diam}_1(\widehat{\mathcal U})+\mathrm{Gap}(\pi,Q)+2\varepsilon. \end{aligned}$$ Proposition E.1 states the last form, and Appendix E also states the middle one, which follows because each payoff averages kernel entries with weights $\pi_y\nu_{y'}$. The three terms separate uncertainty among plausible kernels, optimization error and approximation error of the chosen family. The validation data do not estimate the uniform error $\varepsilon$, especially on unobserved pairs; under correct specification, $\varepsilon=0$. **How many models.** We select $K$ and the components on $D_1$ by held-out likelihood, leaving $D_0$ untouched, so that coverage holds conditionally on the selected family. A component is worth adding only if it raises the held-out likelihood. A component outside the convex hull of the others enlarges the family and can reduce $\varepsilon$, but it adds a free weight, which can widen $\widehat{\mathcal U}$ and make the policy more conservative. A component inside the hull adds no new kernel. Anonymous comparisons alone generally cannot identify latent evaluator components, so the components come from side information, such as group labels, annotator identities or candidate models like our profiles, and the comparisons estimate their weights. The guarantee does not certify that the chosen $K$ is sufficient; the remaining misspecification enters only through $\varepsilon$. **Deployment shift.** We treat deployment shift as a modeling choice: it can be represented by $\overline{\mathcal U}_\rho=\\{w:\mathrm{KL}(w\\|v)\le\rho\text{ for some }v\in\widehat{\mathcal U}\\}$, which is compact and convex. On the event $w^\star\in\widehat{\mathcal U}$, it contains every deployment mixture within KL distance $\rho$ of $w^\star$. Training comparisons do not determine this budget. **In the LLM setting you ask about**, the pipeline is: fit candidate component kernels and choose $K$ on $D_1$; form $\widehat{\mathcal U}$ on $D_0$; enlarge it to $\overline{\mathcal U}_\rho$ if deployment shift is expected; run EJMP on the result and report its certificate. Our IMDb experiments prescribe the profiles, nominal weights and radius, so Appendix E is a statistical construction that we have not validated empirically. Its sets satisfy the structural assumptions of our optimization results; for a continuous set, exact integration or the fixed-node bound of Remark 4 is still required. ### References E. M. Bronshtein and L. D. Ivanov. The approximation of convex sets by polyhedra. Siberian Mathematical Journal, 16(5):852–853, 1975. L. Wasserman, A. Ramdas and S. Balakrishnan. Universal inference. Proceedings of the National Academy of Sciences, 117(29):16880–16890, 2020.
Thank you for the positive assessment and for identifying these two gaps between the theory and the implementation. We have added a bound that separates the optimization error on fixed quadrature nodes from the approximation of the continuous uncertainty set, together with a grid-refinement study (Remark 4, Appendix D.2.6). In the new Appendix E, we construct the ambiguity set from comparison data and distinguish coverage of the true kernel from coverage of its projection onto a specified model family.
Weakness 1 & Question 2: Approximate integration and convergence
A fixed grid gives an O(1/T) optimization bound plus an approximation term that does not shrink with T; refining the grid with the target horizon restores O(logT/T). Let H⊂U be the nodes, let ωh>0 be their normalized weights, and initialize the joint law at ω⊗πref. The quadrature implementation is then Algorithm 1 on this finite scenario set. For the affine mixture family and exact node-game updates with fixed 0<η≤1, we show in Remark 4 and Appendix D.2.6 that
0≤VU⋆−gU(πˉT)≤GapH(πˉT,QˉT)+DH(πˉT)≤ηT2R+log(1/ωmin)+δH,
where R=log(1/πref,min), DH(π)=gH(π)−gU(π), and
δH=21supw∈Udist1(w,convH).
Convergence on a fixed grid therefore does not by itself imply convergence to the continuous optimum.
The proof separates the two errors. A joint law supported on H is also feasible for the continuous adversary, which gives the exact identity GapU=GapH+DH. Theorem 4.2 bounds the first term with initial comparison radius 2R+log(1/ωmin). For the second, the Gibbs-eliminated payoff ϕπ(w) is concave and satisfies ∂ϕπ/∂wk=π⊤A(k)νw∈[0,1]. Since differences of simplex weights sum to zero, ϕπ is 21-Lipschitz in ℓ1. Its minimum over convH equals its minimum over H, which yields 0≤DH≤δH.
Refining the grid. To recover the rate for a target horizon T, we choose a grid HT with δHT≤1/T, keep it fixed during the run, and use uniform node weights. A grid with O(TdU) nodes suffices, giving an O(logT/T) bound and O(TdU+1m2) Mirror-Prox arithmetic operations. Concavity permits a smaller construction: for dU≥2, suitably placed boundary nodes give δH=O(∣H∣−2/(dU−1)) by convex-body approximation (Bronshtein and Ivanov, 1975). Hence O(T(dU−1)/2) nodes suffice, which reduces the arithmetic cost to O(T(dU+1)/2m2). These costs exclude constructing the nodes and evaluating numerical certificates. For the two-dimensional IMDb uncertainty set, the boundary-node count is O(T).
This guarantee covers a family of fixed-grid runs indexed by their target horizon; it does not automatically extend to a run that changes grids. Such an output can instead be assessed directly with its continuous saddle-gap certificate (next comment).