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:
- 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).
- 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.
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