Fairness and Welfare Quantification for Regret in Multi-Armed Bandits
This work addresses fairness and welfare considerations in multi-armed bandit algorithms, offering a novel perspective but is incremental in extending regret analysis with welfare functions.
The paper tackles the problem of evaluating multi-armed bandit algorithms by introducing Nash regret, based on the Nash social welfare function to incorporate fairness, and develops algorithms achieving Nash regret bounds of O(√(k log T / T)) for a fixed horizon and O(√(k log T / T) log T) for an anytime version, which are shown to be essentially tight.
We extend the notion of regret with a welfarist perspective. Focussing on the classic multi-armed bandit (MAB) framework, the current work quantifies the performance of bandit algorithms by applying a fundamental welfare function, namely the Nash social welfare (NSW) function. This corresponds to equating algorithm's performance to the geometric mean of its expected rewards and leads us to the study of Nash regret, defined as the difference between the -- a priori unknown -- optimal mean (among the arms) and the algorithm's performance. Since NSW is known to satisfy fairness axioms, our approach complements the utilitarian considerations of average (cumulative) regret, wherein the algorithm is evaluated via the arithmetic mean of its expected rewards. This work develops an algorithm that, given the horizon of play $T$, achieves a Nash regret of $O \left( \sqrt{\frac{k \log T}{T}} \right)$, here $k$ denotes the number of arms in the MAB instance. Since, for any algorithm, the Nash regret is at least as much as its average regret (the AM-GM inequality), the known lower bound on average regret holds for Nash regret as well. Therefore, our Nash regret guarantee is essentially tight. In addition, we develop an anytime algorithm with a Nash regret guarantee of $O \left( \sqrt{\frac{k\log T}{T}} \log T \right)$.