Meritocratic Fairness for Infinite and Contextual Bandits
Abstract
We study fairness in linear bandit problems. Starting from the notion of meritocratic fairness introduced in~\citeJKMR16, 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.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The main notions of fairness applied in the application of bandits are meritocratic fairness (group agnostic), subjective fairness (emphasises fairness in each time period) and counterfactual fairness.
“The main notions of fairness applied in the application of bandits are meritocratic fairness [127,156,157] (group agnostic), subjective fairness [201] (emphasises fairness in each time period ) and counterfactual fairness (e.g.[146]).”
From Fairness in machine learning: A survey (2024) · cites this paper as [157]
Cites
Dwork, C., Hardt, M., Pitassi, T., Reingold, O., & Zemel, R. (2012) · Proceedings of the 3rd Innovations in Theoretical Computer Science Conference · doi:10.1145/2090236.2090255 · Cited by 3,501 · see citing works
Fair prediction with disparate impact: a study of bias in recidivism prediction instruments
Chouldechova, A. (2017) · Big Data · doi:10.1089/big.2016.0047 · Cited by 2,159 · see citing works
Using confidence bounds for exploitation-exploration trade-offs
Auer, P. L. (2003) · Cited by 1,219 · see citing works
Algorithmic Decision Making and the Cost of Fairness
Corbett-Davies, S., Pierson, E., Feller, A., Goel, S., & Huq, A. (2017) · Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining · doi:10.1145/3097983.3098095 · Cited by 1,149 · see citing works
Inherent trade-offs in the fair determination of risk scores
Kleinberg, J., Mullainathan, S., & Raghavan, M. (2017) · Schloss Dagstuhl – Leibniz-Zentrum für Informatik · doi:10.4230/lipics.itcs.2017.43 · Cited by 943 · cited 1× · see citing works
“Separately, Kleinberg, Mullainathan, and Raghavan (2017) and Chouldechova (2017) showed that different notions of group fairness may (and sometimes must) conflict with one another.”
BackgroundImproved Algorithms for Linear Stochastic Bandits
Abbasi-Yadkori, Y., Pál, D., & Szepesvári, C. (2011) · Cited by 854 · see citing works
Zafar, M. B., Valera, I., Gomez Rodriguez, M., & Gummadi, K. P. (2017) · Proceedings of the 26th International Conference on World Wide Web · doi:10.1145/3038912.3052660 · Cited by 632 · see citing works
(2008) · ScholarlyCommons (University of Pennsylvania) · Cited by 581 · see citing works
Anantharam, V., Varaiya, P. P., & Walrand, J. C. (1987) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1987.1104491 · Cited by 384 · see citing works
On the (im)possibility of fairness
Friedler, S. A., Scheidegger, C., & Venkatasubramanian, S. (2016) · arXiv · doi:10.48550/arxiv.1609.07236 · Cited by 247 · see citing works
Fairness in Learning: Classic and Contextual Bandits
Joseph, M., Kearns, M., Morgenstern, J., & Roth, A. (2016) · arXiv · doi:10.48550/arxiv.1605.07139 · Cited by 199 · see citing works
Self-citationReinforcement Learning with Immediate Rewards and Linear Hypotheses
Abe, N., Biermann, A., & Long, P. M. (2003) · Algorithmica · doi:10.1007/s00453-003-1038-1 · Cited by 133 · see citing works
Inherent Trade-Offs in Algorithmic Fairness
Kleinberg, J. (2018) · Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems · doi:10.1145/3219617.3219634 · Cited by 125 · see citing works
Flagged first, then by citations
1 of the 14 references couldn’t be matched to a known paper.
Cited by
Sorted by citations
Explainable AI: a review of machine learning interpretability methods
Linardatos, P., Papastefanopoulos, V., & Kotsiantis, S. (2020) · Entropy · doi:10.3390/e23010018 · Cited by 2,922 · see citing works
Fairness in machine learning: A survey
Caton, S., & Haas, C. (2024) · ACM Computing Surveys · doi:10.1145/3616865 · Cited by 646 · see citing works
A snapshot of the frontiers of fairness in machine learning
Chouldechova, A., & Roth, A. (2020) · Communications of the ACM · doi:10.1145/3376898 · Cited by 362 · see citing works
Self-citationBias Mitigation for Machine Learning Classifiers: A Comprehensive Survey
Hort, M., Chen, Z., Zhang, J. M., Harman, M., & Sarro, F. (2023) · ACM Journal on Responsible Computing · doi:10.1145/3631326 · Cited by 248 · see citing works
Fairness in Machine Learning: A Survey
Caton, S., & Haas, C. (2020) · arXiv · doi:10.48550/arxiv.2010.04053 · Cited by 646 · see citing works
Fairness in Learning-Based Sequential Decision Algorithms: A Survey
Zhang, X., & Liu, M. (2021) · Studies in systems, decision and control · doi:10.1007/978-3-030-60990-0_18 · Cited by 41 · see citing works
FaiRIR: Mitigating Exposure Bias From Related Item Recommendations in Two-Sided Platforms
Dash, A., Chakraborty, A., Ghosh, S., Mukherjee, A., & Gummadi, K. P. (2022) · IEEE Transactions on Computational Social Systems · doi:10.1109/tcss.2022.3164655 · Cited by 36 · see citing works
Achieving Counterfactual Fairness for Causal Bandit
Huang, W. Q., Zhang, L., & Wu, X. (2022) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v36i6.20653 · Cited by 19 · see citing works
Kernel dependence regularizers and Gaussian processes with applications to algorithmic fairness
Li, Z., Pérez-Suay, A., Camps‐Valls, G., & Sejdinović, D. (2022) · Pattern Recognition · doi:10.1016/j.patcog.2022.108922 · Cited by 15 · see citing works
Matchmaking Under Fairness Constraints: A Speed Dating Case Study
Paraschakis, D., & Nilsson, B. J. (2020) · Communications in computer and information science · doi:10.1007/978-3-030-52485-2_5 · Cited by 13 · see citing works
Equal Opportunity in Online Classification with Partial FeedbackPreprint
Bechavod, Y., Ligett, K., Roth, A., Waggoner, B., & Wu, Z. S. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1902.02242 · Cited by 13 · see citing works
Self-citationFairness of Exposure in Stochastic BanditsPreprint
Wang, L., Bai, Y., Sun, W., & Joachims, T. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2103.02735 · Cited by 13 · see citing works
Moment Multicalibration for Uncertainty EstimationPreprint
Jung, C., Lee, C., Pai, M. M., Roth, A., & Vohra, R. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2008.08037 · Cited by 12 · see citing works
Self-citationAchieving User-Side Fairness in Contextual Bandits
Huang, W. Q., Labille, K., Wu, X., Lee, D., & Heffernan, N. T. (2022) · Human-Centric Intelligent Systems · doi:10.1007/s44230-022-00008-w · Cited by 11 · see citing works
A Dynamic Decision-Making Framework Promoting Long-Term Fairness
Puranik, B., Madhow, U., & Pedarsani, R. (2022) · Proceedings of the AAAI/ACM Conference on AI Ethics and Society · doi:10.1145/3514094.3534127 · Cited by 8 · see citing works
Beyond Individual and Group Fairness
Awasthi, P., Cortes, C., Mansour, Y., & Mohri, M. (2020) · arXiv · doi:10.48550/arxiv.2008.09490 · Cited by 8 · see citing works
Precarity: Modeling the Long Term Effects of Compounded Decisions on Individual Instability
Nokhiz, P., Ruwanpathirana, A. K., Patwari, N., & Venkatasubramanian, S. (2021) · Proceedings of the AAAI/ACM Conference on AI Ethics and Society · doi:10.1145/3461702.3462529 · Cited by 7 · see citing works
Fairness-aware Bandit-based Recommendation
Huang, W. Q., Labille, K., Wu, X., Lee, D., & Heffernan, N. T. (2021) · IEEE International Conference on Big Data (BigData) · doi:10.1109/bigdata52589.2021.9671959 · Cited by 4 · see citing works
Long-Term Fairness in Sequential Multi-Agent Selection With Positive Reinforcement
Puranik, B., Guldogan, O., Madhow, U., & Pedarsani, R. (2024) · IEEE Journal on Selected Areas in Information Theory · doi:10.1109/jsait.2024.3416078 · Cited by 3 · see citing works
Chen, V., Williams, J., Leben, D., & Heidari, H. (2023) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v37i5.25737 · Cited by 3 · see citing works
Sociotechnical Aspects of Automated Recommendations: Algorithms, Ethics, and Evaluation
Paraschakis, D. (2020) · doi:10.24834/isbn.9789178770755 · Cited by 2 · see citing works
Ranked Prioritization of Groups in Combinatorial Bandit Allocation
Xu, L., Biswas, A., Fang, F., & Tambe, M. (2022) · International Joint Conference on Artificial Intelligence · doi:10.24963/ijcai.2022/723 · Cited by 1 · see citing works
Incorporating Expert Guidance in Epidemic ForecastingPreprint
Rodríguez, A., Adhikari, B., Ramakrishnan, N., & Prakash, B. A. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2101.10247
- Authors
- Joseph, M., Kearns, M., Morgenstern, J., Neel, S., & Roth, A.
- Affiliations
- University of Pennsylvania (US)
- Venue
- Proceedings of the 2018 AAAI/ACM Conference on AI, Ethics, and Society
- Publisher
- ACM
- Published
- 2018-12-27
- Pages
- 158-163
- ISSN
- 3065-8365 (ISSN-L)
- OpenAlex
- W2909878761
- Cited by
- 24
- References
- 14
- Citations by year
- 2024: 1 · 2023: 4 · 2022: 6 · 2021: 5 · 2020: 7 · 2019: 1
- FWCI
- 4.80
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- Proceedings of the AAAI/ACM Conference on AI Ethics and Society (publishedVersion)
- Topics
- Social Sciences › Decision Sciences › Management Science and Operations Research › Advanced Bandit Algorithms Research
- Physical Sciences › Computer Science › Computer Networks and Communications › Optimization and Search Problems
- Social Sciences › Safety Research › Ethics and Social Impacts of AI
- Keywords
- linear bandits, contextual bandits, regret bounds, lower bounds, online learning
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review