Achieving Fairness in Stochastic Multi-armed Bandit Problem
We study an interesting variant of the stochastic multi-armed bandit problem, called the Fair-SMAB problem, where each arm is required to be pulled for at least a given fraction of the total available rounds. We investigate the interplay between learning and fairness in terms of a pre-specified vector denoting the fractions of guaranteed pulls. We define a fairness-aware regret, called r-Regret, that takes into account the above fairness constraints and naturally extends the conventional notion of regret. Our primary contribution is characterizing a class of Fair-SMAB algorithms by two parameters: the unfairness tolerance and learning algorithm used as a black-box. We provide a fairness guarantee for this class that holds uniformly over time irrespective of the choice of the learning algorithm. In particular, when the learning algorithm is UCB1, we show that our algorithm achieves O(log(T)) r-Regret. Finally, we evaluate the cost of fairness in terms of the conventional notion of regret.
Code (0)
등록된 구현이 없습니다.
Tasks
FairnessMulti-Armed BanditsSimilar Papers 제목 키워드 기반
Achieving Fairness in the Stochastic Multi-armed Bandit Problem
We study an interesting variant of the stochastic multi-armed bandit problem, called the Fair-SMAB problem, where each arm is required to be pulled for at least a given fraction of the total available rounds. We investig…
FairnessA Regret bound for Non-stationary Multi-Armed Bandits with Fairness Constraints
The multi-armed bandits' framework is the most common platform to study strategies for sequential decision-making problems. Recently, the notion of fairness has attracted a lot of attention in the machine learning commun…
Decision MakingFairnessMulti-Armed BanditsSequential Decision MakingA new look at fairness in stochastic multi-armed bandit problems
We study an important variant of the stochastic multi-armed bandit (MAB) problem, which takes fairness into consideration. Instead of directly maximizing cumulative expected reward, we need to balance between the total r…
FairnessFair Algorithms for Multi-Agent Multi-Armed Bandits
We propose a multi-agent variant of the classical multi-armed bandit problem, in which there are $N$ agents and $K$ arms, and pulling an arm generates a (possibly different) stochastic reward for each agent. Unlike the c…
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 Bandits