2016

Fair Algorithms for Infinite and Contextual Bandits

Joseph, Matthew, Kearns, Michael, Morgenstern, Jamie et al.

Understand

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.

Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays – part i: I.i.d. rewards
Venkatachalam Anantharam, Pravin Varaiya, and Jean Walrand · 1987
Earlier work this paper cites.
Using confidence bounds for exploitation-exploration trade-offs
Peter Auer · 2002
Earlier work this paper cites.
Reinforcement learning with immediate rewards and linear hypotheses
Naoki Abe, Alan W Biermann, and Philip M Long · 2003
Earlier work this paper cites.
Online convex optimization in the bandit setting: gradient descent without a gradient
Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan · 2005
Earlier work this paper cites.
Geometric random walks: a survey
Santosh Vempala · 2005
Earlier work this paper cites.
Hit-and-run from a corner
László Lovász and Santosh Vempala · 2006
Earlier work this paper cites.
Stochastic linear optimization under bandit feedback
Varsha Dani, Thomas P Hayes, and Sham M Kakade · 2008
Earlier work this paper cites.

Improved algorithms for linear stochastic bandits
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári · 2011
Cited alongside, same era.
Fairness through awareness
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel · 2012
Cited alongside, same era.
An introduction to matrix concentration inequalities
Joel A Tropp et al · 2015
Cited alongside, same era.
On the (im)possibility of fairness
Original
Sorelle A. Friedler, Carlos Scheidegger, and Suresh Venkatasubramanian · 2016
Cited alongside, same era.
Equality of opportunity in supervised learning
Original
Moritz Hardt, Eric Price, and Nathan Srebro · 2016
Cited alongside, same era.
Fairness in learning: Classic and contextual bandits
Matthew Joseph, Michael Kearns, Jamie H Morgenstern, and Aaron Roth · 2016
Cited alongside, same era.
Facet guessing for finding the m-best integral solutions of a linear program
Erik M Lindgren, Alexandros G Dimakis, and Adam Klivans · 2016
Cited alongside, same era.

Fairness in criminal justice risk assessments: The state of the art
Original
Richard Berk, Hoda Heidari, Shahin Jabbari, Michael Kearns, and Aaron Roth · 2017
Closest in time.
Fair prediction with disparate impact: A study of bias in recidivism prediction instruments
Original
Alexandra Chouldechova · 2017
Closest in time.
Algorithmic decision making and the cost of fairness
Original
Sam Corbett-Davies, Emma Pierson, Avi Feller, Sharad Goel, and Aziz Huq · 2017
Closest in time.
Inherent trade-offs in the fair determination of risk scores
J. Kleinberg, S. Mullainathan, and M. Raghavan · 2017
Closest in time.
Learning non-discriminatory predictors
Original
Blake Woodworth, Suriya Gunasekar, Mesrob I Ohannessian, and Nathan Srebro · 2017
Closest in time.
Fairness beyond disparate treatment and disparate impact: Learning classification without disparate mistreatment
Muhammad Bilal Zafar, Isabel Valera, Manuel Gomez Rodriguez, and Krishna P. Gummadi · 2017
Closest in time.

alphaXiv searches the wider corpus for related work and actual follow-ups.

alphaXiv is searching for related work…

Reading the bibliography…