  When an AI system interacts with multiple users, it frequently needs to make
allocation decisions. For instance, a virtual agent decides whom to pay
attention to in a group setting, or a factory robot selects a worker to deliver
a part. Demonstrating fairness in decision making is essential for such systems
to be broadly accepted. We introduce a Multi-Armed Bandit algorithm with
fairness constraints, where fairness is defined as a minimum rate that a task
or a resource is assigned to a user. The proposed algorithm uses contextual
information about the users and the task and makes no assumptions on how the
losses capturing the performance of different users are generated. We provide
theoretical guarantees of performance and empirical results from simulation and
an online user study. The results highlight the benefit of accounting for
contexts in fair decision making, especially when users perform better at some
contexts and worse at others.
