CS Paper Radar

Rank Without an Oracle: Deviation-Aware Interaction-Rank Selection from Offline Multi-Agent Logs

Xiangwu Wang, Chengwei Cao, Hongyuan Tang

cs.MA cs.GT ·submitted 2026-09-08 07:27 UTC · v1

Abstract

Offline multi-agent payoff models are estimated under a logging distribution but used on distributions induced by learned solutions and unilateral deviations. Standard held-out loss can therefore favor an interaction class that predicts logged play well while distorting strategic incentives. We introduce Selective Interaction-Rank Validation (SIRV) for finite games with known logging distributions. A training split fits nested payoff models and constructs a common union of all candidate deployment and unilateral-replacement distributions; an independent calibration split evaluates every candidate on this same union. SIRV returns the smallest rank whose simultaneous upper worst-target risk is within tolerance of the best upper score, and abstains when a declared target is unsupported or too imprecisely estimated. A common coverage event yields a finite-candidate target-risk bound and a candidate-specific coarse correlated equilibrium (CCE) gap certificate. We also isolate an exact two-point off-support non-identifiability result. In a controlled factorial study with 2,048 independent games per family, empirical-Bernstein bounds reduce the median CCE-gap certificate by 42.5% relative to Hoeffding bounds on common returns, with a 1.36-point reduction in supported return. Under paired rank misspecification and in a separately generated congestion family, the SIRV-EB fallback rule lowers mean true candidate-selection CCE regret relative to ID-Mean, while retaining game-level losses. Across 384 games at $N=3,5,8$, ID-Mean-relative mean CCE-regret effects stay positive while certified return falls sharply under weak coverage. These results separate certifiable model selection from universal strategic improvement.

Comment
18 pages, 9 figures, including appendices

Closest papers

Nearest neighbours by meaning across the whole index.

All against the machine: the Solo score for rating skill in variable environments

cs.LG physics.soc-ph ·2026-10-03 ·David Reguera, Xavier R. Hoffmann, Irene Pérez, Pol Colomer-de-Simón, Miquel Masoliver +3 more
benchmark similarity 0.61
Abstract

We propose a distribution-free metric to rate individual skill in ``player-versus-environment'' settings, where participants face heterogeneous tasks without direct opponents. Such settings are common in digital platforms, games, education, finance, and the benchmark evaluation of AI agents. They combine high randomness, tasks of widely varying difficulty, and unknown heterogeneity across individuals. Our metric maps each task outcome to a bounded performance score with zero population mean and variance bounded by $1/3$, regardless of the outcome distribution, so that scores are directly comparable across tasks. Aggregating these scores over tasks yields an interpretable skill score for each individual (the ``Solo'' rating), and a reshuffling null model tests whether that score exceeds what chance alone would produce. We validate the approach on the progression of $2\times10^5$ players in the mobile games Candy Crush Saga and Bubble Witch 3 Saga. The metric identifies high- and low-skill players with high statistical confidence, their classification persists over hundreds of subsequent levels, and a windowed version of the score tracks changes in performance along progression.

0.21

High-Dimensional Off-Policy Evaluation without Sample Splitting using an Onsager Correction

cs.LG stat.MLmath.ST ·2026-11-05 ·Saksham Jain, Guillaume Braun, Masaaki Imaizumi
theory similarity 0.60
Abstract

Reward models used for off-policy evaluation (OPE) are commonly selected using held-out data. When sample size and context dimension grow proportionally, the difference in test risk between models fitted on the full sample and on a fixed fraction of it need not vanish. Held-out evaluation can therefore consistently estimate the test risk of the model trained on the smaller sample, but because the relative ranking of candidate reward models can change after full-data refitting, held-out selection can be suboptimal. We develop an Onsager-corrected, target-policy-weighted criterion that estimates the full-data reward model's out-of-sample risk under the target policy using only its training observations. This enables early stopping along the full-data gradient-descent trajectory without sample splitting. For neural networks with fixed depth and hidden width under Gaussian contexts, single-index rewards, context-dependent multi-index target policies, and known context-independent logging, we prove uniform consistency of our criterion over a fixed finite set of gradient-descent iterates and a near-oracle guarantee for the selected reward model. The same correction yields a doubly robust estimator that consistently estimates the true policy value without sample splitting, even when reward-model prediction error does not vanish. Experiments show decreasing risk-estimation error as dimension grows at a fixed sample-to-dimension ratio, and improved reward-model selection relative to held-out baselines. Empirically, our correction also reduces the root mean squared error of doubly robust value estimates computed from the same data used to fit and select the reward models.

0.25

Context-dependent agent evaluation with orthogonal equilibrium learning

cs.AI ·2026-09-25 ·Haorui Ma, Zehua Zang, Jiangmeng Li, Yi Li, Fanjing Xu +1 more
similarity 0.60
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.

0.09

Beyond IPS: Reliable Counterfactual Evaluation in Multi-Stage Ad Systems without Logged Propensities

cs.IR ·2026-10-29 ·Mohsen Malmir, Mohamed A. Radwan, Houssam Nassif, Murat Ali Bayir
similarity 0.60
Abstract

Offline evaluation of ad-ranking policies in multi-stage delivery systems is challenging because action propensities are often unavailable, limiting inverse propensity scoring (IPS). Reward-model-based estimators such as the Direct Method (DM) avoid propensities but can be biased when candidate policies induce impression distributions that differ from the logged data. We formalize DM-based counterfactual replay and propose mixture-weighted reward modeling, which reweights logged data toward a mixture of candidate-policy distributions using density ratios from a multiclass domain classifier. We bound each candidate's value-estimation error by overlap, cold-start, and replay terms, and derive an asymptotic rule that uses the cold-start mass to decide whether to trust offline selection or route candidates to online A/B testing. On an ads-delivery simulator and on production traffic from a large-scale CTR ranking system, the mixture-weighted reward model improves policy selection over its unweighted counterpart in both settings, with the largest gains at low overlap in simulation. Combined with a doubly robust correction, it attains the highest Top-1 accuracy in production and at low and medium overlap in simulation.

0.31

Adaptive Doubly Robust Off-Policy Evaluation for Ranking Policies under Diverse User Behavior

cs.LG cs.IR ·2026-08-30 ·Kosuke Iguchi, Ren Kishimoto
published similarity 0.59
Abstract · 14 pages, 4 figures, 7 tables. Accepted at CONSEQUENCES 2026 and selected for oral presentation

Off-policy evaluation (OPE) of ranking policies is challenging be- cause selecting and ordering multiple items from a candidate set makes the number of possible rankings grow combinatorially with the number of candidates and the ranking length. Consequently, Inverse Propensity Scoring (IPS), whose importance weight is the full-ranking probability ratio under the evaluation and logging policies, can have excessive variance. Independent IPS (IIPS) and Reward Interaction IPS (RIPS) reduce variance by imposing fixed assumptions on how users browse rankings, but may introduce bias when those assumptions mismatch actual behavior. Adaptive Inverse Propensity Scoring (AIPS) addresses this trade-off by adap- tively marginalizing importance weights over the actions that affect each position-wise reward. It attains minimum variance within a class of unbiased IPS-based estimators when the true user be- havior model is observed. However, its estimation accuracy may still degrade for longer rankings, and AIPS does not use a reward model for residual correction. We propose Adaptive Doubly Robust (ADR), which combines adaptive importance weighting with re- ward regression through a control-variate correction. We establish its unbiasedness when the true user behavior model is observed and characterize a sufficient condition under which it reduces vari- ance relative to AIPS. Across synthetic experiments with 10,000 simulations per condition, ADR improves mean squared error over AIPS and conventional ranking OPE estimators across a range of logged-data sizes and ranking lengths.

0.46

When Can You Trust Offline Evaluation of Equal-Cost Top-k Allocation? A Controlled, Reproducible Benchmark and Practitioner's Guide

cs.LG stat.MEstat.ML ·2026-08-12 ·Binshuang Li
benchmark similarity 0.59
Abstract

Organizations decide whom to treat under a budget and want to know what a targeting rule would have earned before deploying it. Off-policy evaluation promises this from logged data, but the deployable rule is a deterministic top-k policy: it removes all averaging over actions, so weak overlap hits the estimate directly. We benchmark six estimators across five datasets and two known-effect sweeps, and validate the mechanisms against a non-simulated paired reference. First, weak overlap is governed by logger-target action alignment, not by logging sharpness alone: what governs support is the logger's probability of the target's actions. Sharpening a logger built from the target's own score barely moves overlap over the tested range; action-level disagreement collapses it. Effective sample size ranks this risk across logging environments, but is weak at ranking candidates within the single log a practitioner holds, and its cut point does not transfer. Second, the optimizer's curse is not fixed by cross-fitting the outcome nuisance. When the rule is fit on the data used to evaluate it, cross-fitting the nuisance alone leaves the reuse bias in place and makes it worse. Honest policy-level splitting avoids the reuse by targeting the learning procedure's value -- a change of estimand, not a de-biasing of the full-sample policy. Third, propensity-estimation error is the largest degradation we measure: an out-of-fold estimate hurts IPS more than any other stress we apply, leaves doubly-robust estimation almost unchanged, and can invert the overlap diagnostic itself. Logging is synthesized and propensities floored at 0.02, so every failure occurs with bounded weights; the floor also reduces the two tuned hybrids to their untuned parents, leaving four practically distinct estimators, and all exact-value surfaces are synthetic or semi-synthetic. We release the benchmark; public data only.

0.04

World Models Need Not Be Right to Rank Policies Right: Relative Bounds and Audit Limits

cs.LG cs.AI ·2026-10-31 ·Ahanaf Hasan Ariq, Hasaan Ahmad
published similarity 0.59
Abstract · 10 pages, 2 figures, 2 tables. Accepted as a poster at the NeurIPS 2026 Workshop on World Models in Physical AI

Selecting a reinforcement-learning (RL) policy usually requires additional environment interaction, while learned world models offer cheap but potentially biased evaluations. This raises two distinct questions: can shared model errors preserve pairwise rankings despite poor absolute values, and do they make a small number of real audits more informative? We derive an exact pairwise simulation identity and a relative bound separating common-mode Bellman residuals from policy-specific error. The analysis motivates RAVEL (Relative Auditing of Value Errors in Learned models), a selective policy tournament whose eliminations use held-out real outcomes. We test 45 SAC, TD3, and PPO policies per task in DMC cheetah-run and walker-walk. At rollout horizon 500, model rankings remain strong (Kendall tau = 0.962 and 0.800), and same-run differential-error ratios are 0.674 and 0.106. Yet mean paired audit-error correlations are only 0.007 and 0.090, and pairing changes standard deviation by -2.5 percent and +1.9 percent. Simultaneous intervals attain 99.98 percent and 99.75 percent coverage, but certify only 13.2 percent and 0 percent of decisions at eight audits. RAVEL improves low-budget walker-walk regret, whereas real-only successive halving is better at the largest budget, rejecting the precommitted twofold efficiency target. Frozen-model optimization lowers real return without increasing predicted return on average. Thus ranking fidelity, useful audit covariance, and upward model exploitation are distinct properties, separated in part by closed-loop trajectory divergence.

0.38

Rank Confidence Sequences:Anytime-valid Leaderboards

cs.AI stat.ME ·2026-09-26 ·Hamed Khosravi, Xiaoming Huo
benchmark similarity 0.57
Abstract

Leaderboards rank models by their average scores on benchmark items, and they are consulted repeatedly while the evaluation is still running. Existing confidence intervals for a model's rank control their error rate only if they are computed once, after a number of items chosen in advance. If they are recomputed as results arrive, and the evaluation stops once they look decisive, their error rate exceeds its nominal level. Anytime-valid methods keep their guarantees at all sample sizes simultaneously and hence under any stopping rule. They exist for the accuracy of one model, for one pair of models and for the set of models that may be best. For pairwise battles they also give ranks. None gives ranks when all models are scored on the same items, which makes their scores dependent. We construct rank confidence sequences: for every model, a set of ranks that contains its true rank, simultaneously for all models and at all times, at a chosen error level $α$, in finite samples. The construction combines betting e-processes, one for each ordered pair of models, with closed testing over the possible orderings of the models. It allows any dependence between the models' scores on an item. The method has two advantages. A leaderboard can be inspected after every item without inflating its error rate. The evaluation of each model can stop as soon as the question asked about it is answered, which saves compute. When results are examined only once, halfway through or later, little power is lost relative to fixed-sample methods. The paper quantifies these advantages in simulations and on public leaderboard data.

0.57