Timezone: »
We introduce the study of fairness in multi-armed bandit problems. Our fairness definition demands that, given a pool of applicants, a worse applicant is never favored over a better one, despite a learning algorithm’s uncertainty over the true payoffs. In the classic stochastic bandits problem we provide a provably fair algorithm based on “chained” confidence intervals, and prove 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, providing a strong separation between fair and unfair learning that 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 vice versa. 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.
Author Information
Matthew Joseph (University of Pennsylvania)
Michael Kearns (University of Pennsylvania)
Michael Kearns is Professor and National Center Chair in the Computer and Information Science department at the University of Pennsylvania. His research interests include topics in machine learning, algorithmic game theory, social networks, and computational finance. Prior to joining the Penn faculty, he spent a decade at AT&T/Bell Labs, where he was head of AI Research. He is co-director of Penn’s Warren Center for Network and Data Sciences (warrencenter.upenn.edu), and founder of Penn’s Networked and Social Systems Engineering (NETS) undergraduate program (www.nets.upenn.edu). Kearns consults extensively in technology and finance, and is a Fellow of the Association for the Advancement of Artificial Intelligence and the American Academy of Arts and Sciences.
Jamie Morgenstern (University of Pennsylvania)
Aaron Roth (University of Pennsylvania)
More from the Same Authors
-
2021 : A Joint Exponential Mechanism for Differentially Private Top-k Set »
Andres Munoz Medina · Matthew Joseph · Jennifer Gillenwater · Monica Ribero Diaz -
2022 : Differentially Private Gradient Boosting on Linear Learners for Tabular Data »
Saeyoung Rho · Shuai Tang · Sergul Aydore · Michael Kearns · Aaron Roth · Yu-Xiang Wang · Steven Wu · Cedric Archambeau -
2023 Poster: Replicable Reinforcement Learning »
Eric Eaton · Marcel Hussing · Michael Kearns · Jessica Sorrell -
2023 Poster: Scalable Membership Inference Attacks via Quantile Regression »
Martin Bertran · Shuai Tang · Aaron Roth · Michael Kearns · Jamie Morgenstern · Steven Wu -
2022 Poster: Online Minimax Multiobjective Optimization: Multicalibeating and Other Applications »
Daniel Lee · Georgy Noarov · Mallesh Pai · Aaron Roth -
2022 Poster: Practical Adversarial Multivalid Conformal Prediction »
Osbert Bastani · Varun Gupta · Christopher Jung · Georgy Noarov · Ramya Ramalingam · Aaron Roth -
2022 Poster: Private Synthetic Data for Multitask Learning and Marginal Queries »
Giuseppe Vietri · Cedric Archambeau · Sergul Aydore · William Brown · Michael Kearns · Aaron Roth · Ankit Siva · Shuai Tang · Steven Wu -
2021 : Panel »
Oluwaseyi Feyisetan · Helen Nissenbaum · Aaron Roth · Christine Task -
2021 : Invited talk: Aaron Roth (UPenn / Amazon): Machine Unlearning. »
Aaron Roth -
2021 Poster: Adaptive Machine Unlearning »
Varun Gupta · Christopher Jung · Seth Neel · Aaron Roth · Saeed Sharifi-Malvajerdi · Chris Waites -
2020 : Invited Talk 7:Fair Portfolio Design »
Michael Kearns -
2020 : Keynote: Michael Kearns »
Michael Kearns -
2019 : Aaron Roth, "Average Individual Fairness" »
Aaron Roth -
2019 : Pan-Private Uniformity Testing »
Kareem Amin · Matthew Joseph -
2019 : Poster Session »
Clement Canonne · Kwang-Sung Jun · Seth Neel · Di Wang · Giuseppe Vietri · Liwei Song · Jonathan Lebensold · Huanyu Zhang · Lovedeep Gondara · Ang Li · FatemehSadat Mireshghallah · Jinshuo Dong · Anand D Sarwate · Antti Koskela · Joonas Jälkö · Matt Kusner · Dingfan Chen · Mi Jung Park · Ashwin Machanavajjhala · Jayashree Kalpathy-Cramer · · Vitaly Feldman · Andrew Tomkins · Hai Phan · Hossein Esfandiari · Mimansa Jaiswal · Mrinank Sharma · Jeff Druce · Casey Meehan · Zhengli Zhao · Hsiang Hsu · Davis Railsback · Abraham Flaxman · · Julius Adebayo · Aleksandra Korolova · Jiaming Xu · Naoise Holohan · Samyadeep Basu · Matthew Joseph · My Thai · Xiaoqian Yang · Ellen Vitercik · Michael Hutchinson · Chenghong Wang · Gregory Yauney · Yuchao Tao · Chao Jin · Si Kai Lee · Audra McMillan · Rauf Izmailov · Jiayi Guo · Siddharth Swaroop · Tribhuvanesh Orekondy · Hadi Esmaeilzadeh · Kevin Procopio · Alkis Polyzotis · Jafar Mohammadi · Nitin Agrawal -
2019 : Gaussian Differential Privacy »
Jinshuo Dong · Aaron Roth -
2019 : Invited talk #3 »
Aaron Roth -
2019 Poster: Average Individual Fairness: Algorithms, Generalization and Experiments »
Saeed Sharifi-Malvajerdi · Michael Kearns · Aaron Roth -
2019 Poster: Equal Opportunity in Online Classification with Partial Feedback »
Yahav Bechavod · Katrina Ligett · Aaron Roth · Bo Waggoner · Steven Wu -
2019 Oral: Average Individual Fairness: Algorithms, Generalization and Experiments »
Saeed Sharifi-Malvajerdi · Michael Kearns · Aaron Roth -
2019 Poster: Multi-Criteria Dimensionality Reduction with Applications to Fairness »
Uthaipon Tantipongpipat · Samira Samadi · Mohit Singh · Jamie Morgenstern · Santosh Vempala -
2019 Spotlight: Multi-Criteria Dimensionality Reduction with Applications to Fairness »
Uthaipon Tantipongpipat · Samira Samadi · Mohit Singh · Jamie Morgenstern · Santosh Vempala -
2019 Poster: Learning Auctions with Robust Incentive Guarantees »
Jacob Abernethy · Rachel Cummings · Bhuvesh Kumar · Sam Taggart · Jamie Morgenstern -
2019 Poster: Locally Private Gaussian Estimation »
Matthew Joseph · Janardhan Kulkarni · Jieming Mao · Steven Wu -
2018 : Invited Talk 3: Fairness in Allocation Problems »
Michael Kearns -
2018 Poster: Online Learning with an Unknown Fairness Metric »
Stephen Gillen · Christopher Jung · Michael Kearns · Aaron Roth -
2018 Poster: A Smoothed Analysis of the Greedy Algorithm for the Linear Contextual Bandit Problem »
Sampath Kannan · Jamie Morgenstern · Aaron Roth · Bo Waggoner · Zhiwei Steven Wu -
2018 Spotlight: A Smoothed Analysis of the Greedy Algorithm for the Linear Contextual Bandit Problem »
Sampath Kannan · Jamie Morgenstern · Aaron Roth · Bo Waggoner · Zhiwei Steven Wu -
2018 Poster: Local Differential Privacy for Evolving Data »
Matthew Joseph · Aaron Roth · Jonathan Ullman · Bo Waggoner -
2018 Spotlight: Local Differential Privacy for Evolving Data »
Matthew Joseph · Aaron Roth · Jonathan Ullman · Bo Waggoner -
2017 Poster: Accuracy First: Selecting a Differential Privacy Level for Accuracy Constrained ERM »
Katrina Ligett · Seth Neel · Aaron Roth · Bo Waggoner · Steven Wu -
2016 Workshop: Adaptive Data Analysis »
Vitaly Feldman · Aaditya Ramdas · Aaron Roth · Adam Smith -
2016 Poster: Privacy Odometers and Filters: Pay-as-you-Go Composition »
Ryan Rogers · Salil Vadhan · Aaron Roth · Jonathan Ullman -
2016 Poster: Learning from Rational Behavior: Predicting Solutions to Unknown Linear Programs »
Shahin Jabbari · Ryan Rogers · Aaron Roth · Steven Wu -
2015 Workshop: Adaptive Data Analysis »
Adam Smith · Aaron Roth · Vitaly Feldman · Moritz Hardt -
2015 Poster: Generalization in Adaptive Data Analysis and Holdout Reuse »
Cynthia Dwork · Vitaly Feldman · Moritz Hardt · Toni Pitassi · Omer Reingold · Aaron Roth -
2015 Poster: On the Pseudo-Dimension of Nearly Optimal Auctions »
Jamie Morgenstern · Tim Roughgarden -
2015 Spotlight: On the Pseudo-Dimension of Nearly Optimal Auctions »
Jamie Morgenstern · Tim Roughgarden -
2014 Workshop: NIPS Workshop on Transactional Machine Learning and E-Commerce »
David Parkes · David H Wolpert · Jennifer Wortman Vaughan · Jacob D Abernethy · Amos Storkey · Mark Reid · Ping Jin · Nihar Bhadresh Shah · Mehryar Mohri · Luis E Ortiz · Robin Hanson · Aaron Roth · Satyen Kale · Sebastien Lahaie -
2014 Invited Talk: Games, Networks, and People »
Michael Kearns -
2013 Poster: Marginals-to-Models Reducibility »
Tim Roughgarden · Michael Kearns -
2007 Spotlight: Privacy-Preserving Belief Propagation and Sampling »
Michael Kearns · Jinsong Tan · Jennifer Wortman Vaughan -
2007 Poster: Privacy-Preserving Belief Propagation and Sampling »
Michael Kearns · Jinsong Tan · Jennifer Wortman Vaughan -
2006 Poster: Learning from Multiple Sources »
Yacov Crammer · Michael Kearns · Jennifer Wortman Vaughan -
2006 Poster: A Small World Threshold for Economic Network Formation »
Eyal Even-Dar · Michael Kearns