MNL-Bandit in non-stationary environments

Ayoub Foussoul, Vineet Goyal, Varun GuptaarXiv 2023 · DOI · arXiv

Abstract

This paper introduces EEMNSE, the first algorithm to achieve optimal dynamic regret for the Multinomial Logit (MNL) Bandit problem in non-stationary environments. The authors address the challenge of shifting customer preferences by introducing a novel stochastic analysis tool called the "uninterrupted purchases process" (UPP) to manage estimation bias. Combined with the MASTER meta-algorithm framework, EEMNSE provides near-optimal regret bounds, closing a significant gap in non-stationary assortment selection theory.

Introduction

In online retail, sellers must decide which subset of products (an assortment) to present to customers to maximize revenue. The Multinomial Logit (MNL) Bandit is the standard mathematical framework for this task, modeling the probability of a customer choosing a specific item or nothing at all based on "attraction parameters."

While most existing research assumes these parameters are stationary, real-world preferences are dynamic—influenced by trends, seasons, and competition. This non-stationarity introduces a technical challenge: standard epoch-based algorithms, which offer the same assortment until a "no-purchase" event occurs, become biased if preferences shift during an epoch. This paper provides the first solution that maintains optimality despite these shifts.

Methods

The proposed solution, EEMNSE (Exploration-Exploitation algorithm for MNL-bandit in Non-Stationary Environments), utilizes a two-layered approach:

  1. Base Algorithm: An adaptation of the Upper Confidence Bound (UCB) epoch-based algorithm. It maintains optimistic estimates of product popularity to balance exploration (trying new assortments) and exploitation (showing proven winners).
  2. MASTER Meta-Algorithm: The base algorithm is wrapped in the "MASTER" framework (Wei and Luo, 2021). This framework runs multiple instances of the base algorithm across different time scales and monitors for environmental "shocks." If a significant shift is detected, the relevant learning process is restarted.
Algorithm 1: Exploration-Exploitation for MNL-Bandit in near-stationary environments.

The core theoretical innovation is the Uninterrupted Purchases Process (UPP). To handle the bias caused by shifting parameters, the authors "sandwich" the actual purchase process between two theoretical stationary geometric random variables. This allows for the derivation of non-symmetric concentration bounds that ensure the algorithm remains accurate even when the ground truth is in flux.

Key Insights and Theoretical Contributions

  • The "Sandwich" Trick: By proving that a biased, non-stationary process is bounded by two stationary processes, the authors make the complex mathematics of shifting preferences tractable without sacrificing optimality.
  • Refined Variation Measure: The authors argue that standard measures of change (like the $L_\infty$ norm) are insufficient for the MNL setting. They introduce $\Delta_\infty^K$, a new variation measure that specifically tracks the total attraction of product subsets, providing a more precise characterization of problem difficulty.
  • Closing the Optimality Gap: Through the derivation of matching theoretical lower bounds, the authors demonstrate that EEMNSE is near-optimal (up to logarithmic factors), meaning no polynomial-time algorithm can significantly outperform it in this setting.

Key Results

The paper establishes a "worst-case expected regret" bound, representing the difference between the algorithm's performance and an omniscient oracle that knows preferences in advance.

  • Regret Bound: $\tilde{O}\left(\min\left\{\sqrt{NTL}, N^{1/3}(\Delta_\infty^K)^{1/3}T^{2/3} + \sqrt{NT}\right\}\right)$
    • $N$: Number of products.
  • $T$: Total time horizon.
  • $L$: Number of abrupt environment switches.
  • $\Delta_\infty^K$: Total gradual variation in the environment.

These upper bounds are tight, as the authors proved that any algorithm must incur at least $\tilde{\Omega}(\sqrt{NLT})$ or $\tilde{\Omega}(N^{1/3}(\Delta_\infty^K)^{1/3}T^{2/3})$ regret.

Limitations and Future Work

While providing robust theoretical guarantees, the work has some limitations. The model assumes "adversarial" changes, which can be arbitrary; leveraging structured changes (e.g., seasonal cycles) could lead to more efficient specialized algorithms. Additionally, the MASTER framework's requirement to run multiple instances of the base algorithm may introduce computational overhead in systems with a very large number of products ($N$). Finally, future empirical studies using real-world retail data would be valuable to validate these theoretical findings in practice.

Summary updated

Abstract

In this paper, we study the MNL-Bandit problem in a non-stationary environment and present an algorithm with a worst-case expected regret of $\tilde{O}\left( \min \left\{ \sqrt{NTL}\;,\; N^{\frac{1}{3}}(Δ_{\infty}^{K})^{\frac{1}{3}} T^{\frac{2}{3}} + \sqrt{NT}\right\}\right)$. Here $N$ is the number of arms, $L$ is the number of changes and $Δ_{\infty}^{K}$ is a variation measure of the unknown parameters. Furthermore, we show matching lower bounds on the expected regret (up to logarithmic factors), implying that our algorithm is optimal. Our approach builds upon the epoch-based algorithm for stationary MNL-Bandit in Agrawal et al. 2016. However, non-stationarity poses several challenges and we introduce new techniques and ideas to address these. In particular, we give a tight characterization for the bias introduced in the estimators due to non stationarity and derive new concentration bounds.
BibTeX
@misc{foussoul2023mnl,
  author = {Ayoub Foussoul and Vineet Goyal and Varun Gupta},
  title = {{MNL-Bandit in non-stationary environments}},
  year = {2023},
  eprint = {2303.02504},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2303.02504},
}
Figure