Reproduce “Fairness in Learning: Classic and Contextual Bandits” on OpenResearch

About this paper

Matthew Joseph, Michael Kearns, Jamie Morgenstern, Aaron Roth

This research formalizes a definition of individual fairness for classic and contextual multi-armed bandit problems, demonstrating that ensuring fair treatment where objectively superior options are not disfavored due to learning uncertainty, imposes a quantifiable cost on an algorithm's learning efficiency. The study provides algorithms with regret bounds and theoretical separations, illustrating how fairness can lead to slower learning rates or even exponential regret depending on the problem structure.

Key insights

• Individual fairness, even when consistent with an optimal policy, fundamentally conflicts with the efficiency of *learning* that policy due to uncertainty, incurring a quantifiable cost in terms of regret.
• The cost of fairness varies significantly based on the underlying problem structure, ranging from a mild polynomial increase in regret for some function classes (e.g., linear bandits) to a severe exponential increase for others (e.g., conjunctions).
• The established equivalence between fair contextual bandit learning and KWIK learning provides a powerful framework for identifying function classes where fairness is tractable or intractable.

Summary by alphaXiv.