Near-Optimal MNL Bandits Under Risk Criteria

Guangyu Xi, Chao Tao, Yuan ZhouAAAI 2021 · DOI

Introduction

In online retail environments, platforms must decide which subset of products (an assortment) to display to users. This is traditionally modeled as a Multinomial Logit (MNL) Bandit problem, where the objective is to maximize expected revenue. However, maximizing average revenue often ignores the volatility or risk associated with specific strategies. For instance, a high-revenue strategy might rely on a small group of "whale" customers, creating instability and risking long-term user diversity.

To address this, decision-makers in finance and industry often employ risk criteria such as Conditional Value-at-Risk (CVaR) or the Sharpe ratio. This paper introduces the first near-optimal framework for MNL bandits that prioritizes risk management, providing strong theoretical guarantees for complex, non-linear risk functions.

The Risk-Aware Framework

The authors propose two primary algorithms: RiskAwareUCB (Upper Confidence Bound) and RiskAwareTS (Thompson Sampling). The core innovation lies in identifying three "mild conditions" that a risk function $U$ must satisfy to be solvable within this framework:

  1. Quasiconvexity: Prevents the algorithm from getting stuck in local optima.
  2. Boundedness: Ensures the risk value remains within a manageable range.
  3. One-sided Lipschitz Condition: Guarantees that small changes in product preference parameters lead to predictable changes in risk.

This framework is remarkably general, encompassing a wide variety of popular risk measures used in practice.

Table 1: Various risk criteria and their mathematical properties within the proposed framework.

The algorithms maintain optimistic estimates of unknown product preference parameters ($v_i$). In each episode, the algorithm selects an assortment that maximizes the risk criterion based on these estimates. This process continues until a "no-purchase" event occurs, providing the necessary data to refine the preference estimates.

Key Insights and Theoretical Results

A major technical contribution is the "Monotone Maximum" Lemma, which proves that for risk functions satisfying the specified conditions, an optimistic estimate of product preferences always yields a risk value at least as high as the true optimal assortment. This justifies the application of UCB-style optimism in risk-sensitive settings.

Crucially, the authors prove that RiskAwareUCB achieves a regret bound of $\tilde{O}(\sqrt{NT})$. This is considered near-optimal as it matches the $\Omega(\sqrt{NT})$ lower bound established for the simpler case of standard revenue maximization, showing that risk awareness does not necessarily come at the cost of theoretical efficiency.

Empirical Evaluation

The researchers evaluated their algorithms using both synthetic data and real-world data from the UCI Car Evaluation Database. In the real-world scenario, car attributes were mapped to preference parameters, and random profit values were assigned to each vehicle. The goal was to maximize CVaR at the 0.05 percentile.

Figure 1: Regret comparison between risk-aware and standard bandit algorithms.

The experiments demonstrated that standard revenue-maximizing UCB and Thompson Sampling perform poorly when evaluated against risk metrics. In contrast, the risk-aware variants converged significantly faster to the optimal risk-adjusted assortment. Notably, RiskAwareTS generally outperformed RiskAwareUCB in practice, a trend often seen in bandit literature.

Limitations and Future Work

While the framework is robust, it currently cannot handle Value-at-Risk (VaR) due to its discontinuity, which violates the one-sided Lipschitz condition. Additionally, the model assumes product profits are known beforehand; future work could explore scenarios where profits are also random variables that must be learned. Finally, for very large product sets, finding the optimal assortment remains computationally intensive, suggesting a need for more efficient exact optimization methods for specific risk functions.

Summary updated

BibTeX
@inproceedings{xi2021near,
  author = {Guangyu Xi and Chao Tao and Yuan Zhou},
  title = {{Near-Optimal MNL Bandits Under Risk Criteria}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i12.17245},
}
Figure