Fair Algorithms for Infinite and Contextual Bandits
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.
Code (0)
등록된 구현이 없습니다.
Tasks
FairnessMulti-Armed BanditsSimilar Papers 제목 키워드 기반
Adapting to Misspecification in Contextual Bandits
A major research direction in contextual bandits is to develop algorithms that are computationally efficient, yet support flexible, general-purpose function approximation. Algorithms based on modeling rewards have shown …
Multi-Armed BanditsregressionContextual bandits with concave rewards, and an application to fair ranking
We consider Contextual Bandits with Concave Rewards (CBCR), a multi-objective bandit problem where the desired trade-off between the rewards is defined by a known concave objective function, and the reward vector depends…
FairnessMulti-Armed BanditsFairness in Learning: Classic and Contextual Bandits
We introduce the study of fairness in multi-armed bandit problems. Our fairness definition can be interpreted as demanding that given a pool of applicants (say, for college admission or mortgages), a worse applicant is n…
FairnessMulti-Armed BanditsFairness of Exposure in Stochastic Bandits
Contextual bandit algorithms have become widely used for recommendation in online systems (e.g. marketplaces, music streaming, news), where they now wield substantial influence on which items get exposed to the users. Th…
FairnessMulti-Armed BanditsUpper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits
The principle of optimism in the face of uncertainty is one of the most widely used and successful ideas in multi-armed bandits and reinforcement learning. However, existing optimistic algorithms (primarily UCB and its v…
counterfactualMulti-Armed Banditsregression