Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits
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(θ)𝒳(θ), where 𝒳 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.
Related
- Proof of Stake economy under centralized exchanges--a mean field model
- Relaxed Centralized Circumcentered-Reflection Methods for Convex Feasibility: Convergence and Finite Termination
- Centralized Fault-Location and PMU Placement Strategies in Weakly Observable Grids: A Comprehensive Review
- Centralized Multi-Objective UAV–UGV Task Allocation for Disaster Relief Material Distribution with Mobile UAV Bases
- Distributed Formation Model Predictive Control Under Communication Denial: An Edge-Splitting ADMM with Centralized-Equivalence Gating and Confidence-Decayed Coupling
BibTeX
@misc{xu2026exact,
title = {{Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits}},
author = {Lishang Xu and Guodong Ma and Pengcheng Weng and Zixuan Xia},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.19963},
eprint = {2609.19963},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.19963},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits
AU - Lishang Xu
AU - Guodong Ma
AU - Pengcheng Weng
AU - Zixuan Xia
PY - 2026
DA - 2026/10/03
PB - arXiv
DO - 10.48550/arxiv.2609.19963
UR - https://arxiv.org/abs/2609.19963
AB - 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(θ)𝒳(θ), where 𝒳 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.
ER -