Paper deep dive
Context-dependent agent evaluation with orthogonal equilibrium learning
Haorui Ma, Zehua Zang, Jiangmeng Li, Yi Li, Fanjing Xu, Stefan Feuerriegel
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 9/29/2026, 12:21:38 PM
Summary
The paper introduces NashEval, a framework for context-dependent agent evaluation that addresses the limitations of score-based models by framing evaluation as a contextual game. It proposes a Debiased Payoff Matrix (DPM) and an orthogonal loss to learn context-to-equilibrium mappings robustly from offline feedback, ensuring that errors in nuisance function estimation affect the equilibrium risk only through higher-order terms.
Entities (10)
Relation Signals (7)
Stefan Feuerriegel → affiliatedwith → LMU Munich
confidence 98% · Affiliation: AI in Management, LMU Munich
Jiangmeng Li → affiliatedwith → Chinese Academy of Sciences
confidence 98% · Affiliation: Institute of Software, Chinese Academy of Sciences
Haorui Ma → affiliatedwith → LMU Munich
confidence 98% · Affiliation: AI in Management, LMU Munich
NashEval → uses → Orthogonal Loss
confidence 95% · NashEval then learns the context-to-equilibrium mapping with a tailored orthogonal loss
NashEval → uses → Debiased Payoff Matrix
confidence 95% · NashEval first constructs debiased estimates of the contextual payoff matrix that characterizes the game.
NashEval → isinspiredby → Social Choice Theory
confidence 92% · Inspired by social choice theory, we frame evaluation as a contextual game
NashEval → addresseslimitationof → Bradley-Terry
confidence 90% · Existing score-based models for this purpose (e.g., Bradley-Terry) impose a transitive preference ordering, which fails to reflect collective preferences when human judgements are heterogeneous.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Many applications require to evaluate agents under contextual information (e.g., a prompt, task, or user group). We study how to perform such context-dependent agent evaluation from offline feedback. Existing score-based models for this purpose (e.g., Bradley-Terry) impose a transitive preference ordering, which fails to reflect collective preferences when human judgements are heterogeneous. Inspired by social choice theory, we frame evaluation as a contextual game between two players, each selecting a distribution over agents as the strategy to receive greater collective preference than the other. Then, the support of the Nash equilibrium defines a context-specific set of winners. However, learning context-specific equilibria from offline logs is difficult because each context reveals human feedback on only a subset of agents, and, hence, a naive plug-in estimator can therefore be biased. To address these challenges, we propose NashEval, a general framework for robust contextual equilibrium learning. NashEval first constructs debiased estimates of the contextual payoff matrix that characterizes the game. NashEval then learns the context-to-equilibrium mapping with a tailored orthogonal loss, which avoids the need to solve a separate game for each context. We show theoretically that errors in estimating the nuisance functions underlying the payoff matrix affect the risk of the learned equilibrium (i.e., exploitability) only through higher-order terms. Across various experiments, NashEval improves robustness of equilibrium learning and consistently identifies the set of top-performing agents across contexts.
Tags
Links
- Source: https://arxiv.org/abs/2609.31897v1
- Canonical: https://arxiv.org/abs/2609.31897v1
Trouble viewing inline? Open PDF directly →
Full Text
209,853 characters extracted from source content.
Expand or collapse full text
Context-dependent agent evaluation with orthogonal equilibrium learning Haorui Ma & Stefan Feuerriegel11footnotemark: 1 †thanks: Corresponding authors: Haorui Ma (H.Ma@lmu.de) and Stefan Feuerriegel (feuerriegel@lmu.de). Affiliation: AI in Management, LMU Munich Affiliation: Munich, Germany Affiliation: Munich Center for Machine Learning, Germany Email: H.Ma,feuerriegel@lmu.de Jiangmeng Li Yi Li & Fanjing Xu Affiliation: Institute of Software Affiliation: Chinese Academy of Sciences Email: jiangmeng2019@iscas.ac.cn Zehua Zang Affiliation: Peking University Abstract Many applications require to evaluate agents under contextual information (e.g., a prompt, task, or user group). We study how to perform such context-dependent agent evaluation from offline feedback. Existing score-based models for this purpose (e.g., Bradley–Terry) impose a transitive preference ordering, which fails to reflect collective preferences when human judgements are heterogeneous. Inspired by social choice theory, we frame evaluation as a contextual game between two players, each selecting a distribution over agents as the strategy to receive greater collective preference than the other. Then, the support of the Nash equilibrium defines a context-specific set of winners. However, learning context-specific equilibria from offline logs is difficult because each context reveals human feedback on only a subset of agents, and, hence, a naïve plug-in estimator can therefore be biased. To address these challenges, we propose NashEval, a general framework for robust contextual equilibrium learning. NashEval first constructs debiased estimates of the contextual payoff matrix that characterizes the game. NashEval then learns the context-to-equilibrium mapping with a tailored orthogonal loss, which avoids the need to solve a separate game for each context. We show theoretically that errors in estimating the nuisance functions underlying the payoff matrix affect the risk of the learned equilibrium (i.e., exploitability) only through higher-order terms. Across various experiments, NashEval improves robustness of equilibrium learning and consistently identifies the set of top-performing agents across contexts. A Preprint 1 Introduction Many applications require agents to be evaluated together with contextual information, such as the prompt, task, language, domain, or user group [84, 36, e.g.,].. For example, in model routing, the goal is not to identify a single globally best language model, but to select an appropriate model for a particular prompt [62]. More generally, agents may have different strengths across tasks and domains [36], and human preferences can also vary across users and settings [38]. Here, we study context-dependent agent evaluation from selectively observed relative feedback (e.g., pairwise preferences or partial rankings) collected from a population of voters with heterogeneous preferences to identify, for each context, a set of agents that best reflects collective preference of the population (see Figure 1). Figure 1: Agent evaluation is subject to two challenges: (1) preferences sampled from a large population of voters are heterogeneous and, thus, often intransitive; and (2) the capabilities of agents vary across contexts. ⇒ We propose a novel framework called NashEval for this task by framing evaluation as solving a contextual, two-player zero-sum game, constructed from the preferences. In this paper, we propose NashEval, a game-theoretic framework for contextual agent evaluation. Our framework is flexible and accommodates any form of relative feedback that can be represented as ordered partitions (e.g.. pairwise preferences, partial rankings, and winner-of-subset feedback). For a given context, we formulate the evaluation as a regularized two-player zero-sum game, in which each player selects a distribution over agents and seeks to outperform the other according to the collective preference. The support of the corresponding Nash equilibrium then defines a context-specific set of winners. To learn this equilibrium from selectively observed feedback, our framework proceeds in two stages. First, we construct a novel debiased payoff matrix (DPM) that is robust to nuisance misspecification. Second, we use the estimated payoff to introduce a tailored orthogonal loss to directly learn the context-to-equilibrium mapping. Thereby, we amortize equilibrium computation rather than solving a separate game for every context. We show theoretically that that the robustness guarantees of the DPM transfer to the learned equilibrium; i.e., errors in estimating the nuisance functions underlying the payoff matrix affect the risk of the learned equilibrium (i.e., exploitability) only through higher-order terms and, under suitable conditions, can therefore achieve quasi-oracle convergence rate. As a by-product, we derive a general equilibrium learning framework that is robust to nuisance misspecifications. Our main contributions are: (i) We propose NashEval, a novel game-theoretic framework for learning context-dependent agent evaluators from logged data with relative feedback. (i) We derive strong theoretical guarantees for our equilibrium learner in the form of Neyman orthogonality, bounds on the average exploitability, and a quasi-oracle convergence rate. (i) We demonstrate the effectiveness of our NashEval framework on both simulated and real-world datasets. 2 Related work11 1 We provide an extended related work in Appendix A. Social choice theory: This literature studies collective choice under potentially intransitive preferences [32, 13]. Concepts like Condorcet [22] and Copeland winners [20] may fail to identify a unique or robust winner [22, 54, 77]. We build on this literature by developing a game-theoretic solution concept for context-dependent agent evaluation. Agent evaluations: There are several approaches for related but different settings (see Table 1). Traditionally, evaluation methods aggregate feedback across contexts to produce a single global leaderboard [18, 34, e.g.,], and, more recently, there are extensions to incorporate contextual information [62, 36, 17, e.g.,]. However, these approaches rely on score-based models [9, e.g., Bradley–Terry;], and therefore assume transitive preferences, meaning that if A≻BA B and B≻CB C, then A≻CA C. Importantly, this assumption can be restrictive when feedback is collected from a heterogeneous population, since aggregating individual preferences can result in intransitive collective preferences [22, 49], particularly for subjective, open-ended tasks [38]. As a result, models that assume such transitivity can be misspecified and produce biased (or even conflicting) evaluations that do not reflect the underlying heterogeneous. To the best of our knowledge, approaches for context-dependent agent evaluation with intransitive collective preferences are missing. Game-theoretic approaches: A common approach is to frame agent evaluation as a two-player zero-sum game between two dueling evaluation policies that compete head-to-head for voter preference [85]. The game is characterized by an antisymmetric payoff matrix (PM) constructed from the relative feedback, and its Nash equilibrium is a distribution over agents for which support is interpreted as the set of winners. Because no evaluation policy strictly beats this equilibrium, it is the best evaluation achievable under intransitive feedback and has typically favorable properties (e.g., Condorcet-consistent, meaning that when a Condorcet winner exists, the equilibrium places all probability on that agent). In the dueling bandit literature, such equilibrium concepts are referred to as the von Neumann winner (vNw) [25] and, social choice theory, as the maximal lottery [50, 32]. Recently, Lanctot et al. [52], Khalaf et al. [46] study maximal lotteries for global agent evaluation. In contrast, approaches that learns the context-specific equilibrium for agent evaluation are still missing. Table 1: Key works on agent evaluation from relative feedback. PreferenceEvaluator Global Contextual Transitive [18, 34] [62, 36] Intransitive [52, 46] NashEval (ours) Why context-dependent agent evaluation is challenging? A major difficulty of context-dependent evaluation is that, for a given context, a voter is shown only a small subset of agents, and thus the feedback is often partially observed. This means that the contextual PM must be estimated using nuisance functions33 3 The term “nuisance functions” refers to components that facilitate estimation of statistical target by modeling observable distributions from data but are not themselves of direct interest.. When these nuisance functions are misspecified, the estimated PM can be biased, which leads to a suboptimal approximation of the equilibrium (see Proposition 1). Hence, a key challenge is to learn the contextual equilibrium in a way that is robust to errors in the nuisance function. 3 Preliminaries When preferences are aggregated across a population, they may become intransitive even if each individual’s preferences are transitive (see Appendix E.1 for an example). In such cases, a single deterministic winner may not exist, which motivates game-theoretic solution concepts (i.e., lotteries over winners) that can represent collective preferences [32, 13]. Preference game: Let A∈[−1,1]K×KA∈[-1,1]^K× K denote the collective preference matrix with entriesAjk=P(j≻k)−P(k≻j)A_jk=P(j k)-P(k j), which satisfies A=−A⊤A=-A . We interpret A as the payoff matrix of a symmetric two-player zero-sum game, where the two players play strategies π,q∈ΔKπ,q∈ _K. Player π receives payoff (π,q)=π⊤AqP(π,q)=π Aq, and player q receives −(π,q)-P(π,q). The corresponding Nash equilibrium is given by the following minimax formulation [79]: (π⋆,q⋆)=(argmaxπminq(π,q),argminqmaxπ(π,q)). (π ,q )= ( _π _qP(π,q),\ _q _πP(π,q) ). (1) By symmetry, both players share the same equilibrium strategy, and the solution is called von Neumann winner [25] or maximal lottery [50, 32]. The equilibrium is well suited to intransitive preferences because it depends only on pairwise comparisons and always exists by the minimax theorem. Additional properties, including Condorcet consistency and related consistency axioms, are discussed in Appendix E. 4 Context-dependent agent evaluation from selective feedback We now formulate context-dependent agent evaluation from offline, selectively observed relative feedback as a contextual game and define its equilibrium. Setting: ∙ Agents: Let ℳ=1,…,KM=\1,…,K\ denote the candidate agents, which perform tasks specified by the context X∈X (e.g., a prompt, task, language, domain, or user group). A menu m⊂ℳm is a subset of agents being compared, and let Q denote the collection of all possible menus. For each context, Sm∈0,1S^m∈\0,1\ indicates whether menu m was selected to generate the feedback, YmY_m. ∙ Relative feedback: The feedback YmY_m is relative, represented by an ordered partition of the selected menu, i.e., Ym=(B1≻⋯≻Br),Bi≠∅,Bi∩Bj=∅ for i≠j,⋃i=1rBi=m, Y_m=(B_1 ·s B_r), B_i≠ , B_i∩ B_j= \ for i≠ j, _i=1^rB_i=m, (2) where r is the number of blocks, and where agents within the same block are tied and earlier blocks are preferred. The above various forms of relative feedback, including pairwise preferences, partial rankings, and winner-of-subset feedback (see Table 5). For example, pairwise feedback corresponds to |m|=2|m|=2. ∙ Logged data: We write the logged data as O=(X,Sm:m∈,SmYm:m∈)O= (X,\ \S^m\ :\ m \,\ \S^mY_m\ :\ m \ ) and observe i.i.d. samples n=Oii=1n∼ℙD_n=\O_i\_i=1^n . Pairwise outcomes: For each menu m, the feedback YmY_m naturally induces a pairwise outcome for every j,k⊂m\j,k\⊂ m: Zjkm=j≻Ymk−k≻Ymj∈−1,0,1, Z_jk^m=1\j _Y_mk\-1\k _Y_mj\∈\-1,0,1\, (3) which satisfies Zjkm=−ZkjmZ^m_jk=-Z^m_kj and where Zjkm=0Z^m_jk=0 denotes a tie. We are then interested in the context-dependent mean pairwise outcome, defined as gjkm(x)=[Zjkm∣X=x]g^m_jk(x)=E[Z^m_jk X=x], which quantifies the average collective preference of agent j over agent k under context x and menu m. Contextual payoff: We then aggregate context-dependent mean pairwise outcomes across menus into a contextual payoff matrix (PM). Definition 1 (Contextual payoff matrix). Let jk=m∈:j,k⊆mQ_jk=\m :\j,k\ m\ be the set of menus containing the pair j,k\j,k\. Let ℱ=fjk:[−1,1]jk→[−1,1]∣j,k∈ℳ,j≠kF=\f_jk:\ [-1,1]^Q_jk→[-1,1] j,k ,j≠ k\ denote set of smooth, odd functions that serve as menu aggregators, with fkj=fjkf_kj=f_jk for every j≠kj≠ k. Then, the contextual payoff matrix is defined by aggregating the menu-specific mean outcomes gjkm(x)g^m_jk(x) via the menu aggregators fjk∈ℱf_jk : A(x)=(Ajk(x))j,k∈ℳ,where Ajk(x)=fjk(gjkm(x):m∈jk)(j≠k), A(x)= (A_jk(x) )_j,k , A_jk(x)=f_jk ( \g^m_jk(x)\ :\ m _jk \ ) (j≠ k), (4) with Ajj(x)=0A_j(x)=0 for every j∈ℳj . Remark 1. The contextual PM characterizes the expected pairwise preferences under a given context, which reflects the collective preference of the population. Since gkjm(x)=−gjkm(x)g^m_kj(x)=-g^m_jk(x), we have Akj(x)=−Ajk(x)A_kj(x)=-A_jk(x). Thus, A(x)A(x) is skew-symmetric. Remark 2. A simple instantiation of the aggregators is the uniformly weighted combination fjk(gjk)=1|jk|∑m∈jkgjkmf_jk(g_jk)= 1|Q_jk| _m _jkg_jk^m. In practice, users can customize the aggregator to their needs, for example, to assign more or less weight to feedback from certain menus. See Appendix F for more instantiations. Contextual equilibrium: Based on the contextual PM, we formulate a regularized contextual game and define its equilibrium. Definition 2 (Contextual game and its equilibrium). Let Ω be continuously differentiable on a neighborhood of ΔK _K and κ-strongly convex on ΔK _K, where κ>0κ>0. We consider a regularized two-player zero-sum game, where the expected payoff between two players with strategies π,q∈ΔKπ,q∈ _K is given by FΩ(π,q,x)=π⊤A(x)q−[Ω(π)−Ω(q)]F_ (π,q;x)=π A(x)q-[ (π)- (q)]. The regularized contextual equilibrium is the minimax solution of the optimization problem: π⋆(x)=argmaxπ∈ΔKminq∈ΔKFΩ(π,q,x):=π⊤A(x)q−[Ω(π)−Ω(q)]. π (x)= _π∈ _K\ _q∈ _K\ F_ (π,q;x):=π A(x)q-[ (π)- (q)]. (5) Since FΩ(π,q,x)=−FΩ(q,π,x)F_ (π,q;x)=-F_ (q,π;x), the game is symmetric and zero-sum. Strong convexity implies that the associated self-play operator is strongly monotone, which ensures uniqueness of the equilibrium and which also ensures Lipschitz continuity to perturbations of the PM [24, 74] (see Appendix C for details). Further, the regularization term can be used to control the equilibrium according to constraints in practice. For example, one can incorporate deployment considerations such as agent cost or encourage properties such as sparsity. In practice, a common choice is to combine a linear term for the deployment cost with an L2L_2 regularizer; i.e., Ω(π)=λ2‖π‖22+∑j=1Kcjπj, (π)= λ2\|π\|_2^2+ _j=1^Kc_j _j, where cjc_j is the cost of deploying agent j. Target. Our aim to learn the context-to-equilibrium mapping x↦π⋆(x)x π (x) defined in Eq. (5). Here, uniqueness of the equilibrium ensures that this mapping is well-defined. We then interpret the support of the contextual equilibrium (i.e. supp(π⋆(x))=k:πk⋆(x)>0supp(π (x))=\k:π _k(x)>0\) as the set of winning agents for the given context x. We make standard identifiability assumptions (see Assumption 1), such as positivity and missing at random [69], so that we can identify the contextual PM from observed data through the context-dependent mean outcomes μ0,jkm(x)μ^m_0,jk(x): gjkm(x)=[Zjkm∣X=x]=[Zjkm∣X=x,Sm=1]:=μ0,jkm(x)for m∈jk. g^m_jk(x)=E[Z^m_jk X=x]=E[Z^m_jk X=x,S^m=1]:=μ^m_0,jk(x) m _jk. (6) Hence, identification of the contextual PM, and thus its equilibrium, follows from Eqs. (4) and (5) (see Appendix J.2 for details). Nuisances: We refer to μ0,jkm(x)μ^m_0,jk(x) and e0m(x)e^m_0(x) as nuisance functions and write η0=(0,0) _0=( μ_0, e_0), where (i) 0=(μ0m)m∈ μ_0=( _0^m)_m , μ0m=(μ0,jkm)j,k∈m,j≠k _0^m=(μ^m_0,jk)_j,k∈ m,\,j≠ k, is the collection of the outcome regressions and (i) 0=(e0m)m∈ e_0=(e_0^m)_m are the selection propensities across menus. Stability: We adapt the stability result for equilibrium mappings [24] to our context-dependent setting (see Appendix C.5 for the derivation and definition of ∥⋅∥⋆\|· \|_ .). Proposition 1 (Contextual payoff stability). For any two contexts x,x′∈x,x , ‖π⋆(x)−π⋆(x′)‖≤κ−1‖(A(x)−A(x′))π⋆(x′)‖⋆≤κ−1‖A(x)−A(x′)‖⋆. \|π (x)-π (x ) \|≤κ^-1 \|(A(x)-A(x ))π (x ) \|_ ≤κ^-1 \|A(x)-A(x ) \|_ . (7) Proposition 1 shows that the equilibrium is Lipschitz continuous with respect to changes in the contextual PM, which implies that errors in the contextual PM propagate directly to the equilibrium. Hence, in order to accurately learn the contextual equilibrium, we need to accurately estimate the contextual PM A(x)A(x). However, this is challenging: some pairwise entries of the PM are missing, and, because A(x)A(x) depends on estimated nuisance functions, a naïve plug-in estimator can inherit first-order bias from the nuisance estimation error. To remove this first-order bias, we propose a novel Neyman-orthogonal equilibrium learning method in the next section. 5 Orthogonal equilibrium learning Overview: Our NashEval framework consists of two stages (see Figure 2): in Stage 1, we estimate the contextual payoff matrix A^(x) A(x) from the logged feedback, and in Stage 2, we use estimated contextual payoff matrix to learn the context-to-equilibrium mapping. Importantly, we show in Section 5.1 that a naïve, plug-in equilibrium learner is subject to the so-called plug-in bias, which can lead to a suboptimal equilibrium. As a remedy, we develop a Neyman-orthogonal equilibrium learner, and, to do so, we first propose a debiased payoff matrix (DPM) that is robust to nuisance misspecification (Section 5.2), which we use in Stage 1. In Section 5.3, we present a tailored orthogonal loss based on DPM for learning the contextual equilibrium in Stage 2. Finally, we show that our NashEval framework has favorable theoretical guarantees, such as Neyman-orthogonality and a quasi-oracle convergence rate (Section 5.4). 5.1 Why a naïve plug-in equilibrium learner is problematic Plug-in equilibrium learner. A natural approach is to first estimate the outcome regressions μ^jkm μ^m_jk using an arbitrary machine learning method and then “plug” them into the menu aggregator. This yields A^jkPI(x)=1|jk|∑m∈jkμ^jkm(x),where μ^jkm(x)=^[Zjkm∣X=x,Sm=1]. A^PI_jk(x)= 1|Q_jk| _m _jk μ^m_jk(x), μ^m_jk(x)= E[Z^m_jk X=x,S^m=1]. (8) where we consider the mean aggregator for simplicity. We can then learn the equilibrium π^PI(x) π^PI(x) using the estimated contextual PM A^PI(x) A^PI(x). However, by Proposition 1, errors in the estimated contextual PM propagate directly to the learned equilibrium. In particular, the error of the equilibrium is Lipschitz-bounded by the error of the contextual PM estimator: ‖π^PI(x)−π⋆(x)‖≤1κ|jk|∑m∈jk‖Δμm(x)‖\| π^PI(x)-π (x)\|≤ 1κ|Q_jk| _m _jk\| μ^m(x)\|). Hence, errors in μ^m μ^m affect the estimated contextual PM (and therefore the learned equilibrium) at first order. In semiparametric statistics, such sensitivity to direct plug-in estimation is commonly referred to as plug-in bias [44]. The effect can be particularly pronounced when κ is small. Key idea: orthogonal learning. To reduce such sensitivity to nuisance estimation errors, NashEval builds on orthogonal statistical learning [15, 33]. Let η η denote the estimated nuisance functions and suppose the equilibrium mapping πθ _θ is learned by minimizing θ^=argminθ∈Θℒ(θ,η^):=[ℓ(πθ(X),A(X,η^))] θ= _θ∈ L(θ; η):=E [ ( _θ(X),A(X; η)) ] (9) Our goal thus is to construct a loss for which the gradient with respect to θ is locally insensitive to errors in the nuisance functions. Formally, a loss is Neyman-orthogonal if DηDθℒ(θ,η0)[θ^−θ,η^−η0]=0,∀θ∈Θ D_ηD_θL(θ; _0)[ θ-θ, η- _0]=0, ∀θ∈ (10) where DηD_η and DθD_θ are the Gateaux derivatives w.r.t. η and θ, under directions hθ=θ^−θh_θ= θ-θ and hη=η^−η0h_η= η- _0. Hence, orthogononality means that the gradient DθℒD_θL is robust to perturbations hηh_η around its true value. Intuitively, orthogonality thus removes the first-order effect of nuisance estimation errors on the learning objective, thus allowing nuisance errors to enter the final estimation error only through higher-order terms [33]. In the following, we adapt this idea to both stages of NashEval. However, doing so is nontrivial and requires a tailored orthogonalization for each stage. For Stage 1, we construct a debiased payoff matrix that is orthogonal to nuisance estimation errors. For Stage 1, we use this estimator to define an orthogonal loss for learning the contextual equilibrium. In Section 5.3, we formally establish the property of Neyman-orthogonality. 5.2 Stage 1: Debiased payoff matrix In this section, we construct the debiased payoff matrix (DPM) for Stage 1 that is robust to nuisance estimation errors. We begin with the average payoff ψjk=X[Ajk(X)]=X[fjk(μ0,jkm(X)m∈jk)] _jk=E_X[A_jk(X)]=E_X [f_jk(\μ^m_0,jk(X)\_m _jk) ]. The efficient influence function (EIF) of the average payoff provides a correction (i.e., debiasing term) to the plug-in payoff estimator, and, using this correction, we can construct a debiased PM that removes first-order sensitivity to nuisance estimation errors. Definition 3 (Debiased payoff matrix). For generic nuisances η=(,)η=( μ, e), we define the debiased payoff matrix as () AjkDB(x,η):=0[Γjk(O,η)∣X=x],(j≠k)ADB(x,η):=(AjkDB(x,η))j,k∈ℳ, A^DB_jk(x;η):=E_0 [ _jk(O;η) X=x ],(j≠ k) A^DB(x;η):= (A^DB_jk(x;η) )_j,k , (11) with diagonal entries Ajj(x)A_j(x) set to 0. Here, Γjk(O,η) _jk(O;η) is the EIF-based pseudo-outcome of the payoff (see Appendix J.3 for details): Γjk(O,η)=fjk(μjkm(X)m∈jk)⏟plug-in term+∑m∈jk∂fjk∂um(μjkm′(X)m′∈jk)Smem(X)Zjkm−μjkm(X)⏟debiasing term _jk(O;η)= f_jk\! (\μ^m_jk(X)\_m _jk )_plug-in term+ _m _jk ∂ f_jk∂ u_m\! (\μ^m _jk(X)\_m _jk ) S^me^m(X) \Z^m_jk-μ^m_jk(X) \_debiasing term Theorem 1 (Properties of the debiased payoff matrix). Under Assumptions 1–3, we have: (i) AjkDB(x,η0)=0[Γjk(O,η0)∣X=x]=Ajk(x)A^DB_jk(x; _0)=E_0 [ _jk(O; _0) X=x ]=A_jk(x); and (i) for every perturbation h=(hμ,he)h=(h_μ,h_e), the debiased payoff is Neyman-orthogonal w.r.t. η: DηAjkDB(x,η)[h]|η=η0=0.D_ηA^DB_jk(x;η)[h] |_η= _0=0. Proof. See Appendix J.4. ∎ The theorem shows that the debiased payoff matrix recovers the true contextual PM when the nuisances are correctly specified, and that it is locally insensitive to nuisance perturbations. More precisely, under smoothness condition, we can show that the the pointwise bias induced by nuisance misspecification is bounded by second-order nuisance errors: |AjkDB(x,η)−Ajk(x)|≤Lf2‖Δμ(x)‖22+∑m∈jk|∂fjk∂um(μ(x))||Δem(x)|em(x)|Δμm(x)|. |A^DB_jk(x;η)-A_jk(x) |≤ L_f2 \| μ(x) \|_2^2+ _m _jk | ∂ f_jk∂ u_m (μ(x) ) | | e^m(x)|e^m(x)\,| μ^m(x)|. (12) where ∇fjk∇ f_jk is LfL_f-Lipschitz. We formally derive this bound in Appendix J.5. Compared with plug-in estimator, nuisance errors affect the debiased payoff matrix only through a squared outcome-error term and an outcome–propensity error product. In practice, given fitted nuisances η^=(^,^) η=( μ, e), we construct DPM estimator A^DB(x,η^) A^DB(x; η) by regressing Γjk(O,η^) _jk(O; η) on X for each pair (j,k)(j,k) with j≠kj≠ k, and set A^jjDB:=0 A^DB_j:=0. 5.3 Stage 2: Orthognal equilibriamy learning Figure 2: Overview of our NashEval. In Stage 1, we estimate the contextual payoff matrix using the debiased payoff matrix estimator (DPME). In Stage 2, we use the estimated payoff matrix to learn the context-to-equilibrium mapping via an orthogonal loss. In Stage 2, we learn the the context-to-equilibrium mapping πθ(⋅) _θ(·) using the estimated contextual PM from Stage 1. A straightforward approach would be to solve the estimated contextual games fore each context and then use the resulting equilibria as labels. However, repeatedly solving such games is computationally expensive and thus not scalable. Instead, we directly learn the context-to-equilibrium mapping using a tailored, differentiable training loss using gradient-based optimation. To construct this loss, we build upon the gap function, which reformulates equilibrium computation as a differentiable optimization problem for a fixed payoff matrix [4, 37] (see Appendix C.4 for a background). We extend the gap function to our contextual setting with stochastic payoffs, and, to do so, we combine it with our DPM from Stage 1 to obtain a orthogonal loss for learning π⋆(⋅)π (·): Definition 4 (Orthogonal gap loss). For a generic nuisance η, let ADB(x,η)A^DB(x;η) be the population pseudo-outcome regression target in Eq. (11). We define the population orthogonal gap loss as ℒ(θ,η)=X[GΩ(πθ(X),ADB(X,η),X)], (θ;η)=E_X [G_ ( _θ(X);A^DB(X;η),X ) ], (13) where GΩG_ is the regularized gap function, defined as GΩ(π,A,x)=maxq∈ΔK−FΩ(π,q,x)=maxq∈ΔK⟨−Aπ,π−q⟩+Ω(π)−Ω(q). G_ (π;A,x)= _q∈ _K \-F_ (π,q;x) \= _q∈ _K \ -Aπ,\ π-q + (π)- (q) \. (14) Theorem 2 (Differentiability and Neyman-orthogonality). Under Assumptions 2–4, the orthogonal gap loss ℒ(θ,η)L(θ;η) is differentiable with respect to θ for every fixed nuisance η satisfying Assumption 2. Under Assumption 1, the loss is also universally Neyman-orthogonal: for every θ∈Θθ∈ and every pair of directions (hθ,hη)(h_θ,h_η) with bounded hηh_η, it holds that DηDθℒ(θ,η0)[hθ,hη]=0,∀θ∈Θ. D_ηD_θL(θ; _0)[h_θ,h_η]=0, ∀θ∈ . (15) Proposition 2 (Oracle recovery under realizability). Let Assumptions 1, 3, and 4 hold, and let us assume the policy class is realizable, i.e., there exists θ0∈Θ _0∈ such that πθ0(x)=π⋆(x) _ _0(x)=π (x) for almost every x. Then, under the oracle nuisance η0 _0, we have argminθ∈Θℒ(θ,η0)=θ∈Θ:πθ(x)=π⋆(x) for almost every x, _θ∈ L(θ; _0)= \θ∈ : _θ(x)=π (x) for almost every x \, (16) and the minimum population gap risk equals zero. Proof. We prove Theorem 2 and Proposition 2 in Appendices J.7 and J.6, respectively. ∎ Intuitively, the gap function measures the largest advantage available to an optimal opponent against a candidate strategy π and equals zero at equilibrium. We replace the fixed contextual PM A with the debiased payoff matrix ADB(X,η)A^DB(X;η), which depends on the nuisance function η, and average over contexts to obtain a population gap risk. Theorem 2 shows that our proposed loss is universally Neyman-orthogonal and therefore locally insensitive to nuisance estimation errors. Procedure: In practice, training NashEval framework proceeds in two stages. (1) We estimate the nuisance functions η η using KCFK_ CF-fold cross-fitting [15]. For each fold, we fit the nuisance functions on the remaining KCF−1K_ CF-1 folds and evaluate the pseudo-outcomes Γjk(O,η^) _jk(O; η) on the held-out fold. We then regress the cross-fitted pseudo-outcomes on X to obtain A^DB(⋅,η^) A^DB(·; η). (2) We minimize the empirical orthogonal gap loss to obtain πθ _ θ: θ^∈argminθ∈Θℒ^n(θ),where ℒ^n(θ):=1n∑i=1nGΩ(πθ(Xi),A^DB(Xi,η^),Xi). θ∈ _θ∈ L_n(θ), L_n(θ):= 1n _i=1^nG_ \! ( _θ(X_i); A^DB(X_i; η),X_i ). (17) At inference time, the learned parameter θ θ is used to predict the contextual equilibrium πθ^(x⋆) _ θ(x_ ) for a new context x⋆∈Xx_ ∈ X. The corresponding support supp(πθ^(x⋆))supp( _ θ(x_ )) then provides the predicted set of winners that best align with the collective preference. For a downstream decision-making task with some utility function (k,x)U(k,x), one can select a deterministic winner via argmaxk∈supp(πθ^(x⋆))(k,x⋆) _k ( _ θ(x_ ))U(k,x_ ). 5.4 Theoretical guarantees We provide theoretical guarantees for the learned equilibrium under our empirical orthogonal gap loss. To measure the quality of the equilibrium, we introduce the regularized exploitability, which is the regularized analogue of a standard measure of equilibrium quality in two-player zero-sum games and which is commonly used to evaluate how close a learned policy is to the true Nash equilibrium [92]. For a symmetric game with context x, the exploitability of the learned policy πθ _ θ under the true contextual payoff matrix A(x)A(x) is given by the regularized gap function ExplA(x)(πθ^(x)):=GΩ(πθ^(x),A(x),x). _A(x) ( _ θ(x) ):=G_ ( _ θ(x);A(x),x ). (18) We define the the corresponding average exploitability as Expl(πθ^):=X[ExplA(X)(πθ^(X))]Expl( _ θ):=E_X[Expl_A(X)( _ θ(X))], where X∼PXX P_X. Theorem 3 (Empirical error bound for average exploitability). Let Assumptions 1–4 and 5–6 in Appendix J.1 hold. Further, let rμ,re→0r_μ,r_e→ 0 be the nuisance convergence rates and eAe_A the payoff regression error in Assumption 6. Let ℒ L be the population counterpart of ℒ^n L_n. Then, the empirical minimizer θ θ in Eq. (17) satisfies Expl(πθ^)≤4infθ∈ΘExpl(πθ)+4supθ∈Θ|ℒ^(θ)−ℒ^n(θ)|+Op(K2κeA2+rμ4+e¯−2rμ2re2).Expl( _ θ)≤ 4 _θ∈ Expl( _θ)+4 _θ∈ | L(θ)- L_n(θ) |+O_p\! ( K^2κ \e_A^2+r_μ^4+ e^-2r_μ^2r_e^2 \ ). (19) Corollary 1 (Quasi-oracle convergence rate). Under standard assumptions (see Appendix J.9), the empirical minimizer θ θ achieves the same exploitability rate as the minimization with oracle payoff matrix A(x)A(x). Proof. See Appendix J.8, J.9 for the proof. ∎ Theorem 3 shows that, for NashEval, the nuisance estimation errors affect the exploitability rate only through higher-order terms, whereas, for the plug-in learner, the corresponding contribution of the nuisance error term would be rμ2r_μ^2). In the following, we verify the theoretical advantage of NashEval over the plug-in learner through numerical experiments. 6 Experiments Baselines. We group the baselines into two categories:: (1) Global+intransitive baselines: Maximal lottery [52], Robust maximal lottery [46], and Pluralistic leaderboard [38] (2) Contextual+transitive baselines: Bradley–Terry (BT-Plug-in) [9], BT-regularized, and BT-debiased [34]. We refer to our method as NashEval-debiased. We further compare to plug-in learner from Section 5.2 called NashEval-plug-in to demonstrate the benefits of debiasing. NashEval-oracle serves as oracle upper-bound on the performance; therein, we replace η η in NashEval by the true η0 _0 and keep everything else unchanged. Since our framework is model-agnostic, we instantiate NashEval and the baselines with the same machine learning backbone to ensure fair comparison (see Appendix I for details). Metrics. We evaluate equilibrium quality through average unregularized exploitability and winner-set recovery using the F1F_1 score of the predicted equilibrium support. For RQ2 , we additionally report the head-to-head game value, and, for the cost analysis, the average strict win rate. See Appendix I.1 for details. RQ1 Does NashEval improve a equilibrium learning? We first verify the theoretical benefits of our method using a simulated dataset, where the true equilibrium is known. We consider three forms of relative feedback generated by NvN_v voters with Nv=1,3,5N_v=1,3,5. We simulate with K=5K=5 agents and d=5d=5-dimensional contexts (see Appendix G for details). Results. Figure 3 shows the results. (i) Across all three feedback forms, our NashEval framework outperforms the baselines when Nv≥3N_v≥ 3 and thus performs best. In particular, NashEval-debiased consistently performs closest to NashEval-oracle in terms of both exploitability and support F1F_1. (i) When Nv=1N_v=1, preferences are transitive, and NashEval performs comparably to BT-debiased, which is expected. (i) NashEval-debiased achieves better exploitability and F1F_1 scores than the NashEval-plug-in, which demonstrates the benefit of Neyman-orthogonality. (iv) Finally, BT-Reg and BT-debiased have higher exploitability and lower F1F_1 score for Nv≥3N_v≥ 3. This suggests that regularization or debiasing alone cannot overcome misspecification from imposing transitivity when collective preferences are intransitive. Figure 3: RQ1 Equilibrium quality using a simulated dataset with ground-truth. Shown: mean exploitability and F1F_1 score on simulated dataset for #\#voters=1,3,5=1,3,5 over 5 random seeds. RQ2 How does NashEval perform in larger-scale, realistic agent evaluation settings? We evaluate NashEval in two large-scale real-world agent evaluation settings: (1) evaluating LLMs on RouterBench [41], using the model evaluations of Li et al. [56], and (2) evaluating reinforcement learning (RL) agents in the multi-objective highway-driving environment of MO-Gymnasium [31], which is built on HighwayEnv [55]. For RouterBench, we use ten LLMs and 8,7428,742 prompts. For the driving task, we train five RL agents on 256 configurations (i.e., context) with different reward models. The pairwise preference data are sampled from three external judges, each of which has internally transitive preferences (see Appendix H.2 and H.3 for details). We then measure how closely our NashEval is to to the true contextual evaluation. We further report the game value against NashEval-debiased, which quantifies whether each baseline has a higher or lower collective preference compared to NashEval. Table 2: Performance comparison for LLMs using RouterBench [41]. Method Exploitability [↓ ] Support F1F_1 [↑ ] Game value [↑ ] NashEval-debiased (ours) 0.380±0.0000.380± 0.000 0.300±0.0010.300± 0.001 0.000±0.0000.000± 0.000 NashEval-plug-in 0.398±0.0010.398± 0.001 0.287±0.0010.287± 0.001 −0.016±0.001-0.016± 0.001 BT-debiased / Borda 0.395±0.0010.395± 0.001 0.274±0.0010.274± 0.001 −0.010±0.001-0.010± 0.001 BT-Plug-in 0.401±0.0030.401± 0.003 0.270±0.0020.270± 0.002 0.014±0.0030.014± 0.003 Maximal lottery 0.423±0.0000.423± 0.000 0.246±0.0000.246± 0.000 −0.030±0.000-0.030± 0.000 Robust maximal lottery 0.423±0.0000.423± 0.000 0.246±0.0000.246± 0.000 −0.030±0.000-0.030± 0.000 Pluralistic leaderboard 0.470±0.0000.470± 0.000 0.242±0.0000.242± 0.000 −0.136±0.000-0.136± 0.000 Table 3: Performance comparison for RL agents using the MO-Highway benchmark [31]. Method Exploitability [↓ ] Support F1F_1 [↑ ] Game value [↑ ] NashEval-debiased (ours) 0.066±0.0070.066± 0.007 0.708±0.0230.708± 0.023 0.000±0.0000.000± 0.000 NashEval-plug-in 0.068±0.0000.068± 0.000 0.713±0.0000.713± 0.000 −0.027±0.006-0.027± 0.006 BT-debiased / Borda 0.099±0.0030.099± 0.003 0.525±0.0140.525± 0.014 −0.017±0.004-0.017± 0.004 BT-Plug-In 0.232±0.0000.232± 0.000 0.438±0.0000.438± 0.000 −0.072±0.004-0.072± 0.004 Maximal lottery 0.105±0.0000.105± 0.000 0.505±0.0000.505± 0.000 −0.006±0.006-0.006± 0.006 Robust maximal lottery 0.105±0.0000.105± 0.000 0.505±0.0000.505± 0.000 −0.006±0.006-0.006± 0.006 Pluralistic leaderboard 0.217±0.0000.217± 0.000 0.556±0.0000.556± 0.000 −0.147±0.004-0.147± 0.004 Results. Tables 3 and 3 show the results. (1) Overall, our NashEval-debiased achieves the lowest mean exploitability on both RouterBench and the RL-agent benchmark and thus performs best. (2) On both real-world benchmarks, it also achieves lower exploitability and higher support F1F_1 than BT-debiased / Borda and the global evaluation baselines. This confirms that our NashEval is more accurate in recovering the contextual evaluation under intransitive preferences. (3) The head-to-head game values favor NashEval-debiased over all competitors on both benchmarks. This demonstrates that NashEval-debiased better reflects the underlying collective preferences. Insights. We examine the frequency of how often each agent is selected as the winner in the RouterBench dataset. We use the same setup as in RQ2. We divide the test data by domain and then compute the average winning rate of each agent by domain. We visualize the frequency as heatmap in Figure 4. We observe that the estimated evaluation is largely consistent with the approximated true evaluation, which provides further evidence that NashEval is effective in capture context-dependent variation in agent performance. For example, frontier reasoning-based models (e.g., GPT-5, Gemini 2.5 Pro) perform better on the Math domain, in line with our expectation. Figure 4: Insights. Winner frequency for each agent in the RouterBench dataset. Left: estimated evaluation from NashEval-debiased. Right: (approximated) true evaluation. Conclusion. We develop, to the best of our knowledge, the first game-theoretic framework for context-dependent agent evaluation under potentially intransitive collective preferences. Our experiments confirm the theoretical properties of NashEval and demonstrate the benefit of our Neyman-orthogonal equilibrium learning. References [1] K. Abe and Y. Kaneko (2021) Off-policy exploitability-evaluation in two-player zero-sum markov games. In AAMAS, Cited by: Appendix A. [2] S. Ameli, S. Zhuang, I. Stoica, and M. W. Mahoney (2025) A statistical framework for ranking LLM-based chatbots. In ICLR, Cited by: Appendix A. [3] E. Areyan Viqueira, C. Cousins, E. Upfal, and A. Greenwald (2019) Learning equilibria of simulation-based games. arXiv preprint arXiv:1905.13379. Cited by: Appendix A. [4] A. Auslender (1973) Brève communication. résolution numérique d’inégalités variationnelles. Revue française d’automatique informatique recherche opérationnelle. Mathématique 7 (R2), p. 67–72. Cited by: §C.4, §5.3. [5] D. Balduzzi, K. Tuyls, J. Perolat, and T. Graepel (2018) Re-evaluating evaluation. In NeurIPS, Cited by: Appendix A. [6] P. L. Bartlett and S. Mendelson (2002) Rademacher and Gaussian complexities: risk bounds and structural results. Journal of Machine Learning Research 3, p. 463–482. Cited by: §J.1. [7] V. Bengs, A. Saha, and E. Hüllermeier (2022) Stochastic contextual dueling bandits under linear stochastic transitivity models. In ICML, p. 1764–1786. Cited by: Appendix A. [8] P. J. Bickel, C. A. J. Klaassen, Y. Ritov, and J. A. Wellner (1998) Efficient and adaptive estimation for semiparametric models. Springer, New York. Note: Reprint of the 1993 original External Links: ISBN 978-0-387-98473-5 Cited by: Appendix A, §D.1. [9] R. A. Bradley and M. E. Terry (1952) Rank analysis of incomplete block designs: i. the method of paired comparisons. Biometrika 39 (3/4), p. 324–345. Cited by: Appendix A, §2, §6. [10] F. Brandl, F. Brandt, and H. G. Seedig (2016) Consistent probabilistic social choice. Econometrica 84 (5), p. 1839–1880. Cited by: Appendix A, §E.3. [11] F. Brandl, F. Brandt, and C. Stricker (2022) An analytical and experimental comparison of maximal lottery schemes. Social Choice and Welfare 58 (1), p. 5–38. External Links: Document Cited by: Appendix A. [12] F. Brandl and F. Brandt (2020) Arrovian aggregation of convex preferences. Econometrica 88 (2), p. 799–844. External Links: Document Cited by: Appendix A. [13] F. Brandt (2017) Rolling the dice: recent results in probabilistic social choice. In Trends in Computational Social Choice, Cited by: Appendix A, §2, §3. [14] C. Chen, Y. Zhang, X. Liu, Z. Xie, S. D. Liu, and N. Jiang (2026) Offline two-player zero-sum markov games with KL regularization. In ICML, Note: arXiv:2605.13025 Cited by: Appendix A. [15] V. Chernozhukov, D. Chetverikov, M. Demirer, E. Duflo, C. Hansen, W. Newey, and J. Robins (2018) Double/debiased machine learning for treatment and structural parameters. The Econometrics Journal 21 (1), p. C1–C68. External Links: Document Cited by: Appendix A, §J.1, §J.1, §5.1, §5.3. [16] W. Chi, V. Chen, A. N. Angelopoulos, W. Chiang, A. Mittal, N. Jain, T. Zhang, I. Stoica, C. Donahue, and A. Talwalkar (2025) Copilot Arena: a platform for code LLM evaluation in the wild. In Proceedings of the 42nd International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 267, p. 10354–10382. Cited by: Appendix A. [17] C. Chiang, T. Ishida, and M. Sugiyama (2025) LLM routing with dueling feedback. arXiv preprint arXiv:2510.00841. Cited by: Appendix A, §2. [18] W. Chiang, L. Zheng, Y. Sheng, A. N. Angelopoulos, T. Li, D. Li, B. Zhu, H. Zhang, M. I. Jordan, J. E. Gonzalez, and I. Stoica (2024) Chatbot Arena: an open platform for evaluating LLMs by human preference. In ICML, Cited by: Appendix A, §B.2, §H.1, Table 1, §2. [19] P. F. Christiano, J. Leike, T. B. Brown, M. Martic, S. Legg, and D. Amodei (2017) Deep reinforcement learning from human preferences. In NeurIPS, Cited by: Appendix A. [20] A. H. Copeland (1951) A “reasonable” social welfare function. Note: Mimeographed notes, Seminar on Applications of Mathematics to the Social Sciences, University of Michigan Cited by: §2. [21] Q. Cui and S. Du (2022) When are offline two-player zero-sum markov games solvable?. NeurIPS. Cited by: Appendix A. [22] M. de Condorcet (1785) Essai sur l’application de l’analyse à la probabilité des décisions rendues à la pluralité des voix. Imprimerie Royale, Paris. Cited by: Appendix A, §2, §2. [23] Q. Di, T. Jin, Y. Wu, H. Zhao, F. Farnoud, and Q. Gu (2024) Variance-aware regret bounds for stochastic contextual dueling bandits. In ICLR, Cited by: Appendix A. [24] A. L. Dontchev and R. T. Rockafellar (2009) Implicit functions and solution mappings: a view from variational analysis. Springer Monographs in Mathematics, Springer. Cited by: §C.5, §4, §4. [25] M. Dudík, K. Hofmann, R. E. Schapire, A. Slivkins, and M. Zoghi (2015) Contextual dueling bandits. In COLT, Cited by: Appendix A, §2, §3. [26] M. Dudík, J. Langford, and L. Li (2011) Doubly robust policy evaluation and learning. In ICML, Cited by: Appendix A. [27] B. Dutta and J. Laslier (1999) Comparison functions and choice correspondences. Social Choice and Welfare 16 (4), p. 513–532. Cited by: Appendix A. [28] F. Facchinei and J. Pang (2003) Finite-dimensional variational inequalities and complementarity problems. Springer Series in Operations Research, Springer, New York. Cited by: §J.1, §C.1, §C.1, §C.5.1. [29] J. Fearnley, M. Gairing, P. W. Goldberg, and R. Savani (2015) Learning equilibria of games via payoff queries. Journal of Machine Learning Research 16 (39), p. 1305–1344. Cited by: Appendix A. [30] D. S. Felsenthal and M. Machover (1992) After two centuries, should Condorcet’s voting procedure be implemented?. Behavioral Science 37 (4), p. 250–274. Cited by: Appendix A. [31] F. Felten, L. N. Alegre, A. Nowé, A. L. C. Bazzan, E. G. Talbi, G. Danoy, and B. C. d. Silva (2023) A toolkit for reliable benchmarking and research in multi-objective reinforcement learning. In Advances in Neural Information Processing Systems, Vol. 36. External Links: Link Cited by: §H.3, Table 3, §6. [32] P. C. Fishburn (1984) Probabilistic social choice based on simple voting comparisons. The Review of Economic Studies 51 (4), p. 683–692. Cited by: Appendix A, §2, §2, §3, §3. [33] D. J. Foster and V. Syrgkanis (2023) Orthogonal statistical learning. The Annals of Statistics 51 (3), p. 879–908. External Links: Document Cited by: Appendix A, §J.1, §J.1, §D.3, Appendix D, §5.1, §5.1. [34] D. Frauen, A. Deviyani, M. van der Schaar, and S. Feuerriegel (2026) Nonparametric LLM evaluation from preference data. In ICML, Cited by: Appendix A, Table 1, §2, §6. [35] D. Frauen, M. Schröder, K. Hess, and S. Feuerriegel (2025) Orthogonal survival learners for estimating heterogeneous treatment effects from time-to-event data. In NeurIPS, Cited by: Appendix A. [36] E. Frick, C. Chen, J. Tennyson, T. Li, W. Chiang, A. N. Angelopoulos, and I. Stoica (2025) Prompt-to-leaderboard. arXiv preprint arXiv:2502.14855. Cited by: Appendix A, Appendix A, §B.3, §I.3, §1, Table 1, §2. [37] M. Fukushima (1992) Equivalent differentiable optimization problems and descent methods for asymmetric variational inequality problems. Mathematical Programming 53 (1), p. 99–110. External Links: Document Cited by: §C.4, §5.3, Proposition 4. [38] N. Haghtalab, A. D. Procaccia, H. Shao, S. L. Wang, and K. Yang (2026) Pluralistic leaderboards. In ICML, Cited by: Appendix A, §I.3, §I.3, §1, §2, §6. [39] D. Halpern, E. Micha, A. D. Procaccia, B. Schiffer, I. Shapira, and S. Zhang (2026) AI alignment from social choice perspectives. arXiv preprint arXiv:2606.21550. Note: Accepted for publication in ACM SIGecom Exchanges Cited by: Appendix A. [40] F. R. Hampel (1974) The influence curve and its role in robust estimation. Journal of the American Statistical Association 69 (346), p. 383–393. Cited by: Appendix A. [41] Q. J. Hu, J. Bieker, X. Li, N. Jiang, B. Keigwin, G. Ranganath, K. Keutzer, and S. K. Upadhyay (2024) RouterBench: a benchmark for multi-LLM routing system. In ICML 2024 Agentic Markets Workshop, Note: Poster Cited by: §H.2, Table 3, §6. [42] N. Jiang and L. Li (2016) Doubly robust off-policy value evaluation for reinforcement learning. In ICML, Cited by: Appendix A. [43] P. R. Jordan, Y. Vorobeychik, and M. P. Wellman (2008) Searching for approximate equilibria in empirical games. In AAMAS, p. 1063–1070. Cited by: Appendix A. [44] E. H. Kennedy (2023) Towards optimal doubly robust estimation of heterogeneous causal effects. Electronic Journal of Statistics 17 (2), p. 3008–3049. External Links: Document Cited by: Appendix A, §5.1. [45] E. H. Kennedy (2024) Semiparametric doubly robust targeted double machine learning: a review. In Handbook of Statistical Methods for Precision Medicine, p. 207–236. Cited by: Appendix A, §J.1, §J.1, §D.1, §D.1, §D.1, Appendix D. [46] H. Khalaf, S. L. Wang, D. Halpern, I. Shapira, F. d. P. Calmon, and A. D. Procaccia (2026) Robust AI evaluation through maximal lotteries. In ICML, Cited by: Appendix A, §B.1, §I.3, §I.3, Table 1, §2, §6. [47] E. Kohlberg and J. Mertens (1986) On the strategic stability of equilibria. Econometrica 54 (5), p. 1003–1037. External Links: Document Cited by: §C.5.1. [48] E. Korkmaz (2026) The axiomatic value of regularization in AI alignment from human preferences. In ICML, Note: Spotlight Cited by: Appendix A, §E.3. [49] G. H. Kramer (1973) On a class of equilibrium conditions for majority rule. Econometrica 41 (2), p. 285–297. Cited by: §2. [50] G. Kreweras (1965) Aggregation of preference orderings. In Mathematics and Social Sciences I, Cited by: Appendix A, §2, §3. [51] G. Laffond, J. Laslier, and M. Le Breton (1993) The bipartisan set of a tournament game. Games and Economic Behavior 5 (1), p. 182–201. External Links: Document Cited by: Appendix A. [52] M. Lanctot, K. Larson, Y. Bachrach, L. Marris, Z. Li, A. Bhoopchand, T. Anthony, B. Tanner, and A. Koop (2023) Evaluating agents using social choice theory. arXiv preprint arXiv:2312.03121. Cited by: Appendix A, §B.1, Table 1, §2, §6. [53] T. Larsson and M. Patriksson (1994) A class of gap functions for variational inequalities. Mathematical Programming 64 (1), p. 53–79. Cited by: §C.4, Proposition 4. [54] J. Laslier (1997) Tournament solutions and majority voting. Springer-Verlag. Cited by: Appendix A, §2. [55] E. Leurent (2018) An environment for autonomous driving decision-making. Note: GitHub repository External Links: Link Cited by: §H.3, §6. [56] H. Li, Y. Zhang, Z. Guo, C. Wang, S. Tang, Q. Zhang, Y. Chen, B. Qi, P. Ye, L. Bai, Z. Wang, and S. Hu (2026) LLMRouterBench: a massive benchmark and unified framework for LLM routing. In Findings of the Association for Computational Linguistics: ACL 2026, M. Liakata, V. P. Moreira, J. Zhang, and D. Jurgens (Eds.), Cited by: §H.2, §6. [57] V. Melnychuk, D. Frauen, J. Schweisthal, and S. Feuerriegel (2026) Orthogonal representation learning for estimating causal quantities. In AISTATS, Cited by: Appendix A. [58] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Kumaran, D. Wierstra, S. Legg, and D. Hassabis (2015) Human-level control through deep reinforcement learning. Nature 518 (7540), p. 529–533. External Links: Document Cited by: §H.3. [59] R. Munos, M. Valko, D. Calandriello, M. Gheshlaghi Azar, M. Rowland, Z. D. Guo, Y. Tang, M. Geist, T. Mesnard, C. Fiegel, A. Michi, M. Selvi, S. Girgin, N. Momchev, O. Bachem, D. J. Mankowitz, D. Precup, and B. Piot (2024) Nash learning from human feedback. In ICML, Cited by: Appendix A. [60] X. Nie and S. Wager (2021) Quasi-oracle estimation of heterogeneous treatment effects. Biometrika 108 (2), p. 299–319. Cited by: Appendix A. [61] S. Omidshafiei, C. Papadimitriou, G. Piliouras, K. Tuyls, M. Rowland, J. Lespiau, W. M. Czarnecki, M. Lanctot, J. Perolat, and R. Munos (2019) α-Rank: multi-agent evaluation by evolution. Scientific Reports 9, p. 9937. Cited by: Appendix A. [62] I. Ong, A. Almahairi, V. Wu, W. Chiang, T. Wu, J. E. Gonzalez, M. W. Kadous, and I. Stoica (2025) RouteLLM: learning to route LLMs from preference data. In ICLR, Cited by: Appendix A, §1, Table 1, §2. [63] L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. L. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, J. Schulman, J. Hilton, F. Kelton, L. Miller, M. Simens, A. Askell, P. Welinder, P. F. Christiano, J. Leike, and R. Lowe (2022) Training language models to follow instructions with human feedback. In NeurIPS, Cited by: Appendix A. [64] R. Rafailov, A. Sharma, E. Mitchell, C. D. Manning, S. Ermon, and C. Finn (2023) Direct preference optimization: your language model is secretly a reward model. In NeurIPS, Cited by: Appendix A. [65] A. Raffin, A. Hill, A. Gleave, A. Kanervisto, M. Ernestus, and N. Dormann (2021) Stable-Baselines3: reliable reinforcement learning implementations. Journal of Machine Learning Research 22 (268), p. 1–8. External Links: Link Cited by: §H.3. [66] R. L. Rivest and E. Shen (2010) An optimal single-winner preferential voting system based on game theory. In COMSOC, Cited by: Appendix A. [67] C. Rosset, C. Cheng, A. Mitra, M. Santacroce, A. Awadallah, and T. Xie (2024) Direct Nash optimization: teaching language models to self-improve with general preferences. arXiv preprint arXiv:2404.03715. Cited by: Appendix A. [68] M. Rowland, S. Omidshafiei, K. Tuyls, J. Perolat, M. Valko, G. Piliouras, and R. Munos (2019) Multiagent evaluation under incomplete information. In NeurIPS, Cited by: Appendix A. [69] D. B. Rubin (1974) Estimating causal effects of treatments in randomized and nonrandomized studies. Journal of Educational Psychology 66 (5), p. 688–701. Cited by: §J.1, §4. [70] D. B. Rubin (1976) Inference and missing data. Biometrika 63 (3), p. 581–592. Cited by: §J.1. [71] A. Saha (2021) Optimal algorithms for stochastic contextual preference bandits. In NeurIPS, Cited by: Appendix A. [72] H. Schechter Vera, S. Dua, B. Zhang, D. Salz, R. Mullins, et al. (2025) EmbeddingGemma: powerful and lightweight text representations. arXiv preprint arXiv:2509.20354. Cited by: §I.2. [73] M. Sion (1958) On general minimax theorems. Pacific Journal of Mathematics 8 (1), p. 171–176. Cited by: §C.3. [74] S. Sokota, R. D’Orazio, J. Z. Kolter, N. Loizou, M. Lanctot, I. Mitliagkas, N. Brown, and C. Kroer (2023) A unified approach to reinforcement learning, quantal response equilibria, and two-player zero-sum games. In International Conference on Learning Representations, Cited by: §J.1, §C.2, §4. [75] P. Stone (2011) The luck of the draw: the role of lotteries in decision making. Oxford University Press. External Links: Document Cited by: Appendix A. [76] G. Swamy, C. Dann, R. Kidambi, Z. S. Wu, and A. Agarwal (2024) A minimaximalist approach to reinforcement learning from human feedback. In ICML, Cited by: Appendix A. [77] T. N. Tideman (1987) Independence of clones as a criterion for voting rules. Social Choice and Welfare 4 (3), p. 185–206. External Links: Document Cited by: Appendix A, §2. [78] A. W. van der Vaart (1998) Asymptotic statistics. Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press. External Links: Document Cited by: §D.1. [79] J. von Neumann (1928) Zur theorie der gesellschaftsspiele. Mathematische Annalen 100 (1), p. 295–320. Cited by: §3. [80] Y. Vorobeychik (2010) Probabilistic analysis of simulation-based games. ACM Transactions on Modeling and Computer Simulation 20 (3), p. 16:1–16:25. External Links: Document Cited by: Appendix A. [81] M. P. Wellman (2006) Methods for empirical game-theoretic analysis. In AAAI, p. 1552–1556. Cited by: Appendix A. [82] Y. Wu, T. Jin, H. Lou, F. Farnoud, and Q. Gu (2024) Borda regret minimization for generalized linear dueling bandits. In ICML, Cited by: Appendix A. [83] Y. Wu, Z. Sun, H. Yuan, K. Ji, Y. Yang, and Q. Gu (2025) Self-play preference optimization for language model alignment. In ICLR, Cited by: Appendix A. [84] A. Xu, S. Bansal, Y. Ming, S. Yavuz, and S. Joty (2025) Does context matter? ContextualJudgeBench for evaluating LLM-based judges in contextual settings. In Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 9541–9564. Cited by: §1. [85] Y. Yue, J. Broder, R. Kleinberg, and T. Joachims (2012) The k-armed dueling bandits problem. Journal of Computer and System Sciences 78 (5), p. 1538–1556. Cited by: Appendix A, §2. [86] Y. Zhang, M. Li, D. Long, X. Zhang, H. Lin, B. Yang, P. Xie, A. Yang, D. Liu, J. Lin, F. Huang, and J. Zhou (2025) Qwen3 embedding: advancing text embedding and reranking through foundation models. arXiv preprint arXiv:2506.05176. Cited by: §I.2. [87] Y. Zhang, C. Chen, and N. Jiang (2026) Beyond pessimism: offline learning in KL-regularized games. arXiv preprint arXiv:2604.06738. Cited by: Appendix A. [88] Y. Zhang, D. Yu, B. Peng, L. Song, Y. Tian, M. Huo, N. Jiang, H. Mi, and D. Yu (2025) Iterative Nash policy optimization: aligning LLMs with general preferences via no-regret learning. In ICLR, Cited by: Appendix A. [89] Z. Zhang, X. Hu, Y. Huang, K. Zhang, R. Chen, Y. Liu, Q. Wen, K. Xu, X. Zhang, N. Z. Gong, and L. Sun (2026) RankLLM: weighted ranking of LLMs by quantifying question difficulty. In ICLR, Cited by: Appendix A. [90] Z. Zhao, S. Jin, and Z. M. Mao (2024) Eagle: efficient training-free router for multi-LLM inference. In Proceedings of the Workshop on Machine Learning for Systems at NeurIPS 2024, p. 1–8. Cited by: Appendix A. [91] H. Zhong, W. Xiong, J. Tan, L. Wang, T. Zhang, Z. Wang, and Z. Yang (2022) Pessimistic minimax value iteration: provably efficient equilibrium learning from offline datasets. In ICML, Proceedings of Machine Learning Research, Vol. 162, p. 27117–27142. Cited by: Appendix A. [92] M. Zinkevich, M. Johanson, M. Bowling, and C. Piccione (2007) Regret minimization in games with incomplete information. In NeurIPS, Cited by: §5.4. Appendix A Related Work Agent evaluation from relative feedback. Relative feedback, particularly pairwise preferences, is widely used to evaluate generative agents. Chatbot Arena and its successor LMArena collect head-to-head judgments on LLM responses [18], while Copilot Arena applies the same evaluation to coding agents [16]. A standard approach aggregates these comparisons with a score-based model such as Bradley–Terry to produce a global leaderboard [9, 18]. Subsequent work proposes improved evaluation and ranking procedures by modeling ties and dependence among agents [2], estimating nonparametric ranking functionals [34], learning prompt-dependent Bradley–Terry scores [36], or incorporating question difficulty into rankings [89]. Frick et al. [36] is contextual but retains a Bradley–Terry model at each prompt. Despite these differences, these methods ultimately summarize agents by scalar scores or an ordered leaderboard, which fail to represent intransitive preferences. To accommodate potentially intransitive preferences, Rivest and Shen [66] use the equilibrium distribution of the pairwise majority-margin game as a randomized single-winner voting rule. Recent agent-evaluation work extends this social-choice perspective to heterogeneous tasks or populations through locally stable top-k sets [38] and maximal lotteries [52, 46]. These social-choice methods nevertheless aggregate feedback across contexts to produce a global evaluation, which can obscure context-dependent variation in agents’ relative capabilities. Other related game-theoretic methods rank agents from empirical interaction payoffs using Nash averaging or α-Rank, including under incomplete payoff information [5, 61, 68]. To our knowledge, no existing method simultaneously captures context-dependent variation in agents’ relative capabilities and represents the collective preference of a heterogeneous population. Social choice and maximal lotteries. Social choice theory studies how individual preferences can be aggregated into collective decisions, including settings where majority preferences are cyclic and no deterministic Condorcet winner exists [22, 13]. A central randomized rule is the maximal lottery, introduced by Kreweras [50] and developed by Fishburn [32]: it selects a distribution over alternatives that maximizes the worst-case expected majority margin, equivalent to an equilibrium strategy of the induced two-player zero-sum game. Subsequent work has studied maximal lotteries and related tournament-based rules through game-theoretic, axiomatic, computational, and empirical analyses [30, 51, 54, 27, 12, 11]. Maximal lotteries extend the Condorcet principle and satisfy strong population- and composition-consistency properties, while robustness to cloned alternatives is a standard criterion for voting rules [77, 10]. More broadly, lotteries are considered suitable for decision making when a deterministic choice is undesirable [75]. Recent work brings this perspective to AI alignment by treating heterogeneous human feedback as a preference-aggregation problem and studying the axiomatic consequences of aggregation and regularization [39, 48]. Unlike this literature, which aggregates preferences into a global majority profile without modeling context-dependent variation, we learn a context-specific maximal lottery (with convex regularization) from selectively observed offline feedback. Double/debiased machine learning. Double/debiased machine learning (DML) builds on semiparametric efficiency theory [8, 45] to support valid inference on target parameters while using flexible machine learning models for nuisance functions. Its main tools include influence-function analysis in robust estimation [40], efficient influence functions from semiparametric theory [8], and Neyman-orthogonal moment equations [15]. Foster and Syrgkanis [33] extend this principle to general two-stage statistical learning: Neyman-orthogonality removes the first-order effect of nuisance estimation error on the target loss, allowing the learner to attain quasi-oracle rates under suitable conditions [60]. Such orthogonal learning paradigm is used in many scenarios, such as heterogeneous treatment-effect estimation [44], survival analysis [35], off-policy evaluation and learning [26, 42], and representation learning for causal quantities [57]. We show that the same principle applies to contextual equilibrium learning from stochastic relative feedback by constructing a debiased payoff estimator and an orthogonal gap loss. LLM routing from preferential feedback. LLM routing studies the selection of the best LLM(s) for a given prompt. A specific line of work is to learn a predictive router from pairwise preferential feedback [90, 62, 17, 36]. This can be viewed as a special case of our general formulation: the context is the prompt, the agents are the LLMs. However, these works assume that the preference is transitive: they assign implicit contextual scores and then approximate the preference via a utility function (or link function). This leads to misspecification when preferences cycle. In contrast, our framework does not assume transitivity and instead learns a contextual equilibrium that yields better alignment. Game-theoretic RLHF. Canonical RLHF methods learn a scalar reward model from pairwise comparisons [19, 63, e.g.,], while direct preference optimization eliminates explicit reward-model fitting but retains the Bradley–Terry preference assumption [64]. To accommodate general, potentially intransitive preferences, recent works instead formulate language-model alignment as a two-player zero-sum game and trains a Nash policy through self-play or no-regret optimization [59, 76, 67, 83, 88]. Although conceptually similar, its goal is to learn the response-generation Nash policy, which is different to our agent evaluation setting with the target being the Nash policy over a set of candidates. Contextual dueling bandits. This line of work studies how to learn a context-dependent policy when the bandit can only collect pairwise or subsetwise preferential feedback [85, 25, 71, 7, 23, 82, e.g.]. Saha [71], Bengs et al. [7] and Di et al. [23] all implicitly assume stochastic transitivity, which we do not. Wu et al. [82] uses Borda score to define a transitivity-robust regret, but still learns a single winner that is neither Condorcet-consistent nor independent of clones (Appendix E). Dudík et al. [25] is the first to propose the concept of ”von Neumann winner” in the dueling bandit setting, which allows for preference cycles and upon which we build our NashEval. But their estimator of the preference matrix is not debiased and thus suffers from plug-in bias. Finally, all of these works are targeted for an interactive setting, where the bandit iteratively selects which pair to compare, digests the feedback, and then approximates the optimal policy. In contrast, our work is targeted for an offline setting, where the feedback is collected beforehand. Thus, these works are not applicable to our setting. Offline reinforcement learning in games. Offline RL in games studies how to learn equilibrium policies from offline multi-agent behaviors, and thus is related to our setting. Existing methods learn such policies directly from observed rewards, with or without KL regularization [21, 91, 87, 14]. Closest to our debiasing approach, Abe and Kaneko [1] construct doubly robust off-policy estimators of the exploitability of candidate policy profiles and use them for policy selection; we instead debias the contextual PM and learn the entire context-to-equilibrium mapping with an orthogonal gap loss. Finally, RL in games has a fundamentally different observation model: the payoff is sampled directly from the reward model for joint actions, whereas we observe only the relative feedback of the agents within a menu. Hence, these methods are not applicable to our setting. Equilibrium learning from stochastic/noisy games. A related literature studies equilibrium approximation when the payoff function is unavailable analytically but can be accessed through payoff queries or stochastic simulation. This line develops search procedures, probabilistic error bounds, and finite-sample guarantees for equilibria computed from empirical games [81, 43, 80, 3, 29, e.g.,]. However, these equilibrium learning methods does not apply debiasing w.r.t. the nuisance functions, and thus are subject to plug-in bias. In contrast, our approach uses a debiased payoff matrix (DPM) that is robust to nuisance misspecification, and optimizes a Neyman-orthogonal loss to learn the contextual equilibria. Appendix B Additional experiments We complement the main experiments with additional results. In Section B.1, we compare pooled and prompt-specific equilibria on RouterBench to illustrate how aggregation can hide contextual winners. In Section B.2, we examine subgroup-specific equilibria and apply NashEval-debiased to human feedback from LM Arena. We use these analyses to illustrate variation in agent capabilities across contexts and the presence of multiple agents in an equilibrium’s support. Because we do not know the true equilibria in LM Arena, we treat comparisons with empirical subgroup lotteries as descriptive evidence rather than an accuracy assessment. In Section B.3, we compare cost–performance trade-offs to assess whether contextual equilibrium evaluation remains useful when we account for inference costs. In Section B.4, we replace the outcome and payoff regression backbones with MLPs to examine whether the main synthetic findings persist under an alternative model instantiation. In Section B.5, we vary the regularization strength to assess the sensitivity of exploitability and winner-set recovery to this choice. B.1 Aggregation hides true contextual winners Existing maximal-lottery-based agent evaluators aggregate preferences across all or a subset of contexts to compute a global maximal lottery [52, 46]. Using the RouterBench dataset, we show that this aggregation can hide the true contextual winners and lead to suboptimal evaluation. We use MMLUPro and LiveCodeBench as examples. Figures 5 and 6 compare the equilibrium distribution obtained from aggregated preferences with the distributions for individual prompts (i.e., contexts). The aggregated preferences yield a Condorcet winner: Gemini 2.5 Pro for MMLUPro and GPT-5 for LiveCodeBench. Across individual prompts, however, the contextual equilibria are highly heterogeneous and need not contain a Condorcet winner. In some contexts, the aggregated winner is not even in the contextual equilibrium support (see Contexts 2 and 3 for LiveCodeBench). Therefore, aggregation hides the true contextual winners and can lead to suboptimal evaluation. This motivates our work on a contextual evaluator that adaptively selects the best agent or agents for each context. Figure 5: Equilibrium distributions for aggregated MMLUPro preferences and individual prompts. Aggregation yields a Condorcet winner, whereas the contextual equilibria are heterogeneous and need not contain NashEval-debiased. Therefore, aggregation hides the true contextual winners and can lead to suboptimal evaluation. Figure 6: Equilibrium distributions for aggregated LiveCodeBench preferences and individual prompts. Aggregation yields a Condorcet winner, whereas the contextual equilibria are heterogeneous and need not contain NashEval-debiased. Therefore, aggregation hides the true contextual winners and can lead to suboptimal evaluation. B.2 Experiment on LM Arena We demonstrate our NashEval-debiased on the Arena Human Preference 140K data. In LMArena, a user compares responses from two anonymously presented language models and supplies a preference, a tie, or a both-bad judgment [18]. The full release contains 135,634 human votes involving 53 models and 128,336 distinct first-user prompts (Appendix H.1). We restrict both training and analysis to the 17,480 comparisons between the 15 models in Table 9, which cover 17,296 distinct prompts. B.2.1 Heterogeneity of the agent capability across contexts In this section, we provide evidence of the heterogeneity of agent capability across contexts in the LM Arena dataset. We stratify the LMArena data by discrete context attributes (see Table 8,8) and construct majority-margin matrices using win-minus-loss counts for each stratification, with unobserved model pairs replaced by ties. We then compute an equilibrium distribution for each subgroup having at least 90% pair coverage. When multiple equilibria exist, we choose the one with minimal l2l_2 norm. Results. We quantify heterogeneity using pairwise total-variation distances between the equilibrium distributions. For each single- or two-attribute combination, we report the mean and maximum total-variation distance in Table 4. We further visualize the subgroup-specific equilibria in Figures 7 and 8. These equilibria are highly heterogeneous across subgroups. For example, Gemini 2.5 Pro is not in the equilibrium support for either (code,math)=(No,yes)(code,math)=(No,yes) or (yes,no)(yes,no). Therefore, a single global equilibrium cannot represent how agent performance varies across contexts. (a) Code (b) Mathematics (c) Code and mathematics Figure 7: Subgroup-specific equilibrium distributions across code and mathematics contexts. Each plotted circle is an agent in the equilibrium support, and the y-axis shows its equilibrium probability. Further stratification can introduce new agents into the support (e.g., MiniMax M1), indicating that a global equilibrium does not reflect context-specific agent capabilities. Figure 8: Subgroup-specific equilibrium distributions across language, code, instruction-following, and mathematics contexts. Each plotted circle is an agent in the equilibrium support, and the y-axis shows its equilibrium probability. Agent capabilities vary substantially across contexts. Table 4: Heterogeneity of subgroup-specific equilibrium distributions in LMArena illustrated by total variation within each attribution composition. Only subgroups with at least 90% pair coverage are included. Subgroups vary substantially in their winning agents within each stratification. Stratification Subgroups Mean TV Max TV Distinct winners Single attribute Language 5 0.612 0.866 3 Code 2 0.900 0.900 2 Instruction following 2 0.000 0.000 1 Mathematics 2 0.500 0.500 1 Two attributes Language × code 6 0.460 0.600 1 Language × instruction following 6 0.736 1.000 4 Language × mathematics 5 0.734 1.000 4 Code × instruction following 4 0.438 0.875 2 Code × mathematics 3 1.000 1.000 3 Instruction following × mathematics 3 0.333 0.500 1 For this experiment, we define the context using only the recorded language, code, mathematics, and instruction-following labels. We display a selection of subgroups that have at least 100 comparisons and observed feedback for at least 94 of the 105 selected-model pairs. The true context-specific equilibrium is unavailable in LM Arena. We therefore use the empirical maximal lottery within each subgroup as a reference, i.e. disagreement or agreement do not necessarily imply the accuracy of the method. Figure 9: Attribute-specific equilibria for six LM Arena subgroups defined by language, code, mathematics, and instruction-following labels. Panel A shows the NashEval-debiased equilibrium probability of each selected model. Panel B shows the regularized maximal lottery from pairwise win-minus-loss counts pooled within the same subgroup. Both panels use ρ=0.01ρ=0.01 and report percentages. Note: this is different from the heatmap Figure 4, which reports the winner frequencies of the agents. Results. Figure 9 shows that the evaluation of our NashEval-debiased is largely consistent with the empirical maximal lottery, which indicates the effectiveness of our NashEval. For English prompts without code, mathematics, or instruction following, both equilibria assign all probability to Gemini 2.5 Pro. For English coding prompts without mathematics or instruction following, the predicted equilibrium assigns all probability to DeepSeek R1, while the empirical lottery assigns it 71.4%. The predicted equilibrium changes across these contexts: DeepSeek R1 receives no probability in the first group but is the sole supported model in the second. For English instruction-following prompts without code or mathematics, the predicted equilibrium assigns 43.1% to DeepSeek R1 and 42.8% to Gemini 2.5 Pro, whereas the empirical lottery assigns 58.3% to GPT-4.1. Claude Opus 4 receives zero predicted probability in all six displayed groups, despite having the highest listed price. B.3 Cost-constrained performance. Experimental setup. We reuse the RouterBench payoff models from RQ2 across five seeds and 500 test prompts. For NashEval-debiased, NashEval-plug-in, and Maximal lottery, we incorporate the prices in Table 11 through Ωβ(π)=ρ2‖π‖22+βc~⊤π,ρ=0.01,c~j=cj−minkckmaxkck−minkck. _β(π)= ρ2\|π\|_2^2+β c π, ρ=0.01, c_j= c_j- _kc_k _kc_k- _kc_k. (20) Here, cjc_j is the cost of 1,0001,000 input and 1,0001,000 output tokens. We vary β and compare against BT-cost, which maximizes its predicted pairwise score under a per-prompt expected-cost budget following Theorem 1 of Frick et al. [36] (Appendix I.3). We compare all methods by realized mean expected cost. For the equilibrium methods, we use Eq. (20) with the price weights β∈0.025t:t=0,…,12∪0.35,0.4,0.5,0.75,1,1.5,2,3,5,10,20. β∈\0.025t:t=0,…,12\∪\0.35,0.4,0.5,0.75,1,1.5,2,3,5,10,20\. (21) Metrics. We report unregularized exploitability against an unrestricted opponent and average strict win rate against the ten single-agent opponents with equal weight. We give ties, including self-comparisons, zero credit and retain them in the denominator. Results. Figures 10 and 11 show that NashEval-debiased offers the strongest empirical trade-off through much of the intermediate-cost region, achieving the pareto frontier among intermediate cost ranges for both metrics. This demonstrates that our method is able to produce the cost-constrained contextual evaluations that reflect the collective preference of the population. Figure 10: Cost–exploitability trade-offs on RouterBench across five seeds and 500 test prompts. Our method largely achieves the empirical Pareto frontier over costs of approximately USD 22–1111 per 1,0001,000 standardized requests among the evaluated policies. Therefore, under the same cost budge, our method produces contextual evaluations that better reflect the collective preference of the population. Figure 11: Cost–average-win-rate trade-offs on RouterBench. Our method largely achieves the empirical Pareto frontier at intermediate cost range [2,11][2,11]. Therefore, under the same cost budge, our method produces contextual evaluations that better reflect the collective preference of the population. B.4 Ablations on backbone. Experimental setup. We conduct ablation study on the backbone of the outcome nuisance estimator and the second-stage payoff regressor on the simulated dataset from RQ1. We jointly replace LightGBM in these two components with multilayer perceptrons (MLPs). We retain the LightGBM propensity estimator and compute equilibria with the same numerical solver as in RQ1, without introducing a learned policy predictor. For NashEval-oracle, we use the same MLP payoff regressor as for NashEval-debiased, but construct the pseudo-outcomes with the true nuisances. NashEval-plug-in uses the fold-averaged MLP outcome predictions without a separate payoff regression. The remained is unchanged compared with RQ1. We evaluate unregularized exploitability and support F1F_1, using the same support threshold of 10−310^-3, and summarize each metric by its mean and standard deviation across 5 random seeds.seeds. We use two hidden layers with widths (64,64)(64,64) for each outcome nuisance and (128,128)(128,128) for each pairwise payoff regressor, with ReLU activations. We train both networks with Adam at learning rate 3×10−33× 10^-3 and an L2L_2 weight penalty of 10−410^-4, using batch sizes of 512512 and 1,0241,024, respectively. We allow at most 300300 epochs and apply early stopping on a held-out subset of the corresponding training data with patience 12. We fix these MLP settings before evaluating the test sets. We regress the unclipped debiased pseudo-outcomes, clip predicted margins to [−1,1][-1,1], and impose antisymmetry before solving for the equilibrium. We report the mean and std of the (unregularized) exploitability and F1F_1 score over five random seeds in Figure 12. For Nv≥3N_v≥ 3, our NashEval consistently outperforms other non-oracle baselines. For Nv=1N_v=1, preferences are transitive and the BT-model-based baselines are slightly better. The result is consistent with the main findings in RQ1 in Section 6. This proves the effectiveness of our NashEval regardless of the backbone instantiations, and that the higher performance is attributed to the method itself. Figure 12: Ablation study on the outcome nuisance and payoff backbone on the simulated dataset. We note that our NashEval outperforms the non-oracle baselines on Nv≥3N_v≥ 3 and achieves comparable performance with BT-based baselines on Nv=1N_v=1. This result demonstrate the effectiveness of the learning framework itself. B.5 Performance over varying regularization strengths. We investigate the effect of the regularization strength ρ on the performance of our method on the simulated dataset. The setting is similar to RQ1, but we fix the number of voters to 33. Then we vary ρ within the range 0.0,0.001,0.01,0.1,1.0\0.0,0.001,0.01,0.1,1.0\ and compare against other contextual evaluation baselines. We report the mean and std of the (unregularized) exploitability and F1F_1 score over five random seeds in Figure 13. We observe no significant change in both metrics when ρ≤0.01ρ≤ 0.01, with performance slightly decreasing for ρ beyond that range. We also observe a slight improvement in F1F_1 score when ρ is increased from 0.10.1 to 1.01.0. This is likely due to the sparsity imposed by the L2L_2 regularizer, which reduces the size of the support and thus the chance of false positives. In summary, our NashEval is robust to the choice of ρ. Figure 13: Mean ± std Mean exploitability and F1F_1 score on simulated dataset for #\#voters=3=3 over 5 random seeds, plotted against varying regularization strengths ρ. B.6 Comparison with the numerical equilibrium solver A naíve approach is to only estimate the contextual PM, and then solve the equilibrium every time a new context is encountered. We compare our NashEval-debiased and NashEval-plug-in with the numerical equilibrium solver using both the debiased and plug-in PM estimators. We adopt the same settings as in RQ1, where we use unregularized exploitability and support F1F_1 scores to evaluate the quality of the learned equilibrium while recording the mean runtime during inference. We use a custom solver that enumerates over all possible supports (2K−12^K-1) to search for equilibria that satisfy the KKT conditions. Figure 14: Performance comparison of our NashEval with the numerical solver. Mean ± std Mean exploitability and F1F_1 score on simulated dataset for #\#voters=1,3,5=1,3,5 over 5 random seeds. Results. Results on Figure 14 show that our NashEval performs comparably to the numerical solver when number of voters is larger than 1. Runtime comparison is given in Figure 15. We see that our NashEval is much more efficient during inference: The runtime of NashEval-debiased remain stable, while the inference runtime of the numerical solver increases exponentially when K increases. Figure 15: Inference runtime comparison between our NashEval-debiased and the numerical equilibrium solver. Our NashEval is much more efficient during inference time. Appendix C Preliminaries of Game Theory In this appendix, we introduce the game-theoretic concepts needed to understand our solution concept and methods. In Section C.1, we introduce variational inequalities and monotone operators, which provide the main tools for characterizing and solving equilibria in two-player zero-sum games. In Section C.2, we introduce the self-play operator and show that its variational-inequality solutions coincide with the symmetric equilibria of our regularized game. In Section C.3, we prove existence and uniqueness of the contextual regularized equilibrium. In Section C.4, we introduce the gap function and establish its consistency, equilibrium-error control, and differentiability. In Section C.5, we prove that the equilibrium is stable under perturbations of the payoff matrix. Notation and standing conventions. We conduct the game-theoretic analysis at a fixed context x. Unless stated otherwise, we suppress the context from the payoff notation and write A=A(x)A=A(x). The regularizer Ω does not depend on x. Recall that A=−A⊤A=-A and that Ω is continuously differentiable on a neighborhood of ΔK _K and κ-strongly convex on ΔK _K with respect to ∥⋅∥\|·\|, where κ>0κ>0. Thus, for every p,q∈ΔKp,q∈ _K, Ω(q)≥Ω(p)+⟨∇Ω(p),q−p⟩+κ2‖q−p‖2. (q)≥ (p)+ ∇ (p),q-p + κ2\|q-p\|^2. (22) Game-theoretic setting. Game theory studies strategic interactions in which each player’s payoff depends on the strategies chosen by all players. A game specifies the players, their feasible strategy sets, their payoff functions, and a solution concept that describes stable joint behavior. In this work, we study a contextual, regularized, two-player zero-sum game over the shared mixed-strategy simplex ΔK _K. At each context x, the row player receives FΩ(π,q,x)F_ (π,q;x) and the column player receives −FΩ(π,q,x)-F_ (π,q;x), where the skew-symmetric matrix A(x)A(x) encodes collective pairwise preferences and the context-independent regularizer Ω induces strong convexity. We seek the symmetric saddle point of this game, which coincides with its Nash equilibrium and defines the contextual von Neumann winner π⋆(x)π (x). C.1 Variational inequalities and monotone operators In this subsection, we introduce variational inequalities and strong monotonicity, which provide the equilibrium characterization and uniqueness argument used throughout this appendix. A variational inequality is the problem of finding, for an operator V:ΔK→ℝKV: _K ^K and the convex compact set ΔK _K, a point π⋆∈ΔKπ ∈ _K such that ⟨V(π⋆),π−π⋆⟩≥ 0for all π∈ΔK. V(π ),\ π-π \ ≥\ 0 all π∈ _K. (23) We write VI(V,ΔK)VI(V, _K) for this problem. Geometrically, Eq. (23) says that −V(π⋆)-V(π ) makes a non-acute angle with every feasible direction at π⋆π , so no feasible direction decreases the objective represented by V. See Facchinei and Pang [28]. The operator property that governs uniqueness is monotonicity. An operator V is monotone on ΔK _K if ⟨V(p)−V(q),p−q⟩≥ 0for all p,q∈ΔK, V(p)-V(q),\ p-q \ ≥\ 0 all p,q∈ _K, and κ-strongly monotone with respect to ∥⋅∥\|·\| if the stronger inequality ⟨V(p)−V(q),p−q⟩≥κ‖p−q‖2 V(p)-V(q),\ p-q \ ≥\ κ\,\|p-q\|^2 (24) holds for the same quantifiers. We use two standard facts [28]: the gradient of a differentiable κ-strongly convex function is κ-strongly monotone, and a strongly monotone VI has at most one solution. In our game, the linear part π↦−Aπ -Aπ contributes no curvature because ⟨−Ad,d⟩=−d⊤Ad=0 -Ad,d =-d Ad=0 for A=−A⊤A=-A . C.2 The self-play operator In this subsection, we define the self-play operator, characterize symmetric equilibria as solutions of its variational inequality, and establish the strong monotonicity needed to prove uniqueness. For the regularized game FΩ(π,q)=π⊤Aq−[Ω(π)−Ω(q)]F_ (π,q)=π Aq-[ (π)- (q)] of Definition 2, define the self-play operator VΩ(π)=−Aπ+∇Ω(π).V_ (π)\ =\ -Aπ+∇ (π). (25) This is the standard self-play operator for a regularized zero-sum game [74]. The next lemma gives its exact saddle-point characterization. Lemma 1 (Self-play variational inequality). A pair (π⋆,π⋆)(π ,π ) with π⋆∈ΔKπ ∈ _K is a symmetric saddle point (i.e. a Nash equilibrium) of FΩF_ if and only if ⟨−Aπ⋆+∇Ω(π⋆),π−π⋆⟩≥ 0for all π∈ΔK, -Aπ +∇ (π ),\ π-π \ ≥\ 0 all π∈ _K, (26) Moreover VΩV_ is κ-strongly monotone with respect to ∥⋅∥\|·\|. Proof. Necessity. Suppose (π⋆,π⋆)(π ,π ) is a saddle point. We fix the column strategy at π⋆π and discard the term Ω(π⋆) (π ), which does not depend on π. The row player then maximizes fπ⋆(π)=π⊤Aπ⋆−Ω(π)f_π (π)\ =\ π Aπ - (π) (27) over ΔK _K. The function fπ⋆f_π is concave because it equals a linear function minus a convex function. The saddle-point property implies that π⋆π maximizes it over the convex set ΔK _K. The first-order optimality condition for this differentiable concave problem is exactly Eq. (26). Sufficiency. Conversely, suppose Eq. (26) holds. By convexity, Ω(π)≥Ω(π⋆)+⟨∇Ω(π⋆),π−π⋆⟩ (π)≥ (π )+ ∇ (π ),π-π for all π∈ΔKπ∈ _K. Hence, for every π, fπ⋆(π)−fπ⋆(π⋆)=⟨Aπ⋆,π−π⋆⟩−[Ω(π)−Ω(π⋆)]≤⟨Aπ⋆−∇Ω(π⋆),π−π⋆⟩≤0, f_π (π)-f_π (π )= Aπ ,π-π - [ (π)- (π ) ]≤ Aπ -∇ (π ),\ π-π ≤ 0, where the final inequality follows from Eq. (26). We add Ω(π⋆) (π ) to both sides and obtain FΩ(π,π⋆)≤FΩ(π⋆,π⋆)F_ (π,π )≤ F_ (π ,π ) for all π∈ΔKπ∈ _K. Therefore, π⋆π is a best response for the row player. For the column player, skew-symmetry gives FΩ(p,q)=−FΩ(q,p)F_ (p,q)=-F_ (q,p), so FΩ(π⋆,q)=−FΩ(q,π⋆)≥−FΩ(π⋆,π⋆)=FΩ(π⋆,π⋆), F_ (π ,q)=-F_ (q,π )\ ≥\ -F_ (π ,π )=F_ (π ,π ), Here we use FΩ(π⋆,π⋆)=(π⋆)⊤Aπ⋆=0F_ (π ,π )=(π ) Aπ =0, which follows from d⊤Ad=0d Ad=0 for skew-symmetric A. Thus, π⋆π is also a best response for the column player, and (π⋆,π⋆)(π ,π ) is a saddle point with value zero. This direction uses skewness twice and fails without it. Strong monotonicity. Let p,q∈ΔKp,q∈ _K and put d=p−qd=p-q. Then ⟨VΩ(p)−VΩ(q),d⟩=−d⊤Ad⏟= 0+⟨∇Ω(p)−∇Ω(q),d⟩=⟨∇Ω(p)−∇Ω(q),d⟩. V_ (p)-V_ (q),d = -\,d Ad_=\,0+ ∇ (p)-∇ (q),d = ∇ (p)-∇ (q),d . (28) The first term vanishes because d⊤Ad=12d⊤(A+A⊤)d=0d Ad= 12d (A+A )d=0 for skew-symmetric A. For the second, we write Eq. (22) twice, once at (p,q)(p,q) and once at (q,p)(q,p): Ω(q)≥Ω(p)+⟨∇Ω(p),q−p⟩+κ2‖d‖2,Ω(p)≥Ω(q)+⟨∇Ω(q),p−q⟩+κ2‖d‖2. (q)\ ≥\ (p)+ ∇ (p),q-p + κ2\|d\|^2, (p)\ ≥\ (q)+ ∇ (q),p-q + κ2\|d\|^2. We add the two inequalities and cancel Ω(p)+Ω(q) (p)+ (q) to obtain ⟨∇Ω(p)−∇Ω(q),d⟩≥κ‖d‖2 ∇ (p)-∇ (q),d ≥κ\|d\|^2. We substitute this result into Eq. (28) and obtain Eq. (24) for VΩV_ . ∎ C.3 Existence and uniqueness In this subsection, we combine the minimax theorem with the self-play characterization to prove that the contextual regularized equilibrium exists, is symmetric, and is unique, which makes the target mapping x↦π⋆(x)x π (x) well defined. Proposition 3 (Existence and uniqueness of the regularized equilibrium). Let A=−A⊤A=-A and let Ω be continuously differentiable on a neighborhood of ΔK _K and κ-strongly convex on ΔK _K, with κ>0κ>0. Then the game FΩF_ of Definition 2 admits a saddle point, every saddle point is symmetric of the form (π⋆,π⋆)(π ,π ), the game value is zero, and π⋆π is unique. Consequently π⋆(x)π (x) is a well-defined single-valued function of x. Proof. Existence. The strategy set ΔK _K is compact and convex, and FΩF_ is upper-semicontinuous and concave in π and lower-semicontinuous and convex in q. Hence Sion’s minimax theorem [73] gives maxπ∈ΔKminq∈ΔKFΩ(π,q)=minq∈ΔKmaxπ∈ΔKFΩ(π,q)=:val(FΩ), _π∈ _K\ _q∈ _KF_ (π,q)\ =\ _q∈ _K\ _π∈ _KF_ (π,q)\ =:\ val(F_ ), with both extrema attained, so a saddle point exists. Value zero and symmetry. Skew-symmetry of A gives FΩ(p,q)=−FΩ(q,p)F_ (p,q)=-F_ (q,p) for all p,qp,q, since p⊤Aq=−q⊤Ap Aq=-q Ap and the bracket [Ω(p)−Ω(q)][ (p)- (q)] also changes sign. The game is thus symmetric. If we exchange the roles of the players, we map saddle points to saddle points and negate the value. Hence, val(FΩ)=−val(FΩ)val(F_ )=-val(F_ ), so val(FΩ)=0val(F_ )=0. Let (π⋆,q⋆)(π ,q ) be any saddle point. Because the value is zero and FΩ(p,p)=0F_ (p,p)=0 for every p, antisymmetry implies that (q⋆,π⋆)(q ,π ) is also a saddle point. The standard interchangeability of saddle-point components then implies that (π⋆,π⋆)(π ,π ) and (q⋆,q⋆)(q ,q ) are saddle points. It therefore suffices to establish uniqueness among symmetric saddle points. Uniqueness. By Lemma 1, symmetric saddle points are exactly the solutions of VI(VΩ,ΔK)VI(V_ , _K), so it suffices to show that this variational inequality has at most one solution. Suppose π1,π2∈ΔK _1, _2∈ _K both solve it. We test the inequality for π1 _1 at the feasible point π2 _2 and test the inequality for π2 _2 at the feasible point π1 _1. This gives ⟨VΩ(π1),π2−π1⟩≥ 0,⟨VΩ(π2),π1−π2⟩≥ 0. V_ ( _1),\ _2- _1 \ ≥\ 0, V_ ( _2),\ _1- _2 \ ≥\ 0. We add the two inequalities and write d=π1−π2d= _1- _2. We obtain ⟨VΩ(π1)−VΩ(π2),d⟩≤ 0. V_ ( _1)-V_ ( _2),\ d \ ≤\ 0. On the other hand, Lemma 1 states that VΩV_ is κ-strongly monotone, so ⟨VΩ(π1)−VΩ(π2),d⟩≥κ‖d‖2 V_ ( _1)-V_ ( _2),d ≥κ\|d\|^2. Together, these two bounds imply κ‖π1−π2‖2≤ 0, κ\,\| _1- _2\|^2\ ≤\ 0, and since κ>0κ>0 this forces ‖π1−π2‖=0\| _1- _2\|=0, i.e. π1=π2 _1= _2. The symmetric saddle point is therefore unique. For any saddle point (π⋆,q⋆)(π ,q ), the preceding argument shows that both (π⋆,π⋆)(π ,π ) and (q⋆,q⋆)(q ,q ) are symmetric saddle points. Uniqueness gives π⋆=q⋆π =q , so every saddle point is symmetric and x↦π⋆(x)x π (x) is single-valued. ∎ C.4 Gap functions In this subsection, we specialize gap functions to the self-play variational inequality and establish the properties that make the resulting gap a valid differentiable loss for learning the contextual equilibrium. Gap functions convert a variational inequality into scalar optimization by assigning each candidate solution a nonnegative measure of its violation. The classical construction appears, up to an equivalent change of sign, in Auslender [4]. Fukushima [37] developed a differentiable regularized gap function, and Larsson and Patriksson [53] placed this construction within a broader class of gap functions for variational inequalities. For a general operator V on a feasible set C, the classical gap has the form supy∈C⟨V(z),z−y⟩ _y∈ C V(z),z-y : it is nonnegative because y=zy=z is feasible, and it vanishes exactly when z solves VI(V,C)VI(V,C). In our game, Lemma 1 identifies equilibrium with the variational inequality induced by the self-play operator VΩ(π)=−Aπ+∇Ω(π)V_ (π)=-Aπ+∇ (π). The regularized gap in Definition 4 is equivalently the maximum payoff available to an opponent against π, relative to self-play. Its inner maximizer is the unique regularized best response TΩ(π,A,x):=argminq∈ΔKπ⊤Aq+Ω(q).T_ (π;A,x):= _q∈ _K \π Aq+ (q) \. (29) We define the regularized gap function as GΩ(π,A,x) G_ (π;A,x) :=maxq∈ΔK⟨−Aπ,π−q⟩+Ω(π)−Ω(q) := _q∈ _K \ -Aπ,π-q + (π)- (q) \ =Ω(π)−minq∈ΔKπ⊤Aq+Ω(q) = (π)- _q∈ _K \π Aq+ (q) \ =Ω(π)−π⊤ATΩ(π,A,x)−Ω(TΩ(π,A,x)). = (π)-π AT_ (π;A,x)- (T_ (π;A,x) ). (30) The second equality uses π⊤Aπ=0π Aπ=0, which follows from the skew-symmetry of A. Consequently, we can solve the game by minimizing GΩ(π,A,x)G_ (π;A,x) over ΔK _K. The minimum value is zero, and the equilibrium π⋆(x)π (x) is its unique minimizer. Strong convexity makes the inner best response unique, while Danskin’s theorem supplies a gradient for outer minimization. Proposition 4 (Properties of the gap function). [37, 53] Fix a context x and a payoff A, and let π⋆=π⋆(x)π =π (x) be the equilibrium. Then, for every π∈ΔKπ∈ _K: 1. (Nonnegativity and consistency) The gap is nonnegative and vanishes exactly at the equilibrium, GΩ(π,A,x)≥ 0,GΩ(π,A,x)=0⇔π=π⋆. G_ (π;A,x)\ ≥\ 0, G_ (π;A,x)=0 π=π . (31) 2. (Equilibrium error control) The squared equilibrium error is bounded by the gap: ‖π−π⋆‖2≤2κGΩ(π,A,x). \|π-π \|^2\ ≤\ 2κ\,G_ (π;A,x). (32) 3. (Differentiability) The gap GΩ(⋅,A,x)G_ (·;A,x) is differentiable, with ∇πGΩ(π,A,x)=−ATΩ(π,A,x)+∇Ω(π), _πG_ (π;A,x)=-A\,T_ (π;A,x)+∇ (π), (33) which involves no derivative of TΩT_ with respect to π. Proof. Nonnegativity and consistency. For fixed π, define hπ(q):=π⊤Aq+Ω(q)h_π(q):=π Aq+ (q). Since π⊤Aπ=0π Aπ=0, Eq. (30) gives GΩ(π,A,x)=hπ(π)−minq∈ΔKhπ(q)≥0. G_ (π;A,x)=h_π(π)- _q∈ _Kh_π(q)≥ 0. Equality holds if and only if π minimizes hπh_π over ΔK _K. The first-order condition for this convex problem is ⟨−Aπ+∇Ω(π),q−π⟩≥0for every q∈ΔK. -Aπ+∇ (π),q-π ≥ 0 every q∈ _K. Lemma 1 shows that this condition holds if and only if π is the unique equilibrium π⋆π . Equilibrium error control. Let d=π−π⋆d=π-π . We evaluate the maximum in Eq. (30) at q=π⋆q=π and obtain GΩ(π,A,x)≥⟨−Aπ,d⟩+Ω(π)−Ω(π⋆). G_ (π;A,x)≥ -Aπ,d + (π)- (π ). Strong convexity at π⋆π gives Ω(π)−Ω(π⋆)≥⟨∇Ω(π⋆),d⟩+κ2‖d‖2. (π)- (π )≥ ∇ (π ),d + κ2\|d\|^2. Skew-symmetry gives ⟨−A(π−π⋆),d⟩=0 -A(π-π ),d =0, while the equilibrium variational inequality gives ⟨−Aπ⋆+∇Ω(π⋆),d⟩≥0 -Aπ +∇ (π ),d ≥ 0. Therefore, GΩ(π,A,x)≥κ2‖π−π⋆‖2, G_ (π;A,x)≥ κ2\|π-π \|^2, which proves Eq. (32). Differentiability. The maximization objective in Eq. (30) is strongly concave in q, so it has the unique maximizer TΩ(π,A,x)T_ (π;A,x). For fixed q, skew-symmetry gives ∇π[⟨−Aπ,π−q⟩+Ω(π)−Ω(q)]=−Aq+∇Ω(π). _π [ -Aπ,π-q + (π)- (q) ]=-Aq+∇ (π). Danskin’s theorem evaluates this derivative at the unique maximizer and gives Eq. (33). ∎ C.5 Equilibrium stability with respect to the payoff In this subsection, we apply variational-inequality sensitivity analysis to bound changes in the contextual equilibrium by perturbations of the payoff matrix, thereby establishing the stability result used in the main analysis. We denote the dual norm ∥⋅∥⋆\|·\|_ as ‖v‖⋆:=sup‖u‖≤1⟨v,u⟩,‖B‖⋆:=sup‖u‖≤1‖Bu‖⋆. \|v\|_ := _\|u\|≤ 1 v,u , \|B\|_ := _\|u\|≤ 1\|Bu\|_ . Proof of Proposition 1. We adapt the standard two-VI sensitivity argument [24, Theorem 2F.9]. We retain the perturbation term induced by the payoff matrix. We fix x,x′∈x,x and write π=π⋆(x),π′=π⋆(x′),d=π−π′. π=π (x), π =π (x ), d=π-π . For brevity, we write A=A(x)A=A(x) and A′=A(x′)A =A(x ). By Lemma 1, we test the two equilibrium variational inequalities at π′π and π, respectively, and obtain ⟨−Aπ+∇Ω(π),π′−π⟩ -Aπ+∇ (π),π -π ≥0, ≥ 0, (34) ⟨−A′π′+∇Ω(π′),π−π′⟩ -A π +∇ (π ),π-π ≥0. ≥ 0. (35) We rewrite both inequalities in terms of d and add them to obtain 0 0 ≤⟨Aπ−A′π′−∇Ω(π)−∇Ω(π′),d⟩ ≤ Aπ-A π -\∇ (π)-∇ (π )\,d =⟨(A−A′)π′,d⟩+⟨Ad,d⟩⏟=0−⟨∇Ω(π)−∇Ω(π′),d⟩. = (A-A )π ,d + Ad,d _=0- ∇ (π)-∇ (π ),d . (36) The skew-symmetry of A gives ⟨Ad,d⟩=0 Ad,d =0. Because Ω is differentiable and κ-strongly convex, its gradient is κ-strongly monotone, so ⟨∇Ω(π)−∇Ω(π′),d⟩≥κ‖d‖2. ∇ (π)-∇ (π ),d ≥κ\|d\|^2. We combine this inequality with Eq. (36) and apply dual Hölder to obtain κ‖d‖2≤⟨(A−A′)π′,d⟩≤‖(A−A′)π′‖∗‖d‖. κ\|d\|^2≤ (A-A )π ,d ≤\|(A-A )π \|_*\,\|d\|. If d=0d=0, the claim is immediate. Otherwise, we divide by κ‖d‖κ\|d\| and obtain ‖π⋆(x)−π⋆(x′)‖≤κ−1‖A(x)−A(x′)π⋆(x′)‖∗. \|π (x)-π (x )\|≤κ^-1\|\A(x)-A(x )\π (x )\|_*. Finally, ‖π′‖≤1\|π \|≤ 1 by the norm normalization in the main text, and therefore ‖(A−A′)π′‖∗≤‖A−A′‖⋆‖π′‖≤‖A−A′‖⋆. \|(A-A )π \|_*≤\|A-A \|_ \|π \|≤\|A-A \|_ . This proves both inequalities in Proposition 1. ∎ C.5.1 Instability of the unregularized equilibrium/maximal lottery Without regularization, a single-valued equilibrium selection is not uniformly continuous in the payoff matrix near games with multiple equilibria [47, 28]. For ϵ>0ε>0, we consider the two skew-symmetric games Aϵ+=ϵ(01−10),Aϵ−=−Aϵ+. A_ε^+=ε pmatrix0&1\\ -1&0 pmatrix, A_ε^-=-A_ε^+. The unique maximal lottery of Aϵ+A_ε^+ is e1e_1, while that of Aϵ−A_ε^- is e2e_2. Hence ‖Aϵ+−Aϵ−‖op=2ϵ⟶0,‖e1−e2‖2=2. \|A_ε^+-A_ε^-\|_op=2ε 0, \|e_1-e_2\|_2= 2. Thus, a vanishing payoff perturbation can produce a constant change in the selected equilibrium. The discontinuity occurs at the limiting tie game A=0A=0, whose equilibrium set is the whole simplex. We need additional regularity or strong convexity to obtain a uniformly stable single-valued target. Appendix D Background on efficient influence functions and orthogonal statistical learning Our work draws on efficient semiparametric inference and orthogonal statistical learning. In Section D.1, we define the efficient influence function, use the von Mises expansion to isolate plug-in bias, and specialize these concepts to the average contextual payoff. In Section D.2, we use the efficient influence function to construct a one-step estimator and then convert its uncentered form into a regression target for the contextual payoff. In Section D.3, we extend this bias correction from a scalar functional to our context-to-equilibrium mapping and explain the resulting robustness guarantee. We refer the reader to Kennedy [45] for a detailed treatment of influence-function-based estimation and to Foster and Syrgkanis [33] for the general theory of orthogonal statistical learning. D.1 Efficient influence function Let O∼P0O P_0, where the true distribution P0P_0 belongs to a statistical model P, and let ψ:→ℝψ:P be a scalar target functional. Consider any regular one-dimensional parametric submodel Pt:|t|<ϵ⊆\P_t:|t|<ε\ through P0P_0, with Pt=0=P0P_t=0=P_0 and score s(O)=∂tlogpt(O)|t=0s(O)= . _t p_t(O) |_t=0. The efficient influence function (EIF) φ(O,P0) (O;P_0) is the mean-zero, finite-variance element of the tangent space that represents every pathwise derivative: dtψ(Pt)|t=0=0[φ(O,P0)s(O)],0[φ(O,P0)]=0. . ddtψ(P_t) |_t=0=E_0 [ (O;P_0)s(O) ], _0 [ (O;P_0) ]=0. (37) In a nonparametric model, this representation determines the EIF uniquely. In a semiparametric model, the EIF is the influence function in the tangent space with the smallest variance, and its variance gives the semiparametric efficiency bound [8, 78, 45]. A smooth functional admits the von Mises expansion ψ(P¯)−ψ(P)=∫φ(o,P¯)d(P¯−P)(o)+R2(P¯,P),ψ( P)-ψ(P)= (o; P)\,d( P-P)(o)+R_2( P,P), (38) where R2(P¯,P)R_2( P,P) is a second-order remainder composed of products or squares of differences between components of P¯ P and P. The EIF gives the linear response of ψ to a local perturbation of the data distribution, while R2R_2 collects the nonlinear residual. We set P¯=P P= P and P=P0P=P_0 in Eq. (38). Since ∫φ(o,P^)P^(o)=0 (o; P)\,d P(o)=0, the plug-in error satisfies ψ(P^)−ψ(P0)=−0[φ(O,P^)]+R2(P^,P0).ψ( P)-ψ(P_0)=-E_0 [ (O; P) ]+R_2( P,P_0). (39) Thus, the first term in Eq. (39) is the first-order plug-in bias, conditional on the fitted distribution P P. A direct plug-in estimator retains this term, so its bias can have the same first-order magnitude as the nuisance-estimation error. An EIF-based correction estimates and cancels this linear term, leaving only the second-order remainder [45]. In our setting, we derive the EIF for the average payoff because point evaluation of a conditional regression generally need not be pathwise differentiable when X is continuous [45]. For a pair (j,k)(j,k), this scalar functional is ψjk(P):=P[fjk(μP,jkm(X)m∈jk)], _jk(P):=E_P\! [f_jk\! (\μ^m_P,jk(X)\_m _jk ) ], (40) where ηP=(P,P) _P=( μ_P, e_P) collects the outcome regressions and menu-selection propensities induced by P. Under MAR, positivity, and the regularity conditions of Lemma 2, its EIF is φjk(O,P)=Γjk(O,ηP)−ψjk(P), _jk(O;P)= _jk(O; _P)- _jk(P), (41) where Γjk _jk is defined as Γjk(O,η)=fjk(μjkm(X)m∈jk)+∑m∈jk∂fjk∂um(μjkm′(X)m′∈jk)Smem(X)Zjkm−μjkm(X) _jk(O;η)=f_jk\! (\μ^m_jk(X)\_m _jk )+ _m _jk ∂ f_jk∂ u_m\! (\μ^m _jk(X)\_m _jk ) S^me^m(X) \Z^m_jk-μ^m_jk(X) \ (42) D.2 One-step estimator and pseudo-outcome Suppose that we estimate P0P_0 by P P on an auxiliary sample or through cross-fitting, and let ℙnP_n denote the empirical measure on the evaluation observations. The generic one-step estimator is ψ^1S:=ψ(P^)+ℙn[φ(O,P^)]. ψ^1S:=ψ( P)+P_n [ (O; P) ]. (43) Equation (39) shows why this correction works. The expectation of the added EIF term estimates the negative of the first-order plug-in bias, so the remaining bias is R2(P^,P0)R_2( P,P_0). For the average payoff, Eqs. (41) and (43) reduce the one-step estimator to ψ^jkDB=ℙn[Γjk(O,η^)]. ψ^DB_jk=P_n [ _jk(O; η) ]. (44) The plug-in payoff inside Γjk _jk and the centered EIF correction combine into a single sample average. This construction explains why we call Γjk _jk an EIF-based pseudo-outcome: it is the uncentered EIF, Γjk(O,ηP)=ψjk(P)+φjk(O,P) _jk(O; _P)= _jk(P)+ _jk(O;P). Our target is the contextual payoff Ajk(x)A_jk(x) rather than only its population average. The pseudo-outcome makes this conditional target accessible because 0[Γjk(O,η0)∣X=x]=Ajk(x).E_0 [ _jk(O; _0) X=x ]=A_jk(x). (45) For a generic nuisance η, the same conditional expectation defines the nuisance-indexed surface AjkDB(x,η)A^DB_jk(x;η) in Eq. (11). Theorem 1 shows that this surface equals Ajk(x)A_jk(x) at η0 _0 and has zero first derivative with respect to the nuisance. Equation (12) further shows that its conditional bias depends only on ‖Δμ‖22\| μ\|_2^2 and products of Δem e^m and Δμm μ^m. We therefore regress the cross-fitted values Γjk(O,η^) _jk(O; η) on X to estimate the full contextual surface A^jkDB(x) A^DB_jk(x), which we call the debiased payoff matrix estimator (DPME). D.3 Orthogonal statistical learning Classical one-step estimation typically targets a finite-dimensional functional such as ψjk _jk. Our target x↦π⋆(x)x π (x) is a function, so we use orthogonal statistical learning (OSL) to estimate it through a two-stage risk minimization problem [33]. Let θ index a target function and let η denote nuisance functions estimated in the first stage. For a population risk ℛ(θ,η)R(θ;η), Neyman-orthogonality requires the target gradient to be locally insensitive to nuisance perturbations: DηDθℛ(θ,η)[hθ,hη]|η=η0=0. .D_ηD_θR(θ;η)[h_θ,h_η] |_η= _0=0. (46) When Eq. (46) holds for every θ, we call the risk universally orthogonal. This property removes the first-order effect of nuisance estimation from the learning objective rather than only from a scalar estimator. Neyman-orthogonality. Neyman-orthogonality describes the derivative of a target moment or loss gradient with respect to nuisance functions. An EIF-based correction often constructs an orthogonal moment because it cancels the first-order nuisance derivative identified by the von Mises expansion. Therefore, the EIF can often be used to construct an orthogonal loss function for OSL. We apply the same principle twice. First, the EIF-based pseudo-outcome yields the orthogonal payoff surface ADB(x,η)A^DB(x;η). Second, we insert this surface into the regularized gap risk ℒ(θ,η)=X[GΩ(πθ(X),ADB(X,η),X)].L(θ;η)=E_X\! [G_ ( _θ(X);A^DB(X;η),X ) ]. (47) The derivative DηADB(x,η)[hη]D_ηA^DB(x;η)[h_η] vanishes at η0 _0 by Theorem 1. The chain rule therefore makes the mixed derivative of Eq. (47) vanish for every θ, as formalized in Theorem 2. In practice, we cross-fit η η, construct Γjk(O,η^) _jk(O; η), regress these pseudo-outcomes on X to obtain A^DB A^DB, and minimize the empirical gap loss to learn πθ _ θ. Orthogonality changes the leading nuisance contribution from first order to second order. In our payoff learner, Eq. (12) gives the rate Op(rμ2+rμre)O_p(r_μ^2+r_μr_e) under the stated norm conditions, instead of the Op(rμ)O_p(r_μ) plug-in bias. For a linear aggregator, the term rμ2r_μ^2 vanishes, and the remaining product term gives the usual double-robust property. This higher-order dependence permits slower and more flexible nuisance estimation while retaining the oracle learning rate when the conditions of Corollary 1 hold. This creates favorable empirical generalization properties, and allows the use of general machine learning models. Appendix E Benefits of equilibrium-based evaluation: a social-choice perspective E.1 How do cycles arise? Here we give a simple example of how the cyclic preference arises during the aggregation of voters. Consider three equally weighted raters and three alternatives a,b,ca,b,c, with preferences a≻1b≻1ca _1b _1c, b≻2c≻2ab _2c _2a, and c≻3a≻3bc _3a _3b. Each rater is individually transitive. In the order (a,b,c)(a,b,c), their majority-margin matrices are A(1)=(011−101−1−10),A(2)=(0−1−11011−10),A(3)=(01−1−10−1110). A^(1)= pmatrix0&1&1\\ -1&0&1\\ -1&-1&0 pmatrix, A^(2)= pmatrix0&-1&-1\\ 1&0&1\\ 1&-1&0 pmatrix, A^(3)= pmatrix0&1&-1\\ -1&0&-1\\ 1&1&0 pmatrix. Aggregating the three raters gives A=13∑h=13A(h)=13(01−1−1011−10), A= 13 _h=1^3A^(h)= 13 pmatrix0&1&-1\\ -1&0&1\\ 1&-1&0 pmatrix, so that a≻ba b, b≻cb c, and c≻ac a. Thus, cycles can arise from aggregation even when no individual rater is intransitive. E.2 Why can an equilibrium policy better align with human preferences? In the profile above, each alternative is ranked first, second, and third by exactly one rater. A policy that respects this diversity should therefore treat the alternatives symmetrically. The equilibrium does so: for this problem, it is the uniform policy π∗=(1/3,1/3,1/3)π^*=(1/3,1/3,1/3). In contrast, any deterministic selection (i.e., a pure policy) would arbitrarily favor one of the three equally represented groups. E.3 Social choice axioms The maximal-lottery rule satisfies several desirable social-choice axioms [10]: • Condorcet consistency: If one alternative defeats every other alternative by a positive margin, the unique maximal lottery places all mass on it. • Population consistency: If a lottery is maximal for two raters separately, it remains maximal after their profiles are combined. • Composition consistency: A component of similar alternatives can be evaluated internally without changing its relationship to alternatives outside the component. Thus, adding variants or copies of one agent does not distort the probabilities assigned to unrelated agents. • Cloning consistency: Introducing a clone of an alternative does not change the probabilities assigned to alternatives outside the cloned component. For agent evaluation, these axioms provide concrete operational guarantees. An agent that defeats every competitor is selected with probability one; combining feedback from user groups that agree on an evaluator preserves that evaluator; and adding duplicate or closely related variants of one agent does not change the probabilities assigned to unrelated agents. Thus, the evaluation remains consistent when feedback is pooled and when the candidate set contains redundant agent variants. Adding regularization may change which axioms can be satisfied. For the KL-regularized equilibrium, Korkmaz [48] establishes independence of irrelevant alternatives, population consistency, a regularized form of Pareto optimality, and approximate strategy-proofness. These guarantees motivate regularization in preference-based AI systems, but they depend on the choice of regularizer and do not generally hold for arbitrary strongly convex regularizers. Appendix F instantiations F.1 A summary of different comparative feedback We summarize the different relative feedback modalities and how to convert them into ordered partitions in Table 5. We further provide an example of the conversion on a menu of five items. Table 5: Turning comparative feedback modalities into ordered partitions, illustrated on the menu m=1,…,5m=\1,…,5\. Note the zero-verdict may have different interpretations for different modalities. Modality Raw response Ordered partition YmY_m Zero verdicts Pairwise duel 1≻31 3 (1,3)(\1\,\3\) a declared tie Full ranking 1≻2≻3≻4≻51 2 3 4 5 (1,2,3,4,5)(\1\,\2\,\3\,\4\,\5\) none arise Weak ranking 1,2≻3≻4,5\1,2\ \3\ \4,5\ (1,2,3,4,5)(\1,2\,\3\,\4,5\) revealed indifference Top-r (r=2r=2) T=1,2T=\1,2\ (1,2,3,4,5)(\1,2\,\3,4,5\) censoring: the order inside T and inside its complement is never asked Best–worst best 11, worst 55 (1,2,3,4,5)(\1\,\2,3,4\,\5\) censoring within the middle block Cardinal scores s=(5,5,3,1,1)s=(5,5,3,1,1) (1,2,3,4,5)(\1,2\,\3\,\4,5\) equal scores Example. Take the menu m=1,…,5m=\1,…,5\ and the reported weak ranking Ym=(1,2≻3≻4,5)Y_m=(\1,2\ \3\ \4,5\), so that bYm(1)=bYm(2)=1b_Y_m(1)=b_Y_m(2)=1, bYm(3)=2b_Y_m(3)=2 and bYm(4)=bYm(5)=3b_Y_m(4)=b_Y_m(5)=3. Applying equation 3 to each of the (52)=10 52=10 pairs gives Zm=(0011100111−1−1011−1−1−100−1−1−100). Z^m= pmatrix -0& -0& -1& -1& -1\\ -0& -0& -1& -1& -1\\ -1&-1& -0& -1& -1\\ -1&-1&-1& -0& -0\\ -1&-1&-1& -0& -0 pmatrix. F.2 Instantiations of the aggregator function We provide three instantiations of the aggregator fjkf_jk in Definition 1. In addition to smoothness and oddness, we typically require idempotence, fjk(u,…,u)=uf_jk(u,…,u)=u. Idempotence ensures that Ajk(x)=uA_jk(x)=u whenever every contributing menu has the same payoff gjkm(x)=ug^m_jk(x)=u. The choice of aggregator determines how menu-specific preferences contribute to the contextual payoff and can therefore change the equilibrium. When aggregation is useful. An aggregator is useful when the same pair appears in multiple overlapping menus and those menus provide distinct evidence about the pairwise preference. This occurs, for example, when evaluators report full rankings, weak rankings, or top-r choices over menus of different sizes. Linear weights can represent a prespecified deployment distribution over menus, balance menu sizes, or downweight menus known to produce less reliable or more heavily censored comparisons. A nonlinear aggregator can make the influence of a menu-specific margin depend on its magnitude. The cubic-link construction below, for example, gives larger absolute margins more influence on the transformed scale. In all these cases, the aggregator forms part of the estimand: different choices can produce different payoff matrices and equilibria when preferences depend on menu composition. Therefore, researchers should specify the weights independently of the observed outcomes or treat estimated weights as additional nuisance functions. Every menu assigned positive weight must also satisfy the menu-specific coverage and positivity assumptions. Notes on pairwise feedback. When every menu contains exactly two agents, each covered pair (j,k)(j,k) has the single menu m=j,km=\j,k\, so jk=j,kQ_jk=\\j,k\\. No cross-menu aggregation is needed, and we use the identity map fjk(uj,k)=uj,k,Ajk(x)=gjkj,k(x).f_jk(u_\j,k\)=u_\j,k\, A_jk(x)=g^\j,k\_jk(x). (48) Linear aggregator. Let wjkm≥0w^m_jk≥ 0 be fixed menu weights satisfying ∑m∈jkwjkm=1 _m _jkw^m_jk=1 and wkjm=wjkmw^m_kj=w^m_jk. We define fjk((um)m∈jk):=∑m∈jkwjkmum.f_jk ((u_m)_m _jk ):= _m _jkw^m_jku_m. (49) This aggregator is smooth, odd, idempotent, and valued in [−1,1][-1,1]. Uniform weights recover the mean aggregator in Section 4, while nonuniform weights enable practitioners to customize the importance of each menu. Nonlinear aggregator. We can apply a smooth odd link before averaging. For α≥0α≥ 0, define the strictly increasing bijection ϕα:[−1,1]→[−1,1] _α:[-1,1]→[-1,1] by ϕα(u):=u+αu31+α, _α(u):= u+α u^31+α, (50) and use the link-transformed weighted aggregator fjk(α)((um)m∈jk):=ϕα−1(∑m∈jkwjkmϕα(um)).f_jk^(α) ((u_m)_m _jk ):= _α^-1\! ( _m _jkw^m_jk _α(u_m) ). (51) The oddness of ϕα _α and ϕα−1 _α^-1 makes fjk(α)f_jk^(α) odd. The normalized weights make it idempotent. Moreover, ϕα′(u)=(1+3αu2)/(1+α)>0 _α (u)=(1+3α u^2)/(1+α)>0, so its inverse is smooth and the weighted average remains in its range. The choice α=0α=0 recovers the linear aggregator in Eq. (49). When α>0α>0 and at least two menus receive positive weight, the construction generally gives a nonlinear aggregation rule. Unlike the linear case, this nonlinear aggregator can have nonzero curvature, so the quadratic Taylor remainder in Eq. (12) need not vanish. F.3 Instantiations of the cost function In the main section, we use the linear expected cost Φ(π)=c⊤π (π)=c π, where c∈ℝ+Kc _+^K contains the deployment costs. We next give a nonlinear soft-budget extension and an exact hard-budget formulation. Convex cost disutility. Let φ:ℝ+→ℝ :R_+ be a continuously differentiable, convex, and nondecreasing disutility of expected spend. We define Φ(π):=φ(c⊤π),Ω(π):=Ω0(π)+Φ(π), (π):= (c π), (π):= _0(π)+ (π), (52) where Ω0 _0 is the differentiable, κ-strongly convex base regularizer. Convexity of Φ preserves the strong-convexity modulus of Ω0 _0. A smooth family that interpolates between linear pricing and a soft budget is φ(s):=λ0s+λ¯γlog(1+exp(s−Bγ)),φ′(s)=λ0+λ¯σ(s−Bγ), (s):= _0s+ λγ \! (1+ \! ( s-Bγ ) ), (s)= _0+ λ\,σ\! ( s-Bγ ), (53) where λ0,λ¯≥0 _0, λ≥ 0, B is the soft budget, γ>0γ>0 controls the transition width, and σ(t)=(1+e−t)−1σ(t)=(1+e^-t)^-1. The marginal price therefore increases smoothly from λ0 _0 to λ0+λ¯ _0+ λ as expected spend crosses B. The choice λ¯=0 λ=0 recovers linear pricing, while the limit γ↓0γ 0 yields the hinge disutility λ0s+λ¯(s−B)+ _0s+ λ(s-B)_+. Hard cost budget. Let C≥minj∈ℳcjC≥ _j c_j and define the nonempty compact convex strategy set ΔK(C):=π∈ΔK:c⊤π≤C. _K(C):=\π∈ _K:c π≤ C\. (54) We impose the budget on both players and define the constrained contextual equilibrium as πC⋆(x):=argmaxπ∈ΔK(C)minq∈ΔK(C)π⊤A(x)q−[Ω0(π)−Ω0(q)]. _C (x):= _π∈ _K(C) _q∈ _K(C) \π A(x)q-[ _0(π)- _0(q)] \. (55) Using the same feasible set for both players preserves antisymmetry and the zero game value. Compactness and convexity give existence, while strong convexity of Ω0 _0 gives uniqueness by the same argument as in Appendix C. Alternatively, we can also choose a large λ¯ λ (e.g. λ¯=100 λ=100) and still use the unconstrained optimization with Eq. (52). This yields a approximately-hard budget formulation and usually is easier to solve. Appendix G Simulated agent-evalaution dataset In this section, we construct a simulated agent-evaluation dataset with context-dependent agent performance and heterogeneous voter preferences. The data-generating process (DGP) generates pairwise comparisons, partial rankings, or winner-only feedback and provides the exact contextual payoff matrix for each modality, making precise evaluation possible. G.1 Context and vector performance We draw contexts independently as Xi∼Unif([0,1]d)X_i ([0,1]^d) with d=5d=5 and use K=5K=5 agents. Agent j has a performance vector rj(x)∈ℝpr_j(x) ^p with p=12p=12. We partition its coordinates into three groups g=4g+1,…,4g+4G_g=\4g+1,…,4g+4\ indexed by g∈0,1,2g∈\0,1,2\. For each coordinate t∈gt _g, we define rjt(x)=assj(x)+acCjt+ahtanhhjt(x),(as,ac,ah)=(1,2,0.15).r_jt(x)=a_ss_j(x)+a_cC_jt+a_h \h_jt(x)\, (a_s,a_c,a_h)=(1,2,0.15). (56) Here, sj(x)s_j(x) represents quality shared across criteria, CjtC_jt represents group specialization, and hjt(x)h_jt(x) represents criterion-specific contextual variation. We generate sjs_j and hjth_jt from two independent random Fourier feature fields. For a generic output a, we define the unstandardized field as fa(x) f_a(x) =2D∑b=1DVbacos(ωb⊤x+ϕb), = 2D _b=1^DV_ba ( _b x+ _b), (57) ωb _b ∼(0,ℓf−2Id),ϕb∼Unif(0,2π),Vba∼(0,1). (0, _f^-2I_d), _b (0,2π), V_ba (0,1). We draw all frequencies, phases, and coefficients independently. Within each field, the outputs share frequencies and phases but use separate coefficient columns. The shared-quality and criterion-specific fields have K and KpKp outputs, respectively. We use D=128D=128 and ℓf=0.5 _f=0.5, then center and scale each output to unit empirical standard deviation on 4,096 independent uniform calibration contexts. The standardized outputs define sj(x)s_j(x) and hjt(x)h_jt(x). To specify specialization, we draw a uniform permutation (a1,…,aK)(a_1,…,a_K) of 0,…,K−1\0,…,K-1\ and set (o0,o1,o2)=(0,2,4)(o_0,o_1,o_2)=(0,2,4). Then Cjt=2−2K−1[(aj−og)modK],t∈g.C_jt=2- 2K-1 [(a_j-o_g) K ], t _g. (58) We hold all latent field draws and specialization profiles fixed within each replication. G.2 Voters and population preferences Voter v assigns utility uvj(x)=wv⊤rj(x),wv∈Δp.u_vj(x)=w_v r_j(x), w_v∈ _p. (59) The population contains Nv∈1,3,5N_v∈\1,3,5\ voters. We draw a pool of five voters with preferred groups (g1,…,g5)=(0,1,2,0,1)(g_1,…,g_5)=(0,1,2,0,1) and use its first NvN_v members. For each voter, we independently draw θv∼Dirichlet(α4) _v ( 1_4) with α=20α=20. We construct θ~v∈ℝp θ_v ^p by placing these four coordinates in gvG_g_v and setting the remaining coordinates to zero. We then set wv=ϵpp+(1−ϵ)θ~v,ϵ=0.1.w_v= εp1_p+(1-ε) θ_v, ε=0.1. (60) Each member of the finite population has weight 1/Nv1/N_v, and each response samples a voter uniformly from this population. For distinct utilities, we define the latent population margin as Mjk(x)=1Nv∑v=1Nvsignuvj(x)−uvk(x),Mkj(x)=−Mjk(x),Mjj(x)=0.M_jk(x)= 1N_v _v=1^N_vsign\u_vj(x)-u_vk(x)\, M_kj(x)=-M_jk(x), M_j(x)=0. (61) The continuous field draws make exact utility ties a probability-zero event, and the implementation resolves numerical ties by agent index. With Nv=1N_v=1, M(x)M(x) follows the voter’s transitive ordering. With Nv∈3,5N_v∈\3,5\, majority aggregation can generate cycles. The populations of sizes three and five contain preferred-group counts (1,1,1)(1,1,1) and (2,2,1)(2,2,1), respectively. G.3 Menus, selection, and feedback A menu m contains the agents presented to one voter. Pairwise feedback uses all ten menus of size two. Partial-ranking feedback uses the five menus rank=1,2,3,1,2,5,1,4,5,2,3,4,3,4,5.Q_rank= \\1,2,3\,\1,2,5\,\1,4,5\,\2,3,4\,\3,4,5\ \. (62) This catalogue covers every pair. Winner feedback uses all (53)=10 53=10 menus of size three. A pair belongs to one or two ranking menus and exactly three winner menus. For each replication, we draw b∼(0,Id)b (0,I_d) and set b¯=b/‖b‖2 b=b/\|b\|_2. We define σ(z)=(1+e−z)−1σ(z)=(1+e^-z)^-1 and e0m(x) e^m_0(x) =e0(x)=emin+(emax−emin)σ(η12b¯⊤(x−12d)), =e_0(x)=e_ +(e_ -e_ )σ\! (η 12\, b (x- 121_d) ), (63) Sim|Xi S_i^m X_i ∼Bernoullie0(Xi),(emin,emax,η)=(0.25,0.75,2). \e_0(X_i)\, (e_ ,e_ ,η)=(0.25,0.75,2). We draw menu selections independently conditional on the context and independently of voter responses. Thus, the DGP satisfies MAR conditional on X. Each e0m(x)e^m_0(x) is a menu inclusion probability, so one context can generate multiple records and the probabilities need not sum to one. The lower bound emin=0.25e_ =0.25 bounds inverse propensities by four. For each selected (i,m)(i,m), we independently sample Vim∼Unif1,…,NvV_im \1,…,N_v\. The selected voter orders the agents in m by uVim,j(Xi)u_V_im,j(X_i). Pairwise feedback reports the preferred agent, partial-ranking feedback reports the complete order, and winner feedback reports only the highest-utility agent. All comparisons extracted from one response use the same voter. Records at the same context sample voters independently. For a pair j,k∈mj,k∈ m, the encoded margin from pairwise or ranking feedback is Zjkm=signuVim,j(Xi)−uVim,k(Xi).Z^m_jk=sign\u_V_im,j(X_i)-u_V_im,k(X_i)\. (64) For winner feedback, we set Wim=argmaxa∈muVim,a(Xi)W_im= _a∈ mu_V_im,a(X_i) and define Zjkm=Wim=j−Wim=k.Z^m_jk=1\W_im=j\-1\W_im=k\. (65) Eq. (65) assigns zero when another menu member wins because winner-only feedback does not reveal the relative order of j and k. G.4 Ground truth game and experimental parameters We let jk=m:j,k∈mQ_jk=\m:j,k∈ m\ and gjkm(x)=[Zjkm∣X=x]g^m_jk(x)=E[Z^m_jk X=x]. Because the DGP satisfies MAR conditional on X, we have gjkm(x)=μ0,jkm(x)g^m_jk(x)=μ^m_0,jk(x). We define the ground-truth game by averaging uniformly over the menus containing each pair: Ajk(x)=∑m∈jkλ(m∣j,k)gjkm(x),λ(m∣j,k)=1|jk|.A_jk(x)= _m _jkλ(m j,k)g^m_jk(x), λ(m j,k)= 1|Q_jk|. (66) For pairwise and ranking feedback, gjkm(x)=Mjk(x)g^m_jk(x)=M_jk(x) on every containing menu, so A(x)=M(x)A(x)=M(x). For winner feedback, we define pjm(x)=1Nv∑v=1Nvj=argmaxa∈muva(x),gjkm(x)=pjm(x)−pkm(x).p^m_j(x)= 1N_v _v=1^N_v1\! \j= _a∈ mu_va(x) \, g^m_jk(x)=p^m_j(x)-p^m_k(x). (67) Table 6 gives the parameters used in Figure 3. Within each replication, we share the performance fields, specialization permutation, selection direction, voter pool, and training and test contexts across the nine modality–population-size settings. Table 6: Parameters of the simulated dataset. Parameter Value Meaning K,d,pK,d,p 5,5,125,5,12 Agents, context dimensions, and performance criteria. X Unif([0,1]5)Unif([0,1]^5) Independent training and test contexts. D,ℓfD, _f 128,0.5128,0.5 Fourier features and field length scale. ncaln_cal 4,0964,096 Uniform contexts for field standardization. (as,ac,ah)(a_s,a_c,a_h) (1,2,0.15)(1,2,0.15) Shared quality, specialization, and criterion variation amplitudes. (o0,o1,o2)(o_0,o_1,o_2) (0,2,4)(0,2,4) Offsets of the three specialization profiles. NvN_v 1,3,51,3,5 Equally weighted voters, drawn as prefixes of one pool. (g1,…,g5)(g_1,…,g_5) (0,1,2,0,1)(0,1,2,0,1) Preferred criterion groups in the voter pool. ϵ,αε,α 0.1,200.1,20 Uniform weight allocation and Dirichlet concentration. Menu sizes 2,3,32,3,3 Pairwise, partial ranking, and winner feedback. Menu counts 10,5,1010,5,10 Catalogues for the three respective modalities. (emin,emax,η)(e_ ,e_ ,η) (0.25,0.75,2)(0.25,0.75,2) Inclusion bounds and selection logit scale. n,ntestn,n_test 20,000,4,09620,000,4,096 Training and test contexts per experiment. Test replications 55 Seeds 70–74, each covering all nine settings. Appendix H Details of the real-world datasets We describe the data sources, context variables, agent populations, and feedback protocols used in our application experiments. In Section H.1, we describe the human preference data from LM Arena and the context attributes we use to examine heterogeneity across user prompts and tasks. In Section H.2, we explain how we combine benchmark scores with LLM judgments to construct offline pairwise feedback and complete test reference matrices for evaluating contextual policies and their performance under domain shift. In Section H.3, we describe how we train driving agents with different reward weights and construct comparisons from simulated judges with distinct utilities. This setting extends our evaluation beyond language models to agents that trade off multiple performance objectives. We distinguish observed human judgments in LM Arena from the constructed preferences in RouterBench and the driving simulator, and provide the data-construction details needed to interpret and reproduce these experiments. H.1 LM Arena dataset LMArena is a crowdsourced platform in which a (human) user submits a prompt, receives responses from two anonymously presented language models, and indicates which response is better, whether the responses tie, or whether both are unsatisfactory [18]. The Arena Human Preference 140K dataset records these votes together with the conversation histories and associated metadata. The dataset fits our framework: the observed menu m are the pairs (j,k)(j,k), with pairwise preference YmY_m. The prompt and its metadata constitute the context X. For each context, only one menu’s outcome is selected, and the others are not observed. The crowdsourced votes span 126 detected language labels and a variety of tasks, providing naturally heterogeneous evaluation contexts and human preferences. We use the latest public release, which contains 135,634 votes collected from April 17, 2025 to July 24, 2025, covering 53 models. Our experiments retain the 16 models listed in Table 9 to ensure minimal coverage over the pairs. For each comparison, we construct the context from the conversation and salient metadata, including language, task-category annotations (e.g., mathematics, creative writing, instruction following, and hard prompts), and whether the conversation involves code. Tables 8 and 8 report the marginal distributions of the principal discrete context attributes. We aggregate the recorded language labels into five categories: English, Polish, Russian, Chinese (including both zh and zh-Hant), and Other. The code, instruction-following, and mathematics indicators are taken directly from the dataset annotations. Table 7: Marginal distribution of language groups. Language group Count Share English 71,175 52.5% Polish 13,813 10.2% Russian 9,263 6.8% Chinese 7,346 5.4% Other 34,037 25.1% Table 8: Marginal distributions of binary context attributes. Attribute Value Count Share Code Yes 39,363 29.0% No 96,271 71.0% Instruction following Yes 24,666 18.2% No 110,968 81.8% Mathematics Yes 10,892 8.0% No 124,742 92.0% Table 9: Selected agents from the Arena Human Preference 140K dataset, with list prices in USD per 10610^6 tokens. Provider Agent Input Output OpenAI o3-2025-04-16 2.00 8.00 o4-mini-2025-04-16 1.10 4.40 gpt-4.1-2025-04-14 2.00 8.00 Anthropic claude-opus-4-20250514 15.00 75.00 claude-sonnet-4-20250514 3.00 15.00 Google gemini-2.5-pro 1.25 10.00 gemini-2.5-flash 0.30 2.50 Alibaba (Qwen) qwen3-235b-a22b-instruct-2507 0.09 0.55 qwen3-30b-a3b 0.12 0.50 Moonshot AI kimi-k2-0711-preview 0.57 2.30 MiniMax minimax-m1 0.55 2.20 Mistral AI mistral-medium-2505 0.40 2.00 DeepSeek deepseek-r1-0528 0.50 2.15 deepseek-v3-0324 0.25 1.00 Meta llama-4-maverick-17b-128e-instruct 0.20 0.80 H.2 RouterBench dataset RouterBench evaluates LLM routers by running multiple models on a common collection of prompts and recording their responses, task-specific correctness scores, and inference costs [41]. We use its latest release [56] and retain the K=10K=10 flagship models in Table 11 with complete coverage across ten subsets (see Table 10). The resulting benchmark contains 8,7428,742 prompts. The context X includes the prompt, source subset, task domain, mathematics and code indicators, language group, and token length, following the LMArena context schema in Section H.1. RouterBench provides absolute scores rather than relative feedback. A score sj(x)s_j(x) induces Zjk(x)=signsj(x)−sk(x)Z_jk(x)=sign\s_j(x)-s_k(x)\ and is therefore transitive by construction. We use this verdict when the native scores distinguish a pair and elicit a preference only when both models succeed (if both fail, then we simply treat it as a both bad verdict). For each prompt, we sample Q=20Q=20 of the (102)=45 102=45 pairs uniformly and independently, giving the known propensity e0m(x)=20/45e^m_0(x)=20/45 and satisfying positivity. A sampled pair (j,k)(j,k) at prompt x is then resolved as Zjk(x)=sign(sj−sk),sj≠sk(the benchmark orders the pair),0,sj=sk=0(both agents fail),judge verdict,sj=sk>0(both agents succeed),Z_jk(x)= casessign(s_j-s_k),&s_j≠ s_k (the benchmark orders the pair),\\ 0,&s_j=s_k=0 (both agents fail),\\ judge verdict,&s_j=s_k>0 (both agents succeed), cases (68) so a judge is used only when both models succeed. We draw judges from three latest open-source frontier models supplied by different providers and assign them distinct emphases—rigour, depth, or efficiency—within a common six-metric rubric. This emulates the real-world rater diversity and heterogeneity, which also might introduce intransitive feedback. Each pair is judged in both presentation orders and the verdicts are averaged to mitigate position bias. We select 500500 prompts from the benchmark as a separate test set, unseen by the training. All 4545 pairs on the 500500 test prompts are evaluated by all three judges, yielding a complete reference payoff matrix as the ground truth. Each of the 8,2428,242 training prompts receives the 2020 sampled pairs and one randomly assigned judge. Overall, the processing yields 232,340232,340 comparisons, including 67,50067,500 test comparisons. Table 10 shows the constitution. Knowledge tasks account for 67.0%67.0\% of prompts, programming 17.8%17.8\%, chat and instruction following 8.6%8.6\%, logic 4.6%4.6\%, and mathematics 2.1%2.1\%; 20.7%20.7\% involve code and 4.9%4.9\% mathematics. Different to LM Arena, the routerbench is 96.0%96.0\% English, with some CJK. Table 10: Composition of the RouterBench panel. “Feedback modality” is the benchmark’s native outcome format; the last two columns give the share of sampled pairs that the label already orders and the share on which both agents succeed and a judge is therefore consulted. Subset Prompts Test Domain Feedback modality Ord. Judged MMLU-Pro 3,000 50 knowledge Binary (correct/incorrect) 13.1% 75.5% HLE 2,158 50 knowledge Binary (correct/incorrect) 17.1% 3.0% LiveCodeBench 1,055 50 programming Binary (pass/fail) 19.5% 60.4% ArenaHard 750 100 chat / IF Ternary (win/tie/loss) 48.7% 42.6% SimpleQA 500 50 knowledge Ternary (correct/incorrect/not attempted) 30.1% 19.5% SWE-bench 500 50 programming Binary (pass/fail) 24.9% 10.8% ARC-AGI 400 50 logic Binary (exact/non-match) 23.2% 9.8% GPQA 198 50 knowledge Binary (correct/incorrect) 22.3% 63.5% LiveMathBench 121 30 math Binary (correct/incorrect) 21.9% 54.1% AIME 60 20 math Binary (correct/incorrect) 28.4% 56.5% Total 8,742 500 22.1% 41.3% Table 11: Selected agents from the RouterBench dataset, with list prices in USD per 10610^6 tokens. † -5-chat is no longer served; its price is taken from the benchmark’s own records. Provider Agent Input Output OpenAI gpt-5 (medium) 1.25 10.00 gpt-5-chat† 1.25 10.00 Anthropic claude-sonnet-4 3.00 15.00 Google gemini-2.5-pro 1.25 10.00 gemini-2.5-flash 0.30 2.50 Alibaba qwen3-235b-a22b-thinking-2507 0.23 2.30 DeepSeek deepseek-v3-0324 0.25 1.00 deepseek-r1-0528 0.50 2.15 Z-AI glm-4.6 0.43 1.75 Moonshot AI kimi-k2-0905 0.60 2.50 H.3 Reinforcement-learning agent dataset We construct a contextual agent-evaluation dataset using mo-highway-fast-v0, the multi-objective highway-driving environment in MO-Gymnasium [31], built on HighwayEnv [55]. An agent controls a vehicle among simulated traffic and receives separate rewards for speed, right-lane occupancy, and collision avoidance; the collision component is a nonpositive penalty. The tasks are contextual, containing five configuration features: lane count, vehicle count, traffic density, initial lane, and initial ego spacing. We sample lane and vehicle counts uniformly from 2,3,4,5\2,3,4,5\ and 20,…,60\20,…,60\, density from U[0.7,1.5]U[0.7,1.5], the initial lane uniformly among valid lanes, and ego spacing from U[0.5,3]U[0.5,3], then fix the configuration for the episode. The driving task is inherently multi-objecitve: for example, agents can trade speed with safety. We simulate external judges through linear utilities over an episode-performance vector zj=(r¯speed,r¯lane,1−collision)∈[0,1]3z_j=( r_speed, r_lane,1-1\collision\)∈[0,1]^3. Three equally weighted judges use Uh(j)=vh⊤zjU_h(j)=v_h z_j, with weights approximately (0.67,0.31,0.02)(0.67,0.31,0.02), (0.044,0.0,0.95)(0.044,0.0,0.95), and (0.26,0.01,0.72)(0.26,0.01,0.72). Each offline comparison samples a pair menu m=j,km=\j,k\ uniformly from the ten unordered pairs and a judge uniformly from the three judges. Both agents are then evaluated on the same contextual task. The signed verdict ZjkmZ^m_jk is +1+1 if the judge prefers j and −1-1 otherwise, with exact utility ties broken by a fair coin; hence e0m(x)=1/10e^m_0(x)=1/10 per comparison. Our target Ajk(x)A_jk(x) further averages over the initialization scenarios. We train agents by the scalar reward wj⊤rw_j r, where wjw_j specifies agent j’s training weights on the reward vector r=(rspeed,rlane,rcollision)r=(r_speed,r_lane,r_collision). We apply deep Q-learning [58] through Stable-Baselines3 [65]. Each agent receives 20,00020,000 interaction steps with two hidden layers of 256 units. We adapt the official HighwayEnv DQN example,44 4 https://highway-env.farama.org/quickstart/ using learning rate 5×10−45× 10^-4, replay capacity 15,00015,000, batch size 32, and target updates every 50 steps. The final five agents use weights (0.1,0.8,0.1)(0.1,0.8,0.1), (0.8,0.1,0.1)(0.8,0.1,0.1), (0.45,0.1,0.45)(0.45,0.1,0.45), (0.02,0,0.98)(0.02,0,0.98), and (0.2,0,0.8)(0.2,0,0.8), respectively. The first three use discount factor 0.80.8; the last two use 0.990.99 to emphasize longer-term safety. These design choices make sure that the agents trained have a range of varying capabilities. The resulting dataset contains 256 configurations (i.e. context) with eight initializations and has eventually 20,48020,480 offline comparisons. Validation and test set contain 32 configurations, with 32 and 64 initializations per configuration, respectively. For each validation or test configuration, we evaluate all five agents and average all three judges’ verdicts to estimate the complete payoff matrix, without assigning ties. Primary data exploration shows that the contextual PMs contain cycle roughly 1/31/3 of the times. Appendix I Implementation In Section I.1, we define the evaluation metrics used in our experiments. In Section I.2, we specify the training details of our NashEval. In Section I.3, we describe the baselines. We summarize our method (i.e. NashEval-debiased) in Algorithm 1. Algorithm 1 NashEval-debiased: contextual equilibrium learning from selective feedback 1: Training log n=Oii=1nD_n=\O_i\_i=1^n, menu aggregators fjkj<k\f_jk\_j<k, context-independent strongly convex regularizer Ω , number of folds KCFK_CF, and policy class πθ:θ∈Θ\ _θ:θ∈ \. 2: Encode each observed Yi,mY_i,m as verdicts Zi,jkmZ^m_i,jk using Eq. (3). 3: Partition the training indices into folds I1,…,IKCFI_1,…,I_K_CF, keeping all records from each context together. 4: for b=1,…,KCFb=1,…,K_CF do 5: for each menu m∈m do 6: Fit e^m,(−b)(x) e^m,(-b)(x) to SimS_i^m on all i∉Ibi∉ I_b using binary log loss. 7: Fit μ^jkm,(−b)(x) μ^m,(-b)_jk(x) to Zi,jkmZ^m_i,jk for each j<kj<k in m using squared error on i∉Ibi∉ I_b with Sim=1S_i^m=1. 8: end for 9: for each i∈Ibi∈ I_b and pair j<kj<k do 10: Set ^i,jk(−b)=(μ^jkm,(−b)(Xi))m∈jk μ^(-b)_i,jk= ( μ^m,(-b)_jk(X_i) )_m _jk. 11: Construct the out-of-fold target from Eq. (42): 12: Γ^i,jk=fjk(^i,jk(−b))+∑m∈jkSim=1∂fjk∂um(^i,jk(−b))Zi,jkm−μ^jkm,(−b)(Xi)e^m,(−b)(Xi). _i,jk=f_jk\! ( μ^(-b)_i,jk )+ _ subarraycm _jk\\ S_i^m=1 subarray ∂ f_jk∂ u_m\! ( μ^(-b)_i,jk ) Z^m_i,jk- μ^m,(-b)_jk(X_i) e^m,(-b)(X_i). 13: end for 14: end for 15: Pool the targets from all folds and fit a shared payoff regressor: 16: a^∈argmina∑i=1n∑j<ka(Xi,j,k)−Γ^i,jk2. a∈ _a _i=1^n _j<k \a(X_i,j,k)- _i,jk \^2. 17: Define A^jkDB(x)=clip[−1,1]a^(x,j,k) A^DB_jk(x)=clip_[-1,1]\ a(x,j,k)\ for j<kj<k, and set A^kjDB(x)=−A^jkDB(x) A^DB_kj(x)=- A^DB_jk(x) and A^jjDB(x)=0 A^DB_j(x)=0. 18: Minimize the empirical gap loss to learn πθ _ θ: 19: ℒ^n(θ)=1n∑i=1nGΩ(πθ(Xi),A^DB(Xi),Xi). L_n(θ)= 1n _i=1^nG_ \! ( _θ(X_i); A^DB(X_i),X_i ). 20: return A^DB A^DB and πθ _ θ. 21: Inference: For a new context x⋆x_ , return πθ^(x⋆)∈ΔK _ θ(x_ )∈ _K. We evaluate the residual correction only for observed menus, so the algorithm never requires an unobserved verdict. We retain the full pseudo-outcome values during payoff regression and clip only the fitted payoff predictions. We use LightGBM for the nuisance and payoff models and the multilayer perceptron described in Section I.2 for the policy. For experiments that compute equilibria directly, we replace policy training and prediction by a numerical equilibrium solver applied to A^DB(x) A^DB(x) with the experiment’s regularizer. I.1 Evaluation metrics We evaluate a policy π on ntestn_test contexts xix_i using reference payoff matrices AirefA_i^ref, with positive entries indicating preference for the row agent over the column agent. We use the true matrices in synthetic experiments and approximated matrices in RouterBench and MO-Highway. Average exploitability. Exploitability measures the largest advantage an opponent can obtain against the evaluated policy. We average the unregularized best-response payoff over test contexts: Expl^0(π)=1ntest∑i=1ntestmaxq∈ΔKq⊤Airefπ(xi). Expl_0(π)= 1n_test _i=1^n_test _q∈ _Kq A_i^refπ(x_i). (69) Lower is better, and we allow an unrestricted opponent even when we impose a cost penalty on the evaluated policy. Support F1F_1. Support F1F_1 measures how accurately a policy recovers the reference winner set, without comparing the assigned probabilities. We define Sτ(p)=j:pj>τS_τ(p)=\j:p_j>τ\ and average the overlap with the reference equilibrium πiref _i^ref: F^1(π)=1ntest∑i=1ntest2|Sτ(π(xi))∩Sτ(πiref)||Sτ(π(xi))|+|Sτ(πiref)|. F_1(π)= 1n_test _i=1^n_test 2|S_τ(π(x_i))∩ S_τ( _i^ref)||S_τ(π(x_i))|+|S_τ( _i^ref)|. (70) Higher is better, and we use τ=10−3τ=10^-3 in the synthetic experiments and the reference equilibrium under the experiment’s specified regularization. Head-to-head game value. Game value measures the evaluated policy’s net preference advantage against a specified opponent policy. We report the average payoff of π against q: V^(π,q)=1ntest∑i=1ntestπ(xi)⊤Airefq(xi). V(π,q)= 1n_test _i=1^n_testπ(x_i) A_i^refq(x_i). (71) In the RQ2 tables, we take q to be NashEval-debiased, so positive values favor the row method and negative values favor NashEval-debiased. Average strict win rate. Strict win rate measures how often a sampled agent wins against an equally weighted pool of single-agent opponents. We let Wi,jkW_i,jk denote the reference probability that agent j strictly defeats agent k at xix_i and compute WR^(π)=1ntestK∑i=1ntest∑j=1K∑k=1Kπj(xi)Wi,jk. WR(π)= 1n_testK _i=1^n_test _j=1^K _k=1^K _j(x_i)W_i,jk. (72) We assign ties and self-comparisons zero credit and retain them in the denominator, so payoff margins alone do not determine this metric when ties occur. I.2 training details We use LightGBM to estimate the outcome regressions μ0,jkmμ^m_0,jk and selection propensities e0me^m_0, and to fit the debiased payoff matrix A^DB A^DB. We split training contexts into KCFK_CF folds and keep all records from the same context in one fold. For each fold, we fit the nuisance models on the remaining folds and predict the nuisances on the held-out fold to construct its pseudo-outcomes. We then pool these out-of-fold pseudo-outcomes to train the payoff regressor. Sentence embedding. For contexts that include text, we use the fixed Qwen3-Embedding-4B encoder [86] to map each prompt to femb(x)∈ℝdf_emb(x) ^d. We compare Qwen3-Embedding-0.6B, Qwen3-Embedding-4B, and EmbeddingGemma-300M [72] with embedding dimensions from 32 to 1024. In these comparisons, we observe little variation in nuisance prediction accuracy across encoders and only small gains from larger embeddings. We therefore use Qwen3-Embedding-4B with d=64d=64 to limit encoding and storage costs. Nuisance estimation. For each menu m and pair j<kj<k in m, we fit a separate LightGBM regressor to estimate μ0,jkm(x)μ^m_0,jk(x) by minimizing squared error on records with Sm=1S^m=1. We impose μ^kjm(x)=−μ^jkm(x) μ^m_kj(x)=- μ^m_jk(x) and μ^jjm(x)=0 μ^m_j(x)=0. For each menu, we fit a LightGBM binary classifier to estimate e0m(x)e^m_0(x) from the inclusion indicator SmS^m using binary log loss on all training contexts. We cross-fit both nuisance estimators as described above. Payoff regression. We fit a shared LightGBM regressor to the cross-fitted pseudo-outcomes Γjk(O,η^) _jk(O; η) using (x,j,k)(x,j,k) as inputs and treating j and k as categorical features. We minimize squared error to estimate the conditional mean of these targets and obtain A^DB(x) A^DB(x). This regression targets the debiased payoff surface rather than directly observed entries of the ground-truth matrix A(x)A(x). Hyperparameter tuning. We tune the nuisance estimators and the shared payoff regressor by grid search with three-fold cross-validation. Tables 12 and 13 give the respective search spaces. We select the number of boosting iterations by early stopping, with a maximum of 1,000 iterations. We distinguish these tuning folds from the KCFK_CF folds used to construct out-of-fold nuisance predictions. Note that we use a slightly more complex search space for the payoff regressor than the nuisance estimators. Table 12: Hyperparameter search space for the nuisance estimators. The index ν∈μ,eν∈\μ,e\ denotes the outcome or propensity model. Hyperparameter Symbol Search space Learning rate lrνlr_ν 0.01,0.1\0.01,0.1\ Maximum leaves per tree nleaf,νn_leaf,ν 7,15,31\7,15,31\ Maximum tree depth dmax,νd_ ,ν 7, 10 Minimum observations per leaf nmin,νn_ ,ν 30,50,100,200\30,50,100,200\ L2L_2 penalty on leaf values λ2,ν _2,ν 0,0.1,1\0,0.1,1\ Feature fraction per tree fνf_ν 0.6,0.8,1.0\0.6,0.8,1.0\ Number of trees TνT_ν 50, 100, 200 Table 13: Hyperparameter search space for the shared payoff regressor. Hyperparameter Symbol Search space Learning rate lrAlr_A 0.02,0.05,0.1\0.02,0.05,0.1\ Maximum leaves per tree nleaf,An_leaf,A 15,31,62\15,31,62\ Maximum tree depth dmax,Ad_ ,A 10, 15 Minimum observations per leaf nmin,An_ ,A 50,100,200\50,100,200\ L2L_2 penalty on leaf values λ2,A _2,A 0,0.1,1\0,0.1,1\ Feature fraction per tree fAf_A 0.6,0.8,1.0\0.6,0.8,1.0\ Number of trees TAT_A 50, 100, 200, 400 Equilibrium learning. We parameterize the equilibrium predictor πθ(x) _θ(x) as a multilayer perceptron with two hidden layers, ReLU activations, and a K-dimensional softmax output that maps each context to a distribution over agents (During inference or testing, the threshold for a winner is 0.0010.001.). We train the network to minimize the empirical orthogonal gap loss and approximate the target equilibrium π⋆(x)π (x). We tune the hyperparameters of the predictor by grid search specified in Table 14. Table 14: Hyperparameter search space for the equilibrium predictor. We fix two hidden layers and vary their common width. Hyperparameter Search space or fixed setting Hidden-layer widths (64,64),(128,128),(256,256)\(64,64),(128,128),(256,256)\ Learning rate 10−4,3×10−4,10−3\10^-4,3× 10^-4,10^-3\ Weight decay 0,10−5,10−4\0,10^-5,10^-4\ Batch size 128,256\128,256\ Maximum training epochs 500500 Early-stopping patience 3030 epochs I.3 Baselines Oracle nuisance baseline. For NashEval-oracle, we substitute the exact outcome functions μ0,jkm(x)μ^m_0,jk(x) and inclusion propensities e0m(x)e^m_0(x) into the orthogonal training target: Γi,jkON=1|jk|∑m∈jk[μ0,jkm(Xi)+Sime0m(Xi)Zi,jkm−μ0,jkm(Xi)]. ^ON_i,jk= 1|Q_jk| _m _jk [μ^m_0,jk(X_i)+ S_i^me^m_0(X_i) \Z^m_i,jk-μ^m_0,jk(X_i) \ ]. (73) We use the same training log and payoff regression as NashEval-debiased: 300 trees, seven leaves, learning rate 0.050.05, and minimum leaf size 100. We clip predictions to [−1,1][-1,1] and impose antisymmetry and a zero diagonal to obtain A^ON(x) A^ON(x). NashEval-related policies. We compute NashEval-debiased, NashEval-plug-in, and NashEval-oracle from A^DB A^DB, A^PI A^PI, and A^ON A^ON, respectively. In the synthetic experiment, we set all agent costs to zero and use the following regularizer: Ω(π)=ρ2‖π−1KK‖22,ρ=0.001. (π)= ρ2 \|π- 1K1_K \|_2^2, ρ=0.001. (74) BT and Borda policies. For an estimated matrix B(x)B(x), we fit BT scores separately at each context: s^B(x)=argmins∈ℝK s^B(x)= _s ^K 1(K2)∑j<k[log1+exp(sj−sk)−1+Bjk(x)2(sj−sk)]+κBT2‖s‖22, 1 K2 _j<k [ \1+ (s_j-s_k)\- 1+B_jk(x)2(s_j-s_k) ]+ _BT2\|s\|_2^2, (75) κBT=10−4. _BT=10^-4. We use Newton iterations with line search and stop when the maximum absolute score gradient is at most 10−910^-9. We set B=A^DBB= A^DB for BT-debiased and B=A^PIB= A^PI for BT-Plug-in, and select argmaxjs^jB(x) _j s^B_j(x). For winner feedback, we use the encoded margins in Eq. (65). BT-Reg uses the same scores as BT-Plug-in to form A^jkBT(x)=tanh(s^jPI(x)−s^kPI(x)2), A^BT_jk(x)= \! ( s^PI_j(x)- s^PI_k(x)2 ), (76) and computes its equilibrium with the same policy regularizer and strength ρ as NashEval in Eq. (74). Borda selects the largest average row margin of A^DB(x) A^DB(x): argmaxj(K−1)−1∑k≠jA^jkDB(x) _j(K-1)^-1 _k≠ j A^DB_jk(x). With complete, equally weighted pairs and a common L2L_2 score penalty, BT scores and row sums have the same ordering. With identical tie-breaking by agent index, BT-debiased and Borda therefore yield the same policy, which we label BT-debiased / Borda. BT-cost on RouterBench. We train a cost-constrained adaptation of the contextual BT model of Theorem 1 in Frick et al. [36]. For each prompt, we form P^jkBT(x)=σ(s^j(x)−s^k(x)) P^BT_jk(x)=σ( s_j(x)- s_k(x)) and fix the opponent to q=/Kq=1/K. Given a budget C≥minjcjC≥ _jc_j, we solve π^BT-cost(x;C)∈argmaxπ∈ΔK:c⊤π≤Cπ⊤P^BT(x)q. π_BT -cost(x;C)∈ _π∈ _K:\ c π≤ Cπ P^BT(x)q. (77) We evaluate 31 equally spaced budgets between the minimum and maximum costs, together with every distinct model cost, for 37 budgets in total. Maximal lottery. We compute a context-independent equilibrium from pooled training payoffs M^jk M_jk, using the regularization and cost treatment specified for each experiment. We average the observed training verdicts for each pair across contexts. Let ℐjkI_jk index the training comparisons of agents j and k, and let Zi,jkmiZ_i,jk^m_i denote comparison i’s signed verdict, oriented in favor of j. We define M^jk=1|ℐjk|∑i∈ℐjkZi,jkmi,j<k,M^kj=−M^jk,M^jj=0. M_jk= 1|I_jk| _i _jkZ_i,jk^m_i, j<k, M_kj=- M_jk, M_j=0. (78) Robust maximal lottery. Following Khalaf et al. [46], we define (w^0,τ)=w∈Δ||:12∥w−w^0∥1≤τ,ℳτ=∑g∈wgM^(g):w∈(w^0,τ)W( w_0,τ)= \w∈ _|G|: 12 w- w_0 _1≤τ \, _τ= \ _g w_g M^(g):w ( w_0,τ) \ (79) as the ambiguity set and choose the primary radius τn=min1,||n+2nlog2δ,δ=0.05, _n= \! \1, |G|n+ 2n 2δ \, δ=0.05, (80) where n is the number of training prompts. We also evaluate τ∈0,.025,.05,.1,.2,.4,.6,.8,1τ∈\0,.025,.05,.1,.2,.4,.6,.8,1\, together with τn _n, without test-based radius selection. The robust policy is the solution of π^rob∈argmaxπ∈ΔKminw∈(w^0,τ)minj∈[K]π⊤(∑g∈wgM^(g))ej. π_rob∈ _π∈ _K\; _w ( w_0,τ) _j∈[K]π \! ( _g w_g M^(g) )e_j. (81) We then solve Eq. (81) with the exact dual linear program from Theorem 17 of Khalaf et al. [46]. Pluralistic leaderboard. We adapt the ranking method of Haghtalab et al. [38] to incomplete comparisons by treating each training prompt as one voter. We infer its scores from the 20 observed pairs xO_x through u^x=argminu∈ℝK∑(j,k)∈x(uj−uk−Zjk(x))2+∥u∥22. u_x= _u ^K _(j,k) _x (u_j-u_k-Z_jk(x) )^2+ u _2^2. (82) We sort u^x u_x in descending order and break ties with a permutation fixed by the data-split seed. This completion step is our adapter, so the ranking guarantees concern the inferred rankings rather than the original cyclic preferences. We implement the iterated-rounding committee procedure and the geometric-checkpoint ranking construction of Algorithms 1 and 2 in Haghtalab et al. [38]. We use the paper’s parameters ϵ=0.01ε=0.01, α=1/2+4ϵα=1/2+4ε, and β=1/4+2ϵβ=1/4+2ε, and use growth factor two for the checkpoint sizes. Since our candidate set has only K=10K=10 models, we enumerate the committees at each checkpoint and replace the paper’s approximate multiplicative-weights subroutine with an exact empirical linear program. For candidate committees C1,…,CLC_1,…,C_L of size k, let baℓ=1n∑x=1na≻xcfor every c∈Cℓ.b_a = 1n _x=1^n1\! \a _xc\ for every c∈ C_ \. (83) We compute the stable lottery over committees by minimizing minδ∈ΔL,vvsubject to∑ℓ=1Lδℓbaℓ≤v∀a∈[K]. _δ∈ _L,\,v\;v to _ =1^L _ b_a ≤ v ∀ a∈[K]. (84) We use δ to select committees in order to produce the ranking. At each rounding step, we select a committee with positive probability under δ that minimizes the fraction of unsatisfied prompts at threshold β−ϵβ-ε, and repeat on the remaining unsatisfied prompts. We construct checkpoint committees of sizes 1,2,4,…1,2,4,… and append each model to the ranking when it first appears, then append any remaining models. Let W3W_3 be the top-three models in the ranking. We convert the ranking to a uniform lottery over its top three models for policy evaluation. Appendix J Proofs We collect the assumptions in Section J.1. We then prove identification, derive the EIF and the conditional bias bound, establish Neyman-orthogonality, and prove the empirical exploitability bound and quasi-oracle rate. Notation and conventions. We write P0P_0 for the observed-data law and PXP_X for its context marginal. We fix the finite agent and menu collections, the aggregators fjkf_jk, and the context-independent regularizer Ω . All functions, fitted quantities, policy selections, and suprema below are measurable, and pointwise statements hold outside a common PXP_X-null set. We suppress pair and menu indices when they do not affect the argument, write η=(μ,e)η=(μ,e) and η0=(μ0,e0) _0=( _0,e_0), and set Δμ=μ^−μ0 μ= μ- _0 and Δe=e^−e0 e= e-e_0 for fitted nuisance errors. We use ∥⋅∥1\|·\|_1 and ∥⋅∥2\|·\|_2 for the vector ℓ1 _1 and Euclidean norms. For the policy norm ∥⋅∥\|·\|, we define the dual norm and induced matrix norm by ‖v‖⋆:=sup‖u‖≤1⟨v,u⟩,‖B‖⋆:=sup‖u‖≤1‖Bu‖⋆. \|v\|_ := _\|u\|≤ 1 v,u , \|B\|_ := _\|u\|≤ 1\|Bu\|_ . Finite-dimensional norm equivalence gives a constant CmatC_mat such that ‖B‖⋆2≤Cmat∑j,k|Bjk|2\|B\|_ ^2≤ C_mat _j,k|B_jk|^2. For a scalar function h, we write ‖h‖L2(PX)=(X[h(X)2])1/2\|h\|_L_2(P_X)=(E_X[h(X)^2])^1/2, so ‖Δμ‖22‖L2(PX)=(X‖Δμ(X)‖24)1/2\|\| μ\|_2^2\|_L_2(P_X)=(E_X\| μ(X)\|_2^4)^1/2. We write L20(P0)L_2^0(P_0) for the square-integrable, mean-zero functions of O. All regularity constants are uniform in n, and κ is fixed for the quasi-oracle rate. J.1 Assumptions We state the full list of assumptions used in the analysis. Assumption 1 (Identifiability). In order to identify the contextual payoff Ajk(x)A_jk(x) from the observed data, we make the following assumptions: (i) pairwise menu coverage: jk≠∅Q_jk≠ for every pair j,k⊆ℳ\j,k\ ; (i) missing at random (MAR): Sm⟂Zjkm|XS^m Z^m_jk X for every m∈jkm _jk; (i) positivity: e0m(x)=P(Sm=1∣X=x)≥e¯>0e^m_0(x)=P(S^m=1 X=x)≥ e>0 almost everywhere for every m∈jkm _jk. The potential-verdict formulation follows Rubin [69], and MAR [70] and positivity [45] are standard identifying conditions in missing-data and causal analysis. Assumption 2 (Boundedness). We fix αμ>0 _μ>0 and write Iα:=(−1−αμ,1+αμ)I_α:=(-1- _μ,1+ _μ). We assume (i) generic and fitted nuisances used in the bias, differentiability, and rate bounds satisfy μjkm(x)∈Iαμ^m_jk(x)∈ I_α and em(x)≥e¯e^m(x)≥ e, with e¯ e from Assumption 1, and (i) the fitted payoff has finite entrywise L2(PX)L_2(P_X) error. For the quasi-oracle result, we additionally require (i) a uniform envelope suph∈ℋn|h(x)|≤H _h _n|h(x)|≤ H, where ℋnH_n is the loss class in Assumption 8 and H is independent of n. Assumption 3 (Smoothness). We assume (i) each fjkf_jk extends to a continuously differentiable function on IαjkI_α^Q_jk, with IαI_α from Assumption 2, (i) Ω is continuously differentiable on a neighborhood of ΔK _K, and (i) θ↦πθ(x)θ _θ(x) is continuously differentiable when we differentiate the gap loss. For population gap-loss differentiation, we further require a neighborhood UθU_θ of each θ such that X[Mθ(X)]<∞,Mθ(x):=supϑ∈Uθ‖Dθπϑ(x)‖op, _X[M_θ(X)]<∞, M_θ(x):= _ ∈ U_θ\|D_θ _ (x)\|_op, (85) where ‖J‖op:=sup‖v‖2≤1‖Jv‖\|J\|_op:= _\|v\|_2≤ 1\|Jv\|. For gap-loss differentiability, orthogonality, and the quantitative remainder and rate bounds, we further assume ‖∇fjk(u)−∇fjk(v)‖2≤Lf‖u−v‖2\|∇ f_jk(u)-∇ f_jk(v)\|_2≤ L_f\|u-v\|_2 for all u,v∈Iαjku,v∈ I_α^Q_jk. Such differentiability conditions are standard in influence-function and orthogonal-learning analyses [45, 33]. The Jacobian envelope justifies differentiation of the population gap loss under expectation, as we show in Section J.7. Assumption 4 (Strong convexity). We assume that Ω is κ-strongly convex on ΔK _K with respect to ∥⋅∥\|·\|, where κ>0κ>0. Strongly convex regularization is common in regularized zero-sum games [74], and it makes the equilibrium unique [28]. Assumption 5 (Cross-fitting). We observe i.i.d. data O1,…,On∼P0O_1,…,O_n P_0 and use a data-independent partition into a fixed number KCFK_CF of folds. Each nuisance fit uses only observations outside its evaluation fold and satisfies the stated propensity and rate conditions. We use ADB(⋅,η^)A^DB(·; η) for the average of the fold-specific regression targets. Cross-fitting is standard in DML [15]. Assumption 6 (Nuisance and payoff-estimation rates). We assume ‖Δμ‖2‖L2(PX)=Op(rμ)\|\| μ\|_2\|_L_2(P_X)=O_p(r_μ) and ‖Δe‖L2(PX)=Op(re)\| e\|_L_2(P_X)=O_p(r_e) for deterministic rates rμ,re→0r_μ,r_e→ 0, together with the moment bounds ‖Δμ‖22‖L2(PX)=Op(rμ2),‖ΔeΔμ‖L2(PX)=Op(rμre). \| \| μ \|_2^2 \|_L_2(P_X)=O_p(r_μ^2), \| e\, μ \|_L_2(P_X)=O_p(r_μr_e). (86) The outcome bounds hold uniformly over agent pairs, the propensity bound over contributing menus, and the product bound over pairs and contributing menus, with the product evaluated menu-wise. We define eA:=maxj,k‖A^jkDB(⋅,η^)−AjkDB(⋅,η^)‖L2(PX). e_A:= _j,k \| A^DB_jk(·; η)-A^DB_jk(·; η) \|_L_2(P_X). (87) For the quasi-oracle rate, we additionally require eA=Op(n−1/4),rμ≲n−1/8,e¯−1rμre≲n−1/4, e_A=O_p(n^-1/4), r_μ n^-1/8, e^-1r_μr_e n^-1/4, (88) and omit the separate condition on rμr_μ for affine aggregators. Product-rate conditions of this type are standard in DML [15] and orthogonal statistical learning [33]. For fixed e¯>0 e>0, we can satisfy Eq. (88) with matching nuisance rates rμ,re≲n−1/8r_μ,r_e n^-1/8 and payoff-regression error eA=Op(n−1/4)e_A=O_p(n^-1/4), using flexible nuisance learners such as gradient-boosted trees (e.g., LightGBM) or neural networks [15] when they attain these rates in the stated norms. Assumption 7 (Realizability). For oracle recovery in Proposition 2, we assume that some θ0∈Θ _0∈ satisfies πθ0(x)=π⋆(x) _ _0(x)=π (x) for PXP_X-almost every x. Assumption 8 (Loss-class complexity). For the quasi-oracle result, we assume a deterministic class ℬnB_n containing A and, with probability tending to one, A^DB(⋅,η^) A^DB(·; η). We define ℋn:=x↦GΩ(πθ(x);B(x),x):θ∈Θ,B∈ℬn _n:=\x G_ ( _θ(x);B(x),x):θ∈ ,\ B _n\ and assume the expected absolute Rademacher-complexity bound ℜn(ℋn):=X,σ[suph∈ℋn|1n∑i=1nσih(Xi)|]≤Cn−1/2, R_n(H_n):=E_X,σ\! [ _h _n | 1n _i=1^n _ih(X_i) | ]≤ Cn^-1/2, (89) where C is independent of n, and σ1,…,σn _1,…, _n are independent uniform signs in −1,1\-1,1\, independent of the contexts. Rademacher-complexity bounds are commonly used to control uniform deviations [6]. Because the bound covers the entire class ℋnH_n, it permits reuse of observations for payoff and policy fitting. J.2 Identification of the contextual payoff matrix Proof. We fix a pair j≠kj≠ k, a menu m∈jkm _jk, and a context x outside the null set on which the identification assumptions may fail. Menu-specific positivity gives P(Sm=1∣X=x)=e0m(x)≥e¯>0P(S^m=1 X=x)=e^m_0(x)≥ e>0, so the observed-data regression μ0,jkm(x)μ^m_0,jk(x) is well-defined. Menu-specific MAR implies conditional mean independence between SmS^m and ZjkmZ^m_jk given X. Therefore, μ0,jkm(x) μ^m_0,jk(x) =[Zjkm∣X=x,Sm=1] =E[Z^m_jk X=x,S^m=1] =[Zjkm∣X=x] =E[Z^m_jk X=x] =gjkm(x). =g^m_jk(x). This argument only requires the conditional mean equality [Zjkm∣X,Sm]=[Zjkm∣X]E[Z^m_jk X,S^m]=E[Z^m_jk X] almost surely. It does not require joint independence across menus. Thus, our method handles the case where only one menu is observed per context (i.e., ∑m∈Sm=1 _m S^m=1). The equality holds for every m∈jkm _jk. Hence, we identify each off-diagonal payoff entry by substituting the observed-data regressions into Eq. (4): Ajk(x)=fjk(μ0,jkm(x):m∈jk).A_jk(x)=f_jk\! ( \μ^m_0,jk(x):m _jk \ ). Pairwise menu coverage ensures that jkQ_jk is nonempty, and menu-specific positivity applies to every menu in this set. Definition 1 fixes Ajj(x)=0A_j(x)=0, so the observed-data law identifies the entire contextual payoff matrix A(x)A(x). Under the regularizer conditions in Assumptions 3(i) and 4, Ω is fixed and the equilibrium is unique, so Eq. (5) also identifies π⋆(x)π (x). ∎ J.3 Efficient influence function of the average payoff Lemma 2 (Efficient influence function of the average payoff). Under Assumptions 1–3, fix j≠kj≠ k and define the average payoff ψjk:=0[Ajk(X)] _jk:=E_0[A_jk(X)]. In the nonparametric observed-data model, we obtain the efficient influence function of ψjk _jk at P0P_0 by centering the pseudo-outcome in Eq. (42) at the true nuisance η0=(μ0,e0) _0=( _0,e_0): φjk(O,P0)=Γjk(O,η0)−ψjk. _jk(O;P_0)= _jk(O; _0)- _jk. (90) In particular, 0[Γjk(O,η0)]=ψjkE_0[ _jk(O; _0)]= _jk and 0[φjk(O,P0)]=0E_0[ _jk(O;P_0)]=0. Proof of Lemma 2. We consider a regular one-dimensional parametric submodel Pt:|t|<δ\P_t:|t|<δ\ of the observed-data law, with Pt=0=P0P_t=0=P_0. Let the densities be ptp_t. We write O=(X,,~)O=(X,S, Y), where =(Sm)m∈S=(S^m)_m and ~=(SmYm)m∈ Y=(S^mY_m)_m . We factor the joint density as pt(o)=pt(x)pt(∣x)pt(~∣x,). p_t(o)=p_t(x)\,p_t(s x)\,p_t( y x,s). We define the score as the derivative of the log density at t=0t=0: s(O) s(O) :=dtlogpt(O)|t=0 := . ddt p_t(O) |_t=0 =sX(X)+s|X(∣X)+s~|X,(~∣X,), =s_X(X)+s_S X(S X)+s_ Y X,S( Y X,S), where each component is the log derivative of the corresponding density factor. The score has finite second moment, and its components satisfy 0 _0 [sX(X)]=0, [s_X(X)]=0, 0 _0 [s|X(∣X)∣X]=0, [s_S X(S X) X]=0, 0 _0 [s~|X,(~∣X,)∣X,]=0. [s_ Y X,S( Y X,S) X,S]=0. Thus, 0[s(O)]=0E_0[s(O)]=0, sX(X)=0[s(O)∣X]s_X(X)=E_0[s(O) X], and s−sXs-s_X is the conditional score of O given X. We fix j≠kj≠ k and abbreviate f=fjkf=f_jk. Under PtP_t, we define μt,jkm(x)=Pt[Zjkm∣X=x,Sm=1]μ^m_t,jk(x)=E_P_t[Z^m_jk X=x,S^m=1] and collect these regressions in μt(x)=(μt,jkm(x))m∈jk _t(x)=(μ^m_t,jk(x))_m _jk. We write ψt=Pt[f(μt(X))] _t=E_P_t[f( _t(X))] and ψ0=ψjk _0= _jk. The product and chain rules give ψ˙0 ψ_0 :=dtψt|t=0 := . ddt _t |_t=0 (91) =0[f(μ0(X))−ψ0sX(X)]+∑m∈jk0[∂mf(μ0(X))μ˙0m(X)], =E_0\! [\f( _0(X))- _0\s_X(X) ]+ _m _jkE_0\! [ _mf( _0(X)) μ^m_0(X) ], where ∂mf=∂f/∂um _mf=∂ f/∂ u_m and μ˙0m=dμt,jkm/dt|t=0 μ^m_0= .dμ^m_t,jk/dt |_t=0. In order to get μ˙0m μ^m_0, we compute the regression derivative using the observed-data ratio μt,jkm(x)=Pt[SmZjkm∣X=x]Pt[Sm∣X=x]. μ^m_t,jk(x)= E_P_t[S^mZ^m_jk X=x]E_P_t[S^m X=x]. The quotient rule and the conditional score identity yield μ˙0m(x) μ^m_0(x) =1e0m(x)0[SmZjkm−μ0,jkm(x)s(O)−sX(x)∣X=x] = 1e^m_0(x)E_0\! [S^m\Z^m_jk-μ^m_0,jk(x)\\s(O)-s_X(x)\ X=x ] (92) =0[Sme0m(x)Zjkm−μ0,jkm(x)s(O)∣X=x]. =E_0\! [ S^me^m_0(x)\Z^m_jk-μ^m_0,jk(x)\s(O) X=x ]. For the second equality, we use 0[SmZjkm−μ0,jkm(x)∣X=x]=0E_0[S^m\Z^m_jk-μ^m_0,jk(x)\ X=x]=0. Then, we substitute Eq. (92) into Eq. (91) and apply iterated expectations. Since f(μ0(X))f( _0(X)) is a function of X, we obtain ψ˙0 ψ_0 =0[f(μ0(X))−ψ0s(O)] =E_0\! [\f( _0(X))- _0\s(O) ] (93) +∑m∈jk0[∂mf(μ0(X))Sme0m(X)Zmjk−μm0,jk(X)s(O)] + _m _jkE_0\! [ _mf( _0(X)) S^me^m_0(X) \Z^m_jk-μ^m_0,jk(X) \s(O) ] =0[Γjk(O,η0)−ψjks(O)]. =E_0\! [\ _jk(O; _0)- _jk\s(O) ]. We now verify the EIF definition in Section D.1 for φjk(O,P0):=Γjk(O,η0)−ψjk _jk(O;P_0):= _jk(O; _0)- _jk. Each residual correction has conditional mean zero given X, and 0[f(μ0(X))]=ψjkE_0[f( _0(X))]= _jk, so 0[φjk]=0E_0[ _jk]=0. Bounded verdicts, bounded derivatives, and positivity give 0[φjk2]<∞E_0[ _jk^2]<∞. Thus, φjk _jk belongs to L20(P0)L_2^0(P_0), the space of square-integrable mean-zero functions, which is the closed tangent space of the nonparametric observed-data model. Since the submodel was arbitrary, Eq. (93) represents every pathwise derivative exactly as required by Eq. (37), with ψ=ψjkψ= _jk and φ=φjk = _jk. These properties establish that φjk _jk is the unique canonical gradient and hence the EIF. At a generic law P, we obtain φjk(O,P)=Γjk(O,ηP)−ψjk(P) _jk(O;P)= _jk(O; _P)- _jk(P), as stated in Eq. (41). We add back ψjk(P) _jk(P) and replace ηP _P by a generic nuisance η to obtain the uncentered pseudo-outcome in Eq. (42). ∎ J.4 Neyman-orthogonality of Γjk _jk We prove conditional unbiasedness and Neyman-orthogonality under Assumptions 1–3. Proof. We fix j≠kj≠ k, a direction h, and a context x outside the null sets in the assumptions and the conditional expectation identities below. We write ηt=η0+th _t= _0+th for |t|≤t0|t|≤ t_0. Since μ0,jkm(x)∈[−1,1]μ^m_0,jk(x)∈[-1,1] and e0m(x)≥e¯e^m_0(x)≥ e, we can choose t0=t0(x,h)>0t_0=t_0(x,h)>0 small enough that μtm(x)∈Iαμ^m_t(x)∈ I_α and etm(x)>0e^m_t(x)>0 for every m∈jkm _jk. We write f=fjkf=f_jk and collect the outcome components into ut(x)=μtm(x)m∈jku_t(x)=\ _t^m(x)\_m _jk, so ut(x)=u0(x)+thμ(x)u_t(x)=u_0(x)+th_μ(x). Assumption 1 gives gjkm(x)=μ0,jkm(x)g^m_jk(x)=μ^m_0,jk(x) and hence Ajk(x)=f(u0(x))A_jk(x)=f(u_0(x)). Define G(t):=0[Γjk(O,ηt)|X=x],|t|≤t0,G(t)\ :=\ E_0 [ _jk(O; _t)\ |\ X=x ], |t|≤ t_0, (94) where the expectation remains under the fixed law P0P_0 as the nuisance argument varies. We will show G(0)=Ajk(x)G(0)=A_jk(x) and G′(0)=0G (0)=0. Bounded verdicts, continuity of the aggregator gradient, and positive propensities give conditional integrability along the path. Conditional on X=xX=x, the nuisance factors in Eq. (42) are deterministic, so G(t)=f(ut(x))+∑m∈jk∂f∂um(ut(x))1etm(x)0[SmZjkm−μtm(x)|X=x]⏟=:Tm(t).G(t)=f (u_t(x) )+ _m _jk ∂ f∂ u_m (u_t(x) )\, 1e^m_t(x)\, E_0 [S^m \Z^m_jk-μ^m_t(x) \\ |\ X=x ]_=:\,T_m(t). (95) The selected residual has an explicit conditional mean. By the definition of the observed-data regression μ0,jkmμ^m_0,jk, 0[SmZjkm∣X=x]=e0m(x)0[Zjkm∣X=x,Sm=1]=e0m(x)μ0,jkm(x).E_0[S^mZ^m_jk X=x]=e^m_0(x)E_0[Z^m_jk X=x,S^m=1]=e^m_0(x)μ^m_0,jk(x). (96) This identity does not require MAR. We use Assumption 1 only to identify the regression with the full-data margin. Since 0[Smμtm(x)∣X=x]=e0m(x)μtm(x)E_0[S^mμ^m_t(x) X=x]=e^m_0(x)μ^m_t(x), subtracting gives Tm(t)=e0m(x)μ0,jkm(x)−μtm(x)=−te0m(x)hμm(x),T_m(t)=e^m_0(x) \μ^m_0,jk(x)-μ^m_t(x) \=-\,t\,e^m_0(x)\,h_μ^m(x), (97) where the last equality uses μt=μ0+thμ _t= _0+th_μ. Substituting this expression into Eq. (95), we obtain G(t)=f(ut(x))−tB(t),B(t):=∑m∈jk∂f∂um(ut(x))e0m(x)etm(x)hμm(x).G(t)=f (u_t(x) )\ -\ t\,B(t), B(t):= _m _jk ∂ f∂ u_m (u_t(x) )\, e^m_0(x)e^m_t(x)\,h_μ^m(x). (98) We use this expression as a version of the conditional expectation for all |t|≤t0|t|≤ t_0. At t=0t=0 it gives G(0)=f(u0(x))=Ajk(x)G(0)=f(u_0(x))=A_jk(x), proving conditional unbiasedness. Continuity of the gradient and positivity of the denominators imply that B(t)B(t) is continuous at zero. We can now differentiate the explicit expression for G, without interchanging a derivative and an expectation. For t≠0t≠ 0, equation 98 gives G(t)−G(0)t=f(ut(x))−f(u0(x))t−B(t). G(t)-G(0)t= f (u_t(x) )-f (u_0(x) )t-B(t). (99) By Assumption 3, the chain rule along the affine path ut(x)=u0(x)+thμ(x)u_t(x)=u_0(x)+th_μ(x) gives dtf(ut(x))|t=0=∑m∈jk∂f∂um(u0(x))hμm(x)=⟨∇f(u0(x)),hμ(x)⟩. . ddtf (u_t(x) ) |_t=0= _m _jk ∂ f∂ u_m (u_0(x) )\,h_μ^m(x)= ∇ f (u_0(x) ),\ h_μ(x) . (100) Since etm(x)=e0m(x)e^m_t(x)=e^m_0(x) at t=0t=0, the limit of the correction term is B(0)=∑m∈jk∂f∂um(u0(x))hμm(x)=⟨∇f(u0(x)),hμ(x)⟩.B(0)= _m _jk ∂ f∂ u_m (u_0(x) )\,h_μ^m(x)= ∇ f (u_0(x) ),\ h_μ(x) . (101) The limits in equation 100 and equation 101 cancel in equation 99, giving G′(0)=⟨∇f(u0(x)),hμ(x)⟩−⟨∇f(u0(x)),hμ(x)⟩=0. G (0)= ∇ f(u_0(x)),h_μ(x) - ∇ f(u_0(x)),h_μ(x) =0. Thus, for every direction h, Neyman-orthogonality holds for PXP_X-almost every x. ∎ J.5 Exact conditional bias and second-order remainder We derive the exact conditional bias and prove Eq. (12) under the identification, boundedness, and smoothness conditions in Assumptions 1–3. Lemma 3 (Exact conditional bias). Under these conditions, we fix j≠kj≠ k, write f=fjkf=f_jk and μ(x)=(μjkm(x))m∈jkμ(x)=(μ^m_jk(x))_m _jk, and consider a generic nuisance η=(μ,e)η=(μ,e) with μjkm(x)∈Iαμ^m_jk(x)∈ I_α and em(x)>0e^m(x)>0. We define Δμ=μ−μ0 μ=μ- _0 and Δem=em−e0m e^m=e^m-e^m_0. Then, for almost every x, 0[Γjk(O,η)∣X=x]−Ajk(x)=−Rf(x)+∑m∈jk∂f∂um(μ(x))Δem(x)em(x)Δμm(x),E_0 [ _jk(O;η) X=x ]-A_jk(x)=-R_f(x)+ _m _jk ∂ f∂ u_m (μ(x) )\, e^m(x)e^m(x)\, μ^m(x), (102) where Rf(x)=f(μ0(x))−f(μ(x))−⟨∇f(μ(x)),μ0(x)−μ(x)⟩R_f(x)=f( _0(x))-f(μ(x))- ∇ f(μ(x)),\, _0(x)-μ(x) is the first-order Taylor remainder of f at μ(x)μ(x). Consequently, Eq. (12) holds. Proof. We fix x and suppress it below. The selected residual has conditional mean 0[Sm(Zjkm−μjkm)∣X=x]=−e0mΔμmE_0[S^m(Z^m_jk-μ^m_jk) X=x]=-e^m_0 μ^m. We substitute this identity into Eq. (42) and use Ajk(x)=f(μ0)A_jk(x)=f( _0) to obtain AjkDB(x,η)−Ajk(x) A^DB_jk(x;η)-A_jk(x) =f(μ)−f(μ0)−∑m∈jk∂mf(μ)e0memΔμm =f(μ)-f( _0)- _m _jk _mf(μ) e^m_0e^m μ^m =f(μ)−f(μ0)−⟨∇f(μ),Δμ⟩⏟−Rf(x)+∑m∈jk∂mf(μ)(1−e0mem)Δμm. = f(μ)-f( _0)- ∇ f(μ), μ _-R_f(x)+ _m _jk _mf(μ) (1- e^m_0e^m ) μ^m. The identity 1−e0m/em=Δem/em1-e^m_0/e^m= e^m/e^m gives Eq. (102). Since μ0(x)∈[−1,1]jk _0(x)∈[-1,1]^Q_jk and IαjkI_α^Q_jk is convex, the segment between μ(x)μ(x) and μ0(x) _0(x) lies in IαjkI_α^Q_jk. The Lipschitz gradient bound therefore gives |Rf(x)|≤(Lf/2)‖Δμ(x)‖22|R_f(x)|≤(L_f/2)\| μ(x)\|_2^2, and the triangle inequality proves Eq. (12). The Lipschitz gradient on the bounded cube IαjkI_α^Q_jk also gives Gf:=maxsupu∈Iαjkj≠k‖∇fjk(u)‖1<∞G_f:= _j≠ k _u∈ I_α^Q_jk\|∇ f_jk(u)\|_1<∞. If em(x)≥e¯e^m(x)≥ e, as in Assumption 2, then |0[Γjk(O,η)∣X=x]−Ajk(x)|≤Lf2‖Δμ(x)‖22+Gfe¯maxm∈jk|Δem(x)Δμm(x)|. |E_0 [ _jk(O;η) X=x ]-A_jk(x) |\ ≤\ L_f2 \| μ(x) \|_2^2+ G_f e _m _jk | e^m(x) μ^m(x) |. (103) ∎ Under the remainder-component conditions in Eq. (86), this bound yields conditional bias of order Op(rμ2+rμre)O_p(r_μ^2+r_μr_e) in L2(PX)L_2(P_X). For an affine aggregator, Rf≡0R_f≡ 0, and Eq. (102) vanishes if either μ=μ0μ= _0 or e=e0e=e_0. For a nonlinear aggregator, correct propensities alone leave the outcome-curvature term −Rf(x)-R_f(x). J.6 Proof of Proposition 2 Proof. Theorem 1 gives ADB(x,η0)=A(x)A^DB(x; _0)=A(x), and Proposition 4 gives GΩ(π,A(x),x)≥0G_ (π;A(x),x)≥ 0, with equality exactly when π=π⋆(x)π=π (x). Under Assumption 7, we choose θ0 _0 with πθ0(X)=π⋆(X) _ _0(X)=π (X) almost surely, so ℒ(θ0,η0)=0L( _0; _0)=0 is the minimum risk. Every minimizer therefore has zero expected nonnegative gap, which implies πθ(X)=π⋆(X) _θ(X)=π (X) almost surely. Conversely, every such policy has zero risk and attains the minimum. ∎ J.7 Proof of Theorem 2 We first prove differentiability under Assumptions 2–4. We then use identification and the payoff remainder to prove universal Neyman-orthogonality. Proof. Differentiability. We fix a nuisance η satisfying Assumption 2 and write B(x)=ADB(x,η)B(x)=A^DB(x;η). The Lipschitz aggregator gradients on the bounded domain IαjkI_α^Q_jk and the propensity lower bound give a uniform bound on B(x)B(x) through Eq. (42). For any matrix B, strong convexity gives the unique maximizer qB(p):=argminq∈ΔKΩ(q)−⟨Bp,q⟩q_B(p):= _q∈ _K\ (q)- Bp,q \ in the variational gap. Danskin’s theorem gives gB(p):=∇pGΩ(p,B,x)=∇Ω(p)−(B+B⊤)p+B⊤qB(p). g_B(p):= _pG_ (p;B,x)=∇ (p)-(B+B )p+B q_B(p). (104) This formula holds without skew-symmetry of B and reduces to Eq. (33) when B is skew-symmetric. We fix a direction hθh_θ and define ℓt(x):=GΩ(πθ+thθ(x),B(x),x) _t(x):=G_ ( _θ+th_θ(x);B(x),x). The chain rule gives dtℓt(x)=⟨gB(x)(πθ+thθ(x)),Dθπθ+thθ(x)[hθ]⟩. ddt _t(x)= g_B(x)( _θ+th_θ(x)),D_θ _θ+th_θ(x)[h_θ] . The uniform bound on B(x)B(x) and continuity of ∇Ω∇ on the compact simplex give ‖gB(x)(p)‖∗≤Cg\|g_B(x)(p)\|_*≤ C_g uniformly in x and p∈ΔKp∈ _K. For sufficiently small |t||t|, the segment from θ to θ+thθ+th_θ lies in UθU_θ. The mean value theorem and duality therefore give |ℓt(X)−ℓ0(X)t|≤CgMθ(X)‖hθ‖2. | _t(X)- _0(X)t |≤ C_gM_θ(X)\|h_θ\|_2. Eq. (85) makes the bound integrable, so dominated convergence justifies differentiation under expectation. The chain rule at t=0t=0 then gives Dθℒ(θ,η)[hθ] D_θL(θ;η)[h_θ] =X[⟨gB(X)(πθ(X)),Dθπθ(X)[hθ]⟩]. =E_X\! [ g_B(X)( _θ(X)),D_θ _θ(X)[h_θ] ]. (105) Therefore, the loss is differentiable with respect to θ. Neyman-orthogonality. We fix θ, a policy direction hθh_θ, and a bounded nuisance direction hηh_η. We write Bt(x)=ADB(x,η0+thη)B_t(x)=A^DB(x; _0+th_η), so B0(x)=A(x)B_0(x)=A(x). Positivity and boundedness of hηh_η give etm(x)≥e¯/2e_t^m(x)≥ e/2 for sufficiently small |t||t|. Since μ0,jkm(x)∈[−1,1]μ^m_0,jk(x)∈[-1,1], boundedness of hηh_η also gives μ0,jkm(x)+thμm(x)∈Iαμ^m_0,jk(x)+th^m_μ(x)∈ I_α when |t|‖hμ‖∞<αμ|t|\|h_μ\|_∞< _μ. Eq. (12), the Lipschitz aggregator gradients, and the finite pair and menu collections therefore give esssupx‖Bt(x)−A(x)‖⋆≤Cht2, ess\,sup_x\|B_t(x)-A(x)\|_ ≤ C_ht^2, (106) where ChC_h is independent of x and t. We next bound the change in the policy gradient induced by a payoff perturbation. We fix x, suppress it below, and use the maximizer qB(p)q_B(p) defined above. We add the first-order optimality inequalities for qB(p)q_B(p) and qA(p)q_A(p) and use strong convexity to obtain κ‖qB(p)−qA(p)‖2 κ\|q_B(p)-q_A(p)\|^2 ≤⟨(B−A)p,qB(p)−qA(p)⟩, ≤ (B-A)p,q_B(p)-q_A(p) , ‖qB(p)−qA(p)‖ \|q_B(p)-q_A(p)\| ≤κ−1‖B−A‖⋆. ≤κ^-1\|B-A\|_ . The second inequality uses duality and the norm normalization in Section 4. We apply Eq. (104) and ‖B⊤‖⋆=‖B‖⋆\|B \|_ =\|B\|_ to obtain ‖gB(p)−gA(p)‖∗ \|g_B(p)-g_A(p)\|_* ≤3‖B−A‖⋆+‖A‖⋆‖qB(p)−qA(p)‖ ≤ 3\|B-A\|_ +\|A\|_ \|q_B(p)-q_A(p)\| ≤(3+κ−1‖A‖⋆)‖B−A‖⋆. ≤(3+κ^-1\|A\|_ )\|B-A\|_ . (107) The true payoff is uniformly bounded, so CA:=3+κ−1esssupx‖A(x)‖⋆<∞C_A:=3+κ^-1 ess\,sup_x\|A(x)\|_ <∞ bounds the factor on the right uniformly in x and p. We now combine the payoff remainder with the policy-gradient bound. Along the path η0+thη _0+th_η, the same domination argument applies with propensity lower bound e¯/2 e/2. We apply Eq. (105) and the bounds in Eqs. (106) and (107) to obtain |Dθℒ(θ,η0+thη)[hθ]−Dθℒ(θ,η0)[hθ]| |D_θL(θ; _0+th_η)[h_θ]-D_θL(θ; _0)[h_θ] | ≤CACht2‖hθ‖2X[Mθ(X)]. ≤ C_AC_ht^2\|h_θ\|_2E_X[M_θ(X)]. (108) We divide by |t||t| and let t→0t→ 0. Hence, DηDθℒ(θ,η0)[hθ,hη]=limt→0Dθℒ(θ,η0+thη)[hθ]−Dθℒ(θ,η0)[hθ]t=0. D_ηD_θL(θ; _0)[h_θ,h_η]= _t→ 0 D_θL(θ; _0+th_η)[h_θ]-D_θL(θ; _0)[h_θ]t=0. Since θ was arbitrary, this proves the universal Neyman-orthogonality in Eq. (15). ∎ J.8 Empirical error bound We first establish the deterministic oracle comparison underlying Theorem 3 using boundedness, smoothness, and strong convexity in Assumptions 2–4. We then use identification, cross-fitting, and the estimation rates in Assumptions 1, 5, and 6 to obtain the rate form. The comparison does not require realizability or a specified generalization rate. Proof. Let θ θ be an empirical minimizer of ℒ^n L_n as defined in Eq. (17). We define the population loss and abbreviate the deviation and payoff error as ℒ^(θ) L(θ) :=X[GΩ(πθ(X),A^DB(X,η^),X)], :=E_X[G_ ( _θ(X); A^DB(X; η),X)], εgen _gen :=supθ∈Θ|ℒ^(θ)−ℒ^n(θ)|,ℰA:=κ−1X‖A^DB(X,η^)−A(X)‖⋆2. := _θ∈ | L(θ)- L_n(θ)|, _A:=κ^-1E_X\| A^DB(X; η)-A(X)\|_ ^2. Fix a context x at which the assumptions hold, write A=A(x)A=A(x) and B=A^DB(x,η^)B= A^DB(x; η), and let p∈ΔKp∈ _K be arbitrary. For either payoff C∈A,BC∈\A,B\, define φC(p,q):=⟨−Cp,p−q⟩+Ω(p)−Ω(q),q∈ΔK. _C(p,q):= -Cp,p-q + (p)- (q), q∈ _K. By the variational expression in the gap definition equation 14, GΩ(p,C,x)=maxq∈ΔKφC(p,q)G_ (p;C,x)= _q∈ _K _C(p,q). By Assumption 3, Ω is continuous, so q↦φC(p,q)q _C(p,q) is continuous on the compact simplex and attains a finite maximum. Taking q=pq=p gives φC(p,p)=0 _C(p,p)=0, so both gaps are nonnegative. The candidate p need not be an equilibrium of either game. To compare the gaps, we use strong concavity in the opponent strategy. For q0,q1∈ΔKq_0,q_1∈ _K and α∈[0,1]α∈[0,1], put qα=(1−α)q0+αq1q_α=(1-α)q_0+α q_1. Assumption 4 gives Ω(qα)≤(1−α)Ω(q0)+αΩ(q1)−κ2α(1−α)‖q1−q0‖2. (q_α)≤(1-α) (q_0)+α (q_1)- κ2α(1-α)\|q_1-q_0\|^2. The term ⟨−Bp,p−q⟩ -Bp,p-q is affine in q, and Ω(p) (p) is constant in q. Negating the displayed inequality and adding these terms therefore yields φB(p,qα) _B(p,q_α) ≥(1−α)φB(p,q0)+αφB(p,q1) ≥(1-α) _B(p,q_0)+α _B(p,q_1) +κ2α(1−α)‖q1−q0‖2. + κ2α(1-α)\|q_1-q_0\|^2. (109) Thus q↦φB(p,q)q _B(p,q) is κ-strongly concave with respect to the same norm used in the theorem. Fix α∈(0,1)α∈(0,1). For any q∈ΔKq∈ _K, apply equation 109 with q0=pq_0=p and q1=q_1=q. Since (1−α)p+αq∈ΔK(1-α)p+α q∈ _K and φB(p,p)=0 _B(p,p)=0, GΩ(p,B,x) G_ (p;B,x) ≥φB(p,(1−α)p+αq) ≥ _B (p,(1-α)p+α q ) ≥αφB(p,q)+κ2α(1−α)‖p−q‖2. ≥α _B(p,q)+ κ2α(1-α)\|p-q\|^2. Dividing by α and rearranging gives φB(p,q)≤1αGΩ(p,B,x)−κ(1−α)2‖p−q‖2(q∈ΔK). _B(p,q)≤ 1αG_ (p;B,x)- κ(1-α)2\|p-q\|^2 (q∈ _K). (110) The midpoint choice α=1/2α=1/2 gives the coefficient 22 on the gap; retaining α allows that coefficient to approach 11. We now relate the two payoff matrices. Write E=B−AE=B-A. Subtracting the two variational gap objectives gives the exact identity φA(p,q)=φB(p,q)+⟨Ep,p−q⟩. _A(p,q)= _B(p,q)+ Ep,p-q . This identity holds for arbitrary real matrices A and B. Let a=‖Ep‖∗≥0a=\|Ep\|_*≥ 0. The dual-norm inequality gives ⟨Ep,p−q⟩≤a‖p−q‖ Ep,p-q ≤ a\|p-q\|. Combining this with equation 110 yields GΩ(p,A,x) G_ (p;A,x) ≤1αGΩ(p,B,x)+maxq∈ΔKa‖p−q‖−κ(1−α)2‖p−q‖2 ≤ 1αG_ (p;B,x)+ _q∈ _K \a\|p-q\|- κ(1-α)2\|p-q\|^2 \ ≤1αGΩ(p,B,x)+supt≥0at−κ(1−α)2t2. ≤ 1αG_ (p;B,x)+ _t≥ 0 \at- κ(1-α)2t^2 \. The second inequality enlarges the set of feasible distances to all nonnegative real numbers. Completing the square, at−κ(1−α)2t2=a22κ(1−α)−κ(1−α)2(t−aκ(1−α))2. at- κ(1-α)2t^2= a^22κ(1-α)- κ(1-α)2 (t- aκ(1-α) )^2. The supremum is a2/[2κ(1−α)]a^2/[2κ(1-α)], attained at t=a/[κ(1−α)]t=a/[κ(1-α)]. Taking α=1/2α=1/2 gives GΩ(p,A,x)≤2GΩ(p,B,x)+1κ‖(B−A)p‖∗2.G_ (p;A,x)≤ 2G_ (p;B,x)+ 1κ\|(B-A)p\|_*^2. (111) This argument applies to every p∈ΔKp∈ _K, including boundary policies. Interchanging A and B gives the reverse comparison with the same squared error, since ‖(A−B)p‖∗=‖(B−A)p‖∗\|(A-B)p\|_*=\|(B-A)p\|_*. Apply equation 111 with p=πθ^(X)p= _ θ(X) and B=A^DB(X,η^)B= A^DB(X; η). Under our measurability conventions, the expectation over contexts is well defined, and Expl(πθ^)≤2ℒ^(θ^)+1κX[‖(A^DB(X,η^)−A(X))πθ^(X)‖∗2].Expl( _ θ)≤ 2 L( θ)+ 1κE_X\! [ \|( A^DB(X; η)-A(X)) _ θ(X) \|_*^2 ]. All integrands are nonnegative, so the inequality also holds with an infinite right-hand side if the payoff error has no finite second moment. The L2(PX)L_2(P_X) payoff error in Assumption 2 and compactness of the strategy domain ensure a finite population gap. By the definition of the uniform deviation, ℒ^(θ^)≤ℒ^n(θ^)+εgen. L( θ)≤ L_n( θ)+ _gen. This inequality applies to the data-dependent θ θ because the supremum defining εgen _gen is over all θ∈Θθ∈ . Substituting it gives the intermediate bound equation 112. Empirical minimization further allows ℒ^n(θ^) L_n( θ) to be written as infθ∈Θℒ^n(θ) _θ∈ L_n(θ), although the bound itself holds for any fitted policy in the class. Thus the resulting bound is Expl(πθ^)≤2ℒ^n(θ^)+εgen+1κX[‖(A^DB(X,η^)−A(X))πθ^(X)‖∗2].Expl( _ θ)≤ 2 \ L_n( θ)+ _gen \+ 1κE_X\! [ \|( A^DB(X; η)-A(X)) _ θ(X) \|_*^2 ]. (112) Write ℒA(θ):=X[GΩ(πθ(X),A(X),X)]=Expl(πθ)L^A(θ):=E_X[G_ ( _θ(X);A(X),X)]=Expl( _θ), and let δ(θ):=12κX[‖(A^DB(X,η^)−A(X))πθ(X)‖∗2]. δ(θ):= 12κE_X\! [ \|( A^DB(X; η)-A(X)) _θ(X) \|_*^2 ]. Applying equation 111 in both directions and taking expectations over X gives ℒA(θ)≤2ℒ^(θ)+2δ(θ),ℒ^(θ)≤2ℒA(θ)+2δ(θ). ^A(θ)≤ 2 L(θ)+2δ(θ), L(θ)≤ 2L^A(θ)+2δ(θ). For any comparator θ∈Θθ∈ , the definition of εgen _gen and empirical optimality yield ℒ^(θ^) L( θ) ≤ℒ^n(θ^)+εgen ≤ L_n( θ)+ _gen ≤ℒ^n(θ)+εgen≤ℒ^(θ)+2εgen. ≤ L_n(θ)+ _gen≤ L(θ)+2 _gen. (113) Using the forward comparison at θ θ and the reverse comparison at θ therefore gives Expl(πθ^)≤4ℒA(θ)+4εgen+4δ(θ)+2δ(θ^).Expl( _ θ)≤ 4L^A(θ)+4 _gen+4δ(θ)+2δ( θ). (114) The norm normalization in Section 4 gives δ(θ)≤ℰA/2δ(θ) _A/2 uniformly over θ. Taking the infimum gives the deterministic oracle inequality Expl(πθ^)≤4infθ∈ΘExpl(πθ)+4εgen+3ℰA.Expl( _ θ)≤ 4 _θ∈ Expl( _θ)+4 _gen+3E_A. (115) No population minimizer is required. If ℰAE_A or εgen _gen is infinite, the inequality holds with an infinite right-hand side. To obtain the rate form in the theorem, we use the remaining assumptions. The norm normalization in Section 4 gives ‖(A^DB−A)πθ^‖∗≤‖A^DB−A‖⋆\|( A^DB-A) _ θ\|_*≤\| A^DB-A\|_ . We separate the error of the second-stage regression from the bias induced by the fitted nuisances: A^DB(⋅,η^)−A=A^DB(⋅,η^)−ADB(⋅,η^)+ADB(⋅,η^)−A. A^DB(·; η)-A= \ A^DB(·; η)-A^DB(·; η) \+ \A^DB(·; η)-A \. The first term has maximum entrywise L2(PX)L_2(P_X) error eAe_A by Eq. (87). Let bn:=maxj,k‖AjkDB(⋅,η^)−Ajk‖L2(PX). b_n:= _j,k\|A^DB_jk(·; η)-A_jk\|_L_2(P_X). The positivity and smoothness conditions in Assumptions 2 and 3 allow us to apply equation 103. Since ‖maxm|vm|‖L22≤∑m‖vm‖L22\| _m|v_m|\|_L_2^2≤ _m\|v_m\|_L_2^2 and the menu collections are fixed, the remainder-component rates in Assumption 6 give bn=Op(rμ2+e¯−1rμre)b_n=O_p(r_μ^2+ e^-1r_μr_e). Under Assumption 5, the triangle inequality gives the same bound for the average of the fold-specific targets. The triangle inequality also gives maxj,k‖A^jkDB−Ajk‖L2(PX)≤eA+bn _j,k\| A^DB_jk-A_jk\|_L_2(P_X)≤ e_A+b_n. Thus, writing CmatC_mat for the norm-comparison constant defined in the notation paragraph, ℰA≤Cmatκ∑j,k‖A^jkDB−Ajk‖L2(PX)2≤2CmatK2κ(eA2+bn2). _A≤ C_matκ _j,k\| A^DB_jk-A_jk\|_L_2(P_X)^2≤ 2C_matK^2κ(e_A^2+b_n^2). Squaring the rate for bnb_n yields ℰA=1κX‖A^DB−A‖⋆2=Op(K2κ(eA2+rμ4+e¯−2rμ2re2)).E_A= 1κE_X\| A^DB-A\|_ ^2=O_p\! ( K^2κ (e_A^2+r_μ^4+ e^-2r_μ^2r_e^2 ) ). (116) The OpO_p constant depends on CmatC_mat, LfL_f, and GfG_f. For non-Euclidean policy norms, CmatC_mat can itself depend on K, whereas the Euclidean norm gives Cmat=1C_mat=1. For the affine aggregators of Section 4, Lf=0L_f=0 and Rf≡0R_f≡ 0, so the rμ4r_μ^4 term is absent and the nuisance contribution is e¯−2rμ2re2 e^-2r_μ^2r_e^2. Substituting equation 116 into equation 115, expanding εgen _gen as its defining supremum, and absorbing the factor 33 into Op(⋅)O_p(·) proves exactly equation 19. The stochastic remainder is nonnegative and is bounded by a stochastically bounded multiplier of the displayed scale, which includes the random regression error eA2e_A^2. Neither realizability nor a rate for the generalization deviation is used in this argument. ∎ J.9 Proof of Corollary 1 We specialize Theorem 3 under realizability and loss-class complexity in Assumptions 7 and 8, the bounded loss envelope in Assumption 2, and the additional rates in Eq. (88). Proof. Write ℒA(θ):=Expl(πθ)L^A(θ):=Expl( _θ). Assumption 7 implies infθ∈ΘℒA(θ)=0 _θ∈ L^A(θ)=0. We first establish the oracle rate, which does not use the nuisance or payoff convergence rates in equation 88. We use the i.i.d. sampling in Assumption 5 and the complexity bound in Assumption 8 to control generalization. For a measurable function h, write Ph:=Xh(X)Ph:=E_Xh(X) and Pnh:=n−1∑ih(Xi)P_nh:=n^-1 _ih(X_i), and set Zn:=suph∈ℋn|Ph−Pnh|Z_n:= _h _n|Ph-P_nh|. Let X1′,…,Xn′X _1,…,X _n be an independent copy of the contexts, with empirical average Pn′P _n. Jensen’s inequality gives the first bound below. Independently swapping each pair (Xi,Xi′)(X_i,X _i) leaves its law unchanged, which gives the equality after introducing the signs. The triangle inequality then gives Zn _n ≤X,X′suph∈ℋn|Pn′h−Pnh| _X,X _h _n|P _nh-P_nh| =X,X′,σsuph∈ℋn|1n∑i=1nσih(Xi′)−h(Xi)| =E_X,X ,σ _h _n | 1n _i=1^n _i\h(X _i)-h(X_i)\ | ≤2ℜn(ℋn)≤2Cn−1/2. ≤ 2 R_n(H_n)≤ 2Cn^-1/2. Markov’s inequality implies Zn=Op(n−1/2)Z_n=O_p(n^-1/2). To define the oracle benchmark, let ℒn,or(θ):=1n∑i=1nGΩ(πθ(Xi),A(Xi),Xi),θ^or∈argminθ∈Θℒn,or(θ). _n,or(θ):= 1n _i=1^nG_ ( _θ(X_i);A(X_i),X_i), θ_or∈ _θ∈ L_n,or(θ). Because A∈ℬnA _n, its deviation εgen,or:=supθ∈Θ|ℒA(θ)−ℒn,or(θ)| _gen,or:= _θ∈ |L^A(θ)-L_n,or(θ)| also satisfies εgen,or≤Zn=Op(n−1/2) _gen,or≤ Z_n=O_p(n^-1/2). For every θ∈Θθ∈ , ℒA(θ^or)≤ℒn,or(θ^or)+εgen,or≤ℒn,or(θ)+εgen,or≤ℒA(θ)+2εgen,or. ^A( θ_or) _n,or( θ_or)+ _gen,or _n,or(θ)+ _gen,or ^A(θ)+2 _gen,or. Taking the infimum and using realizability proves Expl(πθ^or)=Op(n−1/2)Expl( _ θ_or)=O_p(n^-1/2). For the learner using the estimated payoff, retain εgen _gen and ℰAE_A as defined in the theorem proof. On the event that the fitted payoff belongs to ℬnB_n, we have εgen≤Zn _gen≤ Z_n. This event has probability tending to one, so εgen=Op(n−1/2) _gen=O_p(n^-1/2) even when the fitted payoff uses the policy-training observations. The deterministic comparison equation 115 and realizability give Expl(πθ^)≤4εgen+3ℰA. ( _ θ)≤ 4 _gen+3E_A. The matrix-norm comparison in the notation paragraph and the payoff-error decomposition used in equation 116 give ℰA≲1κ∑j,k‖A^jkDB−Ajk‖L2(PX)2=Op(K2κeA2+rμ4+e¯−2rμ2re2).E_A 1κ _j,k\| A^DB_jk-A_jk\|_L_2(P_X)^2=O_p\! ( K^2κ\e_A^2+r_μ^4+ e^-2r_μ^2r_e^2\ ). (117) The conditions in equation 88 imply eA2=Op(n−1/2)e_A^2=O_p(n^-1/2), rμ4≲n−1/2r_μ^4 n^-1/2, and e¯−2rμ2re2≲n−1/2 e^-2r_μ^2r_e^2 n^-1/2. Since K and the regularity constants are fixed, ℰA=Op(n−1/2)E_A=O_p(n^-1/2). Substitution into equation 115 proves the same exploitability rate for θ θ, which minimizes the estimated-payoff loss. For affine aggregators, the rμ4r_μ^4 term vanishes, so the separate condition on rμr_μ is unnecessary. Replacing the payoff and nuisance rate conditions by the corresponding little-o conditions makes ℰA=op(n−1/2)E_A=o_p(n^-1/2). ∎