- Rating
- 2
- Confidence
- 1
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies learning in continuous games where players only have the access to noisy pairwise comparisons, without seeing the actual payoffs. It first shows that standard external regret and coarse correlated equilibria (CCE) cannot be uniquely determined from such ordinal feedback. In particular, Theorem 3.1 shows that the distributions remaining CCE under all equivalent utility representations are exactly those supported on pure Nash equilibria. The authors solve this with a framework based on the normalized gradient, showing that this projected normalized gradient play achieves sublinear ordinal regret. More interestingly, Under additional assumptions on ordinal potential games, Theorem 5.2 also establishes almost-sure last-iterate convergence to the Nash set. However, the whole paper is purely theoretical, and there is no experimental evaluation. To be very honest, I am not able to verify all the proofs in the appendix, particularly the stochastic approximation argument for Theorem 5.2, which is actually one of the critic strengths on my mind.
Critical strengths
I like the observation that standard learning objectives in games can change under different numerical representations of the same preferences. The example in Figure 1 is particularly useful. Even though the games have identical preferences, standard gradient play can behave differently because the gradients of individual players are scaled differently. Normalizing each player's gradient addresses this particular issue. Together with Theorem 3.1, this gives a good motivation for studying learning objectives that depend only on ordinal information. Besides I also find Theorem 5.2 interesting. Establishing almost-sure convergence to Nash equilibria using only noisy comparisons is a stronger result than simply bounding a newly defined regret measure. The discontinuity of normalized gradients near stationary points also makes the convergence analysis nontrivial. I appreciate that the authors address this issue through differential inclusions.
Critical weaknesses
My biggest concern is whether the proposed framework and its regret guarantees constitute a sufficiently new contribution.
Ordinal directional regret is essentially linearized regret with each player's gradient normalized. Given this definition, Theorem 4.1 seems to follow from the standard online gradient descent analysis. The connection between ordinal regret and the proposed equilibrium residual in Equation (7) also appears to be a direct consequence of the definitions. While these results are mathematically reasonable, I do not see much technical novelty in them.
I have a similar concern about Theorem 5.1. The comparison-based estimator is closely related to existing gradient estimation methods, and the regret bound is established for the finite-resolution field that the estimator targets. The main issue is that this is not the original ordinal directional regret introduced earlier in the paper. In fact, Proposition E.1 gives a strongly convex example where the finite-resolution regret stays bounded while the original ordinal regret grows linearly.
Theorem 5.2 is probably the most interesting technical result. However, the convergence guarantee is restricted to ordinal potential games. In this setting, all players' comparisons are consistent with a common potential function, making the algorithm closely related to comparison-based optimization of that potential. I would like to understand what additional difficulties arise from the multi-agent setting, and how much of the analysis goes beyond existing results for comparison-based optimization. As it stands, I find the result interesting but its novelty somewhat difficult to assess.
Moreover, the practical motivation is not entirely clear to me. The paper assumes that comparisons have a fixed error probability independent of the difference between the two actions. This is a rather specific noise model. In settings such as RLHF or recommendation systems, comparisons between nearly identical choices are often less reliable. As the authors note, other noise models may allow numerical information to be recovered through repeated comparisons. I would like to see a clearer discussion of when the proposed purely ordinal setting is the right model, especially since the paper does not provide experiments or a concrete application.
Questions for authors
-
Can the authors give a more concrete interpretation of small ordinal directional regret in terms of players' preferences? For example, under convexity or other additional assumptions, can it be related to the improvement achievable by a fixed deviation?
-
Theorem 5.1 only bounds regret for the finite-resolution field, and Proposition E.1 shows that this does not generally imply sublinear regret for the original normalized field. Are there reasonable additional assumptions under which the algorithm can guarantee the original ordinal directional regret? I think this would substantially strengthen the result.
-
What is the main technical difference between Theorem 5.2 and existing convergence results for comparison-based optimization? Since the theorem assumes an ordinal potential game, it would be helpful to clarify which parts of the proof are specific to the multi-agent setting.
3 comments
(Response to Q1 (continued))
Proof of the field identity above. For a quadratic unilateral cost, the second-order terms cancel in the symmetric difference, giving the exact identity $q_i(x_i+\delta u,x_{-i}) - q_i(x_i-\delta u,x_{-i}) = 2\delta\langle\nabla_iq_i(x),u\rangle$. The regular increasing transformation preserves both the comparison sign and the normalized gradient direction. Thus the finite comparison sign equals . For a nonzero block gradient, spherical symmetry gives $D_i^\delta(x) = \frac{1}{\kappa_{d_i}} \mathbb E_{U_i}!\left[\operatorname{sgn}\langle\nabla_iJ_i(x),U_i\rangle,U_i\right] =\frac{\nabla_iJ_i(x)}{|\nabla_iJ_i(x)|} =D_i(x).$ At a stationary block, implies that as well. The quadratic difference identity then shows that the two symmetric query costs are equal for every direction. Hence every comparison sign is zero, giving . The field identity therefore holds even at stationary blocks, without requiring gradient norms to be bounded away from zero.
We thank the reviewer for suggesting this extension. We will add this corollary and its proof to the revised manuscript.
Q3. What is the main technical difference between Theorem 5.2 and existing convergence results for comparison-based optimization? Since the theorem assumes an ordinal potential game, it would be helpful to clarify which parts of the proof are specific to the multi-agent setting.
We agree that ordinal potential games admit a comparison-based optimization interpretation: every unilateral cost comparison coincides with the corresponding potential comparison, as stated in Section 5.3.
Theorem 5.2 already yields a single-agent result of independent interest. Taking and , it establishes almost sure convergence of the actual iterates to the global minimizer set of a smooth pseudoconvex objective over a compact convex feasible set, using one noisy comparison per iteration under the stated assumptions. This guarantee is not established by the smooth convex optimization results of Saha et al. (2021).
In the multi-agent setting, the theorem analyzes simultaneous, projected, block-normalized updates from noisy unilateral comparisons. The additional distinctions compared to the optimization setting concern the available oracle, the block dynamics, and the convergence target:
-
Unilateral comparison oracle. Each player compares two of its own actions while opponents’ actions remain fixed. The oracle does not provide comparisons between arbitrary joint profiles. For example, the comparisons with a global best-so-far candidate used by Saha et al. (2021) are not generally available.
-
Separate block normalization. The single-valued preference-direction field (defined in eq. (3)) normalizes each player’s gradient separately, rescaling the blocks by different factors. This field can be discontinuous at profiles where one gradient block vanishes while others remain nonzero, even though the globally normalized potential gradient is continuous there. Figure 1 also illustrates that block normalization makes learning trajectories invariant under regular increasing cost transformations.
-
Assumptions and convergence target. The theorem does not require joint convexity of the potential. Under the stated nondegeneracy assumption, blockwise pseudoconvexity of the players’ costs identifies constrained stationary points of the potential with Nash equilibria. Such equilibria need not globally minimize the potential. Consequently, the smooth convex optimization guarantees of Saha et al. (2021) do not directly establish the claimed convergence result.
The main technical challenge we address. The comparison estimator satisfies . Vanishing comparison radii do not generally imply along moving iterates near stationary blocks. This difficulty already occurs with one player; block normalization additionally requires handling it when only some players are stationary. Thus, the convergence argument cannot simply treat the updates as asymptotically unbiased estimates of a continuous normalized field.
The proof addresses this through the following steps. We complete the normalized potential field with the closed unit ball at each zero-gradient block. Lemma E.2 establishes graph consistency of the finite-resolution fields with this completion. Lemma E.3 then represents the feasible noisy updates as projected stochastic approximation to the corresponding differential inclusion. Lemma E.4 shows that the potential is a Lyapunov function for the projected limiting differential inclusion: its directional derivative is nonpositive for every admissible velocity and vanishes exactly at constrained stationary points of . Finally, Lemma E.6 identifies this set with the Nash set. These properties allow us to apply the result of Majewski et al. (2018), yielding almost-sure convergence of the actual iterates to the Nash set using one comparison per player and round, and to a single equilibrium when the Nash set is finite.
We will clarify these distinctions and the main proof steps in the main text. Appendix E.3.1 provides the full proof, beginning with an outline.
Comparison noise model. Our model isolates learning from ordering information: repeated comparisons improve confidence in a preference but cannot identify utility gaps. It covers exact comparisons and comparison labels subject to independent corruption, as also considered by Saha et al. (2021). Human judgments can exhibit gap-dependent errors; with a known, calibrated, invertible link, such feedback can additionally reveal numerical gap information. We will clarify the distinction between these information models and the scope of our guarantees.
LLM-routing application and toy experiments. We have added simulations of a synthetic LLM-routing game in Appendix F. LLM routing selects which model should answer each prompt; for example, RouteLLM [Ong et al., ICLR 2025] learns this selection from response-level preference data. Our application introduces strategic interaction: two independently managed applications adapt their routing policies while sharing inference capacity. Changing one application’s routing policy changes congestion and therefore the other application’s preferences, creating a continuous game.
Each application chooses the fractions of its requests to send to each of two LLM services. We use human comparisons from Chatbot Arena to calibrate the response-quality component of the costs, which we combine with modeled operating and congestion costs. A simulated evaluator compares two nearby routing policies for one application while holding the other’s policy fixed, and returns only a noisy preference label. Our CNGP algorithm updates from these unilateral comparisons without observing numerical costs or cost differences.
The costs are constructed to give an ordinal potential game satisfying all assumptions of Theorem 5.2. In the two-dimensional setting, Figure 2 (left) in Appendix F of the revised manuscript shows routing trajectories approaching the unique Nash equilibrium from different initializations, illustrating the theorem’s last-iterate convergence conclusion. Figure 2 (right) shows decreasing mean distance to Nash over 64 runs per noise level, with larger terminal errors as comparisons become less reliable (see also Figure 3). A six-dimensional extension with three traffic classes per application also shows decreasing distance to Nash. Appendix F provides a detailed description of the application and the experimental setting.
[Ong et al., ICLR 2025] Ong, Isaac, Amjad Almahairi, Vincent Wu, Wei-Lin Chiang, Tianhao Wu, Joseph E. Gonzalez, Mohammed Kadous, and Ion Stoica. RouteLLM: Learning to Route LLMs from Preference Data. ICLR 2025.
We thank the reviewer for their time, useful feedback and constructive questions.
Technical contributions. Theorem 4.1 uses the standard projected OGD inequality; we will make this explicit and cite Zinkevich (2003). Equation (7) is the associated regret–residual identity, and the comparison estimator builds on existing work as discussed in the paper. Our technical contributions include the exact ordinally robust CCE characterization (Theorem 3.1) which we believe is of independent interest, finite-resolution regret and its separation from the original benchmark even for smooth strongly convex costs (Theorem 5.1 and Proposition E.1), and almost sure Nash convergence (Theorem 5.2). Our response to Q2 below adds a bound on the (original) ordinal regret as suggested, and our response to Q3 discusses the significance and the convergence analysis of Theorem 5.2. In particular, the proof requires graph consistency of the finite-comparison fields and a projected Lyapunov analysis near stationary blocks to establish the result. It also yields a standalone single-agent pseudoconvex optimization guarantee.
Responses to questions:
Ordinal directional regret measures the cumulative normalized first-order incentive to move toward a fixed alternative.
For a fixed unilateral alternative yi, let hi,t(yi)=⟨Di(xt),xi,t−yi⟩ and gi,t=∥∇iJi(xt)∥.
Along the feasible unilateral move xi,t(λ)=(1−λ)xi,t+λyi for λ∈[0,1], the chain rule gives at λ=0, dλdJi(xi,t(λ),x−i,t)=−gi,thi,t(yi).
Thus hi,t(yi)>0 means that a sufficiently small move toward yi is strictly preferred. Since Regi,TD=supyi∈Xi∑t=1Thi,t(yi), sublinear ordinal directional regret means that no fixed alternative provides a persistent positive average of these normalized first-order gains.
Under blockwise pseudoconvexity, every strictly preferred full deviation also has positive directional gain: Ji(yi,x−i,t)<Ji(xt)⟹hi,t(yi)>0. The converse need not hold for a full deviation because the move can overshoot.
Under convexity of Ji with respect to its ith variable, Ji(xt)−Ji(yi,x−i,t)≤gi,thi,t(yi). Hence every fixed yi satisfies $\sum_{t:g_{i,t}>0} \frac{J_i(x_t)-J_i(y_i,x_{-i,t})}{g_{i,t}} \le \operatorname{Reg}_{i,T}^{D}.$ Each numerator is the signed cost reduction from switching completely to yi. At zero-gradient rounds, convexity implies that the current action is already a unilateral minimizer, so no positive deviation gain is omitted. Thus, sublinear ordinal regret bounds the cumulative gain of every fixed deviation on this normalized scale. It does not, in general, imply sublinear ordinary (unnormalized) external regret.
We will add these interpretations and the convexity bound to the revised manuscript.
Yes, suppose $J_i(x_i,x_{-i}) =\phi_i\left(q_i(x_i,x_{-i})\right),$ where ϕi′>0, and qi(⋅,x−i) is quadratic for every fixed opponents’ profile. Then Diδ(x)=Di(x) for every comparison radius δ>0 for which the symmetric queries are feasible. Consequently, the finite-resolution and original ordinal regrets coincide pathwise, and all guarantees of Theorem 5.1 apply unchanged to the original ordinal regret under the same feedback assumptions, stepsizes, and comparison radii. This uses one comparison per player and round against arbitrary opponents. Only the dependence on the player’s own action must admit a quadratic representation; its coefficients may depend on the opponents’ actions. Convexity and potential structure are unnecessary for this regret result.