Pith. sign in

REVIEW 2 major objections 5 minor 35 references

Price of Fairness in Bandits: A Tight Minimax Characterization

T0 review · 2 major / 5 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that in k-armed bandits where welfare is the negative-power mean of per-round rewards, the minimax regret is Θ~(σ√(k^{max(1,q)}/T)), so for fairness strength q>1 the k^{q/2} penalty is information-theoretically unavoidable

desk verdict Solid lower-bound machinery and a clever schedule, but the claimed minimax rate is undefined over the stated class because means are unbounded. read the letter →

arxiv 2607.13402 v1 pith:GYP5ACYT submitted 2026-07-15 stat.ML cs.AIcs.LG

Dhruv Sarkar , Soumyadeep Dutta , Sayak Ray Chowdhury This is my paper
classification stat.MLcs.AIcs.LG MSC 62C2062L0591B32
keywords multi-armedbanditsgeneralizedp-meanregretnegative-powerwelfarestrictfairnessminimaxlowerboundUCB-HAREharmonicschedulesub-Gaussianrewards
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks how much statistical efficiency a learner must sacrifice to guarantee fair treatment of every round in a multi-armed bandit, when fairness is formalized as a negative-power mean of the per-round expected rewards. The authors prove that the minimax regret over sub-Gaussian bandits with nonnegative means is Θ~(σ√(k^{max(1,q)}/T)), where q>0 is the fairness strength. For q>1, this lifts the classical √(k/T) rate to √(k^q/T), meaning the extra arm-count penalty k^{q/2} is an inherent cost of strict fairness, not a flaw of earlier uniform-exploration algorithms. They also introduce UCB-HARE, a two-phase algorithm whose inverse-weighted harmonic exploration schedule matches this lower bound up to logarithmic factors. A sympathetic reader would care because this settles an open question in the fair-bandit literature and tells practitioners exactly how much fairness costs in regret.

What carries the argument

The argument turns on two constructions. First, the needle-in-haystack instance family (all means zero except one arm with mean μ>0), together with the information-cost inequality (Lemma 4.7) that converts the rate at which an algorithm can raise its probability of pulling the optimal arm into a lower bound on the cumulative inverse-power penalty. Second, the UCB-HARE algorithm, whose exploration phase uses a harmonic rank schedule—pulling arms with frequency proportional to 1/r—and pairs each risky exploration pull with a certified anchor pull, an arm whose lower confidence bound is strictly positive. The schedule's prefix-balance property (Lemma 3.6) guarantees every arm is adequately samp

What would settle it

Simulate the needle-in-haystack family used in the paper for a fixed q>1 (say q=3) across k=10,30,100 with T large, and fit the scaling of the best achievable regret in k: an exponent of (q+1)/2≈2 rather than q/2=1.5 would contradict the claimed minimax lower bound.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that the minimax (−q)-mean regret over the class of σ-sub-Gaussian bandits with nonnegative means is Ω(σ√(k^{max(1,q)}/T)) (Theorem 1.1), and the UCB-HARE algorithm achieves O~(σ√(k^{max(1,q)}/T)) (Theorem 1.2). For 0<q≤1 the classical √(k/T) rate persists; for q>1 the rate becomes √(k^q/T). The lower bound is obtained from a needle-in-haystack family of instances in which only one arm has positive mean, and the proof is distilled into a general information-cost inequality that lower-bounds the cumulative penalty of any fairness-sensitive objective whose welfare is bottlenecked by the rate of identifying the optimal arm. The upper bound repl

Load-bearing premise

The result depends on the assumption that every arm's expected reward is nonnegative and the best arm's mean is strictly positive; if any arm could have a negative mean, the negative-power welfare objective (which is set to zero when any round's expected reward is zero) and the algorithm's anchor-certification safety argument would both break.

Editorial extensions

If this is right

  • For q>1, the classical √(k/T) regret rate is superseded by √(k^q/T); this is the exact minimax rate up to log factors.
  • Algorithms based on uniform early exploration (the prior state of the art) are provably suboptimal in their k-dependence: they incur k^{(q+1)/2}/√T whereas the fundamental limit is k^{q/2}/√T.
  • The price of strict fairness is zero for 0<q≤1 in the minimax scaling: the classical rate is attainable, so fairness up to Nash/geometric strength comes for free in k.
  • The same information-cost inequality applies beyond negative-power means and is in principle adaptable to other bandit models, such as linear bandits, as the authors note.
  • The regret bound is gap-free: it holds uniformly over instances without knowledge of suboptimality gaps, with only the optimal mean and sub-Gaussian parameter entering the bound.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The harmonic schedule's success suggests a design principle the authors leave implicit: any fair-exploration scheme must allocate exploration roughly inversely to rank to raise the optimal arm's selection probability from 1/k without paying the full k^{q} penalty; other inverse-frequency schedules might achieve the same endpoint with smaller constants.
  • The nonnegativity assumption is doing more work than the fairness framing suggests: if arm means are merely lower-bounded by a known negative constant, one could shift all rewards, but the anchor-certification argument and the zero-round convention for the negative-power mean would need reworking. A testable extension is to quantify how the minimax rate degrades as the mean lower bound approaches
  • The paper's lower bound construction uses one good arm; instances with many good arms are likely easier. An editor's guess is that a constant fraction of near-optimal arms would yield a smaller k-exponent, so the worst-case rate may only bite in the sparse-optimal-arm regime.
  • The information-cost inequality could serve as a general tool for sequential decision problems with bottleneck objectives (e.g., minimax regret under constraints on worst-round reward), connecting naturally to the Rawlsian maximin ideal in welfare economics.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper studies the strictly fair regime p=-q<0 of the generalized p-mean regret in stochastic k-armed bandits with nonnegative means and sigma-sub-Gaussian rewards. It claims a tight minimax rate sigma*sqrt(k^{max(1,q)}/T): a needle-in-haystack lower bound and a matching upper bound for a new algorithm, UCB-HARE, which combines a harmonic rank schedule with a certified positive-mean anchor. The main technical contributions are an information-cost inequality (Lemma 4.7) and a two-phase analysis that carefully handles the stopping time and the dependence between the block coin flips and the stopping event. The internal derivations appear consistent, but the minimax formulation is not valid as stated because the class ESG(k,sigma)+ has no upper bound on the optimal mean, making the finite-horizon minimax regret infinite.

Significance. If the unbounded-mean issue is repaired by an explicit bound on mu_* or by rephrasing the claims as instance-dependent/asymptotic, the paper would make a substantial contribution. The information-cost abstraction is clean and general, the lower bound is derived from first principles, and UCB-HARE's harmonic anchored exploration is a genuine algorithmic idea with a careful formal analysis. The predicted k^{q/2} penalty for q>1 is crisp and falsifiable. I did not find an internal gap in the main proof chain, but the discrepancy between the claimed 'minimax' rate and the actual theorems is central and must be fixed before publication.

major comments (2)
  1. [Section 1.2, Assumption 1.1, Theorem 1.1] The minimax regret over ESG(k,sigma)+ is infinite as stated. Since Assumption 1.1 imposes no upper bound on mu_*, take any algorithm and any k>=2, T=1. Let p_i=P(I_1=i) and choose i* with p_i*<=1/k. Set mu_*=M and all other means 0. Then m_1=M p_i*<=M/k and R_{1,-q}>=M(1-1/k), which is unbounded as M goes to infinity. Hence R_{T,-q}(k,sigma)=infinity for every T>=1, so no finite rate of the form sigma*sqrt(k^{max(1,q)}/T) can be a uniform upper bound over the stated class. The lower bound in Theorem 1.1 is not false, but it is vacuous as a 'minimax rate' statement, and the claimed matching upper bound cannot hold. The paper needs either (a) an explicit bounded-mean assumption (e.g., mu_i in [0,U]) with asymptotic statements for T sufficiently large, or (b) an explicit reframing of all upper bounds as instance-dependent, keeping the mu_*-dependent term.
  2. [Abstract, Theorem 1.2, Corollary 5.2] The advertised clean rate suppresses a mu_*-dependent term that is load-bearing. Theorem 5.1 gives R_{T,-q} <= C_q [ sigma*sqrt(H_k K_q(k) L/T) + mu_* H_k K_q(k)/T + mu_* delta ], and Corollary 5.2 for q>1 retains the term mu_* k^q/T. This term is not bounded uniformly over ESG(k,sigma)+ because mu_* is unbounded; it is also not dominated by sigma k^{q/2}/sqrt(T) for all T,k. Thus the abstract's claim that UCB-HARE achieves O_tilde(sigma*sqrt(k^{max(1,q)}/T)) is not a consequence of the stated theorems. The clean rate is only valid for a fixed instance and T large relative to mu_* (and, under a bounded-mean fix, for T sufficiently large). The authors should either state this qualification explicitly or prove a genuinely uniform bound over a bounded class.
minor comments (5)
  1. [Title/Abstract] The title line 'PRICE OFFAIRNESS INBANDITS' is missing spaces. The abstract also uses O_tilde without defining it; define it in Section 1 or 3.
  2. [Algorithm 1, line 7] The loop 'for slot h in (theta_b,1-theta_b) do' is cryptic. It presumably means iterating over the scheduled and auxiliary slots in an order determined by theta_b; please spell this out in pseudocode or in the caption.
  3. [Lemma 3.1] The handling of zero coordinates for negative-order means is by convention set to zero, but the proof says 'follows by continuity'. Since the convention is discontinuous for p<0, please state explicitly that Lemma 3.1 is applied only where all coordinates are positive, or handle the zero case separately.
  4. [Lemma 6.5] The event names A_t and F_t are introduced with the same letter A as the algorithm in the statement 'Fix an arbitrary algorithm A'. Rename the events (e.g., cal A_t, cal F_t) to avoid confusion.
  5. [Section 7] The text references Figures 3-6 but the final version should ensure the plots are included with axes and legend labels readable. Experiment D's description says 'we eventually have' in the proof sketch; this is informal and should be aligned with the formal proof.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: lower bound from first-principles information-cost inequality, upper bound from self-contained algorithm analysis; self-citations are baselines only.

full rationale

The central derivation is self-contained. The lower bound (Theorem 4.1/1.1) is built from the definition of negative-power welfare M_{-q}, a needle-in-haystack family of Gaussian instances, Jensen's inequality (Lemma 4.3), and a general information-cost inequality (Lemmas 4.4-4.7); the choice mu = sigma sqrt(k^q/T) is standard rate balancing of a derived bound, not an input assumption. The upper bound (Theorem 5.1) is analyzed from the algorithm's own definitions: harmonic-schedule prefix balance (Lemma 3.6), concentration (Lemma 6.1), anchor certification (Lemma 6.2), the ex-ante reward floor (Lemma 6.5), and UCB pseudo-regret (Lemma 6.8). No fitted parameter is renamed as a prediction. Self-citations [SPR25] and [SPC26] appear only as prior-work comparisons and a remark about linear-bandit extensions; neither supports the lower bound, the UCB-HARE algorithm, or the claimed matching rate. The unbounded-mean issue with class ESG(k,sigma)+ is a correctness concern about the stated minimax formulation, not a circularity in the derivation chain; for a fixed instance the instance-dependent upper bound remains independently meaningful. Score 0.

Assumptions & free parameters 1 free parameters · 4 assumptions · 0 invented entities

No data-fitted constants; the only hand-chosen parameter is the confidence level δ=1/T. The anchor is an algorithmic notion, not a postulated physical entity.

free parameters (1)
  • δ = 1/T
    Confidence parameter in UCB-HARE, set to 1/T to make failure probability negligible; not fitted to data but chosen by hand.
assumptions (4)
  • domain assumption Assumption 1.1: all arm means are nonnegative and μ*>0.
    Used throughout; negative-power welfare is only well-defined for nonnegative per-round rewards and the anchor requires a certified positive lower confidence bound.
  • domain assumption σ-sub-Gaussian noise with known σ.
    Used for confidence radii in the algorithm and for the Gaussian hard instances in the lower bound.
  • standard math Standard bandit lower bound Ω(σ√(k/T)) [BC12] for average regret.
    Quoted and extended to p≤1 via power-mean monotonicity; gives the q≤1 regime lower bound.
  • standard math Hoeffding/sub-Gaussian concentration and union bound for the good event E.
    Used to certify anchors and control Phase II regret.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Price of Fairness in Bandits: A Tight Minimax Characterization." pith.science (2026). https://pith.science/paper/GYP5ACYT

@misc{pith2026260713402,
  author       = {Pith},
  title        = {Pith review of: Price of Fairness in Bandits: A Tight Minimax Characterization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GYP5ACYT}},
  note         = {Machine review of arXiv:2607.13402}
}
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.

Figures

Figures reproduced from arXiv: 2607.13402 by the authors.

Figure 1
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), drawn afresh when that block begins. The Scheduled Slot comes first if θb = 1, the Auxiliary Slot otherwise. Scheduled Slot. Exploration in this slot follows a strict schedule whe… view at source ↗
Figure 2
Figure 2. ). Observe that this design exhibits a harmonic property. Since any rank r divides a 1/r fraction of consecutive integers, its exploration frequency is proportional to 1/r. Also, the sequence, being generated entirely a priori, remains independent of the reward history. 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 : 1 2 3 4 5 6 7 8 9 10 . . [PITH_FULL_I… view at source ↗
Figure 3
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, −20} [PITH_FULL_IMAGE:figures/full_fig_p027_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Single-trial ex-ante reward mt on a 200-arm instance with five elevated-mean arms (µ⋆ = 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…
Figure 5
Figure 5. Figure 5: Regret comparison between UCB-HARE and Welfarist-UCB at k ∈ {10, 100}, for fairness levels p ∈ {−1.0, −2.0, −5.0}, in Experiment D. The gap between the two algorithms grows with q = −p. At q = 1, UCB-HARE and Welfarist-UCB stay close at both arm counts, matching the re…
Figure 6
Figure 6. 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. 27 [PITH_FULL_IMAGE:figures/full_fig_p028_6.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

35 extracted references

  1. [1]

    Advances in neural information processing systems , volume=

    Improved algorithms for linear stochastic bandits , author=. Advances in neural information processing systems , volume=

  2. [2]

    2026 , eprint=

    Improved Algorithms for Nash Welfare in Linear Bandits , author=. 2026 , eprint=

    2026

  3. [3]

    Proceedings of the 37th

    Fairness and Welfare Quantification for Regret in Multi-Armed Bandits , author=. Proceedings of the 37th

  4. [4]

    Foundations and Trends

    Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems , author=. Foundations and Trends

  5. [5]

    Krishna, Anand and John, Philips George and Barik, Adarsh and Tan, Vincent Y. F. , booktitle=

  6. [6]

    Fair Division and Collective Welfare , author=

  7. [7]

    Revisiting Social Welfare in Bandits:

    Sarkar, Dhruv and Pandey, Nishant and Ray Chowdhury, Sayak , journal=. Revisiting Social Welfare in Bandits:

  8. [8]

    Biometrika , volume=

    On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples , author=. Biometrika , volume=. 1933 , publisher=

    1933

Show all 35 references
  1. [9]

    Econometrica , volume=

    The Bargaining Problem , author=. Econometrica , volume=. 1950 , doi=

    1950

  2. [10]

    Journal of Economic Theory , volume=

    On the Measurement of Inequality , author=. Journal of Economic Theory , volume=. 1970 , doi=

    1970

  3. [11]

    The Annals of Mathematical Statistics , volume=

    Consensus of Subjective Probabilities: The Pari-Mutuel Method , author=. The Annals of Mathematical Statistics , volume=. 1959 , doi=

    1959

  4. [12]

    Journal of Economic Theory , volume=

    Equity, Envy, and Efficiency , author=. Journal of Economic Theory , volume=. 1974 , doi=

    1974

  5. [13]

    Journal of the Operational Research Society , volume=

    Rate Control for Communication Networks: Shadow Prices, Proportional Fairness and Stability , author=. Journal of the Operational Research Society , volume=. 1998 , doi=

    1998

  6. [14]

    2000 , doi=

    Fair End-to-End Window-Based Congestion Control , author=. 2000 , doi=

    2000

  7. [15]

    Proceedings of the 29th

    An Axiomatic Theory of Fairness in Network Resource Allocation , author=. Proceedings of the 29th. 2010 , doi=

    2010

  8. [16]

    Operations Research , volume=

    The Price of Fairness , author=. Operations Research , volume=. 2011 , doi=

    2011

  9. [17]

    Proceedings of the 47th Annual

    Approximating the Nash Social Welfare with Indivisible Items , author=. Proceedings of the 47th Annual. 2015 , doi=

    2015

  10. [18]

    Proceedings of the 8th Innovations in Theoretical Computer Science Conference (

    Nash Social Welfare, Matrix Permanent, and Stable Polynomials , author=. Proceedings of the 8th Innovations in Theoretical Computer Science Conference (. 2017 , doi=

    2017

  11. [19]

    Proceedings of the 2017

    Convex Program Duality, Fisher Markets, and Nash Social Welfare , author=. Proceedings of the 2017. 2017 , doi=

    2017

  12. [20]

    2019 , doi=

    The Unreasonable Fairness of Maximum Nash Welfare , author=. 2019 , doi=

    2019

  13. [21]

    Proceedings of the Twenty-Ninth Annual

    Approximating Nash Social Welfare under Budget-Additive Valuations , author=. Proceedings of the Twenty-Ninth Annual. 2018 , doi=

    2018

  14. [22]

    Proceedings of the Twenty-Ninth Annual

    Nash Social Welfare for Indivisible Items under Separable, Piecewise-Linear Concave Utilities , author=. Proceedings of the Twenty-Ninth Annual. 2018 , doi=

    2018

  15. [23]

    Proceedings of the 2018

    Finding Fair and Efficient Allocations , author=. Proceedings of the 2018. 2018 , doi=

    2018

  16. [24]

    Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (

    Greedy Algorithms for Maximizing Nash Social Welfare , author=. Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (

  17. [25]

    Proceedings of the 62nd

    A Constant-Factor Approximation Algorithm for Nash Social Welfare with Submodular Valuations , author=. Proceedings of the 62nd

  18. [26]

    Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (

    Uniform Welfare Guarantees Under Identical Subadditive Valuations , author=. Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (. 2020 , doi=

    2020

  19. [27]

    , booktitle=

    Barman, Siddharth and Bhaskar, Umang and Krishna, Anand and Sundaram, Ranjani G. , booktitle=. Tight Approximation Algorithms for. 2020 , doi=

    2020

  20. [28]

    Proceedings of the 36th

    Universal and Tight Online Algorithms for Generalized-Mean Welfare , author=. Proceedings of the 36th. 2022 , doi=

    2022

  21. [29]

    Proceedings of the 2018

    Fair Allocation of Indivisible Public Goods , author=. Proceedings of the 2018. 2018 , doi=

    2018

  22. [30]

    Proceedings of the 18th International Conference on Web and Internet Economics (

    Nash Welfare Guarantees for Fair and Efficient Coverage , author=. Proceedings of the 18th International Conference on Web and Internet Economics (

  23. [31]

    Proceedings of the 38th International Conference on Machine Learning (

    Regularized Online Allocation Problems: Fairness and Beyond , author=. Proceedings of the 38th International Conference on Machine Learning (

  24. [32]

    On the Fairness of Normalized

    Eckart, Owen and Psomas, Alexandros and Verma, Paritosh , booktitle=. On the Fairness of Normalized. 2024 , doi=

    2024

  25. [33]

    Proceedings of the 38th

    Maximizing Nash Social Welfare under Two-Sided Preferences , author=. Proceedings of the 38th. 2024 , doi=

    2024

  26. [34]

    Advances in Neural Information Processing Systems 37 (

    Learning Social Welfare Functions , author=. Advances in Neural Information Processing Systems 37 (. 2024 , doi=

    2024

  27. [35]

    The Long Arm of Nashian Allocation in Online

    Huang, Zhiyi and Lee, Chui Shan and Shu, Xinkai and Wang, Zhaozi , booktitle=. The Long Arm of Nashian Allocation in Online. 2025 , doi=

    2025

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.