aiqbench analysis
This research advances the theoretical limits of exploration in centralized serial-dictatorship matching bandits by characterizing how learning one player-arm pair imposes regret on others. The authors demonstrate that specific constraints reduce to pairwise exploration quotas and construct policies that attain every Pareto-minimal point without assuming optimizer uniqueness. These findings provide a rigorous framework for managing externalities in multi-agent reinforcement learning systems where complete matchings are required.
Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits
arXiv:2609.19963v2 Announce Type: cross Abstract: Exploration in centralized serial-dictatorship matching bandits must use complete matchings, so learning one player-arm pair can impose regret on others. We study this externality under a known common priority order and Gaussian rewards with unit variance. We show that the matching-level Graves-Lai constraints reduce to finitely many pairwise exploration quotas and, at top-choice-separated instances, yield a polynomial-size marginal linear program. At these instances, the exact attainable set of expected logarithmic regret coefficients is $G(\theta)\mathcal{X}(\theta)$, where $\mathcal{X}$ is the feasible matching-allocation set and $G$ maps allocations to player regret. The usual upper-closed Graves-Lai region can be strictly larger despite having the same Pareto-minimal boundary. We further show that identical exploration quotas can induce very different regret through their scheduling. Finally, we construct estimate-solve-track policies, uniformly good on the full row-strict class, that attain every fixed positively weighted optimum without assuming optimizer uniqueness. Every Pareto-minimal point is pointwise attainable, possibly through an instance-calibrated target.
Abstract:Exploration in centralized serial-dictatorship matching bandits must use complete matchings, so learning one player-arm pair can impose regret on others. We study this externality under a known common priority order and Gaussian rewards with unit variance. We show that the matching-level Graves-Lai constraints reduce to finitely many pairwise exploration quotas and, at top-choice-separated instances, yield a polynomial-size marginal linear program. At these instances, the exact attainable set of expected logarithmic regret coefficients is $G(\theta)\mathcal{X}(\theta)$, where $\mathcal{X}$ is the feasible matching-allocation set and $G$ maps allocations to player regret. The usual upper-closed Graves-Lai region can be strictly larger despite having the same Pareto-minimal boundary. We further show that identical exploration quotas can induce very different regret through their scheduling. Finally, we construct estimate-solve-track policies, uniformly good on the full row-strict class, that attain every fixed positively weighted optimum without assuming optimizer uniqueness. Every Pareto-minimal point is pointwise attainable, possibly through an instance-calibrated target.
v2: expanded and corrected proofs in the appendices (new Remark D.8), added and corrected references, updated AI use statement, typos and wording fixed; main results unchanged
Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG); Machine Learning (stat.ML)
arXiv:2609.19963 [cs.GT]
(or arXiv:2609.19963v2 [cs.GT] for this version)
Full text under the publisher's open licence · 198 words
Related coverage
Why I Left Google DeepMind
LessWrong · Jul 15, 2026
Expenditure Horizon: Measuring Optimization Ability, with an Application to NanoGPT
METR · Jul 21, 2026
Conditional Total Correlation and the Serial Depth of Adaptive Parallel Sampling
arXiv · Aug 27, 2026
Building Blocks for Foundation Model Training and Inference on AWS
Hugging Face · May 11, 2026