Fair Algorithms for Infinite and Contextual Bandits

By Matthew Joseph, Michael Kearns, Jamie H. Morgenstern, Seth Neel, Aaron Roth. 2016

59 citations recorded by the source corpus.

We study fairness in linear bandit problems. Starting from the notion of meritocratic fairness introduced in Joseph et al. [2016], we carry out a more refined analysis of a more general problem, achieving better performance guarantees with fewer modelling assumptions on the number and structure of available choices as well as the number selected. We also analyze the previously-unstudied question of fairness in infinite linear bandit problems, obtaining instance-dependent regret upper bounds as well as lower bounds demonstrating that this instance-dependence is necessary. The result is a framework for meritocratic fairness in an online linear setting that is substantially more powerful, general, and realistic than the current state of the art.

Subfields: Computer Networks and Communications, Management Science and Operations Research, Reinforcement Learning

How researchers see this paper

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

In Computer Networks and Communications

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Measurement and Fairness (2019, background): “present a framework for “ensuring” individual fairness when using a computational system to decide who should receive some resource or opportunity [31, 32].”
Prediction-Based Decisions and Fairness: A Catalogue of Choices, Assumptions, and Definitions (2018, methodology): “The notion of “quality” in the contextual bandit setup [89, 88] is analogous to “true risk” in the rest of our”
Explanation in Human-AI Systems: A Literature Meta-Review, Synopsis of Key Ideas and Publications, and Bibliography for Explainable AI (2019, neutral): “These include: • Transparency (Bansal, Farhadi, and Parikh, 2014; Fallon and Blaha, 2018; Hayes and Shah, 2017; Wachter, Mittelstadt, and Russel, 2017), • Accountability (Adler, et al., 2018; Belotti and Edwards, 2001; Kroll et al, 2016), • Safety and privacy (Amodei, Olah, Steinhardt, Christiano, S”
On Fairness and Calibration (2017, background): “Fairness has also been applied to bandit problems in online learning settings [20, 21].”
A comparative study of fairness-enhancing interventions in machine learning (2018, neutral): “We do not consider interventions that focus on sequential or reinforcement learning such as Ensign et al. (2018a,b); Jabbari et al. (2017); Joseph et al. (2016b,a) Preprocessing algorithms The motivation behind preprocessing algorithms is the idea that training data is the cause of the…”
Individual Fairness in Hindsight (2018, background): “Liu et al. (2017) and Gillen et al. (2018) study the model of Joseph et al. (2016b) under different notions of individual fairness.”
Online Learning with an Unknown Fairness Metric (2018, background): “Joseph et al. [2016b] extend the work of Joseph et al. [2016a] to the setting in which the algorithm is faced with a continuum of options at each time step, and give improved bounds for the linear contextual bandit case.”
Fairness in Machine Learning: A Survey (2020, unknown): “Thus, bandit approaches frame the fairness problem as a stochastic multi-armed bandit framework, assigning either individuals to arms, or groups of “similar” individuals to arms, and fairness quality as a reward represented as regret [145, 189].”
Avoiding Resentment Via Monotonic Fairness (2019, background): ““Meritocratic fairness” [24] appears similar, but differs in that it ranks points based on the expected outcome for their attribute values rather than the actual attribute, i.”