PaperlayerView exact revision on arXiv

Source-linked AI summary

Achieving Fairness in the Stochastic Multi-armed Bandit Problem

Vishakha Patil, Ganesh Ghalme, Vineet Nair, Y. Narahari

arXiv:1907.10516v2cs.LGstat.ML

TL;DR

FAIR-MAB asks how to maximize reward while meeting per-arm pull quotas at every round, a constraint that makes conventional regret an inadequate measure. The paper introduces FAIR-LEARN, a black-box fairness framework, and reports sub-logarithmic r-Regret with UCB1, becoming constant for sufficiently large T.

  • Problem

    FAIR-MAB requires minimum per-arm pull fractions at every round, so conventional regret against an unconstrained optimal policy does not adequately measure performance.

    Source: §1 · p. 2, §2.3 · p. 5

  • Method

    FAIR-LEARN combines an unfairness tolerance with a black-box learning algorithm and guarantees fairness uniformly over time, independently of the chosen algorithm.

    Source: §1 · p. 3

  • Results

    With UCB1, FAIR-UCB has sub-logarithmic r-Regret and, for sufficiently large T, constant r-Regret.

    Source: §1 · p. 3

  • Takeaways & Limitations

    FAIR-LEARN can be implemented on top of any MAB algorithm to provide uniform-time fairness with quantifiable regret cost.

    Source: §1 · p. 3, §8 · p. 12

    The model restricts each quota to ri ∈ [0, 1/k), with the quotas summing to less than 1.

    Source: §2.1 · p. 4

Abstract

from arXiv · show

We study an interesting variant of the stochastic multi-armed bandit problem, called the Fair-SMAB problem, where each arm is required to be pulled for at least a given fraction of the total available rounds. We investigate the interplay between learning and fairness in terms of a pre-specified vector denoting the fractions of guaranteed pulls. We define a fairness-aware regret, called $r$-Regret, that takes into account the above fairness constraints and naturally extends the conventional notion of regret. Our primary contribution is characterizing a class of Fair-SMAB algorithms by two parameters: the unfairness tolerance and the learning algorithm used as a black-box. We provide a fairness guarantee for this class that holds uniformly over time irrespective of the choice of the learning algorithm. In particular, when the learning algorithm is UCB1, we show that our algorithm achieves $O(\ln T)$ $r$-Regret. Finally, we evaluate the cost of fairness in terms of the conventional notion of regret.

1 Introduction

FAIR-MAB adds per-arm minimum-pull quotas to stochastic bandits while retaining reward maximization. FAIR-LEARN separates fairness enforcement from the choice of learning algorithm, with UCB1 yielding strong r-Regret guarantees.

1 Introduction

  • FAIR-MAB requires each arm to receive a prespecified fraction of pulls by the end of every round while the algorithm maximizes expected reward.The quotas are represented by a fairness vector r.Source: §1 · p. 2
  • The fairness-aware r-Regret compares an algorithm with an optimal policy that also satisfies the fairness constraints.The constraints model resource entitlements, where minimum allocations can conflict with maximizing efficiency.Source: §1 · p. 2
  • The paper illustrates quota-based allocation with housing ads, sponsored search ads, crowdsourcing, and wireless quality of service.In the housing-ad example, minimum display fractions are intended to ensure access for both men and women.Source: §1 · pp. 2–3
  • FAIR-LEARN combines an unfairness tolerance with a black-box learning algorithm and guarantees fairness at every time, regardless of that algorithm.The framework can be implemented on top of existing MAB algorithms.Source: §1 · p. 3
  • With UCB1, FAIR-UCB has sub-logarithmic r-Regret and, for sufficiently large T, constant r-Regret.The paper also reports stronger fairness than LFG [11], whose guarantee is asymptotic, and a regret bound with finer dependence on instance parameters.Source: §1 · p. 3

2 The Model

The model specifies a stochastic bandit with exogenous per-arm fairness quotas, then evaluates algorithms by fairness over time and regret against a fair benchmark.

2.1 The FAIR-MAB Problem

  • An instance specifies a horizon, arms, reward means, and quotas, with each quota below 1/k and their sum below 1; rewards are Bernoulli and means are unknown.The paper assumes without loss of generality that arm means are ordered, with arm 1 optimal.Source: §2.1 · p. 4

2.2 Notion of Fairness

  • The paper strengthens asymptotic fairness with α-fairness: each arm's quota shortfall is at most α at every time.At α = 0 the algorithm is fair; any constant α-fair guarantee also implies asymptotic fairness.Source: §2.2 · p. 4

2.3 Notions of Regret

  • Conventional regret is inadequate for FAIR-MAB because its optimal policy ignores quotas; r-Regret instead uses a policy satisfying the fairness constraints.For suboptimal arms, required quota pulls are the fair baseline, while additional pulls incur the arm's mean-gap cost; fairness and low regret impose competing pull-count goals.Source: §2.3 · p. 5

3 A Framework for FAIR-MAB Algorithms

FAIR-LEARN enforces fairness uniformly over time regardless of the black-box learning algorithm. With UCB1, FAIR-UCB has sub-logarithmic r-Regret, which is constant for sufficiently large horizons in the stated case.

3 A Framework for FAIR-MAB Algorithms

  • FAIR-LEARN is a meta-algorithm that allows any MAB learning algorithm to be plugged in as a black box without losing its fairness guarantee.The authors describe the framework as readily implementable in practice.Source: §3 · pp. 5–6
  • FAIR-LEARN is α-fair at every time, independent of the learning algorithm used as a black box.The guarantee also holds for α = 0.Source: §3 · p. 5
  • With UCB1, FAIR-UCB has sub-logarithmic r-Regret when S(T) is nonempty and constant r-Regret when S(T) is empty.The paper also provides a distribution-free r-Regret bound for FAIR-UCB.Source: §3 · p. 6

4 Cost of Fairness

The conventional-regret cost of fairness depends on the unfairness tolerance α. Under the stated conditions, regret is logarithmic when S(T) is empty, but can be O(T) when it is nonempty.

4 Cost of Fairness

  • O(ln T) expected regret holds when S(T) is empty, including when α exceeds riT − 8 ln T/∆i^2 for every suboptimal arm i.The threshold depends on the problem instance.Source: §4 · p. 7
  • O(T) regret can occur when S(T) is nonempty, with additional regret riT − α for each arm i in S(T).The result makes the conventional-regret trade-off explicit in the unfairness tolerance α.Source: §4 · p. 7

5 Proof of Theoretical Results

The fairness proof tracks arm sets and uses induction to maintain an invariant that bounds each arm’s quota shortfall. The UCB1 regret analysis separately considers whether an arm’s required fair pulls exceed a logarithmic threshold.

5 Proof of Theoretical Results

  • The fairness proof partitions the arms into sets M1,t through Mk,t and St, then uses induction to maintain the partition conditions over time.The sets are defined by ranges of quota shortfall; St contains arms whose shortfall is below α.Source: §5 · pp. 7–8
  • The maintained invariant yields ⌊rit⌋ − Ni,t ≤ α for every arm at every time, establishing FAIR-LEARN’s α-fairness.The proof tracks the pulled arm and the transitions of unpulled arms between sets from one round to the next.Source: §5 · p. 8
  • The FAIR-UCB regret analysis bounds expected pulls of suboptimal arms by treating separately cases above and below the 8 ln T threshold.The proof builds on the UCB1 regret analysis and uses the arm’s fairness-required pull count to distinguish the cases.Source: §5 · pp. 9–10

6 Experimental Results

Simulations illustrate the cost of fairness and compare FAIR-UCB with LFG. FAIR-UCB and LFG have comparable r-Regret, while FAIR-UCB’s fairness guarantee holds uniformly over time and LFG’s is asymptotic.

6 Experimental Results

  • FAIR-UCB and LFG perform comparably in r-Regret, and the simulations validate the logarithmic r-Regret bound.Figure 3 plots time against r-Regret on a logarithmic scale.Source: §6 · pp. 10–11, Figure 3 · p. 11
  • In Figure 2, as unfairness tolerance α increases up to a problem-dependent threshold, conventional regret decreases while maximum fairness violation increases; above it, regret drops drastically and logarithmic regret is recovered.Source: §6 · p. 11
  • FAIR-UCB’s fairness guarantee holds uniformly over the horizon, whereas LFG’s fairness violation eventually falls to zero, giving asymptotic fairness.Figure 4 compares time with maximum fairness violation for an instance with three arms and α = 0.Source: Figure 4 · p. 11, §6 · p. 11

7 Related Work

The related work situates FAIR-MAB among fairness methods for online learning and bandits with additional constraints. It contrasts the paper’s guarantees with prior work, especially LFG and a personalized news-feed approach.

7 Related Work

  • Prior fairness work spans classification, regression, ranking, recommendation, and online learning, including bandit approaches to individual and meritocratic fairness [13; 14; 15; 16; 17; 18; 19; 20; 21; 22; 23; 24; 25; 26; 27].Joseph et al. [24] use a meritocratic criterion; other cited works consider treatment equality and fairness relative to an unknown metric.Source: §7 · pp. 11–12
  • Other constrained bandit settings include knapsack, budget, and resource-allocation constraints [4] [5] [28] [29] [31].These works constrain arm pulls through budgets, costs, or resource allocation.Source: §7 · p. 12
  • Unlike LFG [11], FAIR-MAB provides a uniform-over-time fairness guarantee and an O(ln T) r-Regret bound with finer dependence on instance parameters.The paper describes LFG’s guarantee as asymptotic.Source: §7 · p. 12
  • Unlike Celis et al. [34], the algorithm gives deterministic any-time fairness, an explicit fairness–regret trade-off through α, and O(1) computational overhead.The cited approach provides any-time fairness only in expectation and requires at least one linear program per round.Source: §7 · p. 12

8 Discussion and Future Work

The discussion presents uniform-time fairness and the fairness–regret trade-off as central conclusions, while identifying other fairness notions in online learning as future work. The appendix states the bounded-variable setup for Hoeffding’s lemma and describes UCB1’s estimate-based arm selection.

8 Discussion and Future Work

  • The paper concludes that minimum-pull guarantees can be indispensable in resource allocation, while r-Regret benchmarks against an optimal policy satisfying the same fairness constraints.It identifies incorporating disparate impact, statistical parity, and equalized odds into online learning as future work.Source: §8 · p. 12

A.1 Hoeffding’s Lemma; A.2 Upper Confidence Bound (UCB) based Algorithm

  • Hoeffding’s lemma is introduced for i.i.d. bounded random variables, and UCB1 selects the arm with the highest estimate formed from empirical reward and a confidence interval.The estimate depends on the arm’s empirical mean and number of prior pulls.Source: §A.2 · p. 16, §A.1 · p. 16

A.3 Distribution-free Regret Bound for UCB1

The appendix derives a distribution-free regret bound for UCB1 and uses the zero-quota case to transfer that bound to FAIR-UCB. The proof relies on concentration arguments and a comparison of suboptimal-arm pulls.

A.3 Distribution-free Regret Bound for UCB1

  • UCB1’s distribution-free regret bound is derived by bounding suboptimal-arm pulls using concentration events, Hoeffding’s inequality, a union bound, and Jensen’s inequality.The supplied theorem passages do not preserve the full bound expression.Source: §A.3 · pp. 18–19

B.1 Distribution-free r-Regret bound for FAIR-UCB √

  • FAIR-UCB’s distribution-free r-Regret bound follows by comparing its regret with the zero-quota case, where FAIR-UCB reduces to UCB1.The proof uses the same instance with all fairness quotas set to zero.Source: §A.3 · p. 19, §B.1 · p. 20

B.2 Cost of Fairness in the MAB Problem

The cost-of-fairness analysis bounds regret by controlling suboptimal-arm pulls, with cases determined by how many pulls are needed to satisfy each arm’s quota. The supplied results give a logarithmic pull bound in the below-threshold case.

B.2 Cost of Fairness in the MAB Problem

  • The proof bounds expected regret by bounding expected pulls of each suboptimal arm and separates arms according to their quota-related pull requirements.The paper states an expected-regret result for FAIR-UCB, but the supplied theorem expression is incomplete.Source: §B.2 · pp. 20–21
  • For arms with r_i T − α ≥ 8 ln T, the analysis bounds expected pulls using the quota requirement and an additional term.The supplied expression is incomplete, so its additional term cannot be specified.Source: §B.2 · p. 21
  • For arms with r_i T − α < 8 ln T, the expected number of pulls is bounded by 8 ln T.This is the case where the quota-related pull requirement falls below the stated threshold.Source: §B.2 · p. 21, C Horizon-aware Algorithms · p. 23

C Horizon-aware Algorithms

T-FAIR-UCB uses a known horizon to separate quota satisfaction from regret minimization, achieving logarithmic r-Regret while satisfying fairness at the horizon endpoint. Its analysis uses a threshold on quota-driven pulls to bound suboptimal-arm pulls.

C Horizon-aware Algorithms

  • The initial quota-satisfaction pulls can both explore the arms and incur no regret during the first T′ rounds.The passage defines T′ as the sum of the quota fractions multiplied by T.Source: C Horizon-aware Algorithms · p. 21
  • T-FAIR-UCB knows T and separates fairness-constraint satisfaction from regret minimization, but guarantees fairness at the horizon rather than uniformly over time.It satisfies all arms’ fairness requirements at T′, not the every-round guarantee of FAIR-UCB.Source: C Horizon-aware Algorithms · pp. 21–22
  • The proof divides suboptimal arms according to whether their quota requires at least 8 ln T pulls, bounding pulls by 8 ln T when the quota is below that threshold.The supplied proof passages do not show the full bound for the other case.Source: C Horizon-aware Algorithms · pp. 22–23
  • O(ln T) r-Regret is achieved by T-FAIR-UCB for the Fair-MAB problem.The theorem also gives an r-dependent regret bound, though its expression is not fully present in these passages.Source: C Horizon-aware Algorithms · pp. 22–23

D Rationale for Simulation Parameters

The simulations use two synthetic FAIR-MAB instances, with parameter choices tailored to display regret behavior in one and fairness guarantees in the other. Horizon, arm counts, reward gaps, and quotas are selected to balance convergence visibility, runtime, and evaluation rigor.

D Rationale for Simulation Parameters

  • The experiments use synthetic data to control the tuning of parameters across two FAIR-MAB instances.Instance 1 evaluates fairness versus regret; Instance 2 compares FUCB with LFG.Source: D Rationale for Simulation Parameters · p. 23
  • Instance 1 uses a larger T to capture FAIR-UCB convergence, while Instance 2 uses a smaller T to show maximum fairness violation more clearly.Large horizons increase simulation time, while small horizons may miss bandit convergence.Source: D Rationale for Simulation Parameters · p. 24
  • Instance 1 uses a moderate arm count and small adjacent reward gaps to show regret behavior without excessive simulation time.The selected mean rewards begin at µ1 = 0.8 and set µi = µ1 − ∆i with ∆i = 0.01i.Source: D Rationale for Simulation Parameters · pp. 23–24
  • Instance 2 uses few arms and larger reward differences so the optimal arm is identified quickly and fairness guarantees can be tested more rigorously.Higher quota fractions for suboptimal arms make the fairness test stricter relative to classic UCB1.Source: D Rationale for Simulation Parameters · p. 24
  • The fairness vector is chosen to make Instance 1 depict conventional regret’s cost of fairness and Instance 2 assess fairness guarantees carefully.The authors report trying other fairness-vector values but selecting these for representation.Source: D Rationale for Simulation Parameters · p. 24
Loading 1907.10516v2…