Thompson Sampling for Multinomial Logit Contextual Bandits

Min-hwan Oh, Garud IyengarNeurIPS 2019 · OpenReview

This paper tackles a sophisticated version of the recommendation problem: how to choose a set of items to show a user when their choice depends on both the context (who they are and what the items are) and the specific mix of items offered. The authors present the first Thompson Sampling (TS) algorithms for the Multinomial Logit (MNL) contextual bandit problem, providing solutions that scale independently of the total number of items and outperform existing state-of-the-art methods.

The Assortment Selection Problem

In many online platforms, the system doesn't just show one item; it shows an assortment. The goal is to maximize revenue by picking the best assortment. This is traditionally modeled using the Multinomial Logit (MNL) model, which captures how users choose one item from a set based on relative utilities.

The challenge here is three-fold:

  1. Contextual Information: The utility of an item isn't fixed; it depends on features (context) of the user and the item.
  2. Exploration vs. Exploitation: The system must balance showing assortments it knows are good (exploitation) with trying new ones to learn more about user preferences (exploration).
  3. Combinatorial Complexity: If you have $N$ items and want to show $K$, there are $\binom{N}{K}$ possible assortments. This makes standard Upper Confidence Bound (UCB) methods computationally expensive, as they often require calculating confidence scores for every possible combination.

Proposed Algorithms

The authors propose two Thompson Sampling-based algorithms to address these challenges, both leveraging efficient linear programming solvers to handle assortment selection without iterating through every possible combination.

1. TS-MNL (Bayesian Approach)

The first algorithm is a standard Bayesian approach. It maintains a posterior distribution of the unknown preference parameters. In each round, it samples a parameter from this distribution and picks the assortment that would be optimal for that specific sample.

Pseudocode for TS-MNL, the standard Bayesian Thompson Sampling approach.

2. TS-MNL with Optimistic Sampling

The second algorithm is designed for worst-case (frequentist) regret analysis. Standard TS can struggle here because the probability of being "optimistic" (overestimating the value of the best assortment) can vanish exponentially as the assortment size $K$ grows.

To fix this, instead of one sample, the algorithm draws $M$ independent samples from a Gaussian approximation of the posterior. It then uses the maximum utility across those $M$ samples for each item. This "optimistic sampling" ensures the algorithm explores enough to guarantee low regret without needing an astronomical number of samples.

Key Findings and Theoretical Guarantees

The authors evaluated their algorithms using both synthetic datasets (where true user preference parameters are known) and the real-world MovieLens dataset.

  • Theoretical Bounds: They prove a Bayesian regret bound of $\tilde{O}(d\sqrt{T})$ and a frequentist regret bound of $\tilde{O}(d^{3/2}\sqrt{T})$, where $d$ is the number of features and $T$ is the number of rounds. These match or exceed the best-known bounds for simpler linear bandits.
  • Independence from Catalog Size: Crucially, their regret bounds do not depend on the total number of items ($N$) in the catalog. This is a significant advantage for large-scale systems with millions of products.
  • Empirical Performance: In simulations, both TS variants significantly outperformed the existing UCB-based state-of-the-art. Thompson Sampling was not only more accurate (lower regret) but also more computationally efficient, as it avoids maintaining complex confidence ellipsoids for every possible assortment.
  • The Optimism Boost: The "Optimistic Sampling" version consistently performed better than the standard Gaussian approximation, confirming that the theoretical trick translates to real-world efficiency.

Limitations and Future Work

While highly effective, the pure Bayesian version (Algorithm 1) faces posterior intractability. Because no conjugate prior exists for the MNL model, calculating the exact posterior requires Markov Chain Monte Carlo (MCMC) methods, which can be slow in practice. Additionally, the model assumes item utility is a linear function of features, which might not capture highly complex, non-linear user behaviors.

Future directions suggest that the novel "optimistic sampling" framework could be applied to other complex combinatorial problems beyond the MNL model, such as cascading bandits or ranking problems.

Reference: Oh, M., & Iyengar, G. (2019). Thompson Sampling for Multinomial Logit Contextual Bandits. Advances in Neural Information Processing Systems (NeurIPS).",

Summary updated

Abstract

We consider a dynamic assortment selection problem where the goal is to offer a sequence of assortments that maximizes the expected cumulative revenue, or alternatively, minimize the expected regret. The feedback here is the item that the user picks from the assortment. The distinguishing feature in this work is that this feedback has a multinomial logistic distribution. The utility of each item is a dynamic function of contextual information of both the item and the user. We propose two Thompson sampling algorithms for this multinomial logit contextual bandit. Our first algorithm maintains a posterior distribution of the true parameter and establishes $\tilde{O}(d\sqrt{T})$ Bayesian regret over $T$ rounds with $d$ dimensional context vector. The worst-case computational complexity of this algorithm could be high when the prior distribution is not a conjugate. The second algorithm approximates the posterior by a Gaussian distribution, and uses a new optimistic sampling procedure to address the issues that arise in worst-case regret analysis. This algorithm achieves $\tilde{O}(d^{3/2}\sqrt{T})$ worst-case (frequentist) regret bound. The numerical experiments show that the practical performance of both methods is in line with the theoretical guarantees.
BibTeX
@inproceedings{oh2019thompson,
  author = {Min-hwan Oh and Garud Iyengar},
  title = {{Thompson Sampling for Multinomial Logit Contextual Bandits}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2019},
  url = {https://openreview.net/forum?id=WuvoVPysDs},
}
Figure