Fairness in Learning: Classic and Contextual Bandits

Introduction

Automated techniques from statistics and machine learning are increasingly being used to make decisions that have important consequences on people’s lives, including hiring (Miller, 2015), lending (Byrnes, 2016), policing (Rudin, 2013), and even criminal sentencing (Barry-Jester et al., 2015). These high stakes uses of machine learning have led to increasing concern in law and policy circles about the potential for (often opaque) machine learning techniques to be discriminatory or unfair (Coglianese and Lehr, 2016; Barocas and Selbst, 2016). Moreover, these concerns are not merely hypothetical: Sweeney (2013) observed that contextual ads for public record services shown in response to Google searches for stereotypically African American names were more likely to contain text referring to arrest records, compared to comparable ads shown in response to searches for stereotypically Caucasian names, which showed more neutral text. She confirmed that this was not because of stated preferences of the advertisers, but rather the automated outcome of Google’s targeting algorithms. Despite the recognized importance of this problem, very little is known about technical solutions to the problem of “unfairness”, or the extent to which “fairness” is in conflict with the goals of learning. For example, a 2014 White House report (Podesta et al., 2014) notes that “[t]he increasing use of algorithms to make eligibility decisions must be carefully monitored for potential discriminatory outcomes for disadvantaged groups, even absent discriminatory intent$\ldots$ additional research in measuring adverse outcomes due to the use of scores or algorithms is needed to understand the impacts these tools are having and will have in both the private and public sector as their use grows.” Along the same lines, a 2016 White House report (Munoz et al., 2016) observes that “[a]s improvements in the uses of big data and machine learning continue, it will remain important not to place too much reliance on these new systems without questioning and continuously testing the inputs and mechanics behind them and the results they produce.” Similarly, in a recent speech FTC Commissioner Julie Brill (Julie Brill, 2015) observed, “$\ldots$ a lot remains unknown about how big data-driven decisions may or may not use factors that are proxies for race, sex, or other traits that U.S. laws generally prohibit from being used in a wide range of commercial decisions $\ldots$ What can be done to make sure these products and services––and the companies that use them – treat consumers fairly and ethically?”

Our main conceptual result is that this intuition is incorrect in the face of unknown reward functions. Even though the constraint of fairness is consistent with implementing the optimal policy, it is not necessarily consistent with learning the optimal policy. We show that fairness always has a cost, in terms of the achievable learning rate of the algorithm. For some problems, the cost is mild, but for others, the cost is large.

2 Our Results

We divide our results into two parts. First, we study the classic stochastic multi-armed bandit problem (Lai and Robbins, 1985; Katehakis and Robbins, 1995). In this case, there are no contexts, and each arm $i$ has a fixed but unknown average reward $\mu_{i}$. Note that this is a special case of the contextual bandit problem in which the contexts are the same every day. In this setting, our fairness constraint specializes to require that with probability $1-\delta$, for any pair of arms $i,j$ for which $\mu_{i}\geq\mu_{j}$, at no round $t$ does the algorithm play arm $j$ with probability higher than that with which it plays arm $i$. Note that even this special case models interesting scenarios from the point of view of fairness in learning. It models, for example, the case in which choices are made by a loan officer after applicants have been categorized into $k$ internally indistinguishable equivalence classes based on their applications.

Without a fairness constraint, it is known that it is possible to guarantee non-trivial regret to the optimal policy after only $T=O(k)$ many rounds (Auer et al., 2002). In Section 3, we give an algorithm that satisfies our fairness constraint and is able to guarantee non-trivial regret after $T=O(k^{3})$ rounds. We then show in Section 4 that it is not possible to do better – any fair learning algorithm can be forced to endure constant per-round regret for $T=\Omega(k^{3})$ rounds. Thus, we tightly characterize the optimal regret attainable by fair algorithms in this setting, and formally separate it from the regret attainable by algorithms absent a fairness constraint. Note that this already shows a separation between the best possible learning rates for contextual bandit learning with and without the fairness constraint – the stochastic multi-armed bandit problem is a special case of every contextual bandit problem, and for general contextual bandit problems, it is also known how to get non-trivial regret after only $T=O(k)$ many rounds (Agarwal et al., 2014; Beygelzimer et al., 2011; Chu et al., 2011).

We then move on to the general contextual bandit setting and prove a broad characterization result, relating fair contextual bandit learning to KWIK learning (Li et al., 2011). The KWIK model, which stands for Knows What it Knows and has a close relationship with reinforcement learning, is a model of sequential supervised classification in which the learning algorithm must be confident in its predictions. Informally, a KWIK learning algorithm receives a sequence of unlabeled examples, whose true labels are defined by some unknown function in a class $C$. For each example, the algorithm may either predict a label, or announce “I Don’t Know”. The KWIK requirement is that with high probability, for each example, if the algorithm predicts a label, then its prediction must be very close to the true label. The quality of a KWIK learning algorithm is characterized by its “KWIK bound”, which provides an upper bound on the maximum number of times the algorithm can be forced to announce “I Don’t Know”. For any contextual bandit problem (defined by the set of functions $C$ from which the payoff functions $f_{j}$ may be selected), we show that the optimal learning rate of any fair algorithm is determined by the best KWIK bound for the class $C$. We prove this constructively – we give a reduction showing how to convert a KWIK learning algorithm into a fair contextual bandit algorithm in Section 5, and vice versa in Section 6. Both reductions show that the KWIK bound of the KWIK algorithm is polynomially related to the regret of the fair algorithm.

3 Other Related Work

Several papers study the problem of fairness in machine learning. One line of work aims to give algorithms for batch classification which achieve group fairness otherwise known as equality of outcomes, statistical parity – or algorithms that avoid disparate impact (see e.g. Calders and Verwer (2010); Luong et al. (2011); Kamishima et al. (2011); Feldman et al. (2015); Fish et al. (2016) and Adler et al. (2016) for a study of auditing existing algorithms for disparate impact). While statistical parity is sometimes a desirable goal – indeed, it is sometimes required by law – as observed by Dwork et al. (2012) and others, it suffers from two problems. First, if different populations indeed have different statistical properties, then it can be at odds with accurate classification. Second, even in cases when statistical parity is attainable with an optimal classifier, it does not prevent discrimination at an individual level – see Dwork et al. (2012) for a catalog of ways in which statistical parity can be insufficient from the perspective of fairness. In contrast, we study a notion aimed at guaranteeing fairness at the individual level.

Our definition of fairness is most closely related to that of Dwork et al. (2012), who proposed and explored the basic properties of a technical definition of individual fairness formalizing the idea that “similar individuals should be treated similarly”. Specifically, their work presupposes the existence of a task-specific metric on individuals, and proposes that fair algorithms should satisfy a Lipschitz condition with respect to this metric. Our definition of fairness is similar, in that the expected reward of each arm is a natural metric through which we define fairness. The main conceptual distinction between our work and Dwork et al. (2012) is that their work operates under the assumption that the metric is known to the algorithm designer, and hence in their setting, the fairness constraint binds only insofar as it is in conflict with the desired outcome of the algorithm designer. The most challenging aspect of this approach (as they acknowledge) is that it requires that some third party design a “fair” metric on individuals, which in a sense encodes much of the relevant challenge. The question of how to design such a metric was considered by Zemel et al. (2013), who study methods to learn representations that encode the data, while obscuring protected attributes. Our fairness constraint, conversely, is entirely aligned with the goal of the algorithm designer in that it is satisfied by the optimal policy; nevertheless, it affects the space of feasible learning algorithms, because it interferes with learning an optimal policy, which depends on the unknown reward functions.

At a technical level, our work is related to Amin et al. (2012) and Amin et al. (2013), which also relate KWIK learning to bandit learning in a different context, unrelated to fairness (when the arm space is very large).

Preliminaries

Let $\Pi$ be the set of policies mapping contexts to distributions over arms $X^{k}\to\Delta^{k}$, and $\pi^{*}$ the optimal policy which selects a distribution over arms as a function of contexts to maximize the expected reward of those arms. The pseudo-regret of an algorithm $\mathcal{A}$ on contexts $x^{1},\ldots,x^{T}$ is defined as follows, where $\pi^{t}$ represents $\mathcal{A}$’s distribution on arms at round $t$:

We hereafter refer to this as the regret of $\mathcal{A}$. The optimal policy $\pi^{*}$ pulls arms with highest expectation at each round, so:

We say that $\mathcal{A}$ satisfies regret bound $R(T)$ if $\max_{x^{1},\ldots,x^{T}}\textrm{Regret}(x^{1},\ldots,x^{t})\leq R(T)$.

We now define what it means for a contextual bandit algorithm to be $\delta$-fair with respect to its arms. Informally, this will mean that $\mathcal{A}$ will play arm $i$ with higher probability than arm $j$ in round $t$ only if $i$ has higher mean than $j$ in round $t$, for all $i,j\in[k]$, and in all rounds $t$.

$\mathcal{A}$ is $\delta$-fair if, for all sequences of contexts $x^{1},\ldots,x^{t}$ and all payoff distributions $\mathcal{D}^{t}_{1},\ldots,\mathcal{D}^{t}_{k}$, with probability at least $1-\delta$ over the realization of the history $h$, for all rounds $t\in[T]$ and all pairs of arms $j,j^{\prime}\in[k]$,

Definition 1 prohibits favoring lower payoff arms over higher payoff arms. One relaxed definition only requires that $\pi^{t}_{j|h}=\pi^{t}_{j^{\prime}|h}$ when $f_{j}(x^{t}_{j})=f_{j^{\prime}}(x^{t}_{j^{\prime}})$ – requiring only identical individuals (concerning expected payoff) be treated identically. This relaxation is a special case of Dwork et al. (2012)’s proposed family of definitions, which require that “similar individuals be treated similarly”. We use Definition 1 as it is better motivated in its implications for fair treatment of individuals, but all of our results – including our lower bounds – apply also to this relaxation.

Its numerical predictions are accurate: for all $t$, $\hat{y}^{t}\in\{\bot\}\cup[f(x^{t})-\epsilon,f(x^{t})+\epsilon]$, and

1 Specializing to Classic Stochastic Bandits

In Sections 3 and 4, we study the classic stochastic bandit problem, an important special case of the contextual bandit setting described above. Here we specialize our notation to this setting, in which there are no contexts. For each arm $j\in[k]$, there is an unknown distribution $\mathcal{D}_{j}$ over $$with unknown mean$\mu_{j}$. A learning algorithm$\mathcal{A}$chooses an arm$i_{t}$in round$t$, and observes the reward$r^{t}_{i_{t}}\sim\mathcal{D}_{i_{t}}$for the arm that it chose. Let$i^{*}\in[k]$be the arm with highest expected reward:$i^{*}\in\operatorname*{arg\,max}_{i\in[k]}\mu_{i}$. The pseudo-regret of an algorithm$\mathcal{A}$on$\mathcal{D}_{1},\ldots,\mathcal{D}_{k}$ is now just:

$\delta$-fairness in the classic bandit setting specializes as follows:

$\mathcal{A}$ is $\delta$-fair if, for all distributions $\mathcal{D}_{1},\ldots,\mathcal{D}_{k}$, with probability at least $1-\delta$ over the history $h$, for all $t\in[T]$ and all $j,j^{\prime}\in[k]$:

Fair Classic Stochastic Bandits: An Algorithm

In this section, we describe a simple and intuitive modification of the standard UCB algorithm (Auer et al., 2002), called FairBandits, prove that it is fair, and analyze its regret bound. The algorithm and its analysis highlight a key idea that is important to the design of fair algorithms in this setting: that of chaining confidence intervals. Intuitively, as a $\delta$-fair algorithm explores different arms it must play two arms $j_{1}$ and $j_{2}$ with equal probability until it has sufficient data to deduce, with confidence $1-\delta$, either that $\mu_{j_{1}}>\mu_{j_{2}}$ or vice versa. FairBandits does this by maintaining empirical estimates of the means of both arms, together with confidence intervals around those means. To be safe, the algorithm must play the arms with equal probability while their confidence intervals overlap. The same reasoning applies simultaneously to every pair of arms. Thus, if the confidence intervals of each pair of arms $j_{i}$ and $j_{i+1}$ overlap for each $i\in[k]$, the algorithm is forced to play all arms $j$ with equal probability. This is the case even if the confidence intervals around arm $j_{k}$ and arm $j_{1}$ are far from overlapping – i.e. when the algorithm can be confident that $\mu_{j_{1}}>\mu_{j_{k}}$.

This approach initially seems naive: in an attempt to achieve fairness, it seems overly conservative when ruling out arms, and can be forced to play arms uniformly at random for long periods of time. This is reflected in its regret bound, which is only non-trivial after $T\gg k^{3}$, whereas the UCB algorithm (Auer et al., 2002) achieves non-trivial regret after $T=O(k)$ rounds. However, our lower bound in Section 4 shows that any fair algorithm must suffer constant per-round regret for $T\gg k^{3}$ rounds on some instances.

Initially, the active set contains all arms. The active set of arms at each subsequent round is defined to be the set of arms that are chained to the arm with highest upper confidence bound at the previous round. The algorithm can be confident that arms that have become unchained to the arm with the highest upper confidence bound at any round have means that are lower than the means of any chained arms, and hence such arms can be safely removed from the active set, never to be played again. This has the useful property that the active set of arms can only shrink: at any round $t$, $S_{t}\subseteq S_{t-1}$; see Figure 1 for an example of active set evolution over time.

We first observe that with probability $1-\delta$, all of the confidence intervals maintained by FairBandits $(\delta)$ contain the true means of their respective arms over all rounds. We prove this claim, along with all other claims in this section without proofs, in Appendix A.

The fairness of FairBandits follows almost immediately from this guarantee.

Next, we upper bound the regret of FairBandits.

If $\delta<1/\sqrt{T}$, then FairBandits has regret

Before proving Theorem 2, we highlight two points. First, this bound becomes non-trivial (i.e. the average per-round regret is $\ll 1$) for $T=\Omega(k^{3})$. As we show in the next section, it is not possible to improve on this. Second, the bound may appear to have suboptimal dependence on $T$ when compared to unconstrained regret bounds (where the dependence on $T$ is often described as logarithmic). However, it is known that $\Omega\left(\sqrt{kT}\right)$ regret is necessary even in the unrestricted setting (without fairness) if one does not make data-specific assumptions on an instance (Bubeck and Cesa-Bianchi, 2012) (e.g. that there is a lower bound on the gap between the best and second best arm). It would be possible to state a logarithmic dependence on $T$ in our setting as well while making assumptions on the gaps between arms, but since our fairness constraint manifests itself as a cost that depends on $k$, we choose for clarity to avoid such assumptions. Without such assumptions, our dependence on $T$ is also optimal.

We now prove Theorem 2. Lemma 2 upper bounds the probability any arm $i$ active in round $t$ has been pulled substantially fewer times than its expectation, i.e. $n_{i}^{t}\ll\frac{t}{k}$. Lemma 3 upper bounds the width of any confidence interval used by FairBandits in round $t$ by $\eta(t)$, conditioned on $i$ being pulled the number of times guaranteed by Lemma 2. Finally, we stitch this together to prove Theorem 2 by upper bounding the total regret incurred for $T$ rounds by noticing that the regret of any arm active in round $t$ is at most $k\eta(t)$.

We begin by lower bounding the probability that any arm active in round $t$ has been pulled substantially fewer times than its expectation.

With probability at least $1-\frac{\delta}{2t^{2}}$,

for all $i\in S^{t}$ (for all active arms in round $t$).

We now use this lower bound on the number of pulls of active arm $i$ in round $t$ to upper-bound $\eta(t)$, an upper bound on the confidence interval width FairBandits uses for any active arm $i$ in round $t$.

Consider any round $t$ and any arm $i\in S^{t}$. Condition on $n_{i}^{t}\geq\frac{t}{k}-\sqrt{\frac{t\ln(\frac{2kt^{2}}{\delta})}{2}}$. Then,

Finally, we prove the bound on the total regret of the algorithm, using the bound on the width of any active arm’s confidence interval in round $t$ provided by Lemma 3.

We further condition on the event that for all $j,t$,

which holds with probability at least $1-\frac{\pi\delta}{2}$ by Lemma 2 and a union bound over all times $t$. This implies that, for all rounds $t$, for every active arm $j\in S^{t}$, Lemma 3 applies, and therefore

Finally, we upper-bound the per-round regret of pulling any active arm $i\in S^{t}$ at round $t$. Since $i_{*}$ is active, any $i\in S^{t}$ is chained to arm $i_{*}$. Since all active arms have confidence interval width at most $\eta(t)$ and $i$ must be chained using at most $k$ arms’ confidence intervals, we have that

where this bound is derived in Appendix A.1. ∎

Fair Classic Stochastic Bandits: A Lower Bound

We now show that the regret bound for FairBandits has an optimal dependence on $k$: no fair algorithm has diminishing regret before $T=\Omega(k^{3})$ rounds. All missing proofs are in Appendix B. The main result of this section is the following.

There is a distribution $P$ over $k$-arm instances of the stochastic multi-armed bandit problem such that any fair algorithm run on $P$ experiences constant per-round regret for at least

Despite the fact that regret is defined in a prior-free way, the proof of Theorem 3 proceeds via Bayesian reasoning. We construct a family of lower bound instances such that arms have payoffs drawn from Bernoulli distributions, denoted $B(\mu)$ for mean $\mu$. So, to specify a problem instance, it suffices to specify a mean for each of $k$ arms: $\mu_{1},\ldots,\mu_{k}$. The proof formalizes the following outline.

We define an instance distribution $P=P_{1}\times\ldots\times P_{k}$ over means $\mu_{i}$ (Definition 3). $P$ will have two important properties. First, we will draw means from $P$ such that for any $i\in[k-1]$, $\mu_{i}=\mu_{i+1}$ with probability at least $1/4$. Second, for any realization of means drawn from $P$, if an algorithm plays uniformly at random over $[k]$, it will suffer constant per-round regret.

We treat $P_{i}$ as a prior distribution over mean $\mu_{i}$, and analyze the posterior distribution $P_{i}(r^{1}_{i},,\ldots,r^{t}_{i})$ over means that results after applying Bayes’ rule to the payoff observations $r^{1}_{i},\ldots,r^{t}_{i}$ made by the algorithm. Bayes’ rule implies (Lemma 4) the joint distribution over rewards and means drawn from $P$ is identical to the distribution which first draws means according to $P$, then draws rewards conditioned on those means, and finally resamples the means from the posterior distribution on means. Thus, we can reason about fairness (a frequentist quantity) by analyzing the Bayesian posterior distribution on means conditioned on the observed rewards.

We begin by describing our distribution over instances. Each arm $i$’s payoff distribution will be Bernoulli with mean $\mu_{i}\sim P_{i}$ independently of each other arm.

For each arm $i$, $\mu_{i}$ is distributed according to the distribution with the following probability mass function:

Let $P=\prod_{i}P_{i}$ denote the joint distribution on arms’ expected payoffs.

We treat $P$ as a prior distribution over instances, and analyze the posterior distribution on instances given the realized rewards. Lemma 4 justifies this reasoning.

Consider the following two experiments: In the first, let $\mu_{i}\sim P_{i}$ and $r^{1}_{i},\ldots,r^{t}_{i}\sim B(\mu_{i})$, and $W$ denote the joint distribution on $(\mu_{i},r^{1}_{i},\ldots,r^{t}_{i})$. In the second, let $\mu_{i}\sim P_{i}$, and $r^{1}_{i},\ldots,r^{t}_{i}\sim B(\mu_{i})$, and then re-draw the mean $\mu^{\prime}_{i}\sim P_{i}(r^{1}_{i},\ldots,r^{t}_{i})$ from its posterior distribution given the rewards. Let $(\mu^{\prime}_{i},r^{1}_{i},\ldots,r^{t}_{i})\sim W^{\prime}$. Then, $W$ and $W^{\prime}$ are identical distributions.

We will say $h^{t}$ $\delta$-distinguishes arm $i$ for $\mathcal{A}$ if, for some $\alpha\in$,

The next lemma shows that if no arm is $\sqrt{\delta}$-distinguished by a history, all pairs of arms $i,i+1$ have posterior probability strictly greater than $\delta$ of having equal means.

Suppose $\mathcal{A}$ has history $h^{t}$, and that $h^{t}$ does not $\sqrt{\delta}$-distinguish any arm $i$. Then, for all arms $i,i+1$,

Now, we prove that for any fair algorithm, with probability $\geq\tfrac{1}{2}$ over the draw of histories $h^{t}$, $h^{t}$ must $\sqrt{2\delta}$-distinguish some arm, or the algorithm must play uniformly across all $k$ arms conditioned on $h^{t}$.

Suppose an algorithm $\mathcal{A}$ is $\delta$-fair. Then:

We now lower-bound the number of observations from arm $i$ which are required to $\delta$-distinguish it.

Fix any $\delta<\frac{1}{8}$. Let $\mu_{i}\sim P_{i}$ as in Definition 3. Then, arm $i$ is $\sqrt{2\delta}$-distinguishable by $h^{t}$ only if $T_{i}=\Omega(k^{2}\ln\frac{1}{\delta})$, where $T_{i}=|\{t^{\prime}:h^{t^{\prime}}_{2}=i,t^{\prime}\leq t\}|$ is the number of times arm $i$ is played.

Write $p,p+\frac{1}{3k}$ to represent the two possible realizations that $\mu_{i}$ might take, when drawn from the distribution over instances given in Definition 3. Let $A$ represent the event that $\mu_{i}=p$ and $B$ the event that $\mu_{i}=p+\frac{1}{3k}$. Let $\delta^{\prime}=\sqrt{2\delta}$ throughout.

We now calculate under what conditions either (a) $X\leq\frac{\delta^{\prime}}{1-\delta^{\prime}}$, or (b) $X\geq\frac{1-\delta^{\prime}}{\delta^{\prime}}$. One of these must hold if $i$ is $\delta^{\prime}$-distinguished. Before we do so, we mention that a Chernoff bound implies that with probability $1-\delta^{\prime}$, for events $A$ and $B$, Equations 1 and 2, respectively:

since the mean of $m$ Bernoulli trials with mean $p$ ( or $p+\frac{1}{3k}$) is $mp$ (or $mp+\frac{m}{3k}$).

We begin by analyzing case (a), where $\delta^{\prime}=\sqrt{2\delta}<1/2$ implies

Taking logarithms on both sides, we have that

where the inequality follows from $\ln(1+x)\geq\frac{x}{x+1}$ for $x\in[-1,\infty]$. Then, this implies that

Multiplying both sides by $-1$, this implies that

Equation 1 implies $|3ks-3kmp-m|\leq m+3k\sqrt{2m\ln\frac{2}{\delta^{\prime}}}$, which with the previous line implies

Since $p,1-p\in[1/3,2/3]$ and $\delta^{\prime}=\sqrt{2\delta}$, solving for $m$ implies that $m=\Omega(k^{2}\ln\frac{1}{\delta^{\prime}})$.

where we used the fact that $1+x\leq e^{x}$ for all $x$. Taking logarithms, this will imply that

whose last inequality comes the range of $p$. Combining this inequality with Equation 2, this implies

and solving for $m$ and substituting for $\delta^{\prime}$ gives that $m=\Omega(k^{2}\ln\frac{1}{\delta})$.

Thus, if either $X\geq\frac{1-\delta^{\prime}}{\delta^{\prime}}$ or $X\leq\frac{\delta^{\prime}}{1-\delta^{\prime}}$, it must be that $m=\Omega(k^{2}\ln\frac{1}{\delta})$. ∎

We now have the tools in hand to prove Theorem 3.

Assume $\mathcal{A}$ is some $\delta$-fair algorithm where $\delta<1/8$. Fix $T$; we claim that with probability at least $\frac{1}{2}$, for any $t=o(k^{3}\ln\frac{1}{\delta})$, $t\leq T$, $\pi^{t}_{j|h^{t}}=\frac{1}{k}$ for all $j$. Since the payoff for uniformly random play is $\leq\frac{1}{2}+\frac{1}{k}$, while the best arm has payoff $\geq\frac{2}{3}$, in any round $t$ where $\pi^{t}_{i|h^{t}}=\pi^{t}_{i^{\prime}|h^{t}}$ for all $i,i^{\prime}\in[k]$, the algorithm suffers $\Omega(1)$ regret in that round.

Lemma 6 implies that, with probability at least $\frac{1}{2}$ over the distribution over histories $h^{t}$, either (a) $\pi^{t^{\prime}}_{i|h^{t^{\prime}}}=\pi^{t^{\prime}}_{i^{\prime}|h^{t^{\prime}}}$ for all $i,i^{\prime}\in[k],t^{\prime}\leq t$ or (b) $h^{t}$ must $\sqrt{2\delta}$-distinguish some arm $i$. Case $(a)$ implies our claim. In case (b), Lemma 7 states than an arm $i$ is $\sqrt{2\delta}$-distinguishable only if $T_{i}=\Omega(k^{2}\ln\frac{1}{\delta})$. We now argue that unless $t=\Omega(k^{3}\ln\frac{1}{\delta})$, $T_{i}=o(k^{2}\ln\frac{1}{\delta})$, which will imply our claim for case $(b)$.

Fix some $i,t$. We lower-bound $t$ for which, with probability at least $1-\frac{\delta^{\prime}}{k}$ over histories $h^{t}$, it will be the case that $n_{i}^{t}\geq c\cdot k^{2}\ln\frac{1}{\delta}$ when $\pi^{t^{\prime}}_{i|h^{t^{\prime}}}=\pi^{t^{\prime}}_{i^{\prime}|h^{t^{\prime}}}$ for all $i,i^{\prime}\in[k],t^{\prime}\leq t$. Let $X_{1},\ldots,X_{t}$ be indicator variables of arm $i$ being played in round $t^{\prime}\leq t$. Note that for all $t^{\prime}\leq t$, $E[X_{t^{\prime}}]=\frac{1}{k}$, since in all rounds prior to $t$, we have all arms are played with equal probability. For any $\epsilon\in$, as $n_{i}^{t^{\prime}}$ are nondecreasing in $t^{\prime}$, an additive Chernoff bound implies

If $k\sqrt{\frac{t\ln\frac{2k}{\delta^{\prime}}}{2}}\leq\frac{c}{2}\cdot k^{3}\ln\frac{1}{\delta}$, then $t\geq\frac{c}{2}\cdot k^{3}\ln\frac{1}{\delta}$; if not, then $t\geq\frac{\frac{c^{2}}{2}k^{4}\ln^{2}\frac{1}{\delta}}{\ln\frac{2k}{\delta^{\prime}}}$. Thus, $n_{i}^{t}<c\cdot k^{2}\ln\frac{1}{\delta}$ with probability $1-\delta^{\prime}$ for all $i$ unless $t\geq\min\left(\frac{c}{2}\cdot k^{3}\ln\frac{1}{\delta},\frac{\frac{c^{2}}{2}k^{4}\ln^{2}\frac{1}{\delta}}{\ln\frac{2k}{\delta^{\prime}}}\right)=\Omega(k^{3}\ln\frac{1}{\delta})$ for $\delta^{\prime}\in[\frac{1}{2},1]$. ∎

KWIK Learnability Implies Fair Bandit Learnability

In this section, we show if a class of functions is KWIK learnable, then there is a fair algorithm for learning the same class of functions in the contextual bandit setting, with a regret bound polynomially related to the function class’ KWIK bound. Intuitively, KWIK-learnability of a class of functions guarantees we can learn the function’s behavior to a high degree of accuracy with a high degree of confidence. As fairness constrains an algorithm most before the algorithm has determined the payoff functions’ behavior accurately, this guarantee enables us to learn fairly without incurring much additional regret. Formally, we prove the following polynomial relationship.

For an instance of the contextual multi-armed bandit problem where $f_{j}\in C$ for all $j\in[k]$, if $C$ is $(\epsilon,\delta)$-KWIK learnable with bound $m(\epsilon,\delta)$, KWIKToFair $(\delta,T)$ is $\delta$-fair and achieves regret bound:

for $\delta\leq\frac{1}{\sqrt{T}}$ where $\epsilon^{*}=\arg\min_{\epsilon}(\max(\epsilon\cdot T,k\cdot m(\epsilon,\frac{\min(\delta,1/T)}{kT^{2}}))).$

We condition on both (a) and (b) holding for all arms $i$ and rounds $t$ from Lemma 8, which occur with probability $1-\delta$ for all arms and all times $t$. Therefore, we proceed by conditioning on the event that for all arms $i$ and all rounds $t$, if $L_{i}=s^{t}_{i}$ for $s^{t}_{i}\neq\bot$ then $|s^{t}_{i}-f_{i}(x^{t}_{i})|\leq\epsilon^{*}$. Having done so, there are two possibilities for each round $t$.

In case 1, for each $i$ we have that $L_{i}(x^{t}_{i})=s^{t}_{i}\neq\bot$. By the condition above, for any arms $i$ and $j$, $f_{i}(x_{i}^{t})\geq f_{j}(x_{j}^{t})$ implies that $s^{t}_{i}+\epsilon^{*}\geq s^{t}_{j}-\epsilon^{*}$. Since in this case no learner outputs $\bot$, arm $j$ chains to the top arm only if arm $i$ does. Therefore $\pi_{i\mid h}^{t}\geq\pi_{j\mid h}^{t}$. In case 2, there exists some $i$ such that $L_{i}(x^{t}_{i})=\bot$. Then we choose uniformly at random across all arms, so $\pi_{i\mid h}^{t}=\pi_{j\mid h}^{t}$ for all $i$ and $j$.

Thus, with probability at least $1-\delta$, for each round $t$, $f_{i}(x_{i}^{t})\geq f_{j}(x_{j}^{t})$ implies that $\pi_{i\mid h}^{t}\geq\pi_{j\mid h}^{t}$. ∎

We now use the KWIK bounds of the KWIK learners to upper-bound the regret of KWIKToFair$(\delta,T)$.

KWIKToFair$(\delta,T)$ achieves regret $O(\max(k^{2}\cdot m(\epsilon^{*},\delta^{*}),k^{3}\ln\frac{Tk}{\delta}))$.

We first condition on the event that both (a) and (b) from Lemma 8 hold for all $t,i$, which holds with probability $1-\min(\delta,\frac{1}{T})$, and bound the regret when they both hold. Choose an arbitrary round $t$ in the execution of KWIKToFair$(\delta,T)$. As above, there are two cases. In the first case, $L_{i}(x^{t}_{i})=s^{t}_{i}\neq\bot$ for all $i$ and we choose uniformly at random from the arms chained by $\epsilon^{*}$-intervals to the arm with the highest prediction. Since we have conditioned on the event that all KWIK learners are correct, $i^{*}\in S^{t}$. Furthermore, for any $i,j\in S^{t}$, we have that $|s^{t}_{i}-s^{t}_{j}|\leq 2k\epsilon^{*}$, and in particular that $|s^{t}_{i}-s^{t}_{i^{*}}|\leq 2k\epsilon^{*}$. Thus, the regret is at most $2k\epsilon^{*}$ in such a round. In the second case some arm outputs $\bot$, so we choose randomly from all $k$ arms, and the worst-case regret is 1. Thus, the total regret will be at most $2k\epsilon^{*}T+n+\delta T$ where $n$ is the number of rounds in which some $L_{i}$ outputs $\bot$.

We now upper bound $n_{i}$, the number of rounds in which arm $i$ outputs $\bot$. Fix some arm $i$ which outputs $\bot$ in $n_{i}$ rounds. Arm $i$ is played and therefore receives feedback every time it outputs $\bot$ with probability at least $1/k$. Thus, using a Chernoff bound, with probability $1-\delta^{\prime}$, arm $i$ receives feedback for $n_{i}$ outputs of $\bot$ in at least $\frac{n_{i}}{k}-\sqrt{2n_{i}\ln\frac{2}{\delta^{\prime}}}$ rounds. $L_{i}$ has the guarantee that there can be at most $m(\epsilon^{*},\delta^{*})$ many such rounds (in which it outputs $\bot$ and receives feedback). Thus,

If $n_{i}\geq ck\cdot m(\epsilon^{*},\delta^{*})$, this implies

We now analyze cases in which (1) $k\ln\frac{2}{\delta^{\prime}}\leq m(\epsilon^{*},\delta^{*})$ and (2) $k\ln\frac{2}{\delta^{\prime}}>m(\epsilon^{*},\delta^{*})$.

For $c>4$, this leads to contradiction. Thus, in this case, if we set $\delta^{\prime}=\frac{\delta}{k}$, we know that with probability $1-\delta$, $n_{i}\leq 4k\cdot m(\epsilon^{*},\delta^{*})$ which summing up over all $i$ implies $\sum_{i}n_{i}\leq 4k^{2}\cdot m(\epsilon^{*},\delta^{*})$, as desired.

which solving for $n_{i}$ implies that $n_{i}=O(k^{2}\ln\frac{1}{\delta^{\prime}})$, so $\sum_{i}n_{i}=O(k^{3}\ln\frac{k}{\delta})$ by setting $\delta^{\prime}=\frac{\delta}{k}$ and taking a union bound. Thus, there are at most $n=O(\max(k^{2}\cdot m(\epsilon,\delta^{*}),k^{3}\ln\frac{k}{\delta}))$ rounds in expectation during the execution of KWIKToFair$(\delta,T)$ in which some arm outputs $\bot$.

Combining both cases, the total regret incurred by KWIKToFair$(\delta,T)$ across all $T$ rounds is

Our presentation of KWIKToFair$(\delta,T)$ has a known time horizon $T$. Its guarantees extend to the case in which $T$ is unknown via the standard “doubling trick” to prove Theorem 4 in Appendix C.

An important instance of the contextual bandit problem is the linear case, where $C$ consists of the set of all linear functions of bounded norm in $d$ dimensions. This captures the natural setting in which the rewards of each arm are governed by an underlying linear regression model on a $d$-dimensional real valued feature space. The linear case is well studied, and there are known KWIK algorithms (Strehl and Littman, 2008) for the set of linear functions $C$, which allows us via our reduction to give a fair contextual bandit algorithm for this setting with a polynomial regret bound.

Then, an application of Theorem 4 implies that KWIKToFair has a polynomial regret guarantee for the class of linear functions. This proof can be found in Appendix C.

Let $C$ and $\mathcal{X}$ be as in Lemma 10, and $f_{j}\in C$ for each $j\in[k]$. Then, KWIKToFair$(T,\delta)$ using the learner from (Strehl and Littman, 2008) has regret:

Fair Bandit Learnability Implies KWIK Learnability

In this section, we show how to use a fair, no-regret contextual bandit algorithm to construct a KWIK learning algorithm whose KWIK bound has logarithmic dependence on the number of rounds $T$. Intuitively, any fair algorithm which achieves low regret must both be able to find and exploit an optimal arm (since the algorithm is no-regret) and can only exploit that arm once it has a tight understanding of the qualities of all arms (since the algorithm is fair). Thus, any fair no-regret algorithm will ultimately have tight $(1-\delta)$-confidence about each arm’s reward function.

The condition that $C$ should contain a function that can take on values that are multiples of $\epsilon$ is for technical convenience; $C$ can always be augmented by adding a single such function.

We now argue that the numeric predictions of $\mathcal{B}$ are correct within an additive $\epsilon$. Let:

When $\mathcal{B}(x^{t})=y^{t}\in$, note that $|E^{t}|\leq 1$, else $\mathcal{B}$ would have output $\bot$.

In this section, we exploit the other direction of the equivalence we have proven between fair contextual bandit algorithms and KWIK learning algorithms to give a simple contextual bandit problem for which fairness imposes an exponential cost in its regret bound. This is in contrast to the case in which the underlying class of functions is linear, for which we gave fair contextual bandit algorithms with regret bounds within a polynomial factor of their unconstrained counterparts. In this problem, the context domain is the $d$-dimensional boolean hypercube: $\mathcal{X}=\{0,1\}^{d}$ – i.e. the context each round for each individual consists of $d$ boolean attributes. Our class of functions $C$ is the class of boolean conjunctions:

We first give a simple but unfair algorithm, ConjunctionBandit, for this problem which obtains a regret bound which is linear in $d$. It maintains a set of candidate variables $C_{j}^{*}$ for each conjunction $f_{j}$; this set shrinks across rounds, while always containing the true set of variables over which $f_{j}$ is defined. We denote the boolean value of variable $m$ in the context for arm $j$ in round $t$ by $x_{j,m}^{t}$.

The formal claim and proof that ConjunctionBandit achieves regret $R(T)=O(k^{2}d)$, as well as ConjunctionBandit’s formal description, can be found in Appendix C. ConjunctionBandit violates the fairness in every round $t$ in which it predicts 0 for arm $i$ but 1 for arm $j$ even though $f_{i}(x^{t})=f_{j}(x^{t})=1$, as $\pi^{t}_{i}{}=0<\frac{1}{k}<\pi^{t}_{j}{}$.

We now show that fair algorithms cannot guarantee subexponential regret in $d$. This relies upon a known lower bound for KWIK learning conjunctions (Li, 2009):

There exists a sequence of examples $(x^{1},\ldots,x^{2^{d}-1})$ such that for $\epsilon,\delta\leq 1/2$, every $(\epsilon,\delta)$-KWIK learning algorithm $\mathcal{B}$ for the class $C$ of conjunctions on $d$ variables must output $\bot$ for $x^{t}$ for each $t\in[2^{d}-1]$. Thus, $\mathcal{B}$ has a KWIK bound of at least $m(\epsilon,\delta)=\Omega(2^{d})$.

We then use the equivalence between fair algorithms and KWIK learning to translate this lower bound on $m(\epsilon,\delta)$ into a minimum worst case regret bound for fair algorithms on conjunctions. We modify Theorem 6 to yield the following lemma, proven in Appendix C.

Suppose $\mathcal{A}$ is a $\delta$-fair algorithm for the contextual bandit problem over the class $C$ of conjunctions on $d$ variables. If $\mathcal{A}$ has regret bound $R(T,\delta)$ then for $\delta^{\prime}=2T\delta$, FairToKWIK is an $(0,\delta^{\prime})$-KWIK algorithm for $C$ with KWIK bound $m(0,\delta^{\prime})=4R(m(0,\delta^{\prime}),\delta)$.

Lemma 11 then lets us lower-bound the worst case regret of fair learning algorithms on conjunctions.

For $\delta<\frac{1}{2T}$, any $\delta$-fair algorithm for the contextual bandit problem over the class $C$ of conjunctions on $d$ boolean variables has a worst case regret bound of $R(T)=\Omega(2^{d})$.

Let $T\leq 2^{d-1}$. We know then that if $\delta^{\prime}<1$, Lemma 11 guarantees the existence of a sequence of contexts $x^{1},\ldots,x^{T}$ for which any $(0,\delta^{\prime})$-KWIK algorithm has KWIK bound $m(T,0,\delta^{\prime})=T$.

Lemma 12 implies $4R(m(T,0,\delta^{\prime}),\delta)$ gives a KWIK bound of $m(T,0,\delta^{\prime})$ when $\delta^{\prime}=2T\delta$. Thus, if $\delta<\frac{1}{2T}$, then $\delta^{\prime}<1$ and so $R(m(T,0,\delta^{\prime}),\delta)=\frac{m(T,0,\delta^{\prime})}{4}=\frac{T}{4}$ . ∎

Together with the analysis of ConjunctionBandit, this demonstrates a strong separation between fair and unfair contextual bandit algorithms: when the underlying functions mapping contexts to payoffs are conjunctions on $d$ variables, there exist a sequence of contexts on which fair algorithms must incur regret exponential in $d$ while unfair algorithms can achieve regret linear in $d$.

References

Appendix A Missing Proofs for the Classic Stochastic Bandits Upper Bound

We begin by proving Lemma 1, used in Section 3 to prove the fairness of the FairBandits algorithm.

Choose an arbitrary arm $i$ and round $t$ and define indicator variables $X_{1},\ldots,X_{n_{i}(t)}$ where $X_{n}$ takes on the reward of pull $n$ of arm $i$. By a Chernoff bound, for any $a\geq 0$,

In particular for $a=\sqrt{n_{i}^{t}\ln((\pi t)^{2}/3\delta)/2}$, it is the case that

By a union bound over all rounds $t$, the probability of any true mean ever falling outside of its confidence interval is at most $\delta(\frac{6}{\pi^{2}}\sum_{t=1}^{\infty}\frac{1}{t^{2}})=\delta$. ∎

Next, we prove Lemma 2, which we used in Section 3 to bound the regret of FairBandits in Theorem 2.

Setting $\epsilon t=\sqrt{\frac{t\ln(\frac{2t^{2}k}{\delta})}{2}}$, this bound becomes

as desired. Then, taking a union bound over all active arms of which there are at most $k$, the claim follows. ∎

where the final step follows from $\delta\leq\frac{1}{\sqrt{T}}$.

Appendix B Missing Proofs for the Classic Stochastic Bandits Lower Bound

All lemmas in this section are used in Section 4 to prove the fair lower bound in Theorem 3. The first, Lemma 4, lets us analyze distributions over payoffs.

Let $R_{i}$ represent the joint distribution on rewards for either experiment: in both cases, the joint distribution on rewards is identical, since the process which generates them is the same.

We will use the notation $m,d^{1},\ldots,d^{t}$ to represent some fixed realization of the random variables $\mu_{i},r^{1}_{i},\ldots,r^{t}_{i}$ and $\mu^{\prime}_{i},r^{1}_{i},\ldots,r^{t}_{i}$. In particular, it suffices to show that

The first experiment which generates $(\mu_{i},r^{1}_{i},\ldots,r^{t}_{i})$ according to $W$ has probability mass on this particular value of its random variables:

The second experiment has joint probability:

where equality follows from Bayes’ Rule. ∎

Next, we prove Lemma 5, used to reason about distinguishing between arms.

Since neither $i$ nor $i+1$ is $\sqrt{\delta}$-distinguished by $h^{t}$, for any $\alpha_{i}\in\{\frac{1}{3}+\frac{i}{3k},\frac{1}{3}+\frac{i+1}{3k}\},\alpha_{i+1}\in\{\frac{1}{3}+\frac{i+1}{3k},\frac{1}{3}+\frac{i+2}{3k}\}$, the posterior probability of $\mu_{i}=\alpha_{i}$ is less than $1-\sqrt{\delta}$, and in particular for $\alpha=\frac{1}{3}+\frac{i+1}{3k}$, it must be the case that

Finally, we prove Lemma 6, which lets us reason about how fair algorithm choices depend on histories.

We will define a set of histories which cause $\mathcal{A}$ to play some pair of arms $i$ and $i+1$ with different probabilities when $\mu_{i}=\mu_{i+1}$. Define the set $\textrm{unfair}(\mathcal{A},\mu)$ such that $h^{t}\in\textrm{unfair}(\mathcal{A},\mu)$ if there exist $i\in[k-1],t^{\prime}\in[t]$ such that $\mu_{i}=\mu_{i+1}$ but $\pi^{t^{\prime}}_{i|h^{t^{\prime}}}\neq\pi^{t^{\prime}}_{i+1|h^{t^{\prime}}}$.

where the first equality comes from the fact that $h^{t}$ is a history for which $\pi^{t^{\prime}}_{i|h^{t}}\neq\pi^{t^{\prime}}_{i+1|h^{t}}$ and the second equality from the definition of the set unfair.

We will show that Equation 4 cannot hold with probability more than $\frac{1}{2}$ over the draw of $\mu,h^{t}$ from the underlying distribution, or else $A$ would not satisfy $\delta$-fairness. Since $A$ is $\delta$-fair, for any fixed $\mu$

and therefore for any distribution $P$ over $\mu$ that

Thus, with probability at least $\frac{1}{2}$ over the distribution over histories and means,

However, Equation 4 shows this does not hold for any $h^{t}$ which does not $\sqrt{2\delta}$-distinguish any arm but for which $\pi^{t^{\prime}}_{i|h^{t^{\prime}}}\neq\frac{1}{k}$ for some $i\in[k],t^{\prime}\leq t$. Thus, for at least $\frac{1}{2}$ of all probability mass over histories, either $\pi^{t^{\prime}}_{i|h^{t^{\prime}}}=\frac{1}{k}$ for all $i,t^{\prime}\leq t$, or $h^{t}$ must $\sqrt{2\delta}$-distinguish some arm. ∎

Appendix C Missing Proofs for the Contextual Bandit Setting

We begin by proving two results related to KWIKToFair. The first, Lemma 8, was used in Section 5 to prove that KWIKToFair is $\delta$-fair in Theorem 5.

We proceed to Theorem 4, used in Section 5 to construct a $\delta$-fair algorithm with quantified regret from KWIK learners.

We use repeated calls to KWIKToFair $(\delta,T)$ to run for an indefinite number of rounds. Specifically, we will make calls $E=1,2,\ldots$ to KWIKToFair $(6\delta/\pi(\log(T)^{2},2^{E})$. We will refer to each such call to KWIKToFair by its epoch $E$. By Lemma 8, each epoch $E$ is $6\delta/\pi E^{2}k$-fair, i.e. has a $6\delta/\pi E^{2}k$ probability of violating fairness. Therefore by a union bound across epochs, the probability of ever violating fairness through repeated calls to KWIKToFair is bounded above by $\sum_{E=1}^{\infty}\frac{6\delta}{(\pi E)^{2}}=\frac{6\delta}{\pi^{2}}\sum_{E=1}^{\infty}\frac{1}{E^{2}}=\delta$, so the overall algorithm is $\delta$-fair.

Next, by Lemma 9 each epoch $E$ contributes at most regret $3\cdot 2^{E}k\epsilon^{*}_{E}$ where $\epsilon^{*}_{E}$ denotes the value of $\epsilon^{*}$ used in epoch $E$, i.e. $\epsilon^{*}_{E}$ satisfying $\epsilon^{*}_{E}=k\cdot m(\epsilon^{*}_{E},6\delta/\pi E^{2},2^{E})$. Then since each epoch $E$ covers $2^{E}$ rounds, through round $T$ the algorithm has used fewer than $\log(T)$ epochs, and by the doubling trick achieves regret $R(T)<\sum_{E=1}^{\log(T)}3\cdot 2^{E}k\epsilon^{*}_{E}=O(Tk\epsilon^{*})=O(k^{2}\cdot m(\epsilon^{*},\delta^{*}))$. ∎

Next, we address the special subcase of KWIKToFair for linear functions outlined in Corollary 1.

This brings us to the formal algorithm description of ConjunctionBandit and its corresponding regret bound, used in Section 6.1 as an example of an unfair learning algorithm for conjunctions.

We can now upper bound the regret achieved by ConjunctionBandit.

ConjunctionBandit achieves regret $R(T)=O(k^{2}d)$.

First, we claim that for every $j$, for the duration of the algorithm, that $C_{j}\subseteq C_{j}^{*}$, where $C_{j}$ is the true set of variables corresponding to $f_{j}$. This holds at initialization: $C_{j}\subseteq[d]=C_{j}^{*}$. Suppose the claim holds prior to round $t$: if $C^{*}_{j}$ is updated in this round, then $f_{j}(x^{t}_{j})=1\Rightarrow\forall m\in[d]:x^{t}_{j,m}=0,m\notin C_{j}$. Thus, $C^{*}_{j}=C^{*}_{j}\setminus\{m:x^{t}_{j,m}=0\}=C^{*}_{j}\setminus\{m:x^{t}_{j,m}=0\cap m\notin C_{j}\}\supset C_{j}$.

Therefore, the algorithm never makes false positive mistakes: in any round $t$, $j\in S^{t}\Rightarrow f_{j}(x_{j}^{t})=1$. Therefore ConjunctionBandit only accumulates regret in rounds where it makes false negative mistakes by predicting that all arms have reward 0 when some arm has reward 1.

Finally, we prove Lemma 12, which we used in Section 6.1 to translate between fair and KWIK learning on conjunctions.

We mimic the structure of the proof of Theorem 6, once again using FairToKWIK to construct a KWIK learner $\mathcal{B}$ by running the given fair algorithm $\mathcal{A}$ on a constructed bandit instance for each context $x^{t}$.

It remains to upper bound $m(\epsilon,\delta)$. Any round where $\mathcal{B}$ outputs $\perp$ means a choice between two contexts, one of which has a difference of 1 between arms. It follows that choosing randomly between both arms and contexts incurs expected regret $1/4$. Therefore $\frac{m(\epsilon,\delta)}{4}<R(m(\epsilon,\delta),\delta^{*},d)=R(m(\epsilon,\delta),\frac{\delta}{2T},d)$. ∎