A Tractable Online Learning Algorithm for the Multinomial Logit Contextual Bandit

The MNL model is a widely used choice model for capturing consumer purchase behavior in assortment selection models (see Flores et al. [2019] and Avadhanula [2019]). Recently, large-scale field experiments at Alibaba [Feldman et al., 2018] have demonstrated the efficacy of the MNL model in boosting revenues. Rusmevichientong et al. [2010] and Sauré & Zeevi [2013] were a couple of early works that studied explore-then-commit strategies for the dynamic assortment selection problem under the MNL model when there are no contexts/product features. The works of Agrawal et al. [2019] and Agrawal et al. [2017] revisited this problem and presented adaptive online learning algorithms based on the Upper Confidence Bounds(UCB) and Thompson Sampling (TS) ideas. These approaches, unlike earlier ideas, did not require prior information about the problem parameters and had near-optimal regret bounds. Following these developments, the contextual variant of the problem has received considerable attention. Cheung & Simchi-Levi [2017] and Oh & Iyengar [2019] propose TS-based approaches and establish Bayesian regret bounds on their performance³³3Our results give worst-case regret bound which is strictly stronger than Bayesian regret bound. Worst-case regret bounds directly imply Bayesian regret bounds with same order dependence.. Chen et al. [2020] present a UCB-based algorithm and establish min-max regret bounds. However, these contextual MNL algorithms and their performance bounds depend on a problem parameter $\kappa$ that can be prohibitively large, even for simple real-life examples. See Figure 1 for an illustration and Section 1.2 for a detailed discussion.

We note that Ou et al. [2018] also consider a similar problem of developing an online algorithm for the MNL model with linear utility parameters. Though they establish a regret bound that does not depend on the aforementioned parameter $\kappa$, they work with an inaccurate version of the MNL model. More specifically, in the MNL model, the probability of a consumer preferring an item is proportional to the exponential of the utility parameter and is not linear in the utility parameter as assumed in Ou et al. [2018].

The multi-armed bandit problem, which underlies these dynamic decision making settings, has been well studied in the literature (see Xu et al. [2021], Grant & Szechtman [2021]). Our problem is closely related to the parametric bandit problem, where a common unknown parameter connects the rewards of each arm. In particular, for linear bandits, each arm $a\in A$ (consider $A$ to be the set of all arms) is associated with a $d$-dimensional vector $x_{a}\in\mathbb{R}^{d}$ known a priori. And the expected reward upon selecting arm $a\in A$ is given by the inner product $\theta\cdot x_{a}$, for some unknown parameter vector $\theta$ (see Dani et al. [2008], Rusmevichientong & Tsitsiklis [2010], Abbasi-Yadkori et al. [2011]). The key difference is that the rewards (i.e., the revenue of the retailer) corresponding to an assortment under the MNL cannot be modeled in the framework of linear payoffs. Closer to our formulation is the literature on generalized linear bandits (see Filippi et al. [2010] and Faury et al. [2020]), where the expected payoff upon selecting arm $a$ is given by $f(\theta\cdot x_{a})$, where $f$ is a real-valued, non-linear function. However, unlike our setting, where an arm could be a collection of $K$ products (thus involving $K$ $d$-dimensional vectors), $f(.)$ is a single variable function in these prior works.

As discussed earlier, the retailer’s revenue (reward function) is the softmax function. Intuitively, the curvature of the reward function influences how easy (or difficult) it is to learn the true choice parameter $\theta_{*}$. In Section 2, we explicitly define $\kappa$ as inversely proportional to the lower bound on of the derivative of the reward function in the entire decision region. Existence of a global lower bound on the curvature of the reward function is a necessary assumption for the maximum likelihood estimation of $\theta_{*}$.

In previous works on generalized linear bandits and variants [Filippi et al., 2010, Li et al., 2017, Oh & Iyengar, 2019], the quantity $\kappa$ features in regret guarantees as a multiplicative factor of the primary term (i.e., as $\tilde{\mathrm{O}}(\kappa\sqrt{T})$), and this is because they ignore the local effect of the curvature, and use global properties (via $\kappa$) leading to loose worst-case bounds. For a cleaner exposition of this issue, lets take $K=1$, i.e., the rewards are given by a sigmoid function of $\theta\cdot x$. The derivative of sigmoid is “bell”-shaped (see Figure 1). When $\theta\cdot x$ is very high (i.e., the assortment contains products with high utilities) or when $\theta\cdot x$ is very low (i.e., the assortment contains products with low utility), the value of $\kappa$ will be large. From Assumption 2, for $K=1$, $\kappa$ is equivalent to $\max\frac{1}{a(1-a)}$, for some $a\in(0,1)$. Thus, when $a$ is close to $1$ or $0$, the value of $\kappa$ will be large. The exponential dependence for $K=1$ case follows when we replace $a$ with a sigmoid function. In the context of our problem, this translates to an exponential dependence of the per-round regret on the magnitude of utilities (i.e., $\theta\cdot x$).

In this paper, we build on recent developments for generalized linear bandits (Faury et al. [2020]) to propose a new optimistic algorithm, CB-MNL for the problem of contextual multinomial logit bandits. CB-MNL follows the standard template of optimistic parameter search strategies (also known as optimism in the face of uncertainty approaches)  [Abbasi-Yadkori et al., 2011, Abeille et al., 2021]. We use Bernstein-style concentration for self-normalized martingales, which were previously proposed in the context of scalar logistic bandits in Faury et al. [2020], to define our confidence set over the true parameter, taking into account the effects of the local curvature of the reward function. We show that the performance of CB-MNL (as measured by regret) is bounded as $\tilde{\mathrm{O}}\mathinner{\left(d\sqrt{T}+\kappa\right)}$, significantly improving the theoretical performance over existing algorithms where $\kappa$ appears as a multiplicative factor in the leading term. We also leverage a self-concordance [Bach, 2010] like relation for the multinomial logit reward function [Zhang & Lin, 2015], which helps us limit the effect of $\kappa$ on the final regret upper bound to only the higher-order terms. Finally, we propose a different convex confidence set for the optimization problem in the decision set of CB-MNL, which reduces the optimization problem to a constrained convex problem.

In summary, our work establishes strong worst-case regret guarantees by carefully accounting for local gradient information and using second-order function approximation for the estimation error.

For a vector $x\,\in\,\mathbb{R}^{d}$, $x^{\top}$ denotes the transpose. Given a positive definite matrix $\mathbf{M}\,\in\,\mathbb{R}^{d\times d}$, the induced norm is given by $||x||_{\mathbf{M}}=\sqrt{x\mathbf{M}x}$. For two symmetric matrices $\mathbf{M_{1}}$ and $\mathbf{M_{2}}$, $\mathbf{M_{1}}\succeq\mathbf{M_{2}}$ means that $\mathbf{M_{1}}-\mathbf{M_{2}}$ is positive semi-definite. For any positive integer $n$, $[n]\coloneqq\{1,2,3,\cdots,n\}$. $\mathbf{I}_{d}$ denotes an identity matrix of dimension $d\times d$. The platform (i.e. the learner) is referred using the pronouns she/her/hers.

Following Filippi et al. [2010], Li et al. [2017], Oh & Iyengar [2019], Faury et al. [2020], we introduce the following assumptions on the problem structure.

This assumption simplifies analysis and removes scaling constants from the equations.

Note that $\mu_{i}(\mathbf{X}_{\mathcal{Q}_{t}}^{\top}\theta)(1-\mu_{i}(\mathbf{X}_{\mathcal{Q}_{t}}^{\top}\theta))$ denotes the derivative of the softmax function along the $i_{th}$ direction. This assumption is necessary from the likelihood theory Lehmann & Casella [2006] as it ensures that the fisher matrix for $\theta_{*}$ estimation is invertible for all possible input instances. We refer to Oh & Iyengar [2019] for a detailed discussion in this regard. We denote $L$ and $M$ as the upper bounds on the first and second derivatives of the softmax function along any component, respectively. We have $L,M\leq 1$ [Gao & Pavel, 2017] for all problem instances.

CB-MNL, described in Algorithm 1, uses a regularized maximum likelihood estimator to compute an estimate $\hat{\theta}_{t}$ of $\theta_{*}$. Since $\{r_{t,i}\}_{i\in\mathcal{Q}_{t}}$ follows a multinomial distribution, the regularized log-likelihood (negative cross entropy loss) function, till the $(t-1)_{th}$ round, under parameter $\theta$ could be written as:

$\mathcal{L}_{t}^{\lambda_{t}}(\theta)$ is concave in $\theta$ for $\lambda_{t}>0$, and the maximum likelihood estimator is given by calculating the critical point of $\mathcal{L}_{t}^{\lambda_{t}}(\theta)$. Setting $\nabla_{\theta}\mathcal{L}_{t}^{\lambda_{t}}(\theta)=0$, we get $\hat{\theta}_{t}$ as the solution of:

For future analysis we also define

At the start of the interaction, when no contexts have been observed, $\hat{\theta}_{t}$ is well-defined by Eq (5) when $\lambda_{t}>0$. Therefore, the regularization parameter $\lambda_{t}$ makes CB-MNL burn-in period free, in contrast to some previous works, e.g. Filippi et al. [2010].

Algorithm 1 follows the template of in the face of uncertainty (OFU) strategies [Auer et al., 2002, Filippi et al., 2010, Faury et al., 2020]. Technical analysis of OFU algorithms relies on two key factors: the design of the confidence set and the ease of choosing an action using the confidence set.

In Section 4, we derive $E_{t}(\delta)$ (defined below) as the confidence set on $\theta_{*}$ such that $\theta_{*}\in C_{t}(\delta),\,\forall t$ with probability at least $1-\delta$ (randomness is over user choices). $E_{t}(\delta)$ used for making decisions at each round (see Eq (12)) by CB-MNL in Algorithm 1:

where $\beta_{t}(\delta)\coloneqq\gamma_{t}(\delta)+\frac{\gamma_{t}^{2}(\delta)}{\lambda_{t}}$, and

A confidence set similar to $E_{t}(\delta)$ in Eq (7) was recently proposed in Abeille et al. [2021] for the simpler logisitic bandit setting. Here, we extend its construction to the MNL setting. The set $E_{t}(\delta)$ is convex since the log-loss function is convex. This makes the decision step in Eq (12) a constraint convex optimization problem. However, it is difficult to prove bounds directly with $E_{t}(\delta)$. Therefore we leverage a result in Faury et al. [2020], where the authors proposed a new Bernstein-like tail inequality for self-normalized vectorial martingales (see Appendix A.1), to derive another confidence set on $\theta_{*}$:

where

$\dot{\mu}_{i}(\cdot)$ is the partial derivative of $\mu_{i}$ in the direction of the $i_{th}$ component of the assortment and $\gamma_{t}(\delta)$ is defined in Eq (8). The value of $\gamma_{t}(\delta)$ is an outcome of the concentration result of Faury et al. [2020]. As a consequence of this concentration, we have $\theta_{*}\,\in\,C_{t}(\delta)$ with probability at least $1-\delta$ (randomness is over user choices). The Bernstein-like concentration inequality used here is similar to Theorem 1 of Abbasi-Yadkori et al. [2011] with the difference that we take into account local variance information (hence local curvature information of the reward function) in defining $\mathbf{H}_{t}$. The above discussion is formalized in Appendix A.1.

The set $C_{t}(\delta)$ is non-convex, which follows from the non-linearity of $\mathbf{H}^{-1}_{t}(\theta)$. We use $C_{t}(\delta)$ directly to prove regret guarantees. In Section 4.3, we mention how the a convex set $E_{t}(\delta)$ is related to $C_{t}(\delta)$ and share many useful properties of $C_{t}(\delta)$. Till then, to maintain ease of technical flow and to compare it with the previous work Faury et al. [2020], we assume that the algorithm uses $C_{t}(\delta)$ as the confidence set. We highlight that for the confidence sets, $C_{t}(\delta)$ and $E_{t}(\delta)$, Algorithm CB-MNL is identical except for the calculation in Eq (12). For later sections we also define the following norm inducing design matrix based on all the contexts observed till time $t-1$:

The detailed proof is provided in A.4. Here we develop the main ideas leading to this result and develop an analytical flow which will be re-used while working with convex confidence set $E_{t}(\delta)$ in Section 4.3. In the previous works Filippi et al. [2010], Li et al. [2017], Oh & Iyengar [2021], global upper and lower bounds of the derivative of the link function (here softmax) are employed early in the analysis, leading to loss of local information carried by the MLE estimate $\theta_{t}$. In those previous works the first step was to upper bound the prediction error by the Lipschitz constant (which is a global property) of the softmax (or sigmoid for the logistic bandit case) function, as:

For building intuition, assume that $\mathbf{X}_{\mathcal{Q}_{t}}^{\top}\theta_{*}$ lies on “flatter” region of $\mu(\cdot)$, then Eq (15) is a loose upper bound.

Next we show how using a global lower bound in form of $\kappa$ (see Assumption 2) early in the analysis in the works Filippi et al. [2010], Li et al. [2017], Oh & Iyengar [2021] lead to loose prediction error upper bound. For this we first introduce a new notation:

We also define $\mathbf{G}_{t}(\theta_{t},\theta_{*})\coloneqq\sum_{s=1}^{t-1}\sum_{i\in\mathcal{Q}_{s}}\alpha_{i}(\mathbf{X}_{\mathcal{Q}_{s}},\theta_{t},\theta_{*})x_{s,i}x_{s,i}^{\top}+\lambda\mathbf{I}_{d}.$ From Eq (6), we obtain (see A.2 for details of this derivation):

From Assumption 2, $\mathbf{G}_{t}(\theta_{t},\theta_{*})$ is a positive definite matrix for $\lambda>0$ and therefore can be used to define a norm. Using Cauchy-Schwarz inequality with Eq (17) simplifies the prediction error as:

The previous literature Filippi et al. [2010], Oh & Iyengar [2021] has utilized $\mathbf{G}_{t}^{-1}(\theta_{t},\theta_{*})\succeq\kappa^{-1}\mathbf{V}_{t}$ and upper bounded $\alpha_{i}(\mathbf{X}_{\mathcal{Q}_{t}},\theta_{t},\theta_{*})$ by Lipschitz constant (directly at this stage), thereby incurring loose regret bounds. Instead, here we work with the norm induced by $\mathbf{H}_{t}(\theta_{*})$ and retain the location information in $\alpha_{i}(\mathbf{X}_{\mathcal{Q}_{t}},\theta_{t},\theta_{*})$.

It is not straight-forward to bound $||\theta_{*}-\theta_{t}||_{\mathbf{H}_{t}(\theta_{*})}$, we extend the self-concordance style relations from Faury et al. [2020] for the multinomial logit function which allow us to relate $\mathbf{G}_{t}^{-1}(\theta_{t},\theta_{*})$ and $\mathbf{H}_{t}^{-1}(\theta_{t})$ (or $\mathbf{H}_{t}^{-1}(\theta_{*})$) to develop a bound on $||\theta_{*}-\theta||_{\mathbf{H}_{t}(\theta_{*})}$.

Proofs of Lemma 4 and 5 have been deferred to A.3. Notice that Lemma 5 is a key result which characterizes worthiness of the confidence set $C_{t}(\delta)$. Recall that $\gamma_{T}(\delta)=\mathrm{O}(\sqrt{d\log(KT)})$ (with a tuned $\lambda$ as in Corollary 2). Therefore, any $\theta\,\in\,C_{t}(\delta)$ is not too far from the optimal $\theta_{*}$ under the norm induced by $||\cdot||_{\mathbf{H}_{t}(\theta_{*})}$. Now, we use Lemma 5 in Eq (19) to get:

The quantity $\alpha_{i}(\mathbf{X}_{\mathcal{Q}_{t}},\theta_{t},\theta_{*})$ as described in the Eq (16) is upper bounded in the following result

We use the result of Lemma 6 in Eq (20) followed by an application of Lemma 4 and the relation $\sum_{i\in\mathcal{Q}_{t}}||x_{t,i}||^{2}_{\mathbf{H}_{t}^{-1}(\theta_{t})}\leq\kappa\sum_{i\in\mathcal{Q}_{t}}||x_{t,i}||^{2}_{\mathbf{V}_{t}^{-1}}$ from Assumption 2, to arrive at the statement of Lemma 3.

The complete technical work is provided in A.4 and A.5. The key step to retrieve the upper bounds of Theorem 1 is to calculate $T$ rounds summation of the prediction error as given in Eq (3). Compared to the previous literature Filippi et al. [2010], Li et al. [2017], Oh & Iyengar [2021], the term $\sum_{i\in\mathcal{Q}_{t}}\dot{\mu}_{i}(\mathbf{X}_{\mathcal{Q}_{t}}^{\top}\theta_{*})||x_{t,i}||_{\mathbf{H}_{t}^{-1}(\theta_{*})}$ is new here. Further, our treatment of this term is much simpler and straight-forward as compared to that in Faury et al. [2020]

Sections 4.1 & 4.2 provide an analytical framework for calculating the regret bounds given: (1) the confidence set (Eq (9)) with the guarantee that $\theta_{*}\,\in\,C_{t}(\delta)$ with probability at least $1-\delta$; (2) the assurance that the confidence set is small (Lemma 5). In order to re-use previously developed techniques, we show: (1) $E_{t}(\delta)\supseteq C_{t}(\delta)$ (see Eq (7)) and therefore $\theta_{*}\,\in\,E_{t}(\delta)$ with probability at least $1-\delta$ (see Lemma 7; (2) an analog of Lemma 5 using $E_{t}(\delta)$ (see Lemma 8). The proof of Theorem 1 is therefore repeated while using Lemma 8, following steps as sketched in sections 4.1 & 4.2. The order dependence of the regret upper bound is retained (see Corollary 2).

The complete proof is provided in A.6. We highlight the usefulness of Lemma 7. Since all of set $C_{t}(\delta)$ lies within $E_{t}(\delta)$, the consequence of the concentration inequality also implies $\mathbb{P}(\forall t\geq 1,\theta_{*}\in E_{t}(\delta))\geq 1-\delta$.

The complete proof can be found in A.6.