Paper deep dive
Price of Fairness in Bandits: A Tight Minimax Characterization
Dhruv Sarkar, Soumyadeep Dutta, Sayak Ray Chowdhury
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 90%
Last extracted: 7/16/2026, 5:01:14 AM
Summary
This paper investigates the fundamental limits of fairness in stochastic multi-armed bandit problems by analyzing the generalized p-mean welfare objective. It focuses on the strictly fair regime (q = -p > 0), where negative-power means heavily penalize low per-round rewards. The authors establish a tight minimax lower bound of Ω(σ√(k^max(1,q)/T)) using a needle-in-haystack construction, proving that a polynomial penalty of k^(q/2) on the number of arms is information-theoretically unavoidable for q > 1. To match this bound, they propose UCB-HARE (Harmonic Anchored Rank Exploration), an algorithm that replaces uniform early exploration with a harmonic rank schedule protected by a positive-mean anchor, achieving regret within logarithmic factors of the lower bound. Experiments confirm UCB-HARE outperforms prior uniform-exploration baselines.
Entities (6)
Relation Signals (8)
Generalized p-Mean → interpolatesbetween → Utilitarian Welfare
confidence 95% · interpolating between utilitarian welfare (p=1), Nash welfare (p→0), and Rawlsian fairness (p→−∞).
Generalized p-Mean → interpolatesbetween → Nash Social Welfare
confidence 95% · interpolating between utilitarian welfare (p=1), Nash welfare (p→0), and Rawlsian fairness (p→−∞).
Generalized p-Mean → interpolatesbetween → Rawlsian Fairness
confidence 95% · interpolating between utilitarian welfare (p=1), Nash welfare (p→0), and Rawlsian fairness (p→−∞).
UCB-HARE → achieves → Minimax Regret Lower Bound
confidence 90% · Its regret is Õ(σ√(k^max(1,q)/T)), matching the lower bound up to logarithmic factors.
UCB-HARE → replaces → Uniform Exploration
confidence 90% · UCB-HARE ... replaces uniform exploration with an inverse-weighted harmonic rank schedule
Needle-in-Haystack Construction → usedtoprove → Minimax Regret Lower Bound
confidence 90% · Using a needle-in-haystack construction, we prove an algorithm-independent lower bound Ω(σ√(k^max(1,q)/T))
Welfarist-UCB → has → Regret O(k^{(q+1)/2}/√T)
confidence 85% · the best prior algorithm relied on uniform early exploration and achieved regret O(k^{(q+1)/2}/√T)
Strictly Fair Regime → introduces → Polynomial Penalty k^(q/2)
confidence 85% · for q>1, this shows that the penalty k^{q/2} is information-theoretically unavoidable.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:In bandit problems, standard regret-minimizing algorithms treat exploration as an amortized cost, which can expose early participants to unfair ex-ante losses in settings such as clinical trials. Recent work addresses this by evaluating the sequence of per-round expected rewards through the generalized $p$-mean, interpolating between utilitarian welfare ($p=1$), Nash welfare ($p\to0$), and Rawlsian fairness ($p\to-\infty$). Although tight guarantees are known for $p\ge0$, the strictly fair regime $q=-p>0$ remains unresolved because negative-power means are dominated by the smallest per-round rewards. For $\sigma$-sub-Gaussian rewards with nonnegative means, the best prior algorithm relied on uniform early exploration and achieved regret $O(k^{(q+1)/2}/\sqrt{T})$, while the only general lower bound was the classical $\Omega(\sigma\sqrt{k/T})$. Thus it was unclear whether the extra dependence on $k$ was intrinsic to strict fairness or an artifact of uniform exploration. We close this gap by identifying the exact polynomial price of strict fairness. Using a needle-in-haystack construction, we prove an algorithm-independent lower bound $\Omega(\sigma\sqrt{k^{\max(1,q)}/T})$; for $q>1$, this shows that the penalty $k^{q/2}$ is information-theoretically unavoidable. We then introduce \textsf{UCB-HARE} (Harmonic Anchored Rank Exploration), which replaces uniform exploration with an inverse-weighted harmonic rank schedule protected by a certified positive-mean anchor. Its regret is $\widetilde{O}(\sigma\sqrt{k^{\max(1,q)}/T})$, matching the lower bound up to logarithmic factors. Experiments on synthetic instances confirm that \textsf{UCB-HARE} improves over uniform-exploration baselines, with gains increasing as $q$ grows.
Tags
Links
- Source: https://arxiv.org/abs/2607.13402v1
- Canonical: https://arxiv.org/abs/2607.13402v1
Trouble viewing inline? Open PDF directly →
Full Text
127,062 characters extracted from source content.
Expand or collapse full text
Price of Fairness in Bandits: A Tight Minimax Characterization Dhruv Sarkar1,2 Soumyadeep Dutta1 Sayak Ray Chowdhury3 1Indian Institute of Technology Kharagpur 2Mohamed bin Zayed University of Artificial Intelligence 3Indian Institute of Technology Kanpur dhruv.sarkar223@gmail.com soumyadeep.mind@gmail.com sayakrc@iitk.ac.in Abstract In sequential decision-making problems with bandit feedback, traditional algorithms typically minimize cumulative regret, treating early-round exploration as an acceptable amortized cost. However, in critical sequential settings (e.g., clinical trials), this utilitarian approach exposes early rounds (e.g., patients) to disproportionate and unfair ex-ante losses. To guarantee equitable outcomes in each round, a recent line of work evaluates the sequence of per-round expected rewards through the generalized p-mean function, which interpolates between utilitarian welfare (p=1p=1), Nash social welfare (p→0p→ 0) and Rawlsian fairness (p→−∞p→-∞). While the regime p≥0p≥ 0 is by now well understood, with tight upper and lower bounds, the strictly fair regime, parameterized by q=−p>0q=-p>0, is not. The difficulty stems from the inverse-power form of the objective: a negative-power mean is dominated by the smallest per-round expected reward, so a policy that assigns very low expected reward to even one round incurs a welfare loss that cannot be offset by later rounds. To sidestep this, existing algorithms rely on uniform exploration in early rounds. For σ-sub-Gaussian rewards with non-negative means, the best known algorithm [21] incurs regret of order O(k(q+1)/2/T)O (k^(q+1)/2/ T ), where k is the number of arms and T is the total number of rounds. At the same time, the known lower bound in this case is the classical average-regret limit Ω(σk/T) (σ k/T ), which does not capture the hardness of the problem when q>0q>0. The price of strict fairness is therefore open on both sides: prior upper bound held only against a loose lower bound, leaving unresolved how much of the k(q+1)/2k^(q+1)/2 dependence is information-theoretically necessary, and how much is due to uniform exploration. We close this gap by identifying the exact polynomial penalty on the number of arms as kq/2k^q/2. First, using a needle-in-haystack construction, we prove an algorithm-independent lower bound of Ω(σkmax(1,q)/T) (σ k (1,q)/T ); for q>1q>1 this lifts the classical k/T k/T rate to kq/T k^q/T, showing that the kq/2k^q/2 penalty is information-theoretically unavoidable. Second, we introduce the UCB-HARE (Harmonic Anchored Rank Exploration) algorithm, which replaces uniform sampling with an inverse-weighted rank schedule shielded by a certified positive-mean anchor. We show that its leading-order regret is O~(σkmax(1,q)/T) O (σ k (1,q)/T ), which matches the lower bound up to logarithmic factors. Experiments on synthetic instances confirm that UCB-HARE outperforms the uniform-exploration-based baselines, with the advantage growing in q. 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 νi _i supported on ℝR with mean μi _i. We denote the problem instance by the vector of distributions ν=(ν1,…,νk)ν=( _1,…, _k) and let μ⋆:=maxi∈[k]μi _ := _i∈[k] _i denote the optimal mean. At each round t∈[T]t∈[T], the learner selects an action It∈[k]I_t∈[k] according to a policy (an algorithm) A, which maps the observable history of past actions and rewards to a probability distribution over [k]:=1,…,k[k]:=\1,…,k\, and receives an independent reward Xt∼νItX_t _I_t. We define the ex-ante reward at round t as mt:=[μIt]m_t:=E[ _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 RT,avg(,ν):=μ⋆−1T∑t=1TmtR_T, avg( A,ν):= _ - 1T _t=1^Tm_t [8]. 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 [22], 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 [18], a principled replacement for the arithmetic mean is the generalized p-mean. For an ex-ante reward sequence (m1,…,mT)(m_1,…,m_T), with each mt∈ℝ≥0m_t _≥ 0, it is defined as p(m1,…,mT):=(1T∑t=1T(mt)p)1/p,p≠0,(∏t=1Tmt)1/T,p=0, M_p(m_1,…,m_T)\ :=\ cases ( 1T _t=1^T(m_t)^p )^1/p,&p≠ 0,\\[4.0pt] ( _t=1^Tm_t )^1/T,&p=0, cases with corresponding p-mean regret RT,p(,ν):=μ⋆−p(m1,…,mT)R_T,p( A,ν):=μ - M_p(m_1,…,m_T). The parameter p controls the strictness of the fairness requirement: p=1p=1 recovers classical average regret, p→0p→ 0 maximizes the geometric mean (Nash social welfare), and p→−∞p→-∞ approaches the strict Rawlsian maximin ideal. Throughout the paper, we make the following assumption. Assumption 1.1 (Non-Negative Means). The expected rewards satisfy μi≥0 _i≥ 0 for all i∈[k]i∈[k], with the optimal arm satisfying μ⋆>0 _ >0. This assumption is standard [5, 15, 21] 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 (μi≥0 _i≥ 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>0q=-p>0. By convention, if mt=0m_t=0 for any t∈[T]t∈[T], we set −q(m1,…,mT)=0 M_-q(m_1,…,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, −q(m1,…,mT)≤T1/qmint∈[T]mt M_-q(m_1,…,m_T)\ ≤\ T^1/q\, _t∈[T]m_t. Consequently, any exploration policy that assigns very low probability to the optimal arm, by driving mtm_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→0p→ 0), and [15] extended the framework to generalized p-mean regret for arbitrary p. For the sub-Gaussian model, [21] 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 μ^i(t)+ci(t) μ_i(t)+c_i(t), the empirical mean plus a confidence radius, thereby favoring arms that appear promising or remain uncertain [8]. 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 (mt)−q(m_t)^-q inside the objective and can dominate the regret. Writing q=−p>0q=-p>0, their algorithm attains O~q(σk(q+1)/2T) O_q\! ( σ\,k^(q+1)/2 T ) regret.111A subscript q in asymptotic notation (e.g. O~q O_q, Ωq _q, Θq _q) indicates that hidden constants may depend on q. This guarantee leaves open the optimal dependence on the number of arms, especially in the strongly fair regime q>1q>1. Uniform exploration assigns the unknown optimal arm only a 1/k1/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 ata_t at round t, then the corresponding inverse-power contribution scales as at−qa_t^-q. Thus, the factor k(q+1)/2k^(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 Ω(σkT) \! (σ kT ) [8], which extends to all p≤1p≤ 1 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: What is the intrinsic polynomial dependence on k for negative-power welfare, and how much of the k(q+1)/2k^(q+1)/2 dependence of uniform exploration is information-theoretically necessary? Resolving this question, especially if the minimax scale remains k/T k/T or rises to k(q+1)/2/Tk^(q+1)/2/ 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≥0q=-p≥ 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 kq/2/Tk^q/2/ 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∈[k]i∈[k] has a σ-sub-Gaussian reward distribution νi _i with a non-negative mean μi≥0 _i≥ 0, i.e., X∼νi[exp(λ(X−μi))]≤exp(σ2λ22)E_X _i[ (λ(X- _i))]≤ ( σ^2λ^22 ) for all λ∈ℝλ . Define the class ℰ(k,σ)+:=ν=(ν1,…,νk)∣∀i∈[k],νi is σ-sub-Gaussian with mean 0≤μi<∞.E_ SG(k,σ)^+:= \ν=( _1,…, _k) ∀ i∈[k],\, _i is σ-sub-Gaussian with mean 0≤ _i<∞ \. The minimax (−q)(-q)-mean regret over this class is defined as ℜT,−q(k,σ):=infsupν∈ℰ(k,σ)+RT,−q(,ν),whereRT,p(,ν):=μ⋆−p(m1,…,mT). R_T,-q(k,σ)\ :=\ _ A\ _ν _ SG(k,σ)^+\ R_T,-q( A,ν), R_T,p( A,ν):=μ - M_p(m_1,…,m_T). We focus on the case that each μi _i and σ are constants that do not scale with k and T. Theorem 1.1 (Minimax lower bound). Fix q=−p>0q=-p>0. For any number of arms k≥8k≥ 8 and horizon T≥1T≥ 1, the (−q)(-q)-mean regret over ℰ(k,σ)+E_ SG(k,σ)^+ satisfies ℜT,−q(k,σ)≥Ωq(σkmax(1,q)T). R_T,-q(k,σ)\ ≥\ _q\! (σ k (1,q)T ). For the strongly fair regime (q>1q>1), this lifts the classical k/T k/T bound to exactly kq/2/Tk^q/2/ 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 [8], 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 4.7) 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 kq/2k^q/2 price; the same principle is can be adapted to general bandit settings, e.g., linear bandits [1, 20]. 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/k1/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/r1/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. Theorem 1.2 (Instance-Dependent Upper Bound). Fix q=−p>0q=-p>0. For any fixed instance ν∈ℰ(k,σ)+ν _ SG(k,σ)^+ with optimal mean μ⋆>0 _ >0, UCB-HARE guarantees RT,−q(UCB-HARE,ν)≤O~q(σHkKq(k)T+μ⋆HkKq(k)T),R_T,-q( UCB-HARE,ν)≤ O_q σ H_kK_q(k)T+ _ H_kK_q(k)T , where Hk=∑r=1k1/rH_k= _r=1^k1/r is harmonic number, and Kq(k)=∑r=1k(k/r)qK_q(k)= _r=1^k(k/r)^q is generalized harmonic sum. By the standard asymptotics Hk=Θ(logk)H_k= ( k) and Kq(k)=Θq(k),0<q<1,Θ(klogk),q=1,Θq(kq),q>1.⟹RT,−q(-,ν)≤O~q(σk/T),0<q<1,O~(σk/T),q=1,O~q(σkq/T),q>1.K_q(k)= cases _q(k),&0<q<1,\\ (k k),&q=1,\\ _q(k^q),&q>1. cases R_T,-q( UCB-HARE,ν)≤ cases O_q\! (σ k/T ),&0<q<1,\\[5.69054pt] O\! (σ k/T ),&q=1,\\[5.69054pt] O_q\! (σ k^q/T ),&q>1. cases Thus, after poly-logarithmic factors are suppressed, - UCB-HARE matches the lower bound for every fixed q>0q>0: for 0<q≤10<q≤ 1, the classical k/T k/T term remains dominant, while for q>1q>1 the negative-power objective raises the polynomial dependence to kq/2/Tk^q/2/ T. Comparison with Prior Work. The best known upper bound for (−q)(-q)-mean regret is O~q(σk(q+1)/2T) O_q\! ( σ\,k^(q+1)/2 T ), which is achieved by the Welfarist-UCB algorithm [21]. In contrast, - UCB-HARE achieve the minimax O~q(σkq/2T) O_q\! ( σ\,k^q/2 T ) regret. Table 1 summarizes the comparison. Table 1: Regret bounds for q=−p>0q=-p>0 (polylog factors, q-dependent constants suppressed). For q>1q>1, our bounds raise the k/T k/T rate to kq/T k^q/T, closing the gap left open by prior work. Regime Prior Lower Bound Our Lower Bound Welfarist-UCB UCB-HARE(Ours) 0<q<10<q<1 σk/Tσ k/T σk/Tσ k/T σk(q+1)/2/Tσ k^(q+1)/2/ T σk/Tσ k/T q=1q=1 σk/Tσ k/T σk/Tσ k/T σk/Tσ k/ T σk/Tσ k/T q>1q>1 σk/Tσ k/T σkq/2/Tσ k^q/2/ T σk(q+1)/2/Tσ k^(q+1)/2/ T σkq/2/Tσ k^q/2/ T 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 (∏iui)1/n ( _iu_i )^1/n, equivalently ∑ilogui _i u_i – originates in Nash’s axiomatic treatment of bargaining [19]. The generalized-mean family p(u1,…,un)=(1n∑i=1nuip)1/p M_p(u_1,…,u_n)= ( 1n _i=1^nu_i^p )^1/p embeds it in a continuum: p=1p=1 is utilitarian welfare, p→0p→ 0 is Nash welfare, and p→−∞p→-∞ is egalitarian max-min welfare, with smaller p encoding stronger aversion to unequal utility profiles [3, 18]. 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 [13, 10]. The same logarithmic objective underlies proportional fairness in network resource allocation, and the broader α-fair family interpolates between proportional and max-min fairness, which are equivalent, up to monotone transformations, to the generalized-mean [14, 17, 16]. 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 [9], spawning a substantial approximation-algorithms literature [11, 2]. 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 [7, 4, 6, 12]. 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, - UCB-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 ν is drawn uniformly at random from a finite set :=ν(1),…,ν(k)V:=\ν^(1),…,ν^(k)\. If we can lower-bound the regret of an arbitrary algorithm averaged over j∈1,…,kj∈\1,…,k\, it follows that there must exist at least one specific index j (and hence, an instance ν(j)ν^(j)) for which the same lower bound applies. We construct V such that any arm i is optimal for at most one instance in this set – a “needle-in-haystack” configuration. Fix some μ>0μ>0. For each j∈[k]j∈[k], we define the instance ν(j)=(ν1(j),…,νk(j))ν^(j)= ( _1^(j),…, _k^(j) ) by νj(j)=(μ,σ2)andνi(j)=(0,σ2) for i≠j. _j^(j)=N(μ,σ^2) _i^(j)=N(0,σ^2) for i≠ j. so that the optimal arm for ν(j)ν^(j) (i.e., the j-th arm) fails to be optimal for any other instance ν(j′)ν^(j ). We write ℙjP_j for the law under ν(j)ν^(j) and ℙ(⋅)=1k∑j=1kℙj(⋅)P(·)= 1k _j=1^kP_j(·) 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 ⊆ℰ(k,σ)+V _ SG(k,σ)^+, any lower bound for V also holds over ℰ(k,σ)+E_ SG(k,σ)^+. Fix an arbitrary algorithm. Let aj,t:=ℙj(It=j)a_j,t:=P_j(I_t=j) be the probability of pulling the optimal arm at round t under ν(j)ν^(j). Since all other arms have mean zero, the ex-ante reward on ν(j)ν^(j) is mt(j)=μaj,tm_t^(j)=μ\,a_j,t, so the negative-power welfare on ν(j)ν^(j) depends only on the sequence (aj,t)t(a_j,t)_t. Let st:=1k∑j=1kaj,ts_t:= 1k _j=1^ka_j,t denote the average success probability at round t. Since x↦x−qx x^-q is convex for q=−p>0q=-p>0, Jensen’s inequality gives 1k∑jaj,t−q≥st−q 1k _ja_j,t^-q≥ s_t^-q for every t; averaging over time and then over the k instances, some ν(j)∈ν^(j) satisfies 1T∑taj,t−q≥1T∑tst−q 1T _ta_j,t^-q≥ 1T _ts_t^-q. Since x↦x−1/qx x^-1/q is decreasing, this yields (−q)(-q)-mean welfare of the ex-ante reward sequence −q(m1(j),…,mT(j)):=(1T∑t=1T(mt)−q)−1/q=μ(1T∑t=1Taj,t−q)−1/q≤μ(1T∑t=1Tst−q)−1/q. M_-q (m_1^(j),…,m_T^(j) ):= 1TΣ _t=1^T(m_t)^-q ^-1/q=μ 1TΣ _t=1^Ta_j,t^-q ^-1/q≤μ 1TΣ _t=1^Ts_t^-q ^-1/q. The lower bound, therefore, reduces to the question: how large an inverse-power cost ∑tst−q _ts_t^-q must a learner incur to raise sts_t from its uninformed baseline 1/k1/k to a constant scale? Two key estimates connect the success probability sts_t to the history ℋt−1=I1,X1,…,It−1,Xt−1H_t-1=\I_1,X_1,…,I_t-1,X_t-1\. Let ℐt:=I(J;ℋt−1)I_t:=I(J;H_t-1) denote the mutual information that the history carries about the arm J∼Unif([k])J ([k]).222Three objects share the symbol I and should not be conflated: the action It∈[k]I_t∈[k] selected at round t; the mutual-information operator I(⋅;⋅)I(·\,;·); and the mutual information ℐt:=I(J;ℋt−1)I_t:=I(J;H_t-1) between the random index and the history. We write ℐtI_t in script throughout to distinguish it from the action ItI_t. For s∈[1/k,1]s∈[1/k,1], define dk(s):=(s∥1k)d_k(s):= kl\! (s\, \|\, 1k ), the binary relative entropy between Bernoulli(s)(s) and Bernoulli(1/k)(1/k). It satisfies dk(1/k)=0d_k(1/k)=0, is nonnegative, and is increasing on [1/k,1][1/k,1]. Because sts_t may dip below 1/k1/k, we track the truncated quantity rt:=maxst,1/kr_t:= \s_t,1/k\, so that dk(rt)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. Lemma 2.1 (Informal, see Lemma˜4.4). For every round t, dk(rt)≤ℐt\ d_k(r_t) _t. To see this, note that if st<1/ks_t<1/k, then rt=1/kr_t=1/k and the claim follows from dk(1/k)=0d_k(1/k)=0 and nonnegativity of mutual information. Otherwise st≥1/ks_t≥ 1/k, so rt=str_t=s_t. Here, the action ItI_t can be viewed as an estimator of the hidden index J. Since ItI_t is generated from ℋt−1H_t-1 and is independent of J, the data-processing inequality gives I(J;It)≤I(J;ℋt−1)=ℐtI(J;I_t)≤ I(J;H_t-1)=I_t, while this estimator succeeds with probability ℙ(It=J)=stP(I_t=J)=s_t, so the Fano converse yields I(J;It)≥dk(st)I(J;I_t)≥ d_k(s_t). Combining the two, we obtain ℐt≥dk(st)=dk(rt)I_t≥ d_k(s_t)=d_k(r_t). ∎ The second estimate controls the one-step growth of ℐtI_t in the "needle-in-haystack" problem. Lemma 2.2 (Informal, see Lemma˜4.5). At every round t, ℐt+1−ℐt≤λst≤λrtI_t+1-I_t≤λ s_t≤λ r_t, where λ:=((μ,σ2)∥(0,σ2))=μ2/(2σ2)λ:= KL\! (N(μ,σ^2)\, \|\,N(0,σ^2) )=μ^2/(2σ^2). 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 (0,σ2)N(0,σ^2): if It≠JI_t≠ J the reward has law (0,σ2)N(0,σ^2), so its divergence from the reference is zero, whereas if It=JI_t=J the reward has law (μ,σ2)N(μ,σ^2), at KL-divergence exactly λ. Averaging over It=J\I_t=J\ gives ℐt+1−ℐt≤λℙ(It=J)=λstI_t+1-I_t≤λ\,P(I_t=J)=λ s_t; the second inequality follows from st≤rts_t≤ r_t. ∎ The two estimates above reduce the lower-bound argument to a deterministic calculation. The variable rtr_t tracks the learner’s progress from the random-guessing scale 1/k1/k toward constant success probability. When rtr_t is of order r, the inverse-power penalty is of order r−q−1r^-q-1, while one round can acquire at most λrλ r units of information. Raising rtr_t from 1/k1/k to a constant scale thus costs r−q−1/λr^-q-1/λ per unit of information demanded, and integrating this rate against the information requirement dk′(s)d_k (s) gives a leading cost of order 1λ∫1/k1/2s−q−1dk′(s)s 1λ _1/k^1/2s^-q-1\,d_k (s)\,ds. Since dk′(s)=log((k−1)s1−s)d_k (s)= \! ( (k-1)s1-s ), this integral already contributes order kqk^q on the subinterval [2/k,4/k][2/k,4/k], yielding the following deterministic inequality. Claim 2.3 (Informal, see Lemma˜4.6). Let rt∈[1/k,1]r_t∈[1/k,1] and let ℐtI_t be nondecreasing with ℐ1=0,dk(rt)≤ℐtI_1=0,\,d_k(r_t) _t, and ℐt+1−ℐt≤λrtI_t+1-I_t≤λ r_t for all t∈[T]t∈[T]. Then there exists a constant cq>0c_q>0, depending only on q, such that ∑t=1T(rt−q−1)≥cqmin(T,kqλ) _t=1^T r_t^-q-1 \ ≥\ c_q\, T,\ k^qλ . Since rt≥str_t≥ s_t gives st−q≥rt−qs_t^-q≥ r_t^-q, combining the averaging argument above with Claim˜2.3 produces a fixed instance ν(j)ν^(j) with 1T∑t=1Taj,t−q≥ 1+Ωq(min(1,kqλT)) 1T _t=1^Ta_j,t^-q\ ≥\ 1+ _q 1,\ k^qλ T . Substituting λ=μ2/(2σ2)λ=μ^2/(2σ^2), the (−q)(-q)-mean regret is bounded below by Ωq(μmin(1,σ2kqμ2T)) _q μ\, (1, σ^2k^qμ^2T) . Choosing μ=σkq/Tμ=σ k^q/T balances the two terms and yields the negative-power lower bound Ωq(σkq/2/T) _q σ k^q/2/ T . Combined with the classical average-regret baseline Ω(σk/T) σ k/T [8] (which carries over to (−q)(-q)-mean regret by monotonicity of generalized means (Lemma˜3.1)), this gives the minimax lower bound Ωq(σkmax1,q/T) _q σ k \1,q\/T . ∎ A general information-cost inequality. Claim 2.3 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−1r^-q-1 is a non-increasing function of the success probability; the information needed to sustain success probability r is at least dk(r)d_k(r); and this information can grow by at most λrλ r per round. Abstracting these into a cost c, an information requirement ϕφ, and an acquisition rate ψ, the same argument gives the following (Lemma˜4.7): if ϕ(rt)≤ℐtφ(r_t) _t and ℐt+1−ℐt≤λψ(rt)I_t+1-I_t≤λ\,ψ(r_t) for a non-increasing cost c, a strictly increasing ϕφ with ϕ(1/k)=0φ(1/k)=0, and a non-decreasing ψ, then ∑t=1Tc(rt)≥minc(s⋆)T,1λ∫1/ks⋆c(r)ϕ′(r)ψ(r)dr _t=1^Tc(r_t)\ ≥\ \! \\,c(s )\,T,\ \ 1λ _1/k^s c(r)\,φ (r)ψ(r)\,dr \ for any target scale s⋆s . The negative-power bound of Claim 2.3 is recovered (Corollary˜4.8) by taking c(r)=r−q−1c(r)=r^-q-1, ϕ=dkφ=d_k, ψ(r)=rψ(r)=r, and s⋆=1/2s =1/2, whereupon the integral evaluates to order kq/λk^q/λ. Stated this way, the objective enters only through the cost c and the problem’s structure only through the acquisition rate ψ, 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/k1/k. Yet prior algorithms [21] 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 π over [k][k], mapping each rank r∈[k]r∈[k] to a unique arm πr _r. Next, partition the time horizon into a rigid tiling of 2-round blocks (see Figure˜1). Each block b≥1b≥ 1 spans the two bandit rounds: t=2b−1t=2b-1 and t=2bt=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). Phase I: Preparation (HARE) Phase I: Exploitation (UCB)Block timeline (b) ⟶ (t) ⟶ …AuxSchUnblockPhase I stops at t=τt=τ (even)Bτ>0andmini∈[k]Ni≥32σ2LBτ2B_τ>0 _i∈[k]N_i≥ 32σ^2LB_τ^2UCBUCBUCBb=1b=1b=2b=2b=⌈τ/2⌉b= τ/2 =1t=1t=2t=2t=3t=3t=4t=4t=τ−1t=τ-1t=τt= =τ+1t=τ+1t=τ+2t=τ+2 Figure 1: Phase I demonstrates harmonic anchored rank exploration. Sch denotes the Scheduled Slot, reserved for exploration while Aux denotes the Auxiliary Slot. The exact ordering of these slots in a block b is decided by a fair coin θb∼Ber(1/2) _b (1/2), drawn afresh when that block begins. The Scheduled Slot comes first if θb=1 _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 rbr_b (equivalently, arm πrb _r_b) to explore. This schedule, denoted by the sequence (rb)b≥1(r_b)_b≥ 1, is generated by iterating an integer n=1,2,3,…n=1,2,3,… serially through the natural numbers and appending all divisors d≤kd≤ k of each n in ascending order (see Figure˜2). Observe that this design exhibits a harmonic property. Since any rank r divides a 1/r1/r fraction of consecutive integers, its exploration frequency is proportional to 1/r1/r. Also, the sequence, being generated entirely a priori, remains independent of the reward history. rb: 1,﹈ 1, 2,﹈ 1, 3,﹈ 1, 2, 4,﹈ 1, 5,﹈ 1, 2, 3,6,﹈ 1,7,﹈ 1, 2, 4,8,﹈ 1, 3,9,﹈ 1, 2, 5,10,﹈…n:12345678910… array[]r c c c c c c c c c c lr_b:& \;1,\; 10& \;1,\;2, 10& \;1,\;3, 10& \;1,\;2,\;4, 10& \;1,\;5, 10& \;1,\;2,\;3,\; [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,0 [rgb]0,0,0 [named]pgfstrokecolorrgb0,0,0 @color@gray@stroke0 @color@gray@fill06,\; 10& \;1,\; [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,0 [rgb]0,0,0 [named]pgfstrokecolorrgb0,0,0 @color@gray@stroke0 @color@gray@fill07,\; 10& \;1,\;2,\;4,\; [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,0 [rgb]0,0,0 [named]pgfstrokecolorrgb0,0,0 @color@gray@stroke0 @color@gray@fill08,\; 10& \;1,\;3,\; [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,0 [rgb]0,0,0 [named]pgfstrokecolorrgb0,0,0 @color@gray@stroke0 @color@gray@fill09,\; 10& \;1,\;2,\;5,\; [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,0 [rgb]0,0,0 [named]pgfstrokecolorrgb0,0,0 @color@gray@stroke0 @color@gray@fill010,\; 10&…\\[6.45831pt] n:&1&2&3&4&5&6&7&8&9&10&… array Figure 2: (Harmonic schedule for k=5k=5 arms) The sequence rbr_b iteratively appends divisors of n, discarding any divisor >k>k. Each block b maps to a rank rbr_b. Auxiliary Slot. This slot pulls the safest known arm, if available, to defend the welfare floor. Let c(n):=σ2log(8kT/δ)nc(n):=σ 2 (8kT/δ)n denote the confidence radius after n samples (δ∈(0,1)δ∈(0,1) is the confidence level). Writing μ^i(t) μ_i(t) and Ni(t)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 Bt−1:=maxi∈[k]μ^i(t−1)−c(Ni(t−1)),B_t-1:= _i∈[k]\ μ_i(t-1)-c(N_i(t-1))\, where t is its allotted round. If Bt−1>0B_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 πrb _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 τ, defined as the first even round t such that Bt>0andmini∈[k]Ni(t)≥32σ2log(8kT/δ)/Bt2.B_t>0 _i∈[k]N_i(t)≥ 32σ^2 (8kT/δ)/B_t^2. (2.4) 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 I: Exploitation. Upon satisfying (2.4), the block structure is discarded. For all subsequent rounds t>τt>τ, the algorithm employs the standard UCB index to pull arms, i.e., it selects the arm It:=argmaxi∈[k]μ^i(t−1)+c(Ni(t−1)).I_t:= *arg\,max _i∈[k]\ μ_i(t-1)+c(N_i(t-1))\. Remarks on Algorithm Design. (i) Block boundaries. The stopping condition is evaluated only at even rounds (block boundaries), so the event τ>t\τ>t\ depends solely on the history prior to block b and is independent of the intra-block coin flip θb _b. This preserves the strict 1/21/2 marginal probabilities that the ex-ante reward bound (Lemma˜6.5) relies on; evaluating mid-block could truncate the auxiliary slot and break them. (i) Dynamic thresholding. The anchor threshold Bt−1B_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 Algorithm˜1. 2.3 Upper Bound We begin with a deterministic conversion that reduces the nonlinear (−q)(-q)-mean regret to a cumulative inverse penalty. Define it as AT:=∑t=1T[(μ⋆/mt)q−1]A_T:= _t=1^T [( _ /m_t)^q-1 ], where mt:=[μIt]m_t:=E[ _I_t], μ⋆:=maxi∈[k]μi _ := _i∈[k] _i. Lemma 2.5 (Inverse penalty conversion; informal, see Lemma˜3.2). RT,−q≤μ⋆q⋅ATTR_T,-q≤ _ q· A_TT. To see this, factor μ⋆ _ out of the (−q)(-q)-mean to get −q(m1,…,mT)=μ⋆(1+AT/T)−1/q M_-q(m_1,…,m_T)= _ \,(1+A_T/T)^-1/q; the bound then follows from the elementary inequality 1−(1+u)−1/q≤u/q1-(1+u)^-1/q≤ u/q for u≥0u≥ 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/δ)L:= (8kT/δ) and c(n):=σ2L/nc(n):=σ 2L/n, and define ℰ:=∀i∈[k],∀n≤T:|μ^i,n−μi|≤c(n)E:=\\,∀ i∈[k],\ ∀ n≤ T:\ | μ_i,n- _i|≤ c(n)\,\. Applying sub-Gaussian concentration to each of the kTkT arm–count pairs and a union bound gives Pr(ℰ)≥1−δ/4 (E)≥ 1-δ/4. On ℰE every lower confidence bound is valid, Li(t):=μ^i(t)−c(Ni(t))≤μiL_i(t):= μ_i(t)-c(N_i(t))≤ _i, so whenever Bt:=maxiLi(t)>0B_t:= _iL_i(t)>0, any maximizing arm a satisfies μa≥La(t)=Bt>0 _a≥ 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⋆:=max⌈128σ2L/μ⋆2⌉, 1n_ := \ 128σ^2L/ _ ^2 ,\,1\, S:=⌈Hkn⋆⌉S:=\; H_kn_ , and T0:=18kST_0:=18kS. Lemma 2.6 (Finite Preparation Window; informal, see Lemmas˜6.2 and 6.6). On ℰE, an anchor exists once the optimal arm has received n⋆n_ samples, and the harmonic schedule forces Phase I to terminate by round T0=18kHkn⋆T_0=18kH_kn_ . To see this, suppose the optimal arm i⋆i_ has n⋆n_ samples. Its confidence radius is then c(Ni⋆)≤σ2L/(128σ2L/μ⋆2)=μ⋆/8c(N_i_ )≤σ 2L/(128σ^2L/ _ ^2)= _ /8. So on ℰE, Li⋆(t)=μ^i⋆(t)−c(Ni⋆(t))≥μ⋆−2c(Ni⋆(t))≥34μ⋆,L_i_ (t)= μ_i_ (t)-c(N_i_ (t))≥ _ -2c(N_i_ (t))≥ 34 _ , giving Bt>0B_t>0 and hence an anchor. For the duration, the prefix-balance property of the harmonic schedule guarantees that by block 8kS+18kS+1 every rank (and thus every arm) has at least n⋆n_ samples. At that point the optimal arm certifies Bt≥3μ⋆/4B_t≥ 3 _ /4, and the stopping threshold satisfies 32σ2L/Bt2≤32σ2L/(3μ⋆/4)2=5129σ2L/μ⋆2≤n⋆32σ^2L/B_t^2≤ 32σ^2L/(3 _ /4)^2= 5129σ^2L/ _ ^2≤ n_ . So the stopping condition holds at this block boundary, and since each block spans two rounds, Phase I ends by T0=18kST_0=18kS. ∎ We split the cumulative inverse penalty at this deterministic time, AT≤∑t=1T∧T0[(μ⋆/mt)q−1]⏟ATprep+∑t=T0+1T[(μ⋆/mt)q−1]⏟ATUCB,A_T≤ Σ _t=1^T T_0 [( _ /m_t)^q-1 ]_A_T^prep+ Σ _t=T_0+1^T [( _ /m_t)^q-1 ]_A_T^UCB, with ATUCB:=0A_T^UCB:=0 if T≤T0T≤ T_0. This is to avoid conditioning on the random stopping time τ. We first control the preparation term. For block b, define the expanding frontier ab:=mink,⌊(b−1)/8S⌋a_b:= \k, (b-1)/8S \: by the start of block b, every arm whose random rank is at most aba_b has accumulated enough samples to certify an anchor, were it the optimal arm. Claim 2.7 (Growing reward floor; informal, see Lemma˜6.5). There is a universal constant c0>0c_0>0 (one may take c0=1/4c_0=1/4) such that for every round t, with b=⌈t/2⌉b= t/2 , mt≥c0μ⋆max1/k,ab/k\ m_t≥ c_0 _ \1/k,\ a_b/k\. To see this, let R⋆R_ be the rank of the optimal arm under the initial permutation, so R⋆R_ is uniform on [k][k]. The ex-ante reward has two sources. The scheduled slot is the current round with probability 1/21/2 (the within-block coin flip), and the scheduled arm is optimal with probability 1/k1/k, giving a baseline contribution of order μ⋆/k _ /k. The auxiliary slot contributes when R⋆≤abR_ ≤ a_b: the optimal arm then has n⋆n_ samples by the start of block b, which on ℰE certifies an anchor of mean at least 3μ⋆/43 _ /4. Since Pr(R⋆≤ab)=ab/k (R_ ≤ a_b)=a_b/k, the round is the auxiliary slot with probability 1/21/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 μ⋆ab/k _ a_b/k. Finally, if Phase I has already ended before round t, the Phase-I rule is at least as safe (shown below in Lemma˜2.9), so in all cases mt≥c0μ⋆max1/k,ab/km_t≥ c_0 _ \1/k,\ a_b/k\. ∎ The reward floor yields a bound on the preparation penalty. Claim 2.8 (Preparation inverse penalty; informal, see Lemma˜6.7). There exists a constant Cq>0C_q>0, depending only on q, such that ATprep=∑t=1T∧T0[(μ⋆/mt)q−1]≤CqSKq(k),whereKq(k):=∑r=1k(kr)q.A_T^prep=Σ _t=1^T T_0 [( _ /m_t)^q-1 ]≤ C_q\,S\,K_q(k),\,where\,\,K_q(k):=Σ _r=1^k ( kr )^q. To see this, note the window t≤T∧T0t≤ T T_0 spans at most 9kS9kS blocks (T0=18kST_0=18kS, two rounds per block), and by Claim˜2.7 every round in block b has (μ⋆/mt)q≤Cqmax1/k,ab/k−q( _ /m_t)^q≤ C_q \1/k,\,a_b/k\^-q. We partition the blocks by the frontier value aba_b: the first 8S8S blocks have ab=0a_b=0 and contribute Oq(Skq)O_q(Sk^q); each value ab=ra_b=r for r=1,…,k−1r=1,…,k-1 persists for O(S)O(S) blocks, contributing Oq(S(k/r)q)O_q (S(k/r)^q ); and the saturated blocks (ab=ka_b=k) add Oq(S)O_q(S). Summing up, we get ATprep≤CqS∑r=1k(kr)q=CqSKq(k)A_T^prep≤ C_qS _r=1^k ( kr )^q=C_qS\,K_q(k). ∎ It remains to control the rounds after T0T_0. The stopping rule ensures that, once Phase I begins, every arm has a confidence radius small relative to μ⋆ _ . Lemma 2.9 (Phase-I safety; informal, see Lemma˜6.4). On ℰE, if Phase I stops at round τ, then every arm selected by the UCB rule in Phase I has a true mean of at least μ⋆/2 _ /2. To see this, recall that at the stopping time Bτ>0B_τ>0 and miniNi(τ)≥32σ2L/Bτ2 _iN_i(τ)≥ 32σ^2L/B_τ^2. On ℰE no lower confidence bound exceeds its true mean, so Bτ≤μ⋆B_τ≤ _ ; hence every arm has at least 32σ2L/μ⋆232σ^2L/ _ ^2 samples and confidence radius at most μ⋆/4 _ /4. Now let i be any arm selected by UCB in Phase I. Its index dominates the optimal arms’, μ^i(t)+c(Ni(t))≥μ^i⋆(t)+c(Ni⋆(t))≥μ⋆ μ_i(t)+c(N_i(t))≥ μ_i_ (t)+c(N_i_ (t))≥ _ , so μi≥μ^i(t)−c(Ni(t))=(μ^i(t)+c(Ni(t)))−2c(Ni(t))≥μ⋆−μ⋆2=μ⋆2. _i≥ μ_i(t)-c(N_i(t))= ( μ_i(t)+c(N_i(t)) )-2c(N_i(t))≥ _ - _ 2= _ 2. This safety property lets the Phase-I penalty be controlled by UCB pseudo-regret. Claim 2.10 (Phase-I inverse penalty; informal, see Lemma˜6.8). There exists a constant Cq>0C_q>0, depending only on q, such that ATUCB=∑t=T0+1T[(μ⋆/mt)q−1]≤Cq(σμ⋆kTL+Tδ).A_T^UCB=Σ _t=T_0+1^T [( _ /m_t)^q-1 ]≤ C_q ( σ _ kTL+Tδ ). To see this, assume T>T0T>T_0 (else the sum is empty). By Lemma˜2.6, all rounds t>T0t>T_0 lie in Phase I, and on ℰE, Lemma˜2.9 gives selected mean at least μ⋆/2 _ /2; since Pr(ℰ)≥1−δ/4 (E)≥ 1-δ/4, this yields the unconditional floor mt≥μ⋆/4m_t≥ _ /4. On mt∈[μ⋆/4,μ⋆]m_t∈[ _ /4, _ ] the inverse-power map is locally Lipschitz, so (μ⋆/mt)q−1≤Cq(μ⋆−mt)/μ⋆( _ /m_t)^q-1≤ C_q( _ -m_t)/ _ . The numerator μ⋆−mt _ -m_t is the expected pseudo-regret at round t; on ℰE the standard UCB argument bounds its cumulative sum over Phase I by O(σkTL)O(σ kTL), while ℰcE^c contributes at most O(μ⋆Tδ)O( _ Tδ). Dividing by μ⋆ _ gives the displayed bound. ∎ Combining Claims˜2.8 and 2.10 gives AT≤Cq(SKq(k)+σμ⋆kTL+Tδ)A_T≤ C_q (S\,K_q(k)+ σ _ kTL+Tδ ), where S=⌈Hkn⋆⌉S= H_kn_ . Since n⋆≤1+128σ2L/μ⋆2n_ ≤ 1+128σ^2L/ _ ^2, the preparation term obeys SKq(k)≤HkKq(k)(1+Cσ2L/μ⋆2)SK_q(k)≤ H_kK_q(k)\,(1+Cσ^2L/ _ ^2), and applying Lemma˜2.5 yields the (−q)(-q)-mean regret RT,−q≤Cq[μ⋆HkKq(k)T+σ2LHkKq(k)μ⋆T+σkLT+μ⋆δ].R_T,-q≤ C_q [ _ H_kK_q(k)T+ σ^2L\,H_kK_q(k) _ T+σ kLT+ _ δ ]. Because HkKq(k)≥kH_kK_q(k)≥ k, the third term satisfies σkL/T≤μ0σ kL/T≤ _0, where μ0:=σHkKq(k)L/T _0:=σ H_kK_q(k)L/T. For the second term, note that it equals exactly μ02/μ⋆ _0^2/ _ , which is large only when μ⋆ _ is small; there, however, the trivial bound RT,−q≤μ⋆R_T,-q≤ _ takes over. Combining the two, we get minμ⋆,μ02μ⋆≤μ0 \ _ ,\ _0^2 _ \≤ _0, so the second and third terms together contribute at most O(μ0)O( _0). The first and fourth terms carry through unchanged. Setting δ=1/Tδ=1/T gives RT,−q≤Cq[σHkKq(k)LT+μ⋆HkKq(k)T].R_T,-q≤ C_q [σ H_kK_q(k)LT+ _ H_kK_q(k)T ]. Paper Organization In Section˜3, we collect the main technical ingredients used throughout the paper. We begin with basic properties of (−q)(-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 - UCB-HARE. With these preliminaries established, Section˜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. Section˜5 presents the pseudocode of - UCB-HARE together with its main guarantee. The matching upper bound for - UCB-HARE is proved in Section˜6, where we combine the reward floor created during preparation with the safety of the subsequent UCB phase. Finally, Section˜7 presents our experimental evaluation and compares - UCB-HARE against uniform-exploration-based baselines. 3 Preliminaries We operate in the standard k-armed stochastic bandit setting over a horizon T. Let mt:=[μIt]m_t:=E[ _I_t] denote the ex-ante expected reward at round t, and let μ⋆:=maxi∈[k]μi _ := _i∈[k] _i. In this section, we establish some prerequisites for our analysis.Section˜3.1 introduces the welfare objective and the specific reductions we use to bound it. Section˜3.2 reviews the information-theoretic tools necessary for our minimax lower bounds. Finally, Section˜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 [15, 18] in the negative (fair) regime, which penalizes suboptimal assignments to early rounds. Parameterizing this regime by q=−p>0q=-p>0, we define the (−q)(-q)-mean welfare of the ex-ante reward sequence as: −q(m1,…,mT):=(1T∑t=1Tmt−q)−1/q. M_-q(m_1,…,m_T):= ( 1T _t=1^Tm_t^-q )^-1/q. The (−q)(-q)-mean regret of an algorithm A on instance ν is its welfare shortfall relative to the optimal fixed-arm policy: RT,−q(,ν):=μ⋆−q(m1,…,mT).R_T,-q( A,ν):= _ - M_-q(m_1,…,m_T). We begin with three properties. First, Lemma˜3.1 establishes monotonicity of the welfare function, which we use in our lower bound proof in Section˜4. Lemma 3.1 (Power mean monotonicity). Let x1,…,xT≥0x_1,…,x_T≥ 0. If p≤rp≤ r, then p(x1,…,xT)≤r(x1,…,xT), M_p(x_1,…,x_T)≤ M_r(x_1,…,x_T), with the usual continuous interpretation at p=0p=0. Proof. For positive coordinates, this is the classical generalized mean inequality derived via Jensen’s inequality. For coordinates equal to zero, the result follows by continuity, under the convention that negative-order means evaluate to zero if any coordinate is zero. ∎ The remaining two results aid Section˜6, where we establish upper bounds for - UCB-HARE. Lemma˜3.2 first isolates the outer non-linearity of the regret into a cumulative inverse penalty. Lemma˜3.3 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. Lemma 3.2 (First Linearization: Regret to Penalty). Let q>0q>0, μ⋆>0 _ >0, and recall mt∈(0,μ⋆]m_t∈(0, _ ] for all t. Define AT:=∑t=1T[(μ⋆mt)q−1].A_T:= _t=1^T [ ( _ m_t )^q-1 ]. Then RT,−q(,ν)≤μ⋆qATT.R_T,-q( A,ν)≤ _ q A_TT. Proof. Factoring out μ⋆ _ and substituting ATA_T, RT,−q(,ν) R_T,-q( A,ν) =μ⋆−q(m1,…,mT) = _ - M_-q(m_1,…,m_T) =μ⋆[1−(1T∑t=1T(μ⋆mt)q)−1/q] = _ [1- ( 1T _t=1^T ( _ m_t )^q )^-1/q ] =μ⋆[1−(1+ATT)−1/q] = _ [1- (1+ A_TT )^-1/q ] ≤μ⋆[1−(1−ATqT)]=μ⋆qATT, ≤ _ [1- (1- A_TqT ) ]= _ q A_TT, where the inequality uses (1+u)−1/q≥1−u/q(1+u)^-1/q≥ 1-u/q for u≥0u≥ 0, which holds because u↦(1+u)−1/qu (1+u)^-1/q is convex when q>0q>0, and 1−u/q1-u/q is its tangent line at u=0u=0. ∎ Lemma 3.3 (Second Linearization: Penalty to Pseudo-Regret). For every q>0q>0, there exists Cq>0C_q>0 such that for all x∈[1/4,1]x∈[1/4,1], x−q−1≤Cq(1−x).x^-q-1≤ C_q(1-x). Consequently, if y∈[μ⋆/4,μ⋆]y∈[ _ /4, _ ], then (μ⋆y)q−1≤Cqμ⋆−yμ⋆. ( _ y )^q-1≤ C_q _ -y _ . Proof. Let f(x)=x−qf(x)=x^-q. The bound holds for x=1x=1. For x∈[1/4,1)x∈[1/4,1), the Mean Value Theorem guarantees some c∈(x,1)c∈(x,1) such that f(1)−f(x)=f′(c)(1−x)f(1)-f(x)=f (c)(1-x). As f(1)=1f(1)=1, we get x−q−1 x^-q-1 =qc−q−1(1−x) =qc^-q-1(1-x) <q4q+1(1−x), <q4^q+1(1-x), where the inequality follows because c↦c−q−1c c^-q-1 is strictly decreasing and c>x≥1/4c>x≥ 1/4. Setting Cq:=q4q+1C_q:=q4^q+1 establishes the primary inequality. The consequence follows by substituting x=y/μ⋆x=y/ _ for any y∈[μ⋆/4,μ⋆]y∈[ _ /4, _ ]. ∎ 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 (P∥Q) KL(P\,\|\,Q). For Bernoulli distributions with parameters p,q∈(0,1)p,q∈(0,1), we denote the binary relative entropy by (p∥q):=plog(pq)+(1−p)log(1−p1−q). kl(p\,\|\,q):=p ( pq )+(1-p) ( 1-p1-q ). 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. Lemma 3.4. Let X and Y be random variables, and let PY|XP_Y|X denote the conditional distribution of Y given X. For any fixed reference distribution Q over the support of Y, the mutual information satisfies: I(X;Y)≤X[(PY∣X∥Q)].I(X;Y) _X [ KL(P_Y X\,\|\,Q) ]. Proof. By definition, I(X;Y)=X[(PY∣X∥PY)]I(X;Y)=E_X[ KL(P_Y X\,\|\,P_Y)], where PYP_Y is the marginal distribution of Y. For any reference distribution Q, we can expand the divergence as (PY∣X∥Q)=(PY∣X∥PY)+Y∣X[log(PY(Y)/Q(Y))] KL(P_Y X\,\|\,Q)= KL(P_Y X\,\|\,P_Y)+E_Y X[ (P_Y(Y)/Q(Y))]. Taking the expectation over X yields X[(PY∣X∥Q)]=I(X;Y)+(PY∥Q)E_X[ KL(P_Y X\,\|\,Q)]=I(X;Y)+ KL(P_Y\,\|\,Q). Since KL divergence is non-negative, the bound follows. ∎ The second property establishes a lower bound on the mutual information required to identify a uniformly drawn hypothesis. We express this via the function dk:[1/k,1]→ℝ+d_k:[1/k,1] _+, defined as dk(s):=slog(ks)+(1−s)log(k(1−s)k−1)=(s∥1k).d_k(s):=s (ks)+(1-s) ( k(1-s)k-1 )= kl (s\, \|\, 1k ). Note that dk(s)d_k(s) is strictly increasing on [1/k,1][1/k,1]. Lemma 3.5 (Mutual Information Fano Converse). Let J be a random variable drawn uniformly from [k][k]. Let J J be any estimator of J, and define the success probability as s:=ℙ(J^=J)s:=P( J=J). Then the mutual information satisfies: I(J;J^)≥dk(s).I(J; J)≥ d_k(s). Proof. Let E=J≠J^E= 1\J≠ J\ denote the binary error indicator, where ℙ(E=0)=sP(E=0)=s. We bound the conditional entropy H(J∣J^)H(J J) by expanding the joint conditional entropy H(E,J∣J^)H(E,J J) via the chain rule in two ways. First, H(E,J∣J^)=H(J∣J^)+H(E∣J,J^)H(E,J J)=H(J J)+H(E J, J). As E is deterministically computed from J and J J, the second term vanishes, yielding H(E,J∣J^)=H(J∣J^)H(E,J J)=H(J J). Second, expanding with respect to E yields H(E,J∣J^)=H(E∣J^)+H(J∣E,J^)H(E,J J)=H(E J)+H(J E, J). We bound the components on the right-hand side individually. Conditioning reduces entropy, so H(E∣J^)≤H(E)=Hb(s):=−slogs−(1−s)log(1−s),H(E J)≤ H(E)=H_b(s):=-s s-(1-s) (1-s), where HbH_b is the binary entropy function. For the remaining term, we condition on the realization of E: 1. If E=0E=0, J is exactly J J, yielding zero conditional entropy. 2. If E=1E=1, J must take one of the remaining k−1k-1 values, which has entropy at most log(k−1) (k-1). Averaging over the indicator E yields H(J∣E,J^)≤s(0)+(1−s)log(k−1)H(J E, J)≤ s(0)+(1-s) (k-1). Equating the two expansions bounds the conditional entropy, recovering Fano’s inequality: H(J∣J^)≤Hb(s)+(1−s)log(k−1).H(J J)≤ H_b(s)+(1-s) (k-1). By definition, the mutual information is I(J;J^)=H(J)−H(J∣J^)I(J; J)=H(J)-H(J J). Since J is uniformly distributed over [k][k], its prior entropy is H(J)=logkH(J)= k. We substitute our bounds and group the terms as follows: I(J;J^) I(J; J) ≥logk−[Hb(s)+(1−s)log(k−1)] ≥ k- [H_b(s)+(1-s) (k-1) ] =(slogk+(1−s)logk)+slogs+(1−s)log(1−s)−(1−s)log(k−1) = (s k+(1-s) k )+s s+(1-s) (1-s)-(1-s) (k-1) =s(logk+logs)+(1−s)[logk+log(1−s)−log(k−1)] =s( k+ s)+(1-s) [ k+ (1-s)- (k-1) ] =slog(ks)+(1−s)log(k(1−s)k−1) =s (ks)+(1-s) ( k(1-s)k-1 ) =dk(s). =d_k(s). ∎ 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≥1n≥ 1, define the truncated divisor set n:=d∈[k]:d∣nD_n:=\d∈[k]:d n\. The harmonic schedule, denoted (rb)b≥1(r_b)_b≥ 1, is constructed by concatenating the sets 1,2,…D_1,D_2,… in ascending order of n. For example, setting k=5k=5, the sequence discards any divisors strictly greater than k, yielding: rb: 1,﹈ 1, 2,﹈ 1, 3,﹈ 1, 2, 4,﹈ 1, 5,﹈ 1, 2, 3,6,﹈ 1,7,﹈ 1, 2, 4,8,﹈ 1, 3,9,﹈ 1, 2, 5,10,﹈…n:12345678910… array[]r c c c c c c c c c c lr_b:& \;1,\; 10& \;1,\;2, 10& \;1,\;3, 10& \;1,\;2,\;4, 10& \;1,\;5, 10& \;1,\;2,\;3,\; [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,0 [rgb]0,0,0 [named]pgfstrokecolorrgb0,0,0 @color@gray@stroke0 @color@gray@fill06,\; 10& \;1,\; [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,0 [rgb]0,0,0 [named]pgfstrokecolorrgb0,0,0 @color@gray@stroke0 @color@gray@fill07,\; 10& \;1,\;2,\;4,\; [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,0 [rgb]0,0,0 [named]pgfstrokecolorrgb0,0,0 @color@gray@stroke0 @color@gray@fill08,\; 10& \;1,\;3,\; [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,0 [rgb]0,0,0 [named]pgfstrokecolorrgb0,0,0 @color@gray@stroke0 @color@gray@fill09,\; 10& \;1,\;2,\;5,\; [rgb]1,0,0 [named]pgfstrokecolorrgb1,0,0 [rgb]0,0,0 [named]pgfstrokecolorrgb0,0,0 @color@gray@stroke0 @color@gray@fill010,\; 10&…\\[6.45831pt] n:&1&2&3&4&5&6&7&8&9&10&… array The primary advantage of this schedule is the following lemma, which allows us to track the pull count of each rank. Lemma 3.6 (Prefix Balance Lemma). For any rank r∈[k]r∈[k] and block b≥0b≥ 0, denote the number of scheduled pulls allocated to rank r up to and including block b, by Nrsch(b):=#s≤b:rs=rN_r sch(b):=\#\s≤ b:r_s=r\. Then, Nrsch(b)≥brHk−2,N_r sch(b)≥ brH_k-2, where Hk:=∑r=1k1/rH_k:= _r=1^k1/r. Proof. Based on our harmonic schedule, let block b be associated with integer nbn_b (recall Section˜2.2). Comparing index b against that of the last block mapped to nbn_b, we have b≤∑n=1nb|n|=∑r=1k⌊nbr⌋≤nb∑r=1k1r=nbHkb≤ _n=1^n_b|D_n|= _r=1^k n_br ≤ n_b _r=1^k 1r=n_bH_k and hence nb≥b/Hkn_b≥ b/H_k. For any rank r∈[k]r∈[k], its occurrences in the schedule up to block b must at least include every occurrence within the divisor sets 1,…,nb−1D_1,…,D_n_b-1 strictly prior to nbn_b. Therefore, Nrsch(b)≥∑n=1nb−1r∈n=∑n=1nb−1r∣n=⌊nb−1r⌋≥nbr−2≥brHk−2.N_r sch(b)≥ _n=1^n_b-1 1\r _n\= _n=1^n_b-1 1\r n\= n_b-1r ≥ n_br-2≥ brH_k-2. ∎ We also preemptively record here the asymptotic behavior of a certain harmonic penalty sum induced by the schedule (used later in Section˜6), which governs the final regret regime. Fact 3.7 (Asymptotics of the Harmonic Penalty). For any q>0q>0 and k≥1k≥ 1, define the harmonic penalty sum as Kq(k):=∑r=1k(k/r)qK_q(k):= _r=1^k(k/r)^q. Then: Kq(k)=Θq(k),0<q<1,Θ(klogk),q=1,Θq(kq),q>1.K_q(k)= cases _q(k),&0<q<1,\\ (k k),&q=1,\\ _q(k^q),&q>1. cases Proof. We can factor the sum as Kq(k)=kq∑j=1kj−qK_q(k)=k^q _j=1^kj^-q. The sum Sq(k):=∑j=1kj−qS_q(k):= _j=1^kj^-q can be bounded by comparing it to the integral of the monotonically decreasing function f(x)=x−qf(x)=x^-q over the continuous interval [1,k][1,k]: ∫1k+1x−qx≤Sq(k)≤1+∫1kx−qx. _1^k+1x^-q\,dx≤ S_q(k)≤ 1+ _1^kx^-q\,dx. Evaluating the integrals partitions the sequence into three standard regimes: 1. Sub-linear (0<q<10<q<1): The integral evaluates to x1−q1−q x^1-q1-q, yielding Sq(k)=Θq(k1−q)S_q(k)= _q(k^1-q). Multiplying by the leading kqk^q factor gives kq⋅Θq(k1−q)=Θq(k)k^q· _q(k^1-q)= _q(k). 2. Logarithmic (q=1q=1): The integral evaluates to logx x, bounding the harmonic number as log(k+1)≤S1(k)≤1+logk (k+1)≤ S_1(k)≤ 1+ k, yielding S1(k)=Θ(logk)S_1(k)= ( k). Multiplying by k1k^1 yields Θ(klogk) (k k). 3. Convergent (q>1q>1): The improper integral ∫1∞x−qx=1q−1 _1^∞x^-q\,dx= 1q-1 is finite, implying Sq(k)S_q(k) converges to a constant dependent on q. Multiplying by kqk^q gives Θq(kq) _q(k^q). Substituting these bounds establishes the claim. ∎ 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 k/T k/T to kq/T k^q/T. Theorem 4.1 (Main Lower Bound, Restated). For any fairness parameter q>0q>0, number of arms k≥8k≥ 8, and time horizon T≥1T≥ 1, the minimax (−q)(-q)-mean regret of any algorithm A is bounded as ℜT,−q(k,σ):=infsupν∈ℰ(k,σ)+RT,−q(,ν)≥cqσkqT, R_T,-q(k,σ):= _ A _ν _ SG(k,σ)^+R_T,-q( A,ν)≥ c_qσ k^qT, where cq>0c_q>0 is a constant depending only on q. We first establish the classical baseline for p≤1p≤ 1. Proposition 4.2 (Average Regret Baseline). For any power parameter p≤1p≤ 1, number of arms k≥2k≥ 2, and horizon T≥1T≥ 1: ℜT,p(k,σ)≥CσkT, R_T,p(k,σ)≥ Cσ kT, where C>0C>0 is a universal constant. Proof. For p≤1p≤ 1, power mean monotonicity (Lemma˜3.1) bounds the p-mean by the arithmetic mean. Thus, the generalized regret reduces to the usual average regret: RT,p(,ν)≥μ⋆−1T∑t=1Tmtν.R_T,p( A,ν)≥ _ - 1T _t=1^Tm_t^ν. To lower bound the minimax over the sub-gaussian class ℰ(k,σ)+E_ SG(k,σ)^+, we restrict the supremum to the subset of Gaussian instances with variance σ2σ^2. As this Gaussian family is inherently σ-sub-Gaussian, the standard information-theoretic reduction over this hard subset [8] directly establishes the Ω(σk/T) (σ k/T) baseline. ∎ For our main proof, we focus on k difficult “one-good-arm” instances and average the regret over them. Fix q>0q>0, k≥8k≥ 8 and μ>0μ>0. For each j∈[k]j∈[k], define the underlying instance ν(j)ν^(j) by: νi(j)=(μ,σ2),i=j,(0,σ2),i≠j. _i^(j)= casesN(μ,σ^2),&i=j,\\ N(0,σ^2),&i≠ j. cases Let ℙjP_j denote the probability measure under instance ν(j)ν^(j). Let J∼([k])J Unif([k]) index a uniformly random instance, and define ℙP as the law averaged over this random choice, ℙ(⋅):=1k∑j=1kℙj(⋅)P(·):= 1k _j=1^kP_j(·) under which J is first drawn and then instance ν(J)ν^(J) is executed. We define the algorithm’s instance-specific success probability aj,ta_j,t and average success probability sts_t at round t as: aj,t:=ℙj(It=j),st:=ℙ(It=J)=1k∑j=1kaj,t.a_j,t:=P_j(I_t=j), s_t:=P(I_t=J)= 1k _j=1^ka_j,t. Lemma 4.3 (A Fixed-Instance Reduction). There exists an instance j∈[k]j∈[k] such that the time-averaged penalty is bounded below by the ensemble averaged penalty: 1T∑t=1Taj,t−q≥1T∑t=1Tst−q, 1T _t=1^Ta_j,t^-q≥ 1T _t=1^Ts_t^-q, where we define 0−q:=+∞0^-q:=+∞. Proof. Because the map x↦x−qx x^-q is strictly convex on (0,∞)(0,∞), Jensen’s inequality implies that for any round t: 1k∑j=1kaj,t−q≥(1k∑j=1kaj,t)−q=st−q. 1k _j=1^ka_j,t^-q≥ ( 1k _j=1^ka_j,t )^-q=s_t^-q. Averaging both sides over all rounds t∈[T]t∈[T] yields: 1k∑j=1k(1T∑t=1Taj,t−q)≥1T∑t=1Tst−q. 1k _j=1^k ( 1T _t=1^Ta_j,t^-q )≥ 1T _t=1^Ts_t^-q. By the pigeonhole principle, the maximum over the k instances must be at least as large as the ensemble average, meaning there must exist at least one index j∈[k]j∈[k] satisfying the claim. ∎ To bound the success probability sts_t, we track the mutual information collected by any algorithm on J prior to round t, denoted as ℐt:=I(J;ℋt−1)I_t:=I(J;H_t-1). Recall from our preliminaries (Section˜3.2) that the function dk(s):=(s∥ 1/k)d_k(s):= kl(s\,\|\,1/k) represents the minimum information required to guess the optimal arm with success probability s. Lemma 4.4 (Information Lower Bound on Success). Let rt:=maxst,1/kr_t:= \s_t,1/k\. Then dk(rt)≤ℐt.d_k(r_t) _t. Proof. If st<1/ks_t<1/k, then rt=1/kr_t=1/k. Because dk(1/k)=0d_k(1/k)=0 and mutual information is strictly non-negative, the bound dk(rt)≤ℐtd_k(r_t) _t holds trivially. If st≥1/ks_t≥ 1/k, then rt=str_t=s_t. We can view the algorithm’s action ItI_t as an estimator of the optimal arm J. Because ItI_t is generated using only the observed history ℋt−1H_t-1 and independent randomization, the Data Processing Inequality implies I(J;It)≤I(J;ℋt−1)=ℐtI(J;I_t)≤ I(J;H_t-1)=I_t. Finally, Lemma˜3.5 bounds the information from below as ℐt≥I(J;It)≥dk(st)=dk(rt).I_t≥ I(J;I_t)≥ d_k(s_t)=d_k(r_t). ∎ Lemma 4.5 (One-Step Information Gain). Let λ:=((μ,σ2)∥(0,σ2))=μ22σ2λ:= KL(N(μ,σ^2)\,\|\,N(0,σ^2))= μ^22σ^2. Then for every round t, the information gain satisfies: ℐt+1−ℐt≤λst.I_t+1-I_t≤λ s_t. Proof. By the chain rule of mutual information and the conditional independence of an algorithm’s internal randomization, the step-wise information gain is exactly ℐt+1−ℐt=I(J;Yt∣ℋt−1,It)I_t+1-I_t=I(J;Y_t _t-1,I_t). We invoke Lemma˜3.4 using the suboptimal arm distribution Q=(0,σ2)Q=N(0,σ^2) as the reference distribution. As the true reward distribution matches Q exactly whenever J≠ItJ≠ I_t, the conditional KL divergence vanishes entirely on suboptimal pulls, isolating the penalty to just the optimal pulls. Hence, I(J;Yt∣ℋt−1,It) I(J;Y_t _t-1,I_t) ≤J,It,ℋt−1[(PYt∣J,It,ℋt−1∥Q)] _J,I_t,H_t-1 [ KL (P_Y_t J,I_t,H_t-1\,\|\,Q ) ] (conditional reference bound) =J,It[J=It((μ,σ2)∥(0,σ2))] =E_J,I_t [ 1\J=I_t\ KL(N(μ,σ^2)\,\|\,N(0,σ^2)) ] (marginalizing out ℋt−1H_t-1) =λJ,It[J=It]=λst. =λ\,E_J,I_t [ 1\J=I_t\ ]=λ s_t. (definition of success probability) ∎ Lemma 4.6 (Main Information-Cost Inequality). Let q>0q>0 and k≥8k≥ 8. Suppose a sequence rt∈[1/k,1]r_t∈[1/k,1] and a non-decreasing sequence ℐtI_t satisfy ℐ1=0I_1=0, dk(rt)≤ℐtd_k(r_t) _t, and ℐt+1−ℐt≤λrtI_t+1-I_t≤λ r_t for all t∈[T]t∈[T]. Then there exists a constant cq>0c_q>0, depending only on q, such that: ∑t=1T(rt−q−1)≥cqminT,kqλ. _t=1^T(r_t^-q-1)≥ c_q \T, k^qλ \. Proof. Define the continuous extension D(s):=dk(s)D(s):=d_k(s), which is strictly increasing on the interval [1/k,1][1/k,1]. We split the analysis into two cases based on the fact that in the first round, the information crosses a constant threshold. Let τ:=inft∈[T]:ℐt≥D(1/2)τ:= \t∈[T]:I_t≥ D(1/2)\, setting τ=+∞τ=+∞ if this never occurs. Case 1 (τ=+∞τ=+∞): For all rounds t, we have D(rt)≤ℐt<D(1/2)D(r_t) _t<D(1/2). Because D is strictly increasing, this implies rt<1/2r_t<1/2. Therefore, rt−q−1≥2q−1r_t^-q-1≥ 2^q-1. Summing this constant over all T rounds immediately satisfies the bound. Case 2 (τ<+∞τ<+∞): We focus strictly on the rounds before the threshold (t<τt<τ). Define the truncated step-wise increments δt:=minℐt+1,D(1/2)−ℐt≥0 _t:= \I_t+1,D(1/2)\-I_t≥ 0. By our premise, δt≤ℐt+1−ℐt≤λrt _t _t+1-I_t≤λ r_t. Since rt<1/2r_t<1/2 prior to τ, we can bound the penalty term as rt−q−1≥(1−2−q)rt−qr_t^-q-1≥(1-2^-q)r_t^-q. Because D is increasing and D(rt)≤ℐtD(r_t) _t, we know rt≤D−1(ℐt)r_t≤ D^-1(I_t). We introduce the non-increasing function f(u):=(D−1(u))−q−1f(u):=(D^-1(u))^-q-1 to smoothly lower bound the discrete sum via a left-endpoint Riemann integral: ∑t<τrt−q _t<τr_t^-q ≥1λ∑t<τrt−q−1δt ≥ 1λ _t<τr_t^-q-1 _t (since λrt≥δtλ r_t≥ _t) ≥1λ∑t<τf(ℐt)δt ≥ 1λ _t<τf(I_t) _t (applying rt≤D−1(ℐt)r_t≤ D^-1(I_t)) ≥1λ∫0D(1/2)f(u)u. ≥ 1λ _0^D(1/2)f(u)\,du. (left-endpoint upper-sum inequality) We evaluate this integral using the change of variables u=D(s)u=D(s), which gives du=D′(s)dsdu=D (s)ds: ∫0D(1/2)f(u)u _0^D(1/2)f(u)\,du =∫1/k1/2s−q−1D′(s)s = _1/k^1/2s^-q-1D (s)\,ds ≥∫2/k4/ks−q−1log(sk2)s ≥ _2/k^4/ks^-q-1 ( sk2 )\,ds (since D′(s)≥log(sk/2)D (s)≥ (sk/2) for k≥8k≥ 8) =kq2q∫12u−q−1logudu≥Cqkq. = k^q2^q _1^2u^-q-1 u\,du≥ C_qk^q. (substituting u=sk/2u=sk/2) Applying the strictly positive integral constant CqC_q yields ∑t<τ(rt−q−1)≥cqkq/λ _t<τ(r_t^-q-1)≥ c_qk^q/λ. Decreasing cqc_q if necessary to satisfy both cases simultaneously completes the proof. ∎ Proof of Theorem˜4.1. Fix an arbitrary algorithm A. We instantiate the k underlying instances with μ:=σkq/Tμ:=σ k^q/T, which sets the KL-divergence multiplier to λ=μ2/(2σ2)=kq/(2T)λ=μ^2/(2σ^2)=k^q/(2T). Notice that replacing any st<1/ks_t<1/k with rt=1/kr_t=1/k strictly decreases the inverse-power mean. As such, we apply Lemma˜4.5, Lemma˜4.4, and Lemma˜4.6 to the unconditional success probabilities, and get 1T∑t=1Tst−q≥1+cqTminT,kqλ=1+cqmin1,2=1+cq. 1T _t=1^Ts_t^-q≥ 1+ c_qT \T, k^qλ \=1+c_q \1,2\=1+c_q. By Lemma˜4.3, there exists at least one specific instance j∈[k]j∈[k] whose time-averaged penalty j:=1T∑t=1Taj,t−qA_j:= 1T _t=1^Ta_j,t^-q satisfies j≥1+cqA_j≥ 1+c_q. Under this specific instance ν(j)ν^(j), the optimal arm is j with mean μ⋆=μ _ =μ, and the expected reward of the algorithm at round t is exactly mt(j)=μaj,tm_t^(j)=μ a_j,t. If j=+∞A_j=+∞, the (−q)(-q)-mean welfare is strictly zero and the regret is trivially μ. Otherwise, we compute the algorithm’s expected regret directly from the definition of the (−q)(-q)-mean: RT,−q(,ν(j)) R_T,-q( A,ν^(j)) =μ−q(m1(j),…,mT(j)) =μ- M_-q(m_1^(j),…,m_T^(j)) =μ−μ(1T∑t=1Taj,t−q)−1/q =μ-μ ( 1T _t=1^Ta_j,t^-q )^-1/q (factoring out μ) =μ(1−j−1/q) =μ (1-A_j^-1/q ) ≥μ(1−(1+cq)−1/q). ≥μ (1-(1+c_q)^-1/q ). (since j≥1+cqA_j≥ 1+c_q) Defining the strictly positive constant cq′:=1−(1+cq)−1/qc_q :=1-(1+c_q)^-1/q, the regret is bounded by cq′μ=cq′σkq/Tc_q μ=c_q σ k^q/T. Because A was chosen arbitrarily, taking the infimum over all algorithms completes the proof. ∎ Proof of Theorem˜1.1. Let q=|p|q=|p|. Proposition˜4.2 bounds the regret by Ω(k/T) ( k/T) while Theorem˜4.1 bounds it by Ω(kq/T) ( k^q/T). Taking the maximum of these two lower bounds and absorbing the respective constants establishes the result across all regimes. ∎ 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 sts_t. Achieving a larger value of sts_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 sts_t. Any objective that penalizes small values of sts_t must therefore incur a cumulative cost before sts_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 ϕφ and an upper bound λψ(st)λψ(s_t) on the one-step information gain. Lemma 4.7 (Information-Cost Inequality). Fix a baseline s0∈(0,1)s_0∈(0,1) and a target level s⋆∈(s0,1]s ∈(s_0,1]. Let (st)t=1T(s_t)_t=1^T be a sequence in [s0,1][s_0,1], and let (ℐt)t=1T+1(I_t)_t=1^T+1 be a nondecreasing sequence with ℐ1=0I_1=0. Let • c:[s0,1]→ℝ≥0c:[s_0,1] _≥ 0 be nonincreasing; • ϕ:[s0,1]→ℝ≥0φ:[s_0,1] _≥ 0 be absolutely continuous and strictly increasing, with ϕ(s0)=0φ(s_0)=0; • ψ:[s0,1]→ℝ>0ψ:[s_0,1] _>0 be nondecreasing. Suppose that, for some λ>0λ>0, the following two inequalities hold for every t∈[T]t∈[T]: ϕ(st)≤ℐt,ℐt+1−ℐt≤λψ(st).φ(s_t) _t, _t+1-I_t≤λ\,ψ(s_t). Then ∑t=1Tc(st)≥minc(s⋆)T,1λ∫s0s⋆c(s)ϕ′(s)ψ(s)s. _t=1^Tc(s_t)\ ≥\ \c(s )T,\, 1λ _s_0^s c(s)φ (s)ψ(s)\,ds \. Proof. Let ℐ¯:=ϕ(s⋆) I:=φ(s ), and define τ:=inft∈1,…,T+1:ℐt≥ℐ¯,τ:= \t∈\1,…,T+1\:I_t≥ I\, with the convention that τ=+∞τ=+∞ if the set is empty. First suppose that τ=+∞τ=+∞. Then for every t∈[T]t∈[T], ϕ(st)≤ℐt<ϕ(s⋆)φ(s_t) _t<φ(s ). Since ϕφ is strictly increasing, this implies st<s⋆s_t<s . As c is non-increasing, c(st)≥c(s⋆)c(s_t)≥ c(s ) for all t, and hence ∑t=1Tc(st)≥c(s⋆)T. _t=1^Tc(s_t)≥ c(s )T. It remains to consider the case τ<+∞τ<+∞. For every t<τt<τ, we have ℐt<ℐ¯I_t< I, and therefore st<s⋆s_t<s . Define the truncated increment δt:=minℐt+1,ℐ¯−ℐt,t=1,…,τ−1. _t:= \I_t+1, I\-I_t, t=1,…,τ-1. Then δt≥0 _t≥ 0, and δt≤ℐt+1−ℐt≤λψ(st) _t _t+1-I_t≤λψ(s_t). Since c≥0c≥ 0 and ψ>0ψ>0, it follows that c(st)≥1λc(st)ψ(st)δt.c(s_t)≥ 1λ\, c(s_t)ψ(s_t)\, _t. Set g(s):=c(s)ψ(s)g(s):= c(s)ψ(s). Because c is nonincreasing and nonnegative, while ψ is positive and nondecreasing, we have g is nonincreasing. The inequality ϕ(st)≤ℐtφ(s_t) _t, together with the monotonicity of ϕφ, implies st≤ϕ−1(ℐt).s_t≤φ^-1(I_t). Thus g(st)≥g(ϕ−1(ℐt))g(s_t)≥ g(φ^-1(I_t)). Define f(u):=g(ϕ−1(u)),u∈[0,ℐ¯].f(u):=g(φ^-1(u)), u∈[0, I]. The function f is nonincreasing. Hence, for each t<τt<τ, c(st)≥1λf(ℐt)δtc(s_t)≥ 1λf(I_t) _t. The intervals [ℐt,ℐt+δt][I_t,I_t+ _t], t=1,…,τ−1t=1,…,τ-1, form a partition of [0,ℐ¯][0, I], up to endpoints of measure zero: they start at ℐ1=0I_1=0, each interval ends at the next information level unless the threshold ℐ¯ I is reached, and the final interval is truncated exactly at ℐ¯ I. Since f is nonincreasing, f(ℐt)δt≥∫ℐtℐt+δtf(u)u.f(I_t) _t≥ _I_t^I_t+ _tf(u)\,du. Summing over t<τt<τ, we obtain ∑t<τc(st)≥1λ∑t<τf(ℐt)δt≥1λ∫0ℐ¯f(u)u. _t<τc(s_t)≥ 1λ _t<τf(I_t) _t≥ 1λ _0 If(u)\,du. Substituting u=ϕ(s)u=φ(s) gives ∫0ℐ¯f(u)u=∫s0s⋆c(s)ψ(s)ϕ′(s)s. _0 If(u)\,du= _s_0^s c(s)ψ(s)φ (s)\,ds. Therefore ∑t=1Tc(st)≥∑t<τc(st)≥1λ∫s0s⋆c(s)ϕ′(s)ψ(s)s. _t=1^Tc(s_t)≥ _t<τc(s_t)≥ 1λ _s_0^s c(s)φ (s)ψ(s)\,ds. Combining the two cases proves the claimed lower bound. ∎ Corollary 4.8 (Negative-power instantiation; cf. Lemma 4.6). Fix q>0q>0, k≥8k≥ 8, and λ>0λ>0. Let (st)t=1T(s_t)_t=1^T be a sequence in [0,1][0,1], and rt:=maxst,1/kr_t:= \s_t,1/k\. Suppose that a nondecreasing sequence (ℐt)t=1T+1(I_t)_t=1^T+1, with ℐ1=0I_1=0, satisfies dk(rt)≤ℐt,ℐt+1−ℐt≤λrtfor all t∈[T],d_k(r_t) _t, _t+1-I_t≤λ r_t all t∈[T], where dk(s):=kl(s∥ 1/k)d_k(s):=kl(s\,\|\,1/k). Then there exists a constant cq>0c_q>0, depending only on q, such that ∑t=1T(rt−q−1)≥cqminT,kqλ. _t=1^T (r_t^-q-1 )\ ≥\ c_q \T, k^qλ \. Proof. Apply Lemma 4.7 to the sequence (rt)t=1T(r_t)_t=1^T with s0=1k,s⋆=12,c(s)=s−q−1,ϕ(s)=dk(s),ψ(s)=s.s_0= 1k, s = 12, c(s)=s^-q-1, φ(s)=d_k(s), ψ(s)=s. The two assumed inequalities are precisely the two hypotheses of Lemma 4.7. The function c is nonincreasing and nonnegative on (0,1](0,1], the function dkd_k is strictly increasing on [1/k,1][1/k,1], and dk(1/k)=0d_k(1/k)=0. It remains to lower-bound the integral term. A direct computation gives dk′(s)=log(s(k−1)1−s).d_k (s)= ( s(k-1)1-s ). For s∈[2/k,4/k]s∈[2/k,4/k] and k≥8k≥ 8, we have dk′(s)≥log(sk2)d_k (s)≥ ( sk2 ). Moreover, since s≤1/2s≤ 1/2 on the interval of integration, we have c(s)=s−q−1≥(1−2−q)s−q.c(s)=s^-q-1≥(1-2^-q)s^-q. Restricting the nonnegative integrand to the subinterval [2/k,4/k][2/k,4/k], we obtain 1λ∫1/k1/2c(s)dk′(s)ss 1λ _1/k^1/2 c(s)d_k (s)s\,ds ≥1−2−qλ∫2/k4/ks−q−1log(sk2)s ≥ 1-2^-qλ _2/k^4/ks^-q-1 ( sk2 )\,ds =1−2−qλ(k2)q∫12u−q−1logudu, = 1-2^-qλ ( k2 )^q _1^2u^-q-1 u\,du, where the last equality uses the substitution u=sk/2u=sk/2. The integral Iq:=∫12u−q−1loguduI_q:= _1^2u^-q-1 u\,du is a positive constant depending only on q. Thus, the integral term is at least cq′kq/λc_q k^q/λ, where cq′:=(1−2−q)2−qIq>0c_q :=(1-2^-q)2^-qI_q>0. The other term in Lemma 4.7 is c(s⋆)T=(2q−1)Tc(s )T=(2^q-1)T. Therefore ∑t=1T(rt−q−1)≥min(2q−1)T,cq′kqλ≥cqminT,kqλ, _t=1^T (r_t^-q-1 )≥ \(2^q-1)T, c_q k^qλ \≥ c_q \T, k^qλ \, where cq:=min2q−1,cq′c_q:= \2^q-1,c_q \. ∎ Remark (Interpreting the information-cost inequality). Lemma 4.7 separates the lower-bound argument into a small number of model-dependent components. The function c describes how the objective penalizes a given success level. The function ϕφ describes how much information is needed to sustain that success level. The baseline s0s_0 is the success probability available without information. Finally, the pair (λ,ψ)(λ,ψ) describes the maximum rate at which information can be accumulated in one round. With these components specified, the cumulative cost is controlled by the single integral 1λ∫s0s⋆c(s)ϕ′(s)ψ(s)s 1λ _s_0^s c(s)φ (s)ψ(s)\,ds. In the k-armed hard instance used here, ψ(s)=sψ(s)=s because observations from non-optimal arms have the same distribution under every hypothesis; information about the hidden index is obtained only when the optimal arm is pulled (Lemma 4.5). 5 Algorithm and Upper Bound In this section, we formally present our - UCB-HARE algorithm and establish its theoretical guarantees. Algorithm 1 UCB with Harmonic Anchored Rank Exploration (- UCB-HARE) Input: Number of arms k, time horizon T, Sub-Gaussian proxy σ, Confidence δ. Set L=log(8kT/δ)L= (8kT/δ). 1:Initialize round t←1t← 1; block b←1b← 1; counts Ni←0N_i← 0 and empirical means μ^i←0 μ_i← 0 for all i∈[k]i∈[k]. 2:Define c(n)≜σ2L/nc(n) σ 2L/n for n≥1n≥ 1 (with c(0)=+∞c(0)=+∞). 3:Draw random permutation π of [k][k] and initialize schedule (rb)b≥1(r_b)_b≥ 1. 4:Define B≜maxi∈[k]μ^i−c(Ni)B _i∈[k]\ μ_i-c(N_i)\. 5:% Phase I: Preparation Phase 6:while b≤⌈T/2⌉b≤ T/2 and not (B>0∧miniNi≥32σ2L/B2) (B>0 _iN_i≥ 32σ^2L/B^2 ) do 7: Toss fair coin θb∼(1/2) _b Ber(1/2). 8: for slot h∈(θb,1−θb)h∈( _b,1- _b) do 9: if t>Tt>T then break // Halt if exact horizon reached 10: if h=1h=1 or B≤0B≤ 0 then 11: Pull scheduled arm It=πrbI_t= _r_b. // Scheduled slot or anchorless fallback 12: else 13: Pull active anchor It∈argmaxiμ^i−c(Ni)I_t∈ *arg\,max_i\ μ_i-c(N_i)\. 14: end if 15: Observe reward Rt∼νItR_t _I_t, update NIt,μ^ItN_I_t, μ_I_t, B and increment t←t+1t← t+1. 16: end for 17: b←b+1b← b+1. 18:end while 19:% Phase I: UCB Exploitation Phase 20:while t≤Tt≤ T do 21: Pull arm It∈argmaxiμ^i+c(Ni)I_t∈ *arg\,max_i\ μ_i+c(N_i)\ and observe reward Rt∼νItR_t _I_t. 22: Update NIt←NIt+1N_I_t← N_I_t+1 and μ^It←(NIt−1)μ^ItNIt+RtNIt μ_I_t← (N_I_t-1) μ_I_tN_I_t+ R_tN_I_t. 23: t←t+1t← t+1. 24:end while The following theorem establishes the p-mean regret upper bound of - UCB-HARE. Notice that the leading term replaces the kq+1k^q+1 dependency with the harmonic penalty sum Kq(k)K_q(k), matching the fundamental information-theoretic limits. Theorem 5.1 (Algorithm Upper Bound). Fix q>0q>0 and let p=−qp=-q. On any σ-sub-Gaussian bandit instance with non-negative means, running - UCB-HARE with confidence parameter δ∈(0,1)δ∈(0,1) satisfies: RT,−q(,ν)≤Cq[σHkKq(k)LT+μ⋆HkKq(k)T+μ⋆δ],R_T,-q( A,ν)≤ C_q [σ H_kK_q(k)LT+ _ H_kK_q(k)T+ _ δ ], where L=log(8kT/δ)L= (8kT/δ) and Cq>0C_q>0 depends only on q. Instantiating the confidence parameter as δ=1/Tδ=1/T sets the failure penalty to μ⋆/T _ /T. For a sufficiently large horizon (T≳μ⋆2HkKq(k)/σ2T _ ^2H_kK_q(k)/σ^2), this O(1/T)O(1/T) trailing term is dominated by the leading exploration cost. The asymptotic limits of Kq(k)K_q(k) from Fact˜3.7 then classify the regret into three distinct regimes, closing the complexity gap. Corollary 5.2 (Consequences by Regime). For p=−q<0p=-q<0, setting δ=1/Tδ=1/T and absorbing logarithmic factors into the O~ O notation yields: RT,−q(,ν)≤O~q(σkT+μ⋆kT),0<q<1,O~(σkT+μ⋆kT),q=1,O~q(σkq/2T+μ⋆kqT),q>1.R_T,-q( A,ν)≤ cases O_q (σ kT+ _ kT ),&0<q<1,\\[8.0pt] O (σ kT+ _ kT ),&q=1,\\[8.0pt] O_q (σ k^q/2 T+ _ k^qT ),&q>1. cases For q>1q>1, the leading kq/2k^q/2 factor matches the minimax lower bound of Theorem˜1.1 up to logarithmic terms. Here, we note that the introductory bound presented in Theorem˜1.2 is simply an asymptotic restatement of Theorem˜5.1 that suppresses the transient O(1/T)O(1/T) failure penalty to highlight the dependence on Kq(k)K_q(k). 6 Proof of Upper Bound This section proves Theorem˜5.1. Fix an instance with optimal mean μ⋆ _ . If μ⋆=0 _ =0, then every mean is zero and the regret is zero. Hence assume μ⋆>0 _ >0. We first fix the standard “good event” that bounds the empirical mean estimator μ^i,n μ_i,n for all arms and sample counts. Let L=log(8kT/δ)L= (8kT/δ) and define the confidence radius c(n):=σ2L/nc(n):=σ 2L/n. We define the good event as ℰ:=∀i∈[k],∀n∈[T]:|μ^i,n−μi|≤c(n)=⋂i=1k⋂n=1T|μ^i,n−μi|≤c(n).E:= \∀ i∈[k],\,∀ n∈[T]:| μ_i,n- _i|≤ c(n) \ = _i=1^k _n=1^T \| μ_i,n- _i|≤ c(n) \. Lemma 6.1 (Concentration). The good event holds with probability ℙ(ℰ)≥1−δ/4P(E)≥ 1-δ/4. Proof. By Hoeffding’s inequality and a union bound over the kTkT combinations of arms and sample counts, the probability of the complementary failure event is strictly bounded by: ℙ(ℰc)≤∑i=1k∑n=1T2exp(−nc(n)22σ2)=2kTe−L.P(E^c)≤ _i=1^k _n=1^T2 (- nc(n)^22σ^2 )=2kTe^-L. Substituting L=log(8kT/δ)L= (8kT/δ) yields ℙ(ℰc)≤δ/4P(E^c)≤δ/4, and the result follows. ∎ Throughout this section, define the critical sample threshold as: n⋆:=max(⌈128σ2Lμ⋆2⌉,1).n_ := ( 128 σ^2L _ ^2 ,1 ). Under the good event, we now show that allocating n⋆n_ samples to the optimal arm is sufficient to establish an anchor, and hence, a positive welfare floor. Lemma 6.2 (Establishing the anchor). On the good event ℰE, if the optimal arm has accumulated at least n⋆n_ samples, an anchor exists and any such anchor arm a∈[k]a∈[k] has a true mean μa≥3μ⋆/4 _a≥ 3 _ /4. Proof. Assume current round is t and Ni⋆(t−1)≥n⋆N_i_ (t-1)≥ n_ . Because n⋆≥128σ2L/μ⋆2n_ ≥ 128σ^2L/ _ ^2, we have c(Ni⋆(t−1))≤σ2L128σ2L/μ⋆2=μ⋆8.c(N_i_ (t-1))≤σ 2L128σ^2L/ _ ^2= _ 8. Under ℰE, the empirical mean satisfies μ^i⋆(t−1)≥μ⋆−c(Ni⋆(t−1)) μ_i_ (t-1)≥ _ -c(N_i_ (t-1)). The lower confidence bound therefore yields Li⋆(t−1):=μ^i⋆(t−1)−c(Ni⋆(t−1))≥μ⋆−2c(Ni⋆(t−1))≥μ⋆−μ⋆4=34μ⋆.L_i_ (t-1):= μ_i_ (t-1)-c(N_i_ (t-1))≥ _ -2c(N_i_ (t-1))≥ _ - _ 4= 34 _ . Recall that an anchor exists whenever the global safety threshold satisfies Bt−1:=maxiLi(t−1)>0B_t-1:= _iL_i(t-1)>0. By definition of the maximum, Bt−1≥Li⋆(t−1)≥34μ⋆>0,B_t-1≥ L_i_ (t-1)≥ 34 _ >0, guaranteeing the anchor. For any selected anchor arm a∈argmaxiLi(t−1)a∈ *arg\,max_iL_i(t-1), the good event ℰE implies μa≥μ^a(t−1)−c(Na(t−1))=La(t−1) _a≥ μ_a(t-1)-c(N_a(t-1))=L_a(t-1). We conclude that μa≥La(t−1)=Bt−1≥34μ⋆.∎ _a≥ L_a(t-1)=B_t-1≥ 34 _ . Set S=⌈Hkn⋆⌉S= H_kn_ . We define an expanding exploration frontier aba_b over π that guarantees the sampling threshold n⋆n_ to all arms with ranks r<abr<a_b. Lemma 6.3 (Expanding frontier). For any block b≥1b≥ 1, define the frontier ab:=min(k,⌊b−18S⌋).a_b:= (k, b-18S ). By the start of block b, every arm assigned a rank r≤abr≤ a_b is guaranteed at least n⋆n_ total pulls. Furthermore, for all blocks b≥8kS+1b≥ 8kS+1, the frontier strictly saturates at ab=ka_b=k, guaranteeing that all k arms have achieved this sampling threshold. Proof. Assume ab≥1a_b≥ 1. Consider any arm with rank r≤abr≤ a_b. By Lemma˜3.6, the scheduled pulls accrued by this rank prior to block b satisfy Nrsch(b−1)≥b−1rHk−2≥b−1abHk−2.N_r sch(b-1)≥ b-1rH_k-2≥ b-1a_bH_k-2. Substituting S=⌈Hkn⋆⌉S= H_kn_ into the frontier definition yields ab≤(b−1)/(8S)a_b≤(b-1)/(8S), which rearranges to (b−1)/(abHk)≥8n⋆(b-1)/(a_bH_k)≥ 8n_ . Because total pulls dominate scheduled pulls, the samples accumulated up to any round t in block b satisfy N(t)≥Nrsch(b−1)≥8n⋆−2≥n⋆.N(t)≥ N_r sch(b-1)≥ 8n_ -2≥ n_ . For the saturation guarantee, consider any block b≥8kS+1b≥ 8kS+1. Substituting the lower bound b−1≥8kSb-1≥ 8kS into the definition of aba_b yields ab≥min(k,⌊8kS8S⌋)=k.a_b≥ (k, 8kS8S )=k. Since ab≤ka_b≤ k by definition, this enforces ab=ka_b=k, ensuring the sampling guarantee applies to all k arms. ∎ Together, Lemma˜6.2 and Lemma˜6.3 govern the discovery of the anchor: it is established early if R⋆≤abR_ ≤ a_b, and guaranteed in any case by block 8kS+18kS+1, under ℰE. We now use this to lower bound the expected reward mtm_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: Bt>0andmini∈[k]Ni(t)≥32σ2LBt2.B_t>0 _i∈[k]N_i(t)≥ 32σ^2LB_t^2. Let τ∈2,4,6,…τ∈\2,4,6,…\ denote this random stopping time in rounds. We now prove that this empirical threshold guarantees strict safety for Phase I. Lemma 6.4 (Phase I safety). On the good event ℰE, if Phase I terminates at even round τ, the following hold: 1. Bτ≥2μ⋆/3B_τ≥ 2 _ /3. 2. For all i∈[k]i∈[k], Ni(τ)≥32σ2L/μ⋆2N_i(τ)≥ 32σ^2L/ _ ^2. 3. In every Phase I round t>τt>τ, the UCB-selected arm satisfies μi≥μ⋆/2 _i≥ _ /2. Proof. Let τ denote the stopping round. On ℰE, the stopping condition Ni⋆(τ)≥32σ2L/Bτ2N_i_ (τ)≥ 32σ^2L/B_τ^2 bounds the optimal arm’s confidence radius: c(Ni⋆(τ))≤σ2L32σ2L/Bτ2=Bτ4.c(N_i_ (τ))≤σ 2L32σ^2L/B_τ^2= B_τ4. Under ℰE, the empirical mean satisfies μ^i⋆(τ)≥μ⋆−c(Ni⋆(τ)) μ_i_ (τ)≥ _ -c(N_i_ (τ)). The global safety threshold Bτ:=maxjLj(τ)B_τ:= _jL_j(τ) therefore satisfies: Bτ≥Li⋆(τ)=μ^i⋆(τ)−c(Ni⋆(τ))≥μ⋆−2c(Ni⋆(τ))≥μ⋆−Bτ2.B_τ≥ L_i_ (τ)= μ_i_ (τ)-c(N_i_ (τ))≥ _ -2c(N_i_ (τ))≥ _ - B_τ2. Rearranging yields 32Bτ≥μ⋆ 32B_τ≥ _ , establishing (1). Because no lower confidence bound can exceed its true mean on ℰE, we have Bτ≤μ⋆B_τ≤ _ . The stopping condition thus enforces a universal minimum sample count for all i∈[k]i∈[k]: Ni(τ)≥32σ2LBτ2≥32σ2Lμ⋆2,N_i(τ)≥ 32σ^2LB_τ^2≥ 32σ^2L _ ^2, establishing (2). Consequently, the confidence radius for every arm i (sampled NiN_i times) throughout Phase I is bounded as c(Ni)≤μ⋆/4c(N_i)≤ _ /4. For (3), let i be the arm selected by the UCB index in any Phase I round t>τt>τ. On ℰE, its index dominates that of the optimal arm: μ^i(t−1)+c(Ni(t−1))≥μ^i⋆(t−1)+c(Ni⋆(t−1))≥μ⋆. μ_i(t-1)+c(N_i(t-1))≥ μ_i_ (t-1)+c(N_i_ (t-1))≥ _ . Applying the lower confidence bound μi≥μ^i(t−1)−c(Ni(t−1)) _i≥ μ_i(t-1)-c(N_i(t-1)) yields μ⋆−μi≤ 2c(Ni(t−1)). _ - _i\;≤\;2\,c(N_i(t-1)). (6.5) Since c(Ni(t−1))≤μ⋆/4c(N_i(t-1))≤ _ /4 by (2), (6.5) gives μi≥μ⋆−2(μ⋆4)=μ⋆2.∎ _i\;≥\; _ -2 ( _ 4 )\;=\; _ 2. Lemma 6.5 (Ex-ante reward lower bound). There exists a universal constant c0>0c_0>0 such that for every round t≤Tt≤ T, with b:=⌈t/2⌉b:= t/2 , mt:=[μIt]≥c0μ⋆max(1k,abk).m_t:=E[ _I_t]≥ c_0 _ ( 1k, a_bk ). Proof. Let R⋆∈[k]R_ ∈[k] denote the rank of the optimal arm under the initial permutation π. We fix the following probability space: for each arm i∈[k]i∈[k], draw an i.i.d. sequence of rewards Xi,1,Xi,2,…X_i,1,X_i,2,… from νi _i in advance, so that the n-th time arm i is pulled, the algorithm simply reveals Xi,nX_i,n. Note that these reward sequences, the permutation π, and the block coins (θb)b≥1( _b)_b≥ 1 are all drawn independently of one another. Three consequences follow immediately, and are all we need: • Since every empirical mean μ^i,n μ_i,n, and hence the good event ℰE, depends only on the reward sequences, ℰE is independent of π and of every θb _b. • Since R⋆R_ depends only on π, any event defined through R⋆R_ (in particular R⋆=rb\R_ =r_b\ and R⋆≤ab\R_ ≤ a_b\, used below) is independent of the rewards and of every θb _b. • Combining the two, ℰE and any event defined through R⋆R_ are independent of each other, since the first depends only on rewards and the second only on π. Let τ denote the stopping round at which the algorithm transitions from Phase I to Phase I, and let ℋ2b−2H_2b-2 denote the history generated by π, the rewards revealed up to round 2b−22b-2, and θ1,…,θb−1 _1,…, _b-1. Because Phase I termination (2.4) is evaluated exclusively at block boundaries, the indicator t≤τ\t≤τ\ is ℋ2b−2H_2b-2-measurable, and since θb _b is independent of everything ℋ2b−2H_2b-2 depends on, it is independent of t≤τ\t≤τ\ too. The independence of θb _b from ℰE and from R⋆=rb\R_ =r_b\ was already noted above and does not rely on ℋ2b−2H_2b-2 at all, since both events can depend on rewards beyond round 2b−22b-2. At the onset of each Phase I block, the coin θb∼(1/2) _b Ber(1/2) determines the order of the slots. Since θb _b is independent of ℰE, R⋆=rb\R_ =r_b\, R⋆≤ab\R_ ≤ a_b\, and t≤τ\t≤τ\, the marginal probability that any Phase I round t∈2b−1,2bt∈\2b-1,2b\ acts as the scheduled slot is exactly 1/21/2 ; and remains 1/21/2 even after conditioning on any of these events, or their intersections. The same holds for the auxiliary slot. During Phase I (t≤τt≤τ), the algorithm’s action at round t falls into one of three disjoint cases: 1. Round t is the scheduled slot. The algorithm deterministically pulls πrb _r_b. 2. Round t is the auxiliary slot and Bt−1>0B_t-1>0. The algorithm pulls an anchor arm. 3. Round t is the auxiliary slot and Bt−1≤0B_t-1≤ 0. The algorithm defaults to pulling arm πrb _r_b. We lower-bound the expected reward mtm_t by evaluating the algorithm under two sub-events of ℰE. Assuming δ≤1δ≤ 1, we have ℙ(ℰ)≥1−δ/4≥3/4P(E)≥ 1-δ/4≥ 3/4. We define the events AtA_t and FtF_t as follows: At:=ℰ∩R⋆=rbandFt:=ℰ∩R⋆≤ab.A_t:=E∩\R_ =r_b\ F_t:=E∩\R_ ≤ a_b\. Note that we define b:=⌈t/2⌉b:= t/2 globally. This and the infinitude of our harmonic schedule preserves the event definitions across both phases, despite the algorithm abandoning the block structure in Phase I. By the independence noted above, their probabilities satisfy: ℙ(At) (A_t) =ℙ(ℰ)ℙ(R⋆=rb)≥(34)1k=34k, =P(E)P(R_ =r_b)≥ ( 34 ) 1k= 34k, ℙ(Ft) (F_t) =ℙ(ℰ)ℙ(R⋆≤ab)≥(34)abk=3ab4k. =P(E)P(R_ ≤ a_b)≥ ( 34 ) a_bk= 3a_b4k. Since At,Ft⊆ℰA_t,F_t , Phase I’s safety guarantee (Lemma˜6.4), which relies exclusively on ℰE, applies unchanged. Thus, for the UCB regime (t>τt>τ), both [μIt∣At,t>τ]E[ _I_t A_t,t>τ] and [μIt∣Ft,t>τ]E[ _I_t F_t,t>τ] are lower-bounded by μ⋆/2 _ /2. As μi≥0 _i≥ 0, we bound unfavorable Phase I cases strictly by zero. First, we condition on AtA_t. For t≤τt≤τ (Phase I), we isolate Case 1. With probability 1/21/2, round t∈2b−1,2bt∈\2b-1,2b\ acts as the scheduled slot, forcing It=i⋆I_t=i_ under AtA_t. Bounding Cases 2 and 3 by zero yields: [μIt∣At,t≤τ] [ _I_t A_t,t≤τ] ≥ℙ(Case 1)(μ⋆)+ℙ(Cases 2 & 3)(0) (Case 1)( _ )+P(Cases 2 \& 3)(0) =12(μ⋆)=μ⋆2. = 12( _ )= _ 2. Because the conditional expectation is at least μ⋆/2 _ /2 in both phases, we get [μIt∣At]≥μ⋆/2E[ _I_t A_t]≥ _ /2 irrespective of the stopping time τ. Removing the conditioning provides the first bound: mt≥[μIt∣At]ℙ(At)≥μ⋆2(34k)=3μ⋆8k.m_t [ _I_t A_t]P(A_t)≥ _ 2 ( 34k )= 3 _ 8k. Next, we condition on FtF_t. For t≤τt≤τ, we isolate Case 2. Under FtF_t, the constraint R⋆≤abR_ ≤ a_b guarantees the optimal arm has received n⋆n_ samples prior to block b (Lemma˜6.3). Under ℰE, this triggers the anchor Bt≥3μ⋆/4B_t≥ 3 _ /4 (Lemma˜6.2) and strictly eliminates Case 3. With probability 1/21/2, round t∈2b−1,2bt∈\2b-1,2b\ acts as the Auxiliary Slot (Case 2) and pulls the anchor. Bounding Case 1 by zero yields: [μIt∣Ft,t≤τ] [ _I_t F_t,t≤τ] ≥ℙ(Case 1)(0)+ℙ(Case 2)(3μ⋆4) (Case 1)(0)+P(Case 2) ( 3 _ 4 ) =12(3μ⋆4)=3μ⋆8. = 12 ( 3 _ 4 )= 3 _ 8. Again, since Phase I guarantees μ⋆/2≥3μ⋆/8 _ /2≥ 3 _ /8, this lower bound holds irrespective of the stopping time τ, yielding [μIt∣Ft]≥3μ⋆/8E[ _I_t F_t]≥ 3 _ /8. Removing the conditioning provides the second bound: mt≥[μIt∣Ft]ℙ(Ft)≥3μ⋆8(3ab4k)=9abμ⋆32k.m_t [ _I_t F_t]P(F_t)≥ 3 _ 8 ( 3a_b4k )= 9a_b _ 32k. Combining the two bounds, the ex-ante reward satisfies: mt≥max(12μ⋆32k,9abμ⋆32k)≥932μ⋆max(1k,abk).m_t≥ ( 12 _ 32k, 9a_b _ 32k )≥ 932 _ ( 1k, a_bk ). Setting c0=1/4≤9/32c_0=1/4≤ 9/32 completes the proof. ∎ We now bound the maximum duration of Phase I and then derive a cap on its penalty. Lemma 6.6 (Deterministic preparation window). On the good event ℰE, the random stopping time τ of Phase I is bounded as τ≤T0:=18kS,τ≤ T_0:=18kS, where S:=⌈Hkn⋆⌉S:= H_kn_ . Proof. By Lemma˜6.3, at the end of block b0:=8kS+1b_0:=8kS+1 (corresponding to round 2b02b_0), the harmonic schedule guarantees at least n⋆n_ total pulls to every arm i∈[k]i∈[k]. Consequently, the optimal arm satisfies Ni⋆(2b0)≥n⋆N_i_ (2b_0)≥ n_ . On event ℰE, Lemma˜6.2 thus ensures B2b0≥3μ⋆/4>0B_2b_0≥ 3 _ /4>0. As n⋆:=⌈128σ2L/μ⋆2⌉n_ := 128σ^2L/ _ ^2 , we therefore have 32σ2LB2b02≤32σ2L(3μ⋆/4)2=5129σ2Lμ⋆2≤n⋆. 32σ^2LB_2b_0^2≤ 32σ^2L(3 _ /4)^2= 5129 σ^2L _ ^2≤ n_ . Since n⋆≤Ni(2b0)n_ ≤ N_i(2b_0) for all i∈[k]i∈[k], the stopping condition (2.4) holds. Because 2b02b_0 is an even round, the algorithm explicitly evaluates the condition here, forcing Phase I to end at τ where τ≤2b0=16kS+2≤18kS=:T0,τ≤ 2b_0=16kS+2≤ 18kS=:T_0, and the final inequality holds since k,S≥1k,S≥ 1. ∎ Lemma 6.7 (Preparation inverse penalty). There exists a constant Cq>0C_q>0 such that the total inverse penalty up to the deterministic horizon T0T_0 is bounded as ∑t=1T∧T0[(μ∗mt)q−1]<CqSKq(k), _t=1^T T_0 [ ( _*m_t )^q-1 ]<C_qSK_q(k), where Cq:=34⋅4qC_q:=34· 4^q, S:=⌈Hkn⋆⌉S:= H_kn_ , and Kq(k):=∑r=1k(kr)qK_q(k):= _r=1^k ( kr )^q. Proof. By Lemma˜6.6, Phase I ends by round T0=18kST_0=18kS. Since each block spans two rounds, the timeline t≤T∧T0t≤ T T_0 covers at most 9kS9kS blocks. Converting the round-wise summation to a block-wise summation, we get ∑t=1T∧T0[(μ∗mt)q−1]≤2∑b=19kS[(μ∗mt)q−1]<2∑b=19kS(μ∗mt)q, _t=1^T T_0 [ ( _*m_t )^q-1 ]≤ 2 _b=1^9kS [ ( _*m_t )^q-1 ]<2 _b=1^9kS ( _*m_t )^q, where we relax the −1-1 term-wise in the final inequality. This switch is allowed, since by Lemma˜6.5, the ex-ante reward satisfies mt≥14μ∗max(1/k,ab/k)m_t≥ 14 _* (1/k,a_b/k) for any round t in block b, where ab=min(k,⌊b−18S⌋)a_b= (k, b-18S ). This implies: (μ∗mt)q≤4qmax(1k,abk)−q. ( _*m_t )^q≤ 4^q ( 1k, a_bk )^-q. For b∈[1,8S]b∈[1,8S], we have ab=0a_b=0, giving max(1/k,0)=1/k (1/k,0)=1/k. There are 8S8S such blocks. For each r∈1,2,…,k−1r∈\1,2,…,k-1\, we have ab=ra_b=r over the 8S8S blocks in the interval b∈[8rS+1,8(r+1)S]b∈[8rS+1,8(r+1)S]. For b∈[8kS+1,9kS]b∈[8kS+1,9kS], the frontier saturates at k. This final interval contains kSkS blocks. Bounding the total penalty over these intervals yields ∑t=1T∧T0[(μ∗mt)q−1] _t=1^T T_0 [ ( _*m_t )^q-1 ] <2∑b=19kS(μ∗mt)q <2 _b=1^9kS ( _*m_t )^q ≤2[∑b=18S(4k)q+∑r=1k−1∑b=8rS+18(r+1)S4q(kr)q+∑b=8kS+19kS4q(k)q] ≤ 2 [ _b=1^8S(4k)^q+ _r=1^k-1 _b=8rS+1^8(r+1)S4^q ( kr )^q+ _b=8kS+1^9kS4^q ( kk )^q ] =2[8S⋅4qkq+8S⋅4q∑r=1k−1(kr)q+kS⋅4q] =2 [8S· 4^qk^q+8S· 4^q _r=1^k-1 ( kr )^q+kS· 4^q ] <2[8S⋅4qKq(k)+8S⋅4qKq(k)+S⋅4qKq(k)] <2 [8S· 4^qK_q(k)+8S· 4^qK_q(k)+S· 4^qK_q(k) ] =34⋅4qSKq(k). =34· 4^qSK_q(k). The last inequality follows because kq,∑r=1k−1(k/r)qk^q, _r=1^k-1(k/r)^q, and k are all upper-bounded by Kq(k)K_q(k). Setting Cq=34⋅4qC_q=34· 4^q concludes the proof. ∎ We now bound the inverse penalty for the remaining duration of the horizon. Lemma 6.8 (Phase I inverse penalty). There exists a constant Cq>0C_q>0 such that ∑t=T0+1T[(μ⋆mt)q−1]≤Cq(σμ⋆kTL+Tδ), _t=T_0+1^T [ ( _ m_t )^q-1 ]≤ C_q ( σ _ kTL+Tδ ), where the sum evaluates to zero if T≤T0T≤ T_0. Proof. If T≤T0T≤ T_0, the summation is empty and the bound holds trivially. Assume T>T0T>T_0. By Lemma˜6.6, the stopping time satisfies τ≤T0τ≤ T_0, ensuring all rounds t>T0t>T_0 execute exclusively in Phase I. The stopping condition (2.4) requires miniNi(τ)≥32σ2L/Bτ2>0 _iN_i(τ)≥ 32σ^2L/B_τ^2>0, and since Ni(τ)N_i(τ) is a nonnegative integer this forces Ni(τ)≥1N_i(τ)≥ 1 for every arm i∈[k]i∈[k]. On event ℰE, Lemma˜6.4 guarantees the UCB index selects an arm It∈argmaxiμ^i(t−1)+c(Ni(t−1))I_t∈ _i\ μ_i(t-1)+c(N_i(t-1))\ satisfying μIt≥μ⋆/2 _I_t≥ _ /2. Ex-ante rewards are non-negative, so the Law of Total Expectation bounds them as mt=[μIt]≥[μIt∣ℰ]ℙ(ℰ)≥μ⋆2ℙ(ℰ).m_t=E[ _I_t] [ _I_t ]P(E)≥ _ 2P(E). By Lemma˜6.1, ℙ(ℰ)≥1−δ/4≥1/2P(E)≥ 1-δ/4≥ 1/2. Thus, mt≥μ⋆/4m_t≥ _ /4. Since mt≤μ⋆m_t≤ _ unconditionally, we have mt∈[μ⋆/4,μ⋆]m_t∈[ _ /4, _ ]. Applying Lemma˜3.3 bounds the inverse penalty by the linear regret: (μ⋆mt)q−1≤Cq′μ⋆−mtμ⋆. ( _ m_t )^q-1≤ C_q _ -m_t _ . By linearity of expectation (μ⋆−mt=[μ⋆−μIt] _ -m_t=E[ _ - _I_t]) and the Law of Total Expectation, we decompose the single-round regret. As the maximum possible regret is bounded by μ⋆ _ : μ⋆−mt _ -m_t =[μ⋆−μIt∣ℰ]ℙ(ℰ)+[μ⋆−μIt∣ℰc]ℙ(ℰc) =E[ _ - _I_t ]P(E)+E[ _ - _I_t ^c]P(E^c) ≤[μ⋆−μIt∣ℰ]+μ⋆ℙ(ℰc). [ _ - _I_t ]+ _ P(E^c). Applying linearity of expectation again, we get ∑t=T0+1T[(μ⋆mt)q−1] _t=T_0+1^T [ ( _ m_t )^q-1 ] ≤Cq′μ⋆∑t=T0+1T([μ⋆−μIt∣ℰ]+μ⋆ℙ(ℰc)) ≤ C_q _ _t=T_0+1^T (E[ _ - _I_t ]+ _ P(E^c) ) ≤Cq′μ⋆[∑t=T0+1T(μ⋆−μIt)|ℰ]+Cq′Tδ, ≤ C_q _ E [ _t=T_0+1^T( _ - _I_t)\; |\;E ]+C_q Tδ, (6.9) where the second term applies the union bound ℙ(ℰc)≤δ/4≤δP(E^c)≤δ/4≤δ and the relaxation T−T0<T-T_0<T. It remains to bound the inner sum on ℰE. By Lemma˜6.6, Phase I stops at τ≤T0τ≤ T_0, so it suffices to bound the larger sum over all rounds t>τt>τ. Fix any such round t; since ItI_t maximizes the UCB index at round t, we have μ⋆−μIt≤ 2c(NIt(t−1)),t>τ _ - _I_t\;≤\;2\,c(N_I_t(t-1)), t>τ (recall (6.5)) on ℰE, regardless of how NIt(t−1)N_I_t(t-1) was accumulated prior to τ. Fix an arm i∈[k]i∈[k] and let ni:=Ni(T)−Ni(τ)≥0n_i:=N_i(T)-N_i(τ)≥ 0 denote its number of pulls after round τ. We track, for each arm i, the sum ∑t>τ:It=ic(Ni(t−1)), _t>τ:\,I_t=ic(N_i(t-1)), which ranges over exactly these nin_i rounds, namely those after τ at which arm i is selected. At its j-th such pull, arm i has already accumulated at least Ni(τ)+(j−1)≥jN_i(τ)+(j-1)≥ j samples (using Ni(τ)≥1N_i(τ)≥ 1). Therefore, as c(⋅)c(·) is decreasing, ∑t>τ:It=ic(Ni(t−1))≤∑j=1nic(j)=σ2L∑j=1ni1j≤ 2σ2Lni. _t>τ:\,I_t=ic(N_i(t-1))\;≤\; _j=1^n_ic(j)\;=\;σ 2L _j=1^n_i 1 j\;≤\;2σ 2L\, n_i. For the last step, since x↦x−1/2x x^-1/2 is decreasing, j−1/2≤∫j−1jx−1/2xj^-1/2≤ _j-1^jx^-1/2\,dx for every j≥2j≥ 2. Summing from j=2j=2 to nin_i and adding back the j=1j=1 term, ∑j=1ni1j≤ 1+∫1nix−1/2x= 2ni−1≤ 2ni, _j=1^n_i 1 j\;≤\;1+ _1^n_ix^-1/2\,dx\;=\;2 n_i-1\;≤\;2 n_i, which also holds trivially when ni=0n_i=0. Summing over arms and applying Cauchy-Schwarz, ∑t=τ+1T(μ⋆−μIt)≤ 2∑i=1k∑t>τ:It=ic(Ni(t−1))≤ 4σ2L∑i=1kni≤ 4σ2Lk∑ini= 4σ2Lk(T−τ). _t=τ+1^T( _ - _I_t)\;≤\;2 _i=1^k _t>τ:\,I_t=ic(N_i(t-1))\;≤\;4σ 2L _i=1^k n_i\;≤\;4σ 2L\, k _in_i\;=\;4σ 2L\, k(T-τ). Since 0≤τ≤T00≤τ≤ T_0 and every term μ⋆−μIt _ - _I_t is non-negative, this becomes ∑t=T0+1T(μ⋆−μIt)≤∑t=τ+1T(μ⋆−μIt)≤ 4σ2Lk(T−τ)≤ 4σ2LkT. _t=T_0+1^T( _ - _I_t)\;≤\; _t=τ+1^T( _ - _I_t)\;≤\;4σ 2L\, k(T-τ)\;≤\;4σ 2L\, kT. This holds on all of ℰE, so taking conditional expectation given ℰE yields [∑t=T0+1T(μ⋆−μIt)|ℰ]≤ 4σ2LkT,E [ _t=T_0+1^T( _ - _I_t)\; |\;E ]\;≤\;4σ 2L\, kT, and substituting into (6.9) gives ∑t=T0+1T[(μ⋆mt)q−1]≤ 42Cq′σμ⋆kTL+Cq′Tδ. _t=T_0+1^T [ ( _ m_t )^q-1 ]\;≤\;4 2\,C_q σ _ kTL+C_q Tδ. Absorbing the scalar combinations into CqC_q concludes the proof. ∎ Proof of Theorem˜5.1. Recall that Lemma˜3.2 bounds the (−q)(-q)-mean regret by the inverse penalty. Splitting the summation at the fixed round T0T_0 yields: RT,−q≤μ⋆qT(∑t=1T∧T0[(μ⋆mt)q−1]+∑t=T0+1T[(μ⋆mt)q−1]).R_T,-q≤ _ qT ( _t=1^T T_0 [ ( _ m_t )^q-1 ]+ _t=T_0+1^T [ ( _ m_t )^q-1 ] ). Substituting the bounds from Lemma˜6.7 and Lemma˜6.8, and recalling S=Hkn⋆S=H_kn_ , leads to RT,−q R_T,-q ≤μ⋆qT[CqHkn⋆Kq(k)+Cq(σμ⋆kTL+Tδ)] ≤ _ qT [C_qH_kn_ K_q(k)+C_q ( σ _ kTL+Tδ ) ] ≤Cq′T[HkKq(k)(μ⋆n⋆)+σkTL+μ⋆Tδ]. ≤ C_q T [H_kK_q(k)( _ n_ )+σ kTL+ _ Tδ ]. By definition, the anchor threshold is n⋆=max(⌈128σ2L/μ⋆2⌉,1)≤128σ2L/μ⋆2+2n_ = ( 128σ^2L/ _ ^2 ,1)≤ 128σ^2L/ _ ^2+2, which gives μ⋆n⋆≤128σ2Lμ⋆+2μ⋆. _ n_ ≤ 128σ^2L _ +2 _ . The regret is thus bounded as RT,−q≤Cq′[HkKq(k)Tσ2Lμ⋆+μ⋆HkKq(k)T+σkLT+μ⋆δ].R_T,-q≤ C_q [ H_kK_q(k)T σ^2L _ + _ H_kK_q(k)T+σ kLT+ _ δ ]. (6.10) We bound (6.10) by evaluating it relative to μ0:=σHkKq(k)LT _0:=σ H_kK_q(k)LT. Case 1 (μ⋆≤μ0 _ ≤ _0): Since μi≥0 _i≥ 0 for all i∈[k]i∈[k], we have mt≥0m_t≥ 0. The (−q)(-q)-mean regret therefore satisfies RT,−q≤μ⋆≤μ0R_T,-q≤ _ ≤ _0. Case 2 (μ⋆>μ0 _ > _0): By definition of μ0 _0, the leading term in (6.10) is bounded as HkKq(k)Tσ2Lμ⋆=μ02μ⋆<μ0. H_kK_q(k)T σ^2L _ = _0^2 _ < _0. Moreover, as Hk≥1H_k≥ 1 and Kq(k)≥kK_q(k)≥ k, we eventually have σkL/T≤μ0σ kL/T≤ _0. Combining both cases, the regret uniformly satisfies RT,−q≤C[μ0+μ⋆HkKq(k)T+μ⋆δ].R_T,-q≤ C [ _0+ _ H_kK_q(k)T+ _ δ ]. Substituting μ0 _0 concludes the proof: RT,−q≤C[σHkKq(k)LT+μ⋆HkKq(k)T+μ⋆δ].R_T,-q≤ C [σ H_kK_q(k)LT+ _ H_kK_q(k)T+ _ δ ]. ∎ Proof of Corollary˜5.2. From Fact˜3.7, we get Kq(k)=Θq(k),0<q<1,Θ(klogk),q=1,Θq(kq),q>1.K_q(k)= cases _q(k),&0<q<1,\\ (k k),&q=1,\\ _q(k^q),&q>1. cases Substituting these evaluations into the O(σHkKq(k)LT)O (σ H_kK_q(k)LT ) leading term of Theorem˜5.1, and noting that the schedule penalty contributes Hk=Θ(logk)H_k= ( k), produces the required bounds. Absorbing logarithmic terms into the O~ O notation yields the three distinct regret regimes, concluding the proof. ∎ 7 Experiments We evaluate - UCB-HARE against Welfarist UCB [21] and Explore-Then-UCB [15] 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=50k=50, mean rewards μi _i drawn i.i.d. uniformly from [10,1000][10,1000], and Gaussian noise variance σ2=400σ^2=400, over a horizon T=106T=10^6, averaging results over 5050 independent runs to estimate [μIt]E[ _I_t]. Experiment A: Regret across algorithms. Figures˜3(a), 3(b) and 3(c) compare regret for p∈−0.5,−2.0,−20p∈\-0.5,-2.0,-20\. - UCB-HARE minimizes regret most rapidly. Welfarist-UCB is delayed by uniform exploration, and Explore-Then-UCB accrues linear regret prior to commitment. - UCB-HARE mitigates both inefficiencies via a real-time lower confidence bound anchor. Experiment B: Regret scales with q=−pq=-p. Figure˜3(d) shows regret across fairness levels p∈−1,−5,−10,−20p∈\-1,-5,-10,-20\, increasing in magnitude as q=−pq=-p grows, consistent with our theoretical rates. - UCB-HARE ’s regret remains stable across this entire range. (a) p=−0.5p=-0.5 (b) p=−2.0p=-2.0 (c) p=−20p=-20 (d) Varying p Figure 3: (a – c) Regret comparison of - UCB-HARE against Welfarist-UCB and Explore-Then-UCB. (d) - UCB-HARE’s regret across p∈−1,−5,−10,−20p∈\-1,-5,-10,-20\. Figure 4: Single-trial ex-ante reward mtm_t on a 200200-arm instance with five elevated-mean arms (μ⋆=1000 _ =1000). - UCB-HARE’s staircase reveals the advantage of successive anchor discoveries - establishing a welfare floor early on; Welfarist-UCB remains at the uniform exploration baseline throughout Phase I before jumping to the optimum. Experiment C: Ex-ante reward vs t. We construct an instance with k=200k=200 arms, five of which have means 200200, 400400, 600600, 800800, 10001000 and the rest with mean 1010, and run a single trial (no averaging across seeds) over T=5000T=5000 rounds at p=−q=−2.0p=-q=-2.0, tracking the ex-ante reward mtm_t. Single-trial outcomes vary with the random permutation drawn by the algorithm; the run shown in Figure˜4 is representative and captures the novelty of our harmonic anchored rank exploration. We highlight the following: 1. Welfare improves stepwise, not in one jump. - UCB-HARE’s roundwise ex-ante reward mtm_t increases in a sequence of steps, each corresponding to a newly certified anchor, before reaching the optimum. This matches the bound mt≥c0μ⋆max(1/k,ab/k)m_t≥ c_0 _ (1/k,a_b/k) of Lemma˜6.5, which increases in step with the expanding frontier aba_b. 2. Uniform exploration is sub-optimal. Welfarist-UCB’s mtm_t sits at the uniform-exploration floor (mt≈25≳μ⋆/km_t≈ 25 _ /k) for the entire duration of Phase I, confirming that this baseline is indeed the source of the k(q+1)/2k^(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 μ=1000μ=1000, a block of near-optimal arms have mean μ=950μ=950, and the remaining arms have mean μ=10μ=10, with arm identities randomly permuted. We compare k=10k=10 against k=100k=100 over horizons up to T=106T=10^6, averaged over 5050 independent trials, at three fairness levels p∈−1.0,−2.0,−5.0p∈\-1.0,-2.0,-5.0\ with σ2=1.0σ^2=1.0 (Figure 5). Figure 5: Regret comparison between - UCB-HARE and Welfarist-UCB at k∈10,100k∈\10,100\, for fairness levels p∈−1.0,−2.0,−5.0p∈\-1.0,-2.0,-5.0\, in Experiment D. The gap between the two algorithms grows with q=−pq=-p. At q=1q=1, - UCB-HARE and Welfarist-UCB stay close at both arm counts, matching the regime q≤1q≤ 1, where both rates scale as k/T k/T. As q rises to 22 and then 55, Welfarist-UCB’s regret tends to flatten at its starting value for both k=10k=10 and 100100, while - UCB-HARE retains its performance better. This matches the gap between k(q+1)/2k^(q+1)/2 and kq/2k^q/2 from Corollary˜5.2: uniform exploration gets more costly as q grows, while - UCB-HARE ’s harmonic schedule avoids this extra cost. Pushing q further, to 1010 and 2020, makes this flattening pronounced for both algorithms (Figure˜6). This reflects the strongly fair regime’s convergence to the Rawlsian maximin ideal: as q→∞q→∞, the (−q)(-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 μ⋆/k _ /k, while - UCB-HARE’s harmonic schedule certifies a positive-mean anchor sooner and sustains improvement over a longer horizon. Figure 6: At large q, regrets of both algorithms flatten toward the Rawlsian worst-round bottleneck, with - UCB-HARE sustaining improvement over a longer horizon. References [1] Y. Abbasi-Yadkori, D. Pál, and C. Szepesvári (2011) Improved algorithms for linear stochastic bandits. Advances in neural information processing systems 24. Cited by: §1.2. [2] N. Anari, S. Oveis Gharan, A. Saberi, and M. Singh (2017) Nash social welfare, matrix permanent, and stable polynomials. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 67, p. 36:1–36:12. External Links: Document Cited by: §1.3. [3] A. B. Atkinson (1970) On the measurement of inequality. Journal of Economic Theory 2 (3), p. 244–263. External Links: Document Cited by: §1.3. [4] S. Barman, U. Bhaskar, A. Krishna, and R. G. Sundaram (2020) Tight approximation algorithms for p-mean welfare under subadditive valuations. In Proceedings of the 28th Annual European Symposium on Algorithms (ESA), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 173, p. 11:1–11:17. External Links: Document Cited by: §1.3. [5] S. Barman, A. Khan, A. Maiti, and A. Sawarni (2023) Fairness and welfare quantification for regret in multi-armed bandits. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI), Vol. 37, p. 6762–6769. Cited by: §1.1, §1. [6] S. Barman, A. Khan, and A. Maiti (2022) Universal and tight online algorithms for generalized-mean welfare. In Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI), Vol. 36, p. 4793–4800. External Links: Document Cited by: §1.3. [7] S. Barman and R. G. Sundaram (2020) Uniform welfare guarantees under identical subadditive valuations. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI), p. 46–52. External Links: Document Cited by: §1.3. [8] S. Bubeck and N. Cesa-Bianchi (2012) Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends® in Machine Learning 5 (1), p. 1–122. Cited by: §1.1, §1.1, §1.2, §1, §2.1, §4. [9] I. Caragiannis, D. Kurokawa, H. Moulin, A. D. Procaccia, N. Shah, and J. Wang (2019) The unreasonable fairness of maximum nash welfare. ACM Transactions on Economics and Computation 7 (3), p. 12:1–12:32. External Links: Document Cited by: §1.3. [10] R. Cole, N. R. Devanur, V. Gkatzelis, K. Jain, T. Mai, V. V. Vazirani, and S. Yazdanbod (2017) Convex program duality, fisher markets, and nash social welfare. In Proceedings of the 2017 ACM Conference on Economics and Computation (EC), p. 459–460. External Links: Document Cited by: §1.3. [11] R. Cole and V. Gkatzelis (2015) Approximating the nash social welfare with indivisible items. In Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC), p. 371–380. External Links: Document Cited by: §1.3. [12] O. Eckart, A. Psomas, and P. Verma (2024) On the fairness of normalized p-means for allocating goods and chores. In Proceedings of the 25th ACM Conference on Economics and Computation (EC), External Links: Document Cited by: §1.3. [13] E. Eisenberg and D. Gale (1959) Consensus of subjective probabilities: the pari-mutuel method. The Annals of Mathematical Statistics 30 (1), p. 165–168. External Links: Document Cited by: §1.3. [14] F. P. Kelly, A. K. Maulloo, and D. K. H. Tan (1998) Rate control for communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society 49 (3), p. 237–252. External Links: Document Cited by: §1.3. [15] A. Krishna, P. G. John, A. Barik, and V. Y. F. Tan (2025) p-mean regret for stochastic bandits. In Proceedings of the 39th AAAI Conference on Artificial Intelligence (AAAI), Vol. 39, p. 17966–17973. Cited by: §1.1, §1, §3.1, §7. [16] T. Lan, D. Kao, M. Chiang, and A. Sabharwal (2010) An axiomatic theory of fairness in network resource allocation. In Proceedings of the 29th IEEE International Conference on Computer Communications (INFOCOM), p. 1343–1351. External Links: Document Cited by: §1.3. [17] J. Mo and J. Walrand (2000) Fair end-to-end window-based congestion control. IEEE/ACM Transactions on Networking 8 (5), p. 556–567. External Links: Document Cited by: §1.3. [18] H. Moulin (2004) Fair division and collective welfare. MIT Press, Cambridge, MA. Cited by: §1.3, §1, §3.1. [19] J. F. Nash (1950) The bargaining problem. Econometrica 18 (2), p. 155–162. External Links: Document Cited by: §1.3. [20] D. Sarkar, N. Pandey, and S. R. Chowdhury (2026) Improved algorithms for nash welfare in linear bandits. External Links: 2601.22969, Link Cited by: §1.2. [21] D. Sarkar, N. Pandey, and S. Ray Chowdhury (2025) Revisiting social welfare in bandits: UCB is (nearly) all you need. arXiv preprint arXiv:2510.21312. Cited by: §1.1, §1.2, §1, §2.2, §7. [22] W. R. Thompson (1933) On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25 (3/4), p. 285–294. Cited by: §1.