Borda-Based Fair Multi-User Dueling Bandit in Tabular and Generalized Linear Settings

The increasing prevalence of preference-based learning, particularly for machine learning models interacting with human users, gives rise to scenarios where the model's decision should cater to the preferences of a number of users. Due to the inherent misalignments in such preferences, it is natural to seek a fair decision-making paradigm. Motivated by that, we pose the problem of fair multi-user dueling bandit, where each user's preferences over pairs of actions are encoded by a preference matrix unknown to the agent. We design a Nash social welfare objective based on the Borda scores of the individual user preferences. The notion of the Borda score measures the average likelihood of an action being preferred over the other actions, and importantly, it does not require the existence of a completely dominant action. Considering online learning in this general setting, we construct hard instances and establish a minimax lower bound on the achievable regret. We also design an explore-then-commit algorithm and derive an upper bound on its worst-case regret. Furthermore, we formulate a fair multi-user generalized linear dueling bandit to enable modeling large action spaces, which typically necessitate a structured representation. In this setting, too, we establish a lower bound on regret and an upper bound on regret for a proposed explore-then-commit algorithm.