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:
- Contextual Information: The utility of an item isn't fixed; it depends on features (context) of the user and the item.
- 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).
- 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.
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