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(\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.

arXiv commentv3: exposition clarified; a sentence in Section 5.3 that was inaccurate for K > N removed, and the K = N condition stated in the introduction; comparison with Cuvelier et al. made precise; two statements in Appendix B corrected; computational cost stated; experiments rerun with 50 seeds (was 10), KL-UCB baseline added to Figure 2; references updated. Main results unchanged