Discrepancy-Rounded Fair Bandits with Static and Time-Varying Exposure Floors

# Discrepancy-Rounded Fair Bandits with Static and Time-Varying Exposure Floors
Source: [https://arxiv.org/html/2607.22935](https://arxiv.org/html/2607.22935)
###### Abstract

Minimum\-exposure constraints arise in recommendation, content curation, and regulated allocation when each provider, arm, or group must receive guaranteed exposure inside a period rather than only in aggregate\. We study stochastic bandits with exact exposure floors and show that the right object is a rounding problem: a fractional fair schedule is realized as integral pulls, and the exposure error is exactly a discrepancy vector\. The main contribution is a blockwise model with time\-varying floors\. BDQ\-UCB satisfies every block floor deterministically and has fair regret governed by the nonmandatory budgetRR, not the horizonTT, with high\-probability regretO​\(K​R​log⁡\(K​T\)\)O\(\\sqrt\{KR\\log\(KT\)\}\)\. A MOSS residual variant attainsO​\(K​R\)O\(\\sqrt\{KR\}\), and a matching lower bound gives the minimax rateΘ​\(K​R\)\\Theta\(\\sqrt\{KR\}\), even with positive mandatory exposure; a kl\-UCB\+\+residual rule adds instance\-dependent optimality\. The formulation becomes essential for overlapping group floors: per\-arm rounding can violate a group constraint byΩ​\(s\)\\Omega\(s\)in the group size, whereas Beck–Fiala null\-space rounding meets every group floor within the block budget with violation below the arm degreett, and composes with UCB at the sameRR\-parametrized regret\. For learned group plans, we close disjoint systems atΘ~​\(K​T\)\\widetilde\{\\Theta\}\(\\sqrt\{KT\}\), give a dual\-ledger decomposition explaining why naive index rules fail under overlap, and prove a plan\-sampling rule that is pathwise feasible under an initial cover\-slack condition and attains a conditionalO~​\(K​T\)\\widetilde\{O\}\(\\sqrt\{KT\}\)guarantee, leaving the condition\-free overlap rate open\. Experiments on synthetic floors, MovieLens\-100k genre exposure, and deployment stress tests show exact feasibility without penalty tuning and regret competitive with tuned Lagrangian baselines\.

## Introduction

Fairness\-constrained bandits arise when arms are providers, sellers, content sources, treatments, or protected groups that must receive minimum exposure\. A classical stochastic bandit concentrates nearly all pulls on the empirically best arm, but in many allocation systems even a lower\-reward arm is contractually, legally, or ethically entitled to a minimum number of opportunities\.

For a fixed global exposure floor there is a simple, well\-studied solution: give every arm its required pulls, then run a standard bandit algorithm, as Fair\-MAB\(Patilet al\.[2020](https://arxiv.org/html/2607.22935#bib.bib31),[2021](https://arxiv.org/html/2607.22935#bib.bib32)\)formalizes\. Our starting point is different: we read the fairness layer as a*rounding*layer, where the learner realizes a fractional exposure plan through integral pulls and the resulting exposure gap is exactly a discrepancy vector\. This is almost trivial for a single global floor, but becomes structurally useful once floors vary over time and genuinely necessary once they overlap, when a single pull can credit several constraints at once\. Figure[1](https://arxiv.org/html/2607.22935#Sx1.F1)shows the pipeline: within each period, round a fractional fair plan to integral pulls that meet the floor exactly, then spend the remaining rounds learning reward\. The discrepancy rounding leaves behind determines feasibility; the number of nonmandatory rounds determines regret\.

![Refer to caption](https://arxiv.org/html/2607.22935v1/x1.png)Figure 1:The discrepancy\-rounding view of fair bandits\. Each period rounds a fractional fair plan to integral pulls \(the exposure gap is a discrepancy vector\) and spends the remaining rounds on residual UCB\. Per\-arm floors need only cyclic quota rounding; overlapping group floors need genuine set\-discrepancy rounding, where the reduction becomes the algorithm itself rather than merely descriptive language\.This lens organizes the paper\. Our central object is the*blockwise*model, in which the horizon is split into periods, each carrying its own integer floor vector that must be satisfied inside that period rather than only in aggregate\. The blockwise algorithm BDQ\-UCB \(Blockwise Discrepancy\-Quota Upper Confidence Bound\) executes each block’s quota exactly and runs UCB only on the rounds the floor leaves free, so its fair regret is governed by the total nonmandatory budget

R=∑b=1B\(Hb−∑imb,i\),R=\\sum\_\{b=1\}^\{B\}\\Bigl\(H\_\{b\}\-\\sum\_\{i\}m\_\{b,i\}\\Bigr\),not by the horizonTT\. This is the right complexity parameter in a strong sense: a matching lower bound and a MOSS\-based residual rule pin the minimax rate atΘ​\(K​R\)\\Theta\(\\sqrt\{KR\}\), even when the mandatory exposure is a constant fraction of the horizon, and a kl\-UCB\+\+residual rule recovers the exact instance\-dependent constant\. The mandatory pulls, being common to every fair policy, are free; all unavoidable exploration lives in the residual budget\. Algorithm names are systematic: the suffix is the residual index rule \(UCB, MOSS, or kl\-UCB\+\+\); DQ\-UCB is the static base, the B prefix marks the blockwise version, and the Group\-, D\-, OG\-, and P\- prefixes mark the fixed\-, disjoint\-, one\-shot\-, and sampled\-plan group algorithms\.

The reduction becomes necessary when floors are placed over overlapping groups\. Rounding a group\-feasible fractional plan with a per\-arm rule can miss a group floor byΩ​\(s\)\\Omega\(s\)in the group size, whereas Beck–Fiala null\-space rounding, a genuine discrepancy algorithm, meets every group floor within the reserved block budget using group slack strictly below the arm degreett, independent of the group size and the number of groups\. Composed with UCB, this yields Group\-BDQ\-UCB at the same residual\-budget regret for a fixed group plan\. The final question is whether the plan itself can be learned, so the benchmark becomes the best group\-fair plan rather than a given one\. Here the answer is sharp for disjoint groups, where a per\-pull covering rule closes the price of plan adaptivity atΘ~​\(K​T\)\\widetilde\{\\Theta\}\(\\sqrt\{KT\}\)against a matching lower bound, and partial under arbitrary overlap, where linear\-programming duality identifies the exact obstruction and a plan\-sampling rule attains a conditionalO~​\(K​T\)\\widetilde\{O\}\(\\sqrt\{KT\}\)guarantee whose one open hypothesis we state explicitly\. The full complexity picture across settings is summarized in Table[3](https://arxiv.org/html/2607.22935#A2.T3)\(Appendix[B](https://arxiv.org/html/2607.22935#A2)\)\.

We calibrate the claims explicitly\. The static result is a rederivation of fixed\-floor exposure fairness, not a new rate over Fair\-MAB; the modeling contribution is the blockwise floor model, whose floors are period\-specific, revealed before each period, and satisfied inside it\. The separation result rules out final\-count and block\-independent surrogates but not deadline\-aware dynamic penalties, which we include as baselines\. The framework’s value is exact feasibility without penalty calibration and regret governed by the nonmandatory budgetRR\.

## Related Work

The closest prior work is the Fair\-MAB framework\(Patilet al\.[2020](https://arxiv.org/html/2607.22935#bib.bib31),[2021](https://arxiv.org/html/2607.22935#bib.bib32)\), which requires every arm to receive a prescribed fraction of the pulls at every round up to an additive tolerance and measures regret against a fairness\-aware comparator\. Our static result is a discrepancy\-based rederivation of this guarantee rather than a rate improvement, and because the quota is front\-loaded, DQ\-UCB meets the same anytime floor with tolerance one \(Remark[13](https://arxiv.org/html/2607.22935#Thmtheorem13)\), but its purpose is to make the rounding layer explicit and carry it to the blockwise time\-varying floors Fair\-MAB does not capture\. Other fairness criteria for bandits are complementary rather than directly comparable: meritocracy\(Josephet al\.[2016](https://arxiv.org/html/2607.22935#bib.bib24)\), merit\-based exposure\(Wanget al\.[2021](https://arxiv.org/html/2607.22935#bib.bib38)\), Nash social welfare\(Barmanet al\.[2022](https://arxiv.org/html/2607.22935#bib.bib12)\), max\-min fairness\(Haradaet al\.[2025](https://arxiv.org/html/2607.22935#bib.bib22)\), fairness under uncertainty\(Leeet al\.[2026](https://arxiv.org/html/2607.22935#bib.bib27)\), and the fairness–performance frontier\(Wilms and Heitz[2026](https://arxiv.org/html/2607.22935#bib.bib39)\), whose Pareto viewpoint parallels our closed\-form analysis\.

Nearer to exact exposure are works with explicit group or contextual constraints \(fair contextual bandits\(Chenet al\.[2020](https://arxiv.org/html/2607.22935#bib.bib17)\), bilevel group exposure with within\-group merit\(Pokhriyalet al\.[2024](https://arxiv.org/html/2607.22935#bib.bib33)\), hypergeometric finite\-pool ranking floors\(Cartier van Disselet al\.[2025](https://arxiv.org/html/2607.22935#bib.bib16)\), and graph\-structured multi\-regularizer fairness\(Zhouet al\.[2025](https://arxiv.org/html/2607.22935#bib.bib41)\)\) and works that relax the single stationary learner through interacting agents\(Manupriyaet al\.[2025](https://arxiv.org/html/2607.22935#bib.bib30); Xuet al\.[2025](https://arxiv.org/html/2607.22935#bib.bib40); Krishnamurthyet al\.[2026](https://arxiv.org/html/2607.22935#bib.bib25)\)or slow non\-stationarity\(Shaarad and Dukkipati[2020](https://arxiv.org/html/2607.22935#bib.bib34)\), the latter adjacent to our blockwise model\. A separate line enforces constraints through budgets, queues, or duality \(bandits with knapsacks\(Badanidiyuruet al\.[2013](https://arxiv.org/html/2607.22935#bib.bib6)\), concave\-reward convex\-constraint extensions\(Agrawal and Devanur[2014](https://arxiv.org/html/2607.22935#bib.bib3)\), virtual\-queue fairness in combinatorial sleeping bandits\(Liet al\.[2019](https://arxiv.org/html/2607.22935#bib.bib28)\), modified\-index minimum\-rate fairness\(Claureet al\.[2020](https://arxiv.org/html/2607.22935#bib.bib18)\), and dual mirror descent for online allocation\(Balseiroet al\.[2020](https://arxiv.org/html/2607.22935#bib.bib7)\)\) but these certify only asymptotic or average feasibility, whereas exact per\-period feasibility is what our model makes primitive; a deadline\-aware Lagrangian represents this penalty\-based family in our experiments\. None of these enforces time\-varying block\-level floors deterministically without penalty tuning; the combination of exact blockwise feasibility, a tuning\-free design, and a matching minimax lower bound is what is specific to this work\.

The analysis draws on standard bandit machinery: finite\-time upper confidence bound \(UCB\)\(Aueret al\.[2002](https://arxiv.org/html/2607.22935#bib.bib5); Hanet al\.[2024](https://arxiv.org/html/2607.22935#bib.bib21)\); the minimax construction via the Kullback–Leibler \(KL\) chain rule and Pinsker’s inequality\(Bubeck and Cesa\-Bianchi[2012](https://arxiv.org/html/2607.22935#bib.bib15); Lattimore and Szepesvári[2020](https://arxiv.org/html/2607.22935#bib.bib26)\); its Bretagnolle–Huber form for the instance\-dependent lower bound; and the MOSS\(Audibert and Bubeck[2009](https://arxiv.org/html/2607.22935#bib.bib2)\)and kl\-UCB\+\+\(Ménard and Garivier[2017](https://arxiv.org/html/2607.22935#bib.bib1)\)indices behind our rate\-optimal residual rules\. Allocation under time\-varying demand is complementary \(floors there are unknown, ours are revealed per block\(Lyu and Cheung[2023](https://arxiv.org/html/2607.22935#bib.bib29)\)\) and multi\-objective and preference/risk mixtures\(Davoodi and Maghsudi[2025](https://arxiv.org/html/2607.22935#bib.bib19); Tatlıet al\.[2025a](https://arxiv.org/html/2607.22935#bib.bib36),[b](https://arxiv.org/html/2607.22935#bib.bib37)\)share the mixture structure of our Pareto curve\. Finally, the rounding engine is classical discrepancy theory \(Spencer’s theorem\(Spencer[1985](https://arxiv.org/html/2607.22935#bib.bib35)\), Banaszczyk balancing\(Banaszczyk[1998](https://arxiv.org/html/2607.22935#bib.bib8)\), Bansal’s constructive method\(Bansal[2010](https://arxiv.org/html/2607.22935#bib.bib9)\), dependent rounding\(Gandhiet al\.[2006](https://arxiv.org/html/2607.22935#bib.bib20)\), matroid\-friendly rounding\(Bansal and Nagarajan[2016](https://arxiv.org/html/2607.22935#bib.bib10)\), and online vector balancing\(Bansalet al\.[2020](https://arxiv.org/html/2607.22935#bib.bib11); Altschuler and Tikhomirov[2025](https://arxiv.org/html/2607.22935#bib.bib4); Bednorz and Godlewski[2024](https://arxiv.org/html/2607.22935#bib.bib14)\)\), from which we use the Beck–Fiala theorem as the central tool for overlapping floors and to which we connect the harder online results in the open adaptive\-planning question\.

## Problem Setup and the Discrepancy Reduction

We study a stochasticKK\-armed bandit with horizonTT\. Armiiproduces independent rewards in\[0,1\]\[0,1\]with meanμi\\mu\_\{i\}\. Let

i⋆∈arg​maxi∈\[K\]⁡μi,μ⋆=μi⋆,Δi=μ⋆−μi,i^\{\\star\}\\in\\operatorname\*\{arg\\,max\}\_\{i\\in\[K\]\}\\mu\_\{i\},\\qquad\\mu\_\{\\star\}=\\mu\_\{i^\{\\star\}\},\\qquad\\Delta\_\{i\}=\\mu\_\{\\star\}\-\\mu\_\{i\},so thatΔi⋆=0\\Delta\_\{i^\{\\star\}\}=0andΔi≥0\\Delta\_\{i\}\\geq 0for every armii\. Notation is summarized in Table[2](https://arxiv.org/html/2607.22935#A1.T2), and all proofs are deferred to the technical appendix\.

For a target exposure fractionδ∈\[0,1/K\]\\delta\\in\[0,1/K\], the integral floor ism=⌊δ​T⌋m=\\lfloor\\delta T\\rfloor, and a policy ismm\-fair if its final pull counts satisfyNi​\(T\)≥mN\_\{i\}\(T\)\\geq mfor every armi∈\[K\]i\\in\[K\]\(equivalently, the empirical exposure of every arm is at leastm/T≥δ−1/Tm/T\\geq\\delta\-1/T\)\. The bestmm\-fair allocation, the induced fair pseudo\-regret, and the fair\-regret identityReg^m​\(T\)=∑i≠i⋆Δi​\(Ni​\(T\)−m\)\\widehat\{\\mathrm\{Reg\}\}\_\{m\}\(T\)=\\sum\_\{i\\neq i^\{\\star\}\}\\Delta\_\{i\}\\bigl\(N\_\{i\}\(T\)\-m\\bigr\), which shows fair regret is a gap\-weighted count of pulls beyond the quota, are the static \(B=1B=1\) specialization of the blockwise objects of the next section; we defer their formal statements to Appendix[C](https://arxiv.org/html/2607.22935#A3)\(Lemma[10](https://arxiv.org/html/2607.22935#Thmtheorem10)\)\. This gap\-weighted count is what the discrepancy view will make actionable\.

### The Exposure–Discrepancy Identity

We first record that the difference between a fractional fair schedule and an integral pull sequence is exactly a discrepancy vector\. A fractional allocation at timettis a vectorxt∈ℝKx\_\{t\}\\in\\mathbb\{R\}^\{K\}withxt,i≥0x\_\{t,i\}\\geq 0and∑ixt,i=1\\sum\_\{i\}x\_\{t,i\}=1, the intended cumulative fractional exposure of armiiisSi​\(T\)=∑t=1Txt,iS\_\{i\}\(T\)=\\sum\_\{t=1\}^\{T\}x\_\{t,i\}, and a deterministic pullAtA\_\{t\}corresponds to the standard basis vectoreAte\_\{A\_\{t\}\}\. Define the discrepancy vector

DT=∑t=1T\(eAt−xt\)=N​\(T\)−S​\(T\),D\_\{T\}=\\sum\_\{t=1\}^\{T\}\\bigl\(e\_\{A\_\{t\}\}\-x\_\{t\}\\bigr\)=N\(T\)\-S\(T\),whereN​\(T\)=\(N1​\(T\),…,NK​\(T\)\)N\(T\)=\(N\_\{1\}\(T\),\\dots,N\_\{K\}\(T\)\)andS​\(T\)=\(S1​\(T\),…,SK​\(T\)\)S\(T\)=\(S\_\{1\}\(T\),\\dots,S\_\{K\}\(T\)\)\.

###### Proposition 1\(Exposure–discrepancy identity\)\.

Fix any fractional schedulex1,…,xTx\_\{1\},\\dots,x\_\{T\}\. For any pull sequenceA1,…,ATA\_\{1\},\\dots,A\_\{T\}, the following hold\.

1. \(i\)The exposure error of each arm is exactly the corresponding coordinate of the discrepancy vector: Ni​\(T\)−Si​\(T\)=DT,i\.N\_\{i\}\(T\)\-S\_\{i\}\(T\)=D\_\{T,i\}\.Hence, ifSi​\(T\)≥m\+BS\_\{i\}\(T\)\\geq m\+Bfor everyiiand‖DT‖∞≤B\\\|D\_\{T\}\\\|\_\{\\infty\}\\leq B, then the integral pull sequence ismm\-fair\.
2. \(ii\)The reward gap relative to the fractional schedule is a weighted discrepancy: ∑t=1Tμ⊤​xt−∑t=1TμAt=−μ⊤​DT\.\\sum\_\{t=1\}^\{T\}\\mu^\{\\top\}x\_\{t\}\-\\sum\_\{t=1\}^\{T\}\\mu\_\{A\_\{t\}\}=\-\\mu^\{\\top\}D\_\{T\}\.
3. \(iii\)Therefore, minimizing reward loss subject to a fairness floor is a constrained discrepancy\-minimization problem: one chooses one vector from\{e1−xt,…,eK−xt\}\\\{e\_\{1\}\-x\_\{t\},\\dots,e\_\{K\}\-x\_\{t\}\\\}at each timett, controls the terminalℓ∞\\ell\_\{\\infty\}discrepancy for fairness, and controls the weighted discrepancy−μ⊤​DT\-\\mu^\{\\top\}D\_\{T\}for regret\.

The identity is elementary, its proof is telescoping plus linearity, and we deliberately label it a proposition rather than a theorem\. Its value is organizational: it fixes the objects the algorithms manipulate, and it is what will later let a genuine discrepancy algorithm, Beck–Fiala rounding, solve a fairness problem that per\-arm rounding provably cannot\. In the static algorithm in Appendix[C](https://arxiv.org/html/2607.22935#A3)we use a simple constructive rounding schedule for the mandatory quota part; in the blockwise extension the same rounding idea is applied separately to each block\.

## Blockwise Exposure Floors

The main extension is blockwise fairness\. The horizon is partitioned intoBBconsecutive blocksℬ1,…,ℬB\\mathcal\{B\}\_\{1\},\\ldots,\\mathcal\{B\}\_\{B\}, where blockbbhas lengthHbH\_\{b\}, and each block has its own integer floor vector

mb=\(mb,1,…,mb,K\)∈ℤ≥0K,∑i=1Kmb,i≤Hb\.m\_\{b\}=\(m\_\{b,1\},\\ldots,m\_\{b,K\}\)\\in\\mathbb\{Z\}\_\{\\geq 0\}^\{K\},\\qquad\\sum\_\{i=1\}^\{K\}m\_\{b,i\}\\leq H\_\{b\}\.A policy is blockwise fair ifNb,i≥mb,iN\_\{b,i\}\\geq m\_\{b,i\}for every blockbband armii, whereNb,iN\_\{b,i\}is the number of pulls of armiiinside blockbb\. This model captures time\-varying exposure contracts, rotating provider guarantees, periodic protected\-group targets, or demand\-dependent exposure requirements, and it cannot be represented by a single global minimum fraction\.

###### Definition 1\(Best blockwise\-fair allocation\)\.

The best blockwise\-fair allocation gives the floormb,im\_\{b,i\}to every arm in each block and allocates the residualHb−∑jmb,jH\_\{b\}\-\\sum\_\{j\}m\_\{b,j\}pulls of that block to a best arm\. Its value is

OPT𝐦​\(T\)=T​μ⋆−∑b=1B∑i≠i⋆mb,i​Δi,\\mathrm\{OPT\}\_\{\\mathbf\{m\}\}\(T\)=T\\mu\_\{\\star\}\-\\sum\_\{b=1\}^\{B\}\\sum\_\{i\\neq i^\{\\star\}\}m\_\{b,i\}\\Delta\_\{i\},and the realized blockwise fair pseudo\-regret isReg^𝐦​\(T\)=OPT𝐦​\(T\)−∑t=1TμAt\\widehat\{\\mathrm\{Reg\}\}\_\{\\mathbf\{m\}\}\(T\)=\\mathrm\{OPT\}\_\{\\mathbf\{m\}\}\(T\)\-\\sum\_\{t=1\}^\{T\}\\mu\_\{A\_\{t\}\}\.

###### Lemma 2\(Blockwise fair\-regret identity\)\.

For every pull sequence,

Reg^𝐦​\(T\)=∑i≠i⋆Δi​\(Ni​\(T\)−∑b=1Bmb,i\)\.\\widehat\{\\mathrm\{Reg\}\}\_\{\\mathbf\{m\}\}\(T\)=\\sum\_\{i\\neq i^\{\\star\}\}\\Delta\_\{i\}\\left\(N\_\{i\}\(T\)\-\\sum\_\{b=1\}^\{B\}m\_\{b,i\}\\right\)\.If the sequence is blockwise fair, thenReg^𝐦​\(T\)≥0\\widehat\{\\mathrm\{Reg\}\}\_\{\\mathbf\{m\}\}\(T\)\\geq 0\.

### BDQ\-UCB Algorithm and Guarantees

BDQ\-UCB applies discrepancy rounding separately in each block\. At the start of blockbbit executes any deterministic schedule containing exactlymb,im\_\{b,i\}copies of armii, realizing the block floor with terminal discrepancy zero relative to the block target, and then runs UCB for the remainingHb−∑imb,iH\_\{b\}\-\\sum\_\{i\}m\_\{b,i\}rounds using all observations so far\. We use the standard optimistic convention that an arm with zero observations has UCB index\+∞\+\\inftyduring residual rounds \(equivalently, unseen arms are sampled before the empirical\-mean index is used\); this is needed because early blocks may havemb,i=0m\_\{b,i\}=0for some arm, and the additiveKKterm in the regret bounds is its initialization cost\. Pseudocode is Algorithm[1](https://arxiv.org/html/2607.22935#alg1)\.

Algorithm 1BDQ\-UCB1:Input:arms

KK, blocks

BB, block lengths

\(Hb\)\(H\_\{b\}\), floors

\(mb,i\)\(m\_\{b,i\}\), failure prob\.

η∈\(0,1\)\\eta\\in\(0,1\)
2:Output:pull sequence across all blocks

3:

L←log⁡\(2​K​T/η\)L\\leftarrow\\log\(2KT/\\eta\), where

T=∑bHbT=\\sum\_\{b\}H\_\{b\}
4:for

b=1,…,Bb=1,\\dots,Bdo

5:Pull each arm

i∈\[K\]i\\in\[K\]exactly

mb,im\_\{b,i\}times \(any fixed order; count determines fairness\)

6:foreach residual round in block

bbdo

7:For each arm

ii, set

Ui←\+∞U\_\{i\}\\leftarrow\+\\inftyif

Ni=0N\_\{i\}=0and

Ui←μ^i\+2​L/NiU\_\{i\}\\leftarrow\\widehat\{\\mu\}\_\{i\}\+\\sqrt\{2L/N\_\{i\}\}otherwise\.

8:Pull

A∈arg​maxi∈\[K\]⁡UiA\\in\\operatorname\*\{arg\\,max\}\_\{i\\in\[K\]\}U\_\{i\},

NiN\_\{i\}= total pulls of arm

iiso far

9:endfor

10:endfor

Let

R=∑b=1B\(Hb−∑i=1Kmb,i\)R=\\sum\_\{b=1\}^\{B\}\\left\(H\_\{b\}\-\\sum\_\{i=1\}^\{K\}m\_\{b,i\}\\right\)be the total number of nonmandatory rounds\.

###### Theorem 3\(Blockwise exact fairness and regret\)\.

Assume rewards are independent and supported in\[0,1\]\[0,1\]\. BDQ\-UCB satisfies:

1. \(i\)Deterministically,Nb,i≥mb,iN\_\{b,i\}\\geq m\_\{b,i\}for every blockbband armii\.
2. \(ii\)With probability at least1−η1\-\\eta, Reg^𝐦​\(T\)\\displaystyle\\widehat\{\\mathrm\{Reg\}\}\_\{\\mathbf\{m\}\}\(T\)≤K\+∑i:Δi\>0min⁡\{R​Δi,8​LΔi\},\\displaystyle\\leq K\+\\sum\_\{i:\\Delta\_\{i\}\>0\}\\min\\left\\\{R\\Delta\_\{i\},\\,\\frac\{8L\}\{\\Delta\_\{i\}\}\\right\\\},L=log⁡\(2​K​Tη\)\.\\displaystyle\\qquad L=\\log\\left\(\\frac\{2KT\}\{\\eta\}\\right\)\.\(1\)
3. \(iii\)With probability at least1−η1\-\\eta, Reg^𝐦​\(T\)≤K\+4​2​K​R​L\.\\widehat\{\\mathrm\{Reg\}\}\_\{\\mathbf\{m\}\}\(T\)\\leq K\+4\\sqrt\{2KRL\}\.

TakingB=1B=1,H1=TH\_\{1\}=T, andm1,i=mm\_\{1,i\}=mfor every arm recovers the static single\-floor guarantee \(Theorem[12](https://arxiv.org/html/2607.22935#Thmtheorem12), Appendix[C](https://arxiv.org/html/2607.22935#A3)\) as the special case of Theorem[3](https://arxiv.org/html/2607.22935#Thmtheorem3), up to replacingR=T−K​mR=T\-Kmby the looser boundTT\(Corollary[33](https://arxiv.org/html/2607.22935#Thmtheorem33), Appendix[I\.29](https://arxiv.org/html/2607.22935#A9.SS29)\)\.

BDQ\-UCB extends unchanged to the setting wherembm\_\{b\}is revealed only at the start of blockbb, without knowledge of future floors\. Because feasibility is block\-local and the UCB concentration event does not depend on future floors, all realized block constraints hold and the regret bounds of Theorem[3](https://arxiv.org/html/2607.22935#Thmtheorem3)apply conditional on the realized floor sequence; Appendix[E](https://arxiv.org/html/2607.22935#A5)makes this precise\.

### Lower Bounds and the Optimal Rate

This section pins the complexity of blockwise fair bandits from both sides and in both regimes: the residual budgetRR, not the total horizonTT, is the right parameter, in the minimax sense and in the instance\-dependent sense\. Mandatory pulls are matched by the comparator, so the unavoidable exploration cost lives in the nonmandatory rounds\.

###### Theorem 4\(Minimax lower bound\)\.

There is a universal constantc\>0c\>0such that, for everyK≥2K\\geq 2and every residual budgetR≥KR\\geq K, there exists a blockwise\-fair instance with total nonmandatory budgetRRfor which every blockwise\-fair policyπ\\pisatisfies

supμ∈\[0,1\]KReg𝐦π​\(T\)≥c​K​R\.\\sup\_\{\\mu\\in\[0,1\]^\{K\}\}\\mathrm\{Reg\}\_\{\\mathbf\{m\}\}^\{\\pi\}\(T\)\\geq c\\sqrt\{KR\}\.Consequently, BDQ\-UCB is minimax optimal for blockwise fair regret up to logarithmic factors\.

The logarithmic gap between Theorems[3](https://arxiv.org/html/2607.22935#Thmtheorem3)and[4](https://arxiv.org/html/2607.22935#Thmtheorem4)is removable: a MOSS index\(Audibert and Bubeck[2009](https://arxiv.org/html/2607.22935#bib.bib2)\)on residual observations gives BDQ\-MOSS with expected blockwise fair regret at mostC​K​R\+KC\\sqrt\{KR\}\+K, so the minimax rate isΘ​\(K​R\)\\Theta\(\\sqrt\{KR\}\)forR≥KR\\geq K\(Theorem[17](https://arxiv.org/html/2607.22935#Thmtheorem17)\)\. BDQ\-MOSS discards mandatory observations, which makes the reduction black\-box; the UCB variant uses every observation, carries the gap\-dependent guarantee of Theorem[3](https://arxiv.org/html/2607.22935#Thmtheorem3)\(ii\), and is the one we run\. The instance\-dependent characterization, the positive\-mandatory\-exposure lower bound, and the kl\-UCB\+\+variant are in Appendix[D](https://arxiv.org/html/2607.22935#A4)\.

The blockwise model is also strictly more expressive than any single global fraction: a global final\-count constraint fixes total exposure but not*when*an arm receives it, and a block\-independent per\-block surrogate enforces timing only by over\-serving blocks where no exposure is due\. Proposition[34](https://arxiv.org/html/2607.22935#Thmtheorem34)makes this precise on a two\-arm rotating\-floor family: no global final count encodes the constraints, and any block\-independent bound either violates a floor or paysΩ​\(α​Δ​T\)\\Omega\(\\alpha\\Delta T\)extra regret, while BDQ\-UCB is exactly feasible atO​\(K​R​log⁡K​T\)O\(\\sqrt\{KR\\log KT\}\)\. The separation is scoped to those two surrogate classes; deadline\-aware dynamic penalties escape it once tuned, which is why our experiments carry a deadline\-aware Lagrangian as a calibration baseline\.

## Overlapping Group Floors and Set\-Discrepancy Rounding

The constructions so far use per\-arm floors, which cyclic quota rounding \(Lemma[11](https://arxiv.org/html/2607.22935#Thmtheorem11)\) already satisfies exactly\. We now turn to the setting that justifies the discrepancy view as more than a vocabulary:*overlapping*group floors, where a single pull credits several groups at once\. Let𝒢\\mathcal\{G\}be a collection of arm subsets \(groups\), and require that within each block every groupg∈𝒢g\\in\\mathcal\{G\}receive at leastfgf\_\{g\}pulls in aggregate, that is,∑i∈gNb,i≥fg\\sum\_\{i\\in g\}N\_\{b,i\}\\geq f\_\{g\}\. Such constraints arise when a provider belongs to several protected categories simultaneously \(a film is both independent and foreign; a seller sits in several promotional tiers\)\. Each arm belongs to at mostttgroups, the maximum*arm degree*\.

Per\-arm rounding is no longer enough here\. Rounding a group\-feasible fractional planxxto integral pulls incurs a group exposure error\|∑i∈g\(ni−xi\)\|=\|∑i∈gDi\|\\bigl\|\\sum\_\{i\\in g\}\(n\_\{i\}\-x\_\{i\}\)\\bigr\|=\\bigl\|\\sum\_\{i\\in g\}D\_\{i\}\\bigr\|, which is exactly a signed\-sum set discrepancy of the per\-arm discrepancy vectorD=n−xD=n\-xover the set system𝒢\\mathcal\{G\}\. Bounding group violation is therefore a set\-discrepancy problem, and this is where the identity of Proposition[1](https://arxiv.org/html/2607.22935#Thmtheorem1)becomes essential, because the classical Beck–Fiala theorem\(Beck and Fiala[1981](https://arxiv.org/html/2607.22935#bib.bib13)\)bounds exactly this quantity\. The failure of group\-blind rounding is not hypothetical\.

###### Proposition 5\(Naive rounding fails on group floors\)\.

There is a group\-floor instance with groups of sizesson which independent per\-arm nearest\-integer rounding \(the group\-blind analogue of cyclic quota rounding\) violates some group floor byΩ​\(s\)\\Omega\(s\)\.

One might hope to escape by rounding every coordinate up instead, but that inflates the mandatory phase by up to one pull per arm and can exceed the rounds reserved for it; the real problem is meeting every group floor*within the block budget*, and that is what the discrepancy algorithm delivers\.

###### Theorem 6\(Group\-fair rounding via Beck–Fiala\)\.

Let every arm belong to at mostttgroups of𝒢\\mathcal\{G\}, and letx∈ℝ≥0Kx\\in\\mathbb\{R\}\_\{\\geq 0\}^\{K\}be a fractional block plan whose group totals satisfy∑i∈gxi≥fg\+t\\sum\_\{i\\in g\}x\_\{i\}\\geq f\_\{g\}\+tfor everyg∈𝒢g\\in\\mathcal\{G\}and whose ceiling budget satisfies∑i⌈xi⌉≤C\\sum\_\{i\}\\lceil x\_\{i\}\\rceil\\leq C, whereCCis the number of rounds reserved for the mandatory phase of the block\. Beck–Fiala null\-space rounding outputs, in polynomial time, an integral allocationnnwithni∈\{⌊xi⌋,⌈xi⌉\}n\_\{i\}\\in\\\{\\lfloor x\_\{i\}\\rfloor,\\lceil x\_\{i\}\\rceil\\\}for every arm \(hence∑i⌊xi⌋≤∑ini≤∑i⌈xi⌉≤C\\sum\_\{i\}\\lfloor x\_\{i\}\\rfloor\\leq\\sum\_\{i\}n\_\{i\}\\leq\\sum\_\{i\}\\lceil x\_\{i\}\\rceil\\leq C\) and with

\|∑i∈g\(ni−xi\)\|<tfor every​g∈𝒢,\\Bigl\|\\sum\_\{i\\in g\}\(n\_\{i\}\-x\_\{i\}\)\\Bigr\|<t\\qquad\\text\{for every \}g\\in\\mathcal\{G\},independent of the group sizessand of\|𝒢\|\|\\mathcal\{G\}\|\. Consequently every group floorfgf\_\{g\}is met within the reserved budget\.

The rounding composes with learning exactly as in the per\-arm case, giving a group\-fair bandit policy rather than a rounding statement alone\.

###### Corollary 7\(Group\-BDQ\-UCB\)\.

In each blockbb, letxbx\_\{b\}be any group\-feasible fractional plan with slackttwhose ceiling budget satisfies∑i⌈xb,i⌉≤Hb\\sum\_\{i\}\\lceil x\_\{b,i\}\\rceil\\leq H\_\{b\}, letnbn\_\{b\}be its Beck–Fiala rounding, execute thenb,in\_\{b,i\}mandatory pulls of each arm, and run UCB on the remainingRb=Hb−∑inb,iR\_\{b\}=H\_\{b\}\-\\sum\_\{i\}n\_\{b,i\}rounds of the block\. Then every group floor is met in every block deterministically, and with probability at least1−η1\-\\etathe fair regret relative to the comparator that executes the same mandatory allocations\(nb\)b≤B\(n\_\{b\}\)\_\{b\\leq B\}and assigns every residual round to a best arm is at mostK\+4​2​K​R​LK\+4\\sqrt\{2KRL\}, withR=∑bRbR=\\sum\_\{b\}R\_\{b\}andL=log⁡\(2​K​T/η\)L=\\log\(2KT/\\eta\)\.

The proof, in the appendix, is the residual argument of Theorem[3](https://arxiv.org/html/2607.22935#Thmtheorem3)verbatim: the mandatory pulls are comparator\-matched by construction, so only residual pulls of suboptimal arms contribute\. Relative to the fractional plan itself, the mandatory phase additionally changes reward by the weighted discrepancy−μ⊤​\(nb−xb\)\-\\mu^\{\\top\}\(n\_\{b\}\-x\_\{b\}\), which the per\-coordinate containment bounds by the number of fractional coordinates in the block; this is the unavoidable price of integrality, not a learning cost\. Replacing the residual rule by the MOSS index as in Theorem[17](https://arxiv.org/html/2607.22935#Thmtheorem17)yields Group\-BDQ\-MOSS with expected group\-fair regretC​K​R\+KC\\sqrt\{KR\}\+Kby the same embedded\-game reduction\.

The contrast between the two rounding rules is sharp, and it is what makes the discrepancy bridge essential rather than cosmetic\. On a row/column set system over ana×ba\\times bgrid \(every arm int=2t=2groups, group sizes=max⁡\(a,b\)s=\\max\(a,b\)\) with the adversarial half\-integral plan of Proposition[5](https://arxiv.org/html/2607.22935#Thmtheorem5), Beck–Fiala group violation stays belowt=2t=2at every scale while naive nearest rounding grows linearly inss, exactly as the construction predicts \(Table[5](https://arxiv.org/html/2607.22935#A8.T5), Appendix[H](https://arxiv.org/html/2607.22935#A8)\)\. Whent≪st\\ll sthe discrepancy algorithm is provably and unboundedly better than per\-arm rounding\.

## Learning the Group Plan

So far the fractional plan has been an input: Corollary[7](https://arxiv.org/html/2607.22935#Thmtheorem7)guarantees regret only against the comparator that executes the*same*plan\. Beyond off\-the\-shelf rounding lies the harder question of whether the plan itself can be learned, so that the benchmark becomes the best group\-fair plan rather than the given one\. We answer with an optimistic planning layer around the same Beck–Fiala engine, a regret guarantee against the per\-block fractional optimum, and a lower bound showing that this stronger benchmark carries an unavoidable new cost\.

We answer with OG\-BDQ\-UCB, an optimistic planner that in each block solves a linear program over a slacked plan polytope \(group floors raised by the arm degreett, budget reduced by2​K2Kfor rounding and initialization\), rounds the solution with the same Beck–Fiala engine, and spends the reserve on the residual UCB rule\. AgainstOPTad\\mathrm\{OPT\}^\{\\mathrm\{ad\}\}, the best slack\-feasible per\-block plan with its reserve on a best arm, it is exactly feasible and satisfiesOPTad−V≤3​K​B\+4​Hmax​2​L​B\\mathrm\{OPT\}^\{\\mathrm\{ad\}\}\-V\\leq 3KB\+4H\_\{\\max\}\\sqrt\{2LB\}with probability at least1−η1\-\\eta\(Theorem[22](https://arxiv.org/html/2607.22935#Thmtheorem22), Appendix[F](https://arxiv.org/html/2607.22935#A6)\); the built\-in slack costs onlyO​\(B\)O\(B\)against the unslacked optimum under uniform Slater\-type margins \(Proposition[23](https://arxiv.org/html/2607.22935#Thmtheorem23)\)\. More interesting is that this stronger benchmark is genuinely more expensive: in everyRR\-parametrized result above, forced pulls cancel because the comparator matches them, but when the comparator instead places the forced mass optimally*within*each group, forcing exposure onto arms whose ordering is still unresolved is itself an exploration cost\.

###### Proposition 8\(The price of plan adaptivity\)\.

For everyB≥1B\\geq 1and every evenH≥2H\\geq 2there is a family of blockwise group\-floor instances \(K=2​B\+1K=2B\+1arms,BBblocks of lengthHH,*disjoint*groups of size two \(arm degreet=1t=1\), group floorH/2H/2on one fresh group per block\) on which every blockwise\-group\-fair policyπ\\pisatisfies

supfamily\[OPTfrac−𝔼​\[Vπ\]\]≥c​B​H\\sup\_\{\\mathrm\{family\}\}\\ \\bigl\[\\mathrm\{OPT\}^\{\\mathrm\{frac\}\}\-\\mathbb\{E\}\[V^\{\\pi\}\]\\bigr\]\\ \\geq\\ c\\,B\\sqrt\{H\}for a universal constantc\>0c\>0, whereOPTfrac\\mathrm\{OPT\}^\{\\mathrm\{frac\}\}is the sum of per\-block fractional group\-fair optima\. SinceT=B​HT=BH, the bound isc​B⋅Tc\\sqrt\{B\}\\cdot\\sqrt\{T\}, while the same instances admit a fixed\-plan comparator against which Corollary[7](https://arxiv.org/html/2607.22935#Thmtheorem7)achieves regretO​\(K​R​L\)O\(\\sqrt\{KRL\}\)\.

Each block introduces a fresh pair of arms whose within\-pair ordering is unknown and must absorb half the block as forced exposure; an Assouad\-type averaging over independent sign patterns, with a Bretagnolle–Huber two\-point bound per block \(cf\.Lattimore and Szepesvári[2020](https://arxiv.org/html/2607.22935#bib.bib26)\), gives the result, and a Markov selection step keeps the per\-block information cost bounded without restricting the regime \(proof in the appendix\)\. Because the groups are disjoint, the cost is attributable entirely to learning the plan, not to the rounding\.

For disjoint systems, in fact, the gap closes entirely\. No rounding is needed there, the per\-block optimum decomposes across groups, and a per\-pull optimistic covering rule turns each group’s forced mass into its own embedded bandit\. D\-BDQ\-UCB executes, in each blockbb, exactlyfb,gf\_\{b,g\}covering pulls for every groupgg\(each selected as the index\-maximizing memberarg​maxi∈g⁡Ui\\operatorname\*\{arg\\,max\}\_\{i\\in g\}U\_\{i\}, with indices updated after every pull and computed from all observations\) and spends the surplusHb−∑gfb,gH\_\{b\}\-\\sum\_\{g\}f\_\{b,g\}rounds by the global UCB rule\.

###### Theorem 9\(Disjoint groups: the gap closes\)\.

Let the groups be pairwise disjoint and let every block satisfy∑gfb,g≤Hb\\sum\_\{g\}f\_\{b,g\}\\leq H\_\{b\}\. D\-BDQ\-UCB meets every group floor in every block exactly and deterministically, and with probability at least1−η1\-\\etaits realized mean valueVVsatisfies

OPTfrac−V\\displaystyle\\mathrm\{OPT\}^\{\\mathrm\{frac\}\}\-V≤4​K\+4​2​L​\(∑g∈𝒢\|g\|​Fg\+K​R′\)\\displaystyle\\ \\leq 4K\+4\\sqrt\{2L\}\\Bigl\(\\sum\_\{g\\in\\mathcal\{G\}\}\\sqrt\{\|g\|F\_\{g\}\}\+\\sqrt\{KR^\{\\prime\}\}\\Bigr\)≤4​K\+8​K​T​L,\\displaystyle\\ \\leq 4K\+8\\sqrt\{KTL\},whereFg=∑bfb,gF\_\{g\}=\\sum\_\{b\}f\_\{b,g\}is the group’s total floor andR′=T−∑gFgR^\{\\prime\}=T\-\\sum\_\{g\}F\_\{g\}the total surplus\. On the family of Proposition[8](https://arxiv.org/html/2607.22935#Thmtheorem8)the bound isO​\(L⋅B​H\)O\(\\sqrt\{L\}\\cdot B\\sqrt\{H\}\), matching the lower bound up toL\\sqrt\{L\}in every regime; with singleton groups it recovers Theorem[3](https://arxiv.org/html/2607.22935#Thmtheorem3), whose strong and plan\-matched comparators coincide\.

The price of plan adaptivity is thereforeΘ~​\(K​T\)\\widetilde\{\\Theta\}\(\\sqrt\{KT\}\)whenever the groups are disjoint, attained by a general algorithm rather than one tailored to the lower bound’s family, and with singleton groups it recovers the blockwise guarantee of Theorem[3](https://arxiv.org/html/2607.22935#Thmtheorem3)\. What remains genuinely open is the overlapping caset≥2t\\geq 2, where a single pull credits several groups at once and the per\-block optimum no longer decomposes across groups; there the one\-shot planner of Theorem[22](https://arxiv.org/html/2607.22935#Thmtheorem22)matches the lower bound only whenH=Θ​\(B\)H=\\Theta\(B\)\.

The obstruction is algorithm design, not accounting, and linear\-programming duality makes it precise: weak duality turns blockwise group\-fair regret into an exact per\-pull ledger whose two nonnegative columns charge suboptimal pulls and pulls that overshoot an already\-satisfied group \(Proposition[24](https://arxiv.org/html/2607.22935#Thmtheorem24)\)\. The disjoint covering rule controls both columns, but under overlap it provably fails, incurringΩ​\(T\)\\Omega\(T\)regret when one arm lies in two groups whose floors a single pull can discharge at once, a multi\-coverage value the dual prices encode but a within\-group index cannot see \(Proposition[25](https://arxiv.org/html/2607.22935#Thmtheorem25)\); any correct overlap algorithm must be LP\-aware\. Our plan\-sampling algorithm P\-BDQ\-UCB re\-solves the optimistic residual program after every pull and adds a terminal cover\-rounding guard that makes feasibility pathwise under an initial cover\-slack condition; under two explicit one\-step descent inequalities, which hold automatically on disjoint systems, it attainsO~​\(K​T\)\+O~​\(B​\(1/σ2\+K/σ\)\)\\widetilde\{O\}\(\\sqrt\{KT\}\)\+\\widetilde\{O\}\(B\(1/\\sigma^\{2\}\+K/\\sigma\)\)against the fractional optimum\. Removing that descent condition for arbitrary overlap is the paper’s one open problem\. The ledger, the algorithm, the guard, the descent condition, and the conditional theorem are developed in full in Appendix[F](https://arxiv.org/html/2607.22935#A6)\.

## Experiments

The experiments validate three claims on synthetic and semi\-real data: exact feasibility by construction, theRR\-parametrized regret envelope, and the advantage of parameter\-free quota construction over penalty\-based methods\. Every reported run lies below the explicit regret cap of Theorem[3](https://arxiv.org/html/2607.22935#Thmtheorem3)\(a loose sanity check, not a rate verification; all runs useη=1/T\\eta=1/T\), while the rate evidence is the normalized\-regret trend of Figure[8](https://arxiv.org/html/2607.22935#A9.F8)in the appendix\.

The static single\-floor case is a clean rederivation; its experiments are in Appendix[C\.4](https://arxiv.org/html/2607.22935#A3.SS4)\(Table[4](https://arxiv.org/html/2607.22935#A3.T4), Figure[2](https://arxiv.org/html/2607.22935#A3.F2)\), where DQ\-UCB meets the floor at every horizon inside theO​\(K​T​log⁡T\)O\(\\sqrt\{KT\\log T\}\)envelope while every floor\-feasible Lagrangian penalty incurs strictly positive regret\. The main text focuses on the blockwise and group settings\.

Table 1:Synthetic blockwise quotas \(K=6K\{=\}6,B=12B\{=\}12,H=600H\{=\}600,1616seeds\)\. Block violation==total missing mandatory pulls; min margin==smallestNb,i−mb,iN\_\{b,i\}\-m\_\{b,i\}; s\.e\.m\.==standard error of the mean\. Only BDQ\-UCB, BDQ\-MOSS, and theλ≥2\\lambda\\geq 2Lagrangian are blockwise feasible; see text\. Semi\-real MovieLens\-100k counterpart: Table[11](https://arxiv.org/html/2607.22935#A8.T11)\(Appendix[H](https://arxiv.org/html/2607.22935#A8)\)\.### Blockwise Time\-Varying Quotas

We useK=6K=6,B=12B=12blocks, block lengthH=600H=600, and Bernoulli means\(0\.70,0\.57,0\.53,0\.49,0\.45,0\.41\)\(0\.70,0\.57,0\.53,0\.49,0\.45,0\.41\)\. Each block has a nonuniform rotating floor: every arm receives a base quota of0\.03​H0\.03H; one nonbest arm receives an additional0\.17​H0\.17H; another receives an additional0\.07​H0\.07H\. The deadline\-aware Lagrangian baseline selects, at each round of blockbb, the arm maximizing the UCB index plusλ​\(mb,i−Nb,i​\(t\)\)\+/\(Hb−τb​\(t\)\+1\)\\lambda\\,\(m\_\{b,i\}\-N\_\{b,i\}\(t\)\)\_\{\+\}/\(H\_\{b\}\-\\tau\_\{b\}\(t\)\+1\), whereNb,i​\(t\)N\_\{b,i\}\(t\)is the pull count of armiiinside the current block andτb​\(t\)\\tau\_\{b\}\(t\)is the round’s position within the block, so the penalty scales the remaining per\-arm deficit by the block’s remaining rounds\. Table[1](https://arxiv.org/html/2607.22935#Sx7.T1)compares BDQ\-UCB with a global\-quota method that satisfies only the aggregate floor and with this Lagrangian \(block violation counts the total missing mandatory pulls\); Figure[4](https://arxiv.org/html/2607.22935#A8.F4)in Appendix[H](https://arxiv.org/html/2607.22935#A8)visualizes the same comparison\.

The blockwise experiment shows the modeling difference and the value of parameter\-free feasibility\. The global guaranteed\-pull method meets aggregate exposure but violates the block constraints by21742174pulls, so its low apparent regret is an artifact of infeasibility\. A deadline\-aware Lagrangian, once its penalty is large enough, is both feasible and competitive with BDQ\-UCB on regret; we do not claim BDQ\-UCB dominates it\. BDQ\-UCB’s advantage is that exact blockwise feasibility holds deterministically on every instance with no penalty to tune, whereas the Lagrangian’s feasibility depends on a per\-instance penalty search, with small penalties still violating the floor\. We tested the regret claim directly: a sweep over the mandatory fraction found*no*regime where BDQ\-UCB strictly beats the best feasible penalty, the tuned penalty being modestly ahead with the gap shrinking as the floor tightens \(Table[6](https://arxiv.org/html/2607.22935#A8.T6), Appendix[H](https://arxiv.org/html/2607.22935#A8)\)\. The contribution is parameter\-free exact feasibility, not a regret advantage\. The remaining two rows are consistent: BDQ\-MOSS is exactly feasible but pays a premium for discarding mandatory observations, and a virtual\-queue pacing baseline in the style ofLiet al\.\([2019](https://arxiv.org/html/2607.22935#bib.bib28)\)is feasible only at its most conservative settingV=1V=1at much higher regret, itsVV\-sweep lowering regret only by breaking feasibility, the same tuning trap as the Lagrangian\.

### Semi\-Real MovieLens Genre Benchmark

We instantiate one semi\-real benchmark based on MovieLens\-100k\(Harper and Konstan[2015](https://arxiv.org/html/2607.22935#bib.bib23)\)genre exposure\. Arms are theK=18K=18high\-level genre providers, each with a reward meanμ^i\\widehat\{\\mu\}\_\{i\}estimated from historical ratings \(protocol in Appendix[H\.1](https://arxiv.org/html/2607.22935#A8.SS1)\)\. Blocks represent recommendation periods \(B=12B=12,H=600H=600\); a rotating contract elevates one or two genres per block for higher minimum exposure while the rest receive a small base floor\. Each method is run with Bernoulli rewards calibrated byμ^i\\widehat\{\\mu\}\_\{i\}, and the comparator is the best blockwise\-fair allocation under those calibrated means \(1616seeds\): the genre means are real, the reward draws calibrated Bernoulli\. Results appear in Table[11](https://arxiv.org/html/2607.22935#A8.T11)\(Appendix[H](https://arxiv.org/html/2607.22935#A8)\) and match the synthetic pattern\.

To drop the calibrated\-Bernoulli assumption entirely, we rerun theK=18K\{=\}18MovieLens benchmark with rewards drawn non\-parametrically from each genre’s*actual*empirical rating distribution: at each pull of genreiiwe sample a real observed normalized rating, making the reward process the true one rather than a two\-point calibration \(1616seeds\)\. The picture is unchanged: BDQ\-UCB is exactly feasible \(0block violation\) at blockwise regret102\.4±1\.3102\.4\\pm 1\.3, the small penaltyλ=0\.5\\lambda\{=\}0\.5violates the floors \(34\.634\.6missing pulls\), and the feasible penaltiesλ∈\{2,8\}\\lambda\\in\\\{2,8\\\}tie it on regret \(101\.6101\.6–101\.8101\.8; Table[7](https://arxiv.org/html/2607.22935#A8.T7), Appendix[H](https://arxiv.org/html/2607.22935#A8)\)\. Exact feasibility and the feasible\-Lagrangian pattern therefore hold under the real reward distribution, not only calibrated draws\.

### Stress Test: Penalty Tuning at Scale

The blockwise table above exhibits the tuning problem on two instances \(λ=0\.5\\lambda=0\.5violates,λ≥2\\lambda\\geq 2is feasible\); the stronger claim is that no single penalty works*across*instances\. A2424\-instance battery \(arm countsK∈\{18,64,256\}K\\in\\\{18,64,256\\\}, three gap scales, three floor tightnesses, heterogeneous block lengths;1616seeds each\) confirms it: over the gridλ∈\{0\.25,…,32\}\\lambda\\in\\\{0\.25,\\dots,32\\\}feasibility climbs monotonically \(3,4,6,8,9,16,18,223,4,6,8,9,16,18,22of2424\) but no bounded penalty clears more than22/2422/24, the smallest feasibleλ\\lambdaspans a128×128\\timesrange, and two tight small\-gap large\-KKinstances admit no feasibleλ≤32\\lambda\\leq 32\. Only theλ→∞\\lambda\\to\\inftyhard schedule and BDQ\-UCB reach all2424\(regret59\.059\.0and58\.558\.5\); on the oracle\-feasible subset the tuned per\-instance oracle edges BDQ\-UCB on regret \(60\.660\.6vs61\.361\.3\) at the cost of a192192\-run sweep, so the advantage is again tuning\-free exact feasibility, not lower regret\. Full setup, Table[12](https://arxiv.org/html/2607.22935#A8.T12), and Figures[5](https://arxiv.org/html/2607.22935#A8.F5)and[7](https://arxiv.org/html/2607.22935#A8.F7)are in Appendix[H](https://arxiv.org/html/2607.22935#A8)\.

A group\-floor arm exercises the planning layer on real structure: the5454MovieLens genre×\\timespopularity cells \(1818genres×\\times33tiers\), with the1818genre unions and33tier unions as overlapping groups \(arm degreet=2t=2\)\. Learning the plan pays: OG\-BDQ\-UCB improves on the fixed\-plan Group\-BDQ\-UCB by about8%8\\%\(10831083vs11741174against the per\-block fractional optimum\), while a tuned group\-Lagrangian is again lower\-regret when feasible; the mild overlap keeps all three feasible, so this instance isolates the value of*learning*the plan rather than the Beck–Fiala necessity of the adversarial construction\. A disjoint control \(genre\-only floors,t=1t=1\) runs D\-BDQ\-UCB, exactly feasible with no rounding as Theorem[9](https://arxiv.org/html/2607.22935#Thmtheorem9)predicts; a scaling sweep on the lower\-bound family of Proposition[8](https://arxiv.org/html/2607.22935#Thmtheorem8)confirms its sharpest prediction, D\-BDQ\-UCB’s normalized regret staying flat while the one\-shot planner’s grows and is2\.5×2\.5\\timeslarger in the block\-sparse regime \(Table[10](https://arxiv.org/html/2607.22935#A8.T10), Figure[6](https://arxiv.org/html/2607.22935#A8.F6), Appendix[H](https://arxiv.org/html/2607.22935#A8)\)\.

### Deployment\-Facing Stress Tests

Six further studies \(Appendix[H](https://arxiv.org/html/2607.22935#A8), Table[9](https://arxiv.org/html/2607.22935#A8.T9)\), all over1616seeds and reusing the same primitives, stress deployment\-relevant axes: off\-policy value recovery \(N1\), overlapping group floors \(N2\), an adaptively tuned online penalty \(N3\), a LinUCB contextual layer \(N4\), delayed feedback \(N5\), and a mandatory\-sample placement ablation \(N6\)\. Because feasibility is a scheduling property it survives every one, with only regret ever degrading: the off\-policy value is recovered to within0\.0020\.002mean absolute error by IPS, SNIPS, and doubly\-robust estimators, a group\-blind policy misses group floors by34\.334\.3pulls per block where group\-aware rounding stays exact, and even the adaptively tuned online penalty still pays1\.251\.25block violations while it ramps up\.

## Conclusion

We treated fair exposure as rounding: the gap between a fractional fair schedule and an integral pull sequence is a discrepancy vector, feasibility is its control, and reward loss its weighted form\. This single identity organizes the paper\. It recovers the static Fair\-MAB guarantee from rounding alone, but pays off in the blockwise model, where BDQ\-UCB meets every period’s floor deterministically and incurs regret only on the nonmandatory budgetRR, the right complexity parameter in both the minimax \(Θ​\(K​R\)\\Theta\(\\sqrt\{KR\}\)\) and instance\-dependent senses\. Under overlap, Beck–Fiala null\-space rounding meets every group floor within the block budget where per\-arm rounding fails, and learning the plan exposes a new lower bound, settled atΘ~​\(K​T\)\\widetilde\{\\Theta\}\(\\sqrt\{KT\}\)for disjoint systems and attained conditionally under overlap\. Experiments on synthetic, MovieLens, and deployment settings confirm exact feasibility without penalty tuning; the overlapping learned\-plan rate without our descent condition is the main open problem, with adversarially adaptive floors and matroid\-like feasibility systems the natural next targets for this discrepancy bridge\.

## References

- S\. Agrawal and N\. R\. Devanur \(2014\)Bandits with Concave Rewards and Convex Knapsacks\.InProceedings of the 15th ACM Conference on Economics and Computation \(EC\),pp\. 989–1006\.Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p2.1)\.
- D\. J\. Altschuler and K\. Tikhomirov \(2025\)A threshold for online balancing of sparse i\.i\.d\. vectors\.Note:arXiv:2509\.02432Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p3.1)\.
- J\. Audibert and S\. Bubeck \(2009\)Minimax Policies for Adversarial and Stochastic Bandits\.InProceedings of the 22nd Annual Conference on Learning Theory \(COLT\),Cited by:[§D\.1](https://arxiv.org/html/2607.22935#A4.SS1.1.p1.4),[§D\.1](https://arxiv.org/html/2607.22935#A4.SS1.p1.4),[§I\.16](https://arxiv.org/html/2607.22935#A9.SS16.2.p2.24),[Related Work](https://arxiv.org/html/2607.22935#Sx2.p3.1),[Lower Bounds and the Optimal Rate](https://arxiv.org/html/2607.22935#Sx4.SSx2.p2.4)\.
- P\. Auer, N\. Cesa\-Bianchi, and P\. Fischer \(2002\)Finite\-time analysis of the multiarmed bandit problem\.Machine Learning47\(2–3\),pp\. 235–256\.Cited by:[§C\.2](https://arxiv.org/html/2607.22935#A3.SS2.p2.4),[Related Work](https://arxiv.org/html/2607.22935#Sx2.p3.1)\.
- A\. Badanidiyuru, R\. Kleinberg, and A\. Slivkins \(2013\)Bandits with Knapsacks\.InProceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science \(FOCS\),pp\. 207–216\.Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p2.1)\.
- S\. R\. Balseiro, H\. Lu, and V\. Mirrokni \(2020\)Dual Mirror Descent for Online Allocation Problems\.InProceedings of the 37th International Conference on Machine Learning \(ICML\),pp\. 613–628\.Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p2.1)\.
- W\. Banaszczyk \(1998\)Balancing vectors and Gaussian measures ofnn\-dimensional convex bodies\.Random Structures & Algorithms12\(4\),pp\. 351–360\.Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p3.1)\.
- N\. Bansal, H\. Jiang, S\. Singla, and M\. Sinha \(2020\)Online Vector Balancing and Geometric Discrepancy\.InProceedings of the 52nd Annual ACM Symposium on Theory of Computing \(STOC\),pp\. 1139–1152\.Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p3.1)\.
- N\. Bansal and V\. Nagarajan \(2016\)Approximation\-Friendly Discrepancy Rounding\.InProceedings of the 27th Annual ACM\-SIAM Symposium on Discrete Algorithms \(SODA\),pp\. 2012–2031\.Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p3.1)\.
- N\. Bansal \(2010\)Constructive algorithms for discrepancy minimization\.InProceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science \(FOCS\),pp\. 3–10\.Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p3.1)\.
- S\. Barman, A\. Khan, A\. Maiti, and A\. Sawarni \(2022\)Fairness and Welfare Quantification for Regret in Multi\-Armed Bandits\.InProceedings of the 36th AAAI Conference on Artificial Intelligence \(AAAI\),Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p1.1)\.
- J\. Beck and T\. Fiala \(1981\)“Integer\-making” theorems\.Discrete Applied Mathematics3\(1\),pp\. 1–8\.Cited by:[Overlapping Group Floors and Set\-Discrepancy Rounding](https://arxiv.org/html/2607.22935#Sx5.p2.4)\.
- W\. Bednorz and P\. Godlewski \(2024\)Some Remarks on the Gram\-Schmidt Walk Algorithm and Consequences for Komlós Conjecture\.Note:arXiv:2404\.03534Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p3.1)\.
- S\. Bubeck and N\. Cesa\-Bianchi \(2012\)Regret analysis of stochastic and nonstochastic multi\-armed bandit problems\.Foundations and Trends in Machine Learning5\(1\),pp\. 1–122\.Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p3.1)\.
- M\. N\. Cartier van Dissel, S\. Martin\-Gutierrez, L\. Espín\-Noboa, A\. M\. Jaramillo, and F\. Karimi \(2025\)hyperFA\*IR: A Hypergeometric Approach to Fair Rankings with Finite Candidate Pool\.Note:arXiv:2506\.14349Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p2.1)\.
- Y\. Chen, A\. Cuellar, H\. Luo, J\. Modi, H\. Nemlekar, and S\. Nikolaidis \(2020\)Fair contextual multi\-armed bandits: Theory and experiments\.InProceedings of the 36th Conference on Uncertainty in Artificial Intelligence \(UAI\),pp\. 181–190\.Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p2.1)\.
- H\. Claure, Y\. Chen, J\. Modi, M\. Jung, and S\. Nikolaidis \(2020\)Multi\-Armed Bandits with Fairness Constraints for Distributing Resources to Human Teammates\.InProceedings of the ACM/IEEE International Conference on Human\-Robot Interaction \(HRI\),pp\. 299–308\.Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p2.1)\.
- M\. Davoodi and S\. Maghsudi \(2025\)Stochastic Multi\-Objective Multi\-Armed Bandits: Regret Definition and Algorithm\.Note:arXiv:2506\.13125Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p3.1)\.
- R\. Gandhi, S\. Khuller, S\. Parthasarathy, and A\. Srinivasan \(2006\)Dependent rounding and its applications to approximation algorithms\.Journal of the ACM53\(3\),pp\. 324–360\.Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p3.1)\.
- Q\. Han, K\. Khamaru, and C\.\-H\. Zhang \(2024\)UCB Algorithms for Multi\-Armed Bandits: Precise Regret and Adaptive Inference\.Note:arXiv:2412\.06126Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p3.1)\.
- T\. Harada, S\. Ito, and H\. Sumita \(2025\)Bandit Max\-Min Fair Allocation\.Note:arXiv:2505\.05169Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p1.1)\.
- F\. M\. Harper and J\. A\. Konstan \(2015\)The MovieLens datasets: History and context\.ACM Transactions on Interactive Intelligent Systems5\(4\),pp\. 1–19\.Cited by:[Semi\-Real MovieLens Genre Benchmark](https://arxiv.org/html/2607.22935#Sx7.SSx2.p1.6)\.
- M\. Joseph, M\. Kearns, J\. H\. Morgenstern, and A\. Roth \(2016\)Fairness in learning: Classic and contextual bandits\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Vol\.29\.Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p1.1)\.
- R\. Krishnamurthy, A\. Agarwal, L\. Subramanian, and M\. Nickel \(2026\)Creator Incentives in Recommender Systems: A Cooperative Game\-Theoretic Approach for Stable and Fair Collaboration in Multi\-Agent Bandits\.Note:arXiv:2604\.08643Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p2.1)\.
- T\. Lattimore and C\. Szepesvári \(2020\)Bandit Algorithms\.Cambridge University Press\.Cited by:[§I\.16](https://arxiv.org/html/2607.22935#A9.SS16.2.p2.24),[§I\.4](https://arxiv.org/html/2607.22935#A9.SS4.1.p1.20),[Related Work](https://arxiv.org/html/2607.22935#Sx2.p3.1),[Learning the Group Plan](https://arxiv.org/html/2607.22935#Sx6.p3.1)\.
- M\. S\. A\. Lee, K\. Padh, D\. Watson, N\. Kilbertus, and J\. Singh \(2026\)Fairness under Uncertainty in Sequential Decisions\.Note:arXiv:2604\.21711Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p1.1)\.
- F\. Li, J\. Liu, and B\. Ji \(2019\)Combinatorial Sleeping Bandits with Fairness Constraints\.InIEEE Conference on Computer Communications \(INFOCOM\),pp\. 1702–1710\.Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p2.1),[Blockwise Time\-Varying Quotas](https://arxiv.org/html/2607.22935#Sx7.SSx1.p2.3)\.
- L\. Lyu and W\. C\. Cheung \(2023\)Online Resource Allocation: Bandits Feedback and Advice on Time\-Varying Demands\.Note:arXiv:2302\.04182Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p3.1)\.
- P\. Manupriya, Himanshu, S\. Jagarlapudi, and G\. Ghalme \(2025\)Multi\-agent Multi\-armed Bandits with Minimum Reward Guarantee Fairness\.Note:arXiv:2502\.15240Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p2.1)\.
- P\. Ménard and A\. Garivier \(2017\)A Minimax and Asymptotically Optimal Algorithm for Stochastic Bandits\.InProceedings of the 28th International Conference on Algorithmic Learning Theory \(ALT\),Cited by:[§I\.19](https://arxiv.org/html/2607.22935#A9.SS19.1.p1.17),[Related Work](https://arxiv.org/html/2607.22935#Sx2.p3.1),[Corollary 20](https://arxiv.org/html/2607.22935#Thmtheorem20.p1.4.4)\.
- V\. Patil, G\. Ghalme, V\. Nair, and Y\. Narahari \(2020\)Achieving fairness in the stochastic multi\-armed bandit problem\.InProceedings of the 34th AAAI Conference on Artificial Intelligence \(AAAI\),pp\. 5379–5386\.Cited by:[Introduction](https://arxiv.org/html/2607.22935#Sx1.p2.1),[Related Work](https://arxiv.org/html/2607.22935#Sx2.p1.1)\.
- V\. Patil, G\. Ghalme, V\. Nair, and Y\. Narahari \(2021\)Achieving fairness in the stochastic multi\-armed bandit problem\.Journal of Machine Learning Research22\(174\),pp\. 1–31\.Cited by:[§C\.4](https://arxiv.org/html/2607.22935#A3.SS4.p1.7),[Introduction](https://arxiv.org/html/2607.22935#Sx1.p2.1),[Related Work](https://arxiv.org/html/2607.22935#Sx2.p1.1),[Remark 13](https://arxiv.org/html/2607.22935#Thmtheorem13.p1.6.6)\.
- S\. Pokhriyal, S\. Jain, G\. Ghalme, S\. Dhamal, and S\. Gujar \(2024\)Simultaneously Achieving Group Exposure Fairness and Within\-Group Meritocracy in Stochastic Bandits\.Note:arXiv:2402\.05575Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p2.1)\.
- A\. R\. Shaarad and A\. Dukkipati \(2020\)A Regret Bound for Non\-Stationary Multi\-Armed Bandits with Fairness Constraints\.Note:arXiv:2012\.13380Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p2.1)\.
- J\. Spencer \(1985\)Six standard deviations suffice\.Transactions of the American Mathematical Society289\(2\),pp\. 679–706\.Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p3.1)\.
- M\. Tatlı, A\. Mukherjee, Prashanth L\. A\., K\. Shanmugam, and A\. Tajer \(2025a\)Preference\-centric Bandits: Optimality of Mixtures and Regret\-efficient Algorithms\.Note:arXiv:2504\.20877Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p3.1)\.
- M\. Tatlı, A\. Mukherjee, Prashanth L\. A\., K\. Shanmugam, and A\. Tajer \(2025b\)Risk\-sensitive Bandits: Arm Mixture Optimality and Regret\-efficient Algorithms\.Note:arXiv:2503\.08896Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p3.1)\.
- L\. Wang, Y\. Bai, W\. Sun, and T\. Joachims \(2021\)Fairness of Exposure in Stochastic Bandits\.Note:arXiv:2103\.02735Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p1.1)\.
- M\. Wilms and C\. Heitz \(2026\)Fairness vs Performance: Characterizing the Pareto Frontier of Algorithmic Decision Systems\.Note:arXiv:2605\.10604Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p1.1)\.
- T\. Xu, J\. Liu, N\. Mattei, and Z\. Zheng \(2025\)Fair Algorithms with Probing for Multi\-Agent Multi\-Armed Bandits\.Note:arXiv:2506\.14988Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p2.1)\.
- Q\. Zhou, J\. Marecek, and R\. Shorten \(2025\)Online Learning with Multiple Fairness Regularizers via Graph\-Structured Feedback\.Note:arXiv:2508\.14311Cited by:[Related Work](https://arxiv.org/html/2607.22935#Sx2.p2.1)\.

## Appendix ANotation

Table 2:Notation used throughout the paper\.
## Appendix BSummary of Results

Table[3](https://arxiv.org/html/2607.22935#A2.T3)collects the paper’s guarantees in one place, grouping each setting with its upper bound, matching lower bound, and the algorithm that attains the rate\. Reading down the table traces the paper’s arc: the residual budgetRRgoverns the blockwise settings and the horizonTTgoverns the learned\-plan settings, and in every row the upper and lower bounds match up to logarithmic factors except where noted\.

Table 3:Complexity picture across settings; upper and lower bounds match except where noted\. Herekli=kl​\(μi,μ⋆\)\\mathrm\{kl\}\_\{i\}=\\mathrm\{kl\}\(\\mu\_\{i\},\\mu\_\{\\star\}\)andRRis the nonmandatory budget\. Plan\-matched benchmarks execute the same mandatory schedule; learned\-plan benchmarks target the per\-block fractional group\-fair optimum\.†Conditional on the sampled\-plan descent condition and initial cover slack; feasibility of P\-BDQ\-UCB needs only the slack condition\.
## Appendix CStatic Exposure Floors and Pareto Frontier

### C\.1Static Setup: Floor, Best\-Fair Allocation, and the Fair\-Regret Identity

The static single\-floor objects specialized in the main text are as follows\.

###### Definition 2\(Integral fairness floor\)\.

For a target exposure fractionδ∈\[0,1/K\]\\delta\\in\[0,1/K\], define the integral floor

m=⌊δ​T⌋\.m=\\lfloor\\delta T\\rfloor\.A policy ismm\-fair if its final pull countsNi​\(T\)N\_\{i\}\(T\)satisfy

Ni​\(T\)≥mfor every​i∈\[K\]\.N\_\{i\}\(T\)\\geq m\\qquad\\text\{for every \}i\\in\[K\]\.Equivalently, the empirical exposure of every arm is at leastm/T≥δ−1/Tm/T\\geq\\delta\-1/T\. IfK​⌈δ​T⌉≤TK\\lceil\\delta T\\rceil\\leq T, one may replacem=⌊δ​T⌋m=\\lfloor\\delta T\\rfloorbym=⌈δ​T⌉m=\\lceil\\delta T\\rceileverywhere below to obtain the literal floorNi​\(T\)≥δ​TN\_\{i\}\(T\)\\geq\\delta T\.

The best fair allocation is the allocation that maximizes expected reward subject to the same integral floor\. Since all rewards are stationary and independent, the best fair allocation gives exactlymmpulls to every suboptimal arm and all remaining pulls to a best arm; a formal proof is in the appendix\.

###### Definition 3\(Best fair allocation and fair pseudo\-regret\)\.

Let

ni⋆​\(m\)=\{T−\(K−1\)​m,i=i⋆,m,i≠i⋆\.n\_\{i\}^\{\\star\}\(m\)=\\begin\{cases\}T\-\(K\-1\)m,&i=i^\{\\star\},\\\\ m,&i\\neq i^\{\\star\}\.\\end\{cases\}The value of the best fair allocation is

OPTm​\(T\)=∑i=1Kni⋆​\(m\)​μi=T​μ⋆−m​∑i≠i⋆Δi\.\\mathrm\{OPT\}\_\{m\}\(T\)=\\sum\_\{i=1\}^\{K\}n\_\{i\}^\{\\star\}\(m\)\\mu\_\{i\}=T\\mu\_\{\\star\}\-m\\sum\_\{i\\neq i^\{\\star\}\}\\Delta\_\{i\}\.For a policyπ\\pi, its fair pseudo\-regret is

Regmπ​\(T\)=OPTm​\(T\)−𝔼π​\[∑t=1TμAt\],\\mathrm\{Reg\}\_\{m\}^\{\\pi\}\(T\)=\\mathrm\{OPT\}\_\{m\}\(T\)\-\\mathbb\{E\}\_\{\\pi\}\\\!\\left\[\\sum\_\{t=1\}^\{T\}\\mu\_\{A\_\{t\}\}\\right\],whereAtA\_\{t\}is the arm pulled at timett\. The realized fair pseudo\-regret is

Reg^mπ​\(T\)=OPTm​\(T\)−∑t=1TμAt\.\\widehat\{\\mathrm\{Reg\}\}\_\{m\}^\{\\pi\}\(T\)=\\mathrm\{OPT\}\_\{m\}\(T\)\-\\sum\_\{t=1\}^\{T\}\\mu\_\{A\_\{t\}\}\.

###### Lemma 10\(Fair\-regret identity\)\.

For every pull sequenceA1,…,ATA\_\{1\},\\dots,A\_\{T\},

Reg^m​\(T\)=∑i≠i⋆Δi​\(Ni​\(T\)−m\)\.\\widehat\{\\mathrm\{Reg\}\}\_\{m\}\(T\)=\\sum\_\{i\\neq i^\{\\star\}\}\\Delta\_\{i\}\\bigl\(N\_\{i\}\(T\)\-m\\bigr\)\.Consequently, if the policy ismm\-fair, thenReg^m​\(T\)≥0\\widehat\{\\mathrm\{Reg\}\}\_\{m\}\(T\)\\geq 0\.

### C\.2DQ\-UCB Algorithm and Guarantees

The mandatory part of a fair bandit schedule requiresmmpulls of every arm, and the following elementary discrepancy construction gives an integral schedule with exactly those counts and uniformly small prefix imbalance\.

###### Lemma 11\(Balanced quota rounding\)\.

Consider the length\-K​mKmsequence that pulls arms cyclically,

1,2,…,K,1,2,…,K,…,1,2,…,K,1,2,\\dots,K,\\;1,2,\\dots,K,\\;\\ldots,\\;1,2,\\dots,K,with exactlymmfull cycles, and letNi​\(t\)N\_\{i\}\(t\)be the number of pulls of armiiamong the firstt≤K​mt\\leq Kmpulls\. ThenNi​\(K​m\)=mN\_\{i\}\(Km\)=mfor everyii, and for every prefixt≤K​mt\\leq Km,

\|Ni​\(t\)−tK\|≤1for every​i\.\\left\|N\_\{i\}\(t\)\-\\frac\{t\}\{K\}\\right\|\\leq 1\\qquad\\text\{for every \}i\.

Lemma[11](https://arxiv.org/html/2607.22935#Thmtheorem11)is a constructive discrepancy bound: the integral sequence has exact terminal quota and at most one unit of prefix discrepancy relative to the uniform fractional quota schedule\. DQ\-UCB builds on it in two phases\. The discrepancy quota phase uses the balanced schedule to pull every arm exactlymmtimes, enforcing the fairness floor deterministically\. The optimistic residual phase then runs UCB\(Aueret al\.[2002](https://arxiv.org/html/2607.22935#bib.bib5)\)on the remainingT−K​mT\-Kmpulls; since the quota is already satisfied, this phase can focus purely on reward learning\. Whenm=0m=0the fairness constraint is vacuous, and the algorithm pulls each arm once for initialization before running UCB; we assumeT≥KT\\geq Kin that case\. Pseudocode is given as Algorithm[2](https://arxiv.org/html/2607.22935#alg2), with ties in the index broken toward the lowest arm index\.

Algorithm 2DQ\-UCB1:Input:arms

KK, horizon

TT, floor

m∈\{0,…,⌊T/K⌋\}m\\in\\\{0,\\dots,\\lfloor T/K\\rfloor\\\}, failure prob\.

η∈\(0,1\)\\eta\\in\(0,1\)
2:Output:pull sequence

A1,…,ATA\_\{1\},\\dots,A\_\{T\}
3:

s←max⁡\(m,1\)s\\leftarrow\\max\(m,\\,1\);

L←log⁡\(2​K​T/η\)L\\leftarrow\\log\(2KT/\\eta\)
4:for

j=1,…,sj=1,\\dots,sdo

5:for

i=1,…,Ki=1,\\dots,Kdo

6:Pull arm

ii
7:endfor

8:endfor

9:for

t=K​s\+1,…,Tt=Ks\+1,\\dots,Tdo

10:Pull

At∈arg​maxi∈\[K\]⁡\{μ^i​\(t\)\+2​L/Ni​\(t\)\}A\_\{t\}\\in\\displaystyle\\operatorname\*\{arg\\,max\}\_\{i\\in\[K\]\}\\\!\\left\\\{\\widehat\{\\mu\}\_\{i\}\(t\)\+\\sqrt\{2L/N\_\{i\}\(t\)\}\\right\\\}
11:endfor

###### Theorem 12\(Exact fairness and fair regret\)\.

Assume rewards are independent and supported in\[0,1\]\[0,1\]\. Letm∈\{0,1,…,⌊T/K⌋\}m\\in\\\{0,1,\\dots,\\lfloor T/K\\rfloor\\\}, and ifm=0m=0assumeT≥KT\\geq K\. Then DQ\-UCB satisfies the following\.

1. \(i\)*Exact fairness\.*Deterministically, Ni​\(T\)≥mfor every​i∈\[K\]\.N\_\{i\}\(T\)\\geq m\\qquad\\text\{for every \}i\\in\[K\]\.
2. \(ii\)*Gap\-dependent high\-probability bound\.*With probability at least1−η1\-\\eta, Reg^m​\(T\)\\displaystyle\\widehat\{\\mathrm\{Reg\}\}\_\{m\}\(T\)≤K\+∑i:Δi\>0min⁡\{T​Δi,8​LΔi\},\\displaystyle\\leq K\+\\sum\_\{i:\\Delta\_\{i\}\>0\}\\min\\left\\\{T\\Delta\_\{i\},\\,\\frac\{8L\}\{\\Delta\_\{i\}\}\\right\\\},L=log⁡\(2​K​Tη\)\.\\displaystyle\\qquad L=\\log\\\!\\left\(\\frac\{2KT\}\{\\eta\}\\right\)\.\(2\)
3. \(iii\)*Gap\-free high\-probability bound\.*With probability at least1−η1\-\\eta, Reg^m​\(T\)≤K\+4​2​K​T​L\.\\widehat\{\\mathrm\{Reg\}\}\_\{m\}\(T\)\\leq K\+4\\sqrt\{2KTL\}\.
4. \(iv\)*Expected regret\.*Takingη=1/T\\eta=1/T, Regm​\(T\)=O​\(K​T​log⁡\(K​T\)\+K\)\.\\mathrm\{Reg\}\_\{m\}\(T\)=O\\\!\\left\(\\sqrt\{KT\\log\(KT\)\}\+K\\right\)\.

###### Proof sketch\.

Fairness is deterministic: the quota phase pulls every arm exactlymmtimes\. For regret, the standard UCB concentration eventℰ\\mathcal\{E\}\(Hoeffding’s inequality, union bound overK​TKTpairs\) holds with probability1−η1\-\\eta\. Onℰ\\mathcal\{E\}, any suboptimal armiiwith gapΔi\\Delta\_\{i\}can be selected at most1\+8​L/Δi21\+8L/\\Delta\_\{i\}^\{2\}times during the residual phase\. Summing via Lemma[10](https://arxiv.org/html/2607.22935#Thmtheorem10)gives the gap\-dependent bound; anε\\varepsilon\-split optimized atε=8​K​L/T\\varepsilon=\\sqrt\{8KL/T\}gives the gap\-free bound\. The full proof is in Appendix[I\.12](https://arxiv.org/html/2607.22935#A9.SS12)\. ∎

###### Corollary 14\(Realized reward regret\)\.

LetRT=∑t=1TXAtR\_\{T\}=\\sum\_\{t=1\}^\{T\}X\_\{A\_\{t\}\}be the realized reward\. With probability at least1−2​η1\-2\\eta,

OPTm​\(T\)−RT≤K\+4​2​K​T​log⁡\(2​K​T/η\)\+2​T​log⁡\(1/η\)\.\\mathrm\{OPT\}\_\{m\}\(T\)\-R\_\{T\}\\leq K\+4\\sqrt\{2KT\\log\(2KT/\\eta\)\}\+\\sqrt\{2T\\log\(1/\\eta\)\}\.

### C\.3Fairness–Regret Pareto Frontier

The tradeoff between the floor level and achievable reward is a property of the underlying allocation problem, independent of the learning algorithm, and it admits a closed form\. For a probability vectorp∈ℝKp\\in\\mathbb\{R\}^\{K\}\(pi≥0p\_\{i\}\\geq 0,∑ipi=1\\sum\_\{i\}p\_\{i\}=1\), define the fairness levelϕ​\(p\)=mini⁡pi\\phi\(p\)=\\min\_\{i\}p\_\{i\}and the expected rewardV​\(p\)=∑ipi​μiV\(p\)=\\sum\_\{i\}p\_\{i\}\\mu\_\{i\}; an allocationpp*dominates*qqifϕ​\(p\)≥ϕ​\(q\)\\phi\(p\)\\geq\\phi\(q\)andV​\(p\)≥V​\(q\)V\(p\)\\geq V\(q\)with at least one strict inequality\.

###### Theorem 15\(Closed\-form static Pareto frontier\)\.

Assume the best armi⋆i^\{\\star\}is unique\. For every fairness levelβ∈\[0,1/K\]\\beta\\in\[0,1/K\], define

piβ=\{1−\(K−1\)​β,i=i⋆,β,i≠i⋆\.p\_\{i\}^\{\\beta\}=\\begin\{cases\}1\-\(K\-1\)\\beta,&i=i^\{\\star\},\\\\ \\beta,&i\\neq i^\{\\star\}\.\\end\{cases\}Then the Pareto frontier is exactly the curve\{\(ϕ​\(pβ\),V​\(pβ\)\):β∈\[0,1/K\]\}\\\{\(\\phi\(p^\{\\beta\}\),V\(p^\{\\beta\}\)\):\\beta\\in\[0,1/K\]\\\}\. Moreoverϕ​\(pβ\)=β\\phi\(p^\{\\beta\}\)=\\betaand

V​\(pβ\)=μ⋆−β​∑i≠i⋆Δi,V\(p^\{\\beta\}\)=\\mu\_\{\\star\}\-\\beta\\sum\_\{i\\neq i^\{\\star\}\}\\Delta\_\{i\},so the unconstrained regret per round at fairness levelβ\\betaisβ​∑i≠i⋆Δi\\beta\\sum\_\{i\\neq i^\{\\star\}\}\\Delta\_\{i\}\.

###### Corollary 16\(Algorithmic approach to the frontier\)\.

For any integral floormm, DQ\-UCB targets the pointβ=m/T\\beta=m/Ton the Pareto frontier; by Theorem[12](https://arxiv.org/html/2607.22935#Thmtheorem12), its per\-round reward gap relative toV​\(pm/T\)=μ⋆−\(m/T\)​∑i≠i⋆ΔiV\(p^\{m/T\}\)=\\mu\_\{\\star\}\-\(m/T\)\\sum\_\{i\\neq i^\{\\star\}\}\\Delta\_\{i\}vanishes at rateO​\(K​log⁡\(K​T\)/T\)O\(\\sqrt\{K\\log\(KT\)/T\}\)\.

### C\.4Static Experiments

We evaluate the exact DQ\-UCB policy: a deterministic round\-robin quota ofm=⌊δ​T⌋m=\\lfloor\\delta T\\rfloorpulls per arm, followed by pure UCB on the residual budget\. Because the quota phase meets the floor deterministically, realized fair regret is always nonnegative, and no slack convention or terminal repair is needed\. All static experiments use synthetic Bernoulli fair\-bandit instances on CPU, reporting means over1616seeds; the comparator is the best fair allocation \(mmpulls on every arm and the remaining budget on the best arm\), and the baseline is the Lagrangian\-penalty policy that selects the arm maximizing the UCB index plusλ​\(δ−Ni​\(t\)/t\)\\lambda\(\\delta\-N\_\{i\}\(t\)/t\), swept overλ∈\{0\.5,2,8\}\\lambda\\in\\\{0\.5,2,8\\\}\. We report fair pseudo\-regretReg^m​\(T\)\\widehat\{\\mathrm\{Reg\}\}\_\{m\}\(T\)and the realized minimum exposure fractionmini⁡Ni​\(T\)/T\\min\_\{i\}N\_\{i\}\(T\)/T\. We also ran the Fair\-MAB algorithm ofPatilet al\.\([2021](https://arxiv.org/html/2607.22935#bib.bib32)\)on the same instances: it is anytime\-feasible throughout and statistically ties DQ\-UCB, with both at approximately zero fair regret on these easy instances, consistent with Remark[13](https://arxiv.org/html/2607.22935#Thmtheorem13); we report it in prose rather than as additional table rows\.

The first experiment \(E1\) fixesK=5K=5andδ=0\.1\\delta=0\.1and varies the horizon; Table[4](https://arxiv.org/html/2607.22935#A3.T4)\(a\) reports fair regret against the best\-fair oracle and the realized minimum exposure, and Figure[8](https://arxiv.org/html/2607.22935#A9.F8)in the appendix shows the trend across horizons\. The second \(E2\) fixesK=5K=5andT=3\.2×104T=3\.2\\times 10^\{4\}and sweeps the floorδ\\delta; Table[4](https://arxiv.org/html/2607.22935#A3.T4)\(b\) and Figure[2](https://arxiv.org/html/2607.22935#A3.F2)report the resulting frontier, where the best feasible Lagrangian is the lowest\-regret penalty setting that still meets the floor\. The zero\-regret entries for DQ\-UCB mean that on this particular instance the residual UCB phase matched the best fair comparator after the mandatory quota was satisfied \(aftermmquota samples per arm, the best arm’s index remains above every suboptimal index for the rest of the horizon\) and should be read as an easy\-instance diagnostic rather than a universal theorem\. The third \(E3\) fixesT=3\.2×104T=3\.2\\times 10^\{4\}andδ=0\.1\\delta=0\.1and variesKKand the reward\-gap structure \(Table[4](https://arxiv.org/html/2607.22935#A3.T4)\(c\)\)\. TheK=10K=10rows report zero fair regret becauseδ=1/K\\delta=1/KatK=10K=10: the floorm=⌊δ​T⌋m=\\lfloor\\delta T\\rfloormakes the mandatory quotaK​m=TKm=Texhaust the horizon, leaving residual budgetR=0R=0, so no optimistic phase runs and the allocation coincides with the best fair comparator\. TheK=5K=5rows haveR=T−K​m=12​T\>0R=T\-Km=\\tfrac\{1\}\{2\}T\>0, and the hard instance \(gap0\.050\.05\) accrues the largest normalized regret, still within theO​\(K​T​log⁡T\)O\(\\sqrt\{KT\\log T\}\)envelope\.

![Refer to caption](https://arxiv.org/html/2607.22935v1/x2.png)Figure 2:E2: Fairness–regret Pareto frontier \(K=5K=5,T=3\.2×104T=3\.2\\times 10^\{4\}\)\. DQ\-UCB achieves zero fair regret at every floor levelδ\\deltaon this instance; the best feasible Lagrangian incurs positive regret ranging from21262126atδ=0\.05\\delta=0\.05to26\.826\.8atδ=0\.18\\delta=0\.18\.\(a\) E1: Fair regret vs\. horizon \(K=5K=5,δ=0\.1\\delta=0\.1\)

\(b\) E2: Fairness–regret frontier \(K=5K=5,T=3\.2×104T=3\.2\\times 10^\{4\}\)

\(c\) E3: Robustness \(T=3\.2×104T=3\.2\\times 10^\{4\},δ=0\.1\\delta=0\.1\)

Table 4:Static DQ\-UCB experiments \(1616seeds; s\.e\.m\. denotes the standard error of the mean\)\. \(a\) Floor met at every horizon; fair regret per round diminishes to zero byT=8,000T=8\{,\}000, where the exact zeros arise because, after themmquota samples per arm, the best arm’s index remains above every suboptimal index for the remainder of the horizon on this instance\. \(b\) At everyδ\>0\\delta\>0, DQ\-UCB attains zero fair regret on this instance \(an easy\-instance diagnostic, not a universal claim\) while all floor\-feasible Lagrangian settings incur positive regret\. \(c\) Floor met at all\(K,gap\)\(K,\\text\{gap\}\); the largest normalized regret stays within theO​\(K​T​log⁡T\)O\(\\sqrt\{KT\\log T\}\)envelope\.

## Appendix DAdditional Blockwise Complexity Results

### D\.1BDQ\-MOSS: Closing the Minimax Rate

Replace the residual selection rule of BDQ\-UCB by the MOSS index ofAudibert and Bubeck \([2009](https://arxiv.org/html/2607.22935#bib.bib2)\), computed on residual observations only: writingNiresN^\{\\mathrm\{res\}\}\_\{i\}andμ^ires\\widehat\{\\mu\}^\{\\mathrm\{res\}\}\_\{i\}for the pull count and empirical mean of armiiover residual rounds alone, the rule pulls each arm once during the firstKKresidual rounds and thereafter selects

arg​maxi∈\[K\]⁡\{μ^ires\+max⁡\(log⁡\(R/\(K​Nires\)\),0\)Nires\}\.\\operatorname\*\{arg\\,max\}\_\{i\\in\[K\]\}\\left\\\{\\widehat\{\\mu\}^\{\\mathrm\{res\}\}\_\{i\}\+\\sqrt\{\\frac\{\\max\\bigl\(\\log\\bigl\(R/\(KN^\{\\mathrm\{res\}\}\_\{i\}\)\\bigr\),\\,0\\bigr\)\}\{N^\{\\mathrm\{res\}\}\_\{i\}\}\}\\right\\\}\.We call the resulting algorithm BDQ\-MOSS\.

###### Theorem 17\(BDQ\-MOSS closes the minimax rate\)\.

BDQ\-MOSS satisfies the deterministic blockwise fairness guarantee of Theorem[3](https://arxiv.org/html/2607.22935#Thmtheorem3)\(i\), and its expected blockwise fair regret satisfies

Reg𝐦​\(T\)≤C​K​R\+K\\mathrm\{Reg\}\_\{\\mathbf\{m\}\}\(T\)\\ \\leq\\ C\\sqrt\{KR\}\+Kfor a universal constantCC\. Combined with Theorem[4](https://arxiv.org/html/2607.22935#Thmtheorem4), the minimax blockwise fair regret isΘ​\(K​R\)\\Theta\(\\sqrt\{KR\}\)forR≥KR\\geq K, and BDQ\-MOSS attains it up to a universal constant\.

###### Proof idea\.

Because the residual rule reads only residual history, theRRresidual rounds form a standardKK\-armed bandit played by MOSS; by Lemma[2](https://arxiv.org/html/2607.22935#Thmtheorem2)the fair regret equals that embedded pseudo\-regret, which MOSS bounds byC​K​RC\\sqrt\{KR\}\(Audibert and Bubeck[2009](https://arxiv.org/html/2607.22935#bib.bib2)\)\. A doubling trick handles unknownRR\(Appendix[I\.16](https://arxiv.org/html/2607.22935#A9.SS16)\)\. ∎

### D\.2Positive Mandatory Exposure and Instance\-Dependent Rates

The zero\-floor reduction invites the objection that the lower bound says nothing about instances with genuine mandatory exposure\. It does, once the mandatory mass is placed carefully\.

###### Proposition 18\(Positive mandatory exposure does not remove the residual lower bound\)\.

For everyK≥2K\\geq 2,R≥KR\\geq K, and any integer mandatory budgetM≥0M\\geq 0, there is a blockwise\-fair instance with total mandatory exposureMMand total residual budgetRRon which every blockwise\-fair policy suffers minimax fair regretΩ​\(K​R\)\\Omega\(\\sqrt\{KR\}\)\.

The construction, given in full in Appendix[I\.17](https://arxiv.org/html/2607.22935#A9.SS17), places the entire mandatory mass on a reference arm whose reward distribution is identical across all instances in the lower\-bound family: a first block of lengthMMcarries the floor vector\(M,0,…,0\)\(M,0,\\ldots,0\), and arm11is Bernoulli\(1/2\)\(1/2\)under every instance while the alternatives shift only one of the remaining arms\. The forced pulls of arm11then carry no information \(they contribute zero KL divergence between instances\) and are matched by the comparator, so by Lemma[2](https://arxiv.org/html/2607.22935#Thmtheorem2)they cancel from fair regret; the residual block of lengthRRreproduces the standard construction over the remaining arms, givingΩ​\(\(K−1\)​R\)=Ω​\(K​R\)\\Omega\(\\sqrt\{\(K\-1\)R\}\)=\\Omega\(\\sqrt\{KR\}\)\. The point of the proposition is that mandatory exposure, however large, cannot buy the learner out of theΩ​\(K​R\)\\Omega\(\\sqrt\{KR\}\)residual cost\.

The minimax results leave open whether easy instances are easier in the residual budget\. They are, but only down to the classical logarithmic barrier, and again it isRRthat sets the clock\. Call a blockwise\-fair policy*uniformly fast*on the template family of Proposition[18](https://arxiv.org/html/2607.22935#Thmtheorem18)\(arm11Bernoulli\(1/2\)\(1/2\)in every instance, all means in\(0,1\)\(0,1\)withμ⋆<1\\mu\_\{\\star\}<1\) if its expected fair regret iso​\(Ra\)o\(R^\{a\}\)for everya∈\(0,1\]a\\in\(0,1\]on every instance of the family, asR→∞R\\to\\inftywith the mandatory budgetM=M​\(R\)M=M\(R\)growing at most polynomially inRR\. BDQ\-UCB withη=1/T\\eta=1/Tis uniformly fast by Theorem[3](https://arxiv.org/html/2607.22935#Thmtheorem3)\(ii\), so the class is nonempty\.

###### Theorem 19\(Instance\-dependent lower bound\)\.

Letπ\\pibe any uniformly fast blockwise\-fair policy\. Then for every instanceν\\nuof the template family and every armi≠1i\\neq 1withΔi\>0\\Delta\_\{i\}\>0,

lim infR→∞𝔼ν​\[Nires\]log⁡R≥1kl​\(μi,μ⋆\),\\liminf\_\{R\\to\\infty\}\\ \\frac\{\\mathbb\{E\}\_\{\\nu\}\\bigl\[N^\{\\mathrm\{res\}\}\_\{i\}\\bigr\]\}\{\\log R\}\\ \\geq\\ \\frac\{1\}\{\\mathrm\{kl\}\(\\mu\_\{i\},\\mu\_\{\\star\}\)\},and consequently

lim infR→∞Reg𝐦​\(T\)log⁡R≥∑i≠1:Δi\>0Δikl​\(μi,μ⋆\)\.\\liminf\_\{R\\to\\infty\}\\ \\frac\{\\mathrm\{Reg\}\_\{\\mathbf\{m\}\}\(T\)\}\{\\log R\}\\ \\geq\\ \\sum\_\{i\\neq 1:\\,\\Delta\_\{i\}\>0\}\\frac\{\\Delta\_\{i\}\}\{\\mathrm\{kl\}\(\\mu\_\{i\},\\mu\_\{\\star\}\)\}\.

The proof, in Appendix[I\.18](https://arxiv.org/html/2607.22935#A9.SS18), is a change of measure via the Bretagnolle–Huber inequality against the instance that raises armiijust aboveμ⋆\\mu\_\{\\star\}; the mandatory pulls contribute zero divergence, so the information budget is againRR\. Together with the per\-arm term8​log⁡\(2​K​T/η\)/Δi8\\log\(2KT/\\eta\)/\\Delta\_\{i\}of Theorem[3](https://arxiv.org/html/2607.22935#Thmtheorem3)\(ii\), the theorem shows that logarithmic\-in\-RRgrowth with1/Δi1/\\Delta\_\{i\}scaling is necessary, up to the constant relatingkl​\(μi,μ⋆\)\\mathrm\{kl\}\(\\mu\_\{i\},\\mu\_\{\\star\}\)toΔi2\\Delta\_\{i\}^\{2\}\. The constant itself is attainable through the same embedded\-game reduction\.

###### Corollary 20\(BDQ\-KL: both regimes simultaneously\)\.

For Bernoulli rewards, let BDQ\-KL replace the residual rule of BDQ\-UCB by kl\-UCB\+\+\(Ménard and Garivier[2017](https://arxiv.org/html/2607.22935#bib.bib1)\), run on residual observations only with horizon parameterRR\. BDQ\-KL retains the deterministic blockwise fairness guarantee, its expected fair regret is at mostC​K​R\+KC\\sqrt\{KR\}\+Kfor a universal constantCC, and on every fixed instance

lim supR→∞Reg𝐦​\(T\)log⁡R≤∑i≠i⋆Δikl​\(μi,μ⋆\)\.\\limsup\_\{R\\to\\infty\}\\ \\frac\{\\mathrm\{Reg\}\_\{\\mathbf\{m\}\}\(T\)\}\{\\log R\}\\ \\leq\\ \\sum\_\{i\\neq i^\{\\star\}\}\\frac\{\\Delta\_\{i\}\}\{\\mathrm\{kl\}\(\\mu\_\{i\},\\mu\_\{\\star\}\)\}\.

BDQ\-KL is uniformly fast, and its per\-arm residual counts meet the bound of Theorem[19](https://arxiv.org/html/2607.22935#Thmtheorem19)with equality for every arm the theorem constrains, so the plan\-matched blockwise complexity is closed in both regimes, with the exact constant in the instance\-dependent one \(proof in Appendix[I\.19](https://arxiv.org/html/2607.22935#A9.SS19)\)\. The lower bounds, Theorem[17](https://arxiv.org/html/2607.22935#Thmtheorem17), and Corollary[20](https://arxiv.org/html/2607.22935#Thmtheorem20)together say that blockwise fairness costs nothing beyond the classical price of learning on the residual budget:Θ​\(K​R\)\\Theta\(\\sqrt\{KR\}\)in the worst case,\(1\+o​\(1\)\)​log⁡R​∑iΔi/kl​\(μi,μ⋆\)\(1\+o\(1\)\)\\log R\\sum\_\{i\}\\Delta\_\{i\}/\\mathrm\{kl\}\(\\mu\_\{i\},\\mu\_\{\\star\}\)on fixed instances, with the mandatory budgetMMappearing in neither\.

## Appendix EOnline Block\-Start Floors

###### Theorem 21\(Online block\-start floors\)\.

Suppose that before blockbbbegins, the learner observesmbm\_\{b\}, with∑imb,i≤Hb\\sum\_\{i\}m\_\{b,i\}\\leq H\_\{b\}, but does not know future floor vectorsmb\+1,…,mBm\_\{b\+1\},\\ldots,m\_\{B\}\. Online\-BDQ\-UCB, which executes the observed mandatory schedule for blockbband then runs UCB on the residual rounds of that block, satisfies all realized block constraints exactly\. Conditional on the realized floor sequence, the regret bounds of Theorem[3](https://arxiv.org/html/2607.22935#Thmtheorem3)hold with

R=∑b=1B\(Hb−∑imb,i\)\.R=\\sum\_\{b=1\}^\{B\}\\left\(H\_\{b\}\-\\sum\_\{i\}m\_\{b,i\}\\right\)\.

###### Proof\.

Feasibility is block\-local: oncembm\_\{b\}is revealed, the algorithm schedules exactlymb,im\_\{b,i\}pulls of each arm before the block’s residual UCB rounds, meeting the block constraint\. The UCB concentration event depends only on sample counts and does not require knowledge of future floors\. Conditional on the realized sequence\(m1,…,mB\)\(m\_\{1\},\\ldots,m\_\{B\}\), the proof of Theorem[3](https://arxiv.org/html/2607.22935#Thmtheorem3)applies verbatim\. ∎

## Appendix FLearning the Group Plan: Extended Analysis

This appendix develops in full the learned\-plan material summarized in Section[Learning the Group Plan](https://arxiv.org/html/2607.22935#Sx6): the one\-shot planner OG\-BDQ\-UCB, the benchmark\-slack calibration, the dual ledger and its overlap counterexample, and the plan\-sampling algorithm P\-BDQ\-UCB together with its feasibility guarantee, its descent condition, and the conditional regret theorem\. Proofs of the statements collected here appear in the proof sections that follow\.

### F\.1The One\-Shot Planner OG\-BDQ\-UCB

OG\-BDQ\-UCB \(optimistic\-plan Group\-BDQ\-UCB\) runs in each blockbbas follows: pull every arm once \(KKinitialization rounds\); form the clipped indicesUi=min⁡\{1,μ^i\+2​L/Ni\}U\_\{i\}=\\min\\\{1,\\,\\widehat\{\\mu\}\_\{i\}\+\\sqrt\{2L/N\_\{i\}\}\\\}from all observations so far; solve the linear program that maximizes∑iUi​yi\\sum\_\{i\}U\_\{i\}y\_\{i\}over the*plan polytope*

Pb=\{y≥0:\\displaystyle P\_\{b\}=\\Bigl\\\{y\\geq 0:∑i∈gyi≥fb,g\+t∀g∈𝒢,\\displaystyle\\textstyle\\sum\_\{i\\in g\}y\_\{i\}\\geq f\_\{b,g\}\+t\\ \\ \\forall g\\in\\mathcal\{G\},∑iyi=Hb−2K\},\\displaystyle\\textstyle\\sum\_\{i\}y\_\{i\}=H\_\{b\}\-2K\\Bigr\\\},giving the planyby\_\{b\}; roundyby\_\{b\}by Beck–Fiala tonbn\_\{b\}and execute it; and spend the at most2​K2Kleftover rounds of the block by the UCB rule\. The plan polytope is assumed nonempty, that is, the slack floors are coverable withinHb−2​KH\_\{b\}\-2K; the2​K2Kreserve absorbs the ceiling budget of the rounding and the initialization\. The benchmark is the strongest one available to any per\-block policy with the same rounding slack,OPTad=∑b=1B\[maxy∈Pb⁡⟨μ,y⟩\+2​K​μ⋆\]\\mathrm\{OPT\}^\{\\mathrm\{ad\}\}=\\sum\_\{b=1\}^\{B\}\\bigl\[\\max\_\{y\\in P\_\{b\}\}\\langle\\mu,y\\rangle\+2K\\mu\_\{\\star\}\\bigr\], the best slack\-feasible fractional plan per block with its reserve spent on a best arm\.

###### Theorem 22\(OG\-BDQ\-UCB: learning the plan\)\.

OG\-BDQ\-UCB meets every group floor in every block deterministically, and with probability at least1−η1\-\\etaits realized mean valueVVsatisfies

OPTad−V≤3​K​B\+4​Hmax​2​L​B,\\mathrm\{OPT\}^\{\\mathrm\{ad\}\}\-V\\ \\leq\\ 3KB\+4H\_\{\\max\}\\sqrt\{2LB\},whereHmax=maxb⁡HbH\_\{\\max\}=\\max\_\{b\}H\_\{b\}andL=log⁡\(2​K​T/η\)L=\\log\(2KT/\\eta\)\. With equal blocksHb=T/BH\_\{b\}=T/B, the bound reads3​K​B\+4​2​T​L/B3KB\+4\\sqrt\{2\}\\,T\\sqrt\{L/B\}\.

The proof is in Appendix[I\.20](https://arxiv.org/html/2607.22935#A9.SS20): feasibility is Theorem[6](https://arxiv.org/html/2607.22935#Thmtheorem6)applied toyby\_\{b\}, and for regret, block\-bbplanning has at leastbbsamples per arm, so optimism and LP optimality bound the per\-block gap bymin⁡\(1,2​2​L/b\)​Hb\\min\(1,2\\sqrt\{2L/b\}\)H\_\{b\}; summing∑bb−1/2≤2​B\\sum\_\{b\}b^\{\-1/2\}\\leq 2\\sqrt\{B\}with3​K3Kper block for integrality and initialization gives the bound\.

We first record that the rounding slack built into the plan polytope of OG\-BDQ\-UCB costs little whenever the floors admit a Slater\-type interior\.

###### Proposition 23\(Comparator gap under a margin\)\.

WriteVbfracV^\{\\mathrm\{frac\}\}\_\{b\}for the unslacked fractional group\-fair optimum of blockbb\(floorsfb,gf\_\{b,g\}, budget exactlyHbH\_\{b\}\) andVb⋆=maxy∈Pb⁡⟨μ,y⟩\+2​K​μ⋆V^\{\\star\}\_\{b\}=\\max\_\{y\\in P\_\{b\}\}\\langle\\mu,y\\rangle\+2K\\mu\_\{\\star\}for the block\-bbterm ofOPTad\\mathrm\{OPT\}^\{\\mathrm\{ad\}\}\. Suppose blockbbadmits a planz≥0z\\geq 0with∑i∈gzi≥fb,g\+σb​Hb\\sum\_\{i\\in g\}z\_\{i\}\\geq f\_\{b,g\}\+\\sigma\_\{b\}H\_\{b\}for every group and∑izi≤\(1−κb\)​Hb\\sum\_\{i\}z\_\{i\}\\leq\(1\-\\kappa\_\{b\}\)H\_\{b\}, for marginsσb,κb∈\(0,1\)\\sigma\_\{b\},\\kappa\_\{b\}\\in\(0,1\)\. Then

Vbfrac−Vb⋆≤max⁡\{tσb,2​Kκb\},V^\{\\mathrm\{frac\}\}\_\{b\}\-V^\{\\star\}\_\{b\}\\ \\leq\\ \\max\\Bigl\\\{\\frac\{t\}\{\\sigma\_\{b\}\},\\,\\frac\{2K\}\{\\kappa\_\{b\}\}\\Bigr\\\},so under uniform margins the total benchmark gap isO​\(B\)O\(B\), independent of the block lengths\.

The remaining development addresses the open overlapping case\. Writedg​\(τ\)d\_\{g\}\(\\tau\)for groupgg’s remaining deficit in its block just before roundτ\\tau\. Linear\-programming duality turns blockwise group\-fair regret into an exact per\-pull ledger, for every group system\.

###### Proposition 24\(Dual ledger\)\.

Fix a blockbband anyωb∈ℝ\\omega\_\{b\}\\in\\mathbb\{R\},λb≥0\\lambda\_\{b\}\\geq 0that are dual feasible for the block’s fractional program, meaningωb−∑g∋iλb,g≥μi\\omega\_\{b\}\-\\sum\_\{g\\ni i\}\\lambda\_\{b,g\}\\geq\\mu\_\{i\}for every armii, and define the reduced costri=ωb−μi−∑g∋iλb,g≥0r\_\{i\}=\\omega\_\{b\}\-\\mu\_\{i\}\-\\sum\_\{g\\ni i\}\\lambda\_\{b,g\}\\geq 0\. Every blockwise\-group\-fair pull sequence satisfies

Vbfrac−∑τ∈ℬbμAτ≤∑τ∈ℬb\[rAτ\+∑g∋Aτ:dg​\(τ\)=0λb,g\],V^\{\\mathrm\{frac\}\}\_\{b\}\-\\sum\_\{\\tau\\in\\mathcal\{B\}\_\{b\}\}\\mu\_\{A\_\{\\tau\}\}\\ \\leq\\ \\sum\_\{\\tau\\in\\mathcal\{B\}\_\{b\}\}\\Bigl\[\\,r\_\{A\_\{\\tau\}\}\\ \+\\\!\\\!\\sum\_\{g\\ni A\_\{\\tau\}:\\,d\_\{g\}\(\\tau\)=0\}\\\!\\\!\\lambda\_\{b,g\}\\Bigr\],with equality when\(ωb,λb\)\(\\omega\_\{b\},\\lambda\_\{b\}\)is dual optimal, in which case arms in the support of an optimal fractional plan have zero reduced cost\. Every pull’s contribution is nonnegative\.

The proof, in the appendix, is weak duality plus an exact\-crediting identity: blockwise feasibility drives every deficit fromfb,gf\_\{b,g\}to zero, so each group is credited its price on exactlyfb,gf\_\{b,g\}rounds\. Theorem[9](https://arxiv.org/html/2607.22935#Thmtheorem9)is the disjoint instantiation: there the optimal dual is explicit \(ωb=μ⋆\\omega\_\{b\}=\\mu\_\{\\star\}andλb,g=μ⋆−μg⋆\\lambda\_\{b,g\}=\\mu\_\{\\star\}\-\\mu^\{\\star\}\_\{g\}\), the reduced cost ofi∈gi\\in gis the within\-group gapΔ~i\\widetilde\{\\Delta\}\_\{i\}, and D\-BDQ\-UCB controls both ledger columns, bounding reduced costs through the covering selection inequality and zeroing the waste column by stopping each group’s covering pulls at exactlyfb,gf\_\{b,g\}\. That covering rule does not survive overlap:

###### Proposition 25\(The disjoint rule fails under overlap\)\.

There is a four\-arm instance with two overlapping groups \(arm degreet=2t=2\) on which any rule whose covering pulls select an index\-maximizing member of some deficient group and whose surplus pulls select the global index argmax \(D\-BDQ\-UCB applied verbatim\) is exactly feasible yet, on the concentration event, suffers regret at leastT/20−C​LT/20\-CLagainstOPTfrac\\mathrm\{OPT\}^\{\\mathrm\{frac\}\}, for a universal constantCC\.

The construction, proved in the appendix, is two floors sharing one arm whose mean sits slightly below its groupmates’: the optimal cover accepts the lower mean because one unit of that arm’s mass satisfies both floors at once, a multi\-coverage value that the dual prices∑g∋iλg\\sum\_\{g\\ni i\}\\lambda\_\{g\}encode and that a within\-group index comparison cannot see\. On per\-arm floors there is no multi\-coverage, which is why hard mandatory\-first schedules remain competitive there \(cf\. the E\-Scale stress battery in the experiments\); under overlap, any correct algorithm must be LP\-aware\. LP\-awareness alone is still not enough for our proof: the sampled plan must also satisfy explicit one\-step cover and value\-descent inequalities\. We state these conditions openly rather than hiding them inside an invalid concavity argument\.

The algorithm, P\-BDQ\-UCB \(plan\-sampling BDQ\-UCB\), re\-solves the optimistic residual program after every pull and lets the plan choose the arm\. Fix a measurable tie\-breaking rule once and for all: among multiple LP optima or minimum covers, choose the lexicographically first extreme\-point solution\. At roundτ\\tauof blockbb, withr​\(τ\)r\(\\tau\)rounds and integer deficitsdg​\(τ\)d\_\{g\}\(\\tau\)remaining, the algorithm first computes the fractional cover slack

S​\(τ\)\\displaystyle S\(\\tau\)=r​\(τ\)−mc​\(d​\(τ\)\),\\displaystyle=r\(\\tau\)\-\\mathrm\{mc\}\(d\(\\tau\)\),mc​\(d\)\\displaystyle\\mathrm\{mc\}\(d\)=min⁡\{∑iyi:y≥0,∑i∈gyi≥dg​∀g∈𝒢\}\.\\displaystyle=\\min\\Bigl\\\{\\textstyle\\sum\_\{i\}y\_\{i\}:y\\geq 0,\\ \\sum\_\{i\\in g\}y\_\{i\}\\geq d\_\{g\}\\ \\forall g\\in\\mathcal\{G\}\\Bigr\\\}\.The terminal guard fires at most once per block: at the first round withS​\(τ\)≤2​KS\(\\tau\)\\leq 2K, P\-BDQ\-UCB commits to the lexicographically first minimum fractional coverw​\(τ\)w\(\\tau\)ofd​\(τ\)d\(\\tau\), executes the rounded cover⌈w​\(τ\)⌉\\lceil w\(\\tau\)\\rceilover the following rounds, and spends any leftover rounds of the block by the index argmax\. At every earlier round it solves

y^\(τ\)∈arg​max\{∑iUi\(τ\)yi:y≥0,\\displaystyle\\widehat\{y\}\(\\tau\)\\in\\operatorname\*\{arg\\,max\}\\Bigl\\\{\\textstyle\\sum\_\{i\}U\_\{i\}\(\\tau\)y\_\{i\}:\\ y\\geq 0,∑i∈gyi≥dg​\(τ\)​∀g∈𝒢,\\displaystyle\\sum\_\{i\\in g\}y\_\{i\}\\geq d\_\{g\}\(\\tau\)\\ \\forall g\\in\\mathcal\{G\},∑iyi=r\(τ\)\}\\displaystyle\\sum\_\{i\}y\_\{i\}=r\(\\tau\)\\Bigr\\\}with clipped indicesUi=min⁡\{1,μ^i\+2​L/\(Ni∨1\)\}U\_\{i\}=\\min\\\{1,\\widehat\{\\mu\}\_\{i\}\+\\sqrt\{2L/\(N\_\{i\}\\vee 1\)\}\\\}on all observations, and pullsAτ∼y^​\(τ\)/r​\(τ\)A\_\{\\tau\}\\sim\\widehat\{y\}\(\\tau\)/r\(\\tau\)\. Thus the algorithm is defined independently of the analytical condition below: it samples from the optimistic plan until the guard fires\. Proposition[26](https://arxiv.org/html/2607.22935#Thmtheorem26)shows that the block\-start slack conditionHb−mc​\(fb\)\>2​KH\_\{b\}\-\\mathrm\{mc\}\(f\_\{b\}\)\>2Kalone makes the guard’s rounded cover fit deterministically; without it, P\-BDQ\-UCB is a heuristic and no guarantee is claimed\. This is not a Beck–Fiala discrepancy layer; it is a terminal cover\-rounding guard\. The guard is motivated by a simple integrality obstruction: with groups\{a,b\},\{b,c\},\{c,a\}\\\{a,b\\\},\\\{b,c\\\},\\\{c,a\\\}, unit floors, two remaining rounds, and a surplus arm, the fractional program has slack0\.50\.5that no integral sequence can safely spend, since a surplus pull leaves one round against a fractional cover of1\.51\.5\. This example motivates the terminal guard; it does not rule out an unconditionalO~​\(K​T\)\\widetilde\{O\}\(\\sqrt\{KT\}\)plus block\-additive integrality guarantee for overlap, which remains open\.

The guard alone already yields an unconditional feasibility guarantee for arbitrary overlapping systems, with no discrepancy\-rounding layer and no descent assumption\.

###### Proposition 26\(Pathwise feasibility of plan sampling\)\.

Suppose every block satisfies the initial cover\-slack conditionHb−mc​\(fb\)\>2​KH\_\{b\}\-\\mathrm\{mc\}\(f\_\{b\}\)\>2K\. Then P\-BDQ\-UCB satisfies every group floor in every block, pathwise and deterministically: each pull lowersmc\\mathrm\{mc\}by at most one, so the guard fires no later thanr=2​Kr=2Kand at a state withS​\(τc\)\>2​K−1S\(\\tau\_\{c\}\)\>2K\-1, where the rounded minimum cover⌈w​\(τc\)⌉\\lceil w\(\\tau\_\{c\}\)\\rceilhas size at mostmc​\(d​\(τc\)\)\+K≤r​\(τc\)−K\+1\\mathrm\{mc\}\(d\(\\tau\_\{c\}\)\)\+K\\leq r\(\\tau\_\{c\}\)\-K\+1and fits in the remaining budget\.

Turning to regret, for a deficit vectorddwrite

d\+​\(A\)g=max⁡\{dg−𝟏​\{A∈g\},0\}\.d^\{\+\}\(A\)\_\{g\}=\\max\\\{d\_\{g\}\-\\mathbf\{1\}\\\{A\\in g\\\},0\\\}\.Forr≥1r\\geq 1, define the true residual fractional value

Ψμ​\(r,d\)=max⁡\{⟨μ,y⟩:y≥0,∑i∈gyi≥dg​∀g,∑iyi=r\}\.\\Psi\_\{\\mu\}\(r,d\)=\\max\\Bigl\\\{\\langle\\mu,y\\rangle:y\\geq 0,\\textstyle\\sum\_\{i\\in g\}y\_\{i\}\\geq d\_\{g\}\\ \\forall g,\\sum\_\{i\}y\_\{i\}=r\\Bigr\\\}\.The following condition is the exact place where overlap is hard\. It replaces the invalid argument thatmc\\mathrm\{mc\}is concave:mc\\mathrm\{mc\}is convex as a function of deficits, since it is the pointwise maximum of feasible covering\-dual linear forms\.

###### Definition 4\(Sampled\-plan descent condition\)\.

Fixσ∈\(0,1\)\\sigma\\in\(0,1\)andη∈\(0,1\)\\eta\\in\(0,1\), setL=log⁡\(2​K​T/η\)L=\\log\(2KT/\\eta\), and letℰL\\mathcal\{E\}\_\{L\}be the concentration event of the proof of Theorem[12](https://arxiv.org/html/2607.22935#Thmtheorem12), on which every index used by the algorithm satisfies

μi\\displaystyle\\mu\_\{i\}≤Ui​\(τ\)≤μi\+ρi​\(τ\),\\displaystyle\\leq U\_\{i\}\(\\tau\)\\leq\\mu\_\{i\}\+\\rho\_\{i\}\(\\tau\),ρi​\(τ\)\\displaystyle\\rho\_\{i\}\(\\tau\)=min⁡\{1,2​2​L/\(Ni​\(τ\)∨1\)\}\.\\displaystyle=\\min\\\{1,2\\sqrt\{2L/\(N\_\{i\}\(\\tau\)\\vee 1\)\}\\\}\.A block satisfies the sampled\-plan descent condition with marginσ\\sigmaat levelη\\etaif its initial deficits satisfyHb−mc​\(fb\)≥σ​HbH\_\{b\}\-\\mathrm\{mc\}\(f\_\{b\}\)\\geq\\sigma H\_\{b\}, and, onℰL\\mathcal\{E\}\_\{L\}, at every pre\-guard state generated by P\-BDQ\-UCB with remaining budgetrr, deficitsdd, sampling distributionpi=y^i/rp\_\{i\}=\\widehat\{y\}\_\{i\}/r, and radiiρi\\rho\_\{i\}, the following two one\-step inequalities hold:

𝔼A∼p​\[mc​\(d\+​\(A\)\)\]\\displaystyle\\mathbb\{E\}\_\{A\\sim p\}\\bigl\[\\mathrm\{mc\}\(d^\{\+\}\(A\)\)\\bigr\]≤r−1r​mc​\(d\),\\displaystyle\\leq\\frac\{r\-1\}\{r\}\\,\\mathrm\{mc\}\(d\),\(3\)𝔼A∼p​\[Ψμ​\(r−1,d\+​\(A\)\)\+μA\]\\displaystyle\\mathbb\{E\}\_\{A\\sim p\}\\bigl\[\\Psi\_\{\\mu\}\(r\-1,d^\{\+\}\(A\)\)\+\\mu\_\{A\}\\bigr\]≥Ψμ​\(r,d\)−𝔼A∼p​\[ρA\]\.\\displaystyle\\geq\\Psi\_\{\\mu\}\(r,d\)\-\\mathbb\{E\}\_\{A\\sim p\}\[\\rho\_\{A\}\]\.\(4\)

Condition \([3](https://arxiv.org/html/2607.22935#A6.E3)\) is an online\-cover contraction condition; Condition \([4](https://arxiv.org/html/2607.22935#A6.E4)\) is an analytical true\-value descent condition and is not computable without the unknown means\. The definition is therefore a trajectory\-level sufficient condition, not an implementable certificate\. It is nonetheless non\-vacuous:

###### Proposition 27\(The descent condition holds for disjoint systems\)\.

Let the groups be pairwise disjoint\. Then at every pre\-guard state, inequality \([3](https://arxiv.org/html/2607.22935#A6.E3)\) holds unconditionally, and inequality \([4](https://arxiv.org/html/2607.22935#A6.E4)\) holds onℰL\\mathcal\{E\}\_\{L\}\. Consequently, every disjoint instance whose blocks satisfy∑gfb,g≤\(1−σ\)​Hb\\sum\_\{g\}f\_\{b,g\}\\leq\(1\-\\sigma\)H\_\{b\}andσ​Hb\>2​K\\sigma H\_\{b\}\>2Kmeets all hypotheses of Theorem[29](https://arxiv.org/html/2607.22935#Thmtheorem29)\.

Under arbitrary overlap, by contrast, the two inequalities are real assumptions rather than consequences of LP optimism, as the following examples show\.

###### Theorem 29\(Plan sampling under the descent condition\)\.

Fixη∈\(0,1\)\\eta\\in\(0,1\)andL=log⁡\(2​K​T/η\)L=\\log\(2KT/\\eta\)\. Suppose every block satisfies the sampled\-plan descent condition with marginσ\\sigmaat levelη\\eta\(Definition[4](https://arxiv.org/html/2607.22935#Thmdefinition4)\) together with the block\-start slack condition

σ​Hb\>2​Kfor every block​b\.\\sigma H\_\{b\}\>2K\\qquad\\text\{for every block \}b\.Then, in addition to the pathwise feasibility guaranteed by Proposition[26](https://arxiv.org/html/2607.22935#Thmtheorem26), the expected regret of P\-BDQ\-UCB against the per\-block fractional group\-fair optimum satisfies

OPTfrac−𝔼​\[V\]≤K\+4​2​K​T​L\+2​η​T\+C​B​\(Lσ2\+Kσ\),\\mathrm\{OPT\}^\{\\mathrm\{frac\}\}\-\\mathbb\{E\}\[V\]\\leq K\+4\\sqrt\{2KTL\}\+2\\eta T\+CB\\Bigl\(\\frac\{L\}\{\\sigma^\{2\}\}\+\\frac\{K\}\{\\sigma\}\\Bigr\),for a universal constantCC\. Withη=1/T\\eta=1/T, the expected regret is

O~​\(K​T\)\+O~​\(B​\(1σ2\+Kσ\)\)\.\\widetilde\{O\}\(\\sqrt\{KT\}\)\+\\widetilde\{O\}\\\!\\left\(B\\left\(\\frac\{1\}\{\\sigma^\{2\}\}\+\\frac\{K\}\{\\sigma\}\\right\)\\right\)\.

###### Proof sketch\.

The proof is in the appendix\. Feasibility is Proposition[26](https://arxiv.org/html/2607.22935#Thmtheorem26), whose hypothesis follows from the margin clause andσ​Hb\>2​K\\sigma H\_\{b\}\>2K; in particular the guard fires strictly after the block start and its rounded cover fits deterministically\. For regret, on the concentration eventℰL\\mathcal\{E\}\_\{L\}, \([3](https://arxiv.org/html/2607.22935#A6.E3)\) makesS​\(τ\)/r​\(τ\)S\(\\tau\)/r\(\\tau\)a bounded\-increment submartingale starting at leastσ\\sigma; Azuma’s inequality keeps the guard from firing untilr=O​\(L/σ2\+K/σ\)r=O\(L/\\sigma^\{2\}\+K/\\sigma\)\. On the same event, \([4](https://arxiv.org/html/2607.22935#A6.E4)\) gives the per\-pull inequality

𝔼​\[Ψμ​\(τ\)−Ψμ​\(τ\+1\)−μAτ∣ℱτ\]≤𝔼​\[ρAτ∣ℱτ\],\\mathbb\{E\}\[\\Psi\_\{\\mu\}\(\\tau\)\-\\Psi\_\{\\mu\}\(\\tau\{\+\}1\)\-\\mu\_\{A\_\{\\tau\}\}\\mid\\mathcal\{F\}\_\{\\tau\}\]\\leq\\mathbb\{E\}\[\\rho\_\{A\_\{\\tau\}\}\\mid\\mathcal\{F\}\_\{\\tau\}\],which telescopes across sampled pulls\. Summing the confidence radii over actually pulled arms givesK\+4​2​K​T​LK\+4\\sqrt\{2KTL\}, and the committed tail contributes only the guard length\. The concentration failure and slack\-concentration failure contribute2​η​T2\\eta T\. ∎

Theorem[29](https://arxiv.org/html/2607.22935#Thmtheorem29)should be read as a conditional overlap theorem\. It improves over the one\-shot rate of Theorem[22](https://arxiv.org/html/2607.22935#Thmtheorem22)only on trajectories where the sampled\-plan descent condition holds \(automatic in the disjoint case by Proposition[27](https://arxiv.org/html/2607.22935#Thmtheorem27)\) and it identifies the exact per\-step inequalities needed to make LP\-aware plan sampling work\. D\-BDQ\-UCB remains the LP\-free deterministic rule for disjoint systems, where no overlap pricing is needed\. The overlapping case without the descent condition remains open: the triangle\-with\-surplus example shows why a terminal guard is needed, while Remark[28](https://arxiv.org/html/2607.22935#Thmtheorem28)shows why the natural optimistic\-plan proof cannot be closed by a generic convexity or basis\-stability argument\.

## Appendix GExtensions and Discussion

### G\.1Terminal Repair for Slack\-Rounded Policies

The main algorithms in the paper are exactly fair\. However, some discrepancy rounding methods are designed to maintain small discrepancy at every prefix and may end with a small terminal deficit\. The following lemma shows how to repair such a sequence\.

###### Lemma 30\(Terminal repair\)\.

LetA1,…,ATA\_\{1\},\\dots,A\_\{T\}be any preliminary pull sequence with countsNi​\(T\)N\_\{i\}\(T\), and supposeNi​\(T\)≥m−BN\_\{i\}\(T\)\\geq m\-Bfor everyii\. Then there exists another pull sequenceA~1,…,A~T\\widetilde\{A\}\_\{1\},\\dots,\\widetilde\{A\}\_\{T\}with countsN~i​\(T\)≥m\\widetilde\{N\}\_\{i\}\(T\)\\geq mfor everyiisuch that the two sequences differ in at mostK​BKBpositions\. Consequently, because all rewards have means in\[0,1\]\[0,1\], the expected reward changes by at mostK​BKB\.

###### Proof\.

Define the deficit of armiibydi=\(m−Ni​\(T\)\)\+d\_\{i\}=\(m\-N\_\{i\}\(T\)\)\_\{\+\}\. SinceNi​\(T\)≥m−BN\_\{i\}\(T\)\\geq m\-B, we havedi≤Bd\_\{i\}\\leq Bfor everyii, and therefored=∑i=1Kdi≤K​Bd=\\sum\_\{i=1\}^\{K\}d\_\{i\}\\leq KB\. The total number of pulls is fixed atT≥K​mT\\geq Km, so the total deficit among arms belowmmis matched by at leastddsurplus pulls among arms strictly above their required levels\. Choosedid\_\{i\}positions currently assigned to surplus arms \(never reducing a surplus arm belowmm\) and change those positions to armii, for each deficient armii\. After all changes, every arm has count at leastmm\. The number of changed positions is exactlyd≤K​Bd\\leq KB, and changing one pull can change the expected reward by at most11, so the total expected reward changes by at mostK​BKB\. ∎

### G\.2Alternative View: Fractional Frontier and Integral Rounding

The continuous Pareto frontier in Theorem[15](https://arxiv.org/html/2607.22935#Thmtheorem15)is expressed in terms of exposure fractions\. For finiteTT, the integral floormminduces the fractionβT=m/T\\beta\_\{T\}=m/T\. The best fair integral allocation is

ni⋆​\(m\)=\{T−\(K−1\)​m,i=i⋆,m,i≠i⋆,n\_\{i\}^\{\\star\}\(m\)=\\begin\{cases\}T\-\(K\-1\)m,&i=i^\{\\star\},\\\\ m,&i\\neq i^\{\\star\},\\end\{cases\}and dividing byTTgives the exposure vector

ni⋆​\(m\)T=\{1−\(K−1\)​βT,i=i⋆,βT,i≠i⋆\.\\frac\{n\_\{i\}^\{\\star\}\(m\)\}\{T\}=\\begin\{cases\}1\-\(K\-1\)\\beta\_\{T\},&i=i^\{\\star\},\\\\ \\beta\_\{T\},&i\\neq i^\{\\star\}\.\\end\{cases\}Thus the finite\-horizon fair comparator lies exactly on the continuous Pareto frontier atβ=βT\\beta=\\beta\_\{T\}, and the only difference between a desired fractionδ\\deltaand the implemented fractionβT\\beta\_\{T\}is the unavoidable integer\-rounding error0≤δ−βT<1/T0\\leq\\delta\-\\beta\_\{T\}<1/T\.

### G\.3Avoiding Penalty Tuning

A Lagrangian approach would choose actions using an objective of the form

reward estimate−λ⋅fairness violation\.\\text\{reward estimate\}\-\\lambda\\cdot\\text\{fairness violation\}\.The difficulty is that the correctλ\\lambdadepends on the unknown reward gaps, the horizon, and the desired floor\. Ifλ\\lambdais too small, the floor may be violated; if it is too large, the policy may over\-explore low\-reward arms\. DQ\-UCB and BDQ\-UCB avoid this tuning problem by combinatorially enforcing the quota before reward optimization begins; the only statistical tuning parameter is the usual UCB confidence radius\.

## Appendix HDetails of the Deployment\-Facing Studies

The six studies summarized in the main text \(Table[9](https://arxiv.org/html/2607.22935#A8.T9)\) extend the clean stochastic and genre\-exposure validation toward deployment\-level coverage\. We record their exact configurations here; all are reproduced over1616seeds on CPU, reusing the same BDQ\-UCB, blockwise\-Lagrangian, global\-quota, and block\-floor routines as the main experiments\.

*Logged off\-policy replay with propensities \(N1\)\.*A soft logging policy \(arm0favored,ε=0\.5\\varepsilon=0\.5\) generates40,00040\{,\}000pulls with known propensities; we evaluate the blockwise\-fair target allocation off\-policy via IPS, SNIPS, and a doubly\-robust estimator \(per\-arm empirical model\)\. All three match the on\-policy value0\.5950\.595\(MAE0\.00210\.0021,0\.00210\.0021,0\.00190\.0019\)\.

*Overlapping group floors \(N2\)\.*K=8K=8arms, four overlapping groups \(sliding arm windows\), a per\-block floor of0\.20​H0\.20Hon each group; a single pull credits every group its arm belongs to\. The max\-group\-deficit rounding rule is feasible \(0group violation\); a group\-blind per\-arm/UCB policy violates by34\.334\.3pulls per block\. This is the regime where genuine discrepancy rounding matters beyond cyclic quota scheduling\. Table[5](https://arxiv.org/html/2607.22935#A8.T5)isolates the same separation on a controlled adversarial family: the half\-integral plan of Proposition[5](https://arxiv.org/html/2607.22935#Thmtheorem5)with fractional part0\.480\.48, over eight instances differing only in coordinate permutation and seed, where Beck–Fiala stays belowt=2t=2\(1\.04→1\.481\.04\\to 1\.48\) while naive rounding grows linearly inss\(1\.92→11\.521\.92\\to 11\.52, slope0\.480\.48, correlation1\.001\.00\); Figure[3](https://arxiv.org/html/2607.22935#A8.F3)plots the same separation\. Because the plan is adversarial the table is a worst\-case demonstration; a random\-fractional\-part variant shows the same qualitative separation with smaller constants: Beck–Fiala stays flat belowtt\(0\.93→1\.550\.93\\to 1\.55\) while naive rounding grows withss\(0\.86→2\.450\.86\\to 2\.45, correlation0\.990\.99\)\.

Table 5:Overlapping group floors \(row/column set system over ana×ba\\times bgrid; arm degreet=2t=2; group sizes=max⁡\(a,b\)s=\\max\(a,b\)\)\. Maximum group\-exposure violation of Beck–Fiala null\-space rounding versus naive nearest\-integer rounding on the adversarial half\-integral plan \(fractional part0\.480\.48\) of Proposition[5](https://arxiv.org/html/2607.22935#Thmtheorem5), over eight instances differing only in permutation and seed\. Beck–Fiala stays below thet=2t=2bound of Theorem[6](https://arxiv.org/html/2607.22935#Thmtheorem6)at every scale, while naive rounding grows linearly inss\(slope0\.480\.48, corr\.1\.001\.00\): the discrepancy algorithm is the one that makes group floors achievable within the block budget\.![Refer to caption](https://arxiv.org/html/2607.22935v1/figures/fig7_groupdisc.png)Figure 3:Visualization of Table[5](https://arxiv.org/html/2607.22935#A8.T5): maximum group\-exposure violation versus group sizesson the adversarial half\-integral plan \(row/column set system over ana×ba\\times bgrid, arm degreet=2t=2, fractional part0\.480\.48\)\. Beck–Fiala null\-space rounding stays flat below thet=2t=2bound of Theorem[6](https://arxiv.org/html/2607.22935#Thmtheorem6)at every scale \(top axis reports the arm countKKper grid\), while naive per\-arm rounding grows linearly inss\(slope0\.480\.48\)\. Whent≪st\\ll sthe discrepancy algorithm is unboundedly better than per\-arm rounding\.*Adaptive online penalty \(N3\)\.*A deadline\-aware blockwise Lagrangian that doublesλ\\lambdaafter any infeasible block, starting fromλ0=0\.5\\lambda\_\{0\}=0\.5\. It reaches competitive regret \(52\.252\.2\) but incurs1\.251\.25violations on average during the ramp\-up; BDQ\-UCB has0\. Online tuning removes the offline grid but not the transient infeasibility\.

*Contextual provider exposure \(N4\)\.*LinUCB overd=4d=4provider features with blockwise per\-provider floors enforced by block\-quota rounding; the residual rounds run LinUCB\. Block feasibility is exact \(0violation\), so feasibility\-by\-construction composes with contextual learning\.

*Delayed and rolling blocks \(N5\)\.*First, reward feedback delayed byd∈\{0,50,200\}d\\in\\\{0,50,200\\\}rounds: block floors stay exactly met \(feasibility is scheduling, independent of feedback timing\) while regret grows47\.4→69\.1→122\.447\.4\\to 69\.1\\to 122\.4\(Table[8](https://arxiv.org/html/2607.22935#A8.T8)\)\. Second, rolling\-window floors \(0\.08​H0\.08Hper trailing window of lengthHH\): an eager deadline\-aware rule keeps the worst trailing\-window violation at most11pull\.

*Mandatory\-sample ablation \(N6\)\.*At fixed residual budget, mandatory mass placed on hard\-to\-distinguish near\-best arms \(informative\) versus a dummy worst arm \(uninformative\) gives residual regret188\.1±7\.7188\.1\\pm 7\.7vs189\.7±3\.2189\.7\\pm 3\.2\. The direction is consistent with informative mandatory pulls helping, confirming the worst\-caseRR\-only bound is pessimistic when the mandatory exposure happens to be informative; the effect is within seed noise on this instance and is reported as such\.

Three quantities summarized in prose above are tabulated here in full: the residual\-budget sweep behind the regret comparison of the synthetic blockwise experiment \(Table[6](https://arxiv.org/html/2607.22935#A8.T6)\), the real\-rating MovieLens replay of the genre benchmark \(Table[7](https://arxiv.org/html/2607.22935#A8.T7)\), and the delayed\-feedback sweep of study N5 \(Table[8](https://arxiv.org/html/2607.22935#A8.T8)\)\.

Table 6:Residual\-budget sweep on the synthetic blockwise instance \(K=6K\{=\}6,B=12B\{=\}12,1616seeds\): the mandatory base fraction and the induced total residual budgetRRversus blockwise regret of BDQ\-UCB and of the best*feasible*Lagrangian over a six\-point penalty grid \(winningλ\\lambdain parentheses\)\. The tuned penalty is modestly ahead at every setting and the gap \(7\.5→5\.8→1\.6→0\.127\.5\\to 5\.8\\to 1\.6\\to 0\.12\) shrinks as the floor tightens andRRfalls; BDQ\-UCB never strictly wins on regret, consistent with the parameter\-free\-feasibility \(not lower\-regret\) scoping\.Table 7:Real\-rating MovieLens\-100k replay \(K=18K\{=\}18,B=12B\{=\}12,H=600H\{=\}600,1616seeds\): rewards are drawn non\-parametrically from each genre’s actual normalized11–55ratings rather than calibrated Bernoulli draws\. BDQ\-UCB is exactly feasible; the small penaltyλ=0\.5\\lambda\{=\}0\.5violates the floors \(34\.634\.6missing pulls\) while the feasible penalties tie it on regret\. The calibrated\-Bernoulli pattern of Table[11](https://arxiv.org/html/2607.22935#A8.T11)persists under the true reward distribution\.Table 8:Delayed\-feedback sweep of study N5 \(1616seeds\): block feasibility is exact at every delay \(feasibility is a scheduling property, independent of feedback timing\) while only regret degrades\. The companion rolling\-window floor \(trailing windowHH, floor0\.08​H=480\.08H\{=\}48\) is kept to a worst\-window violation of at most one pull by the eager deadline\-aware rule\.Table 9:Six deployment\-facing studies \(1616seeds, CPU\), reusing the BDQ\-UCB, blockwise\-Lagrangian, and block\-floor primitives\. N3 is a clean negative for the adaptive penalty baseline \(transient infeasibility\); N6’s effect is directional only and within seed noise\.Two supporting figures accompany the extended experiments\. Figure[5](https://arxiv.org/html/2607.22935#A8.F5)plots the E\-Scale feasibility–regret tradeoff against the penaltyλ\\lambda, and Figure[6](https://arxiv.org/html/2607.22935#A8.F6)plots the disjoint\-family scaling test underlying Theorem[9](https://arxiv.org/html/2607.22935#Thmtheorem9)\.

methodregret vs\. frac\. opt\.group viol\.feasibleOG\-BDQ\-UCB \(learns plan\)1083\.4±7\.61083\.4\\pm 7\.60\.00\.0yesGroup\-BDQ\-UCB \(fixed plan\)1174\.3±0\.81174\.3\\pm 0\.80\.00\.0yesGroup\-Lagrangian \(λ=4\\lambda=4\)739\.1±4\.9739\.1\\pm 4\.90\.00\.0yes \(tuned\)Group\-Lagrangian \(λ=16\\lambda=16\)741\.5±7\.7741\.5\\pm 7\.70\.00\.0yes \(tuned\)*Disjoint control \(genre\-only floors,t=1t=1\):*D\-BDQ\-UCB \(Thm\.[9](https://arxiv.org/html/2607.22935#Thmtheorem9)\)1042\.8±2\.81042\.8\\pm 2\.80\.00\.0yes

Table 10:E\-Group on5454MovieLens genre×\\timespopularity\-tier cells;1818genre\-union\+\+33tier\-union groups, arm degreet=2t=2\(top block\); regret against the per\-block fractional group\-fair optimum\. OG\-BDQ\-UCB learns a better plan than the fixed\-plan comparator; the tuned group\-Lagrangian is lower\-regret when feasible\. Beck–Fiala*necessity*is isolated by the adversarial group construction \(Table[5](https://arxiv.org/html/2607.22935#A8.T5)\), not by this mild\-overlap real instance\. The disjoint control uses genre\-only floors \(t=1t=1\); D\-BDQ\-UCB is exactly feasible with no rounding, matching Theorem[9](https://arxiv.org/html/2607.22935#Thmtheorem9)\.![Refer to caption](https://arxiv.org/html/2607.22935v1/x3.png)Figure 4:Blockwise regret for each method \(Table[1](https://arxiv.org/html/2607.22935#Sx7.T1); 16 seeds\)\. Blue bars mark methods with zero block violations; red bars mark infeasible methods, annotated with their total number of missing mandatory pulls\. BDQ\-UCB achieves exact feasibility in both settings; Global quota\+UCB has low apparent regret but violates 2174 \(synthetic\) and 4392 \(MovieLens\) mandatory pulls; the Lagrangian is feasible only atλ≥2\\lambda\\geq 2and requires per\-instance penalty tuning\.![Refer to caption](https://arxiv.org/html/2607.22935v1/x4.png)Figure 5:E\-Scale feasibility–regret tradeoff versus the penaltyλ\\lambda\(Table[12](https://arxiv.org/html/2607.22935#A8.T12)\)\. Raisingλ\\lambdabuys feasibility \(blue, left axis:3→223\\to 22of2424\) only by trading away regret on the feasible subset \(orange, right axis:198→61198\\to 61\); no boundedλ\\lambdareaches all2424, which BDQ\-UCB attains without tuning \(green line\)\.![Refer to caption](https://arxiv.org/html/2607.22935v1/x5.png)Figure 6:Disjoint lower\-bound family of Proposition[8](https://arxiv.org/html/2607.22935#Thmtheorem8): regret normalized by theB​HB\\sqrt\{H\}lower\-bound rate, versus the aspect ratioH/BH/Bat fixedTT\. D\-BDQ\-UCB \(Theorem[9](https://arxiv.org/html/2607.22935#Thmtheorem9)\) stays flat \(slope−0\.06\-0\.06, coefficient of variation0\.180\.18\), matchingB​HB\\sqrt\{H\}in every regime, while vanilla OG\-BDQ\-UCB grows \(slope\+0\.28\+0\.28\); the curves cross in the block\-sparse regimeH≫BH\\gg Bwhere OG’s one\-shot plan is loose\.### H\.1Semi\-Real MovieLens Blockwise Table and the E\-Scale Battery

Table[11](https://arxiv.org/html/2607.22935#A8.T11)is the semi\-real MovieLens\-100k counterpart to the synthetic blockwise Table[1](https://arxiv.org/html/2607.22935#Sx7.T1); the pattern matches in both\. Genre reward meansμ^i\\widehat\{\\mu\}\_\{i\}are estimated by normalizing ratings to\[0,1\]\[0,1\]and averaging over the movies carrying each genre, dropping genres with fewer than5050rated movies; the estimated means span\[0\.554,0\.730\]\[0\.554,0\.730\], with Film\-Noir highest\.

Table 11:Semi\-real MovieLens\-100k genre\-exposure blockwise experiment \(K=18K\{=\}18,B=12B\{=\}12,H=600H\{=\}600, real genre means,1616seeds\); companion to the synthetic Table[1](https://arxiv.org/html/2607.22935#Sx7.T1)\. BDQ\-UCB is exactly feasible, Global quota\+UCB violates by43924392pulls, the Lagrangian needsλ≥2\\lambda\\geq 2, and BDQ\-MOSS pays a premium for discarding mandatory observations\.For the E\-Scale battery we generate2424blockwise instances varying jointly in arm countK∈\{18,64,256\}K\\in\\\{18,64,256\\\}with Bernoulli means sampled from the MovieLens\-calibrated range\[0\.554,0\.730\]\[0\.554,0\.730\], in gap scale \(means compressed toward their median by factors\{1,12,14\}\\\{1,\\tfrac\{1\}\{2\},\\tfrac\{1\}\{4\}\\\}\), in floor tightness \(mandatory fraction\{0\.3,0\.6,0\.9\}\\\{0\.3,0\.6,0\.9\\\}of each block\), and in block\-length heterogeneity \(HbH\_\{b\}drawn log\-uniformly from\[200,1800\]\[200,1800\],B=12B=12\)\. For each fixedλ\\lambdain the grid\{0\.25,0\.5,1,2,4,8\}\\\{0\.25,0\.5,1,2,4,8\\\}we run the deadline\-aware Lagrangian on all2424instances with1616seeds each and report the number of instances with zero block violations, the worst per\-instance violation, and mean regret on the feasible subset; an oracle row selects the best feasibleλ\\lambdaper instance, with tuning cost counted as grid runs consumed; a BDQ\-UCB row reports the same metrics with no tuning\. Over the eight\-point gridλ∈\{0\.25,…,32\}\\lambda\\in\\\{0\.25,\\dots,32\\\}, feasibility climbs monotonically withλ\\lambda\(3,4,6,8,9,16,18,223,4,6,8,9,16,18,22of2424\) but no bounded penalty clears more than22/2422/24; the smaller penalties leave worst\-case violations in the hundreds to over a thousand missing pulls\.

Table 12:E\-Scale stress battery \(2424instances×\\times1616seeds\)\. Over the natural grid no bounded penalty is feasible on more than22/2422/24\(only theλ→∞\\lambda\\to\\inftyhard schedule reaches all2424\), and two instances admit no feasibleλ≤32\\lambda\\leq 32\. The tuned per\-instance oracle edges BDQ\-UCB on regret on the common feasible subset \(60\.660\.6vs61\.361\.3\); BDQ\-UCB’s advantage is tuning\-free exact feasibility on all2424, not lower regret\. Regret entries average over each method’s feasible subset\.![Refer to caption](https://arxiv.org/html/2607.22935v1/x6.png)Figure 7:Per\-instance feasible\-penalty ranges across the2424\-instance battery \(log\-λ\\lambdaaxis, instances sorted by smallest feasibleλ\\lambda\)\. The smallest feasible penalty spans a128×128\\timesrange \(0\.250\.25to3232\) and two tight, small\-gap, large\-KKinstances \(red\) admit no feasibleλ≤32\\lambda\\leq 32; no single bounded penalty is simultaneously feasible across the battery, whereas BDQ\-UCB is feasible on all2424without tuning\.

## Appendix IProofs

### I\.1Proof of Proposition[1](https://arxiv.org/html/2607.22935#Thmtheorem1)

We verify the identity’s three claims by telescoping and linearity\.

###### Proof\.

For the first claim,

DT=∑t=1T\(eAt−xt\)=N​\(T\)−S​\(T\),D\_\{T\}=\\sum\_\{t=1\}^\{T\}\(e\_\{A\_\{t\}\}\-x\_\{t\}\)=N\(T\)\-S\(T\),soDT,i=Ni​\(T\)−Si​\(T\)D\_\{T,i\}=N\_\{i\}\(T\)\-S\_\{i\}\(T\)\. IfSi​\(T\)≥m\+BS\_\{i\}\(T\)\\geq m\+Band‖DT‖∞≤B\\\|D\_\{T\}\\\|\_\{\\infty\}\\leq B, thenNi​\(T\)=Si​\(T\)\+DT,i≥mN\_\{i\}\(T\)=S\_\{i\}\(T\)\+D\_\{T,i\}\\geq m\. For the second claim,

∑t=1Tμ⊤​xt−∑t=1TμAt=μ⊤​∑t=1Txt−μ⊤​∑t=1TeAt=−μ⊤​DT\.\\sum\_\{t=1\}^\{T\}\\mu^\{\\top\}x\_\{t\}\-\\sum\_\{t=1\}^\{T\}\\mu\_\{A\_\{t\}\}=\\mu^\{\\top\}\\\!\\sum\_\{t=1\}^\{T\}x\_\{t\}\-\\mu^\{\\top\}\\\!\\sum\_\{t=1\}^\{T\}e\_\{A\_\{t\}\}=\-\\mu^\{\\top\}D\_\{T\}\.The third claim is an immediate reformulation of the first two\. ∎

### I\.2Proof of Lemma[2](https://arxiv.org/html/2607.22935#Thmtheorem2)

The blockwise fair\-regret identity rewrites fair regret as a gap\-weighted count of pulls beyond each block’s quota\.

###### Proof\.

Since∑iNi​\(T\)=T\\sum\_\{i\}N\_\{i\}\(T\)=TandΔi⋆=0\\Delta\_\{i^\{\\star\}\}=0,∑t=1TμAt=∑iNi​\(T\)​μi=T​μ⋆−∑i≠i⋆Δi​Ni​\(T\)\\sum\_\{t=1\}^\{T\}\\mu\_\{A\_\{t\}\}=\\sum\_\{i\}N\_\{i\}\(T\)\\mu\_\{i\}=T\\mu\_\{\\star\}\-\\sum\_\{i\\neq i^\{\\star\}\}\\Delta\_\{i\}N\_\{i\}\(T\)\. Substituting intoReg^𝐦​\(T\)=OPT𝐦​\(T\)−∑tμAt\\widehat\{\\mathrm\{Reg\}\}\_\{\\mathbf\{m\}\}\(T\)=\\mathrm\{OPT\}\_\{\\mathbf\{m\}\}\(T\)\-\\sum\_\{t\}\\mu\_\{A\_\{t\}\}and usingOPT𝐦​\(T\)=T​μ⋆−∑b∑i≠i⋆mb,i​Δi\\mathrm\{OPT\}\_\{\\mathbf\{m\}\}\(T\)=T\\mu\_\{\\star\}\-\\sum\_\{b\}\\sum\_\{i\\neq i^\{\\star\}\}m\_\{b,i\}\\Delta\_\{i\}gives the identity\. Blockwise fairness givesNi​\(T\)=∑bNb,i≥∑bmb,iN\_\{i\}\(T\)=\\sum\_\{b\}N\_\{b,i\}\\geq\\sum\_\{b\}m\_\{b,i\}, so every term is nonnegative\. ∎

### I\.3Proof of Theorem[3](https://arxiv.org/html/2607.22935#Thmtheorem3)

We establish exact blockwise fairness of BDQ\-UCB and itsK\+4​2​K​R​LK\+4\\sqrt\{2KRL\}residual\-regret bound, reusing the concentration event of Theorem[12](https://arxiv.org/html/2607.22935#Thmtheorem12)on the nonmandatory rounds\.

###### Proof\.

The quota schedule in blockbbpulls armiiexactlymb,im\_\{b,i\}times before any residual UCB pulls, so blockwise fairness holds deterministically\.

The same concentration eventℰ\\mathcal\{E\}as in Theorem[12](https://arxiv.org/html/2607.22935#Thmtheorem12)holds with probability at least1−η1\-\\eta\. Onℰ\\mathcal\{E\}, any residual UCB pull of a suboptimal armiiwithnnobservations impliesn≤8​L/Δi2n\\leq 8L/\\Delta\_\{i\}^\{2\}\. Mandatory pulls are comparator\-matched and do not contribute to blockwise fair regret\. Hence only residual pulls of suboptimal arms contribute, at most1\+8​L/Δi21\+8L/\\Delta\_\{i\}^\{2\}per arm beyond the at most one initialization pull absorbed by the additiveKK, and at mostRRin total\. Lemma[2](https://arxiv.org/html/2607.22935#Thmtheorem2)gives

Reg^𝐦​\(T\)≤K\+∑i:Δi\>0min⁡\{R​Δi,8​LΔi\}\.\\widehat\{\\mathrm\{Reg\}\}\_\{\\mathbf\{m\}\}\(T\)\\leq K\+\\sum\_\{i:\\Delta\_\{i\}\>0\}\\min\\\!\\left\\\{R\\Delta\_\{i\},\\frac\{8L\}\{\\Delta\_\{i\}\}\\right\\\}\.The gap\-free bound follows by anε\\varepsilon\-split replacingTTbyRR; choosingε=8​K​L/R\\varepsilon=\\sqrt\{8KL/R\}givesK\+4​2​K​R​LK\+4\\sqrt\{2KRL\}\. IfR=0R=0, regret is zero\. ∎

### I\.4Proof of Theorem[4](https://arxiv.org/html/2607.22935#Thmtheorem4)

We prove theΩ​\(K​R\)\\Omega\(\\sqrt\{KR\}\)minimax bound by reducing to a floor\-free single\-block bandit and applying a KL two\-point argument\.

###### Proof\.

Reduce to a single block with horizonT=RT=Rand zero floors; every policy is then blockwise fair, and this is a standard stochastic bandit problem\. For eachv∈\[K\]v\\in\[K\], define instancePvP\_\{v\}with armvvhaving mean1/2\+ε1/2\+\\varepsilonand all others mean1/21/2\. LetP0P\_\{0\}be the all\-1/21/2instance and setav=𝔼0​Nv​\(R\)a\_\{v\}=\\mathbb\{E\}\_\{0\}N\_\{v\}\(R\)\. Regret on instancevvisε​𝔼v​\[R−Nv​\(R\)\]\\varepsilon\\,\\mathbb\{E\}\_\{v\}\[R\-N\_\{v\}\(R\)\]\. Averaging overvv,

1K​∑v=1KRegvπ​\(R\)=ε​R−εK​∑v=1K𝔼v​Nv​\(R\)\.\\frac\{1\}\{K\}\\sum\_\{v=1\}^\{K\}\\mathrm\{Reg\}\_\{v\}^\{\\pi\}\(R\)=\\varepsilon R\-\\frac\{\\varepsilon\}\{K\}\\sum\_\{v=1\}^\{K\}\\mathbb\{E\}\_\{v\}N\_\{v\}\(R\)\.By the chain rule for KL divergence, the boundkl​\(1/2,1/2\+ε\)≤4​ε2\\mathrm\{kl\}\(1/2,\\,1/2\+\\varepsilon\)\\leq 4\\varepsilon^\{2\}valid forε≤1/4\\varepsilon\\leq 1/4, and Pinsker’s inequality,

𝔼v​Nv​\(R\)≤av\+R​ε​2​av\.\\mathbb\{E\}\_\{v\}N\_\{v\}\(R\)\\leq a\_\{v\}\+R\\varepsilon\\sqrt\{2a\_\{v\}\}\.Summing overvvand applying Cauchy’s inequality to∑vav≤K​R\\sum\_\{v\}\\sqrt\{a\_\{v\}\}\\leq\\sqrt\{KR\},

1K​∑v=1KRegvπ​\(R\)≥ε​R​\(1−1K−ε​2​RK\)\.\\frac\{1\}\{K\}\\sum\_\{v=1\}^\{K\}\\mathrm\{Reg\}\_\{v\}^\{\\pi\}\(R\)\\geq\\varepsilon R\\\!\\left\(1\-\\tfrac\{1\}\{K\}\-\\varepsilon\\sqrt\{\\tfrac\{2R\}\{K\}\}\\right\)\.Settingε=\(4​2\)−1​K/R\\varepsilon=\(4\\sqrt\{2\}\)^\{\-1\}\\sqrt\{K/R\}\(truncated at1/41/4\) givesc​K​Rc\\sqrt\{KR\}for some universalc\>0c\>0; see alsoLattimore and Szepesvári \([2020](https://arxiv.org/html/2607.22935#bib.bib26)\)for the template\. ∎

### I\.5Proof of Proposition[5](https://arxiv.org/html/2607.22935#Thmtheorem5)

We exhibit a single\-group instance on which nearest\-integer rounding misses the floor byΩ​\(s\)\\Omega\(s\)\.

###### Proof\.

Take a single groupggof sizessand a fractional plan withxi=ci\+\(12−ϵ\)x\_\{i\}=c\_\{i\}\+\(\\tfrac\{1\}\{2\}\-\\epsilon\)for eachi∈gi\\in g, with integer partcic\_\{i\}and fractional part12−ϵ\\tfrac\{1\}\{2\}\-\\epsilon\. Nearest\-integer rounding sends everyxix\_\{i\}down tocic\_\{i\}, so∑i∈g\(ni−xi\)=−s​\(12−ϵ\)=−Ω​\(s\)\\sum\_\{i\\in g\}\(n\_\{i\}\-x\_\{i\}\)=\-s\(\\tfrac\{1\}\{2\}\-\\epsilon\)=\-\\Omega\(s\)\. Setting the floorfg=∑i∈gxif\_\{g\}=\\sum\_\{i\\in g\}x\_\{i\}makes the realized group exposure short byΩ​\(s\)\\Omega\(s\)\. ∎

### I\.6Proof of Theorem[6](https://arxiv.org/html/2607.22935#Thmtheorem6)

We give the Beck–Fiala null\-space rounding and bound every group’s exposure error strictly below the arm degreettwithin the reserved budget\.

###### Proof\.

Writexi=⌊xi⌋\+fix\_\{i\}=\\lfloor x\_\{i\}\\rfloor\+f\_\{i\}withfi∈\[0,1\)f\_\{i\}\\in\[0,1\)\. It suffices to producez∈\{0,1\}Kz\\in\\\{0,1\\\}^\{K\}with\|∑i∈g\(zi−fi\)\|<t\|\\sum\_\{i\\in g\}\(z\_\{i\}\-f\_\{i\}\)\|<tfor everyg∈𝒢g\\in\\mathcal\{G\}and to setni=⌊xi⌋\+zin\_\{i\}=\\lfloor x\_\{i\}\\rfloor\+z\_\{i\}: thenni∈\{⌊xi⌋,⌈xi⌉\}n\_\{i\}\\in\\\{\\lfloor x\_\{i\}\\rfloor,\\lceil x\_\{i\}\\rceil\\\}for everyii\(coordinates withfi=0f\_\{i\}=0are frozen atzi=0z\_\{i\}=0from the start\), the totals satisfy∑i⌊xi⌋≤∑ini≤∑i⌈xi⌉≤C\\sum\_\{i\}\\lfloor x\_\{i\}\\rfloor\\leq\\sum\_\{i\}n\_\{i\}\\leq\\sum\_\{i\}\\lceil x\_\{i\}\\rceil\\leq C, and∑i∈g\(ni−xi\)=∑i∈g\(zi−fi\)\\sum\_\{i\\in g\}\(n\_\{i\}\-x\_\{i\}\)=\\sum\_\{i\\in g\}\(z\_\{i\}\-f\_\{i\}\)\.

Initializey←fy\\leftarrow f\. Call a coordinate*alive*ifyi∈\(0,1\)y\_\{i\}\\in\(0,1\)and*frozen*otherwise, and call a group*active*if it contains more thanttalive coordinates\. While at least one coordinate is alive, consider the homogeneous linear system, in the alive coordinates, that fixes∑i∈g,i​aliveyi\\sum\_\{i\\in g,\\ i\\ \\mathrm\{alive\}\}y\_\{i\}for every active groupgg\. Ifaacoordinates are alive, each lies in at mostttgroups, so the number of alive\-coordinate incidences is at mostt​ata; each active group accounts for more thanttof these incidences, so the number of active groups is strictly less thanaa\. The system therefore has fewer equations than unknowns and admits a nonzero solutionvvsupported on the alive coordinates\. Moveyyalong±v\\pm vuntil some coordinate reaches0or11, and freeze it there\. Each iteration freezes at least one coordinate, so the process terminates after at mostKKiterations, each of which solves one linear system, giving polynomial time overall\.

An active group’s alive\-coordinate sum is exactly invariant under every move, and its frozen coordinates never change, so its total∑i∈gyi\\sum\_\{i\\in g\}y\_\{i\}is invariant while the group is active\. Once a group is released it has at mostttalive coordinates, each of which subsequently moves within\(0,1\)\(0,1\)before freezing at0or11, so each contributes strictly less than11of drift, and the group total drifts by strictly less thanttin absolute value\. Hence at termination\|∑i∈g\(zi−fi\)\|<t\|\\sum\_\{i\\in g\}\(z\_\{i\}\-f\_\{i\}\)\|<tfor everyg∈𝒢g\\in\\mathcal\{G\}\.

Finally, for every group,

∑i∈gni=∑i∈gxi\+∑i∈g\(zi−fi\)\>∑i∈gxi−t≥fg,\\sum\_\{i\\in g\}n\_\{i\}=\\sum\_\{i\\in g\}x\_\{i\}\+\\sum\_\{i\\in g\}\(z\_\{i\}\-f\_\{i\}\)\>\\sum\_\{i\\in g\}x\_\{i\}\-t\\geq f\_\{g\},and since∑i∈gni\\sum\_\{i\\in g\}n\_\{i\}is an integer it is at least⌈fg⌉≥fg\\lceil f\_\{g\}\\rceil\\geq f\_\{g\}\. Every group floor is therefore met, and∑ini≤∑i⌈xi⌉≤C\\sum\_\{i\}n\_\{i\}\\leq\\sum\_\{i\}\\lceil x\_\{i\}\\rceil\\leq Ckeeps the allocation within the reserved budget\. ∎

### I\.7Proof of Corollary[7](https://arxiv.org/html/2607.22935#Thmtheorem7)

We show Group\-BDQ\-UCB is exactly group\-feasible via Theorem[6](https://arxiv.org/html/2607.22935#Thmtheorem6)and inherits the residual\-budget regret bound of Theorem[3](https://arxiv.org/html/2607.22935#Thmtheorem3)\.

###### Proof\.

Feasibility: by Theorem[6](https://arxiv.org/html/2607.22935#Thmtheorem6), the rounded plannbn\_\{b\}of every block meets every group floor, and∑inb,i≤∑i⌈xb,i⌉≤Hb\\sum\_\{i\}n\_\{b,i\}\\leq\\sum\_\{i\}\\lceil x\_\{b,i\}\\rceil\\leq H\_\{b\}, so the mandatory phase fits inside the block andRb≥0R\_\{b\}\\geq 0\.

For regret, let the comparator pull armiiexactlynb,in\_\{b,i\}times in blockbband assign allRbR\_\{b\}residual rounds of the block to a best arm\. The algebra of Lemma[2](https://arxiv.org/html/2607.22935#Thmtheorem2), withmb,im\_\{b,i\}replaced bynb,in\_\{b,i\}, expresses the realized fair regret against this comparator as∑i≠i⋆Δi​\(Ni​\(T\)−∑bnb,i\)\\sum\_\{i\\neq i^\{\\star\}\}\\Delta\_\{i\}\\bigl\(N\_\{i\}\(T\)\-\\sum\_\{b\}n\_\{b,i\}\\bigr\), a gap\-weighted count of residual pulls\. The concentration eventℰ\\mathcal\{E\}of the proof of Theorem[12](https://arxiv.org/html/2607.22935#Thmtheorem12)holds with probability at least1−η1\-\\eta; onℰ\\mathcal\{E\}, any residual selection of a suboptimal armiiwithnnprior observations forcesn≤8​L/Δi2n\\leq 8L/\\Delta\_\{i\}^\{2\}, so armiireceives at most1\+8​L/Δi21\+8L/\\Delta\_\{i\}^\{2\}residual pulls beyond the at most one initialization pull absorbed by the additiveKK, and at mostRRresidual pulls in total\. Theε\\varepsilon\-split withε=8​K​L/R\\varepsilon=\\sqrt\{8KL/R\}then yields the boundK\+4​2​K​R​LK\+4\\sqrt\{2KRL\}, exactly as in the proof of Theorem[3](https://arxiv.org/html/2607.22935#Thmtheorem3)\. ∎

### I\.8Proof of Proposition[8](https://arxiv.org/html/2607.22935#Thmtheorem8)

We lower\-bound the price of plan adaptivity byc​B​Hc\\,B\\sqrt\{H\}through an Assouad\-type averaging over sign patterns with a per\-block Bretagnolle–Huber bound\.

###### Proof\.

*The family\.*Arms are a star arm0andBBdisjoint pairs\{ab,ab′\}\\\{a\_\{b\},a\_\{b\}^\{\\prime\}\\\}, soK=2​B\+1K=2B\+1; groups are the pairs, so the arm degree ist=1t=1\. There areBBblocks of even lengthHH, and blockbbcarries the single floorfb,gb=m:=H/2f\_\{b,g\_\{b\}\}=m:=H/2on its own pair, all other floors zero\. The star arm is Bernoulli\(3/4\)\(3/4\)in every instance\. For a sign vectors∈\{±1\}Bs\\in\\\{\\pm 1\\\}^\{B\}, instanceνs\\nu\_\{s\}setsab∼Bernoulli​\(12\+sb​ε\)a\_\{b\}\\sim\\mathrm\{Bernoulli\}\(\\tfrac\{1\}\{2\}\+s\_\{b\}\\varepsilon\)andab′∼Bernoulli​\(12−sb​ε\)a\_\{b\}^\{\\prime\}\\sim\\mathrm\{Bernoulli\}\(\\tfrac\{1\}\{2\}\-s\_\{b\}\\varepsilon\), with

ε:=18​2​H≤14\.\\varepsilon\\ :=\\ \\frac\{1\}\{8\\sqrt\{2H\}\}\\ \\leq\\ \\frac\{1\}\{4\}\.Under everyνs\\nu\_\{s\}, the per\-block fractional optimum placesmmon the good arm of the block’s pair andH−mH\-mon the star, soOPTfrac=B​\[m​\(12\+ε\)\+\(H−m\)​34\]\\mathrm\{OPT\}^\{\\mathrm\{frac\}\}=B\\bigl\[m\(\\tfrac\{1\}\{2\}\+\\varepsilon\)\+\(H\-m\)\\tfrac\{3\}\{4\}\\bigr\]\.

*Regret is bad\-arm mass\.*Fixssand a blockbb; writeG,W,O,SG,W,O,Sfor the block\-bbpulls of the good pair arm, the bad pair arm, all other pairs’ arms, and the star, withG\+W\+O\+S=HG\+W\+O\+S=HandG\+W≥mG\+W\\geq mby blockwise group fairness\. All non\-star means are at most12\+ε\\tfrac\{1\}\{2\}\+\\varepsilon, so the block\-bbregret against the fractional optimum is at least

\(G−m\)​\(14−ε\)\+W​\(14\+ε\)\+O​\(14−ε\)\\displaystyle\(G\-m\)\\bigl\(\\tfrac\{1\}\{4\}\-\\varepsilon\\bigr\)\+W\\bigl\(\\tfrac\{1\}\{4\}\+\\varepsilon\\bigr\)\+O\\bigl\(\\tfrac\{1\}\{4\}\-\\varepsilon\\bigr\)≥−W​\(14−ε\)\+W​\(14\+ε\)=2​ε​W,\\displaystyle\\quad\\geq\\ \-W\\bigl\(\\tfrac\{1\}\{4\}\-\\varepsilon\\bigr\)\+W\\bigl\(\\tfrac\{1\}\{4\}\+\\varepsilon\\bigr\)\\ =2\\varepsilon W,usingG−m≥−WG\-m\\geq\-WandO≥0O\\geq 0\. Henceregb​\(s\)≥2​ε​𝔼s​\[Wb\]\\mathrm\{reg\}\_\{b\}\(s\)\\geq 2\\varepsilon\\,\\mathbb\{E\}\_\{s\}\[W\_\{b\}\], whereWbW\_\{b\}is the block\-bbpull count of the bad arm of pairbb, and every block’s regret is nonnegative\.

*Per\-coordinate two\-point bound\.*Fixbbands−bs\_\{\-b\}, and letP±P\_\{\\pm\}denote the trajectory laws over the whole horizon undersb=±1s\_\{b\}=\\pm 1\. WithA:=\{Nabblk≥m/2\}A:=\\\{N^\{\\mathrm\{blk\}\}\_\{a\_\{b\}\}\\geq m/2\\\}, whereNabblkN^\{\\mathrm\{blk\}\}\_\{a\_\{b\}\}counts block\-bbpulls ofaba\_\{b\}: undersb=−1s\_\{b\}=\-1the bad arm isaba\_\{b\}andregb≥2​ε​\(m/2\)​P−​\(A\)\\mathrm\{reg\}\_\{b\}\\geq 2\\varepsilon\(m/2\)P\_\{\-\}\(A\); undersb=\+1s\_\{b\}=\+1the bad arm isab′a\_\{b\}^\{\\prime\}withNab′blk≥m−NabblkN^\{\\mathrm\{blk\}\}\_\{a\_\{b\}^\{\\prime\}\}\\geq m\-N^\{\\mathrm\{blk\}\}\_\{a\_\{b\}\}, soregb≥2​ε​\(m/2\)​P\+​\(Ac\)\\mathrm\{reg\}\_\{b\}\\geq 2\\varepsilon\(m/2\)P\_\{\+\}\(A^\{c\}\)\. The Bretagnolle–Huber inequality gives

regb​\(s−b,−\)\+regb​\(s−b,\+\)\\displaystyle\\mathrm\{reg\}\_\{b\}\(s\_\{\-b\},\-\)\+\\mathrm\{reg\}\_\{b\}\(s\_\{\-b\},\+\)≥ε​m​\(P−​\(A\)\+P\+​\(Ac\)\)\\displaystyle\\ \\geq\\ \\varepsilon m\\bigl\(P\_\{\-\}\(A\)\+P\_\{\+\}\(A^\{c\}\)\\bigr\)≥ε​m2​e−KL​\(P−,P\+\)\.\\displaystyle\\ \\geq\\ \\frac\{\\varepsilon m\}\{2\}\\,e^\{\-\\mathrm\{KL\}\(P\_\{\-\},P\_\{\+\}\)\}\.The two laws differ only on the arms of pairbb, so by the chain rule andkl​\(12±ε,12∓ε\)≤16​ε2\\mathrm\{kl\}\(\\tfrac\{1\}\{2\}\\pm\\varepsilon,\\tfrac\{1\}\{2\}\\mp\\varepsilon\)\\leq 16\\varepsilon^\{2\}forε≤14\\varepsilon\\leq\\tfrac\{1\}\{4\},

KL​\(P−,P\+\)\\displaystyle\\mathrm\{KL\}\(P\_\{\-\},P\_\{\+\}\)≤16​ε2​𝔼\(s−b,−\)​\[Mb\],\\displaystyle\\ \\leq 16\\varepsilon^\{2\}\\,\\mathbb\{E\}\_\{\(s\_\{\-b\},\-\)\}\\bigl\[M\_\{b\}\\bigr\],Mb\\displaystyle M\_\{b\}:=total horizon pulls of pair​b\.\\displaystyle=\\text\{total horizon pulls of pair \}b\.
*Markov selection\.*Letqb:=2−B​∑s𝔼s​\[Mb\]q\_\{b\}:=2^\{\-B\}\\sum\_\{s\}\\mathbb\{E\}\_\{s\}\[M\_\{b\}\]\. The pairs are disjoint, so∑bMb≤T=B​H\\sum\_\{b\}M\_\{b\}\\leq T=BHpathwise and∑bqb≤B​H\\sum\_\{b\}q\_\{b\}\\leq BH; by Markov’s inequality at mostB/4B/4coordinates haveqb\>4​Hq\_\{b\}\>4H, so at least3​B/43B/4coordinates satisfyqb≤4​Hq\_\{b\}\\leq 4H\. For such a coordinate, averaging overs−bs\_\{\-b\},

2−\(B−1\)​∑s−bKL​\(P−,P\+\)≤16​ε2⋅2​qb≤128​ε2​H=1,2^\{\-\(B\-1\)\}\\\!\\\!\\sum\_\{s\_\{\-b\}\}\\mathrm\{KL\}\(P\_\{\-\},P\_\{\+\}\)\\ \\leq\\ 16\\varepsilon^\{2\}\\cdot 2q\_\{b\}\\ \\leq\\ 128\\,\\varepsilon^\{2\}H\\ =\\ 1,by the choice ofε\\varepsilon, and Jensen’s inequality gives2−\(B−1\)​∑s−be−KL≥e−12^\{\-\(B\-1\)\}\\sum\_\{s\_\{\-b\}\}e^\{\-\\mathrm\{KL\}\}\\geq e^\{\-1\}\.

*Assembling\.*Averaging the two\-point bound oversbs\_\{b\}and then overs−bs\_\{\-b\}, each coordinatebbwithqb≤4​Hq\_\{b\}\\leq 4Hcontributes at least\(ε​m/4\)​e−1\(\\varepsilon m/4\)e^\{\-1\}to the sign\-averaged total regret, so

2−B​∑s\[OPTfrac−𝔼s​Vπ\]\\displaystyle 2^\{\-B\}\\sum\_\{s\}\\bigl\[\\mathrm\{OPT\}^\{\\mathrm\{frac\}\}\-\\mathbb\{E\}\_\{s\}V^\{\\pi\}\\bigr\]≥3​B4⋅ε​m4​e−1\\displaystyle\\ \\geq\\ \\frac\{3B\}\{4\}\\cdot\\frac\{\\varepsilon m\}\{4\}\\,e^\{\-1\}=3256​2​e​B​H,\\displaystyle\\ =\\ \\frac\{3\}\{256\\sqrt\{2\}\\,e\}\\,B\\sqrt\{H\},and the supremum over the family dominates the average, proving the claim withc=3/\(256​2​e\)c=3/\(256\\sqrt\{2\}\\,e\)\. Finally, on the same instances the fixed plan that places the block’s floor mass onaba\_\{b\}\(with unit slack\) is admissible for Corollary[7](https://arxiv.org/html/2607.22935#Thmtheorem7), giving regretO​\(K​R​L\)O\(\\sqrt\{KRL\}\)against the fixed\-plan comparator\. ∎

### I\.9Proof of Theorem[9](https://arxiv.org/html/2607.22935#Thmtheorem9)

We prove exact feasibility of D\-BDQ\-UCB and a4​K\+8​K​T​L4K\+8\\sqrt\{KTL\}regret bound by decomposing the per\-block optimum across disjoint groups\.

###### Proof\.

*Feasibility\.*Groupggreceives exactlyfb,gf\_\{b,g\}covering pulls in blockbb, so every floor is met exactly and deterministically;∑gfb,g≤Hb\\sum\_\{g\}f\_\{b,g\}\\leq H\_\{b\}leaves the surplus nonnegative\.

*The comparator decomposes\.*Writeμg⋆=maxi∈g⁡μi\\mu^\{\\star\}\_\{g\}=\\max\_\{i\\in g\}\\mu\_\{i\}\. For anyy≥0y\\geq 0with∑i∈gyi=Gg≥fb,g\\sum\_\{i\\in g\}y\_\{i\}=G\_\{g\}\\geq f\_\{b,g\}and∑iyi=Hb\\sum\_\{i\}y\_\{i\}=H\_\{b\}, disjointness gives

⟨μ,y⟩\\displaystyle\\langle\\mu,y\\rangle≤∑gμg⋆​Gg\+μ⋆​\(Hb−∑gGg\)\\displaystyle\\ \\leq\\ \\sum\_\{g\}\\mu^\{\\star\}\_\{g\}G\_\{g\}\+\\mu\_\{\\star\}\\Bigl\(H\_\{b\}\-\\sum\_\{g\}G\_\{g\}\\Bigr\)≤∑gfb,g​μg⋆\+μ⋆​\(Hb−∑gfb,g\),\\displaystyle\\ \\leq\\ \\sum\_\{g\}f\_\{b,g\}\\,\\mu^\{\\star\}\_\{g\}\+\\mu\_\{\\star\}\\Bigl\(H\_\{b\}\-\\sum\_\{g\}f\_\{b,g\}\\Bigr\),usingμg⋆≤μ⋆\\mu^\{\\star\}\_\{g\}\\leq\\mu\_\{\\star\}for the second inequality; the value is attained by covering each floor with a best member of its group and assigning the surplus to a best arm\. HenceOPTfrac=∑b\[∑gfb,g​μg⋆\+\(Hb−∑gfb,g\)​μ⋆\]\\mathrm\{OPT\}^\{\\mathrm\{frac\}\}=\\sum\_\{b\}\[\\sum\_\{g\}f\_\{b,g\}\\mu^\{\\star\}\_\{g\}\+\(H\_\{b\}\-\\sum\_\{g\}f\_\{b,g\}\)\\mu\_\{\\star\}\], and withΔ~i=μg⋆−μi\\widetilde\{\\Delta\}\_\{i\}=\\mu^\{\\star\}\_\{g\}\-\\mu\_\{i\}fori∈gi\\in g,

OPTfrac−V=∑g∑i∈gΔ~i​Nicov\+∑i≠i⋆Δi​Nisur,\\mathrm\{OPT\}^\{\\mathrm\{frac\}\}\-V\\ =\\ \\sum\_\{g\}\\sum\_\{i\\in g\}\\widetilde\{\\Delta\}\_\{i\}\\,N^\{\\mathrm\{cov\}\}\_\{i\}\\ \+\\ \\sum\_\{i\\neq i^\{\\star\}\}\\Delta\_\{i\}\\,N^\{\\mathrm\{sur\}\}\_\{i\},whereNicovN^\{\\mathrm\{cov\}\}\_\{i\}andNisurN^\{\\mathrm\{sur\}\}\_\{i\}count covering and surplus pulls of armiiover the horizon\.

*Counting\.*Letℰ\\mathcal\{E\}be the concentration event of the proof of Theorem[12](https://arxiv.org/html/2607.22935#Thmtheorem12), of probability at least1−η1\-\\eta\. At most one covering selection of any arm occurs with zero prior samples\. Onℰ\\mathcal\{E\}, a covering selection ofi∈gi\\in gwithn≥1n\\geq 1prior samples requiresUi≥Uig⋆≥μg⋆U\_\{i\}\\geq U\_\{i^\{\\star\}\_\{g\}\}\\geq\\mu^\{\\star\}\_\{g\}, henceμi\+2​2​L/n≥μg⋆\\mu\_\{i\}\+2\\sqrt\{2L/n\}\\geq\\mu^\{\\star\}\_\{g\}andn≤8​L/Δ~i2n\\leq 8L/\\widetilde\{\\Delta\}\_\{i\}^\{2\}; extra samples from surplus pulls or other blocks only increasenn, soNicov≤1\+8​L/Δ~i2N^\{\\mathrm\{cov\}\}\_\{i\}\\leq 1\+8L/\\widetilde\{\\Delta\}\_\{i\}^\{2\}, while∑i∈gNicov=Fg\\sum\_\{i\\in g\}N^\{\\mathrm\{cov\}\}\_\{i\}=F\_\{g\}\. Splitting groupggatεg=8​\|g\|​L/Fg\\varepsilon\_\{g\}=\\sqrt\{8\|g\|L/F\_\{g\}\},

∑i∈gΔ~i​Nicov\\displaystyle\\sum\_\{i\\in g\}\\widetilde\{\\Delta\}\_\{i\}N^\{\\mathrm\{cov\}\}\_\{i\}≤εg​Fg\+∑i∈g:Δ~i≥εg\(1\+8​LΔ~i\)\\displaystyle\\ \\leq\\ \\varepsilon\_\{g\}F\_\{g\}\+\\sum\_\{i\\in g:\\,\\widetilde\{\\Delta\}\_\{i\}\\geq\\varepsilon\_\{g\}\}\\Bigl\(1\+\\frac\{8L\}\{\\widetilde\{\\Delta\}\_\{i\}\}\\Bigr\)≤2​\|g\|\+4​2​\|g\|​Fg​L\.\\displaystyle\\ \\leq 2\|g\|\+4\\sqrt\{2\\,\|g\|F\_\{g\}L\}\.The surplus term is the residual argument of Theorem[3](https://arxiv.org/html/2607.22935#Thmtheorem3)verbatim: onℰ\\mathcal\{E\}it is at most2​K\+4​2​K​R′​L2K\+4\\sqrt\{2KR^\{\\prime\}L\}\.

*Assembling\.*Summing over groups, using∑g\|g\|≤K\\sum\_\{g\}\|g\|\\leq K\(disjointness\) and Cauchy–Schwarz,

∑g\|g\|​Fg\+K​R′\\displaystyle\\sum\_\{g\}\\sqrt\{\|g\|F\_\{g\}\}\+\\sqrt\{KR^\{\\prime\}\}≤\(∑g\|g\|\+K\)​\(∑gFg\+R′\)\\displaystyle\\ \\leq\\ \\sqrt\{\\Bigl\(\\sum\_\{g\}\|g\|\+K\\Bigr\)\\Bigl\(\\sum\_\{g\}F\_\{g\}\+R^\{\\prime\}\\Bigr\)\}≤2​K​T,\\displaystyle\\ \\leq\\ \\sqrt\{2KT\},which givesOPTfrac−V≤4​K\+4​2​L​\(∑g\|g\|​Fg\+K​R′\)≤4​K\+8​K​T​L\\mathrm\{OPT\}^\{\\mathrm\{frac\}\}\-V\\leq 4K\+4\\sqrt\{2L\}\(\\sum\_\{g\}\\sqrt\{\|g\|F\_\{g\}\}\+\\sqrt\{KR^\{\\prime\}\}\)\\leq 4K\+8\\sqrt\{KTL\}onℰ\\mathcal\{E\}\.

*Consequences\.*On the family of Proposition[8](https://arxiv.org/html/2607.22935#Thmtheorem8):\|g\|=2\|g\|=2,Fgb=H/2F\_\{g\_\{b\}\}=H/2,K=2​B\+1K=2B\+1,R′=B​H/2R^\{\\prime\}=BH/2, so∑g\|g\|​Fg=B​H\\sum\_\{g\}\\sqrt\{\|g\|F\_\{g\}\}=B\\sqrt\{H\}andK​R′≤3​B⋅B​H/2≤2​B​H\\sqrt\{KR^\{\\prime\}\}\\leq\\sqrt\{3B\\cdot BH/2\}\\leq 2B\\sqrt\{H\}, givingO​\(L⋅B​H\)O\(\\sqrt\{L\}\\cdot B\\sqrt\{H\}\)against theΩ​\(B​H\)\\Omega\(B\\sqrt\{H\}\)lower bound in every regime\. With singleton groups,Δ~i=0\\widetilde\{\\Delta\}\_\{i\}=0annihilates the covering term, the strong comparator coincides with the plan\-matched one, and the bound reduces to the surplus term of Theorem[3](https://arxiv.org/html/2607.22935#Thmtheorem3)\. ∎

### I\.10Proof of Lemma[10](https://arxiv.org/html/2607.22935#Thmtheorem10)

The static fair\-regret identity is theB=1B=1specialization of Lemma[2](https://arxiv.org/html/2607.22935#Thmtheorem2), rewriting fair regret as a gap\-weighted count of pulls beyond the quota\.

###### Proof\.

Since∑iNi​\(T\)=T\\sum\_\{i\}N\_\{i\}\(T\)=TandΔi⋆=0\\Delta\_\{i^\{\\star\}\}=0,

∑t=1TμAt=∑i=1KNi​\(T\)​μi=T​μ⋆−∑i≠i⋆Δi​Ni​\(T\)\.\\sum\_\{t=1\}^\{T\}\\mu\_\{A\_\{t\}\}=\\sum\_\{i=1\}^\{K\}N\_\{i\}\(T\)\\mu\_\{i\}=T\\mu\_\{\\star\}\-\\sum\_\{i\\neq i^\{\\star\}\}\\Delta\_\{i\}N\_\{i\}\(T\)\.Substituting intoReg^m​\(T\)=OPTm​\(T\)−∑tμAt\\widehat\{\\mathrm\{Reg\}\}\_\{m\}\(T\)=\\mathrm\{OPT\}\_\{m\}\(T\)\-\\sum\_\{t\}\\mu\_\{A\_\{t\}\}and usingOPTm​\(T\)=T​μ⋆−m​∑i≠i⋆Δi\\mathrm\{OPT\}\_\{m\}\(T\)=T\\mu\_\{\\star\}\-m\\sum\_\{i\\neq i^\{\\star\}\}\\Delta\_\{i\}gives the identity\. Undermm\-fairness every termΔi​\(Ni​\(T\)−m\)\\Delta\_\{i\}\(N\_\{i\}\(T\)\-m\)is nonnegative\. ∎

### I\.11Proof of Lemma[11](https://arxiv.org/html/2607.22935#Thmtheorem11)

We bound the cyclic\-schedule discrepancy by one via a prefix\-count argument\.

###### Proof\.

Aftermmcomplete cycles, each arm has been pulled exactly once per cycle, soNi​\(K​m\)=mN\_\{i\}\(Km\)=m\. For a prefixtt, writet=q​K\+rt=qK\+rwithq≥0q\\geq 0and0≤r<K0\\leq r<K\. Each arm has been pulled eitherqqorq\+1q\+1times\. Sincet/K=q\+r/Kt/K=q\+r/K,

\|Ni​\(t\)−tK\|≤max⁡\{rK,1−rK\}≤1\.\\left\|N\_\{i\}\(t\)\-\\frac\{t\}\{K\}\\right\|\\leq\\max\\\!\\left\\\{\\frac\{r\}\{K\},1\-\\frac\{r\}\{K\}\\right\\\}\\leq 1\.∎

### I\.12Proof of Theorem[12](https://arxiv.org/html/2607.22935#Thmtheorem12)

We prove exact fairness deterministically and theK\+4​2​K​T​LK\+4\\sqrt\{2KTL\}regret bound on a Hoeffding concentration event\.

###### Proof\.

The exact fairness claim is deterministic\. Ifm≥1m\\geq 1, the first phase pulls every arm exactlymmtimes, soNi​\(T\)≥mN\_\{i\}\(T\)\\geq mfor every arm\. Ifm=0m=0, the constraint is vacuous\.

Define the event

ℰ=\{∀i∈\[K\],∀n∈\{1,…,T\}:\|μ^i,n−μi\|≤2​Ln\},\\mathcal\{E\}=\\left\\\{\\forall i\\in\[K\],\\ \\forall n\\in\\\{1,\\dots,T\\\}:\\left\|\\widehat\{\\mu\}\_\{i,n\}\-\\mu\_\{i\}\\right\|\\leq\\sqrt\{\\frac\{2L\}\{n\}\}\\right\\\},whereμ^i,n\\widehat\{\\mu\}\_\{i,n\}is the empirical mean of the firstnnrewards from armii, andL=log⁡\(2​K​T/η\)L=\\log\(2KT/\\eta\)\. By Hoeffding’s inequality and a union bound overK​TKTpairs,

ℙ​\(ℰc\)≤2​K​T​exp⁡\(−4​L\)≤η\.\\mathbb\{P\}\(\\mathcal\{E\}^\{c\}\)\\leq 2KT\\exp\(\-4L\)\\leq\\eta\.
Assumeℰ\\mathcal\{E\}holds\. Fix a suboptimal armi≠i⋆i\\neq i^\{\\star\}selected during the UCB phase withn=Ni​\(t\)n=N\_\{i\}\(t\)observations\. Sinceiimaximizes the UCB index and onℰ\\mathcal\{E\}we haveμ^i⋆\+2​L/Ni⋆≥μ⋆\\widehat\{\\mu\}\_\{i^\{\\star\}\}\+\\sqrt\{2L/N\_\{i^\{\\star\}\}\}\\geq\\mu\_\{\\star\}andμ^i\+2​L/n≤μi\+2​2​L/n\\widehat\{\\mu\}\_\{i\}\+\\sqrt\{2L/n\}\\leq\\mu\_\{i\}\+2\\sqrt\{2L/n\},

Δi≤2​2​Ln,son≤8​LΔi2\.\\Delta\_\{i\}\\leq 2\\sqrt\{\\frac\{2L\}\{n\}\},\\qquad\\text\{so\}\\qquad n\\leq\\frac\{8L\}\{\\Delta\_\{i\}^\{2\}\}\.LetMi=\(Ni​\(T\)−m\)\+M\_\{i\}=\(N\_\{i\}\(T\)\-m\)\_\{\+\}be the number of UCB pulls of armiibeyond the quota\. ThenMi≤1\+8​L/Δi2M\_\{i\}\\leq 1\+8L/\\Delta\_\{i\}^\{2\}\. Using Lemma[10](https://arxiv.org/html/2607.22935#Thmtheorem10),

Reg^m​\(T\)≤K\+∑i:Δi\>0min⁡\{T​Δi,8​LΔi\}\.\\widehat\{\\mathrm\{Reg\}\}\_\{m\}\(T\)\\leq K\+\\sum\_\{i:\\Delta\_\{i\}\>0\}\\min\\\!\\left\\\{T\\Delta\_\{i\},\\frac\{8L\}\{\\Delta\_\{i\}\}\\right\\\}\.For the gap\-free bound, split arms at thresholdε\\varepsilon:

Reg^m​\(T\)≤K\+ε​T\+8​K​Lε\.\\widehat\{\\mathrm\{Reg\}\}\_\{m\}\(T\)\\leq K\+\\varepsilon T\+\\frac\{8KL\}\{\\varepsilon\}\.Choosingε=8​K​L/T\\varepsilon=\\sqrt\{8KL/T\}givesK\+4​2​K​T​LK\+4\\sqrt\{2KTL\}\. The expected\-regret bound follows by settingη=1/T\\eta=1/Tand bounding theℰc\\mathcal\{E\}^\{c\}contribution by11\. ∎

Figure[8](https://arxiv.org/html/2607.22935#A9.F8)provides empirical confirmation: fair regret stays inside theO​\(K​T​log⁡\(K​T\)\)O\(\\sqrt\{KT\\log\(KT\)\}\)envelope and vanishes at largeTT\.

![Refer to caption](https://arxiv.org/html/2607.22935v1/x7.png)Figure 8:E1: Fair regret \(left\) and normalized regretReg/K​T​log⁡T\\mathrm\{Reg\}/\\sqrt\{KT\\log T\}\(right\) for DQ\-UCB vs\. horizonTT\(K=5K=5,δ=0\.1\\delta=0\.1, 16 seeds\)\. Fair regret drops from31\.531\.5atT=2,000T=2\{,\}000to zero forT≥8,000T\\geq 8\{,\}000; the normalized regret stays within theO​\(K​T​log⁡\(K​T\)\)O\(\\sqrt\{KT\\log\(KT\)\}\)envelope of Theorem[12](https://arxiv.org/html/2607.22935#Thmtheorem12)\(it is the regret upper bound that is verified, not a matched growth rate, since realized fair regret is zero at largeTT\)\.
### I\.13Proof of Corollary[14](https://arxiv.org/html/2607.22935#Thmtheorem14)

We pass from pseudo\-regret to realized reward via an Azuma–Hoeffding martingale bound\.

###### Proof\.

Theorem[12](https://arxiv.org/html/2607.22935#Thmtheorem12)boundsOPTm​\(T\)−∑tμAt\\mathrm\{OPT\}\_\{m\}\(T\)\-\\sum\_\{t\}\\mu\_\{A\_\{t\}\}\. Since rewards lie in\[0,1\]\[0,1\], the differencesXAt−μAtX\_\{A\_\{t\}\}\-\\mu\_\{A\_\{t\}\}form a bounded martingale difference sequence\. By Azuma–Hoeffding, with probability at least1−η1\-\\eta,

∑t=1TμAt−∑t=1TXAt≤2​T​log⁡\(1/η\)\.\\sum\_\{t=1\}^\{T\}\\mu\_\{A\_\{t\}\}\-\\sum\_\{t=1\}^\{T\}X\_\{A\_\{t\}\}\\leq\\sqrt\{2T\\log\(1/\\eta\)\}\.A union bound with the event of Theorem[12](https://arxiv.org/html/2607.22935#Thmtheorem12)gives the claim\. ∎

### I\.14Proof of Theorem[15](https://arxiv.org/html/2607.22935#Thmtheorem15)

We identify the value\-maximizing allocation at each fairness level and show the resulting curve is Pareto\-efficient\.

###### Proof\.

Fixβ∈\[0,1/K\]\\beta\\in\[0,1/K\]\. Anyppwithϕ​\(p\)≥β\\phi\(p\)\\geq\\betaassigns at leastβ\\betato every arm\. Among such allocations, the unique reward maximizer assigns exactlyβ\\betato every suboptimal arm and the residual1−\(K−1\)​β1\-\(K\-1\)\\betatoi⋆i^\{\\star\}; this ispβp^\{\\beta\}\. Its value is

V​\(pβ\)=\(1−\(K−1\)​β\)​μ⋆\+β​∑i≠i⋆μi=μ⋆−β​∑i≠i⋆Δi\.V\(p^\{\\beta\}\)=\(1\-\(K\-1\)\\beta\)\\mu\_\{\\star\}\+\\beta\\sum\_\{i\\neq i^\{\\star\}\}\\mu\_\{i\}=\\mu\_\{\\star\}\-\\beta\\sum\_\{i\\neq i^\{\\star\}\}\\Delta\_\{i\}\.Sincepβp^\{\\beta\}is the unique value maximizer at fairness levelβ\\betaandV​\(pβ\)V\(p^\{\\beta\}\)is strictly decreasing inβ\\betawheni⋆i^\{\\star\}is unique, no point on the curve is dominated\. Conversely, any Pareto\-efficientppwithϕ​\(p\)=β\\phi\(p\)=\\betamust equalpβp^\{\\beta\}\. ∎

### I\.15Proof of Corollary[16](https://arxiv.org/html/2607.22935#Thmtheorem16)

We match DQ\-UCB’s guarantee to the integral Pareto frontier and divide byTT\.

###### Proof\.

The best fair integral allocation for floormmassignsmmpulls to each suboptimal arm and all remaining pulls toi⋆i^\{\\star\}, which is the integral version ofpm/Tp^\{m/T\}on the continuous Pareto frontier\. Theorem[12](https://arxiv.org/html/2607.22935#Thmtheorem12)bounds DQ\-UCB’s regret against this allocation; dividing byTTgives convergence of average reward toV​\(pm/T\)V\(p^\{m/T\}\)at rateO​\(K​log⁡\(K​T\)/T\)O\(\\sqrt\{K\\log\(KT\)/T\}\)\. ∎

### I\.16Proof of Theorem[17](https://arxiv.org/html/2607.22935#Thmtheorem17)

We embed the residual rounds as a MOSS game of horizonRR, giving theC​K​R\+KC\\sqrt\{KR\}\+Kbound and, via doubling, the unknown\-RRcase\.

###### Proof\.

Fairness is immediate: the mandatory schedule of BDQ\-UCB is unchanged, so Theorem[3](https://arxiv.org/html/2607.22935#Thmtheorem3)\(i\) applies verbatim\. IfR<KR<K, the fair regret is at mostR≤K​RR\\leq\\sqrt\{KR\}deterministically and the bound holds with anyC≥1C\\geq 1; assumeR≥KR\\geq K\.

The positions of the residual rounds are deterministic given the block structure and floors: blockbbconsists of its mandatory schedule followed byRbR\_\{b\}residual rounds\. Letτ​\(1\)<⋯<τ​\(R\)\\tau\(1\)<\\dots<\\tau\(R\)enumerate the residual rounds, and forr≤Rr\\leq RletAr′=Aτ​\(r\)A^\{\\prime\}\_\{r\}=A\_\{\\tau\(r\)\}andXr′X^\{\\prime\}\_\{r\}denote the arm pulled and the reward observed at therrth residual round\. The residual rule of BDQ\-MOSS is a function of\(A1′,X1′,…,Ar−1′,Xr−1′\)\(A^\{\\prime\}\_\{1\},X^\{\\prime\}\_\{1\},\\dots,A^\{\\prime\}\_\{r\-1\},X^\{\\prime\}\_\{r\-1\}\)only, and, because rewards are independent across pulls and identically distributed within each arm, the conditional law ofXr′X^\{\\prime\}\_\{r\}given the residual past andAr′=iA^\{\\prime\}\_\{r\}=iisνi\\nu\_\{i\}, regardless of how many mandatory pulls occurred in between\. Hence the process\(Ar′,Xr′\)r≤R\(A^\{\\prime\}\_\{r\},X^\{\\prime\}\_\{r\}\)\_\{r\\leq R\}has exactly the law of the MOSS algorithm with horizon parameterRRinteracting with the bandit\(ν1,…,νK\)\(\\nu\_\{1\},\\dots,\\nu\_\{K\}\)forRRrounds\. By Lemma[2](https://arxiv.org/html/2607.22935#Thmtheorem2), the blockwise fair regret of BDQ\-MOSS equals∑i≠i⋆Δi​Nires​\(R\)=∑r=1RΔAr′\\sum\_\{i\\neq i^\{\\star\}\}\\Delta\_\{i\}N^\{\\mathrm\{res\}\}\_\{i\}\(R\)=\\sum\_\{r=1\}^\{R\}\\Delta\_\{A^\{\\prime\}\_\{r\}\}, the pseudo\-regret of the embedded game\. The distribution\-free guarantee for MOSS\(Audibert and Bubeck[2009](https://arxiv.org/html/2607.22935#bib.bib2)\)\(see alsoLattimore and Szepesvári[2020](https://arxiv.org/html/2607.22935#bib.bib26), Chapter 9\) bounds its expectation byC​K​RC\\sqrt\{KR\}for a universal constantCC, with theKKinitialization pulls contributing at mostKK; this proves the upper bound\. The matchingΩ​\(K​R\)\\Omega\(\\sqrt\{KR\}\)is Theorem[4](https://arxiv.org/html/2607.22935#Thmtheorem4), andK​R≥K\\sqrt\{KR\}\\geq KforR≥KR\\geq K, so the additiveKKdoes not affect the rate\.

If the floors are revealed only at block starts,RRis unknown in advance\. Run the residual rule in phasesj=0,1,2,…j=0,1,2,\\dots, where phasejjspans the next2j2^\{j\}residual rounds, restarting the residual statistics and using horizon parameter2j2^\{j\}within the phase\. Each phase is itself an embedded MOSS game by the argument above, so phasejjcontributes expected regret at mostC​K​2j\+KC\\sqrt\{K2^\{j\}\}\+K, and at most⌈log2⁡\(2​R\)⌉\\lceil\\log\_\{2\}\(2R\)\\rceilphases begin, so the total expected fair regret is at mostC′​K​R\+K​⌈log2⁡\(2​R\)⌉C^\{\\prime\}\\sqrt\{KR\}\+K\\lceil\\log\_\{2\}\(2R\)\\rceilfor a universalC′C^\{\\prime\}, preserving the rate up to a logarithmic additive initialization term\. ∎

### I\.17Proof of Proposition[18](https://arxiv.org/html/2607.22935#Thmtheorem18)

We forceΩ​\(K​R\)\\Omega\(\\sqrt\{KR\}\)regret even under positive mandatory exposure, since the mandatory pulls are comparator\-matched and carry no information\.

###### Proof\.

FixK≥2K\\geq 2,R≥KR\\geq K, and an integerM≥0M\\geq 0\. The instance has two blocks: block one has lengthH1=MH\_\{1\}=Mand floor vectorm1=\(M,0,…,0\)m\_\{1\}=\(M,0,\\ldots,0\), so its entire length is mandatory mass on arm11; block two has lengthH2=RH\_\{2\}=Rwith zero floors, so the total residual budget is exactlyRRand the total mandatory budget isMM\. Throughout, arm11is Bernoulli\(1/2\)\(1/2\)under every instance considered\. Three observations drive the argument\. First, becauseH1=m1,1H\_\{1\}=m\_\{1,1\}, every blockwise\-fair policy pulls arm11in every round of block one, and so does the blockwise\-fair comparator; by Lemma[2](https://arxiv.org/html/2607.22935#Thmtheorem2), theseMMpulls cancel from fair regret under every instance\. Second, the law of those observations is the same under all instances, so by the chain rule they contribute zero to the KL divergence between the trajectory distributions of any two instances; all information comes from residual pulls\. Third, under any instance whose unique best arm isvv, every residual pull of an arm other thanvvcosts at least the minimum gap in fair regret\.

Consider firstK≥3K\\geq 3\. LetP0P\_\{0\}give every arm mean1/21/2, and forv∈\{2,…,K\}v\\in\\\{2,\\ldots,K\\\}letPvP\_\{v\}give armvvmean1/2\+ε1/2\+\\varepsilonand every other arm mean1/21/2, withε∈\(0,1/4\]\\varepsilon\\in\(0,1/4\]chosen below\. WriteNvresN\_\{v\}^\{\\mathrm\{res\}\}for the number of residual pulls of armvvandav=𝔼0​\[Nvres\]a\_\{v\}=\\mathbb\{E\}\_\{0\}\[N\_\{v\}^\{\\mathrm\{res\}\}\], so∑v=2Kav≤R\\sum\_\{v=2\}^\{K\}a\_\{v\}\\leq R\. UnderPvP\_\{v\}, fair regret satisfiesRegv≥ε​𝔼v​\[R−Nvres\]\\mathrm\{Reg\}\_\{v\}\\geq\\varepsilon\\,\\mathbb\{E\}\_\{v\}\[R\-N\_\{v\}^\{\\mathrm\{res\}\}\]\. The chain rule givesKL​\(P0π,Pvπ\)=av​kl​\(1/2,1/2\+ε\)≤4​ε2​av\\mathrm\{KL\}\(P\_\{0\}^\{\\pi\},P\_\{v\}^\{\\pi\}\)=a\_\{v\}\\,\\mathrm\{kl\}\(1/2,1/2\+\\varepsilon\)\\leq 4\\varepsilon^\{2\}a\_\{v\}, and Pinsker’s inequality yields𝔼v​\[Nvres\]≤av\+R​ε​2​av\\mathbb\{E\}\_\{v\}\[N\_\{v\}^\{\\mathrm\{res\}\}\]\\leq a\_\{v\}\+R\\varepsilon\\sqrt\{2a\_\{v\}\}\. Averaging over theK−1K\-1alternatives and applying Cauchy–Schwarz,∑v=2Kav≤\(K−1\)​R\\sum\_\{v=2\}^\{K\}\\sqrt\{a\_\{v\}\}\\leq\\sqrt\{\(K\-1\)R\},

1K−1​∑v=2KRegv≥ε​R​\(1−1K−1−ε​2​RK−1\)\.\\frac\{1\}\{K\-1\}\\sum\_\{v=2\}^\{K\}\\mathrm\{Reg\}\_\{v\}\\geq\\varepsilon R\\\!\\left\(1\-\\frac\{1\}\{K\-1\}\-\\varepsilon\\sqrt\{\\frac\{2R\}\{K\-1\}\}\\right\)\.Takeε=\(4​2\)−1​\(K−1\)/R\\varepsilon=\(4\\sqrt\{2\}\)^\{\-1\}\\sqrt\{\(K\-1\)/R\}, which satisfiesε≤1/4\\varepsilon\\leq 1/4becauseR≥K\>\(K−1\)/2R\\geq K\>\(K\-1\)/2\. Thenε​2​R/\(K−1\)=1/4\\varepsilon\\sqrt\{2R/\(K\-1\)\}=1/4, and1−1/\(K−1\)≥1/21\-1/\(K\-1\)\\geq 1/2forK≥3K\\geq 3, so the average regret is at least

ε​R4=\(K−1\)​R16​2≥K​R32,\\frac\{\\varepsilon R\}\{4\}=\\frac\{\\sqrt\{\(K\-1\)R\}\}\{16\\sqrt\{2\}\}\\geq\\frac\{\\sqrt\{KR\}\}\{32\},usingK−1≥K/2K\-1\\geq K/2\. Some instance in the family therefore forces fair regret at leastK​R/32\\sqrt\{KR\}/32\.

Consider nowK=2K=2\. Arm11remains Bernoulli\(1/2\)\(1/2\)under both instances, and arm22is Bernoulli\(1/2\+ε\)\(1/2\+\\varepsilon\)underP\+P^\{\+\}and Bernoulli\(1/2−ε\)\(1/2\-\\varepsilon\)underP−P^\{\-\}; the mandatory pulls of arm11are again uninformative and comparator\-matched\. LetA=\{N1res≥R/2\}A=\\\{N\_\{1\}^\{\\mathrm\{res\}\}\\geq R/2\\\}\. UnderP\+P^\{\+\}the best arm is22withΔ1=ε\\Delta\_\{1\}=\\varepsilon, soRegP\+≥ε​𝔼\+​\[N1res\]≥ε​\(R/2\)​P\+​\(A\)\\mathrm\{Reg\}\_\{P^\{\+\}\}\\geq\\varepsilon\\,\\mathbb\{E\}^\{\+\}\[N\_\{1\}^\{\\mathrm\{res\}\}\]\\geq\\varepsilon\(R/2\)\\,P^\{\+\}\(A\); underP−P^\{\-\}the best arm is11withΔ2=ε\\Delta\_\{2\}=\\varepsilon, soRegP−≥ε​𝔼−​\[R−N1res\]≥ε​\(R/2\)​P−​\(Ac\)\\mathrm\{Reg\}\_\{P^\{\-\}\}\\geq\\varepsilon\\,\\mathbb\{E\}^\{\-\}\[R\-N\_\{1\}^\{\\mathrm\{res\}\}\]\\geq\\varepsilon\(R/2\)\\,P^\{\-\}\(A^\{c\}\)\. By the Bretagnolle–Huber inequality,

P\+​\(A\)\+P−​\(Ac\)≥12​exp⁡\(−KL​\(P\+,π,P−,π\)\),P^\{\+\}\(A\)\+P^\{\-\}\(A^\{c\}\)\\ \\geq\\ \\tfrac\{1\}\{2\}\\exp\\\!\\bigl\(\-\\mathrm\{KL\}\(P^\{\+,\\pi\},P^\{\-,\\pi\}\)\\bigr\),and by the chain ruleKL​\(P\+,π,P−,π\)≤𝔼\+​\[N2res\]​kl​\(1/2\+ε,1/2−ε\)≤16​ε2​R\\mathrm\{KL\}\(P^\{\+,\\pi\},P^\{\-,\\pi\}\)\\leq\\mathbb\{E\}^\{\+\}\[N\_\{2\}^\{\\mathrm\{res\}\}\]\\,\\mathrm\{kl\}\(1/2\+\\varepsilon,\\,1/2\-\\varepsilon\)\\leq 16\\varepsilon^\{2\}Rforε≤1/4\\varepsilon\\leq 1/4, sincekl​\(1/2\+ε,1/2−ε\)=2​ε​log⁡1\+2​ε1−2​ε≤16​ε2\\mathrm\{kl\}\(1/2\+\\varepsilon,1/2\-\\varepsilon\)=2\\varepsilon\\log\\frac\{1\+2\\varepsilon\}\{1\-2\\varepsilon\}\\leq 16\\varepsilon^\{2\}in that range\. Choosingε=\(16​R\)−1/2≤1/4\\varepsilon=\(16R\)^\{\-1/2\}\\leq 1/4makes the exponent at most11, so

RegP\+\+RegP−\\displaystyle\\mathrm\{Reg\}\_\{P^\{\+\}\}\+\\mathrm\{Reg\}\_\{P^\{\-\}\}≥ε​R4​e−1=e−1​R16\\displaystyle\\geq\\frac\{\\varepsilon R\}\{4\}\\,e^\{\-1\}=\\frac\{e^\{\-1\}\\sqrt\{R\}\}\{16\}=Ω​\(R\)=Ω​\(K​R\)\.\\displaystyle=\\Omega\(\\sqrt\{R\}\)=\\Omega\(\\sqrt\{KR\}\)\.
In every case, some instance in the family forces fair regretΩ​\(K​R\)\\Omega\(\\sqrt\{KR\}\)even though the overall instance contains positive mandatory exposureMM, which proves the claim with a universal constant\. ∎

### I\.18Proof of Theorem[19](https://arxiv.org/html/2607.22935#Thmtheorem19)

We derive the instance\-dependentlog⁡R\\log Rlower bound by a change of measure against the instance that lifts armiiaboveμ⋆\\mu\_\{\\star\}\.

###### Proof\.

Fix an instanceν\\nuof the template family, an armi≠1i\\neq 1withΔi\>0\\Delta\_\{i\}\>0, andε∈\(0,1−μ⋆\)\\varepsilon\\in\(0,1\-\\mu\_\{\\star\}\)\. Letν′\\nu^\{\\prime\}agree withν\\nuexcept that armiihas meanμ⋆\+ε\\mu\_\{\\star\}\+\\varepsilon; thenν′\\nu^\{\\prime\}belongs to the family, and armiiis its unique best arm\. WriteRegν​\(R\)\\mathrm\{Reg\}\_\{\\nu\}\(R\)for the expected fair regret ofπ\\piunderν\\nuat residual budgetRR\.

All mandatory pulls are on arm11, whose law is the same underν\\nuandν′\\nu^\{\\prime\}, so by the chain rule for KL divergence the trajectory laws satisfy

KL​\(Pν,Pν′\)=𝔼ν​\[Nires\]​kl​\(μi,μ⋆\+ε\)\.\\mathrm\{KL\}\\bigl\(P\_\{\\nu\},P\_\{\\nu^\{\\prime\}\}\\bigr\)=\\mathbb\{E\}\_\{\\nu\}\\bigl\[N^\{\\mathrm\{res\}\}\_\{i\}\\bigr\]\\,\\mathrm\{kl\}\(\\mu\_\{i\},\\mu\_\{\\star\}\+\\varepsilon\)\.LetA=\{Nires≥R/2\}A=\\\{N^\{\\mathrm\{res\}\}\_\{i\}\\geq R/2\\\}\. Underν\\nu, by Lemma[2](https://arxiv.org/html/2607.22935#Thmtheorem2), the expected fair regret is at leastΔi​𝔼ν​\[Nires\]≥Δi​\(R/2\)​Pν​\(A\)\\Delta\_\{i\}\\,\\mathbb\{E\}\_\{\\nu\}\[N^\{\\mathrm\{res\}\}\_\{i\}\]\\geq\\Delta\_\{i\}\(R/2\)P\_\{\\nu\}\(A\); underν′\\nu^\{\\prime\}, every residual pull of an arm other thaniihas gap at leastε\\varepsilon\(arm11has mean1/2≤μ⋆1/2\\leq\\mu\_\{\\star\}\), so the expected fair regret is at leastε​𝔼ν′​\[R−Nires\]≥ε​\(R/2\)​Pν′​\(Ac\)\\varepsilon\\,\\mathbb\{E\}\_\{\\nu^\{\\prime\}\}\[R\-N^\{\\mathrm\{res\}\}\_\{i\}\]\\geq\\varepsilon\(R/2\)P\_\{\\nu^\{\\prime\}\}\(A^\{c\}\)\. Withcε=min⁡\(Δi,ε\)c\_\{\\varepsilon\}=\\min\(\\Delta\_\{i\},\\varepsilon\), the Bretagnolle–Huber inequality gives

Regν​\(R\)\+Regν′​\(R\)\\displaystyle\\mathrm\{Reg\}\_\{\\nu\}\(R\)\+\\mathrm\{Reg\}\_\{\\nu^\{\\prime\}\}\(R\)≥cε​R2​\(Pν​\(A\)\+Pν′​\(Ac\)\)\\displaystyle\\ \\geq\\ \\frac\{c\_\{\\varepsilon\}R\}\{2\}\\bigl\(P\_\{\\nu\}\(A\)\+P\_\{\\nu^\{\\prime\}\}\(A^\{c\}\)\\bigr\)≥cε​R4​exp⁡\(−𝔼ν​\[Nires\]​kl​\(μi,μ⋆\+ε\)\),\\displaystyle\\ \\geq\\ \\frac\{c\_\{\\varepsilon\}R\}\{4\}\\exp\\Bigl\(\-\\mathbb\{E\}\_\{\\nu\}\\bigl\[N^\{\\mathrm\{res\}\}\_\{i\}\\bigr\]\\,\\mathrm\{kl\}\(\\mu\_\{i\},\\mu\_\{\\star\}\+\\varepsilon\)\\Bigr\),and rearranging,

𝔼ν​\[Nires\]≥log⁡\(cε​R/4\)−log⁡\(Regν​\(R\)\+Regν′​\(R\)\)kl​\(μi,μ⋆\+ε\)\.\\mathbb\{E\}\_\{\\nu\}\\bigl\[N^\{\\mathrm\{res\}\}\_\{i\}\\bigr\]\\ \\geq\\ \\frac\{\\log\\bigl\(c\_\{\\varepsilon\}R/4\\bigr\)\-\\log\\bigl\(\\mathrm\{Reg\}\_\{\\nu\}\(R\)\+\\mathrm\{Reg\}\_\{\\nu^\{\\prime\}\}\(R\)\\bigr\)\}\{\\mathrm\{kl\}\(\\mu\_\{i\},\\mu\_\{\\star\}\+\\varepsilon\)\}\.Fixa∈\(0,1\]a\\in\(0,1\]\. Uniform fastness applied toν\\nuand toν′\\nu^\{\\prime\}givesRegν​\(R\)\+Regν′​\(R\)≤Ra\\mathrm\{Reg\}\_\{\\nu\}\(R\)\+\\mathrm\{Reg\}\_\{\\nu^\{\\prime\}\}\(R\)\\leq R^\{a\}for all sufficiently largeRR, so

lim infR→∞𝔼ν​\[Nires\]log⁡R≥1−akl​\(μi,μ⋆\+ε\)\.\\liminf\_\{R\\to\\infty\}\\frac\{\\mathbb\{E\}\_\{\\nu\}\[N^\{\\mathrm\{res\}\}\_\{i\}\]\}\{\\log R\}\\ \\geq\\ \\frac\{1\-a\}\{\\mathrm\{kl\}\(\\mu\_\{i\},\\mu\_\{\\star\}\+\\varepsilon\)\}\.Lettinga↓0a\\downarrow 0and thenε↓0\\varepsilon\\downarrow 0, using the continuity ofkl​\(μi,⋅\)\\mathrm\{kl\}\(\\mu\_\{i\},\\cdot\)on\(0,1\)\(0,1\), proves the per\-arm claim\. The regret consequence follows from Lemma[2](https://arxiv.org/html/2607.22935#Thmtheorem2):Regν​\(R\)≥∑i≠i⋆Δi​𝔼ν​\[Nires\]≥∑i≠1:Δi\>0Δi​𝔼ν​\[Nires\]\\mathrm\{Reg\}\_\{\\nu\}\(R\)\\geq\\sum\_\{i\\neq i^\{\\star\}\}\\Delta\_\{i\}\\,\\mathbb\{E\}\_\{\\nu\}\[N^\{\\mathrm\{res\}\}\_\{i\}\]\\geq\\sum\_\{i\\neq 1:\\,\\Delta\_\{i\}\>0\}\\Delta\_\{i\}\\,\\mathbb\{E\}\_\{\\nu\}\[N^\{\\mathrm\{res\}\}\_\{i\}\], dropping the nonnegative arm\-11term when arm11is suboptimal, and summing the per\-arm bounds\. ∎

### I\.19Proof of Corollary[20](https://arxiv.org/html/2607.22935#Thmtheorem20)

We embed the residual rounds as a kl\-UCB\+\+game to attain the exact instance\-dependent constant\.

###### Proof\.

The mandatory schedule is unchanged, so feasibility is Theorem[3](https://arxiv.org/html/2607.22935#Thmtheorem3)\(i\)\. Exactly as in the proof of Theorem[17](https://arxiv.org/html/2607.22935#Thmtheorem17), the residual rounds with residual\-only statistics form a standardKK\-armed Bernoulli bandit of horizonRR, played here by kl\-UCB\+\+with horizon parameterRR, and by Lemma[2](https://arxiv.org/html/2607.22935#Thmtheorem2)the blockwise fair regret equals the pseudo\-regret of that embedded game\. kl\-UCB\+\+is simultaneously minimax\-optimal and asymptotically optimal for these models\(Ménard and Garivier[2017](https://arxiv.org/html/2607.22935#bib.bib1)\): the embedded pseudo\-regret is at mostC​K​RC\\sqrt\{KR\}in expectation for a universal constantCC, plus at mostKKfor initialization, and on every fixed instance the pull counts satisfylim supR→∞𝔼​\[Nires\]/log⁡R≤1/kl​\(μi,μ⋆\)\\limsup\_\{R\\to\\infty\}\\mathbb\{E\}\[N^\{\\mathrm\{res\}\}\_\{i\}\]/\\log R\\leq 1/\\mathrm\{kl\}\(\\mu\_\{i\},\\mu\_\{\\star\}\)for every suboptimal armii\. Multiplying byΔi\\Delta\_\{i\}and summing gives the displayed limsup\. The instance\-wise regret is thereforeO​\(log⁡R\)O\(\\log R\), so BDQ\-KL is uniformly fast wheneverMMgrows at most polynomially inRR, and for every armi≠1i\\neq 1of the template family the per\-arm limsup meets the liminf of Theorem[19](https://arxiv.org/html/2607.22935#Thmtheorem19): the instance\-dependent characterization is exact arm by arm\. WhenRRis not known in advance, the doubling scheme of Theorem[17](https://arxiv.org/html/2607.22935#Thmtheorem17)preserves the minimax bound; the exact asymptotic constant is specific to knownRR, since restarting inflates the logarithmic term\. ∎

### I\.20Proof of Theorem[22](https://arxiv.org/html/2607.22935#Thmtheorem22)

We show OG\-BDQ\-UCB is exactly group\-feasible and bound its regret against the slack\-feasible per\-block optimum by3​K​B\+4​Hmax​2​L​B3KB\+4H\_\{\\max\}\\sqrt\{2LB\}\.

###### Proof\.

WritePb=\{y≥0:∑i∈gyi≥fb,g\+t​∀g,∑iyi=Hb−2​K\}P\_\{b\}=\\\{y\\geq 0:\\sum\_\{i\\in g\}y\_\{i\}\\geq f\_\{b,g\}\+t\\ \\forall g,\\ \\sum\_\{i\}y\_\{i\}=H\_\{b\}\-2K\\\}for the block\-bbplan polytope, assumed nonempty, andyb⋆∈arg​maxy∈Pb⁡⟨μ,y⟩y\_\{b\}^\{\\star\}\\in\\operatorname\*\{arg\\,max\}\_\{y\\in P\_\{b\}\}\\langle\\mu,y\\rangle\.

*Feasibility and accounting\.*The planyby\_\{b\}has group totals at leastfb,g\+tf\_\{b,g\}\+tand ceiling budget∑i⌈yb,i⌉≤∑iyb,i\+K=Hb−K\\sum\_\{i\}\\lceil y\_\{b,i\}\\rceil\\leq\\sum\_\{i\}y\_\{b,i\}\+K=H\_\{b\}\-K, so Theorem[6](https://arxiv.org/html/2607.22935#Thmtheorem6)producesnbn\_\{b\}withnb,i∈\{⌊yb,i⌋,⌈yb,i⌉\}n\_\{b,i\}\\in\\\{\\lfloor y\_\{b,i\}\\rfloor,\\lceil y\_\{b,i\}\\rceil\\\}, every group floor met, and∑inb,i≤Hb−K\\sum\_\{i\}n\_\{b,i\}\\leq H\_\{b\}\-K\. Together with theKKinitialization pulls, the block therefore hasℓb:=Hb−K−∑inb,i\\ell\_\{b\}:=H\_\{b\}\-K\-\\sum\_\{i\}n\_\{b,i\}leftover rounds with0≤ℓb≤2​K0\\leq\\ell\_\{b\}\\leq 2K, the upper bound because∑inb,i≥∑i⌊yb,i⌋≥\(Hb−2​K\)−K\\sum\_\{i\}n\_\{b,i\}\\geq\\sum\_\{i\}\\lfloor y\_\{b,i\}\\rfloor\\geq\(H\_\{b\}\-2K\)\-K\. Every group floor is met in every block deterministically\.

*Concentration\.*Letℰ\\mathcal\{E\}be the event of the proof of Theorem[12](https://arxiv.org/html/2607.22935#Thmtheorem12): for every armiiand every countn≤Tn\\leq T, the empirical mean afternnobservations is within2​L/n\\sqrt\{2L/n\}ofμi\\mu\_\{i\};ℙ​\(ℰ\)≥1−η\\mathbb\{P\}\(\\mathcal\{E\}\)\\geq 1\-\\eta\. At the block\-bbplanning step every arm has received one initialization pull in each of blocks1,…,b1,\\dots,b, soNi≥bN\_\{i\}\\geq b, and onℰ\\mathcal\{E\}the clipped index satisfiesμi≤Ui\\mu\_\{i\}\\leq U\_\{i\}\(becauseμ^i\+2​L/Ni≥μi\\widehat\{\\mu\}\_\{i\}\+\\sqrt\{2L/N\_\{i\}\}\\geq\\mu\_\{i\}andμi≤1\\mu\_\{i\}\\leq 1\) and

Ui−μi≤min\(1,22​L/Ni\)≤min\(1,22​L/b\)=:ρb,U\_\{i\}\-\\mu\_\{i\}\\ \\leq\\ \\min\\Bigl\(1,\\ 2\\sqrt\{2L/N\_\{i\}\}\\Bigr\)\\ \\leq\\ \\min\\Bigl\(1,\\ 2\\sqrt\{2L/b\}\\Bigr\)\\ =:\\ \\rho\_\{b\},uniformly over arms\.

*Per\-block regret\.*Onℰ\\mathcal\{E\}, optimism and LP optimality ofyby\_\{b\}give

⟨μ,yb⋆⟩\\displaystyle\\langle\\mu,y\_\{b\}^\{\\star\}\\rangle≤⟨U,yb⋆⟩≤⟨U,yb⟩\\displaystyle\\ \\leq\\ \\langle U,y\_\{b\}^\{\\star\}\\rangle\\ \\leq\\ \\langle U,y\_\{b\}\\rangle≤⟨μ,yb⟩\+ρb​∑iyb,i≤⟨μ,yb⟩\+ρb​Hb\.\\displaystyle\\ \\leq\\ \\langle\\mu,y\_\{b\}\\rangle\+\\rho\_\{b\}\\sum\_\{i\}y\_\{b,i\}\\ \\leq\\ \\langle\\mu,y\_\{b\}\\rangle\+\\rho\_\{b\}H\_\{b\}\.The realized mean value of blockbbis at least⟨μ,nb⟩\\langle\\mu,n\_\{b\}\\rangle\(initialization and leftover pulls contribute nonnegatively\), and⟨μ,nb⟩≥⟨μ,yb⟩−K\\langle\\mu,n\_\{b\}\\rangle\\geq\\langle\\mu,y\_\{b\}\\rangle\-Kbecausenbn\_\{b\}andyby\_\{b\}differ by less than one in at mostKKcoordinates andμi≤1\\mu\_\{i\}\\leq 1\. Hence the block\-bbcontribution toOPTad−V\\mathrm\{OPT\}^\{\\mathrm\{ad\}\}\-Vis at most

\[⟨μ,yb⋆⟩\+2​K​μ⋆\]−\[⟨μ,yb⟩−K\]≤ρb​Hb\+3​K\.\\bigl\[\\langle\\mu,y\_\{b\}^\{\\star\}\\rangle\+2K\\mu\_\{\\star\}\\bigr\]\-\\bigl\[\\langle\\mu,y\_\{b\}\\rangle\-K\\bigr\]\\ \\leq\\ \\rho\_\{b\}H\_\{b\}\+3K\.
*Summation\.*Since∑b=1Bρb≤2​2​L​∑b=1Bb−1/2≤4​2​L​B\\sum\_\{b=1\}^\{B\}\\rho\_\{b\}\\leq 2\\sqrt\{2L\}\\sum\_\{b=1\}^\{B\}b^\{\-1/2\}\\leq 4\\sqrt\{2LB\},

OPTad−V≤3​K​B\+Hmax​∑b=1Bρb≤3​K​B\+4​Hmax​2​L​B\\mathrm\{OPT\}^\{\\mathrm\{ad\}\}\-V\\ \\leq\\ 3KB\+H\_\{\\max\}\\sum\_\{b=1\}^\{B\}\\rho\_\{b\}\\ \\leq\\ 3KB\+4H\_\{\\max\}\\sqrt\{2LB\}onℰ\\mathcal\{E\}, which is the claim; withHb=T/BH\_\{b\}=T/Bthe second term is4​2​T​L/B4\\sqrt\{2\}\\,T\\sqrt\{L/B\}\. ∎

### I\.21Proof of Proposition[23](https://arxiv.org/html/2607.22935#Thmtheorem23)

We bound the cost of the built\-in slack byO​\(B\)O\(B\)using a Slater\-type interior point\.

###### Proof\.

WriteVbfracV^\{\\mathrm\{frac\}\}\_\{b\}for the unslacked optimum andVb⋆=maxy∈Pb⁡⟨μ,y⟩\+2​K​μ⋆V^\{\\star\}\_\{b\}=\\max\_\{y\\in P\_\{b\}\}\\langle\\mu,y\\rangle\+2K\\mu\_\{\\star\}\. IfHb<max⁡\{t/σb,2​K/κb\}H\_\{b\}<\\max\\\{t/\\sigma\_\{b\},2K/\\kappa\_\{b\}\\\}the claim is trivial, because both values lie in\[0,Hb\]\[0,H\_\{b\}\]; so assume otherwise and set

θ:=max⁡\{tσb​Hb,2​Kκb​Hb\}∈\(0,1\]\.\\theta\\ :=\\ \\max\\Bigl\\\{\\frac\{t\}\{\\sigma\_\{b\}H\_\{b\}\},\\ \\frac\{2K\}\{\\kappa\_\{b\}H\_\{b\}\}\\Bigr\\\}\\ \\in\\ \(0,1\]\.Lety∗y^\{\\ast\}attainVbfracV^\{\\mathrm\{frac\}\}\_\{b\}and definex:=\(1−θ\)​y∗\+θ​zx:=\(1\-\\theta\)y^\{\\ast\}\+\\theta z\. For every group,∑i∈gxi≥\(1−θ\)​fb,g\+θ​\(fb,g\+σb​Hb\)=fb,g\+θ​σb​Hb≥fb,g\+t\\sum\_\{i\\in g\}x\_\{i\}\\geq\(1\-\\theta\)f\_\{b,g\}\+\\theta\(f\_\{b,g\}\+\\sigma\_\{b\}H\_\{b\}\)=f\_\{b,g\}\+\\theta\\sigma\_\{b\}H\_\{b\}\\geq f\_\{b,g\}\+t; for the budget,∑ixi≤\(1−θ\)​Hb\+θ​\(1−κb\)​Hb=Hb−θ​κb​Hb≤Hb−2​K\\sum\_\{i\}x\_\{i\}\\leq\(1\-\\theta\)H\_\{b\}\+\\theta\(1\-\\kappa\_\{b\}\)H\_\{b\}=H\_\{b\}\-\\theta\\kappa\_\{b\}H\_\{b\}\\leq H\_\{b\}\-2K\. Paddingxxwith additional mass on a best arm until∑ixi=Hb−2​K\\sum\_\{i\}x\_\{i\}=H\_\{b\}\-2Kpreserves the floors and does not decrease⟨μ,x⟩\\langle\\mu,x\\rangle, so the padded plan lies inPbP\_\{b\}and

Vb⋆≥⟨μ,x⟩\+2​K​μ⋆≥\(1−θ\)​⟨μ,y∗⟩≥Vbfrac−θ​Hb,V^\{\\star\}\_\{b\}\\ \\geq\\ \\langle\\mu,x\\rangle\+2K\\mu\_\{\\star\}\\ \\geq\\ \(1\-\\theta\)\\langle\\mu,y^\{\\ast\}\\rangle\\ \\geq\\ V^\{\\mathrm\{frac\}\}\_\{b\}\-\\theta H\_\{b\},using⟨μ,y∗⟩≤Hb\\langle\\mu,y^\{\\ast\}\\rangle\\leq H\_\{b\}\. Sinceθ​Hb=max⁡\{t/σb,2​K/κb\}\\theta H\_\{b\}=\\max\\\{t/\\sigma\_\{b\},2K/\\kappa\_\{b\}\\\}, the claim follows\. ∎

### I\.22Proof of Proposition[24](https://arxiv.org/html/2607.22935#Thmtheorem24)

We turn blockwise group\-fair regret into an exact per\-pull LP\-duality ledger and instantiate its disjoint form\.

###### Proof\.

For any primal\-feasibleyy\(that is,y≥0y\\geq 0,∑i∈gyi≥fb,g\\sum\_\{i\\in g\}y\_\{i\}\\geq f\_\{b,g\}for every group, and∑iyi=Hb\\sum\_\{i\}y\_\{i\}=H\_\{b\}\), dual feasibility andλb≥0\\lambda\_\{b\}\\geq 0give

⟨μ,y⟩\\displaystyle\\langle\\mu,y\\rangle≤∑i\(ωb−∑g∋iλb,g\)​yi=ωb​Hb−∑gλb,g​∑i∈gyi\\displaystyle\\ \\leq\\ \\sum\_\{i\}\\Bigl\(\\omega\_\{b\}\-\\sum\_\{g\\ni i\}\\lambda\_\{b,g\}\\Bigr\)y\_\{i\}\\ =\\ \\omega\_\{b\}H\_\{b\}\-\\sum\_\{g\}\\lambda\_\{b,g\}\\sum\_\{i\\in g\}y\_\{i\}≤ωb​Hb−∑gfb,g​λb,g,\\displaystyle\\ \\leq\\ \\omega\_\{b\}H\_\{b\}\-\\sum\_\{g\}f\_\{b,g\}\\lambda\_\{b,g\},soVbfrac≤ωb​Hb−∑gfb,g​λb,gV^\{\\mathrm\{frac\}\}\_\{b\}\\leq\\omega\_\{b\}H\_\{b\}\-\\sum\_\{g\}f\_\{b,g\}\\lambda\_\{b,g\}, with equality for a dual\-optimal pair by strong duality, the block program being feasible by assumption and bounded\. Define the credit of roundτ∈ℬb\\tau\\in\\mathcal\{B\}\_\{b\}ascτ=∑g∋Aτ:dg​\(τ\)\>0λb,gc\_\{\\tau\}=\\sum\_\{g\\ni A\_\{\\tau\}:\\,d\_\{g\}\(\\tau\)\>0\}\\lambda\_\{b,g\}\. A pull of an arm inggwhiledg\>0d\_\{g\}\>0lowersdgd\_\{g\}by exactly one, and blockwise group fairness drives every deficit fromfb,gf\_\{b,g\}to0inside the block, so groupggis credited on exactlyfb,gf\_\{b,g\}rounds and∑τ∈ℬbcτ=∑gfb,g​λb,g\\sum\_\{\\tau\\in\\mathcal\{B\}\_\{b\}\}c\_\{\\tau\}=\\sum\_\{g\}f\_\{b,g\}\\lambda\_\{b,g\}\. Since\|ℬb\|=Hb\|\\mathcal\{B\}\_\{b\}\|=H\_\{b\},

Vbfrac−∑τ∈ℬbμAτ\\displaystyle V^\{\\mathrm\{frac\}\}\_\{b\}\-\\sum\_\{\\tau\\in\\mathcal\{B\}\_\{b\}\}\\mu\_\{A\_\{\\tau\}\}≤∑τ∈ℬb\(ωb−μAτ\)−∑τ∈ℬbcτ\\displaystyle\\ \\leq\\ \\sum\_\{\\tau\\in\\mathcal\{B\}\_\{b\}\}\\bigl\(\\omega\_\{b\}\-\\mu\_\{A\_\{\\tau\}\}\\bigr\)\-\\sum\_\{\\tau\\in\\mathcal\{B\}\_\{b\}\}c\_\{\\tau\}=∑τ∈ℬb\[rAτ\+∑g∋Aτ:dg​\(τ\)=0λb,g\],\\displaystyle\\ =\\ \\sum\_\{\\tau\\in\\mathcal\{B\}\_\{b\}\}\\Bigl\[r\_\{A\_\{\\tau\}\}\+\\sum\_\{g\\ni A\_\{\\tau\}:\\,d\_\{g\}\(\\tau\)=0\}\\lambda\_\{b,g\}\\Bigr\],where the equality splitsωb−μAτ=rAτ\+∑g∋Aτλb,g\\omega\_\{b\}\-\\mu\_\{A\_\{\\tau\}\}=r\_\{A\_\{\\tau\}\}\+\\sum\_\{g\\ni A\_\{\\tau\}\}\\lambda\_\{b,g\}and subtracts the credit\. Nonnegativity of every bracket is dual feasibility \(rAτ≥0r\_\{A\_\{\\tau\}\}\\geq 0\) together withλb≥0\\lambda\_\{b\}\\geq 0\. When\(ωb,λb\)\(\\omega\_\{b\},\\lambda\_\{b\}\)is dual optimal, the first display is an equality, hence so is the ledger, and complementary slackness givesri=0r\_\{i\}=0for every arm in the support of an optimal fractional plan\.

For the disjoint instantiation used by Theorem[9](https://arxiv.org/html/2607.22935#Thmtheorem9), takeωb=μ⋆\\omega\_\{b\}=\\mu\_\{\\star\}andλb,g=μ⋆−μg⋆≥0\\lambda\_\{b,g\}=\\mu\_\{\\star\}\-\\mu^\{\\star\}\_\{g\}\\geq 0\. Dual feasibility holds becauseωb−λb,g=μg⋆≥μi\\omega\_\{b\}\-\\lambda\_\{b,g\}=\\mu^\{\\star\}\_\{g\}\\geq\\mu\_\{i\}fori∈gi\\in gandωb=μ⋆≥μi\\omega\_\{b\}=\\mu\_\{\\star\}\\geq\\mu\_\{i\}for ungrouped arms; the dual value isHb​μ⋆−∑gfb,g​\(μ⋆−μg⋆\)=VbfracH\_\{b\}\\mu\_\{\\star\}\-\\sum\_\{g\}f\_\{b,g\}\(\\mu\_\{\\star\}\-\\mu^\{\\star\}\_\{g\}\)=V^\{\\mathrm\{frac\}\}\_\{b\}, so the pair is optimal; and the reduced costs areri=μg⋆−μi=Δ~ir\_\{i\}=\\mu^\{\\star\}\_\{g\}\-\\mu\_\{i\}=\\widetilde\{\\Delta\}\_\{i\}fori∈gi\\in gandri=Δir\_\{i\}=\\Delta\_\{i\}for ungrouped arms, recovering exactly the two columns bounded in the proof of Theorem[9](https://arxiv.org/html/2607.22935#Thmtheorem9)\. ∎

### I\.23Proof of Proposition[25](https://arxiv.org/html/2607.22935#Thmtheorem25)

We construct a two\-group overlap instance on which any within\-group index rule paysΩ​\(T\)\\Omega\(T\), because the optimal cover accepts one arm’s lower mean to satisfy two floors at once\.

###### Proof\.

Four armsa,b,c,sa,b,c,swith Bernoulli means0\.70,0\.70,0\.65,0\.900\.70,0\.70,0\.65,0\.90; groupsg1=\{a,c\}g\_\{1\}=\\\{a,c\\\}andg2=\{b,c\}g\_\{2\}=\\\{b,c\\\}, so the arm degree ist=2t=2;BBblocks of lengthHHdivisible by33, each with floorsfb,g1=fb,g2=H/3f\_\{b,g\_\{1\}\}=f\_\{b,g\_\{2\}\}=H/3\. Because each group reads the full mass of its members, placingH/3H/3onccsatisfies both floors simultaneously, and the fractional optimum puts the remaining2​H/32H/3onss:

Vbfrac=\(0\.65\+2⋅0\.90\)​H3=2\.45​H3per block\.V^\{\\mathrm\{frac\}\}\_\{b\}\\ =\\ \\bigl\(0\.65\+2\\cdot 0\.90\\bigr\)\\tfrac\{H\}\{3\}\\ =\\ 2\.45\\,\\tfrac\{H\}\{3\}\\qquad\\text\{per block\.\}
Consider any rule of the stated class, with indicesUi=min⁡\{1,μ^i\+2​L/Ni\}U\_\{i\}=\\min\\\{1,\\widehat\{\\mu\}\_\{i\}\+\\sqrt\{2L/N\_\{i\}\}\\\}, and work on the concentration eventℰ\\mathcal\{E\}of the proof of Theorem[12](https://arxiv.org/html/2607.22935#Thmtheorem12)\. A covering selection ofccin either group withn≥1n\\geq 1prior samples forcesUc≥Ua≥μaU\_\{c\}\\geq U\_\{a\}\\geq\\mu\_\{a\}\(or the same withbb\), hence0\.65\+2​2​L/n≥0\.700\.65\+2\\sqrt\{2L/n\}\\geq 0\.70andn≤3200​Ln\\leq 3200L; a surplus selection ofccforcesUc≥Us≥0\.90U\_\{c\}\\geq U\_\{s\}\\geq 0\.90, hencen≤128​Ln\\leq 128L\. Since every selection incrementsNcN\_\{c\}, armccis pulled at most1\+3200​L1\+3200Ltimes over the entire horizon\. Likewise a surplus selection ofaaorbbforcesn≤200​Ln\\leq 200L\(gap0\.200\.20toss\), so each incurs at most1\+200​L1\+200Lsurplus pulls\. Outside these at most3\+3600​L3\+3600Lexceptional pulls, every block allocates exactlyH/3H/3covering pulls ofaaforg1g\_\{1\},H/3H/3ofbbforg2g\_\{2\}, andH/3H/3surplus pulls ofss, for a block value of\(0\.70\+0\.70\+0\.90\)​H/3=2\.30​H/3\(0\.70\+0\.70\+0\.90\)H/3=2\.30\\,H/3and a per\-block gap of0\.15​H/3=H/200\.15\\,H/3=H/20\. Every block’s regret against its fractional optimum is nonnegative, each exceptional pull distorts value by at most one, and feasibility is exact throughout since each floor is served by exactlyH/3H/3covering pulls; hence onℰ\\mathcal\{E\}the total regret is at leastT/20−\(3\+3600​L\)T/20\-\(3\+3600L\), which is the claim with a universal constant\. The failure is structural rather than statistical: the rule learns every mean correctly and still paysΩ​\(T\)\\Omega\(T\), because the optimal cover acceptscc’s lower mean in exchange for satisfying two floors with one budget, and no within\-group index comparison represents that exchange\. ∎

### I\.24Proof of Proposition[26](https://arxiv.org/html/2607.22935#Thmtheorem26)

We show P\-BDQ\-UCB is pathwise feasible under the initial cover\-slack condition, via a one\-step slack bound and the terminal cover\-rounding guard\.

###### Proof\.

Fix a block withHb−mc​\(fb\)\>2​KH\_\{b\}\-\\mathrm\{mc\}\(f\_\{b\}\)\>2K, soS​\(0\)\>2​KS\(0\)\>2Kand the guard does not fire at the block start\. Every pull lowersrrby one andmc\\mathrm\{mc\}by at most one\. For the second claim, monotonicity givesmc​\(d\+​\(A\)\)≤mc​\(d\)\\mathrm\{mc\}\(d^\{\+\}\(A\)\)\\leq\\mathrm\{mc\}\(d\); conversely, letπd\\pi\_\{d\}be an optimal solution of the covering dual

mc​\(d\)=max⁡\{⟨π,d⟩:π≥0,∑g∋iπg≤1​∀i\},\\mathrm\{mc\}\(d\)=\\max\\Bigl\\\{\\langle\\pi,d\\rangle:\\ \\pi\\geq 0,\\ \\textstyle\\sum\_\{g\\ni i\}\\pi\_\{g\}\\leq 1\\ \\forall i\\Bigr\\\},whose feasible region does not depend on the demands\. Then

mc​\(d\)−mc​\(d\+​\(A\)\)\\displaystyle\\mathrm\{mc\}\(d\)\-\\mathrm\{mc\}\(d^\{\+\}\(A\)\)≤⟨πd,d−d\+​\(A\)⟩=∑g∋A:dg≥1πd,g\\displaystyle\\ \\leq\\ \\langle\\pi\_\{d\},\\,d\-d^\{\+\}\(A\)\\rangle\\ =\\\!\\\!\\sum\_\{g\\ni A:\\,d\_\{g\}\\geq 1\}\\\!\\\!\\pi\_\{d,g\}≤∑g∋Aπd,g≤1\\displaystyle\\ \\leq\\ \\sum\_\{g\\ni A\}\\pi\_\{d,g\}\\ \\leq 1by the dual constraint at the pulled arm, using thatπd\\pi\_\{d\}remains feasible for the demandsd\+​\(A\)d^\{\+\}\(A\)\. HenceS​\(τ\+1\)−S​\(τ\)∈\[−1,0\]S\(\\tau\+1\)\-S\(\\tau\)\\in\[\-1,0\]in the sampled phase\. SinceS​\(τ\)≤r​\(τ\)S\(\\tau\)\\leq r\(\\tau\)always, the guard fires no later than the round withr​\(τ\)=2​Kr\(\\tau\)=2K; firing cannot occur at the block start, so the firing state has a pre\-guard predecessor with slack above2​K2K, whenceS​\(τc\)\>2​K−1≥KS\(\\tau\_\{c\}\)\>2K\-1\\geq K\. Rounding an optimal fractional coverw​\(τc\)w\(\\tau\_\{c\}\)up coordinatewise raises at mostKKcoordinates, so

∑i⌈wi​\(τc\)⌉\\displaystyle\\sum\_\{i\}\\lceil w\_\{i\}\(\\tau\_\{c\}\)\\rceil≤mc​\(d​\(τc\)\)\+K=r​\(τc\)−S​\(τc\)\+K\\displaystyle\\ \\leq\\ \\mathrm\{mc\}\(d\(\\tau\_\{c\}\)\)\+K\\ =\\ r\(\\tau\_\{c\}\)\-S\(\\tau\_\{c\}\)\+K≤r​\(τc\)−K\+1≤r​\(τc\)\.\\displaystyle\\ \\leq\\ r\(\\tau\_\{c\}\)\-K\+1\\ \\leq\\ r\(\\tau\_\{c\}\)\.The rounded cover therefore fits in the remaining budget; executing it drives every remaining deficit to zero, and leftover rounds, spent on the index argmax, cannot violate one\-sided floor constraints\. Every group floor of every block is thus satisfied, pathwise and deterministically\. ∎

### I\.25Proof of Proposition[27](https://arxiv.org/html/2607.22935#Thmtheorem27)

We verify the two descent inequalities automatically on disjoint systems, where the covering value is linear\.

###### Proof\.

Disjointness makes the covering value linear: no arm serves two groups, somc​\(d\)=∑gdg\\mathrm\{mc\}\(d\)=\\sum\_\{g\}d\_\{g\}\. At a pre\-guard state, primal feasibility ofy^\\widehat\{y\}givesℙ​\(A∈g\)=∑i∈gy^i/r≥dg/r\\mathbb\{P\}\(A\\in g\)=\\sum\_\{i\\in g\}\\widehat\{y\}\_\{i\}/r\\geq d\_\{g\}/rfor every deficient group, so

𝔼​\[mc​\(d\+​\(A\)\)\]\\displaystyle\\mathbb\{E\}\\bigl\[\\mathrm\{mc\}\(d^\{\+\}\(A\)\)\\bigr\]=∑g:dg≥1\(dg−ℙ​\(A∈g\)\)\\displaystyle=\\sum\_\{g:\\,d\_\{g\}\\geq 1\}\\bigl\(d\_\{g\}\-\\mathbb\{P\}\(A\\in g\)\\bigr\)≤\(1−1r\)​∑gdg=r−1r​mc​\(d\),\\displaystyle\\leq\\Bigl\(1\-\\frac\{1\}\{r\}\\Bigr\)\\sum\_\{g\}d\_\{g\}=\\frac\{r\-1\}\{r\}\\,\\mathrm\{mc\}\(d\),which is \([3](https://arxiv.org/html/2607.22935#A6.E3)\), with no event required\.

For \([4](https://arxiv.org/html/2607.22935#A6.E4)\), writeμg⋆=maxi∈g⁡μi\\mu^\{\\star\}\_\{g\}=\\max\_\{i\\in g\}\\mu\_\{i\}andλg=μ⋆−μg⋆≥0\\lambda\_\{g\}=\\mu\_\{\\star\}\-\\mu^\{\\star\}\_\{g\}\\geq 0\. On the pre\-guard regionr\>mc​\(d\)\+2​K≥∑gdgr\>\\mathrm\{mc\}\(d\)\+2K\\geq\\sum\_\{g\}d\_\{g\}, the residual value is linear:

Ψμ​\(r,d\)=μ⋆​r−∑gλg​dg,\\Psi\_\{\\mu\}\(r,d\)=\\mu\_\{\\star\}r\-\\sum\_\{g\}\\lambda\_\{g\}d\_\{g\},because for any feasibleyywith group totalsYg≥dgY\_\{g\}\\geq d\_\{g\}we have⟨μ,y⟩≤∑gμg⋆​Yg\+μ⋆​\(r−∑gYg\)\\langle\\mu,y\\rangle\\leq\\sum\_\{g\}\\mu^\{\\star\}\_\{g\}Y\_\{g\}\+\\mu\_\{\\star\}\(r\-\\sum\_\{g\}Y\_\{g\}\), the coefficient ofYgY\_\{g\}isμg⋆−μ⋆≤0\\mu^\{\\star\}\_\{g\}\-\\mu\_\{\\star\}\\leq 0, and the bound is attained atYg=dgY\_\{g\}=d\_\{g\}\. Both states\(r,d\)\(r,d\)and\(r−1,d\+​\(A\)\)\(r\-1,d^\{\+\}\(A\)\)lie in this region, since∑gd\+​\(A\)g≥∑gdg−1\\sum\_\{g\}d^\{\+\}\(A\)\_\{g\}\\geq\\sum\_\{g\}d\_\{g\}\-1\. Hence, withp=y^/rp=\\widehat\{y\}/rand𝔼​\[d\+​\(A\)g\]=dg−ℙ​\(A∈g\)\\mathbb\{E\}\[d^\{\+\}\(A\)\_\{g\}\]=d\_\{g\}\-\\mathbb\{P\}\(A\\in g\)for deficient groups, linearity gives

𝔼​\[Ψμ​\(r−1,d\+​\(A\)\)\+μA\]−Ψμ​\(r,d\)\\displaystyle\\mathbb\{E\}\\bigl\[\\Psi\_\{\\mu\}\(r\-1,d^\{\+\}\(A\)\)\+\\mu\_\{A\}\\bigr\]\-\\Psi\_\{\\mu\}\(r,d\)=−∑ipi​rˇi,\\displaystyle=\-\\sum\_\{i\}p\_\{i\}\\,\\check\{r\}\_\{i\},rˇi\\displaystyle\\check\{r\}\_\{i\}=μ⋆−μi−∑g∋i:dg≥1λg\.\\displaystyle=\\mu\_\{\\star\}\-\\mu\_\{i\}\-\\\!\\\!\\sum\_\{g\\ni i:\\,d\_\{g\}\\geq 1\}\\\!\\\!\\lambda\_\{g\}\.It therefore suffices thatrˇi≤ρi\\check\{r\}\_\{i\}\\leq\\rho\_\{i\}for every support arm ofy^\\widehat\{y\}\. The optimistic program has the explicit optimal dualωU=maxj⁡Uj\\omega^\{U\}=\\max\_\{j\}U\_\{j\}andλgU=ωU−maxj∈g⁡Uj≥0\\lambda^\{U\}\_\{g\}=\\omega^\{U\}\-\\max\_\{j\\in g\}U\_\{j\}\\geq 0: it is feasible becauseωU−λgU=maxj∈g⁡Uj≥Ui\\omega^\{U\}\-\\lambda^\{U\}\_\{g\}=\\max\_\{j\\in g\}U\_\{j\}\\geq U\_\{i\}fori∈gi\\in gandωU≥Ui\\omega^\{U\}\\geq U\_\{i\}for ungrouped arms, and its objectiveωU​r−∑gλgU​dg=∑gdg​maxj∈g⁡Uj\+\(r−∑gdg\)​ωU\\omega^\{U\}r\-\\sum\_\{g\}\\lambda^\{U\}\_\{g\}d\_\{g\}=\\sum\_\{g\}d\_\{g\}\\max\_\{j\\in g\}U\_\{j\}\+\(r\-\\sum\_\{g\}d\_\{g\}\)\\,\\omega^\{U\}matches the primal optimum, so the pair is optimal\. By complementary slackness, every support arm of every optimal plan has zero reduced cost under this dual: a grouped support armi∈gi\\in gsatisfiesUi=maxj∈g⁡UjU\_\{i\}=\\max\_\{j\\in g\}U\_\{j\}whenλgU\>0\\lambda^\{U\}\_\{g\}\>0, andUi=ωUU\_\{i\}=\\omega^\{U\}otherwise; an ungrouped support arm satisfiesUi=ωUU\_\{i\}=\\omega^\{U\}\. OnℰL\\mathcal\{E\}\_\{L\}, a within\-group maximizeri∈gi\\in gsatisfiesμi\+ρi≥Ui≥Uj≥μj\\mu\_\{i\}\+\\rho\_\{i\}\\geq U\_\{i\}\\geq U\_\{j\}\\geq\\mu\_\{j\}for the group’s best true armjj, soμg⋆−μi≤ρi\\mu^\{\\star\}\_\{g\}\-\\mu\_\{i\}\\leq\\rho\_\{i\}; a global maximizer satisfiesμ⋆−μi≤ρi\\mu\_\{\\star\}\-\\mu\_\{i\}\\leq\\rho\_\{i\}the same way\. In the first caserˇi=μg⋆−μi\\check\{r\}\_\{i\}=\\mu^\{\\star\}\_\{g\}\-\\mu\_\{i\}ifggis deficient andrˇi=μ⋆−μi\\check\{r\}\_\{i\}=\\mu\_\{\\star\}\-\\mu\_\{i\}otherwise; in every caserˇi≤max⁡\{μg⋆−μi,μ⋆−μi\}≤ρi\\check\{r\}\_\{i\}\\leq\\max\\\{\\mu^\{\\star\}\_\{g\}\-\\mu\_\{i\},\\mu\_\{\\star\}\-\\mu\_\{i\}\\\}\\leq\\rho\_\{i\}, because a within\-group maximizer also satisfiesμ⋆−μi≤ρi\\mu\_\{\\star\}\-\\mu\_\{i\}\\leq\\rho\_\{i\}whenever it is a global maximizer, andμg⋆−μi≤μ⋆−μi\\mu^\{\\star\}\_\{g\}\-\\mu\_\{i\}\\leq\\mu\_\{\\star\}\-\\mu\_\{i\}always\. This gives \([4](https://arxiv.org/html/2607.22935#A6.E4)\) onℰL\\mathcal\{E\}\_\{L\}\.

The final claim of the proposition is immediate:∑gfb,g≤\(1−σ\)​Hb\\sum\_\{g\}f\_\{b,g\}\\leq\(1\-\\sigma\)H\_\{b\}is the initial\-slack clause becausemc​\(fb\)=∑gfb,g\\mathrm\{mc\}\(f\_\{b\}\)=\\sum\_\{g\}f\_\{b,g\}, andσ​Hb\>2​K\\sigma H\_\{b\}\>2Kis the block\-start guard condition of Theorem[29](https://arxiv.org/html/2607.22935#Thmtheorem29)\. ∎

### I\.26Proof of Theorem[29](https://arxiv.org/html/2607.22935#Thmtheorem29)

We prove the conditionalO~​\(K​T\)\\widetilde\{O\}\(\\sqrt\{KT\}\)guarantee for P\-BDQ\-UCB by combining slack concentration with the true\-value descent inequality\.

###### Proof\.

Fix a blockbb\. Writer​\(τ\)r\(\\tau\)andd​\(τ\)d\(\\tau\)for the remaining budget and integer deficits before roundτ\\tau,mc\\mathrm\{mc\}andS​\(τ\)=r​\(τ\)−mc​\(d​\(τ\)\)S\(\\tau\)=r\(\\tau\)\-\\mathrm\{mc\}\(d\(\\tau\)\)as in the main text, and

Ψ\(τ\)=Ψμ\(r\(τ\),d\(τ\)\)=max\{⟨μ,y⟩:y≥0,\\displaystyle\\Psi\(\\tau\)=\\Psi\_\{\\mu\}\(r\(\\tau\),d\(\\tau\)\)=\\max\\Bigl\\\{\\langle\\mu,y\\rangle:\\ y\\geq 0,∑i∈gyi≥dg​\(τ\)​∀g,\\displaystyle\\textstyle\\sum\_\{i\\in g\}y\_\{i\}\\geq d\_\{g\}\(\\tau\)\\ \\forall g,∑iyi=r\(τ\)\},\\displaystyle\\sum\_\{i\}y\_\{i\}=r\(\\tau\)\\Bigr\\\},so thatΨ​\(0\)=Vbfrac\\Psi\(0\)=V^\{\\mathrm\{frac\}\}\_\{b\}\. The margin clause givesS​\(0\)≥σ​HbS\(0\)\\geq\\sigma H\_\{b\}, and withσ​Hb\>2​K\\sigma H\_\{b\}\>2Kthe hypothesisHb−mc​\(fb\)\>2​KH\_\{b\}\-\\mathrm\{mc\}\(f\_\{b\}\)\>2Kof Proposition[26](https://arxiv.org/html/2607.22935#Thmtheorem26)holds\. Feasibility, the one\-step boundS​\(τ\+1\)−S​\(τ\)∈\[−1,0\]S\(\\tau\+1\)\-S\(\\tau\)\\in\[\-1,0\]during the sampled phase, and the deterministic guard fit are therefore available throughout; letτc\\tau\_\{c\}be the guard’s firing round, soS​\(τc\)∈\(2​K−1,2​K\]S\(\\tau\_\{c\}\)\\in\(2K\-1,2K\]and the residual polytope is nonempty at every sampled round\.

*Stopped\-process convention\.*The descent condition asserts \([3](https://arxiv.org/html/2607.22935#A6.E3)\)–\([4](https://arxiv.org/html/2607.22935#A6.E4)\) at pre\-guard states reached onℰL\\mathcal\{E\}\_\{L\}\. Formally, every conditional\-expectation step below is applied to the process stopped at the first pre\-guard time whose state violates either inequality; onℰL\\mathcal\{E\}\_\{L\}that time is not beforeτc\\tau\_\{c\}, and every path outsideℰL\\mathcal\{E\}\_\{L\}is charged to the failure budget at the end, at cost at mostTT\.

*Slack concentration\.*Beforeτc\\tau\_\{c\}, letpi​\(τ\)=y^i​\(τ\)/r​\(τ\)p\_\{i\}\(\\tau\)=\\widehat\{y\}\_\{i\}\(\\tau\)/r\(\\tau\)\. By the cover\-contraction inequality \([3](https://arxiv.org/html/2607.22935#A6.E3)\),

𝔼​\[mc​\(d​\(τ\+1\)\)∣ℱτ\]≤r​\(τ\)−1r​\(τ\)​mc​\(d​\(τ\)\),\\mathbb\{E\}\[\\mathrm\{mc\}\(d\(\\tau\+1\)\)\\mid\\mathcal\{F\}\_\{\\tau\}\]\\leq\\frac\{r\(\\tau\)\-1\}\{r\(\\tau\)\}\\mathrm\{mc\}\(d\(\\tau\)\),soM​\(τ\)=S​\(τ\)/r​\(τ\)M\(\\tau\)=S\(\\tau\)/r\(\\tau\)is a submartingale before the guard:𝔼​\[S​\(τ\+1\)\]≥r​\(τ\)−1−r​\(τ\)−1r​\(τ\)​mc​\(d​\(τ\)\)=r​\(τ\)−1r​\(τ\)​S​\(τ\)\\mathbb\{E\}\[S\(\\tau\+1\)\]\\geq r\(\\tau\)\-1\-\\frac\{r\(\\tau\)\-1\}\{r\(\\tau\)\}\\mathrm\{mc\}\(d\(\\tau\)\)=\\frac\{r\(\\tau\)\-1\}\{r\(\\tau\)\}S\(\\tau\)\. Since\|S​\(τ\+1\)−S​\(τ\)\|≤1\|S\(\\tau\+1\)\-S\(\\tau\)\|\\leq 1by Proposition[26](https://arxiv.org/html/2607.22935#Thmtheorem26)and0≤S​\(τ\)≤r​\(τ\)0\\leq S\(\\tau\)\\leq r\(\\tau\), its one\-step increments satisfy\|M​\(τ\+1\)−M​\(τ\)\|≤2/\(r​\(τ\)−1\)\|M\(\\tau\+1\)\-M\(\\tau\)\|\\leq 2/\(r\(\\tau\)\-1\)wheneverr​\(τ\)\>1r\(\\tau\)\>1\. WithM​\(0\)≥σM\(0\)\\geq\\sigma, Azuma’s inequality and∑s≥r1/\(s−1\)2≤2/r\\sum\_\{s\\geq r\}1/\(s\-1\)^\{2\}\\leq 2/rimply that for every pre\-guard state withr​\(τ\)≥r⋆=⌈64​L/σ2⌉r\(\\tau\)\\geq r^\{\\star\}=\\lceil 64L/\\sigma^\{2\}\\rceil,

ℙ​\(M​\(τ\)≤σ/2\)≤exp⁡\(−σ2​r​\(τ\)/64\)≤η2​K​T\.\\mathbb\{P\}\(M\(\\tau\)\\leq\\sigma/2\)\\leq\\exp\(\-\\sigma^\{2\}r\(\\tau\)/64\)\\leq\\frac\{\\eta\}\{2KT\}\.A union bound over all rounds and blocks gives, with probability at least1−η1\-\\eta,M​\(τ\)\>σ/2M\(\\tau\)\>\\sigma/2for every such pre\-guard state\. On this event, whenever additionallyr​\(τ\)≥\(4​K\+2\)/σr\(\\tau\)\\geq\(4K\+2\)/\\sigma, we haveS​\(τ\)\>2​KS\(\\tau\)\>2K, so the guard cannot yet fire\. Hence

r​\(τc\)≤64​Lσ2\+4​K\+2σ\+1\.r\(\\tau\_\{c\}\)\\leq\\frac\{64L\}\{\\sigma^\{2\}\}\+\\frac\{4K\+2\}\{\\sigma\}\+1\.
*Regret in the sampled phase\.*OnℰL\\mathcal\{E\}\_\{L\}, the clipped indices satisfyμi≤Ui≤μi\+ρi\\mu\_\{i\}\\leq U\_\{i\}\\leq\\mu\_\{i\}\+\\rho\_\{i\}withρi=min⁡\{1,2​2​L/\(Ni∨1\)\}\\rho\_\{i\}=\\min\\\{1,2\\sqrt\{2L/\(N\_\{i\}\\vee 1\)\}\\\}, and the true\-value descent inequality \([4](https://arxiv.org/html/2607.22935#A6.E4)\) gives, for each pre\-guard sampled round,

𝔼​\[Ψ​\(τ\)−Ψ​\(τ\+1\)−μAτ∣ℱτ\]≤𝔼​\[ρAτ∣ℱτ\]\.\\mathbb\{E\}\[\\Psi\(\\tau\)\-\\Psi\(\\tau\+1\)\-\\mu\_\{A\_\{\\tau\}\}\\mid\\mathcal\{F\}\_\{\\tau\}\]\\leq\\mathbb\{E\}\[\\rho\_\{A\_\{\\tau\}\}\\mid\\mathcal\{F\}\_\{\\tau\}\]\.Telescoping overτ<τc\\tau<\\tau\_\{c\}, usingΨ​\(τc\)≤r​\(τc\)\\Psi\(\\tau\_\{c\}\)\\leq r\(\\tau\_\{c\}\), and noting that rewards in the committed tail are nonnegative, yields the pathwise inequality

Vbfrac−∑τ∈ℬbμAτ≤∑τ<τc\(Ψ​\(τ\)−Ψ​\(τ\+1\)−μAτ\)\+r​\(τc\)V^\{\\mathrm\{frac\}\}\_\{b\}\-\\sum\_\{\\tau\\in\\mathcal\{B\}\_\{b\}\}\\mu\_\{A\_\{\\tau\}\}\\leq\\sum\_\{\\tau<\\tau\_\{c\}\}\\bigl\(\\Psi\(\\tau\)\-\\Psi\(\\tau\+1\)\-\\mu\_\{A\_\{\\tau\}\}\\bigr\)\+r\(\\tau\_\{c\}\)for the block\. Taking expectations with the stopped\-process convention, summing over blocks, and using the tail bound above, the only remaining term is the sum of confidence radii over actually pulled arms\. For each arm,∑n=1Ni​\(T\)min⁡\{1,2​2​L/n\}≤1\+4​2​L​Ni​\(T\)\\sum\_\{n=1\}^\{N\_\{i\}\(T\)\}\\min\\\{1,2\\sqrt\{2L/n\}\\\}\\leq 1\+4\\sqrt\{2LN\_\{i\}\(T\)\}, so by Cauchy–Schwarz,

∑τ=1TρAτ≤K\+4​2​L​∑iNi​\(T\)≤K\+4​2​K​T​L\.\\sum\_\{\\tau=1\}^\{T\}\\rho\_\{A\_\{\\tau\}\}\\leq K\+4\\sqrt\{2L\}\\sum\_\{i\}\\sqrt\{N\_\{i\}\(T\)\}\\leq K\+4\\sqrt\{2KTL\}\.The reward\-concentration eventℰL\\mathcal\{E\}\_\{L\}fails with probability at mostη\\eta, the slack\-concentration event fails with probability at mostη\\eta, and the regret on either failure is at mostTT\. Thus

OPTfrac−𝔼​\[V\]\\displaystyle\\mathrm\{OPT\}^\{\\mathrm\{frac\}\}\-\\mathbb\{E\}\[V\]≤K\+4​2​K​T​L\+2​η​T\\displaystyle\\leq K\+4\\sqrt\{2KTL\}\+2\\eta T\+B​\(64​Lσ2\+4​K\+2σ\+1\),\\displaystyle\\quad\+B\\left\(\\frac\{64L\}\{\\sigma^\{2\}\}\+\\frac\{4K\+2\}\{\\sigma\}\+1\\right\),which is the claimed bound after absorbing constants intoCC\. ∎

### I\.27Proof of the Static Best\-Fair Comparator

###### Proposition 31\.

Letm∈\{0,1,…,⌊T/K⌋\}m\\in\\\{0,1,\\dots,\\lfloor T/K\\rfloor\\\}\. Among all integer vectorsn=\(n1,…,nK\)n=\(n\_\{1\},\\dots,n\_\{K\}\)satisfyingni≥mn\_\{i\}\\geq mand∑i=1Kni=T\\sum\_\{i=1\}^\{K\}n\_\{i\}=T, the reward∑i=1Kni​μi\\sum\_\{i=1\}^\{K\}n\_\{i\}\\mu\_\{i\}is maximized by assigningmmpulls to every armi≠i⋆i\\neq i^\{\\star\}and assigning all remaining pulls toi⋆i^\{\\star\}\.

###### Proof\.

Letnnbe any feasible fair allocation\. Sinceni≥mn\_\{i\}\\geq m, defineri=ni−m≥0r\_\{i\}=n\_\{i\}\-m\\geq 0, so that∑i=1Kri=T−K​m\\sum\_\{i=1\}^\{K\}r\_\{i\}=T\-Km\. The expected reward ofnnis

∑i=1Kni​μi=m​∑i=1Kμi\+∑i=1Kri​μi\.\\sum\_\{i=1\}^\{K\}n\_\{i\}\\mu\_\{i\}=m\\sum\_\{i=1\}^\{K\}\\mu\_\{i\}\+\\sum\_\{i=1\}^\{K\}r\_\{i\}\\mu\_\{i\}\.The first term is fixed across all feasible allocations, so maximizing reward is equivalent to maximizing∑iri​μi\\sum\_\{i\}r\_\{i\}\\mu\_\{i\}subject tori≥0r\_\{i\}\\geq 0and∑iri=T−K​m\\sum\_\{i\}r\_\{i\}=T\-Km\. This is maximized by placing all residual mass on an arm with largest mean, namelyi⋆i^\{\\star\}:ri⋆=T−K​mr\_\{i^\{\\star\}\}=T\-Kmandri=0r\_\{i\}=0fori≠i⋆i\\neq i^\{\\star\}, equivalentlyni⋆=T−\(K−1\)​mn\_\{i^\{\\star\}\}=T\-\(K\-1\)mandni=mn\_\{i\}=mfori≠i⋆i\\neq i^\{\\star\}\. ∎

### I\.28Proof of the Blockwise Comparator

###### Proposition 32\.

For each blockbb, among all integer allocations satisfyingnb,i≥mb,in\_\{b,i\}\\geq m\_\{b,i\}and∑inb,i=Hb\\sum\_\{i\}n\_\{b,i\}=H\_\{b\}, reward is maximized by assigningmb,im\_\{b,i\}pulls to every arm and all residual pulls to a best arm\.

###### Proof\.

For a fixed block, writenb,i=mb,i\+rb,in\_\{b,i\}=m\_\{b,i\}\+r\_\{b,i\}withrb,i≥0r\_\{b,i\}\\geq 0\. The block reward is∑imb,i​μi\+∑irb,i​μi\\sum\_\{i\}m\_\{b,i\}\\mu\_\{i\}\+\\sum\_\{i\}r\_\{b,i\}\\mu\_\{i\}\. The first term is fixed by the block floors, and the residual mass∑irb,i=Hb−∑imb,i\\sum\_\{i\}r\_\{b,i\}=H\_\{b\}\-\\sum\_\{i\}m\_\{b,i\}is maximized by placing it on a best arm\. Summing over blocks givesOPT𝐦​\(T\)\\mathrm\{OPT\}\_\{\\mathbf\{m\}\}\(T\)\. ∎

### I\.29Proof of Corollary[33](https://arxiv.org/html/2607.22935#Thmtheorem33)

###### Corollary 33\(Static case as a special case\)\.

TakingB=1B=1,H1=TH\_\{1\}=T, andm1,i=mm\_\{1,i\}=mfor every arm reduces Theorem[3](https://arxiv.org/html/2607.22935#Thmtheorem3)to Theorem[12](https://arxiv.org/html/2607.22935#Thmtheorem12), up to replacingR=T−K​mR=T\-Kmby the looser boundTT\.

###### Proof\.

WithB=1B=1,H1=TH\_\{1\}=T, andm1,i=mm\_\{1,i\}=mfor everyii, the blockwise constraint collapses toNi​\(T\)≥mN\_\{i\}\(T\)\\geq m, and BDQ\-UCB executes DQ\-UCB exactly\. The blockwise comparator \(Lemma[2](https://arxiv.org/html/2607.22935#Thmtheorem2)\) becomesOPTm​\(T\)\\mathrm\{OPT\}\_\{m\}\(T\)\(Lemma[10](https://arxiv.org/html/2607.22935#Thmtheorem10)\), and the residual budget isR=T−K​mR=T\-Km\. Substituting into Theorem[3](https://arxiv.org/html/2607.22935#Thmtheorem3)\(ii\)–\(iii\) yields the bounds of Theorem[12](https://arxiv.org/html/2607.22935#Thmtheorem12)\(ii\)–\(iii\), loosened by replacingRRwithTT\. The expected\-regret bound follows by settingη=1/T\\eta=1/T\. ∎

### I\.30Proof of Proposition[34](https://arxiv.org/html/2607.22935#Thmtheorem34)

###### Proposition 34\(Separation from block\-independent floors\)\.

Fixα∈\(0,1/2\]\\alpha\\in\(0,1/2\], an even number of blocksBB, and a block lengthHHsuch thatα​H\\alpha His an integer\. Consider two arms withμ1=1\\mu\_\{1\}=1andμ2=1−Δ\\mu\_\{2\}=1\-\\Delta, whereΔ\>0\\Delta\>0\. In odd blocks, requiremb,2=α​Hm\_\{b,2\}=\\alpha Handmb,1=0m\_\{b,1\}=0; in even blocks, requiremb,1=mb,2=0m\_\{b,1\}=m\_\{b,2\}=0\. Then: \(i\) no single final\-horizon global floor can encode these blockwise constraints, since an allocation may satisfy the exact aggregate count of arm 2 while violating every odd\-block requirement; \(ii\) any block\-independent per\-block lower boundg2​Hg\_\{2\}Hfor arm 2 either violates the odd\-block requirement ifg2<αg\_\{2\}<\\alpha, or, ifg2≥αg\_\{2\}\\geq\\alpha, incurs at leastα​Δ2​T\\tfrac\{\\alpha\\Delta\}\{2\}Tadditional blockwise regret relative to the best blockwise\-fair comparator, whereT=B​HT=BH; and \(iii\) BDQ\-UCB satisfies all blockwise constraints exactly and has regretO​\(K​R​log⁡\(K​T\)\)O\(\\sqrt\{KR\\log\(KT\)\}\)\.

###### Proof\.

The aggregate arm\-2 requirement is\(B/2\)​α​H=α​T/2\(B/2\)\\alpha H=\\alpha T/2\. A global final\-count constraint enforcing this total cannot distinguish odd\-block placements from even\-block placements, proving \(i\)\. For \(ii\), a block\-independent surrogate with per\-block lower boundg2​Hg\_\{2\}Heither under\-enforces odd\-block requirements \(ifg2<αg\_\{2\}<\\alpha\) or forces at leastα​H\\alpha Hpulls of the suboptimal arm in each of theB/2B/2even blocks \(ifg2≥αg\_\{2\}\\geq\\alpha\), incurring at least\(B/2\)​α​H​Δ=α​Δ​T/2\(B/2\)\\alpha H\\Delta=\\alpha\\Delta T/2additional regret\. Part \(iii\) is Theorem[3](https://arxiv.org/html/2607.22935#Thmtheorem3)\. ∎