Fair Algorithms for Infinite and Contextual Bandits
It addresses fairness for online decision-making systems, offering a more general and realistic framework, though it builds incrementally on prior work.
The paper tackles fairness in linear bandit problems by refining meritocratic fairness, achieving better performance guarantees with fewer assumptions on choices and selections, and extends this to infinite linear bandits with instance-dependent regret bounds and lower bounds showing necessity.
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.