Context-dependent agent evaluation with orthogonal equilibrium learning

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

cs.AISep 25, 2026

Context-dependent agent evaluation with orthogonal equilibrium learning

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

Organizations: Munich Center for Machine Learning, Germany · 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 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.

Figures & tables

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.

\Rightarrow

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.

Panel of Table 1 — Table 1: Key works on agent evaluation from relative feedback.

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.

Figure 3: RQ1 Equilibrium quality using a simulated dataset with ground-truth. Shown: mean exploitability and

F_{1}

score on simulated dataset for

\#

voters

=1,3,5

over 5 random seeds.

Table 5

Figure 4: Insights. Winner frequency for each agent in the RouterBench dataset. Left: estimated evaluation from NashEval-debiased . Right: (approximated) true evaluation.

Appendix figures & tables21 assets

Supplementary material from the paper’s appendix.

Appendix

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 .

Panel of Figure 7 — 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.

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

Appendix

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.

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 $\rho=0.01$ and report percentages. Note: this is different from the heatmap Figure 4 , which reports the winner frequencies of the agents.

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

2

–

11

per

1{,}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]

. Therefore, under the same cost budge, our method produces contextual evaluations that better reflect the collective preference of the population.

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

N_{v}\geq 3

and achieves comparable performance with BT -based baselines on

N_{v}=1

. This result demonstrate the effectiveness of the learning framework itself.

Figure 13: Mean

\pm

std Mean exploitability and

F_{1}

score on simulated dataset for

\#

voters

=3

over 5 random seeds, plotted against varying regularization strengths

\rho

Figure 14: Performance comparison of our NashEval with the numerical solver. Mean

\pm

std Mean exploitability and

F_{1}

score on simulated dataset for

\#

voters

=1,3,5

over 5 random seeds.

Figure 15: Inference runtime comparison between our NashEval-debiased and the numerical equilibrium solver. Our NashEval is much more efficient during inference time.

Modality	Raw response	Ordered partition $Y_{m}$	Zero verdicts
Pairwise duel	$1\succ 3$	$(\{1\},\{3\})$	a declared tie
Full ranking	$1\succ 2\succ 3\succ 4\succ 5$	$(\{1\},\{2\},\{3\},\{4\},\{5\})$	none arise
Weak ranking	$\{1,2\}\succ\{3\}\succ\{4,5\}$	$(\{1,2\},\{3\},\{4,5\})$	revealed indifference
Top- $r$ ( $r=2$ )	$T=\{1,2\}$	$(\{1,2\},\{3,4,5\})$	censoring: the order inside $T$ and inside its complement is never asked
Best–worst	best $1$ , worst $5$	$(\{1\},\{2,3,4\},\{5\})$	censoring within the middle block
Cardinal scores	$s=(5,5,3,1,1)$	$(\{1,2\},\{3\},\{4,5\})$	equal scores

Appendix

Table 5: Turning comparative feedback modalities into ordered partitions, illustrated on the menu

m=\{1,\dots,5\}

. Note the zero-verdict may have different interpretations for different modalities.

Parameter	Value	Meaning
$K,d,p$	$5,5,12$	Agents, context dimensions, and performance criteria.
$X$	$\operatorname{Unif}([0,1]^{5})$	Independent training and test contexts.
$D,\ell_{f}$	$128,0.5$	Fourier features and field length scale.
$n_{\mathrm{cal}}$	$4{,}096$	Uniform contexts for field standardization.
$(a_{s},a_{c},a_{h})$	$(1,2,0.15)$	Shared quality, specialization, and criterion variation amplitudes.
$(o_{0},o_{1},o_{2})$	$(0,2,4)$	Offsets of the three specialization profiles.

Appendix

Table 6: Parameters of the simulated dataset.

Table 21

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
Anthropic	claude-sonnet-4-20250514	3.00	15.00
Google	gemini-2.5-pro	1.25	10.00

Appendix

Table 9: Selected agents from the Arena Human Preference 140K dataset, with list prices in USD per

10^{6}

tokens.

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%

Appendix

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.

Provider	Agent	Input	Output
OpenAI	gpt-5 (medium)	1.25	10.00
OpenAI	gpt-5-chat $\dagger$	1.25	10.00
Anthropic	claude-sonnet-4	3.00	15.00
Google	gemini-2.5-pro	1.25	10.00
Google	gemini-2.5-flash	0.30	2.50
Alibaba	qwen3-235b-a22b-thinking-2507	0.23	2.30

Appendix

Table 11: Selected agents from the RouterBench dataset, with list prices in USD per

10^{6}

tokens.

\dagger

gpt-5-chat is no longer served; its price is taken from the benchmark’s own records.

Hyperparameter	Symbol	Search space
Learning rate	$\mathrm{lr}_{\nu}$	$\{0.01,0.1\}$
Maximum leaves per tree	$n_{\mathrm{leaf},\nu}$	$\{7,15,31\}$
Maximum tree depth	$d_{\max,\nu}$	{7, 10}
Minimum observations per leaf	$n_{\min,\nu}$	$\{30,50,100,200\}$
$L_{2}$ penalty on leaf values	$\lambda_{2,\nu}$	$\{0,0.1,1\}$
Feature fraction per tree	$f_{\nu}$	$\{0.6,0.8,1.0\}$

Appendix

Table 12: Hyperparameter search space for the nuisance estimators. The index

\nu\in\{\mu,e\}

denotes the outcome or propensity model.

Hyperparameter	Symbol	Search space
Learning rate	$\mathrm{lr}_{A}$	$\{0.02,0.05,0.1\}$
Maximum leaves per tree	$n_{\mathrm{leaf},A}$	$\{15,31,62\}$
Maximum tree depth	$d_{\max,A}$	{10, 15}
Minimum observations per leaf	$n_{\min,A}$	$\{50,100,200\}$
$L_{2}$ penalty on leaf values	$\lambda_{2,A}$	$\{0,0.1,1\}$
Feature fraction per tree	$f_{A}$	$\{0.6,0.8,1.0\}$

Appendix

Table 13: Hyperparameter search space for the shared payoff regressor.

Hyperparameter	Search space or fixed setting
Hidden-layer widths	$\{(64,64),(128,128),(256,256)\}$
Learning rate	$\{10^{-4},3\times 10^{-4},10^{-3}\}$
Weight decay	$\{0,10^{-5},10^{-4}\}$
Batch size	$\{128,256\}$
Maximum training epochs	$500$
Early-stopping patience	$30$ epochs

Appendix

Table 14: Hyperparameter search space for the equilibrium predictor. We fix two hidden layers and vary their common width.

Agent Evaluation

Agent evaluation measures how reliably AI systems act, use tools, and complete tasks across interactive environments.

See all 144 papers

May 8, 2026

Nash without Numbers: A Social Choice Approach to Mixed Equilibria in Context-Ordinal Games

Nash equilibrium serves as a fundamental mathematical tool in economics and game theory. However, it classically assumes knowledge of player utilities, whereas economics generally regards preferences as more fundamental. To leverage equilibrium analysis in strategic scenarios, one must first elicit numerical utilities consistent with player preferences, a delicate and time-consuming process. In this work, we forgo precise utilities and generalize the Nash equilibrium to a setting where we only assume a player is capable of providing an ordinal ranking of their actions within the context of other players' joint actions. The key technical challenge is to rethink the definition of a best-response. While the classical definition identifies actions maximizing expected payoff, we naturally look towards social choice theory for how to aggregate preferences to identify the most preferred actions. We define this generalized notion of a context-ordinal Nash equilibrium, establish its existence under mild conditions on aggregation methods, introduce notions of regularization, approximation, and regret, explore complexity for simple settings, and develop learning rules for computing such equilibria. In doing so, we provide a generalization of Nash equilibrium and demonstrate its direct applicability to elicited preferences in human experiments.

Ian Gemp, Crystal Qian, Marc Lanctot +1

Google DeepMind · New York, NY, USA · New York, NY USA +2

Nash Equilibrium Social Choice Theory Game Theory Preference Elicitation

Ask PDF

Mar 9, 2026

Learning When to Trust in Contextual Social Bandits

Robust reinforcement learning typically assumes that feedback sources are either globally trustworthy or corrupted within a fixed global budget. We identify a more subtle failure mode that escapes this dichotomy, which we call Contextual Sycophancy. In this failure, evaluators are truthful in benign contexts but systematically biased in critical ones, so that no single evaluator is reliable everywhere and the corrupt evaluators may form a majority in the contexts that matter. Our first result is an information-theoretic lower bound. We exhibit two problem instances that induce identical social-feedback distributions yet have disjoint optimal actions, proving that any algorithm relying on social feedback alone (including any robust aggregator, regardless of breakdown point) incurs

Ω(T)

latent regret. This shows that breaking contextual sycophancy is impossible without having some information. We then show that a sparse stream of ground-truth audits, available with probability

p_{\mathrm{aud}}

, is sufficient. We propose \ESA, which learns a per-evaluator contextual trust boundary from audits and re-weights feedback accordingly, and we prove a high-probability latent-regret bound of

\tilde{\mathcal{O}}\!\big(\sqrt{T\,d_{VC}/p_{\mathrm{aud}}} + d\sqrt{T} + ε_{\mathrm{tol}}T\big)

, where

d_{VC}

is the complexity of the adversary's bias strategy. The audit-dependence

1/\sqrt{p_{\mathrm{aud}}}

matches the information-theoretic necessity of audits. Empirically, \ESA\ recovers the ground truth when

80\%

of the social layer is adversarial, a regime in which median- and mean-based robust baselines fail.

Majid Ghasemi, Mark Crowley

Department of Electrical & Computer Engineering University of Waterloo, Canada

LLM Sycophancy Corruption Robustness Contextual Bandits

Ask PDF

Aug 17, 2026

Policy Optimization and Statistical Inference for Online Contextual Matrix Games

Online decision making often requires navigating a landscape shaped by both dynamic contexts and strategic interactions. In competitive pricing, for example, hotels must account for both dynamic contextual factors and rivals' strategic responses. Existing approaches address only part of this challenge: contextual bandits optimize single-agent decisions using observable features but ignore multi-player interactions, while online matrix games capture strategic behavior through Nash equilibrium but assume fixed payoffs, ignoring contextual information. How should agents act then when strategic payoffs evolve with contextual signals? We introduce online contextual matrix games to integrate contextual information into multi-player online games. We further propose OnGameLearn, an online learning algorithm that efficiently balances exploration and exploitation across both player actions and contexts. This approach comes with statistical guarantees: tail bounds for the estimated payoff matrix, the convergence of the estimated Nash equilibrium, the asymptotic normality of the parameter estimators, and the sublinear regret bound. We also develop the notion of policy value in matrix games and develop a doubly robust,

\sqrt{T}

-consistent estimator for it. Across simulated studies and a real-world hotel pricing application, we find that OnGameLearn effectively navigates the intertwined challenges of strategic and contextual decision-making.

Liner Xiang, Yixin Wang, Hengrui Cai

Department of Statistics, University of California, Irvine · Department of Statistics, University of Michigan

Nash Equilibrium Computation

Ask PDF

Abstract

Agent Evaluation

Explore similar work

Nash without Numbers: A Social Choice Approach to Mixed Equilibria in Context-Ordinal Games

Learning When to Trust in Contextual Social Bandits

Policy Optimization and Statistical Inference for Online Contextual Matrix Games