summaries: The paper studies multinomial logistic (MNL) regression bandits, a generalization of binary logistic bandits. It differs from previous works on MNL bandits by considering a different decision-making process. That is, the authors do not address the combinatorial action selection of previous MNL bandits, but rather study the problem setting where the agent offers a single item, but with K different outcomes.   The paper introduces a UCB-based algorithm for this problem, for which the authors establish a sub-linear regret bound. By building on recent advances in logistic bandits, they improve the prohibitive impact of the constant \kappa from both the design of their algorithm and its theoretical guarantees. This paper presents MNL-UCB Algorithm for contextual MNL bandits problem. At every step, the algorithm estimates a K-tuple of parameter vectors in the confidence region. Specifically, they prove that the regret of MNL-UCB scales as \tilde{O}(dK\sqrt{\kappa}\sqrt{T}) where $\kappa$ is a parameter that captures the degree of (non)-smoothness of the MNL model. It improves the constant from linear in \kappa to \sqrt{\kappa}. They further improved algorithm that achieves a regret bound with problem-dependent constant \kappa being pushed into a second order term.  Compared to the most existing work, a major difference is that each choice is associated with a different parameter so a matrix of parameters needs to be learned.  This paper considers a version of stochastic contextual bandits where the rewards are drawn from a discrete distribution governed by a multionimal logit model. This setting is motivated by applications in online advertising where the user may give various feedbacks in the face of a recommendation beyond a binary ‘clicked’ or ‘did not click’ – e.g. ‘show me again later’, ‘never show me again’. The authors propose and analyse a UCB algorithm for this problem with the confidence sets being based on the work of Faury et al. (2020, ICML) and the regret analysis being based on that of Abbasi-Yadkori et al. (2011, NeurIPS). The particular advantage of utilising the concentration results of Faury et al is that the regret of the resulting algorithm scales favourably (square root order) with respect to a parameter $\kappa$ characterising the smoothness of the logit function around the true parameter. A further algorithm whose dependence on $\kappa$ is relegated to lower order terms w.r.t. the horizon is also developed – however this approach is computationally intractable. In the related (binary) logistic bandit setting, some popular algorithms have been shown to have exponential order dependence on this parameter and the design of algorithms which are robust to its value is useful. It may be useful to note that this version of a multinomial bandit is different from the combinatorial problem in the dynamic assortment selection literature (e.g. Agrawal et al (2017, 2019)) where the different outcomes represent different items.    The paper studies multinomial logistic regression bandit problem, where the number of outcomes can be greater than two. This is an extension of the well-studied generalized linear bandit problem with two outcomes (e.g., clicks and no-clicks). The authors first propose the problem setup with real-life motivated scenarios and then propose a UCB based algorithm to minimize cumulative regret. The authors analyze its performance and derive an upper bound of \tilde{O}(dK\sqrt{\kappa T}), where d is the dimension of the action space, (K + 1) is the number of outcomes, T is the number of interactions, and \kappa is the degree of non-smoothness, which is inherent to the multi-nomial problem. At the end, the authors provide a simulation based study which supports their theoretical insights.  
abstractText: 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 2 possible outcomes (+1 stands for the ‘not click’ outcome): we assume that for a learner’s action xt, the user selects one of K + 1 2 outcomes, say outcome i, with a MNL probabilistic model with corresponding unknown parameter ✓̄⇤i. Each outcome i is also associated with a revenue parameter ⇢i and the goal is to maximize the expected revenue. For this problem, we present MNL-UCB, an upper confidence bound (UCB)-based algorithm, that achieves regret Õ(dK p T ) with small dependency on problemdependent constants that can otherwise be arbitrarily large and lead to loose regret bounds. We present numerical simulations that corroborate our theoretical results.
authors.name: Sanae Amani
authors.name: Christos Thrampoulidis
references.authors: Y. Abbasi-Yadkori D. Pál C. Szepesvári
references.title: Improved algorithms for linear stochastic bandits
references.venue: Advances in Neural Information Processing Systems, pages 2312–2320.
references.authors: M. Abeille L. Faury C. Calauzènes
references.title: Instance-wise minimax-optimal algorithms for logistic bandits
references.venue: In International Conference on Artificial Intelligence and Statistics,
references.authors: M. Abeille A Lazaric
references.title: Linear thompson sampling revisited
references.venue: Electronic Journal of Statistics,
references.authors: P. Agrawal V. Avadhanula T. Tulabandhula
references.title: A tractable online learning algorithm for the multinomial logit contextual bandit
references.venue: arXiv preprint arXiv:2011.14033.
references.authors: S. Agrawal V. Avadhanula V. Goyal A. Zeevi
references.title: Thompson sampling for the mnl-bandit
references.venue: Conference on Learning Theory, pages 76–78.
references.authors: S. Agrawal V. Avadhanula V. Goyal A. Zeevi
references.title: Mnl-bandit: A dynamic learning approach to assortment selection
references.venue: Operations Research, 67(5):1453–1485.
references.authors: O. Avner S. Mannor
references.title: Multi-user communication networks: A coordinated multi-armed bandit approach
references.venue: IEEE/ACM Transactions on Networking, 27(6):2192–2207.
references.authors: F. Berkenkamp A. Krause A.P. Schoellig
references.title: Bayesian optimization with safety constraints: safe and automatic parameter tuning in robotics
references.venue: arXiv preprint arXiv:1602.04450.
references.authors: A. Berman R.J. Plemmons
references.title: Nonnegative matrices in the mathematical sciences
references.venue: SIAM.
references.authors: X. Chen Y. Wang Y. Zhou
references.title: Dynamic assortment optimization with changing contextual information
references.venue: arXiv preprint arXiv:1810.13069.
references.authors: W.C. Cheung D. Simchi-Levi
references.title: Thompson sampling for online personalized assortment optimization problems with multinomial logit choice models
references.venue: Available at SSRN 3075658.
references.authors: V. Dani T.P. Hayes S.M. Kakade
references.title: Stochastic linear optimization under bandit feedback
references.venue: Conference on Learning Theory.
references.authors: K. Dong Y. Li Q. Zhang Y. Zhou
references.title: Multinomial logit bandit with low switching cost
references.venue: arXiv preprint arXiv:2007.04876.
references.authors: S. Dong B. Van Roy
references.title: An information-theoretic analysis for thompson sampling with many actions
references.venue: Advances in Neural Information Processing Systems, pages 4157–4165.
references.authors: L. Faury M. Abeille C. Calauzènes O. Fercoq
references.title: Improved optimistic algorithms for logistic bandits
references.venue: arXiv preprint arXiv:2002.07530.
references.authors: S. Filippi O. Cappe A. Garivier C. Szepesvári
references.title: Parametric bandits: The generalized linear case
references.venue: Advances in Neural Information Processing Systems, pages 586–594.
references.authors: D. Gamarnik J. Gaudio
references.title: Estimation of monotone multi-index models
references.venue: arXiv preprint arXiv:2006.02806.
references.authors: R.A. Horn C.R. Johnson
references.title: Matrix analysis
references.venue: Cambridge university press.
references.authors: T. Lattimore C. Szepesvári
references.title: Bandit algorithms
references.venue: Cambridge University Press.
references.authors: L. Li Y. Lu D. Zhou
references.title: Provably optimal algorithms for generalized linear contextual bandits
references.venue: arXiv preprint arXiv:1703.00048.
references.authors: S. Li F. Hao M. Li Kim H.-C.
references.title: Medicine rating prediction and recommendation in mobile social networks
references.venue: International conference on grid and pervasive computing, pages 216–223. Springer.
references.authors: Oh M.-h. G. Iyengar
references.title: Thompson sampling for multinomial logit contextual bandits
references.venue: Advances in Neural Information Processing Systems, pages 3151–3161.
references.authors: P. Rusmevichientong J.N. Tsitsiklis
references.title: Linearly parameterized bandits
references.venue: Mathematics of Operations Research, 35(2):395–411.
references.authors: D. Russo B. Van Roy
references.title: Eluder dimension and the sample complexity of optimistic exploration
references.venue: In Advances in Neural Information Processing Systems,
references.authors: D. Russo B. Van Roy
references.title: Learning to optimize via posterior sampling
references.venue: Mathematics of Operations Research, 39(4):1221–1243.
references.authors: Y. Sui V. Zhuang J.W. Burdick Y. Yue
references.title: Stagewise safe bayesian optimization with gaussian processes
references.venue: arXiv preprint arXiv:1806.07555.
references.authors: T. Sun Q. Tran-Dinh
references.title: Generalized self-concordant functions: a recipe for newton-type methods
references.venue: Mathematical Programming, 178(1-2):145–213.
references.authors: Tian G.-X. Huang T.-Z.
references.title: Inequalities for the minimum eigenvalue of m-matrices
references.venue: The Electronic Journal of Linear Algebra, 20.
references.authors: Q. Tran-Dinh Li Y.-H. V. Cevher
references.title: Composite convex minimization involving selfconcordant-like cost functions
references.venue: Modelling, Computation and Optimization in Information Systems and Management Sciences, pages 155–168. Springer.
references.authors: Y. Wang X. Chen Y. Zhou
references.title: Near-optimal policies for dynamic multinomial logit assortment selection models
references.venue: Advances in Neural Information Processing Systems, pages 3101–3110.
references.authors: Z. Yang K. Balasubramanian Z. Wang H. Liu
references.title: Learning non-gaussian multi-index model via second-order stein’s method
references.venue: Advances in Neural Information Processing Systems, 30:6097–6106.
sections.text: p T ) with small dependency on problem-
  dependent constants that can otherwise be arbitrarily large and lead to loose regret bounds. We present numerical simulations that corroborate our theoretical results.
sections.heading: 1 Introduction
sections.text: Linear stochastic bandits provide simple, yet commonly encountered, models for a variety of sequential decision-making problems under uncertainty. Specifically, linear bandits generalize the classical multi-armed bandit (MAB) problem of K arms that each yields reward sampled independently from an underlying distribution with unknown parameters, to a setting where the expected reward of each arm is a linear function that depends on the same unknown parameter vector Dani et al. (2008); Abbasi-Yadkori et al. (2011); Rusmevichientong and Tsitsiklis (2010). Linear bandits have been successfully applied over the years in online advertising, recommendation services, resource allocation, etc. Lattimore and Szepesvári (2020). More recently, researchers have explored the potentials of such algorithms in more complex systems, such as in robotics, wireless networks, the power grid, medical trials, e.g., Li et al. (2013); Avner and Mannor (2019); Berkenkamp et al. (2016); Sui et al. (2018). However, linear bandits fail to model a host of other applications. This has called for extensions of linear bandits to a broader range of reward structures beyond linear models. One of the leading lines of work addressing these extensions relies on the Generalized Linear Model (GLM) framework of statistics. In GLMs the expected reward associated with an arm x is given by µ(✓̄Tx), where ✓̄ 2 Rd is the system unknown parameter and µ is a non-linear link function. Specifically, logistic bandits, that are appropriate for modeling binary reward structures, are a special case of generalized linear bandits (GLBs) with µ(x) = (1 + exp( x)) 1. UCB-based algorithms for GLBs were first introduced in Filippi et al. (2010); Li et al. (2017); Faury et al. (2020). The same problem, but with a Thompson Sampling- (TS) strategy was also studied in Abeille et al. (2017);
  35th Conference on Neural Information Processing Systems (NeurIPS 2021).
  Russo and Van Roy (2013, 2014); Dong and Van Roy (2018). Beyond GLMs, an even more general framework for modeling reward is the semi-parametric index model (see for example Yang et al. (2017); Gamarnik and Gaudio (2020) for a list of applications in statistics). A semi-parametric index model relates the reward y 2 R and the action/arm x 2 Rd as y = µ(✓̄T1 x, ✓̄ T 2 x, . . . , ✓̄ T Kx) + ✏, where µ : RK ! R and ✓̄1, . . . , ✓̄K 2 Rd are K system’s unknown parameters. GLBs are special cases of this for K = 1, also known as single-index models (SIM) in statistics. In this paper, we formulate an extension of the problem of binary logistic bandits (i.e., a special case of SIM) to multinomial logit (MNL) bandits, a special case of multi-index models (MIM) to account for settings with more than two possible outcomes on the user choices (K 1). For this model, we present an algorithm and corresponding regret bound. Our algorithmic and analytic contribution is in large inspired by recent exciting progress on binary logistic bandits by Faury et al. (2020).
  To motivate MNL bandits, consider ad placement. When an ad is shown to a user, the user may have several options to react to the ad. For example, she can choose to 1) click on the ad; 2) click on “show me later”; 3) click on “never show me this ad”; 4) not click at all, etc. The user selects each of these options based on an unknown probability distribution that inherently involves linear combinations of the selected feature vector denoting the ad and unknown parameters denoting the user’s preferences about the ad. In this setting, each option is associated with a specific notion of reward. The agent’s goal is to determine ads with maximum expected rewards to increase the chance of a successful advertisement.
  Outline. In Section 1.1, we formally define the problem. In Sections 2.1, 2.2 and 2.4, we elaborate on the challenges that the generalization of the Logistic-UCB-1 by Faury et al. (2020) to the settings with MIM rewards brings to our theoretical analysis. We then summarize our proposed MNL-UCB in Algorithm 1 and provide a regret bound for it in Section 2.5. In Section 3, we present a detailed discussion on the challenges and computation of necessary problem-dependent constants. Finally, we complement our theoretical results with numerical simulations in Section 4.
  Notation. We use lower-case letters for scalars, lower/upper-case bold letters for vectors/matrices. kxk2 denotes the Euclidean norm and x T y inner product. ij denotes the Kronecker delta, i.e., ij = 1 if i 6= j and ij = 0 if i = j. A⌦B denotes the Kronecker product. For square matrices A and B, we use A B to denote B A is positive semi-definite. We denote the minimum and maximum eigenvalues of A by min(A) and max(A). For A ⌫ 0, the weighted 2-norm of ⌫ with respect to A is defined byk⌫k
  A =
  p
  ⌫TA⌫. For positive integers n and m  n, [n] and [m : n] denote the sets {1, 2, . . . , n} and {m, . . . , n}, respectively. For any ⌫ 2 RKd, ⌫̄i = ⌫ [(i 1)d+1:d] 2 Rd denotes the vector containing the i-th set of d entries of ⌫. We use 1 and ei to denote the vector of all 1’s and the i-th standard basis vector, respectively. Finally, we use Õ for big-Oh notation that ignores logarithmic factors.
sections.heading: 1.1 Problem formulation
sections.text: Reward Model. The agent is given a decision set1 D ⇢ Rd. At each round t, the agent chooses an action xt 2 D and observes the user purchase decision yt 2 [K] [ {0}. Here, {0} denotes the “outside decision”, which means the user did not select any of the presented options. The agent’s decision at round t is based on the information gathered until time t, which can be formally encoded in the filtration Ft := (F0, ({xs, ys}t 1s=1)), where F0 represents any prior knowledge. Let each option i 2 [K] be associated with an unknown vector ✓̄⇤i 2 Rd and let ✓⇤ = [✓̄ T ⇤1, ✓̄ T ⇤2, . . . , ✓̄ T ⇤K ] T 2 RKd. The user’s choice of what to click on is given by a multinomial logit (MNL) choice model. Under this model, the probability distribution of the user purchase decision is given by
  P(yt = i|xt,Ft) :=
  8 >><
  >>:
  1
  1+ PK j=1 exp( ¯✓ T ⇤jxt) , if i = 0,
  exp( ¯✓ T
  ⇤ixt)
  1+ PK j=1 exp( ¯✓ T ⇤jxt) , if i 2 [K].
  (1)
  When the user clicks on the i-th option, a corresponding reward ⇢i is revealed to the agent and we set ⇢0 = 0. Then, the expected reward observed by the agent when she plays action xt is
  1Our results extend easily to time-varying decision sets.
  E[Rt|xt,Ft] = PK j=1 ⇢j exp( ¯✓ T ⇤jxt)
  1+ PK j=1 exp( ¯✓ T ⇤jxt) = ⇢T z(xt,✓⇤), where ⇢ = [⇢1, ⇢2, . . . , ⇢K ]T , z(xt,✓⇤) =
  [z1(xt,✓⇤), z2(xt,✓⇤), . . . , zK(xt,✓⇤)]T , and
  zi(xt,✓⇤) = P(yt = i|xt,Ft), 8i 2 [K]. (2)
  Note that E[Rt|xt,Ft] = µ(✓̄ T ⇤1x, ✓̄ T ⇤2x, . . . , ✓̄ T ⇤Kx) is not directly a generalized linear model, i.e., a function µ(✓̄T⇤ xt), but rather it is a multi-index model, where µ : RK ! R. Goal. Let T be the total number of rounds and x⇤ be the optimal action that maximizes the reward in expectation, i.e., x⇤ 2 argmaxx2D ⇢T z(x,✓⇤). The agent’s goal is to minimize the cumulative pseudo-regret defined by RT = PT t=1 ⇢ T z(x⇤,✓⇤) ⇢T z(xt,✓⇤).
sections.heading: 1.2 Contributions
sections.text: We study MNL logistic regression bandits, a generalization of binary logistic bandits, that address applications where the number of outcomes that can be selected by the user is larger than two. The probability of selecting any possible K + 1 > 2 options (+1 stands for the ‘not click’ outcome aka “outside decision”) is modeled using a multinomial logit (MNL) model. For this problem:
  • We identify a critical parameter , which we interpret as the degree of (non)-smoothness (less smooth for larger values of ) of the MNL model over the agent’s decision set. We prove that  scales exponentially with the size of the agent’s decision set creating a challenge in the design of low-regret algorithms, similar to the special binary case previously studied in the literature. • We develop a UCB-type algorithm for MNL logistic regression bandits. At every step, the algorithm decides on the inclusion of a K-tuple of parameter vectors ✓̄⇤1, . . . , ✓̄⇤K in the confidence region in a way that captures the local smoothness of the MNL model around this K-tuple and past actions. We show that this is critical for the algorithm’s favorable regret performance in terms of . • Specifically, we prove that the regret of our MNL-UCB scales as Õ(dK p  p T ). Instead, we show that a confidence ellipsoid that fails to capture local dependencies described above results in regret that scales linearly with  rather than with p . Moreover, our regret bound scales optimally in terms of the number of options K. • We propose an improved algorithm that achieves a regret bound with problem-dependent constant  being pushed into a second order term that vanishes quickly. • We complement our theoretical results with numerical simulations and corresponding discussions on the performance of our algorithm.
sections.heading: 1.3 Related works
sections.text: Generalized Linear Bandits. GLBs were studied in Filippi et al. (2010); Li et al. (2017); Abeille et al. (2017); Russo and Van Roy (2013, 2014); Dong and Van Roy (2018) where the stochastic reward is modeled through an appropriate strictly increasing link function µ. All these works provide regret bounds Õ( p T ), where the multiplicative factor  is a problem-dependent constant and characterizes the degree of non-linearity of the link function.
  Logistic Bandits. In Faury et al. (2020), the authors focused on the logistic bandit problem as a special case of GLBs. By introducing a novel Bernstein-like self-normalized martingale tail-inequality, they reduced the dependency of the existing GLB algorithms’ regret bounds on the constant  by a factor of p  and obtained a O(d p T ) regret for the logistic bandit problem. They further discussed the crucial role of , which can be arbitrarily large as it scales exponentially with the size of the decision set, on the performance of existing algorithms. Motivated by such considerations, with careful algorithmic designs, they achieved to drop entirely the dependence on  leading to a regret of Õ(d p T ).
  Multinomial Logit Bandits. In a different line of work, Agrawal et al. (2017, 2019); Wang et al. (2018); Oh and Iyengar (2019); Chen et al. (2018); Dong et al. (2020); Agrawal et al. (2020) used the multinomial logit choice model to address the dynamic assortment selection problem, which is a combinatorial variant of the bandit problem. In this problem, the agent chooses a so-called assortment which is a subset of a set S = [N ] of N items. At round t, feature vectors xit, for every item i 2 S , are revealed to the agent, and given this contextual information, the agent selects an assortment St ⇢ S
  and observes the user choice yt = i, i 2 St [ {0} where {0} corresponds to the user not selecting any item in St. The user choice is given by a MNL model with an unknown parameter ✓̄⇤ 2 Rd such that the probability that the user selects item i 2 St is exp(✓̄ T ⇤ xit)/(1 + P i2St exp(✓̄ T ⇤ xit)). Furthermore, a revenue parameter denoted by rit for each item i is also revealed at round t. The goal of the agent is to offer assortments with size at most K to maximize the expected cumulative revenue or to minimize the cumulative regret PT t=1 Rt(S ⇤ t , ✓̄⇤) Rt(St, ✓̄⇤), where Rt(St, ✓̄⇤) := P i⇢St rit exp(✓̄ T ⇤ xit)/(1 + P i2St exp(✓̄ T ⇤ xit)). Finally, the closely related paper Cheung and Simchi-Levi (2017) studies a problem where at each round, the agent observes a userspecific context based on which, it recommends a set of items to the user. The probability distribution of each one of the items in that set being selected by the user is given by an MNL model. This problem can be categorized as an online assortment optimization problem. Despite similarities in the use of an MNL model, there are certain differences between Cheung and Simchi-Levi (2017) and our paper in terms of problem formulation. In our setting, the user may have multiple reactions (one of K + 1 options), to a single selected item. In contrast, in Cheung and Simchi-Levi (2017), the agent must select a set of items to each of which the user reacts by either clicking or not clicking. Also, here the probability distribution of different user reactions remains the same at all rounds, while in Cheung and Simchi-Levi (2017) the response to an item from the recommended set depends on the other items in that set. We defer to future work studying implications of our techniques to the setting of Cheung and Simchi-Levi (2017).
sections.heading: 2 Multnomial Logit UCB Algorithms
sections.text: In this section, we introduce two key quantities: (i) ✓t, an estimate of ✓⇤; (ii) ✏t(x), an exploration bonus for each x 2 D at each round t 2 [T ]. Based on these, we design a UCB-type algorithm, called MNL-UCB. At each round t, the algorithm computes an estimate ✓t of ✓⇤, that we present in Section 2.4. For each x 2 D and t 2 [T ], let ✏t(x) be such that the following holds with high probability:
  (x,✓t) := |⇢ T z(x,✓⇤) ⇢ T z(x,✓t)| ✏t(x). (3)
  At round t, having knowledge of ✏t(x), the agent computes the following upper bound on the expected reward ⇢T z(x,✓⇤) for all x 2 D:
  ⇢T z(x,✓⇤)  ⇢ T z(x,✓t) + ✏t(x). (4)
  Then, the learner follows a UCB decision rule to select an action xt according to the following rule:
  xt := argmax x2D
  ⇢T z(x,✓t) + ✏t(x). (5)
  To see how the UCB decision rule in (5) helps us control the cumulative regret, we show how it controls the instantaneous regret by the following standard argument Abbasi-Yadkori et al. (2011); Faury et al. (2020):
  rt = ⇢ T z(x⇤,✓⇤) ⇢ T z(xt,✓⇤) (4)  ⇢T z(x⇤,✓t) + ✏t(x⇤) ⇢ T z(xt,✓⇤)
  (5)  ⇢T z(xt,✓t) ⇢ T z(xt,✓⇤) + ✏t(xt) (3)  2✏t(xt) . (6)
  In view of this, our goal is to design an algorithm that appropriately chooses the estimator ✓t and the exploration bonus ✏t(x) such that its regret is sub-linear.
sections.heading: 2.1 Maximum likelihood estimate
sections.text: The problem of estimating ✓⇤ at round t given Ft is identical to a multi-class linear classification problem, where ✓̄⇤i is the “classifier” for class i. A natural way to compute the estimator of the unknown parameter ✓⇤ of the MNL model given Ft is to use the maximum likelihood principle. At round t, the regularized log-likelihood (aka negative cross-entropy loss) with regularizer > 0 writes
  L t (✓) :=
  t 1X
  s=1
  KX
  i=0
  {ys = i} log zi(xs,✓)
  2 k✓k22 . (7)
  Then, the maximum likelihood estimate of ✓⇤ is defined as ✓̂t := argmax✓ L t (✓). Taking the gradient of (7) with respect to ✓ we obtain
  r✓L t (✓) :=
  t 1X
  s=1
  [ms z(xs,✓)]⌦ xs ✓, (8)
  where ms is the ‘one-hot encoding’ vector of the user’s selection at round s, i.e., ms :=⇥ {ys = 1}, . . . , {ys = K} ⇤T . It will also be convenient to define the Hessian of L t (✓):
  Ht(✓) := IKd + t 1X
  s=1
  A(xs,✓)⌦ xsx T s , (9)
  where A(x,✓)ij := zi(x,✓) ij zj(x,✓) for all i, j 2 [K]. Equivalently, in matrix form
  A(x,✓) := diag(z(x,✓)) z(x,✓)zT(x,✓). (10)
  Note here that A(x,✓) is a matrix function that depends on ✓ and x via the inner products ✓̄ T 1 x, ✓̄ T 2 x, . . . , ✓̄ T Kx. Also, the matrix A(x,✓) has nice algebraic properties (discussed more in Section 3) that turn our to be critical in the execution and analysis of our algorithm.
  Now, we introduce assumptions on the problem structure, under which our theoretical results hold. Assumption 1 (Boundedness). Without loss of generality,kxk2  1 for all x 2 D. Also, ✓⇤ 2 ⇥ := {✓ 2 RKd :k✓k2  S} andk⇢k2  R. Both upper bounds S and R are known to the agent.
  The assumption that S is known is standard in the literature of GLBs. Knowledge of R is also reasonable to assume because ⇢i’s represent the revenue parameters that are typically known or set by the system operator. Assumption 2 (Problem-dependent constants). There exist strictly positive constants 0 < L < 1 and 0 <  < 1 such that sup
  x2D,✓2⇥ max A(x,✓) := L and infx2D,✓2⇥ min A(x,✓) := 1 .
  We comment further on the knowledge of  and L in Section 3. Here, we note that  is reminiscent of the corresponding quantity in binary logistic bandits which is defined accordingly as  := sup
  x2D,k✓̄k 2 S 1/µ̇(✓̄
  T x), where µ̇ is the first derivative of the logistic function µ(x) = 1/(1 +
  exp( x)). As Filippi et al. (2010); Li et al. (2017); Faury et al. (2020) have shown, this quantity plays a key role in characterizing the behavior of binary (K = 1) logit bandit algorithms. In this paper, we will show that the proper analogue of this quantity to multinomial (K > 1) logit bandit algorithms is the parameter  defined in Assumption 2.
sections.heading: 2.2 Confidence set around ✓⇤
sections.text: We introduce a confidence set Ct( ) that will include ✓⇤ with high probability thus allowing us to upper bound (x,✓t) in the following subsection. We start by defining the key quantity
  gt(✓) := ✓ + t 1X
  s=1
  z(xs,✓)⌦ xs. (11)
  To see why this is useful, note that by the first-order optimality condition r✓L t (✓̂t) = 0 we have ✓⇤ satisfying gt(✓⇤) gt(✓̂t) = ✓⇤ + st, with st := Pt 1 s=1 z(xs,✓⇤) ms ⌦ xs. This in turn motivates us to define a confidence set Ct at the beginning of each round t 2 [T ] such that
  Ct( ) := {✓ 2 ⇥ : gt(✓) gt(✓̂t)
  H 1 t (✓)
   t( )}, (12)
  where t( ) is chosen as in Theorem 1 below to guarantee ✓⇤ 2 Ct( ) with high probability 1 . Theorem 1 (Confidence set). Let the Assumption 1 hold and for 2 (0, 1), define t( ) := K3/2dp
  log (1 + td ) +
  p /K
  2 + 2K3/2dp log( 2 ) +
  p S. Then with probability at least 1 , for all
  t 2 [T ] it holds that ✓⇤ 2 Ct( ).
  Once we have properly identified the key quantities gt(✓⇤) and Ht(✓), the proof of the theorem above rather naturally extends Lemma 1 in Faury et al. (2020). Compared to the special case K = 1 studied in Faury et al. (2020), extra care is needed here to properly track the scaling of t( ) with respect to the new parameter K that is of interest for us. The details are deferred to Appendix A. To a great extent, the similarities between the binary and multinomial cases end here. It will turn out that bounding (x,✓t), for an appropriate choice of ✓t, is significantly more intricate here than in the binary case. Our main technical contribution towards this direction is given in the lemmas presented in Section 2.3 that are used to prove the following key result. Lemma 1. Let Assumptions 1 and 2 hold. For all x 2 D, t 2 [T ] and ✓ 2 Ct( ), with probability at least 1 :
  (x,✓)  2RL t( ) p  (1 + 2S)kxk
  V 1 t
  , (13)
  where Vt :=  I + Pt 1 s=1 xsx T s .
  The complete proof is in Appendix B. In the following section, we give a proof sketch.
sections.heading: 2.3 Proof sketch of Lemma 1
sections.text: To prove Lemma 1, we will use the high probability confidence set Ct( ) in (12) paired with the problem setting’s properties encapsulated in Assumptions 1 and 2. To see the key challenges in establishing (13), consider the following. By definition of (x,✓) in (3), Cauchy-Schwarz inequality, and Assumption 1, for any x 2 D, t 2 [T ], and ✓ 2 Ct( ):
  (x,✓)  Rkz(x,✓⇤) z(x,✓)k2. (14)
  Thus, our goal becomes relating kz(x,✓⇤) z(x,✓)k2 to gt(✓⇤) gt(✓̂t)
  H 1 t (✓⇤) and/or gt(✓̂t) gt(✓)
  H 1 t (✓)
  . The reason is that the two latter quantities are both known to be bounded
  by t( ) with high probability since ✓⇤ 2 Ct( ) with probability at least 1 (cf. Theorem 1). We accomplish our goal in three steps. First, in Lemma 2, we connect z(x,✓1) z(x,✓2) to ✓1 ✓2 for any x 2 Rd and ✓1,✓2 2 RKd. Lemma 2. For any x 2 Rd, ✓1,✓2 2 RKd, recall the definition of A(x,✓) in (10) and define
  B(x,✓1,✓2) :=
  Z 1
  0 A(x, v✓1 + (1 v)✓2)dv. (15)
  Then, we have z(x,✓1) z(x,✓2) = ⇥ B(x,✓1,✓2)⌦ xT ⇤ (✓1 ✓2).
  The proof of the lemma above in Appendix B.1 relies on a proper application of the mean-value Theorem. Next, in Lemma 3 below, we relate ✓1 ✓2 to gt(✓1) gt(✓2). Lemma 3. Let
  Gt(✓1,✓2) := IKd + t 1X
  s=1
  B(xs,✓1,✓2)⌦ xsx T s . (16)
  Then, for any ✓1,✓2 2 RKd, we have
  gt(✓1) gt(✓2) = Gt(✓1,✓2)(✓1 ✓2). (17)
  The proof in Appendix B.1 uses the definition of gt(✓), Lemma 2 and a proper application of the mixed-product property of the Kronecker product. Note that Gt(✓1,✓2) ⌫ 0; thus, it is invertible.
  Now, combining Lemmas 2 and 3, our new goal becomes bounding ⇥ B(x,✓⇤,✓)⌦ xT ⇤ G 1 t (✓⇤,✓) gt(✓⇤) gt(✓)
  2 . Our key technical contribution is es-
  tablishing good bounds for the spectral norm ⇥ B(x,✓⇤,✓)⌦ xT ⇤ G 1/2 t (✓⇤,✓)
  2
  and the
  weighted Euclidean norm gt(✓⇤) gt(✓)
  G 1 t (✓⇤,✓) . We start by briefly explaining how we bound the spectral norm above; see Appendix B.2 for details. By using the cyclic property of
  the maximum eigenvalue and the mixed-product property of the Kronecker product, it suffices to bound max ✓ G 1/2 t ⇣ B T B ⌦ xx T ⌘ G 1/2 t ◆ , where we denote B = B(x,✓⇤,✓) and
  Gt = Gt(✓⇤,✓) for simplicity. There are two essential ideas to do so. First, thanks to our Assumption 2, which upper bounds the eigenvalues of A(x,✓) by L, and by recalling the definition of B(x,✓1,✓2), we manage to show that (BBT )⌦ xx T L2 (IK ⌦ x) IK ⌦ xT . Our second idea is to relate the matrix Gt to the Gram matrix of actions
  Vt :=  Id + t 1X
  s=1
  xsx T s . (18)
  Specifically, using our Assumption 2 that the minimum eigenvalue of A(x,✓) is lower bounded by 1/ and standard spectral properties of the Kronecker product, we prove in Lemma 12 in the appendix that Gt ⌫ 1IK ⌦Vt or G 1 t IK ⌦V 1 t . By properly combining the above, we achieve the following convenient upper bound: [B(x,✓⇤,✓)⌦ xT ]G 1/2t (✓⇤,✓)
  2  L
  p kxk
  V 1 t
  . (19)
  To see why this is useful, note that compared to Ht(✓) in (9), which is a ‘matrix-weighted’ version of the Gram matrix, the definition of Vt in (18) is the same as the definition of the Gram matrix in linear bandits. Thus, we are now able to use standard machinery in Abbasi-Yadkori et al. (2011) to bound
  PT t=1kxtkV 1t .
  Finally, we discuss how to control the remaining term gt(✓⇤) gt(✓)
  Gt(✓⇤,✓) 1
  . By adding and
  subtracting gt(✓̂t) to and from the argument inside the norm, it suffices to bound gt(✓⇤) gt(✓̂t)
  Gt(✓⇤,✓) 1
  + gt(✓̂t) gt(✓)
  Gt(✓⇤,✓) 1
  . (20)
  To do this, we exploit the definition of Ct( ) in (12) by first relating the G 1t (✓⇤,✓)–norms with those in terms of H 1t (✓⇤) and H 1 t (✓). To do this, we rely on the generalized self concordance property of the strictly convex log-sum-exp (lse : RK ! R [1) function Tran-Dinh et al. (2015) lse(s) := log(1 + PK i=1 exp(si)). Notice that our z(x,✓) is the gradient of the lse function at point [✓̄T1 x, ✓̄ T 2 x, . . . , ✓̄ T Kx] T , that is z(x,✓) = rlse ⇣ [✓̄ T 1 x, ✓̄ T 2 x, . . . , ✓̄ T Kx] T ⌘ . Thanks to the
  generalized self-concordance property of the lse, upper bounds on its Hessian matrix (essentially the matrix Ht(✓)) have been developed in Tran-Dinh et al. (2015); Sun and Tran-Dinh (2019). Proper use of such bounds leads to lower bounds on Gt(✓⇤,✓) as follows. Lemma 4 (Generalized self-concordance). For any ✓1,✓2 2 ⇥, we have (1 + 2S) 1Ht(✓1) Gt(✓1,✓2) and (1 + 2S) 1Ht(✓2) Gt(✓1,✓2).
  The proof is given in Appendix B.1. Finally, plugging the above lower bounds on matrix Gt into (20) for ✓⇤ and ✓ gives the final bound on (x,✓) in Lemma 1.
sections.heading: 2.4 Error bound on (x,✓t)
sections.text: In this section, we specify ✓t and ✏t(x) for all t 2 [T ] and x 2 D. In view of Lemma 1, the exploration bonus ✏t(x) can be set equal to the RHS of (13), only if ✓t 2 Ct( ). Recall from the definition of Ct( ) in (12) that for ✓t 2 Ct( ), it must be that ✓t 2 ⇥. Since the ML estimator ✓̂t does not necessarily satisfy ✓̂t 2 ⇥, we introduce the following “feasible estimator":
  ✓t := argmin ✓2⇥ gt(✓) gt(✓̂t) H 1 t (✓) , (21)
  which is guaranteed to be in the confidence set Ct( ) for all t 2 [T ] since kgt(✓t) gt(✓̂t)kH 1t (✓) kgt(✓⇤) gt(✓̂t)kH 1t (✓) t( ) and ✓t 2 ⇥. Thus, we have proved the following.
  Corollary 1 (Exploration bonus). For all x 2 D and t 2 [T ], with probability at least 1 , we have
  (x,✓t)  ✏t(x) := 2RL t( ) p  (1 + 2S)kxk
  V 1 t
  . (22)
  Algorithm 1: MNL-UCB 1 for t = 1, . . . , T do 2 Compute ✓t as in (21). 3 Compute xt := argmaxx2D ⇢T z(x,✓t) + ✏t(x) with ✏t(x) defined in (22). 4 Play xt and observe yt.
  With these, we are now ready to summarize MNL-UCB in Algorithm 1. Remark 1. The projection step in (21) is similar to the ones used in Filippi et al. (2010); Faury et al. (2020) for binary logistic bandits. In particular, this step in Filippi et al. (2010) involves norms with respect to Vt instead of Ht(✓) (for K = 1). All of these involve non-convex optimization problems. Empirically, we observe that it occurs frequently that ✓̂t 2 ⇥. Then, ✓t = ✓̂t and these complicated projection steps do not need to be implemented.
sections.heading: 2.5 Regret bound of MNL-UCB
sections.text: In the following theorem, we state the regret bound of MNL-UCB as our main result. Theorem 2 (Regret of MNL-UCB). Fix 2 (0, 1). Let Assumptions 1 and 2 hold. Then, with probability at least 1 , it holds that RT  4RL T ( ) q 2max(1, 1  ) (1 + 2S) dT log(1 + T  d ). In particular, choosing = Kd log(T ) yields RT  O ⇣ RLKd log(T ) p T ⌘ .
  Now we comment on the regret order with respect to the key problem parameters T, d,K and p . With respect to these the theorem shows a scaling of the regret of Algorithm 1 as O(Kd log(T ) p T ). Specifically, for K = 1 we retrieve the exact same scaling as in Theorem 2 of Faury et al. (2020) for the binary case in terms of T, d and . In particular, the bound is optimal with respect to the action-space dimension d as O(d) is the optimal order in the simpler setting of linear bandits Dani et al. (2008). Of course, compared to Faury et al. (2020) our result applies for general K 1 and implies a linear scaling with the number K of possible outcomes that can be selected by the user. In fact, our bound suggests our algorithm on a K-multinomial problem has performance of same order as the performance of the algorithm of Faury et al. (2020) for a binary problem with dimension Kd instead of d. On the one hand, this is intuitive since the MNL reward model indeed involves Kd unknown parameters. Thus, we cannot expect regret better than O(Kd) for Kd unknown parameters. On the other hand, the MNL is a special case of multi-index models rather than a GLM. Thus, it is a-priori unclear whether it differs from a binary logistic model with Kd parameters in terms of regret performance. In fact, our proof does not treat the MNL reward model as a GLM. Despite that, it results to the linear order O(K) same as the optimal order of a binary logistic setting with Kd unknown parameters. Finally, as previously mentioned, the parameter  defined in Assumption 2 generalizes the corresponding parameter for binary bandits. As in Theorem 2 of Faury et al. (2020) our bound for the multinomial case scales with p . Next, we show how this scaling is non-trivial and improves upon standard approaches. Remark 2. Using same tools as for GLM-UCB in Filippi et al. (2010) for single-index reward models (K = 1), we can define the following alternative confidence set around the parameter ✓⇤ of the MNL model:
  Et( ) := ✓ 2 ⇥ : k✓ ✓̃tkṼ 1t   t( ) , (23)
  where t( ) is a slowly increasing function of t with similar order as t( ) (see Lemma 14 in appendix), Ṽt = IK ⌦Vt, and ✓̃t := argmin✓2⇥ kgt(✓) gt(✓̂t)kṼ 1t . Due to the appearance of an extra  factor above compared to (12), relying on Et( ) (23) in our analysis would lead to the following error bound (see Appendix C.2):
  (x, ✓̃t)  ✏̃t(x) := 2RL t( )kxkV 1t . (24)
  This bound is significantly looser compared to our bound in (22) since the parameter  can become arbitrarily large depending on the size of set D ⇥⇥.
sections.heading: 2.6 Improved MNL-UCB
sections.text: The regret of MNL-UCB scales as O( p ) with respect to . A more careful treatment of Ct( ) in (12) leads to Improved MNL-UCB, a modification of MNL-UCB, with a newly defined estimator and improved exploration bonus. Compared to MNL-UCB, the new algorithm is computationally intractable. Yet, it is interesting from a theory perspective as we show a regret bound where the -dependence is pushed into a quickly-vanishing second order term, trading-off a slight increase in the regret’s dependence on K. In particular, we prove improved regret of order O(K1.5d p T log(T ) + K2d log(T )). Due to space limitations, we defer a detailed description (see Algorithm 2) and analysis (see Theorem 3) of Improved MNL-UCB in Appendix D.
sections.heading: 3 Discussion on  and L
sections.text: Knowledge of the problem-dependent constants  and L is required to implement MNL-UCB as they appear in the definition of ✏t(x) in (22). While specifying their true values (defined in Assumption 2) requires solving non-convex optimization problems in general, here we present computationally efficient ways to obtain simple upper bounds. Also, we show that  can indeed scale poorly with the size of D ⇥ ⇥ by deriving an appropriate lower bound for it. The upper bound on L is rather straightforward and it can be easily checked that L  maxx2D e Skxk2
  1+eSkxk2+(K 1)e Skxk2 . Next, we focus on upper/lower bounding , which is more interesting.
  In (26), we will show that  scales unfavorably with the size of the set D ⇥ ⇥. In our regret analysis in the previous sections, it was useful to assume in Assumption 1 that kxk2 1. This assumption was without loss of generality because of the following. Suppose a general setting with X = maxx2Dkxk2> 1. We can then define an equivalent MNL model with actions x̃ = x/X and new parameter vector ✓̃ = X✓. The new problem satisfies the unit norm constraint on the radius of D and has a new parameter norm bound S̃ = SX . For clarity with regards to the goal of this section, it is convenient to keep track of the radius of D (rather than push it in S). Thus, we let X := maxx2Dkxk2 (possibly large). We will prove that  grows at least exponentially in SX , thus it can be very large if the action decision set is large.
  In order to bound , we identify and take advantage of the following key property of A(x,✓) stated as Lemma 5. Recall that a matrix A 2 RK⇥K is strictly diagonally dominant if each of its diagonal entries is greater than the sum of absolute values of all other entries in the corresponding row/column. We also need the definition of an M -matrix: A matrix A is an M -matrix if all its off-diagonal entries are non-positive and the real parts of its eigenvalues are non-negative Berman and Plemmons (1994). Lemma 5. For any x 2 Rd and ✓ 2 RKd, the matrix A(x,✓) in (10) is a strictly diagonally dominant M -matrix.
  This key observation (see Appendix C for the proof) allows us to use Theorem 1.1 in Tian and Huang (2010) that provides upper and lower bounds on the minimum eigenvalue of a strictly diagonally dominant M -matrix. Specifically, we find that for all all x and ✓:
  min i2[K]
  KX
  j=1
  A(x,✓)ij  min(A(x,✓))  max i2[K]
  KX
  j=1
  A(x,✓)ij . (25)
  Starting from this and setting X := maxx2Dkxk2 we show the following bounds (Appendix C.4):
  e SXp K (1 +Ke SXp K )2    eSX(1 +KeSX)2. (26)
sections.heading: 4 Experiments
sections.text: We present numerical simulations to complement and confirm our theoretical findings. In all experiments, we used the upper bound on  in (26) to compute the exploration bonus ✏t(x).
  We evaluate the performance of MNL-UCB on synthetic data. All the results shown depict averages over 20 realizations, for which we have chosen = 0.01, d = 2, and T = 1000. We considered time-independent decision sets D of 20 arms in R2 and the reward vector ⇢ = [1, . . . ,K]T . Moreover,
  the arms and ✓̄⇤i are drawn from N (0, Id) and N (0, Id/K), respectively. The normalization of the latter by K is so that it guarantees that the problem’s signal-to-noise ratiok✓⇤k2 does not change with varying K. Figure 1a depicts the average regret of MNL-UCB for problem settings with different values of K = 1, 2, 3. The plot verifies that larger K leads to larger regret and seems to match the proved scaling of the regret bound of MNL-UCB as O(K) with respect to K. Figure 1b showcases the average regret of MNL-UCB for problem settings with fixed K = 2 and different values of  = 30, 60, 100 (upper bounds computed using (26)). Observe that larger  leads to larger regret. This is consistent with our theoretical findings on the impacts of  on the algorithm’s performance. Finally, Figure 1c emphasizes the value of using the exploration bonus ✏t(x) in (22) compared to ✏̃t(x) introduced in (24) in the UCB decision making step. In this figure, we fixed K = 2 and the average regret curves are associated with a problem setting with  = 30. A comparison between regret curves further confirms the worse regret performance of MNL-UCB when it exploits ✓̃t and ✏̃t(x) rather than ✓t and ✏t(x) in the UCB decision rule at Line 3 of the Algorithm 1.
sections.heading: 5 Conclusion
sections.text: For the MNL regression bandit problem, we developed MNL-UCB and showed a regret Õ(Kd p  p T ) that scales favorably with the critical problem-dependent parameter  and optimally with respect to the number of options K. We further proposed Improved MNL-UCB that achieves a regret bound with problem-dependent constant  being pushed into a second order logarithmic term, trading-off a slight increase in the regret’s dependence on K. After this work was completed, we became aware of Abeille et al. (2021) that improves Faury et al. (2020) in the binary case. Our work shows that extension of Faury et al. (2020) to MNL model is non-trivial and requires several careful analysis adjustments. It is an exciting future direction to investigate whether the algorithmic improvements of Abeille et al. (2021) can be properly adjusted in the multiclass case of interest here. In light of our discussion after Theorem 2 in Section 2.5, another promising future direction is to determine a lower bound that formally justifies the optimal dependence is O(K) or determine an improved algorithm/analysis that lowers the dependency on K. It is also interesting to study the efficacy of Thompson sampling-based algorithms for this new problem. Also, extending our results to other multi-index models is yet another important future direction.
  Acknowledgments and Disclosure of Funding
  This work is supported in part by the National Science Foundation under Grant Number (1934641). Part of this work was completed while the second author was affiliated with the University of California, Santa Barbara.
title: UCB-based Algorithms for Multinomial Logistic Regression Bandits