UCB-based Algorithms for Multinomial Logistic Regression Bandits

Out of the rich family of generalized linear bandits, perhaps the most well studied ones are logistic bandits that are used in problems with binary rewards: for instance, when the learner aims to maximize the profit over a user that can select one of two possible outcomes (e.g., click' vs no-click'). Despite remarkable recent progress and improved algorithms for logistic bandits, existing works do not address practical situations where the number of outcomes that can be selected by the user is larger than two (e.g., click', show me later', never show again', no click'). In this paper, we study such an extension. We use multinomial logit (MNL) to model the probability of each one of K 1\geq 2 possible outcomes ( 1 stands for the not click' outcome): we assume that for a learner's action \mathbf{x}_t, the user selects one of K 1\geq 2 outcomes, say outcome i, with a MNL probabilistic model with corresponding unknown parameter \bar{\boldsymbol{\theta}}_{\ast i} . Each outcome i is also associated with a revenue parameter \rho_i and the goal is to maximize the expected revenue.