Calibrated Fairness in Bandits

By Yang Liu, Goran Radanovic, Christos Dimitrakakis, Debmalya Mandal, David C. Parkes. 2017

101 citations recorded by the source corpus.

We study fairness within the stochastic, \emph{multi-armed bandit} (MAB) decision making framework. We adapt the fairness framework of"treating similar individuals similarly"to this setting. Here, an `individual' corresponds to an arm and two arms are `similar' if they have a similar quality distribution. First, we adopt a {\em smoothness constraint} that if two arms have a similar quality distribution then the probability of selecting each arm should be similar. In addition, we define the {\em fairness regret}, which corresponds to the degree to which an algorithm is not calibrated, where perfect calibration requires that the probability of selecting an arm is equal to the probability with which the arm has the best quality realization. We show that a variation on Thompson sampling satisfies smooth fairness for total variation distance, and give an $\tilde{O}((kT)^{2/3})$ bound on fairness regret. This complements prior work, which protects an on-average better arm from being less favored. We also explain how to extend our algorithm to the dueling bandit setting.

Subfields: General Decision Sciences, Management Science and Operations Research, AI Ethics, Fairness & Society, Game & Decision Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In General Decision Sciences

In Management Science and Operations Research

In AI Ethics, Fairness & Society

In Game & Decision Theory

Citations in the corpus

Beyond Individual and Group Fairness (2020, background): “…also studies of the problem of fair selection [Kearns et al., 2017, Kleinberg and Raghavan, 2018], online learning and multi-armed bandit problems [Liu et al., 2017, Joseph et al., 2018], in particular stochastic and contextual bandits [Joseph et al., 2016, Gillen et al., 2018, Gupta and Kamble,…”
Prediction-Based Decisions and Fairness: A Catalogue of Choices, Assumptions, and Definitions (2018, background): “[112] consider a bandits setup where at each round, one person arrives from each group at random, and one person is hired per round (based only on their group).”
The Frontiers of Fairness in Machine Learning (2018, background): “There is also some work on fairness in machine learning in other settings — for example, ranking [YS17, CSV17], selection [KRW17, KR18], personalization [CV17], bandit learning [JKM + 18, LRD + 17], human-classiﬁer hybrid decision systems [MPZ17], and reinforcement learning [JJK + 17, DTB17].”
Online Learning with an Unknown Fairness Metric (2018, methodology): “a reduction to an online learning algorithm of Lobel et al. [2017], how to simultaneously obtain a logarithmic regret bound and a logarithmic (in T ) number of fairness violations.”
Equal Opportunity in Online Classification with Partial Feedback (2019, methodology): “Second, fair online classiﬁcation and regression in the contextual bandit setting [20, 21, 25].”
Privacy for All: Ensuring Fair and Equitable Privacy Protections (2018, background): “, 2008), fairness-aware online optimization (Liu et al., 2017), and postprocessing the learned model (Kamiran et al.”
Human Decision Making with Machine Assistance (2019, unknown): “…interested in the fairness of decisions completely delegated to machines [1, 4, 6, 31] and has extensively studied the distributive [26, 29, 39, 43, 49, 50, 56, 65, 73–75] and procedural [36, 38] fairness of machine decision-making [9, 14, 18, 19, 32, 46], as well as the feasibility of making fair…”
The Unfair Externalities of Exploration (2017, background): “Our work diﬀers from the line of research on meritocratic fairness in online learning [9, 10, 14], which considers the allocation of limited resources such as bank loans and requires that nobody should be passed over in favor of a less qualiﬁed applicant.”