{"ID":23475160,"CreatedAt":"2026-09-18T01:09:05.407443952Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.19963","arxiv_id":"2609.19963","title":"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(θ)\\Xset(θ)$, where $\\Xset$ 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.","short_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...","url_abs":"https://arxiv.org/abs/2609.19963","url_pdf":"https://arxiv.org/pdf/2609.19963v1","authors":"[\"Lishang Xu\",\"Guodong Ma\",\"Pengcheng Weng\",\"Zixuan Xia\"]","published":"2026-09-17T09:35:34Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[\"LoRA\"]","has_code":false}