Thompson Sampling for the MNL-Bandit

Abstract

We consider a sequential subset selection problem under parameter uncertainty, where at each time step, the decision maker selects a subset of cardinality $K$ from $N$ possible items (arms), and observes a (bandit) feedback in the form of the index of one of the items in said subset, or none. Each item in the index set is ascribed a certain value (reward), and the feedback is governed by a Multinomial Logit (MNL) choice model whose parameters are a priori unknown. The objective of the decision maker is to maximize the expected cumulative rewards over a finite horizon $T$, or alternatively, minimize the regret relative to an oracle that knows the MNL parameters. We refer to this as the MNL-Bandit problem. This problem is representative of a larger family of exploration-exploitation problems that involve a combinatorial objective, and arise in several important application domains. We present an approach to adapt Thompson Sampling to this problem and show that it achieves near-optimal regret as well as attractive numerical performance.

Accepted for presentation at Conference on Learning Theory (COLT) 2017

References in corpus (1)

• Further Optimal Regret Bounds for Thompson Sampling

Cited by in corpus (10)

• Optimal No-regret Learning in Repeated First-price Auctions
• Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits
• Adversarial Combinatorial Bandits with General Non-linear Reward Functions
• Thompson Sampling for Contextual Bandit Problems with Auxiliary Safety Constraints
• Dynamic Learning of Sequential Choice Bandit Problem under Marketing Fatigue
• Multinomial Logit Bandit with Linear Utility Functions
• Thompson Sampling for a Fatigue-aware Online Recommendation System
• Thompson Sampling Algorithms for Cascading Bandits
• Learning to Rank under Multinomial Logit Choice
• Combinatorial Bandits without Total Order for Arms