Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits

Lishang Xu; Guodong Ma; Pengcheng Weng; Zixuan Xia

cs.GTSep 17, 2026

Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits

Authors: Lishang Xu, Guodong Ma, Pengcheng Weng, Zixuan Xia

Organizations: University of Bern · EPFL

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(θ)\mathcal{X}(θ)$ , 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.

Figures & tables

Panel of Figure 1 — Figure 1: The same exploration quotas, scheduled differently, make different players pay. Left: $m_{\mathrm{B}}$ serves the large quotas of $p_{1}$ and $p_{2}$ at once and leaves $p_{3}$ on its worst arm ( $r_{3}=202$ ). Right: $m_{\mathrm{A}}$ , then $m_{\mathrm{C}}$ (dashed), spare $p_{3}$ ( $r_{3}=2.02$ ) but make $p_{2}$ pay for both large quotas ( $r_{2}=222$ ). $r_{i}$ is $p_{i}$ ’s expected logarithmic regret coefficient (Example 4.8 ); the stable matching is $p_{i}\mapsto a_{i}$ ; a small quota is not drawn.

Figure 2: Scheduling trade-off at

T=10^{7}

: final

(\widetilde{R}_{2}/b(T),\,\widetilde{R}_{3}/b(T))

for

\pi_{s}

s\in\{0,0.25,0.5,0.75,1\}

20

seeds each (filled), against the segment

r_{3}=221.8-0.99\,r_{2}

of the asymptotic Graves–Lai (GL) boundary; open markers, shaped as the corresponding split, are oracle

s

-split medians over

20

seeds and sit on it. The plug-in splits are ordered along the segment but displaced outward by the finite-horizon transient. The cross is layered KL-UCB (mean over

50

seeds).

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Result	Instances	Additional hypotheses	Type
Thm C.1 ( $2\times 2$ constants)	$\theta_{\Delta,\gamma}$	uniform goodness on the one-row class $\mathcal{C}$	necessary + attained
Thm 4.1 (information allocation)	$\Theta_{\mathrm{strict}}$	uniform goodness on $\Theta_{\mathrm{strict}}$	necessary
Prop 4.5 , Thm 4.6 (regret region, $C_{w}$ )	$\Theta_{\mathrm{sep}}$	uniform goodness on $\Theta_{\mathrm{strict}}$	necessary
Thm 4.2 (exact quota reduction)	$\Theta_{\mathrm{strict}}$	none	structural
Thm 4.3 , Prop 4.4 (compact LP, schedules)	$\Theta_{\mathrm{sep}}$	$w>0$	structural
Prop 4.9 ( $3\times 3$ frontier)	$\mu^{(3)}$	none	necessary (explicit)

Appendix

Table 1: Scope of the main results. The four standing modeling conventions (Gaussian rewards with known common variance normalized to one, known common priority order, complete matching, centralized semi-bandit feedback) apply throughout and are not repeated.

Line of work	Object	Difference from this paper
Matching-bandit order-level work	Stable regret up to order or constant factors	Does not characterize the full player-level coefficient set or who pays under alternative complete-matching schedules.
Binary stable-regret work	A scalar count of unstable rounds	Studies a scalar binary criterion and may allow two-sided uncertainty; our target is the vector of utility regrets under one-sided Gaussian learning.
Group-fair exploration	Attainable incremental-utility profiles and a bargaining point	Uses grouped arrivals and Nash bargaining; our matching constraints yield an explicit polyhedral coefficient set and recoverable schedules.
Pareto regret work	Trade-offs across benchmark experts or arms, or across gap regimes	The trade-off is across players at a fixed instance, with exact quotas and attainable schedules.

Appendix

Table 2: Comparison by object and conclusion. The present paper studies player-level utility-regret coefficients at a fixed top-choice-separated instance.

variant	E	C	F	cand.	$w^{\top}\!\widetilde{R}/b$ med [IQR]		expl.	wrong	est.	lock-wr.
oracle	✓	–	–	–	$244.4$	$[244.4,244.4]$	$3{,}872$	$0$	$0$	–
plug-in	✓	–	✓	dyn	$299.0$	$[230.5,382.3]$	$6{,}122$	$970$	$0$	–
certified	✓	✓	✓	dyn	$752.2$	$[650.3,872.4]$	$4{,}073$	$0$	$27{,}589$	–
frozen cand.	✓	✓	✓	frz	$28{,}117$	$[874,273{,}425]$	$4{,}473$	$0$	$\approx 10^{7}$	$62\%$
no floor	✓	–	–	dyn	$311.3$	$[242.7,382.8]$	$8{,}772$	$333$	$0$	–
exploit-only	stops	–	✓	lock	$72.1$	$[1.8,57{,}386]$	$4$	$1{,}366$	$0$	$44\%$

Appendix

Table 3: Mechanism ablation at

T=10^{7}

50

seeds,

w=(1,1,1)

C_{w}=244

: persistent quota exploration (E), certification (C), noise floor (F), candidate (dyn/frozen/lock-in); median [IQR] of

w^{\top}\widetilde{R}(T)/b(T)

; median exploration, wrong-exploitation and estimation rounds; fraction of seeds with an incorrect fixed matching (defined below). Count medians are rounded to the nearest integer, with halves rounded up.

Figure 3:

\widetilde{R}_{i}(T)/b(T)

against

T

(median and interquartile band over

50

seeds) for the oracle tracker (left) and the plug-in tracker (right), with the canonical targets

r^{\circ}=(22,20,202)

dotted. The oracle closely tracks all three constants. The plug-in medians for

p_{2},p_{3}

lie between the two frontier endpoints with wide interquartile bands: at finite horizons the empirical optimizers select different endpoints across seeds (Remark F.3 ), because at

w=(1,1,1)

the two vertices differ in weighted cost by only

0.8\%

Figure 4:

w^{\top}\widetilde{R}(T)/(C_{w}b(T))

(median and interquartile band,

50

seeds) for the oracle and plug-in trackers on

\mu^{(3)}

Figure 5: Three exact

N=4

regret vectors spanning a two-dimensional Pareto face. The top-player coordinate

r_{1}=76/3

is constant and is omitted from the projection.

Group	instances $\times$ seeds	$w^{\top}\widetilde{R}/(C_{w}b)$
$3\times 3$	$10\times 50$	$1.63\pm 0.86$
$4\times 4$	$10\times 50$	$1.63\pm 0.74$
$5\times 5$	$10\times 50$	$1.80\pm 0.78$
$3\times 4$	$\phantom{0}3\times 50$	$1.71\pm 0.61$

Appendix

Table 4: Random markets and baselines,

w=(1,\dots,1)

, mean

\pm

sd of

w^{\top}\widetilde{R}(T)/(C_{w}\,b(T))

over

50

seeds. Top: plug-in tracker at

T=10^{7}

on the

33

random instances, pooled by size. Bottom: one further probe instance per size and the three-player instance

\mu^{(3)}

, with the dedicated-cover and layered KL-UCB baselines; KL-UCB is run at

T=10^{7}

and at

T=10^{5}

, where a plug-in run is added for reference. ∗ From the main suite of § 6 (median

1.23

Explore similar work

Price of Fairness in Bandits: A Tight Minimax Characterization
Jul 15, 2026Dhruv Sarkar, Soumyadeep Dutta, Sayak Ray ChowdhuryMulti-Armed Bandits Minimax Regret
1Indian Institute of Technology Kharagpur · 2Mohamed bin Zayed University of Artificial Intelligence · 3Indian Institute of Technology Kanpur
Prior-Agnostic Incentive-Compatible Exploration
Feb 24, 2026Ramya Ramalingam, Osbert Bastani, Aaron RothMulti-Armed Bandits Regret Minimization
Department of Computer and Information Sciences, University of Pennsylvania
Probably Correct Optimal Stable Matching under Two-Sided Uncertainty
Jul 6, 2026Andreas Athanasopoulos, Anne-Marie George, Christos DimitrakakisMulti-Armed Bandits Preference Learning
University of Neuchâtel, Neuchâtel, Switzerland · University of Oslo, Oslo, Norway

Jul 15, 2026J/K move · Enter open · S save

Price of Fairness in Bandits: A Tight Minimax Characterization

Dhruv Sarkar, Soumyadeep Dutta, Sayak Ray Chowdhury

1Indian Institute of Technology Kharagpur · 2Mohamed bin Zayed University of Artificial Intelligence · 3Indian Institute of Technology Kanpur

Multi-Armed Bandits Minimax Regret Fair Resource Allocation Algorithmic Fairness UCB Algorithms Information-Theoretic Lower Bounds

Open paper AskPDF arXiv

In bandit problems, standard regret-minimizing algorithms treat exploration as an amortized cost, which can expose early participants to unfair ex-ante losses in settings such as clinical trials. Recent work addresses this by evaluating the sequence of per-round expected rewards through the generalized

p

-mean, interpolating between utilitarian welfare (

p=1

), Nash welfare (

p\to0

), and Rawlsian fairness (

p\to-\infty

). Although tight guarantees are known for

p\ge0

, the strictly fair regime

q=-p>0

remains unresolved because negative-power means are dominated by the smallest per-round rewards. For

σ

-sub-Gaussian rewards with nonnegative means, the best prior algorithm relied on uniform early exploration and achieved regret

O(k^{(q+1)/2}/\sqrt{T})

, while the only general lower bound was the classical

Ω(σ\sqrt{k/T})

. Thus it was unclear whether the extra dependence on

k

was intrinsic to strict fairness or an artifact of uniform exploration. We close this gap by identifying the exact polynomial price of strict fairness. Using a needle-in-haystack construction, we prove an algorithm-independent lower bound

Ω(σ\sqrt{k^{\max(1,q)}/T})

; for

q>1

, this shows that the penalty

k^{q/2}

is information-theoretically unavoidable. We then introduce UCB-HARE (Harmonic Anchored Rank Exploration), which replaces uniform exploration with an inverse-weighted harmonic rank schedule protected by a certified positive-mean anchor. Its regret is

\widetilde{O}(σ\sqrt{k^{\max(1,q)}/T})

, matching the lower bound up to logarithmic factors. Experiments on synthetic instances confirm that UCB-HARE improves over uniform-exploration baselines, with gains increasing as

q

grows.

Abstract

Explore similar work

Price of Fairness in Bandits: A Tight Minimax Characterization

Prior-Agnostic Incentive-Compatible Exploration

Probably Correct Optimal Stable Matching under Two-Sided Uncertainty