PaperlayerView exact revision on arXiv

Source-linked AI summary

Fairness in Learning: Classic and Contextual Bandits

Matthew Joseph, Michael Kearns, Jamie Morgenstern, Aaron Roth

arXiv:1605.07139v2cs.LGstat.ML

TL;DR

The paper asks whether individual fairness can coexist with effective learning when reward functions are unknown in multi-armed and contextual bandits. It formalizes fairness, develops fair algorithms and lower bounds, and connects contextual fair learning to KWIK learning. The results show cubic fair-learning costs in classic bandits, polynomial dependence on dimension for linear contextual bandits, and exponential worst-case costs for conjunctions.

  • Problem

    The paper studies whether fairness constraints are compatible with learning optimal decisions in bandit settings with unknown rewards.

  • Method

    The paper uses chained confidence intervals for classic bandits and establishes transformations between KWIK learners and fair contextual bandit algorithms.

  • Results

    Fair learning requires O(k^3) rounds for non-trivial regret in classic bandits, has polynomial-in-d per-round regret for linear contextual bandits, and can require exponentially many rounds for conjunctions.

  • Takeaways & Limitations

    Fairness can impose a mild or severe learning cost depending on the bandit problem and reward-function class.

  • Takeaways & Limitations

    The classic-bandit fairness model treats each arm as an internally indistinguishable equivalence class and does not require population-wide statistical parity.

Abstract

from arXiv · show

We introduce the study of fairness in multi-armed bandit problems. Our fairness definition can be interpreted as demanding that given a pool of applicants (say, for college admission or mortgages), a worse applicant is never favored over a better one, despite a learning algorithm's uncertainty over the true payoffs. We prove results of two types. First, in the important special case of the classic stochastic bandits problem (i.e., in which there are no contexts), we provide a provably fair algorithm based on "chained" confidence intervals, and provide a cumulative regret bound with a cubic dependence on the number of arms. We further show that any fair algorithm must have such a dependence. When combined with regret bounds for standard non-fair algorithms such as UCB, this proves a strong separation between fair and unfair learning, which extends to the general contextual case. In the general contextual case, we prove a tight connection between fairness and the KWIK (Knows What It Knows) learning model: a KWIK algorithm for a class of functions can be transformed into a provably fair contextual bandit algorithm, and conversely any fair contextual bandit algorithm can be transformed into a KWIK learning algorithm. This tight connection allows us to provide a provably fair algorithm for the linear contextual bandit problem with a polynomial dependence on the dimension, and to show (for a different class of functions) a worst-case exponential gap in regret between fair and non-fair learning algorithms

1 Introduction

The paper studies whether individual fairness is compatible with learning in contextual bandits, where decisions must respect unknown reward differences. It shows that fairness can impose substantial learning costs, including cubic dependence on arms and exponential delays for some function classes.

  • 1 Introduction: The paper models fairness in contextual bandits, where algorithms choose among applicants or other arms using contexts and unknown reward functions.The optimal policy selects the arm with the highest expected reward, but the reward functions must be learned.
  • 1 Introduction: Fairness requires that an algorithm not favor an individual with lower expected reward over one with higher expected reward.The definition is individual-level rather than population-level statistical parity.
  • 1 Introduction: Fairness can conflict with learning: its cost is mild for some problems but large for others.The constraint is compatible with implementing the optimal policy but not always with learning that policy efficiently.
  • 1 Introduction: In classic stochastic bandits, fair learning requires O(k^3) rounds for non-trivial regret, whereas unconstrained learning can do so after O(k) rounds.The paper also shows that any fair algorithm can be forced to incur constant per-round regret for Ω(k^3) rounds.
  • 1 Introduction: The fairness notion differs from statistical parity because it compares individuals, even when their populations have different average creditworthiness.A qualified individual from a lower-average population cannot be disfavored relative to a less qualified individual from another population.
  • 1 Introduction: The paper connects fair contextual bandit learning to KWIK learning and uses this connection to obtain polynomial-in-d regret for linear contextual bandits.For conjunctions over boolean contexts, fair learners cannot achieve non-trivial regret before exponentially many rounds.

2 Preliminaries

The preliminaries define contextual and classic stochastic bandits through unknown reward distributions and policies, then formalize regret and fairness. They also introduce KWIK learning as a confidence-based prediction model.

  • 2 Preliminaries: A contextual bandit has a context domain, k arms, and one unknown payoff function f_j in a function class for each arm.At each round, the algorithm observes a context, chooses an arm, and receives a stochastic reward.
  • 2 Preliminaries: The optimal policy selects the arm distribution that maximizes expected reward, and regret compares an algorithm with this policy over revealed contexts.The regret bound is defined as a worst-case bound over context sequences.
  • 2 Preliminaries: Contextual-bandit fairness requires that an arm receive higher selection probability only when its mean payoff is higher than another arm’s.The definition must hold with probability at least 1−δ across rounds and arm pairs.
  • 2 Preliminaries: KWIK learning allows a learner to output either an accurate prediction or ⊥, meaning “I don’t know.”Its KWIK bound limits how often the learner may be forced to abstain while maintaining prediction accuracy with high probability.
  • 2 Preliminaries: The classic stochastic bandit is the no-context special case, with each arm having an unknown reward distribution and mean μ_j.The algorithm observes rewards from the distribution associated with the selected arm.

3 Fair Classic Stochastic Bandits: An Algorithm

FairBandits adapts UCB with chained confidence intervals, preserving fairness by treating statistically indistinguishable arms equally. Its active set shrinks as arms become safely separable, but this conservatism yields a regret bound that becomes non-trivial only after Ω(k^3) rounds.

  • Algorithm: FairBandits chains arms whose confidence intervals overlap and plays uniformly among arms connected to the highest-upper-confidence arm.The active set begins with all arms and retains only arms chained to the previous round’s highest-UCB arm.
  • Regret: The regret guarantee becomes non-trivial only for T=Ω(k^3), compared with T=O(k) for unconstrained UCB, and this k-dependence is optimal.Without instance-specific gap assumptions, the stated dependence on T is also optimal.
  • Algorithm: The active set can only shrink because unchained arms are certified to have lower means than the remaining chained arms.Removed arms are never played again.
  • Fairness: With probability at least 1−δ, all maintained confidence intervals contain the corresponding true means throughout the run.This confidence guarantee supports FairBandits’ fairness proof.
  • Fairness: FairBandits is δ-fair because arms in the active set are played uniformly, while excluded arms have strictly smaller means with high probability.Uniform play avoids preferential treatment among active arms.

4 Fair Classic Stochastic Bandits: A Lower Bound

The lower-bound construction shows that fairness forces algorithms to explore arms uniformly until adjacent means can be distinguished with high posterior confidence. Consequently, every fair algorithm can incur constant per-round regret for Ω(k^3) rounds.

  • Lower-bound result: The lower bound proves that no fair algorithm can achieve diminishing regret before Ω(k^3) rounds.This establishes optimal dependence on the number of arms.
  • Hard instances: The hard instance distribution makes adjacent arms equal with probability at least 1/4 while uniform play incurs constant per-round regret.Means are independently drawn from arm-specific distributions, with Bernoulli rewards.
  • Fairness constraint: Fairness requires adjacent arms to be played equally until the posterior probability that their means are equal falls below δ.The argument uses posterior reasoning over observed rewards.
  • Regret consequence: Before histories distinguish an arm, a fair algorithm must play uniformly across all k arms, which produces Ω(1) regret in such rounds.The proof shows this behavior with high probability for the lower-bound histories.
  • Information bottleneck: Distinguishing an arm requires Ω(k^2 ln 1/δ) observations, so uniform exploration delays sufficient information until Ω(k^3 ln 1/δ) rounds.The observation requirement applies to distinguishing adjacent means under the constructed prior.

5 KWIK Learnability Implies Fair Bandit Learnability

The section constructs a fair contextual-bandit algorithm from KWIK learners, using confidence intervals and chaining to control choices while bounding regret through KWIK uncertainty.

  • Guarantees: Theorem 4 states that if the function class is KWIK learnable with bound m(ϵ,δ), KWIKToFair is δ-fair with regret polynomially related to that bound.The regret analysis bounds uncertainty rounds using terms involving k^2·m(ϵ∗,δ∗) and k^3 logarithmic factors.
  • Algorithm construction: KWIKToFair initializes one KWIK learner per arm and interprets numeric predictions as confidence intervals around each arm’s payoff.When a learner outputs ⊥, the algorithm treats the arm as uncertain.
  • Algorithm construction: The algorithm selects uniformly among arms chained through overlapping ϵ∗-intervals, preserving fairness when predictions are sufficiently accurate.When all learners predict, chaining links arms whose intervals cannot reliably distinguish their payoffs.
  • Algorithm construction: When any learner outputs ⊥, KWIKToFair selects uniformly across all arms and updates the selected learner with feedback.Unselected learners whose outputs are ⊥ are rolled back rather than updated.
  • Linear contextual bandits: For bounded-norm linear functions, the construction yields a fair contextual-bandit algorithm with polynomial regret dependence on the dimension.The result uses a KWIK bound of ˜O(d^3/ϵ^4) for linear functions.

6 Fair Bandit Learnability Implies KWIK Learnability

The section shows that any fair contextual-bandit algorithm with low regret can be converted into a KWIK learner, because fairness forces accurate reward-function knowledge before preferential exploitation.

  • Reduction: A fair no-regret bandit algorithm must identify and exploit an optimal arm while maintaining tight confidence about every arm’s reward function.The construction converts this confidence requirement into KWIK predictions.
  • Guarantee: Theorem 6 establishes a polynomial relationship between the fair algorithm’s regret bound and the resulting KWIK bound.The reduction chooses contexts whose payoffs differ by controlled multiples of ϵ∗ and uses fairness to locate an accurate interval for the unknown reward.
  • Reduction: FairToKWIK simulates a two-arm bandit instance for each arriving example and queries the fair algorithm on carefully chosen auxiliary contexts.The simulation uses KWIK feedback and can roll back histories for queries that do not produce an abstention.
  • Exponential separation: For conjunctions, an unfair algorithm achieves regret O(k^2d), but it violates fairness by favoring an arm predicted as 0 over an equally rewarding arm predicted as 1.This contrasts with the exponential worst-case regret required by fair algorithms.
  • Exponential separation: The equivalence implies that fair contextual-bandit regret can be exponentially worse than unfair regret for conjunctions on d Boolean variables.A KWIK lower bound of Ω(2^d) transfers to fair contextual-bandit regret under the stated δ condition.

A Missing Proofs for the Classic Stochastic Bandits Upper Bound

The appendix supplies concentration arguments used to justify confidence intervals and sampling-count bounds in the FairBandits analysis.

  • Confidence intervals: A Chernoff-bound argument controls deviations of empirical rewards from an arm’s true mean.The proof defines indicator variables for successive pulls of a fixed arm.
  • Confidence intervals: A union bound extends the confidence guarantee across all rounds, limiting the probability that any true mean leaves its confidence interval.The resulting failure probability is bounded in terms of δ.
  • Sampling counts: The remaining lemmas establish persistence of active arms and combine per-arm bounds through a union bound.These lemmas are used to bound FairBandits regret in the main text.
  • Sampling counts: A second Chernoff argument bounds deviations between an arm’s number of pulls and its expected selection probability.The proof represents pulls with indicator variables and applies an additive concentration inequality.

B Missing Proofs for the Classic Stochastic Bandits Lower Bound

The appendix develops the probabilistic lower-bound machinery for fair stochastic-bandit learning by comparing reward experiments and histories that fairness cannot reliably distinguish.

  • Lower-bound setup: The lower-bound lemmas analyze payoff distributions and histories to identify when an algorithm’s choices reveal unfair preferences between equally valued arms.The proof reasons about posterior probabilities and indistinguishable reward experiments.
  • Indistinguishable experiments: Two experiments are constructed with identical joint reward distributions, allowing the proof to compare algorithm behavior without changing observed rewards.The equality of reward distributions is used directly in the argument.
  • Fairness constraint: Posterior and probability bounds show that histories producing unequal treatment of equal-mean arms would occur too often for a δ-fair algorithm.The proof combines fairness with Markov-style probability reasoning.
  • Lower-bound conclusion: The resulting probability statement supplies the key contradiction used to establish the stochastic-bandit fair lower bound.The argument concludes after bounding the relevant histories over means and rewards.

C Missing Proofs for the Contextual Bandit Setting

The proofs establish fairness guarantees from KWIK learners and analyze their regret, including a linear-function specialization and an unfair conjunction-learning benchmark.

  • KWIK-to-fair conversion: Theorem 4 repeatedly invokes KWIKToFair across epochs to obtain a δ-fair algorithm with a quantified regret guarantee through the doubling trick.Each epoch contributes at most 3 · 2^E k ε*_E regret, and fewer than log(T) epochs are used through round T.
  • Linear functions: For linear functions, the learner mistake bound is ˜O(d^3/ε^4), yielding regret R(T) = O(T^4/5 k^6/5 d^3/5).The derivation substitutes the fixed-point relation ε* = k · m(ε*, δ)/T into the general regret bound.
  • Conjunction benchmark: ConjunctionBandit is presented as an unfair learning algorithm for conjunctions and achieves regret R(T) = O(k^2d).Its analysis shows that candidate-variable sets remain supersets of the true sets, preventing false-positive mistakes; regret arises from false negatives.
  • Conjunction benchmark: ConjunctionBandit only accumulates regret when it predicts that all arms have reward 0 although some arm has reward 1.The algorithm's candidate-set invariant implies that active arms have reward 1, so false negatives are the remaining source of regret.
  • Fair-to-KWIK conversion: FairToKWIK constructs a KWIK learner by running a fair contextual bandit algorithm on paired contexts, with conjunction outputs handled using ε = 0 and ε* = 1.The construction uses 2T histories and contexts and applies union bounds over rounds, arms, and learner queries to preserve the fairness and accuracy guarantees.
Loading 1605.07139v2…