MNL-Bandit with Fairness Constraints

We study a variant of online assortment optimization under multinomial logit (MNL)-Bandit feedback where, in addition to maximizing the total revenue, the seller must also take fairness into account. We consider the fairness constraint that the seller must offer each product for a predefined fraction of time at any time, giving every product a fair chance for exposure. We first propose two algorithms that satisfy fairness constraints with high probability: a maximum likelihood estimation (MLE)–based algorithm and an upper confidence bound (UCB)–based algorithm, both of which rely on solving linear programs (LPs). These algorithms achieve regret bounds of $\tilde{O}(T^{2/3})$ and $\tilde{O}(T^{1/2})$, respectively. Next, we propose an MLE-based algorithm and a UCB-based algorithm that both satisfy the fairness constraints and avoid solving complex LPs by calculating efficiently solvable assortment optimization problems, with the UCB-based algorithm achieving a $\tilde{O}(T^{1/2})$ regret under the separation assumption for the revenue and utility parameters. Finally, we empirically validate the theoretical results on real data.

History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete.

Funding: This work was supported by the Shanghai Education Development Foundation [Grant 23CGA02] and the National Natural Science Foundation of China [Grant 12301376].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1364) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2025.1364). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.