PaperlayerView exact revision on arXiv

Source-linked AI summary

Context-dependent agent evaluation with orthogonal equilibrium learning

Haorui Ma, Zehua Zang, Jiangmeng Li, Yi Li, Fanjing Xu, Stefan Feuerriegel

arXiv:2609.31897v1cs.AI

TL;DR

Context-dependent evaluation from offline feedback must handle heterogeneous, potentially intransitive preferences and feedback that reveals only subsets of agents. NASHEVAL estimates a debiased contextual payoff matrix and learns the context-to-equilibrium mapping with an orthogonal loss; experiments report lower exploitability on both real-world benchmarks than competing methods.

  • Problem

    Contextual score-based evaluation assumes transitive preferences, while heterogeneous human judgments can produce intransitive collective preferences and offline feedback may cover only subsets of agents.

    Source: §1 · p. 1, §2 · p. 2

  • Method

    NASHEVAL estimates a debiased contextual payoff matrix and uses a tailored orthogonal loss to learn the context-to-equilibrium mapping rather than solving a separate game per context.

    Source: §1 · p. 2, §5 · p. 5, §5.3 · p. 6

  • Results

    NashEval-debiased achieves the lowest mean exploitability on both RouterBench and the RL-agent benchmark, with lower exploitability and higher support F1 than BT-debiased / Borda and global evaluation baselines on both real-world benchmarks.

    Source: §6 · p. 9

  • Takeaways & Limitations

    The experiments demonstrate the benefit of Neyman-orthogonal equilibrium learning and report that NashEval-debiased better reflects underlying collective preferences on the two real-world benchmarks.

    Source: §6 · p. 9

    Identification of the contextual payoff matrix relies on standard assumptions such as positivity and missing at random.

    Source: §4 · p. 4

Abstract

from arXiv · show

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.

1 Introduction

The paper targets context-dependent evaluation from selective relative feedback, where heterogeneous preferences may be intransitive and agents’ capabilities vary by context. NASHEVAL frames evaluation as a contextual game and learns equilibria from logged data.

1 Introduction

  • The goal is to identify, for each context, a set of agents reflecting collective preference from selectively observed relative feedback.Contexts can include prompts, tasks, languages, domains, or user groups.Source: §1 · p. 1
  • NASHEVAL represents evaluation as a regularized two-player zero-sum game; the Nash equilibrium’s support defines the context-specific winners.The framework accommodates relative feedback represented as ordered partitions, including pairwise preferences, partial rankings, and winner-of-subset feedback.Source: §1 · p. 2
  • NASHEVAL constructs a debiased payoff matrix, then uses a tailored orthogonal loss to learn the context-to-equilibrium mapping without solving a separate game for each context.The paper states nuisance-estimation errors affect equilibrium exploitability only through higher-order terms and can yield quasi-oracle convergence under suitable conditions.Source: §1 · p. 2
  • The paper reports theoretical guarantees for equilibrium learning and demonstrates NASHEVAL on simulated and real-world datasets.Its listed guarantees include Neyman orthogonality, average-exploitability bounds, and a quasi-oracle convergence rate.Source: §1 · p. 2

2 Related work2

Prior agent-evaluation approaches either aggregate feedback globally or use contextual score-based models that assume transitivity. The paper positions contextual equilibrium learning under intransitive collective preferences as an unaddressed setting.

2 Related work2

  • Social-choice concepts such as Condorcet and Copeland winners may fail to identify a unique or robust winner; the paper develops a game-theoretic solution for contextual evaluation.The cited discussion frames this work within collective choice under potentially intransitive preferences.Source: §2 · p. 2
  • Score-based approaches such as Bradley–Terry assume transitive preferences, which may be restrictive when heterogeneous voters’ preferences aggregate to intransitive collective preferences.The text notes this issue particularly for subjective, open-ended tasks.Source: §2 · p. 2
  • Existing approaches for contextual agent evaluation with intransitive collective preferences are described as missing.The paper states that transitivity-assuming models can be misspecified and produce biased or conflicting evaluations.Source: §2 · p. 2
  • Game-theoretic evaluation uses a two-player zero-sum game whose equilibrium distribution’s support is interpreted as the set of winners.The equilibrium is called a von Neumann winner in dueling bandits and a maximal lottery in social choice theory; prior work studied global agent evaluation [46] [52].Source: §2 · p. 3
  • For a given context, partial observation makes the contextual payoff matrix depend on nuisance-function estimates, and misspecification can bias that matrix and its equilibrium approximation.The paper identifies robustness to nuisance-function errors as a key learning challenge.Source: §2 · p. 3

3 Preliminaries

The preliminaries motivate lotteries over winners for collective intransitive preferences and define a preference game based on pairwise collective preferences. Its equilibrium distribution supplies a winner set.

3 Preliminaries

  • Table 1 is identified as covering key works on agent evaluation from relative feedback.The supplied caption gives the table’s scope but no specific entries or comparisons.Source: Table 1 · p. 3
  • Aggregating a population’s preferences can yield intransitivity even when each individual’s preferences are transitive, so a deterministic collective winner may not exist.This motivates game-theoretic solution concepts that represent collective preferences as lotteries over winners.Source: §3 · p. 3
  • The preference game uses a skew-symmetric collective preference matrix, with each entry equal to the probability that one agent is preferred over another minus the reverse probability.The matrix serves as the payoff matrix in a symmetric two-player zero-sum game over distributions on agents.Source: §3 · p. 3
  • By symmetry, both players share the same equilibrium strategy, called the von Neumann winner or maximal lottery.The equilibrium’s support is interpreted as the set of winners.Source: §3 · p. 3
  • The equilibrium fits intransitive preferences because it depends only on pairwise comparisons and always exists by the minimax theorem.The text points to Condorcet consistency and related consistency axioms as additional properties discussed in Appendix E.Source: §3 · p. 3

4 Context-dependent agent evaluation from selective feedback

The section defines contextual evaluation from selective relative feedback by constructing a contextual payoff matrix and using it to define a regularized equilibrium whose support is the winner set. Identification relies on assumptions such as positivity and missing at random, while plug-in nuisance estimates can introduce first-order bias.

4 Context-dependent agent evaluation from selective feedback

  • The setting comprises candidate agents, contexts, comparison menus, and relative feedback; feedback can be represented as ordered partitions with ties and preference ordering across blocks.Pairwise preferences, partial rankings, and winner-of-subset feedback are included, with pairwise feedback arising when a menu contains two agents.Source: §4 · pp. 3–4
  • The contextual payoff matrix aggregates menu-specific mean pairwise outcomes using smooth, odd menu aggregators, and represents expected pairwise preferences under a context.The matrix is skew-symmetric; aggregators can be uniformly weighted or customized to weight feedback from menus differently.Source: §4 · p. 4
  • A regularized contextual game uses the payoff matrix and a strongly convex regularizer; the equilibrium’s support is the set of winning agents for that context.The regularizer can incorporate deployment considerations such as agent cost or encourage sparsity.Source: §4 · p. 4
  • The section’s target is the context-to-equilibrium mapping, which is well-defined when the equilibrium is unique.The mapping’s equilibrium support is interpreted as the set of winning agents in that context.Source: §4 · p. 4
  • Identification of the contextual payoff matrix relies on standard assumptions such as positivity and missing at random.The matrix and its equilibrium are identified from the stated contextual mean outcomes and selection propensities.Source: §4 · pp. 4–5
  • The equilibrium is Lipschitz continuous with respect to changes in the contextual payoff matrix, so payoff-estimation errors propagate to the equilibrium.Because some payoff entries are missing and nuisance estimation can introduce first-order bias, the section motivates an orthogonal learner.Source: §4 · p. 5

5 Orthogonal equilibrium learning

NASHEVAL learns contextual equilibria in two stages: it estimates a contextual payoff matrix, then learns a context-to-equilibrium mapping. Its orthogonal construction is designed to limit the effect of nuisance estimation errors on the learned equilibrium.

5.1 Why a na¨ıve plug-in equilibrium learner is problematic

  • A plug-in learner inherits first-order contextual-payoff error, especially when κ is small; orthogonal learning moves nuisance-error effects to higher-order terms.Orthogonality makes the learning objective's gradient locally insensitive to nuisance errors.Source: §5.1 · pp. 5–6

5.2 Stage 1 : Debiased payoff matrix

  • The debiased payoff matrix is locally insensitive to nuisance perturbations, with bias bounded by second-order nuisance errors under a smoothness condition.Compared with the plug-in estimator, the nuisance-error terms are a squared outcome-error term and an outcome–propensity error product.Source: §5.2 · p. 6

5.3 Stage 2 : Orthognal equilibriamy learning

  • Instead of repeatedly solving a game for each context, Stage 2 learns the context-to-equilibrium mapping with a differentiable orthogonal gap loss built from the debiased payoff matrix.The loss is universally Neyman-orthogonal and locally insensitive to nuisance estimation errors.Source: §5.3 · pp. 6–7

5.4 Theoretical guarantees

  • Under the stated assumptions, nuisance estimation errors affect exploitability only through higher-order terms, and the learner achieves the exploitability rate of minimization with an oracle payoff matrix.The comparison is with the plug-in learner, whose nuisance-error contribution is first-order.Source: §5.4 · p. 8

6 Experiments

Across the real-world benchmarks, NashEval-debiased has the lowest mean exploitability and is favored in head-to-head game values; the experiments also examine contextual variation and how pooled evaluation can obscure prompt-specific winners.

6 Experiments

  • On RouterBench and MO-Highway, NashEval-debiased achieves the lowest mean exploitability and is favored in head-to-head game values over all competitors.It also has lower exploitability and higher support F1 than BT-debiased/Borda and global evaluation baselines on both benchmarks.Source: Table 2 · p. 9, Table 3 · p. 9, §6 · p. 9
  • With at least three voters, NASHEVAL outperforms baselines on simulated feedback, and NashEval-debiased is closest to the oracle on exploitability and support F1.At one voter, preferences are transitive and NASHEVAL performs comparably to BT-debiased; NashEval-debiased also outperforms NashEval-plug-in.Source: §6 · pp. 8–9, Figure 3 · p. 9
  • RouterBench heatmaps show estimated evaluations are largely consistent with approximated true evaluations across domains, including stronger reasoning models on Math.The analysis computes each agent’s average winning rate by domain.Source: §6 · p. 9

A Related Work

  • Prior agent-evaluation methods often reduce preferences to scalar scores or global leaderboards, while NashEval learns contextual lotteries for selectively observed feedback.Related work also covers orthogonal learning, contextual routing, dueling bandits, offline games, and equilibrium approximation; the cited approaches differ in preference assumptions, feedback, or debiasing.Source: A Related Work · pp. 15–16

B Additional experiments

  • Additional experiments examine subgroup equilibria in LM Arena, cost–performance trade-offs, alternative MLP backbones, and sensitivity to regularization strength.The LM Arena comparisons are descriptive because the true equilibria are unknown.Source: B Additional experiments · p. 17

B.1 Aggregation hides true contextual winners

  • On MMLUPro and LiveCodeBench, aggregated preferences yield a Condorcet winner, but prompt-level equilibria are heterogeneous and can exclude that winner.Aggregation can therefore hide contextual winners and lead to suboptimal evaluation.Source: Figure 5 · p. 17, §B.1 · p. 17

B.2 Experiment on LM Arena

  • The LM Arena analysis uses 17,480 comparisons among 15 models, covering 17,296 distinct prompts.These are restricted from a release containing 135,634 votes involving 53 models.Source: §B.2 · p. 17

B.2.1 Heterogeneity of the agent capability across contexts

Context-specific equilibria vary substantially across LMArena subgroups, so a global equilibrium can miss which agents win in particular contexts. Across cost trade-offs, backbone ablations, and numerical-solver comparisons, NashEval shows strong empirical performance, while the game-theoretic analysis establishes a unique regularized equilibrium.

B.2.1 Heterogeneity of the agent capability across contexts

  • Subgroup equilibria are highly heterogeneous, and Gemini 2.5 Pro is absent from the support for both code–math subgroups with one attribute present.The reported total-variation summaries cover single- and two-attribute combinations; included subgroups meet the 90% pair-coverage threshold.Source: §B.2.1 · p. 18, Table 4 · p. 20
  • The LM Arena experiment uses only recorded language, code, mathematics, and instruction-following labels, and compares predicted equilibria with empirical maximal lotteries rather than a known true equilibrium.Agreement or disagreement with that reference does not necessarily establish method accuracy.Source: §B.2.1 · p. 18

B.3 Cost-constrained performance.

  • NashEval-debiased largely achieves the empirical Pareto frontier across intermediate costs for both exploitability and average win rate; the exploitability trade-off spans approximately USD 2–11 per 1,000 standardized requests.Source: §B.3 · p. 20, Figure 10 · p. 21, Figure 11 · p. 21

B.4 Ablations on backbone.

  • Across five random seeds, NASHEVAL consistently outperforms other non-oracle baselines for Nv ≥ 3; at Nv = 1, where preferences are transitive, BT-model-based baselines are slightly better.The reported measures are mean and standard deviation of unregularized exploitability and F1 score.Source: §B.4 · p. 22

B.5 Performance over varying regularization strengths.

  • Across tested regularization strengths, NashEval's exploitability and F1 change little for ρ ≤0.01, with performance slightly decreasing beyond that range.The reported F1 score improves slightly as ρ increases from 0.1 to 1.0, which the authors attribute as likely to support sparsity reducing false positives.Source: §B.5 · p. 22, Figure 13 · p. 23

B.6 Comparison with the numerical equilibrium solver

  • NashEval-debiased performs comparably to the numerical solver when the number of voters exceeds one, with stable inference runtime as K increases.The numerical solver's inference runtime increases exponentially with K.Source: §B.6 · p. 22, Figure 14 · p. 23, Figure 15 · p. 24

C Preliminaries of Game Theory

  • The contextual evaluation is a regularized two-player zero-sum game over agent distributions, with a skew-symmetric payoff matrix encoding collective pairwise preferences.The context-independent regularizer induces strong convexity; the equilibrium defines the contextual von Neumann winner.Source: C Preliminaries of Game Theory · p. 24

C.2 The self-play operator

  • The self-play operator characterizes symmetric Nash equilibria through a variational inequality and is strongly monotone under the stated regularization.The strong monotonicity result supports the uniqueness argument.Source: §C.2 · p. 25, §C.1 · p. 25

C.4 Gap functions

The appendix develops the regularized gap as a differentiable measure of equilibrium error, then connects stable equilibrium learning to debiased payoff estimation and orthogonal learning. Its theoretical discussion explains how orthogonality limits the leading effect of nuisance-estimation error, subject to stated conditions.

C.4 Gap functions

  • The regularized gap is nonnegative and vanishes exactly at the equilibrium, and its squared equilibrium error is bounded by the gap.Its inner maximizer is the unique regularized best response, and differentiability supplies a gradient for outer minimization.Source: §C.4 · pp. 26–27

C.5 Equilibrium stability with respect to the payoff

  • The appendix frames equilibrium sensitivity as bounding changes in the contextual equilibrium by perturbations of the payoff matrix.The proof compares the equilibrium variational inequalities at two contexts and uses strong convexity and skew-symmetry.Source: §C.5 · pp. 27–28

C.5.1 Instability of the unregularized equilibrium/maximal lottery

  • Without regularization, a vanishing payoff perturbation can cause a constant change in the selected equilibrium near the tie game whose equilibrium set is the whole simplex.The passage motivates additional regularity or strong convexity for a uniformly stable single-valued target.Source: §C.5.1 · p. 28

D.1 Efficient influence function

  • An EIF-based correction cancels the first-order plug-in bias, leaving only a second-order remainder.The passage contrasts this with direct plug-in estimation, whose bias can have the same first-order magnitude as nuisance-estimation error.Source: §D.1 · p. 29

D.2 One-step estimator and pseudo-outcome

  • The EIF-based pseudo-outcome combines the plug-in payoff and centered correction into a sample-average regression target for contextual payoffs.Regressing cross-fitted pseudo-outcomes on context estimates the contextual payoff surface.Source: §D.2 · p. 30

D.3 Orthogonal statistical learning

  • The learning approach applies orthogonality to the payoff surface and then to a regularized gap risk, making the learning objective locally insensitive to nuisance perturbations.In practice, it cross-fits nuisances, regresses pseudo-outcomes on context, and minimizes empirical gap loss.Source: §D.3 · p. 30
  • Under the stated norm conditions, orthogonality changes the leading nuisance contribution from first order to second order, with rate Op(r^2_µ + r_µr_e).For a linear aggregator, the squared-outcome-error term vanishes; the oracle learning rate is retained when Corollary 1 conditions hold.Source: §D.3 · p. 30

E Benefits of equilibrium-based evaluation: a social-choice perspective

The section illustrates how aggregation can create cyclic collective preferences even when each rater is transitive, and why a mixed equilibrium can represent those preferences more symmetrically than a single winner. It also describes social-choice guarantees and extensions for feedback aggregation, costs, and simulated data.

E.1 How do cycles arise?

  • Aggregating individually transitive rankings can produce majority cycles: a ≻ b, b ≻ c, and c ≻ a.Source: §E.1 · p. 31

E.2 Why can an equilibrium policy better align with human preferences?

  • The uniform equilibrium treats three equally represented alternatives symmetrically, whereas any deterministic choice arbitrarily favors one group.Source: §E.2 · p. 31

E.3 Social choice axioms

  • The stated axioms imply that a universal pairwise winner is selected with probability one, agreement across user groups is preserved, and redundant variants do not distort unrelated agents' probabilities.Source: §E.3 · p. 31

F.1 A summary of different comparative feedback

  • The feedback summary maps comparative modalities to ordered partitions, while noting that a zero verdict can mean different things across modalities.Source: Table 5 · p. 32, §F.1 · p. 32

F.2 Instantiations of the aggregator function

  • Aggregators combine evidence from overlapping menus, and their choices can change the payoff matrix and equilibrium; weights should be set independently of outcomes or modeled as nuisance functions.Every positively weighted menu must satisfy menu-specific coverage and positivity assumptions.Source: §F.2 · p. 32

F.3 Instantiations of the cost function

  • A smooth soft-budget cost raises marginal price as expected spend crosses the budget, while a large penalty can approximate a hard budget in an unconstrained optimization.Setting the surcharge to zero recovers linear pricing; the vanishing-transition-width limit gives a hinge disutility.Source: §F.3 · p. 33

G Simulated agent-evalaution dataset

  • The simulated dataset provides context-dependent agent performance, heterogeneous voter preferences, multiple feedback modalities, and exact contextual payoff matrices for evaluation.Agent performance combines shared quality, group specialization, and criterion-specific contextual variation.Source: G Simulated agent-evalaution dataset · p. 34, §G.1 · p. 34

G.2 Voters and population preferences

  • With one voter the simulated ordering is transitive, while populations of three or five can produce majority cycles; menu selection is MAR conditional on context and has inclusion probabilities bounded below by 0.25.Pairwise, partial-ranking, and winner feedback are generated from sampled voters responding to selected menus.Source: §G.2 · p. 34, §G.3 · p. 35

G.4 Ground truth game and experimental parameters

The simulated experiments define ground-truth contextual games from menu-specific feedback. The real-world data section describes human judgments from LM Arena, where prompts and metadata provide heterogeneous contexts and only one comparison menu is observed per context.

G.4 Ground truth game and experimental parameters

  • The simulated ground-truth game averages menu-specific margins over menus containing each agent pair; for pairwise and ranking feedback, the resulting payoff matrix equals the population margin matrix.Source: §G.4 · p. 35

H Details of the real-world datasets

  • The application experiments include observed LM Arena human judgments, constructed RouterBench preferences, and simulated-judge driving comparisons, with data details provided for interpretation and reproduction.Source: H Details of the real-world datasets · p. 36

H.1 LM Arena dataset

  • LM Arena records votes on pairs of anonymously presented language-model responses, with prompts and metadata as context; only one menu outcome is observed for each context.The described public release contains 135,634 votes from April 17 to July 24, 2025, covering 53 models; the experiments retain 16 models.Source: §H.1 · p. 36

H.2 RouterBench dataset

RouterBench supplies prompt contexts, model scores, and inference costs for evaluating LLM routers. The experiment samples training comparisons and uses a separate prompt set with complete judge-based reference payoff matrices.

H.2 RouterBench dataset

  • RouterBench contributes 8,742 prompts and ten flagship models with complete coverage across ten subsets; contexts include prompt, domain, language group, and other attributes.Source: §H.2 · p. 36
  • Native benchmark scores induce transitive pairwise verdicts; when both models succeed, three judges with distinct emphases provide averaged verdicts from both presentation orders.Source: §H.2 · p. 37
  • The experiment reserves 500 prompts for complete reference payoff matrices and samples 20 of 45 pairs for each of the 8,242 training prompts.The resulting data contain 232,340 comparisons, including 67,500 test comparisons.Source: §H.2 · p. 37

H.3 Reinforcement-learning agent dataset

The driving dataset compares agents with different speed, lane-occupancy, and collision-avoidance trade-offs under contextual driving configurations. The implementation uses observed-menu residual correction, and evaluation includes exploitability and winner-set recovery metrics.

H.3 Reinforcement-learning agent dataset

  • The MO-Highway dataset evaluates agents on contextual driving tasks with separate speed, lane, and collision rewards, using three judges with different utility weights.Its dataset contains 20,480 offline comparisons, and exploratory analysis finds cycles in roughly one third of contextual payoff matrices.Source: §H.3 · pp. 37–39

I Implementation

  • NashEval evaluates residual corrections only on observed menus, retains full pseudo-outcomes for payoff regression, and clips fitted payoff predictions.LightGBM is used for nuisance and payoff models; direct-equilibrium experiments use a numerical solver instead of policy training.Source: I Implementation · p. 40

I.1 Evaluation metrics

  • Average exploitability measures the largest opponent advantage and is lower-is-better, while Support F1 measures recovery of the reference winner set without comparing assigned probabilities.Head-to-head game value reports the average payoff against a specified opponent policy.Source: §I.1 · p. 40

I.2 training details

This section describes cross-fitted payoff estimation and equilibrium training, baseline construction, and the assumptions and theory used to analyze identification and orthogonal learning. It also presents the average-payoff influence function’s stated properties and proofs concerning conditional bias, risk minimization, and universal orthogonality.

I.2 training details

  • Cross-fitting keeps each context within one fold, fits nuisance models on other folds, and pools held-out pseudo-outcomes to train a shared payoff regressor for the debiased payoff surface.The equilibrium predictor is a two-hidden-layer ReLU network with a K-way softmax, trained using empirical orthogonal gap loss; inference labels winners above a 0.001 threshold.Source: §I.2 · pp. 40–41

I.3 Baselines

  • BT-debiased and Borda yield the same policy with complete equally weighted pairs, a common L2 score penalty, and identical index-based tie-breaking; the pluralistic adapter's guarantees concern inferred rankings, not original cyclic preferences.The pluralistic method treats each training prompt as a voter and completes its observed comparisons to infer a ranking.Source: §I.3 · pp. 42–43

J Proofs

  • The proof roadmap covers identification, the efficient influence function and conditional bias bound, Neyman-orthogonality, and empirical exploitability and quasi-oracle rates.Source: J Proofs · p. 44

J.1 Assumptions

  • The analysis assumes pairwise menu coverage, missing at random, positivity, strong convexity, and cross-fitting; its quasi-oracle result additionally relies on nuisance-rate and loss-class complexity conditions.For fixed e > 0, matching nuisance rates rµ, re ≲ n^-1/8 and payoff-regression error eA = Op(n^-1/4) can satisfy Eq. (88) when learners attain those rates in the stated norms.Source: §J.1 · pp. 44–45

J.2 Identification of the contextual payoff matrix

  • Pairwise menu coverage, missing-at-random feedback, and positive inclusion probabilities identify the contextual payoff matrix; a fixed strongly convex regularizer makes its equilibrium unique.The identification argument requires only conditional mean equality and can handle one observed menu per context; it does not require joint independence across menus.Source: §J.2 · p. 45

J.3 Efficient influence function of the average payoff

  • The centered pseudo-outcome is the efficient influence function for average payoff ψ_jk, and its expectation equals ψ_jk before centering.Source: §J.3 · p. 46
  • The influence function φ_jk is the unique canonical gradient for the average payoff.The proof verifies mean zero, square integrability, and representation of every pathwise derivative.Source: §J.3 · p. 47

J.4 Neyman-orthogonality of Γjk

  • Under Assumptions 1–3, Γ_jk is conditionally unbiased and Neyman-orthogonal to nuisance perturbations.At the true nuisance, its conditional expectation equals the target payoff; its derivative along every nuisance direction is zero almost everywhere.Source: §J.4 · p. 47

J.5 Exact conditional bias and second-order remainder

  • The exact conditional bias contains a first-order Taylor remainder and propensity-weighted outcome-regression error.Under the stated remainder conditions, its L2(PX) order is Op(r_μ^2 + r_μr_e); for affine aggregators it vanishes if either nuisance is correct, while correct propensities alone leave a curvature term for nonlinear aggregators.Source: §J.5 · p. 48

J.6 Proof of Proposition 2

  • Under Assumption 7, every minimizer of the risk has policy πθ(X) = π⋆(X) almost surely.This conclusion uses realizability of the target policy and a nonnegative variational gap that is zero exactly at π⋆(X).Source: §J.6 · p. 48

J.7 Proof of Theorem 2

  • Under Assumptions 2–4, the loss is differentiable in θ, and its policy gradient is universally Neyman-orthogonal under the stated conditions.The proof combines the payoff remainder bound with a bound on policy-gradient changes induced by payoff perturbations.Source: §J.7 · pp. 48–49

J.8 Empirical error bound

The proof compares equilibrium gaps under estimated and true payoff matrices, then combines that comparison with payoff-estimation and generalization errors to bound exploitability.

J.8 Empirical error bound

  • The deterministic oracle comparison relies on boundedness, smoothness, and strong convexity, but requires neither realizability nor a specified generalization rate.The inequality does not require a population minimizer.Source: §J.8 · pp. 49, 51
  • Strong concavity of the opponent strategy yields a two-way gap comparison for arbitrary payoff matrices, with squared payoff error controlling the discrepancy.The proof applies the comparison in both directions, including to boundary policies.Source: §J.8 · pp. 50–51
  • Empirical minimization compares the fitted policy with any comparator in the policy class using generalization deviation and payoff error.The proof applies the comparison to the data-dependent fitted policy and then uses empirical optimality.Source: §J.8 · pp. 50–51
  • The payoff-error rate separates second-stage regression error from nuisance-induced bias, and affine aggregators remove the stated r4 µ term.The decomposition also bounds each contextual payoff entry by the regression error plus the remainder rate.Source: §J.8 · pp. 51–52

J.9 Proof of Corollary 1

Under the corollary’s assumptions, the proof controls generalization and payoff-estimation error to obtain an exploitability rate for the learned equilibrium. Affine aggregators relax one separate rate condition.

J.9 Proof of Corollary 1

  • The uniform generalization deviation is Op(n^-1/2) under the stated i.i.d. sampling and complexity bound.This rate also bounds the oracle deviation under the proof’s conditions.Source: §J.9 · p. 52
  • The oracle policy has Op(n^-1/2) exploitability, while the estimated-payoff learner is bounded by 4εgen + 3EA.The comparison applies when the fitted payoff belongs to the specified function class, an event whose probability tends to one.Source: §J.9 · p. 52
  • Under realizability, fixed K, and fixed regularity constants, e ≲ n^-1/2 yields EA = Op(n^-1/2) and the learned policy has the same exploitability rate.For affine aggregators, the r4 µ term vanishes, so the separate condition on rµ is unnecessary.Source: §J.9 · p. 52

Related papers

Loading 2609.31897v1…