1 Introduction↩︎

The stochastic multi-armed bandit problem models sequential decision-making under uncertainty over a horizon of \(T\) rounds. A learner faces \(k\) distinct actions (arms), each associated with an unknown probability distribution \(\nu_i\) supported on \(\mathbb{R}\) with mean \(\mu_i\). We denote the problem instance by the vector of distributions \(\nu=(\nu_1,\dots,\nu_k)\) and let \(\mu_\star:=\max_{i\in[k]}\mu_i\) denote the optimal mean. At each round \(t\in[T]\), the learner selects an action \(I_t\in[k]\) according to a policy (an algorithm) \(\mathsf{A}\), which maps the observable history of past actions and rewards to a probability distribution over \([k]:=\{1,\ldots,k\}\), and receives an independent reward \(X_t\sim\nu_{I_t}\). We define the ex-ante reward at round \(t\) as \(m_t:=\mathbb{E}[\mu_{I_t}]\), where the expectation is over both the reward draws and the algorithm’s internal randomization (if any). The learner is evaluated via the arithmetic mean of this sequence, yielding the standard average regret \(R_{T, \textsf{avg}} (\mathsf{A}, \nu) := \mu_\star- \frac{1}{T}\sum_{t=1}^T m_t\) [2].

This utilitarian objective maximizes total payoff, inherently treating early-round exploration as an acceptable amortized cost. When rounds correspond to distinct individuals, such as patients in a clinical trial [3], this amortization inflicts welfare losses on early participants: an algorithm may achieve asymptotically optimal average regret even after assigning zero expected reward to a sizeable fraction of initial users. To guarantee equitable treatment across all users, recent works embed social welfare functions directly into the learning objective. Grounded in the classical axioms of collective welfare, most notably inequality aversion via the Pigou-Dalton transfer principle [4], a principled replacement for the arithmetic mean is the generalized \(p\)-mean. For an ex-ante reward sequence \((m_1,\ldots,m_T)\), with each \(m_t \in \mathbb{R}_{\ge 0}\), it is defined as \[\mathsf{M}_p(m_1,\dots,m_T)\;:=\; \begin{cases} \big(\tfrac1T\sum_{t=1}^T (m_t)^p\big)^{1/p}, & p\neq 0,\\[4pt] \big(\prod_{t=1}^T m_t\big)^{1/T}, & p=0, \end{cases}\] with corresponding \(p\)-mean regret \(R_{T,p}(\mathsf{A},\nu):=\mu^\star-\mathsf{M}_p(m_1,\dots,m_T)\). The parameter \(p\) controls the strictness of the fairness requirement: \(p=1\) recovers classical average regret, \(p\to0\) maximizes the geometric mean (Nash social welfare), and \(p\to-\infty\) approaches the strict Rawlsian maximin ideal. Throughout the paper, we make the following assumption.

This assumption is standard [1], [5], [6] in social welfare applications such as clinical trials, where arms are pre-screened for baseline safety, and the goal is to identify the optimal arm from a non-harmful pool. Furthermore, fairness metrics derived from the geometric mean (e.g., Nash Social Welfare [5]) are only well-defined over non-negative expected values. Note that bounding the expected reward does not preclude negative individual outcomes: a treatment which is beneficial on average (\(\mu_i \ge 0\)) may still induce adverse side effects in specific instances.

In this work, we study the fundamental limits of the strictly fair regime, parameterized by \(q=-p>0\). By convention, if \(m_t=0\) for any \(t\in[T]\), we set \(\mathsf{M}_{-q}(m_1,\dots,m_T)=0\). The challenge of this regime is inverse-power: because negative power means convert small expected rewards into large penalties, the welfare is bottlenecked by the worst single round, \(\mathsf{M}_{-q}(m_1,\dots,m_T)\;\le\;T^{1/q}\,\min_{t\in[T]} m_t\). Consequently, any exploration policy that assigns very low probability to the optimal arm, by driving \(m_t\) toward zero for even a small fraction of rounds, faces an unrecoverable welfare collapse.

1.1 Prior Work and Gaps↩︎

A recent line of work has studied whether classical bandit methods can be adapted to welfare objectives stronger than average reward. [5] initiated this direction for Nash regret (\(p\to0\)), and [6] extended the framework to generalized \(p\)-mean regret for arbitrary \(p\). For the sub-Gaussian model, [1] proposed Welfarist-UCB, which pairs a data-adaptive uniform exploration phase with a subsequent UCB phase – the standard optimistic rule that pulls the arm maximizing \(\widehat\mu_i(t)+c_i(t)\), the empirical mean plus a confidence radius, thereby favoring arms that appear promising or remain uncertain [2]. Uniform exploration ensures that all arms have sufficiently many samples before this optimistic rule is used. This is important for negative-power welfare: rounds with very small ex-ante reward contribute \((m_t)^{-q}\) inside the objective and can dominate the regret. Writing \(q=-p>0\), their algorithm attains \(\widetilde{O}_q\!\left(\frac{\sigma\,k^{(q+1)/2}}{\sqrt{T}}\right)\) regret.¹

This guarantee leaves open the optimal dependence on the number of arms, especially in the strongly fair regime \(q>1\). Uniform exploration assigns the unknown optimal arm only a \(1/k\) share of early pulls. For negative powers, such low selection probabilities are costly: if the optimal arm is the only arm with a positive mean and is selected with probability \(a_t\) at round \(t\), then the corresponding inverse-power contribution scales as \(a_t^{-q}\). Thus, the factor \(k^{(q+1)/2}\) may reflect both genuine statistical difficulty and the inefficiency of exploring all arms symmetrically.

Before this work, the main generally applicable lower bound was the classical average-regret lower bound \(\Omega\!\left(\sigma\sqrt{\frac{k}{T}}\right)\) [2], which extends to all \(p\le1\) by monotonicity of power means. This bound provides an important baseline, but it is not tailored to negative-power welfare. Average regret measures additive losses over time, whereas a negative-power mean can be dominated by rounds in which the ex-ante reward is unusually small. As a result, existing lower bounds did not determine whether the additional dependence on \(k\) incurred by uniform exploration is unavoidable. This leaves the following question:

Resolving this question, especially if the minimax scale remains \(\sqrt{k/T}\) or rises to \(k^{(q+1)/2}/\sqrt{T}\), requires both a sharper lower bound that captures the inverse-power sensitivity to low-reward rounds, and a more efficient algorithm whose exploration rule is not constrained to be uniform.

1.2 Our Contributions↩︎

Throughout, we treat the fairness level \(q = -p \ge 0\) as fixed and characterize the dependence of the regret on the number of arms \(k\) and time horizon \(T\). We establish that the minimax rate is \(k^{q/2}/\sqrt{T}\) by first proving an algorithm-independent lower bound and then designing an algorithm that achieves it up to poly-logarithmic factors.

1. The Fundamental Price of Strong Fairness. First, we show the polynomial dependence on \(k\) is an information-theoretic necessity, and not due to uniform exploration. Suppose each arm \(i \in [k]\) has a \(\sigma\)-sub-Gaussian reward distribution \(\nu_i\) with a non-negative mean \(\mu_i \ge 0\), i.e., \(\mathbb{E}_{X \sim \nu_i}[\exp(\lambda(X - \mu_i))] \le \exp\left(\frac{\sigma^2 \lambda^2}{2}\right)\) for all \(\lambda \in \mathbb{R}\). Define the class \[\mathcal{E}_{\mathsf{SG}}(k, \sigma)^{+} := \left\{ \nu = (\nu_1, \dots, \nu_k) \mid \forall i \in [k],\, \nu_i \text{ is } \sigma\text{-sub-Gaussian with mean } 0 \le \mu_i < \infty \right\}.\]

The minimax \((-q)\)-mean regret over this class is defined as \[\begin{align} \mathfrak{R}_{T,-q}(k,\sigma)\;:=\;\inf_{\mathsf{A}}\;\sup_{\nu\in \mathcal{E}_{\mathsf{SG}}(k, \sigma)^{+}}\; R_{T,-q}(\mathsf{A},\nu),\quad \text{where} \quad R_{T,p}(\mathsf{A},\nu):=\mu^\star-\mathsf{M}_p(m_1,\dots,m_T). \end{align}\] We focus on the case that each \(\mu_i\) and \(\sigma\) are constants that do not scale with \(k\) and \(T\).

We prove this lower bound by considering a class of "needle-in-haystack" type bandit instances that are difficult to distinguish. While our high-level approach is similar to existing regret lower-bound proof techniques for average welfare [2], additional challenges arise due to negative-power welfare. Specifically, we show how it penalizes low selection probabilities. Since the learner rarely pulls the optimal arm at the start, this keeps the ex-ante reward low for many rounds, which is exactly what the negative-power objective penalizes, eventually forcing the lower bound.

Crucially, the lower bound is not specific to negative power means. It follows from a general information-cost inequality (Lemma 16) that lower-bounds the cumulative cost of any fairness-sensitive objective whose welfare is bottlenecked by the rate at which a learner can identify the optimum. We instantiate it here for the \(p\)-mean welfare, where it yields the \(k^{q/2}\) price; the same principle is can be adapted to general bandit settings, e.g., linear bandits [7], [8].

2. Matching the Limit via UCB-HARE Algorithm. Our analysis reveals that uniform exploration is suboptimal in its dependence on \(k\): by locking the optimal arm’s selection probability at \(1/k\), one keeps its selection probability small for an extended duration, thereby incurring an avoidable welfare penalty. We propose UCB-HARE (Harmonic Anchored Rank Exploration), which replaces uniform sampling with "shielded" exploration: it explores a random permutation of the arms via a harmonically decaying schedule, allocating pulls proportionally to \(1/r\) (where \(r\) is an arm’s rank) rather than uniformly. This schedule guarantees the rapid discovery of an intermediate arm with a strictly positive lower confidence bound: our anchor.

The core insight is that defending the welfare objective does not require waiting for the global optimum; the anchor provides a sufficient safety net. Once discovered, the algorithm couples every risky exploration pull in the tail of the permutation with a safe exploitation pull of the anchor. This dynamic pairing shields the ex-ante reward sequence, allowing the algorithm to safely continue its search for the optimal arm without ever dropping below a critical welfare baseline.

By the standard asymptotics \(H_k=\Theta(\log k)\) and \[K_q(k) = \begin{cases} \Theta_q(k), & 0<q<1,\\ \Theta(k\log k), & q=1,\\ \Theta_q(k^q), & q>1. \end{cases} \implies R_{T,-q}(\mathsf{UCB\text{-}HARE},\nu) \le \begin{cases} \widetilde{O}_q\!\left(\sigma\sqrt{k/T}\right), & 0<q<1,\\[2mm] \widetilde{O}\!\left(\sigma\sqrt{k/T}\right), & q=1,\\[2mm] \widetilde{O}_q\!\left(\sigma\sqrt{k^q/T}\right), & q>1. \end{cases}\] Thus, after poly-logarithmic factors are suppressed, \(\mathsf{UCB\text{-}HARE}\)matches the lower bound for every fixed \(q>0\): for \(0<q\le1\), the classical \(\sqrt{k/T}\) term remains dominant, while for \(q>1\) the negative-power objective raises the polynomial dependence to \(k^{q/2}/\sqrt T\).

Comparison with Prior Work. The best known upper bound for \((-q)\)-mean regret is \(\widetilde{O}_q\!\left(\frac{\sigma\,k^{(q+1)/2}}{\sqrt{T}}\right)\), which is achieved by the Welfarist-UCB algorithm [1]. In contrast, \(\mathsf{UCB\text{-}HARE}\)achieve the minimax \(\widetilde{O}_q\!\left(\frac{\sigma\,k^{q/2}}{\sqrt{T}}\right)\) regret. Table 1 summarizes the comparison.

1.3 Related Work: Generalized-Mean Welfare Beyond Bandits↩︎

Nash and generalized-mean welfare are standard objectives in the algorithmic study of fair allocation. The Nash objective – the geometric mean \(\left(\prod_i u_i\right)^{1/n}\), equivalently \(\sum_i\log u_i\) – originates in Nash’s axiomatic treatment of bargaining [9]. The generalized-mean family \(\mathsf{M}_p(u_1,\ldots,u_n)=\left(\frac{1}{n}\sum_{i=1}^n u_i^p\right)^{1/p}\) embeds it in a continuum: \(p=1\) is utilitarian welfare, \(p\to0\) is Nash welfare, and \(p\to-\infty\) is egalitarian max-min welfare, with smaller \(p\) encoding stronger aversion to unequal utility profiles [4], [10]. The objective studied here is thus not specific to bandit learning, but the standard parametric language for interpolating between efficiency and fairness.

In divisible allocation and market models, the Eisenberg–Gale convex program maximizes logarithmic utilities, linking Fisher-market equilibria to Nash-social-welfare maximization via convex duality [11], [12]. The same logarithmic objective underlies proportional fairness in network resource allocation, and the broader \(\alpha\)-fair family interpolates between proportional and max-min fairness, which are equivalent, up to monotone transformations, to the generalized-mean [13]–[15]. In indivisible fair division, maximum Nash welfare is canonical because, for additive valuations, it simultaneously guarantees Pareto optimality and envy-freeness up to one good [16], spawning a substantial approximation-algorithms literature [17], [18]. Closest to our parameterized objective, recent work studies \(p\)-mean welfare in fair division and online allocation across the full range from utilitarian to Nash to egalitarian welfare [19]–[22].

The distinction in the bandit setting is that the welfare vector consists of per-round ex-ante rewards generated by a learning algorithm, rather than utilities induced by a known allocation. The question is therefore not merely how to optimize an inequality-sensitive objective, but how much additional cost is incurred to protect that objective while the learner is still acquiring information about arms.

2 Technical Overview↩︎

We unfold our technical approach in three stages. The first establishes the fundamental limits of exploration in the strongly fair regime. Second, we present our algorithm, \(\mathsf{UCB\text{-}HARE}\). Finally, its upper bound analysis shows how our method avoids prior inefficiencies to achieve the optimal rate.

2.1 Lower Bound↩︎

We obtain a lower bound on the minimax regret by studying a family of instances instead of a single one. Suppose the true instance \(\nu\) is drawn uniformly at random from a finite set \(\mathcal{V} := \{\nu^{(1)}, \ldots, \nu^{(k)}\}\). If we can lower-bound the regret of an arbitrary algorithm averaged over \(j \in \{1, \ldots, k\}\), it follows that there must exist at least one specific index \(j\) (and hence, an instance \(\nu^{(j)}\)) for which the same lower bound applies. We construct \(\mathcal{V}\) such that any arm \(i\) is optimal for at most one instance in this set – a “needle-in-haystack” configuration.

Fix some \(\mu > 0\). For each \(j \in [k]\), we define the instance \(\nu^{(j)} = \bigl(\nu_1^{(j)}, \ldots, \nu_k^{(j)}\bigr)\) by \[\nu_j^{(j)} = \mathcal{N}(\mu, \sigma^2) \quad \text{and} \quad \nu_i^{(j)} = \mathcal{N}(0, \sigma^2) \text{ for } i \neq j.\] so that the optimal arm for \(\nu^{(j)}\) (i.e., the \(j\)-th arm) fails to be optimal for any other instance \(\nu^{(j')}\). We write \(\mathbb{P}_j\) for the law under \(\nu^{(j)}\) and \(\mathbb{P}(\cdot)= \frac{1}{k}\sum_{j=1}^k \mathbb{P}_j(\cdot)\) be the law averaged over a uniformly random instance index. Both probability measures account for reward randomness and the algorithm’s internal randomization, if any. Since \(\mathcal{V}\subseteq\mathcal{E}_{\mathsf{SG}}(k, \sigma)^{+}\), any lower bound for \(\mathcal{V}\) also holds over \(\mathcal{E}_{\mathsf{SG}}(k, \sigma)^{+}\).

Fix an arbitrary algorithm. Let \(a_{j,t}:=\mathbb{P}_j(I_t=j)\) be the probability of pulling the optimal arm at round \(t\) under \(\nu^{(j)}\). Since all other arms have mean zero, the ex-ante reward on \(\nu^{(j)}\) is \(m_t^{(j)}=\mu\,a_{j,t}\), so the negative-power welfare on \(\nu^{(j)}\) depends only on the sequence \((a_{j,t})_t\). Let \(s_t:=\frac{1}{k}\sum_{j=1}^k a_{j,t}\) denote the average success probability at round \(t\). Since \(x\mapsto x^{-q}\) is convex for \(q=-p>0\), Jensen’s inequality gives \(\frac{1}{k}\sum_{j} a_{j,t}^{-q}\ge s_t^{-q}\) for every \(t\); averaging over time and then over the \(k\) instances, some \(\nu^{(j)}\in\mathcal{V}\) satisfies \(\frac{1}{T}\sum_t a_{j,t}^{-q}\ge\frac{1}{T}\sum_t s_t^{-q}\). Since \(x\mapsto x^{-1/q}\) is decreasing, this yields \((-q)\)-mean welfare of the ex-ante reward sequence \[\mathsf{M}_{-q}\bigl(m_1^{(j)},\ldots,m_T^{(j)}\bigr):=\paren*{\frac{1}{T}\sum\nolimits_{t=1}^T (m_t)^{-q}}^{-1/q} =\mu\paren*{\frac{1}{T}\sum\nolimits_{t=1}^T a_{j,t}^{-q}}^{-1/q} \le\mu\paren*{\frac{1}{T}\sum\nolimits_{t=1}^T s_t^{-q}}^{-1/q}.\] The lower bound, therefore, reduces to the question: how large an inverse-power cost \(\sum_t s_t^{-q}\) must a learner incur to raise \(s_t\) from its uninformed baseline \(1/k\) to a constant scale?

Two key estimates connect the success probability \(s_t\) to the history \(\mathcal{H}_{t-1}= \{I_1,X_1,\ldots, I_{t-1},X_{t-1}\}\). Let \(\mathcal{I}_t := I(J;\mathcal{H}_{t-1})\) denote the mutual information that the history carries about the arm \(J \sim \mathrm{Unif}([k])\).² For \(s\in[1/k,1]\), define \(d_k(s):=\mathsf{kl}\!\left(s\,\middle\|\,\tfrac1k\right)\), the binary relative entropy between Bernoulli\((s)\) and Bernoulli\((1/k)\). It satisfies \(d_k(1/k)=0\), is nonnegative, and is increasing on \([1/k,1]\). Because \(s_t\) may dip below \(1/k\), we track the truncated quantity \(r_t:=\max\{s_t,1/k\}\), so that \(d_k(r_t)\) is always evaluated on its intended domain.

The first estimate says that a success probability above the random-guessing scale can be achieved only if the history distinguishes the identity of the positive-mean arm.

To see this, note that if \(s_t<1/k\), then \(r_t=1/k\) and the claim follows from \(d_k(1/k)=0\) and nonnegativity of mutual information. Otherwise \(s_t\ge 1/k\), so \(r_t=s_t\). Here, the action \(I_t\) can be viewed as an estimator of the hidden index \(J\). Since \(I_t\) is generated from \(\mathcal{H}_{t-1}\) and is independent of \(J\), the data-processing inequality gives \(I(J;I_t)\le I(J;\mathcal{H}_{t-1})=\mathcal{I}_t\), while this estimator succeeds with probability \(\mathbb{P}(I_t=J)=s_t\), so the Fano converse yields \(I(J;I_t)\ge d_k(s_t)\). Combining the two, we obtain \(\mathcal{I}_t\ge d_k(s_t)=d_k(r_t)\). 0◻

The second estimate controls the one-step growth of \(\mathcal{I}_t\) in the "needle-in-haystack" problem.

By the chain rule, the one-step increase equals the conditional mutual information between \(J\) and the new reward, given the past history and the chosen action. Compare the conditional reward law to the reference \(\mathcal{N}(0,\sigma^2)\): if \(I_t\neq J\) the reward has law \(\mathcal{N}(0,\sigma^2)\), so its divergence from the reference is zero, whereas if \(I_t=J\) the reward has law \(\mathcal{N}(\mu,\sigma^2)\), at KL-divergence exactly \(\lambda\). Averaging over \(\{I_t=J\}\) gives \(\mathcal{I}_{t+1}-\mathcal{I}_t\le\lambda\,\mathbb{P}(I_t=J)=\lambda s_t\); the second inequality follows from \(s_t\le r_t\). 0◻

The two estimates above reduce the lower-bound argument to a deterministic calculation. The variable \(r_t\) tracks the learner’s progress from the random-guessing scale \(1/k\) toward constant success probability. When \(r_t\) is of order \(r\), the inverse-power penalty is of order \(r^{-q}-1\), while one round can acquire at most \(\lambda r\) units of information. Raising \(r_t\) from \(1/k\) to a constant scale thus costs \(r^{-q-1}/\lambda\) per unit of information demanded, and integrating this rate against the information requirement \(d_k'(s)\) gives a leading cost of order \(\frac{1}{\lambda}\int_{1/k}^{1/2} s^{-q-1}\,d_k'(s)\,ds\). Since \(d_k'(s)=\log\!\left(\dfrac{(k-1)s}{1-s}\right)\), this integral already contributes order \(k^q\) on the subinterval \([2/k,4/k]\), yielding the following deterministic inequality.

Since \(r_t\ge s_t\) gives \(s_t^{-q}\ge r_t^{-q}\), combining the averaging argument above with [claim:informal-cost] produces a fixed instance \(\nu^{(j)}\) with \(\frac{1}{T}\sum_{t=1}^T a_{j,t}^{-q}\;\ge\;1+\Omega_q\paren*{\min\paren*{1,\;\frac{k^q}{\lambda T}}}\). Substituting \(\lambda=\mu^2/(2\sigma^2)\), the \((-q)\)-mean regret is bounded below by \(\Omega_q\paren*{\mu\,\min(1, \frac{\sigma^2k^q}{\mu^2 T})}\). Choosing \(\mu=\sigma\sqrt{k^q/T}\) balances the two terms and yields the negative-power lower bound \(\Omega_q \paren*{\sigma k^{q/2}/\sqrt{T}}\). Combined with the classical average-regret baseline \(\Omega\paren*{\sigma\sqrt{k/T}}\) [2] (which carries over to \((-q)\)-mean regret by monotonicity of generalized means (6)), this gives the minimax lower bound \(\Omega_q\paren*{\sigma\sqrt{k^{\max\{1,q\}}/T}}\). 0◻

A general information-cost inequality. Claim [claim:informal-cost] is a special case of a general inequality that makes no reference to the bandit objective. Its proof uses only three features: the per-round penalty \(r^{-q}-1\) is a non-increasing function of the success probability; the information needed to sustain success probability \(r\) is at least \(d_k(r)\); and this information can grow by at most \(\lambda r\) per round. Abstracting these into a cost \(c\), an information requirement \(\phi\), and an acquisition rate \(\psi\), the same argument gives the following (16): if \(\phi(r_t)\le\mathcal{I}_t\) and \(\mathcal{I}_{t+1}-\mathcal{I}_t\le\lambda\,\psi(r_t)\) for a non-increasing cost \(c\), a strictly increasing \(\phi\) with \(\phi(1/k)=0\), and a non-decreasing \(\psi\), then \[\sum_{t=1}^T c(r_t)\;\ge\;\min\!\left\{\,c(s^\star)\,T,\;\; \frac{1}{\lambda}\int_{1/k}^{s^\star}\frac{c(r)\,\phi'(r)}{\psi(r)}\,\mathrm dr\right\}\] for any target scale \(s^\star\). The negative-power bound of Claim [claim:informal-cost] is recovered (1) by taking \(c(r)=r^{-q}-1\), \(\phi=d_k\), \(\psi(r)=r\), and \(s^\star=1/2\), whereupon the integral evaluates to order \(k^q/\lambda\). Stated this way, the objective enters only through the cost \(c\) and the problem’s structure only through the acquisition rate \(\psi\), so the inequality applies well beyond negative power means.

2.2 The Algorithm↩︎

Our lower bound exposes that regret depends on how fast the optimal arm’s pull probability rises above the baseline \(1/k\). Yet prior algorithms [1] rely on reward-agnostic uniform exploration – pulling every arm, including the optimal one, at the same low rate while gathering evidence against the rest. Our key is a more judicious initial exploration, designed to quickly secure a nontrivial growing lower bound on the ex-ante reward. We achieve this via a two-phase approach:

Phase I: Preparation. In this phase, we perform shielded exploration of arms by pairing each exploration pull with a safer anchor pull. For this, first rank these arms: draw a uniform random permutation \(\pi\) over \([k]\), mapping each rank \(r \in [k]\) to a unique arm \(\pi_r\). Next, partition the time horizon into a rigid tiling of 2-round blocks (see 1). Each block \(b \ge 1\) spans the two bandit rounds: \(t=2b-1\) and \(t=2b\). Of these, the algorithm reserves one round (the Scheduled Slot) to explore arms, and the other round (the Auxiliary Slot) to exploit the safest known arm (the anchor).

The exact ordering of these slots in a block \(b\) is decided by a fair coin \(\theta_b \sim \text{Ber}(1/2)\), drawn afresh when that block begins. The Scheduled Slot comes first if \(\theta_b = 1\), the Auxiliary Slot otherwise.

Scheduled Slot. Exploration in this slot follows a strict schedule where each block \(b\) is assigned a fixed rank \(r_b\) (equivalently, arm \(\pi_{r_b}\)) to explore. This schedule, denoted by the sequence \((r_b)_{b \ge 1}\), is generated by iterating an integer \(n = 1, 2, 3, \dots\) serially through the natural numbers and appending all divisors \(d \le k\) of each \(n\) in ascending order (see 2). Observe that this design exhibits a harmonic property. Since any rank \(r\) divides a \(1/r\) fraction of consecutive integers, its exploration frequency is proportional to \(1/r\). Also, the sequence, being generated entirely a priori, remains independent of the reward history.

Auxiliary Slot. This slot pulls the safest known arm, if available, to defend the welfare floor. Let \(c(n):=\sigma\sqrt{\frac{2\log(8kT/\delta)}{n}}\) denote the confidence radius after \(n\) samples (\(\delta \in (0,1)\) is the confidence level). Writing \(\hat{\mu}_i(t)\) and \(N_i(t)\) for the empirical mean and number of pulls of arm \(i\) up to (and including) round \(t\), it computes the maximum lower confidence bound \[B_{t-1}:=\max\nolimits_{i\in[k]}\{\hat{\mu}_i(t-1)-c(N_i(t-1))\},\] where \(t\) is its allotted round. If \(B_{t-1}>0\), the maximizing arm is certified as the anchor and is pulled. Otherwise, no anchor has yet been certified, and the scheduled arm \(\pi_{r_b}\) is pulled a second time.

Phase I continues blockwise, until an anchor has been found and sufficient exploration has been performed across all arms. Formally, its termination occurs at stopping time \(\tau\), defined as the first even round \(t\) such that \[\label{eq:stop-condition} B_t > 0 \quad \text{and} \quad \min\nolimits_{i \in [k]} N_i(t) \ge 32\sigma^2 \log(8kT/\delta)/B_t^2.\tag{1}\] The first condition certifies the anchor, while the second adaptively requires every confidence radius to shrink below its certified margin. Together they bound the duration of Phase I, confining the inverse-power penalty to a finite transient before transitioning to UCB-based exploitation.

Phase II: Exploitation. Upon satisfying 1 , the block structure is discarded. For all subsequent rounds \(t > \tau\), the algorithm employs the standard UCB index to pull arms, i.e., it selects the arm \[I_t := \mathop{\mathrm{arg\,max}}\nolimits_{i \in [k]} \lbrace\hat{\mu}_i(t-1) + c(N_i(t-1))\rbrace.\]

Remarks on Algorithm Design. (i) Block boundaries. The stopping condition is evaluated only at even rounds (block boundaries), so the event \(\{\tau>t\}\) depends solely on the history prior to block \(b\) and is independent of the intra-block coin flip \(\theta_b\). This preserves the strict \(1/2\) marginal probabilities that the ex-ante reward bound (21) relies on; evaluating mid-block could truncate the auxiliary slot and break them. (ii) Dynamic thresholding. The anchor threshold \(B_{t-1}\) is read at the moment the auxiliary slot executes, incorporating any scheduled observation already made in the same block. The pseudo-code of UCB-HARE is presented in 4.

2.3 Upper Bound↩︎

We begin with a deterministic conversion that reduces the nonlinear \((-q)\)-mean regret to a cumulative inverse penalty. Define it as \(A_T:=\sum_{t=1}^T\bigl[(\mu_\star/m_t)^q-1\bigr]\), where \(m_t:=\mathbb{E}[\mu_{I_t}]\), \(\mu_\star:=\max_{i\in[k]}\mu_i\).

To see this, factor \(\mu_\star\) out of the \((-q)\)-mean to get \(\mathsf{M}_{-q}(m_1,\ldots,m_T)=\mu_\star\,(1+A_T/T)^{-1/q}\); the bound then follows from the elementary inequality \(1-(1+u)^{-1/q}\le u/q\) for \(u\ge0\). 0◻

Now we show that UCB-HARE keeps the ex-ante reward bounded away from zero quickly enough during preparation, and then behaves like standard UCB after certification. Both parts rest on the standard high-probability event on which the algorithm’s confidence intervals are valid. Let \(L:=\log(8kT/\delta)\) and \(c(n):=\sigma\sqrt{2L/n}\), and define \(\mathcal{E}:=\{\,\forall i\in[k],\;\forall n\le T:\;|\hat{\mu}_{i,n}-\mu_i|\le c(n)\,\}\). Applying sub-Gaussian concentration to each of the \(kT\) arm–count pairs and a union bound gives \(\Pr(\mathcal{E})\ge 1-\delta/4\). On \(\mathcal{E}\) every lower confidence bound is valid, \(L_i(t):=\hat{\mu}_i(t)-c(N_i(t))\le\mu_i\), so whenever \(B_t:=\max_i L_i(t)>0\), any maximizing arm \(a\) satisfies \(\mu_a\ge L_a(t)=B_t>0\) - certifying an anchor with strictly positive true mean.

The next lemma explains why Phase I cannot last too long. Define \(n_\star:=\max\{\lceil 128\sigma^2L/\mu_\star^2\rceil,\,1\}\), \(S:=\;\lceil H_k n_\star\rceil\), and \(T_0:=18kS\).

To see this, suppose the optimal arm \(i_\star\) has \(n_\star\) samples. Its confidence radius is then \(c(N_{i_\star})\le\sigma\sqrt{2L/(128\sigma^2L/\mu_\star^2)}=\mu_\star/8\). So on \(\mathcal{E}\), \[L_{i_\star}(t)=\hat{\mu}_{i_\star}(t)-c(N_{i_\star}(t))\ge\mu_\star-2c(N_{i_\star}(t))\ge\tfrac{3}{4}\mu_\star,\] giving \(B_t>0\) and hence an anchor. For the duration, the prefix-balance property of the harmonic schedule guarantees that by block \(8kS+1\) every rank (and thus every arm) has at least \(n_\star\) samples. At that point the optimal arm certifies \(B_t\ge 3\mu_\star/4\), and the stopping threshold satisfies \(32\sigma^2L/B_t^2\le 32\sigma^2L/(3\mu_\star/4)^2=\tfrac{512}{9}\sigma^2L/\mu_\star^2\le n_\star\). So the stopping condition holds at this block boundary, and since each block spans two rounds, Phase I ends by \(T_0=18kS\). 0◻

We split the cumulative inverse penalty at this deterministic time, \[A_T\le \underbrace{\sum\nolimits_{t=1}^{T\wedge T_0}\Bigl[(\mu_\star/m_t)^q-1\Bigr]}_{A_T^{\mathrm{prep}}} +\underbrace{\sum\nolimits_{t=T_0+1}^{T}\Bigl[(\mu_\star/m_t)^q-1\Bigr]}_{A_T^{\mathrm{UCB}}},\] with \(A_T^{\mathrm{UCB}}:=0\) if \(T\le T_0\). This is to avoid conditioning on the random stopping time \(\tau\). We first control the preparation term. For block \(b\), define the expanding frontier \(a_b:=\min\{k,\lfloor(b-1)/8S\rfloor\}\): by the start of block \(b\), every arm whose random rank is at most \(a_b\) has accumulated enough samples to certify an anchor, were it the optimal arm.

To see this, let \(R_\star\) be the rank of the optimal arm under the initial permutation, so \(R_\star\) is uniform on \([k]\). The ex-ante reward has two sources. The scheduled slot is the current round with probability \(1/2\) (the within-block coin flip), and the scheduled arm is optimal with probability \(1/k\), giving a baseline contribution of order \(\mu_\star/k\). The auxiliary slot contributes when \(R_\star\le a_b\): the optimal arm then has \(n_\star\) samples by the start of block \(b\), which on \(\mathcal{E}\) certifies an anchor of mean at least \(3\mu_\star/4\). Since \(\Pr(R_\star\le a_b)=a_b/k\), the round is the auxiliary slot with probability \(1/2\), and the block-boundary stopping rule makes the continuation of Phase I independent of that coin flip, this yields an auxiliary contribution of order \(\mu_\star a_b/k\). Finally, if Phase I has already ended before round \(t\), the Phase-II rule is at least as safe (shown below in 5), so in all cases \(m_t\ge c_0\mu_\star\max\{1/k,\;a_b/k\}\). 0◻

The reward floor yields a bound on the preparation penalty.

To see this, note the window \(t\le T\wedge T_0\) spans at most \(9kS\) blocks (\(T_0=18kS\), two rounds per block), and by [claim:informal-ex-ante] every round in block \(b\) has \((\mu_\star/m_t)^q\le C_q\max\{1/k,\,a_b/k\}^{-q}\). We partition the blocks by the frontier value \(a_b\): the first \(8S\) blocks have \(a_b=0\) and contribute \(O_q(Sk^q)\); each value \(a_b=r\) for \(r=1,\ldots,k-1\) persists for \(O(S)\) blocks, contributing \(O_q\bigl(S(k/r)^q\bigr)\); and the saturated blocks (\(a_b=k\)) add \(O_q(S)\). Summing up, we get \(A_T^{\mathrm{prep}}\le C_q S\sum_{r=1}^k\Bigl(\tfrac{k}{r}\Bigr)^q=C_q S\,K_q(k)\). 0◻

It remains to control the rounds after \(T_0\). The stopping rule ensures that, once Phase II begins, every arm has a confidence radius small relative to \(\mu_\star\).

To see this, recall that at the stopping time \(B_\tau>0\) and \(\min_i N_i(\tau)\ge 32\sigma^2L/B_\tau^2\). On \(\mathcal{E}\) no lower confidence bound exceeds its true mean, so \(B_\tau\le\mu_\star\); hence every arm has at least \(32\sigma^2L/\mu_\star^2\) samples and confidence radius at most \(\mu_\star/4\). Now let \(i\) be any arm selected by UCB in Phase II. Its index dominates the optimal arms’, \(\hat{\mu}_i(t)+c(N_i(t))\ge\hat{\mu}_{i_\star}(t)+c(N_{i_\star}(t))\ge\mu_\star\), so \[\mu_i\ge\hat{\mu}_i(t)-c(N_i(t))=\bigl(\hat{\mu}_i(t)+c(N_i(t))\bigr)-2c(N_i(t)) \ge\mu_\star-\tfrac{\mu_\star}{2}=\tfrac{\mu_\star}{2}.\]

This safety property lets the Phase-II penalty be controlled by UCB pseudo-regret.

To see this, assume \(T>T_0\) (else the sum is empty). By 4, all rounds \(t>T_0\) lie in Phase II, and on \(\mathcal{E}\), 5 gives selected mean at least \(\mu_\star/2\); since \(\Pr(\mathcal{E})\ge 1-\delta/4\), this yields the unconditional floor \(m_t\ge\mu_\star/4\). On \(m_t\in[\mu_\star/4,\mu_\star]\) the inverse-power map is locally Lipschitz, so \((\mu_\star/m_t)^q-1\le C_q(\mu_\star-m_t)/\mu_\star\). The numerator \(\mu_\star-m_t\) is the expected pseudo-regret at round \(t\); on \(\mathcal{E}\) the standard UCB argument bounds its cumulative sum over Phase II by \(O(\sigma\sqrt{kTL})\), while \(\mathcal{E}^c\) contributes at most \(O(\mu_\star T\delta)\). Dividing by \(\mu_\star\) gives the displayed bound. 0◻

Combining [claim:informal-prep-penalty,claim:informal-phase2-cost] gives \(A_T\le C_q\Bigl(S\,K_q(k)+\tfrac{\sigma}{\mu_\star}\sqrt{kTL}+T\delta\Bigr)\), where \(S= \lceil H_kn_\star \rceil\). Since \(n_\star\le 1+128\sigma^2L/\mu_\star^2\), the preparation term obeys \(S K_q(k)\le H_kK_q(k)\,(1+C\sigma^2L/\mu_\star^2)\), and applying 3 yields the \((-q)\)-mean regret \[R_{T,-q}\le C_q\left[ \frac{\mu_\star H_kK_q(k)}{T} +\frac{\sigma^2L\,H_kK_q(k)}{\mu_\star T} +\sigma\sqrt{\frac{kL}{T}} +\mu_\star\delta\right].\] Because \(H_kK_q(k)\ge k\), the third term satisfies \(\sigma\sqrt{kL/T}\le\mu_0\), where \(\mu_0:=\sigma\sqrt{H_kK_q(k)L/T}\). For the second term, note that it equals exactly \(\mu_0^2/\mu_\star\), which is large only when \(\mu_\star\) is small; there, however, the trivial bound \(R_{T,-q}\le\mu_\star\) takes over. Combining the two, we get \(\min\Bigl\{\mu_\star,\;\tfrac{\mu_0^2}{\mu_\star}\Bigr\}\le\mu_0\), so the second and third terms together contribute at most \(O(\mu_0)\). The first and fourth terms carry through unchanged. Setting \(\delta=1/T\) gives \[R_{T,-q}\le C_q\left[\sigma\sqrt{\frac{H_kK_q(k)L}{T}}+\frac{\mu_\star H_kK_q(k)}{T}\right].\]

Paper Organization↩︎

In 3, we collect the main technical ingredients used throughout the paper. We begin with basic properties of \((-q)\)-mean regret, including the reductions that convert the nonlinear welfare objective into cumulative inverse-penalty bounds. We then review the information-theoretic tools needed for the minimax lower bound, and record the deterministic consequences of the harmonic schedule that drives the exploration phase of \(\mathsf{UCB\text{-}HARE}\). With these preliminaries established, 4 proves the lower bound for the strongly fair regime, showing how the inverse-power objective amplifies the cost of slow identification of the optimal arm. 5 presents the pseudocode of \(\mathsf{UCB\text{-}HARE}\)together with its main guarantee. The matching upper bound for \(\mathsf{UCB\text{-}HARE}\)is proved in 6, where we combine the reward floor created during preparation with the safety of the subsequent UCB phase. Finally, 7 presents our experimental evaluation and compares \(\mathsf{UCB\text{-}HARE}\)against uniform-exploration-based baselines.

3 Preliminaries↩︎

We operate in the standard \(k\)-armed stochastic bandit setting over a horizon \(T\). Let \(m_t := \mathbb{E}[\mu_{I_t}]\) denote the ex-ante expected reward at round \(t\), and let \(\mu_\star:= \max_{i \in [k]} \mu_i\). In this section, we establish some prerequisites for our analysis.3.1 introduces the welfare objective and the specific reductions we use to bound it. 3.2 reviews the information-theoretic tools necessary for our minimax lower bounds. Finally, 3.3 defines the deterministic schedule driving our algorithmic upper bound.

3.1 The \(p\)-Mean Regret↩︎

Our objective is to evaluate collective welfare using the generalized \(p\)-mean functional [4], [6] in the negative (fair) regime, which penalizes suboptimal assignments to early rounds. Parameterizing this regime by \(q = -p > 0\), we define the \((-q)\)-mean welfare of the ex-ante reward sequence as: \[\mathsf{M}_{-q}(m_1, \dots, m_T) := \left(\frac{1}{T} \sum_{t=1}^T m_t^{-q} \right)^{-1/q}.\] The \((-q)\)-mean regret of an algorithm \(\mathsf{A}\) on instance \(\nu\) is its welfare shortfall relative to the optimal fixed-arm policy: \[R_{T,-q}(\mathsf{A}, \nu) := \mu_\star- \mathsf{M}_{-q}(m_1, \ldots, m_T).\]

We begin with three properties. First, 6 establishes monotonicity of the welfare function, which we use in our lower bound proof in 4.

The remaining two results aid 6, where we establish upper bounds for \(\mathsf{UCB\text{-}HARE}\). 7 first isolates the outer non-linearity of the regret into a cumulative inverse penalty. 8 then handles the remaining inner non-linearity, reducing this penalty to the standard linear pseudo-regret by exploiting its local Lipschitz continuity when rewards are bounded away from zero.

3.2 Useful Results From Information Theory↩︎

To establish the fundamental limits of fair exploration, we rely on standard information-theoretic quantities. For two probability distributions \(P\) and \(Q\) defined on a common measurable space, denote the Kullback-Leibler (KL) divergence by \(\mathsf{KL}(P \,\|\, Q)\). For Bernoulli distributions with parameters \(p, q \in (0, 1)\), we denote the binary relative entropy by \[\mathsf{kl}(p \,\|\, q) := p \log\left(\frac{p}{q}\right) + (1-p) \log\left(\frac{1-p}{1-q}\right).\] For our lower bound analysis, we require two structural properties of mutual information. The first allows us to upper-bound the conditional mutual information with respect to an arbitrary reference distribution. This is crucial for isolating the information gain exclusively to rounds where the optimal arm is pulled.

The second property establishes a lower bound on the mutual information required to identify a uniformly drawn hypothesis. We express this via the function \(d_k : [1/k, 1] \to \mathbb{R}_+\), defined as \[d_k(s) := s \log(ks) + (1-s) \log\left(\frac{k(1-s)}{k-1}\right) = \mathsf{kl}\left(s \,\middle\|\, \frac{1}{k}\right).\] Note that \(d_k(s)\) is strictly increasing on \([1/k, 1]\).

3.3 Harmonic Schedule↩︎

To coordinate exploration, our algorithm relies on a deterministic, rank-based sequence which we call the harmonic schedule. For a fixed number of arms \(k\) and any integer \(n \ge 1\), define the truncated divisor set \(\mathcal{D}_n := \{d \in [k] : d \mid n\}\).

The harmonic schedule, denoted \((r_b)_{b \ge 1}\), is constructed by concatenating the sets \(\mathcal{D}_1, \mathcal{D}_2, \dots\) in ascending order of \(n\). For example, setting \(k=5\), the sequence discards any divisors strictly greater than \(k\), yielding:

The primary advantage of this schedule is the following lemma, which allows us to track the pull count of each rank.

We also preemptively record here the asymptotic behavior of a certain harmonic penalty sum induced by the schedule (used later in 6), which governs the final regret regime.

4 Our Lower Bound and Proof↩︎

In this section, we establish the information-theoretic limits of strongly fair exploration. We formally restate our main lower bound theorem below, which highlights that the minimax regret inflates from \(\sqrt{k/T}\) to \(\sqrt{k^q/T}\).

We first establish the classical baseline for \(p \le 1\).

For our main proof, we focus on \(k\) difficult “one-good-arm” instances and average the regret over them. Fix \(q>0\), \(k\ge8\) and \(\mu>0\). For each \(j\in[k]\), define the underlying instance \(\nu^{(j)}\) by: \[\nu_i^{(j)} = \begin{cases} \mathcal{N}(\mu,\sigma^2), & i=j,\\ \mathcal{N}(0,\sigma^2), & i\neq j. \end{cases}\] Let \(\mathbb{P}_j\) denote the probability measure under instance \(\nu^{(j)}\). Let \(J \sim \mathsf{Unif}([k])\) index a uniformly random instance, and define \(\mathbb{P}\) as the law averaged over this random choice, \[\mathbb{P}(\cdot) := \frac{1}{k}\sum_{j=1}^k \mathbb{P}_j(\cdot)\] under which \(J\) is first drawn and then instance \(\nu^{(J)}\) is executed. We define the algorithm’s instance-specific success probability \(a_{j,t}\) and average success probability \(s_t\) at round \(t\) as: \[a_{j,t} := \mathbb{P}_j(I_t=j), \qquad s_t := \mathbb{P}(I_t=J) = \frac{1}{k}\sum_{j=1}^k a_{j,t}.\]

To bound the success probability \(s_t\), we track the mutual information collected by any algorithm on \(J\) prior to round \(t\), denoted as \(\mathcal{I}_t := I(J; \mathcal{H}_{t-1})\). Recall from our preliminaries (3.2) that the function \(d_k(s) := \mathsf{kl}(s \,\|\, 1/k)\) represents the minimum information required to guess the optimal arm with success probability \(s\).

4.1 An Information-Cost Principle↩︎

We isolate the deterministic argument that underlies the lower bound. The statement below abstracts the following tradeoff. A sequential procedure is summarized at round \(t\) by a scalar success level \(s_t\). Achieving a larger value of \(s_t\) requires the history to contain a corresponding amount of information about a hidden index, while the information gained in one round is itself limited by the current value of \(s_t\). Any objective that penalizes small values of \(s_t\) must therefore incur a cumulative cost before \(s_t\) can reach a constant scale.

The lemma is independent of the particular bandit construction. The objective enters only through a nonincreasing penalty function \(c\), while the statistical model enters through an information requirement \(\phi\) and an upper bound \(\lambda\psi(s_t)\) on the one-step information gain.

5 Algorithm and Upper Bound↩︎

In this section, we formally present our \(\mathsf{UCB\text{-}HARE}\)algorithm and establish its theoretical guarantees.

The following theorem establishes the \(p\)-mean regret upper bound of \(\mathsf{UCB\text{-}HARE}\). Notice that the leading term replaces the \(k^{q+1}\) dependency with the harmonic penalty sum \(K_q(k)\), matching the fundamental information-theoretic limits.

Instantiating the confidence parameter as \(\delta=1/T\) sets the failure penalty to \(\mu_\star/T\). For a sufficiently large horizon (\(T \gtrsim \mu_\star^2 H_k K_q(k) / \sigma^2\)), this \(O(1/T)\) trailing term is dominated by the leading exploration cost.

The asymptotic limits of \(K_q(k)\) from [fact:harmonic-penalty] then classify the regret into three distinct regimes, closing the complexity gap.

Here, we note that the introductory bound presented in 2 is simply an asymptotic restatement of 4 that suppresses the transient \(O(1/T)\) failure penalty to highlight the dependence on \(K_q(k)\).

6 Proof of Upper Bound↩︎

This section proves 4. Fix an instance with optimal mean \(\mu_\star\). If \(\mu_\star=0\), then every mean is zero and the regret is zero. Hence assume \(\mu_\star>0\).

We first fix the standard “good event” that bounds the empirical mean estimator \(\hat{\mu}_{i,n}\) for all arms and sample counts.

Let \(L = \log(8kT/\delta)\) and define the confidence radius \(c(n) := \sigma\sqrt{2L/n}\). We define the good event as \[\mathcal{E}:= \quad \left\{ \forall i \in [k], \, \forall n \in [T] : |\hat{\mu}_{i,n} - \mu_i| \le c(n) \right\} \quad = \quad \bigcap_{i=1}^k \bigcap_{n=1}^T \Big\{ |\hat{\mu}_{i,n} - \mu_i| \le c(n) \Big\}.\]

Throughout this section, define the critical sample threshold as: \[n_\star := \max\left(\left\lceil 128\frac{\sigma^2L}{\mu_\star^2}\right\rceil, 1\right).\]

Under the good event, we now show that allocating \(n_\star\) samples to the optimal arm is sufficient to establish an anchor, and hence, a positive welfare floor.

Set \(S = \lceil H_kn_\star \rceil\). We define an expanding exploration frontier \(a_b\) over \(\pi\) that guarantees the sampling threshold \(n_\star\) to all arms with ranks \(r < a_b\).

Together, 18 and 19 govern the discovery of the anchor: it is established early if \(R_\star \le a_b\), and guaranteed in any case by block \(8kS+1\), under \(\mathcal{E}\). We now use this to lower bound the expected reward \(m_t\) for any round \(t\).

Recall that the stopping condition for Phase I is evaluated exclusively at the end of each two-round block (i.e., at even rounds). Specifically, Phase I terminates at the first even round \(t\) where the anchor is secured and the sample counts satisfy: \[B_t > 0 \quad \text{and} \quad \min_{i \in [k]} N_i(t) \ge \frac{32 \sigma^2 L}{B_t^2}.\] Let \(\tau \in \{2, 4, 6, \dots\}\) denote this random stopping time in rounds. We now prove that this empirical threshold guarantees strict safety for Phase II.

We now bound the maximum duration of Phase I and then derive a cap on its penalty.

We now bound the inverse penalty for the remaining duration of the horizon.

7 Experiments↩︎

We evaluate \(\mathsf{UCB\text{-}HARE}\)against Welfarist UCB [1] and Explore-Then-UCB [6] in four parts: a head-to-head regret comparison, a stress test across fairness levels, a closer look at exploration and a targeted test of regret scaling with the number of arms. For the first two, we simulate a \(k\)-armed bandit with \(k=50\), mean rewards \(\mu_i\) drawn i.i.d.uniformly from \([10,1000]\), and Gaussian noise variance \(\sigma^2=400\), over a horizon \(T=10^6\), averaging results over \(50\) independent runs to estimate \(\mathbb{E}[\mu_{I_t}]\).

7.0.0.1 Experiment A: Regret across algorithms.

[fig:h2h-p05,fig:h2h-p2,fig:h2h-p20] compare regret for \(p \in \{-0.5,-2.0, -20\}\). \(\mathsf{UCB\text{-}HARE}\)minimizes regret most rapidly. Welfarist-UCB is delayed by uniform exploration, and Explore-Then-UCB accrues linear regret prior to commitment. \(\mathsf{UCB\text{-}HARE}\)mitigates both inefficiencies via a real-time lower confidence bound anchor.

7.0.0.2 Experiment B: Regret scales with \(q = -p\).

5 (d) shows regret across fairness levels \(p \in \{-1, -5, -10, -20\}\), increasing in magnitude as \(q =-p\) grows, consistent with our theoretical rates. \(\mathsf{UCB\text{-}HARE}\)’s regret remains stable across this entire range.

7.0.0.3 Experiment C: Ex-ante reward vs \(t\).

We construct an instance with \(k=200\) arms, five of which have means \(200\), \(400\), \(600\), \(800\), \(1000\) and the rest with mean \(10\), and run a single trial (no averaging across seeds) over \(T=5000\) rounds at \(p = -q = -2.0\), tracking the ex-ante reward \(m_t\). Single-trial outcomes vary with the random permutation drawn by the algorithm; the run shown in 5 is representative and captures the novelty of our harmonic anchored rank exploration. We highlight the following:

1. Welfare improves stepwise, not in one jump. \(\mathsf{UCB\text{-}HARE}\)’s roundwise ex-ante reward \(m_t\) increases in a sequence of steps, each corresponding to a newly certified anchor, before reaching the optimum. This matches the bound \(m_t \ge c_0 \mu_\star \max(1/k, a_b/k)\) of 21, which increases in step with the expanding frontier \(a_b\).

2. Uniform exploration is sub-optimal. Welfarist-UCB’s \(m_t\) sits at the uniform-exploration floor (\(m_t \approx 25 \gtrsim \mu_\star/k\)) for the entire duration of Phase I, confirming that this baseline is indeed the source of the \(k^{(q+1)/2}\) penalty it incurs. This stems from the fact that Welfarist-UCB samples all \(k\) arms comparably before committing to UCB, regardless of which is optimal.

Experiment D: Regret scaling with \(k\) and \(q\). Here, we choose an instance where one arm has mean \(\mu = 1000\), a block of near-optimal arms have mean \(\mu = 950\), and the remaining arms have mean \(\mu = 10\), with arm identities randomly permuted. We compare \(k = 10\) against \(k = 100\) over horizons up to \(T = 10^6\), averaged over \(50\) independent trials, at three fairness levels \(p \in \{-1.0, -2.0, -5.0\}\) with \(\sigma^2 = 1.0\) (Figure 6).

The gap between the two algorithms grows with \(q = -p\). At \(q = 1\), \(\mathsf{UCB\text{-}HARE}\)and Welfarist-UCB stay close at both arm counts, matching the regime \(q \leq 1\), where both rates scale as \(\sqrt{k/T}\). As \(q\) rises to \(2\) and then \(5\), Welfarist-UCB’s regret tends to flatten at its starting value for both \(k = 10\) and \(100\), while \(\mathsf{UCB\text{-}HARE}\)retains its performance better. This matches the gap between \(k^{(q+1)/2}\) and \(k^{q/2}\) from 2: uniform exploration gets more costly as \(q\) grows, while \(\mathsf{UCB\text{-}HARE}\)’s harmonic schedule avoids this extra cost.

Pushing \(q\) further, to \(10\) and \(20\), makes this flattening pronounced for both algorithms (7). This reflects the strongly fair regime’s convergence to the Rawlsian maximin ideal: as \(q \to \infty\), the \((-q)\)-mean is dominated by the smallest ex-ante reward in the sequence, so both algorithms are limited by their worst round. Welfarist-UCB reaches this limit early, at the uniform-exploration floor \(\mu_\star/k\), while \(\mathsf{UCB\text{-}HARE}\)’s harmonic schedule certifies a positive-mean anchor sooner and sustains improvement over a longer horizon.

References↩︎

---

1. A subscript \(q\) in asymptotic notation (e.g.\(\widetilde{O}_q\), \(\Omega_q\), \(\Theta_q\)) indicates that hidden constants may depend on \(q\).↩︎

2. Three objects share the symbol \(I\) and should not be conflated: the action \(I_t\in[k]\) selected at round \(t\); the mutual-information operator \(I(\cdot\,;\cdot)\); and the mutual information \(\mathcal{I}_t:=I(J;\mathcal{H}_{t-1})\) between the random index and the history. We write \(\mathcal{I}_t\) in script throughout to distinguish it from the action \(I_t\).↩︎