UCB-based Algorithms for Multinomial Logistic Regression Bandits
Authors: Sanae Amani
Christos Thrampoulidis
Venue: NeurIPS 2021 Poster (2021)
Keywords: Generalized Linear Bandits
Logistic Bandits
Multinomial Logit (MNL)
Upper Confidence Bound

Abstract: 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. For this problem, we present MNL-UCB, an upper confidence bound (UCB)-based algorithm, that achieves regret $\tilde{\mathcal{O}}(dK\sqrt{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.

UCB-based Algorithms for Multinomial Logistic Regression Bandits
Sanae Amani University of California, Los Angeles samani@ucla. edu
Christos Thrampoulidis University of British Columbia cthrampo@ece. ubc.
Abstract
Out of the rich family of generalized linear bandits, perhaps the most well studied ones 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 possible outcomes (e.g.. 'click' '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 + 2 2 possible outcomes (+1 stands for the 'not click' outcome): we assume that for learner's action Xx, the user selects one of K + 2 outcomes, say outcome with MNL probabilistic model with corresponding unknown parameter 0... Each outcome is also associated with a revenue parameter Ps 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 /T) (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.
Introduction
Linear stochastic bandits provide simple, yet commonly encountered, models for a variety of sequen- tial eeciiiionmmking problems under uncertainty. Specifically, linear bandits generalize the classical multi-armed bandit (MAB) problem of arms that each yields reward sampled independently from underlying distribution with unknown parameters, of each arm a linear function that depends on the same unknown parameter vector Dani et al. Abbasi-Yadkori (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 al. (2013): Avner and Mannor (2019): Berkenkamp 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 statisties.
setting where the expected reward
GLMss the expected reward associated with an arm x is given
by 1 x). where O E Id is the system unknown parameter and fi 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 ((xx)= = (1 + exp(-x))- UCB-based algorithms for GLBS were first introduced Filippi et (2010); et al. (2017); Faury et (2020). The same problem, but with Thompson Sampling- (TS) strategy was also studied in Abeille et al. (2017);
35th Conference on Neural Information Processing Systems (NcurIPS 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 al. (2017); Gamarnik and Gaudio (2020) for a list of applications in statistics). A semi semi-parametric index model relates the reward y E R. and the action/arm x E R as y = y x, 0"x,.....0k* where J : IR
0xxx + c,
R and 0 ,,,.. ...... 0x E Rd are K system's 's unknown parameters. GLBBs 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.c., special case 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 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 '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 UCBis by Faury al. (2020) to the settings with MIM rewards brings to our theoretical analysis. We then summarize our proposed MNL.-UC in Algorithm 1 and provide regret bound for it in Section 2.5. In Section 3, we present 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. ||x|| denotes the Euclidean norm and x y inner product. 6, denotes the Kronecker delta, i.e., 6;z = 1 if i # j and 5,3 = 0 if = j. A @ B denotes the Kronecker product. For square matrices A and B, use A = B to denote B- A is positive nemi-defiite. We denote the minimum and maximum eigenvalues of A by Amin (A) and (mxxx(A), For A 2 O, the weighted 2-norm of v with respect to A is defined by ||||/|| = VUT Av. For positive integers n and m S n, [n]] and [m n] denote the sets
} and {m,... m}. respectively. For any E IR Kd D; V((i-1)d+1id E Rd denotes the vector containing the i-th set of d entries of v. We use 1 and e; to denote the vector of all I's and the i-th standard basis vector, respectively. Finally, we use Ô for big-Oh -hg notation that ignores logarithmic factors.
1.1 Problem formulation
Reward Model. The agent is given decision set' D C Rd. At each round f, the agent chooses an action X2 E 'D and observes the user purchase decision y E [K] U {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 F, = (Fo, of (xs: ys )==)), where Fu represents any prior knowledge. Let each option
i e [K] be associated with an unknown vector 0., E Rd and let 0. 10" 0 " 0- 0²xx| 1T E Bd 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
i = 0,
1+ exp(O) x1)
Plye = i i(x,, =
exp I x.)
0xx))
i E [K].
1+ exp
When the user clicks on the i-th option, a corresponding reward pa revealed to the agent and we set Po = O. Then, the expected reward observed by the agent when she plays action x, is
OOur results extend easily to time- varying decision sets.

---

Σラ= 1+2 1 expl 0 ,xx))
expl 1,xx)
E X Fil
=p' p²z(xx,,0x) where p = ,Kl", z(x(, =
(x,, 02),22(x1: (x))x.0)) .............................. (x: 0,)l". ".]]"andd
z [x,, 0.) = P(ye = Ft). Vi [K].
(2)
Note that E, X,, Fil ,0 x, xx 0xxxx is not directly generalized linear model, i.e., function 100" xt). but rather it is multi-index model, where R - R.
Goal. Let 7 be the total number of rounds and be the optimal action that maximizes the reward in expectation, i.e., X, arg maxxED p 0x 0.). The agent's goal is to minimize the cumulative pseudo-regret defined by Rt = I (x. O.) p²'z(x,,0)
1.2 Contributions
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 + > 2 options (+1 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 k. which we interpret as the degree smooth for larger values of of the MNL model over the agent's '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.
-mootthhsssssss (less
We develop a UCB-type algorithm for MNL logistic regression bandits. At every step, the algorithm decides the inclusion of K-tuple of parameter vectors ........ 0. K in the confidence region in way that captures the local smoothness the MNL. model around this K-tuple and past actions. We show that this is critical for the algorithm's 's favorable regret performance in terms of
Specifically, we prove that the regret of our MNL-UCB scales Ö(dK /KVT). 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 VR. 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 Sebeem-depennent constant being pushed into second order term that vanishes quickly. We complement our theoretical results with numerical simulations and corresponding discussions on the performance of our algorithm.
1.3 Related works
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 μu. All these works provide regret bounds (RV/T), where the multiplicative factor k is a problem-depender constant and characterizes the degree of non-linearity of the link function.
Logistic Bandits. In Faury et (2020), the authors focused on the logistic bandit problem as a special case of GL.Bs. By introducing novel Bernstein-like self normalized martingale tail- mill-nequullty, they reduced the dependency of the existing GLB algorithms' regret bounds on the constant k by a factor of V and obtained a Odv kT) 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 regret of (dVT))
Multinomial Logit Bandits. In 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 combinatorial variant of the bandit problem. In this problem, the agent chooses so-called assortment which is a subset of a set = [N] of N items. At round feature vectors Xa, for every item E S, are revealed to the agent, and given this contextual information, the agent selects assortment S, C S
3

---

and observes the user choice y1 = i St U {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 0. E TRu such that the probability that the user selects item i St is exp(0, xa) (1] Eies, exp(O- x )). Furthermore, a revenue parameter denoted by Ta for each item i is also revealed at round l. The goal of the agent to offer assortments with size most K maximize the expected cu- mulative revenue or to minimize the cumulative regret Σ (s 0.) Rs, 0.), where
Re (S, = Tit exp(0" xx) 1///(1++isss Dies, exp(0 (0, x.)). Finally, the closely related paper Cheung and Simchi-Levi (2017) studies a problem where at each round, the agent observes a user- specific context based which, it recommends 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 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 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).
2 Multnomial Logit UCB Algorithms
In this section, we introduce two key quantities: (i) 0,, an estimate of 0.: (ii) (x)), an exploration bonus for each x DD at each round & E [T]. Based on these, we design a UCB-type algorithm, called MNL-UCB. At each round I, the algorithm computes an estimate O, of O.. that we present in Section 2.4. For each x E and E [T), let ex(x) be such that the following holds with high probability:
A(x, 0₂) == 10" z0x, 0.) p" z(x, 0,)15 (x).
At round f, having knowledge of ce (x). the agent computes the following upper bound on the expected reward pT 2xx, 0.) for all D:
p p"z 1x S pT z(zxx, O.) (x).
(4)
Then, the learner follows UCB decision rule select action x, according to the following rule:
X == arg max p" zxx 0,) - =x()..
(5)
XED
To see how the UCB decision rule (5) helps us control the cumulative regret, we show how controls the instantaneous regret by the following standard argument Abbasi- Yadkori et al. (201 1); Faury et al. (2020):
(4) z(x,, 0.) S ('z(x,;0 0,) + =x((xx)= - pT z(xx. 0.)
Tt p" z(,,,,, 0.) - -0))-==z((e
55) S p''z(x,,0) 0.) - p² 2x 0.) + (x,) S (xx)
(6)
In view of this, our goal is to design an algorithm that appropriately chooses the estimator O, and the exploration bonus (x) such that its regret sub-linear.
2.1 Maximum likelihood estimate
The problem of estimating 0,, at round t given F, is identical to a multi-class linear classification problem, where 0.; is the "classifier" for class i. A natural way to compute the estimator of the unknown parameter 0, of the MNL. model given F, is to use the maximum likelihood principle. At round the regularized log-likelihood (aka negative cross-entropy loss) with regularizer À > 0 writes
t-1 K
C) = Σ>
1lv. = i) log (zi 0)) 1
(7)
s=1 0=

---

Then, the maximum likelihood estimate of 0. is defined as 0, := arg max, (0). Taking the gradient of (7) with respect we obtain
V Vol
Σ m. 2(x,, 0) ~0,
(8)
where m, is the 'one-hot encoding' vector of the user's selection at round 8, i.e. m,
[1 li.... 1 K3]" It will also be convenient to define the Hessian of C))
t-1 E Ax. 0) @ x,x
H.(0)= AIaa +
(9)
where Axx, 0lis = 2x 0) (6ig - 23 (x, 0)) for all i, E [K]. Equivalently, in matrix form A 0) =- diag(z(x, 0)) z(x, 0)z² 1/xT(x 0).
(10)
Note here that A(x, 0) is matrix function that depends O and via the inner products 0_ x, 8 x, ..., 0 Also, the matrix (xx 0) 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, ||x||| for all D. Also, O, e {0 E kKd :10111 I S} and]|pll2 R. Both upper bounds S and R are known the agent.
The assumption that S' is known is standard in the literature of GLBs. Knowledge of R is also reasonable assume because p; 's represent the revenue parameters that are typically known or set by the system operator.
Assumption 2 Prroblem-dependenttommsse constants). There exist strictly positive constants O < < oc and 0 Dc such that supxED, Amax (A(x, 0)) L and infxED,ece Amin (A(x, 0)) +
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 SUP ss i/i x), where ju 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 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 Assumption 2.
2.2 Confidence set around 0.
We introduce confidence set (8) that will include 0, with high probability thus allowing us to upper bound (xx, 0,) in the following subsection. We start by defining the key quantity
1-1 Σ z(x,, 0) x..
g 00
(11)
To why this is useful, note that by the first-order optimality condition (oC)(0.) 0 have 0, satisfying g, (0.) g. (0.) X0, + s,, with s, == Σ (z(x,, 0.) m.) & x,, This in turn motivates us define a confidence set C, the beginning of each round t [T' such that
(, == (0 e (0) (())
$ B,())))
(12)
H. ((0)
where 3,(8) is chosen in Theorem below to guarantee O, (ō) with high probability 1 8. Theorem 1 (Confidence set). Let the Assumption 1 hold and for E (0, 1), define Be(8)
K3/2d
VN/K + 2k3/2dd log(?) + VAS. Then with probability at least 8, for all VX log (1 + + 2 VA
t [T] it holds that 0. e C,))).
5

---

Once we have properly identified the key quantities g: (0.) and (O),), the proof of the theorem above rather naturally extends Lemma in Faury 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 (8) with respect to the new parameter K that is of interest for us. The details are deferred to Appendix A. To great extent, the similarities between the binary and multinomial cases end here. It will turn out that bounding A (xx, 0z), for an appropriate choice of 0r. 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 and hold. For all x D, t E [T] and C((8), with probability at least 1 - 8:
A(x, 0) S 2RL3 (1+ (5) x
(13)
where V == RAT + x
The complete proof is in Appendix B. In the following section, we give proof sketch.
2.3 Proof sketch of Lemma
To prove Lemma I, we will use the high probability confidence set (o) in (12) paired with the problem setting's s properties encapsulated in Assumptions I and 2. To see the key challenges in establishing (13), consider the following. By definition of A 0) in (3), Seucch--Shwaar inequality,
and Assumption for any D, t [T), and 0 C,(ō):
A 0) < Zx 0.) z(x, 0)122
(14)
Thus, our goal becomes relating ||z(x, +.) zxx. 0)11 to [..()))
g.) -0.)))
(0.) and/or
[g()))) ge (0)
H, (0) The reason is that the two latter quantities are both known to be bounded
by (5) with high probability since 0_ E (6) with probability at least (ef. Theorem 1). We accomplish our goal in three steps. First, in Lemma 2, we connect z(x, 01) z(x, 02) to 0 O2 for any x E &d and 01, 02 E kd
Lemma 2. For any x E Rd, 01, E Rd,, recall the definition of A(x,(x 0) in (10) and define
0x, 02) = //' A(x, 00, + - o)))dd.
(15)
Then, we have z(x, 01) - z(x, 02) [B 0, 02) x²" (0) -0))
The proof of the lemma above in Appendix B. relies on a proper application of the maan-value Theorem. Next, in Lemma 3 below, we relate 0 O2 to (0,) (02)).
Lemma 3. Ler
G. 02) AlRa + Σ
B 01,0, @ x,x!
(16)
Then, for any 01, 02 R we have
g (0))) g: (02) = (e( - -02).
(17)
The proof in Appendix B.1 uses the definition of g. (0), Lemma and proper application of the mixed-product property of the Kronecker product. Note that G. 02) > 0; thus, it is invertible.
Now, combining Lemmas
2 and 3, our new goal becomes bounding [ 0., 0) 8 x"" G., (0.) g: (0)) Our key technical contribution is es- tablishing good bounds for the spectral norm [B(x, 0., 0) 8 x"] [x'"),"''' G. /) and the weighted Euclidean norm [|g. (0)lle,, '0) We start by briefly explaining how we bound the spectral norm above; Appendix B.2 for details. By using the eyclie property of

---

the maximum eigenvalue and the mixed mixed-produs product property of the Kronecker product, it suffices
G 1/2 BB" & (xx") G 1/2 where we denote B = ( O., 0) and
to bound Amax
G2 (., 0) for simplicity. There are two essential ideas to do so. First, thanks our Assumption 2, which upper bounds the eigenvalues of A(x, 0) by L, and by recalling the definition
of (x, 1 02), we manage to show that (BB") & (xx*) N 1 (TK 69 x) (TK 09 x² x²). Our second idea to relate the matrix G2 to the Gram matrix of actions
t-1
v= := KAla + Xxx,
(18)
Specifically, using our Assumption 2 that the minimum eigenvalue of A(x, 0) is lower bounded by 1/k Is and standard spectral properties of the Kronecker product, we prove in Lemma 12 in the appendix that G2 = 1
x I & Vi or G, <KI&& @ V By properly combining the above, we achieve the
following convenient upper bound:
B(x, 0., 0) 2 T G (0.,
(0., 001, S LLvR|lxIlV.
(19)
To see why this is useful, note that compared to ()( in (9), which is a 'matrix- -nerrx--eeihhtd" version of the Gram matrix, the definition of Ve in (18) is the same as the definition of the Gram matrix in linear bandits. Thus, bound Ei Xx lv.".
now able to use standard machinery in Abbasi- Yadkori al. (2011) to
Finally, we discuss how to control the remaining term g. (0.) - (0) G.(00.0)-1 By adding and subtracting (0,) to and from the argument inside the norm, it suffices to bound
g: (o.) - (0.) G)( + g: -000:++//00000 - g:) (0.0000--1
(20)
To do this, exploit the definition of (5) in (12) by first relating the GT (). normm with those in terms of H, and ((). To do this, we rely the generalized self concordance
property of the strictly convex log-sum-exp (Isc : IRK + R U oo) function Tran-Dinh et al. (2015)
Ise(s) == log(1 + Σ exp(s.)). Notice that our zxx, 0) is the gradient of the lse function at point 10, 0x. xxx]"" that is z(x, 0) = Vlse [0] x, x'x,,..00xx""")
0xx("))
Thanks to the generalized self collodanneee property the Ise, upper bounds on its Hessian matrix (essentially the matrix (O)) have been developed in Tran-Dinh et al. (2015); Sun and Tran-Dinh (2019). Proper use of such bounds leads lower bounds on G. 0) as follows.
Lemma 4 (Generalized self-concordance). For any 02, 02 E O, we have (1 + 28)--H,(O0) v G (0,,,0 02) and (1 + 25) - (02) I (0).
The proof is given in Appendix B.1. Finally, plugging the above lower bounds on matrix G, into (20) for 0, and gives the final bound on A(x, 0) Lemma
2.4 Error bound on A O.)
In this section, we specify 0, and c,(x) for all t E [T] and x E DD_ In view of Lemma 1, the exploration bonus (x(x) can be set equal the RHS of (13), only if O, C,()). Recall from the definition of (5) in (12) that for 0, E C,))), must be that O, E O. Since the ML. estimator 0, does not necessarily satisfy 0, E θ, we introduce the following "feasible estimator":
0: == arg min dc
(0) (:))))
(21)
which is guaranteed be in the confidence set (5) for all E [T] since (0.) - (+.))
(000)))((0)))) (0)
(0.) )- g (,,0)llm,;) S (6) and 0, E O. Thus, we have proved the following.
Corollary 1 (Exploration bonus). For all x E D and t E [T]. with probability at least - 6, we have
A(x, S (x()) = 2RI.3.05) R 25 Iv.
(22)
7

---

Algorithm 1: MNL-UCB
for f 1,..., T do
Compute 0g as in (21).
Compute arg M (2 01) + (x) with (x) defined in (22).
Play x, and observe y/-
With these, we are now ready to summarize MNL-UCB in Algorithm 1.
Remark 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 V, instead of H, (0) (for K 1). All of these involve non-convex optimization problems.
Empirically, we observe that it occurs frequently that O₂ E O. Then, 0, = 0g and these complicated projection steps do not need to be implemented.
2.5 Regret bound of MNL-UCB
In the following theorem, we state the regret bound of MNL-UCB as our main result. Theorem 2 (Regret of MNL-UCB). Fix E (0, Let Assumptions and 2 hold. Then, with probability at least 1-ô, 6, it holds that Pr S <4RL3T(0)) max(1, )x + 25) d' log(1 + A In particular, choosing À = Kollog(T) yields Rr S O [I.Kdlog(TT)
Now we comment on the regret order with respect to the key problem parameters T, d, K and Vk. With respect to these the theorem shows a scaling of the regret of Algorithm 1 as O (o)oo Specifically, for K for the binary case in terms of T. dl and k. In particular, the bound is optimal with respect to the action-space dimension d as ( is the optimal order in the simpler setting linear bandits Dani et al. (2008). Of course, compared to Faury et al. (2020) our result applies for general K 2 1 and implies linear scaling with the number K of possible outcomes that can be selected by the user. In fact, our bound suggests 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 special case of multi-index models rather than 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 GLM. Despite that, 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 generalizes the corresponding parameter for binary bandits. As in Theorem of Faury et al. (2020) our bound for the multinomial case scales with VK. Next, we show how this scaling is non-trivial and improves upon standard approaches.
we retrieve the exact same scaling as in Theorem of Faury et al. (2020)
algorithm
K K--mulinomial problem has performance of same order
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 0, of the MNL model:
66 = (0 e ||0 B (o))))
(23)
where (5) slowly increasing function of with similar order as (,) (see Lemma 14 in appendix), V. = Is @ V., and 0, := arg minggee (() g,(0.)ll,,- Due to the appearance of an extra x factor above compared to (12), relying E,( (23) in our analysis would lead to the following error bound (see Appendix C.2):
A(x, 0.) S (x) := (f)
(24)
This bound is significantly looser compared to our bound in (22) since the parameter e can become arbitrarily large depending on the size of set D θ.
8

---

2.6 Improved MNL-UCB
The regret of MNL-UCB scales as ((VR) with respect to K. A more careful treatment of ()) in (12) leads to Improved MNL-UCB, modification of MNL-UCB, with newly defined estimator and improved exploration bonus. Compared MNL-UCB, the new algorithm is computationally intractable. Yet, it is interesting from a theory perspective as we show a regret bound where the x-dependence is pushed into quickly-vanishing second order term, trading-off slight increase the regret's 's dependence on K. In particular, we prove improved regret of order d......oy/llooo kK (og())) Due to space limitations, we defer detailed description (see Algorithm 2) and analysis (see Theorem 3) of Improved MNL-UCB in Appendix D.
+
3 Discussion on K and L
Knowledge of the problem-dependerr constants and L is required to implement MNL-UCB as they appear in the definition of (x() in (22). While specifying their true values (defined Assumption 2) requires solving non-convex optimization problems in general, here efficient ways to obtain simple upper bounds. Also, we show that K can indeed scale poorly with the size of D θ by deriving appropriate lower bound for it. The upper bound on L is rather
present computationally
-9112
straightforward and it can be easily checked that < maxxeD 14e 17e 8x12 Next, we
focus on upper/lower bounding K, which is more interesting.
In (26), we will show that к scales unfavorably with the size of the set D O. In our regret analysis in the previous sections, it was useful to assume in Assumption 1 that ||x||> 1. This assumption was without loss of generality because of the following. Suppose general setting with X = max ||||>>> 1. We can then define an equivalent MNL model with actions X = x/XX and new parameter vector 0 X0. The new problem satisfies the unit norm constraint on the radius of 'D and has new parameter norm bound Š = SX. For clarity with regards to the goal of this section, convenient to keep track of the radius of DD (rather than push it in S). Thus, we let X = m |x|| (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 K. we identify and take advantage of the following key property of A A(x, 0) stated as Lemma Recall that matrix A E R R 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 E Rdd and O E Rdd, the matrix A(x, 0) 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 the minimum eigenvalue of a strietly diagonally dominant M-matrix. Specifically, we find that for all all x and 0:
K
min K
( O) S
0)) I max A(x,
(25)
1=1
Starting from this and setting X == maxxeD||x||_ we show the following bounds (Appendix C.4):
CVR
1 + Ke
v J k SX (1+ ( K25
(26)
4 Experiments
We present numerical simulations to complement and confirm our theoretical findings. In all experi- ments, we used the upper bound on i in (26) to compute the exploration bonus (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, = 2, and T = 1000. We considered iime-independent decision sets D of 20 arms in 2²2 and the reward vector p [L, [L..... KJT. Moreover,

---

30
40
MNI--UC with 600) MNI.-UIC
Regret, R
100
60
20
40
10
500 Iteration,
100
500 Iteration, f
100C
500 Iteration,
1000
(a) MNL-UCB, 30
(b) MNL-UCB, K
(c) K 30,
Figure I: The shaded regions show standard deviation around the average over 20 problem realizations. See text for detailed description.
the arms and 0.; are drawn from (0, Ia) and (V( Ia/K), respectively. The normalization of the latter by K is so that it guarantees that the problem's 's signal-to-noise ratio 0a.o//0..1 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 MNI.-UCB as O ((K) with respect to K. Figure 1 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 's performance. Finally, Figure emphasizes the value of using the exploration bonus c((x) (22) compared to (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 K 30. A comparison between regret curves further confirms the worse regret performance MNL-UCB when it exploits 0, and & (x) rather than 0 and c, (x) in the UCB decision rule at Line 3 of the Algorithm 1.
5 Conclusion
For the MNL regression bandit problem, we developed MNL-UCB and showed regret O(Kd/RVTT that scales favorably with the critical problem-dependent parameter k and optimally with respect to the number of options K. We further proposed Improved MNL-UCB that achieves regret bound with problem-dependent constant being pushed into a second order logarithmic term, trading-off slight increase in the regret's dependence on K. After this work was completed, we became aware of Abeille 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.
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 lower bound that formally justifies the optimal dependence is O(K) or determine improved algorithm/analysii that lowers the dependency on K. is also interesting to study efficacy of Thompson sampling-basee 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.
References
Abbasi-Yadkori, Y., Pál, D., and Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312-2320.
10

---

Abeille, M., Faury, L.. and Calauzènes, C. (2021). Instance-wise minimax minimax-optimal algorithms for logistic bandits. In International Conference on Artificial Intelligence and Statistics, pages 3691-3699. PMLR.
Abeille, M., Lazaric, A., al. (2017). Linear thompson sampling revisited. Electronic Journal of Statistics, 112):5165-5197.
Agrawal, P., Avadhanula, V., and Tulabandhula, T. (2020). A tractable online learning algorithm for the multinomial logit contextual bandit. arXiv preprint arXiv:2011.14033.
Agrawal, S., Avadhanula, V., Goyal, V., and Zeevi, A. (2017). Thompson sampling for the mnl-bandit.
In Conference on Learning Theory, pages 76-78.
Agrawal, S., Avadhanula, V., Goyal, V., and Zeevi, A. (2019). Mnl-bandit: A dynamic learning approach assortment selection. Operations Research, 67(5):1453-1485 14855
Avner, O. and Mannor, S. (2019). Multi-user communication networks: coordinated multi-armed bandit approach. IEEE/ACM Transactions Networking, 27(6):2122-2077.
Berkenkamp, Krause, A., and Schoellig, A. P. (2016). Bayesian optimization with safety con- straints: safe and automatic parameter tuning in robotics. arXiv preprint arXiv:1602.0m 04450.
Berman, A. and Plemmons, R. J. (1994). Nonnegative matrices in the mathematical sciences. SIAM.
Chen, X., Wang, Y., and Zhou, Y. (2018). Dynamic assortment optimization with changing contextual information. arXiv preprint arXiv: 13069.
Cheung, W. C. and Simehi-Levi, (2017). Thompson sampling for online personalized assortment optimization problems with multinomial logit choice models. Available at SSRN 3075658.
Dani, V., Hayes, T. P., and Kakade, S. M. (2008). Stochastic linear optimization under bandit feedback. In Conference on Learning Theory.
Dong, K., Li, Y., Zhang, Q., and Zhou, Y. (2020). Multinomial logit bandit with low switching cost. arXiv preprint arXiv:2007.0487
Dong, S. and Van Roy, B. (2018). An information-theoretic analysis for thompson sampling with many actions. In Advances in Neural Information Processing Systems, pages 4157-4165.
Faury, I.,, Abeille, M., Calauzenes, C., and Fercoq, (2020). Improved optimistic algorithms for logistic bandits. arXiv preprint 20Xiv:2002.07530.
Filippi, S., Cappe, O., Garivier, A., and Szepesvári, C. (2010). Parametric bandits: The generalized linear case. In Advances in Neural Information Processing Systems, pages 586-594.
Gamanik, D. and Gaudio, J. (2020). Estimation of monotone multi-index models. arXiv preprint arXiv:2006.02806.
Horn, R. A. and Johnson, C. R. (2012). Matrix analysis. Cambridge university press.
Lattimore, T. and Szepesvári, (2020). Bandit algorithms. Cambridge University Press.
Li, L., Lu, Y., and Zhou, D. (2017). Provably optimal algorithms for generalized linear contextual bandits. arXiv preprint arXiv: 1703000703.00048.
Li, S., Hao, Li, M., and Kim, H.-C. (2013). Medicine rating prediction and recommendation in mobile social networks. In International conference on grid and pervasive computing, pages 216-223. Springer.
Oh, M.-h. and Iyengar, G. (2019). Thompson sampling for multinomial logit contextual bandits. In Advances in Neural Information Processing Systems, pages 3151-3161.
Rusmevichientong, and Tsitsiklis, N. (2010). Linearly parameterized bandits. Mathematics of Operations Research, 3511)

---

Russo. D. and Van Roy. B. (2013). Eluder dimension and the sample complexity of optimistic exploration. Advances in Neural Information Processing Systems, pages 2256-2266
Russo, D. and Van Roy, B. (2014), Learning to optimize via posterior sampling. Mathematics of Operations Research, 39(4):1221-144)
Sui, Y., Zhuang, V., Burdick, J. W., and Yue, Y. (2018). Stagewise safe bayesian optimization with gaussian processes. arXiv preprint 1xXiv:/806.07555
Sun, T. and Tran-Dinh, Q. (2019). Generalized self-concordant functions: a recipe for newton-type methods. Mathematical Programming. 1751-23)
Tian, G.-X. and Huang, T.-Z. (2010). Inequalities for the minimum eigenvalue of m-matrices. The Electronic Journal of Linear Algebra, 20.
Tran-Dinh, Q. Li, Y.-H., and Cevher, V. (2015). Composite convex minimization involving self- concordant-like cost functions. Modelling, Computation and Optimization Information Systems and Management Sciences, pages 155-168. Springer.
Wang, Y., Chen, X., and Zhou, Y. (2018). Near-optimal policies for dynamic multinomial logit assortment selection models. In Advances in Neural Information Processing Systems, pages 3101-3110.
Yang, Z., Balasubramanian, K., Wang. Z., and Liu, H. (2017). Learning non-gaussian multi-index model via second-order stein's method. Advances in Neural Information Processing Systems, 30:6097-6106
12


Reviews:
[{"review_id": "zZ1dSaB6rUE", "reviewer": "Reviewer_yP7L", "summary": "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. \n\nThe 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.", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written and easy to understand. The problem setting is stylistic but well-motivated. I am convinced that this variant of the MNL problem is worth attention from the research community. My biggest concern, however, is the technical contribution to the community. \n\nWhat is the technical novelty that the authors have shown on top of the existing techniques in the logistic bandits shown in Faury et al. (2020)? Generalization to the multinomial setting from logistic setting using Faury et al. (2020) appears to be fairly straightforward. Can you elaborate on what is technically difficult in such a generalization?\n\nAlso, the paper does not mention a recent work on MNL contextual bandits Agrawal et al. (2020) which studies the combinatorial setting, hence a different problem, but still leverages the work of Faury et al. (2020) to establish improved regret bounds.\n\n- Faury et al. (2020), Improved Optimistic Algorithms for Logistic Bandits\n- Agrawal et al. (2020), A Tractable Online Learning Algorithm for the Multinomial Logit Contextual Bandit, ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "milTQ2cdsOz", "reviewer": "Reviewer_Shft", "summary": "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.\n\nCompared 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.\n", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Contextual MNL is a recent hotly studied topic. \n\nMy biggest concern is the lack of comparison with an existing work. I want to bring one paper into attention: A Tractable Online Learning Algorithm for the Multinomial Logit Contextual Bandit. The main difference between two papers is whether different choices share the same parameters. However, the analyses are very similar in two settings and the analysis is similar to the generalized linear bandits. Moreover, regarding the regret bound, the improvement is also similar: it improves the constant term from \\kappa to \\sqrt{\\kappa} and it meanwhile pushes the constant term into a second order term. Can you clarify \n\n1) The technical difficulty/contribution of this paper (e.g. how it differs from the existing work);\n\n2) What's the connection between two constants (kappa in your paper and kappa in their paper)?\n\n3) What is the regret lower bound? Is the regret optimal with respect to the order of K? I saw the short comments in line 275-285, but can you provide a rigorous argument for that conclusion?\n\nThe writting is good, but the contribution needs to be clearly emphasized.\n\nMinor: 1) The notation \\bar{\\theta}_* can be simplified to \\theta_*;\n\n2) Please define \\otimes before formula (8);\n\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "eMOEk6OJy1r", "reviewer": "Reviewer_KVKE", "summary": "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.  ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. Relevant and practical extension of an important problem. \n2. The theoretical analysis and presentation is unique (some things can be clarified; see detailed comments)\n\nWeaknesses:\n1. The paper does not contain experiments with real-datasets and no comparisons with baselines. \n2. The are a few concerning questions that confuse the reader; hence presentation can be improved (see detailed comments).\n\nDetailed Feedback:\n\n1. I am a bit confused with the bound that the authors have mentioned in the abstract and in the main text. They seem to be inconsistent. Can you please clarify? Also, when mentioning the bounds, please mention what the parameter stands for, e.g., d, T?\n\n2. Equation 2: I believe it should be \\forall i \\in [K] instead of \\forall i \\in [K] \\cup {0}.\n\n3. There seems to be some mistake in the way expected reward is defined in line 82. There should be some argument in \\mu that should depend on the vector \\rho, but I do not see it. Then, the domain of \\mu in line 83 should also be defined properly. \n\n4. Why is it necessary to have all the \\rho_i >=0? I see an option like \"never show me this ad\" generating a positive reward to be contradictory? More so, when compared to not-clicking that generates a reward of 0. \n\n5. Equation 6: What is x_* in the definition of instantaneous regret?\n\n6. The analysis largely depends on the regularization parameter $\\lambda$. I wonder how the analysis will change if in equation 7, one chooses to work without regularization.\nAlso, there is notation abuse. \\lambda_max/\\lambda_min are used for eigen values and \\lambda is used for regularization as well.\n\n7. Right at the point where the authors make assumption 2, it is not clear to me why A will have positive eigen values. Can you please clarify?\n\n8. In Lemma 1, I was confused about what V_t stands for. The authors explain its definition much later. It would be better to reorganize that bit.\n\n9. The presentation of analysis is good. However, I would recommend moving the Lemmas which are used to prove other major results to the appendix, and instead add experiments with real-data in the paper. My major reason for giving the current score is because of its weak experiments. \n\n10. The authors provide intuitive reasons of why there should be a linear dependence in K. However, they have not provided any proof in that regard. Thus, the usage of the word 'optimal' is imprecise in my opinion.\n\n11. There has been a blatant use of vspace/vskip in the entire paper. If the paper is accepted, I would recommend avoiding their large usage. It just destroys the aesthetics of the paper. \n\nMinor:\n1. Line 30: statistic --> statistics?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No, the authors have not mentioned limitations and societal impacts of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "GH1V4RD2NfW", "reviewer": "Reviewer_SPJz", "summary": "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.\n\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I feel that this is a somewhat borderline paper. The extension of the logistic bandit to the multinomial logit setting is one that would be of genuine interest, and the analyses and proposed algorithm seem to be sound. The issue is that the developments are somewhat marginal. Some detailed theoretical work is required get the correct form of the UCB terms to hold over multiple parameter vectors simultaneously, but it seems that a good deal of the effort lies in combining new concentration theory (in this instance from Faury et al. (2020))  with the regret analyses of Abbasi-Yadkori et al. (2011). This is a credible and often used approach within this literature, but its familiarity does bring with it the question of whether there is sufficient novelty to merit publication at a top venue such as NeurIPS, and not an alternative venue. I have no doubt that there are many venues where this solid piece of research would easily clear the acceptance bar.\n\nORIGINALITY: The headline results are new in and of themselves, in so far as the literature has not combined the novel concentration results and regret analyses in the context of this variant of an MNL-bandit. As discussed above, a large component of the analysis is focussed on the combining of existing tools – a perfectly useful piece of work but one that perhaps scores lower in the originality aspect.\n\nQUALITY: As far as I can tell, the theory is accurate and the paper is generally written well. The algorithm is not compared to any (even naïve) competitors so it is hard to gauge its efficacy. We can however see that the variation in its performance with respect to particular problem parameters mirrors the implications of the theory. Where I think the paper could be improved through relatively little effort is through making yet more explicit the connections to the preceding work. The following questions occurred to me while reading the manuscript but did not have answers which I could easily discern. I feel the discussion and my understanding would be improved further by addressing them. \n1.\tFaury et al. (2020) can, according to line 119, drop the dependence on $\\kappa$ entirely. Why is this not possible (or perhaps not pursued?) here?\n2.\tLine 221 asserts the main technical contributions of the paper. Are these ‘main’ in the sense that they are the most challenging, the largest departure from existing techniques, or the most likely to be useful elsewhere? In any of these cases, why not sell this contribution more prominently among your contributions?\n3.\tIn what sense, precisely is the ‘improved algorithm’ computationally intractable? I did not find an explicit discussion of this in the requisite appendix.\n\nCLARITY: I feel the paper is generally clear and well written. As a technical paper with a lot of theoretical angles to introduce in a short page limit it is occasionally more quite concise, but I think it is sufficiently clear for the intended audience.\n\nSIGNIFICANCE: As discussed above, this seems like a pragmatic and realistic extension of logistic bandits to a setting that is likely to arise in online advertising. The analysis is solid and accurate as far as I can tell. This is a nice piece of work, suitably complete for publication (somewhere) and will be of interest to those working in this area.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes - this has been considered by the authors.", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a UCB-based algorithm for multinomial logit bandits. Its initial scores were 6, 6, 5, and 5; and they did not change during the discussion. The reviewers liked the rebuttal of the authors and agreed that this paper would a good contribution to NeurIPS. The main factor in this decision was the importance of the application. On the other hand, the paper builds heavily on Faury et al. (2020) and contains no experiments. In my opinion, this paper is borderline plus and I support its acceptance.
Decision: Accept (Poster)