Dynamic Assortment Optimization with Changing Contextual Information

Dynamic Assortment Optimization with Changing Contextual Information

\affil[1]{Stern School of Business, New York University} \affil[2]{Machine Learning Department, Carnegie Mellon University} \affil[3]{Computer Science Department, Indiana University at Bloomington}

Introduction

In operations, an important research problem facing a retailer is the selection of products/advertisements for display. For example, due to the limited shelf space, stocking restrictions, or available slots on a website, the retailer needs to carefully choose an assortment from the set of substitutable products. In an assortment optimization problem, choice model plays an important role since it characterizes a customer's choice behavior. However, in many scenarios, customers' choice behavior (e.g., mean utilities of products) is not given as a priori and cannot be easily estimated due to the insufficiency of historical data. This motivates the research of dynamic assortment optimization, which has attracted a lot of attentions from the revenue management community in recent years. A typical dynamic assortment optimization problem assumes a finite selling horizon of length $T$ with a large $T$. At each time period, the seller offers an assortment of products (with the size upper bounded by $K$) to an arriving customer. The seller observes the customer's purchase decision, which further provides useful information for learning utility parameters of the underlying choice model. The multinomial logit model (MNL) has been widely used in dynamic assortment optimization literature, see, e.g., Caro2007, Rusmevichientong2010, Saure2013, Agrawal16MNLBandit, Agrawal17Thompson,Chen:18tight,Chen:18near.

In the age of e-commerce, side information of products is widely available (e.g., brand, color, size, texture, popularity, historical selling information), which is important in characterizing customers' preferences for products. Moreover, some features are not static and could change over time (e.g., popularity score or ratings). The feature/contextual information of products will facilitate accurate assortment decisions that are tailored to customers' preferences. In particular, we assume at each time $t=1,\ldots, T$, each product $j$ is associated with a $d$-dimensional feature vector $v_{tj} \in \mathbb{R}^d$. To incorporate the feature information, following the classical conditional logit model McFa73, we assume that the mean utility of product $j$ at time $t$ (denoted by $u_{tj}$) obeys a linear model

Here, $\theta_0 \in \mathbb{R}^d$ is the unknown coefficient to be learned. Based on this linear structure of the mean utility, we adopt the MNL model as the underlying choice model (see Section (ref) and Eq. (ref) for more details). As compared to the standard MNL, this changing contextual MNL model not only incorporates rich contextual information but also allows the utility to evolve over time. The changing utility is an attractive property as it captures the reality in many applications but also brings new technical challenges in learning and decision-making. For example, in existing works of Agrawal16MNLBandit for plain MNL choice models, upper confidence bands are constructed by providing the same assortment repetitively to incoming customers until a no-purchase activity is observed. Such an approach, however, can no longer be applied to MNL with changing contextual information as the utility parameters of products constantly evolve with time. To overcome such challenges, we propose a policy that performs optimization at every single time period, without repetitions of assortments in general.

Our model also allows the revenue for each product $j$ to change over time. In particular, we associate the revenue parameter $r_{tj}$ for the product $j$ at time $t$.

This model generalizes the widely adopted (generalized) linear contextual bandit from machine learning literature (see, e.g., filippi2010parametric, chu11,Abbasi-Yadkori:2011,Agrawal:13,li2017provably and references therein) in a non-trivial way since the MNL cannot be written in a generalized linear model form (when an assortment contains more than one product, see Section (ref) for more details). It is also worthwhile noting that this model incorporates a personalized MNL model proposed by Wang:17:person as a special case, where each product $j$ is associated with a fixed but unknown coefficient $\theta(j)$ and each arriving customer at time $t$ with an observable feature vector $x_t$ (see Section (ref) for a more detailed discussion). On the other hand, we choose to motivate our model from product contextual information since in practice, obtaining products' features is usually easier (and less sensitive) than extracting customers' preferences.

Given this contextual MNL choice model, the key challenge is how to design a policy that simultaneously learns the unknown coefficient $\theta_0$ and sequentially makes the decision on offered assortment. The performance of a dynamic policy is usually measured by the regret, which is defined as the gap between the expected revenue generated by the policy and the oracle expected revenue when $\theta_0$ (and thus the mean utilizes) is known as a priori.

The first contribution of the paper is the construction of an upper confidence bound (UCB) policy. Our UCB policy is based on the maximum likelihood estimator (MLE) and thus is named MLE-UCB. Although UCB has been a well-known technique for bandit problems, how to adopt this high-level idea to solve a problem with specific structures certainly requires technical innovations (e.g., how to build a confidence interval varies from one problem to another). In particular, our MLE-UCB contains two stages. The first stage is a pure exploration stage in which assortments are randomly offered and a “pilot MLE” is computed based on the observed purchase actions. As we will show in Lemma (ref), this pilot estimator serves as a good initial estimator of $\theta_0$. After the exploration phase, the MLE-UCB enters the simultaneous learning and decision-making phase. We carefully construct an upper confidence bound of the expected revenue when offering an assortment. The added interval is based on the Fisher information matrix of the computed MLE from the previous step. Then we solve a combinatorial optimization problem to search the assortment that maximizes the upper confidence bound. By observing the customer's purchase action based on the offered assortment, the policy updates the estimated MLE. In this update, we propose to compute a “local MLE”, which requires the solution to be close enough to our pilot estimator. The local MLE plays an important role in MLE-UCB policy since it guarantees that the obtained estimator at each time period is also close to the unknown true coefficient $\theta_0$.

Under some mild assumptions on features and coefficients, we are able to establish a regret bound $\widetilde{O}(d \sqrt{T})$, where the $\widetilde{O}$ notation suppresses logarithmic dependence on $T$, $K$ (cardinality constraint), and some other problem dependent parameters\footnote{For the ease of presentation in the introduction, we only present the dominating term under the common scenario that the selling horizon $T$ is larger than the dimensionality $d$ and the cardinality constraint $K$. Please refer to Theorem (ref) for a more explicit expression of the obtained regret.}. One remarkable aspect of our regret bound is that our regret has no dependence on the total number of products $N$ (not even in a logarithmic factor). This makes the result attractive to online applications where $N$ is large (e.g., online advertisement). Moreover, it is also worthwhile noting the dependence of $K$ is only through a logarithmic term.

Our second contribution is to establish the lower bound result $\Omega(d\sqrt{T}/K)$. When the maximum size of an assortment $K$ is small (which usually holds in practice), this result shows that our policy is almost optimal.

Moreover, at each time period in the exploitation phase, our UCB policy needs to solve a combinatorial optimization problem, which searches for the best assortment (under the cardinality constraint) that minimizes the upper confidence bound of the expected revenue. Given the complicated structure of the upper confidence bound, there is no simple solution for this combinatorial problem. When $K$ is small and $N$ is not too large, one can directly search over all the possible sets with the size less than or equal to $K$. In addition to the solution of solving the combinatorial optimization exactly, {the third contribution of the work is to provide an approximation algorithm based on dynamic programming that runs in polynomial time with respect to $N$, $K$, $T$.} Although the proposed approximation algorithm has a theoretical guarantee, it is still not efficient for dealing with large-scale applications. To this end, we further describe a computationally efficient greedy heuristic for solving this combinatorial optimization problem. The heuristic algorithm is based on the idea of local search by greedy swapping, with more details described in Sec. (ref).

Related work

Due to the popularity of data-driven revenue management, dynamic assortment optimization, which adaptively learns unknown customers' choice behavior, has received increasing attention in the past few years. Motivated by fast-fashion retailing, the work by Caro2007 first studied dynamic assortment optimization problem, but it makes a strong assumption that the demands for different product are independent. Recent works by Rusmevichientong2010, Saure2013, Agrawal16MNLBandit, Agrawal17Thompson,Chen:18tight,Chen:18near incorporated MNL models into dynamic assortment optimization and formulated the problem into a online regret minimization problem. In particular, for capacitated MNL, Agrawal16MNLBandit and Agrawal17Thompson proposed UCB and Thompson sampling techniques and established the regret bound $\widetilde{O}(\sqrt{NT})$ (when $T \gg N^2$). Chen:18tight further established a matching lower bound of $\Omega(\sqrt{NT})$. It is interesting to compare our regret to the bound for the standard MNL case. When the total number of products $N$ is much larger than $d$ (i.e., $N > d^2$), by incorporating the contextual information, the regret reduces from $\widetilde{O}(\sqrt{NT})$ to $\widetilde{O}(d \sqrt{T})$. The latter one only depends on $d$ and is completely independent of the total number of products $N$, which also demonstrates the usefulness of the contextual information. Chen:18dynamic further studied the dynamic assortment optimization under nested logit models. We also note that to highlight our key idea and focus on the balance between learning of $\theta_0$ and revenue maximization, we study the stylized dynamic assortment optimization problems following the existing literature Rusmevichientong2010, Saure2013, Agrawal16MNLBandit, Agrawal17Thompson, which ignore operations considerations such as price decisions and inventory replenishment.

There is another line of recent research on investigating personalized assortment optimization. {By incorporating the feature information of each arriving customer, both the static and dynamic assortment optimization problems are studied in Chen2015 and Wang:17:person, respectively. It is worthwhile noting that although we do not approach our work from a personalized perspective\footnote{This is because in some applications, the product features are easier to obtain by the seller as compared to customer features.}, the personalized MNL considered in Wang:17:person can be viewed as a special of our model.

In particular, the personalized MNL assumes that each product $j$ is associated with an unknown coefficient $\theta(j) \in \mathbb{R}^D$. When a customer arrives at time $t$ with the observed feature $x_t$, the utility of product $j$ at time $t$ is $u_{tj}=x_t^\top \theta(j)$. Now we explain how to specialize our model to obtain the personalized MNL. Let us define $\theta_0:=\{\theta(1), \ldots, \theta(N)\} \in \mathbb{R}^{DN}$ and the feature vector $v_{tj}:=(0, \ldots, x_{t}, \ldots, 0) \in \mathbb{R}^{DN}$, which is a concatenation of $N$ $D$-dimensional vectors with the $j$-th vector being $x_t$ and all other vectors being 0. Then according to our linear model in Eq. (ref), we have $u_{tj}= v_{tj}^\top\theta_0= x_t^\top \theta(j)$, which recovers the personalized MNL model. Using our regret bound $\widetilde{O}(d\sqrt{T})$ with $d=DN$ as the dimensionality of $\theta_0$, we directly obtain the regret $\widetilde{O}(DN \sqrt{T})$ for the dynamic assortment optimization under the personalized MNL. As compared to the Bayesian regret bound $\widetilde{O}(DN\sqrt{KT})$ in Wang:17:person (see Theorem 3.3. therein), our approach still saves a factor of $\sqrt{K}$.} We also remark that our results require a slightly stronger assumption on the contextual information vectors $\{v_{tj}\}$ compared to Wang:17:person, which allows customer feature vectors $\{x_t\}$ to be adversarially chosen. More specifically, {a stochastic assumption} is imposed on $\{v_{tj}\}$ only during the pure exploration phase of our proposed policy. {After this pure exploration phase, the feature vectors $\{v_{tj}\}$ can also be adversarially chosen.} We refer the readers to Sec. (ref) for further details.

In addition, the developed techniques in our work and Wang:17:person are different, Our policy is based on UCB, while the policy in Wang:17:person is based on Thompson sampling. Furthermore, other research studies personalized assortment optimization in an adversarial setting rather than stochastic setting. For example, Golrezaei2014,Chen:16recom assumed that each customer's choice behavior is known, but that the customers' arriving sequence (or customers' types) can be adversarially chosen and took the inventory level into consideration. Since the arriving sequence can be arbitrary, there is no learning component in the problem and both Golrezaei2014 and Chen:16recom adopted the competitive ratio as the performance evaluation metric.

Another field of related research is the contextual bandit literature, in which the linear contextual bandit has been widely studied as a special case (see, e.g., Dani08stochastic,Rusmevichientong:10:bandit,chu11,Abbasi-Yadkori:2011,Agrawal:13 and references therein). Some recent work extends the linear contextual bandit to generalized linear bandit filippi2010parametric,li2017provably, which assumes a generalized linear reward structure. In particular, the reward $r$ of pulling an arm given the observed feature vector of this arm $x$ is modeled by

for an unknown linear model $\theta_0$ and a known link function $\sigma:\mathbb R\to\mathbb R$. For example, for a linear contextual bandit, $\sigma$ is the identity mapping, i.e., $\mathbb E[r|x]=\sigma(x^\top\theta_0)$. For the logistic contextual bandit, we have $r \in \{0,1\}$ and $\Pr(r=1|x)=\frac{\exp(x^\top\theta_0)}{1+\exp(x^\top\theta_0)}$. { In a standard generalized linear bandit problem (see, e.g., li2017provably) with $N$ arms, it is assumed that a context vector $v_{tj}$ is revealed at time $t$ for each arm $j \in [N]$. Given a selected arm $i_t \in [N]$ at time $t$, the expected reward follows Eq. (ref), i.e., $\mathbb{E}[r_t | v_{t,i_t} ]=\sigma(v_{t,i_t}^\top\theta_0)$. At first glance, our contextual MNL model is a natural extension of the generalized linear bandit to the MNL choice model. However, when the size of an assortment $K\geq 2$, the contextual MNL cannot be written in the form of Eq. ((ref)) and the denominator in the choice probability (see Eq. (ref) in the next section) has a more complicated structure. Therefore, our problem is technically not a generalized linear model and is therefore more challenging. Moreover, in contextual bandit problems, only one arm is selected by the decision-maker at each time period. In contrast, each action in an assortment optimization problem involves a set of items, which makes the action space more complicated.}

Notations and paper organization

Throughout the paper, we adopt the standard asymptotic notations. In particular, we use $f(\cdot) \lesssim g(\cdot)$ to denote that $f(\cdot) = O(g(\cdot))$. Similarly, by $f(\cdot) \gtrsim g(\cdot)$, we denote $f(\cdot) = \Omega(g(\cdot))$. We also use $f(\cdot) \asymp g(\cdot)$ for $f(\cdot) = \Theta(g(\cdot))$. Throughout this paper, we will use $C_0, C_1, C_2，\ldots$ to denote universal constants. For a vector $v$ and a matrix $M$, we will use $\|v\|_2$ and $\|M\|_{\mathrm{op}}$ to denote the vector $\ell_2$-norm and the matrix spectral norm (i.e., the maximum singular value), respectively. Moreover, for a real-valued symmetric matrix $M$, we denote the maximum eigenvalue and the minimum eigenvalue of $M$ by $\lambda_{\max}(M)$ and $\lambda_{\min}(M)$, respectively, and define $\|v\|_M^2:=v^T M v$ for any given vector $v$. For a given integer $N$, we denote the set $\{1,\ldots, N\}$ by $[N]$.

The rest of the paper is organized as follows. In Section (ref), we introduce the mathematical formulation of our models and define the regret. In Section (ref), we describe the proposed MLE-UCB policy and provide the regret analysis. The lower bound result is provided in Section (ref). In Section (ref), we investigate the combinatorial optimization problem in MLE-UCB and propose the approximation algorithm and greedy heuristic. The multivariate case of the approximation algorithm is relegated to the appendix. In Section (ref), we provide the numerical studies. The conclusion and future directions are discussed in Section (ref). Some technical proofs are provided in the online supplementary material.

The problem setup

There are $N$ items, conveniently labeled as $1,2,\cdots,N$. At each time $t$, a set of time-sensitive “feature vectors” $v_{t1}, v_{t2}, \cdots, v_{tN}\in\mathbb R^d$ and revenues $r_{t1},\cdots,r_{tN}\in[0,1]$ are observed, reflecting time-varying changes of items' revenues and customers' preferences. A retailer, based on the features $\{v_{ti}\}_{i=1}^N$ and previous purchasing actions, picks an assortment $S_t\subseteq[N]$ under the cardinality constraint $|S_t|\leq K$ to present to an incoming customer; the retailer then observes a purchasing action $i_t\in S_t\cup\{0\}$ and collects the associated revenue $r_{i_t}$ of the purchased item (if $i_t=0$ then no item is purchased and zero revenue is collected).

We use an MNL model with features to characterize how a customer makes choices. Let $\theta_0\in\mathbb R^d$ be an unknown time-invariant coefficient. For any $S\subseteq[N]$, the choice model $p_{\theta_0,t}(\cdot|S)$ is specified as (let $r_0=0$ and $v_{t0}=0$)

For simplicity, in the rest of the paper we use $p_{\theta,t}(\cdot|S)$ to denote the law of the purchased item $i_t$ conditioned on given assortment $S$ at time $t$, parameterized by the coefficient $\theta\in\mathbb R^d$. The expected revenue $R_t(S)$ of assortment $S\subseteq[N]$ at time $t$ is then given by

{Note that throughout the paper, we use $\mathbb E_{\theta_0,t}[\cdot |S]$ to denote the expectation with respect to the choice probabilities $p_{\theta_0,t}(j|S)$ defined in Eq. (ref).}

Our objective is to design policy $\pi$ such that the regret

is minimized. {Here, $S_t^*$ is an optimal assortment chosen when the full knowledge of choice probabilities is available (i.e., $\theta_0$ is known).}

\SetAlCapSkip{1em}

An MLE-UCB policy and its regret

We propose an MLE-UCB policy, described in Algorithm (ref).

The policy can be roughly divided into two phases. In the first pure exploration phase, the policy selects assortments uniformly at random, consisting of only one item. The objective of the pure exploration is to establish a “pilot” estimator of the unknown coefficient $\theta_0$, i.e., a good initial estimator for $\theta_0$. For the simplicity of the analysis, we choose one item for each assortment in this phase, which facilitates us to adapt existing analysis in filippi2010parametric,li2017provably as the MNL-logit choice model reduces to a generalized linear model when only one item is present in the assortment. In the second phase, we use a UCB-type approach that selects $S_t$ as the assortment maximizing an upper bound $\overline R_t(S_t)$ of the expected revenue $R_t(S_t)$. Such upper bounds are built using a local Maximum Likelihood Estimation (MLE) of $\theta_0$. In particular, in Step 5, instead of computing an MLE, we compute a local MLE, where the estimator $\widehat{\theta}_{t-1}$ lies in a ball centered at the pilot estimator $\theta^*$ with a radius $\tau$. This localization also simplifies the technical analysis based on Taylor expansion, which benefits from the constraint that $\widehat\theta_{t-1}$ is not too far away from $\theta^*$.

To construct the confidence bound, we introduce the matrices $\widehat M_t(\widehat\theta_{t-1}|S)$ and $\widehat I_{t-1}(\widehat\theta_{t-1})$ in Step 6 of Algorithm (ref), which are empirical estimates of the Fisher's information matrices $-\mathbb E[\nabla_\theta^2\log p(\cdot|\theta)]$ corresponding to the MNL choice model $p(\cdot|S_t)$. The population version of the Fisher's information matrices are presented in Eq. (ref) in Sec. (ref). These quantities play an essential role in classical statistical analysis of maximum likelihood estimators (see, e.g., van1998asymptotic).

The proposed MLE-UCB policy has three hyper-parameters: the coefficient $\omega>0$ that controls the lengths of confidence intervals of $R_t(S)$, the number of pure exploration iterations $T_0$, and the radius $\tau_0$ in the local MLE formulation. While theoretical values of $\omega,T_0$ and $\tau$ are given in Theorem (ref), which potentially depend on several unknown problem parameters, in practice we recommend the usage of $T_0=\max\{d\log T, T^{1/4}\}$, $\omega=\sqrt{d\log T}$ and $\tau=1/K$.

In the rest of this section, we give a regret analysis that shows an $\widetilde O(d\sqrt{T})$ upper bound on the regret of the MLE-UCB policy. Additionally, we prove a lower bound of $\widetilde O(d\sqrt{T}/K)$ in Sec. (ref) and show how the combinatorial optimization in Step 7 can be approximately computed efficiently in Sec. (ref).

Regret analysis

To establish rigorous regret upper bounds on Algorithm (ref), we impose the following assumptions:

The item (A1) assumes that the contextual information vectors $\{v_{tj}\}$ in the pure-exploration phase with $t \leq T_0$ are randomly generated from a non-degenerate density. It also places a standard boundedness condition on $\{v_{tj}\}$ for all time periods $t$. Note that after the pure-exploration phase, we allow the contextual vectors $\{v_{tj}\}$ to be adversarially chosen, only subject to boundedness conditions. (A2) additionally assumes a bounded ratio between the probability of choosing any two different items in an arbitrary assortment set. {We remark that if $\|\theta_0\|_2\leq C$, then the boundedness assumption in (A1) implies (A2) with $\rho\leq e^{2 \max\{1,C\nu\}}$.}

We are now ready to state our main result that upper bounds the worst-case accumulated regret of the proposed MLE-UCB policy in Algorithm (ref).

In addition to universal constants, the regret upper bound established in Theorem (ref) has two terms. The first term, $d\sqrt{T}\cdot \log(\lambda_0^{-1}\rho\nu TK)$, is the main regret term that scales as $\widetilde O(d\sqrt{T})$ dropping logarithmic dependency. The second $d^2\lambda_0^{-2}\rho^4\nu^2K^2\log T$ term is a minor term, because it only scales logarithmically with the time horizon $T$. One remarkable aspect of Theorem (ref) is the fact that the regret upper bound has no dependency on the total number of items $N$ (even in a logarithmic term). This is an attractive property of the proposed policy, which allows $N$ to be very large, even exponentially large in $d$ and $K$.

Proof sketch of Theorem (ref)

We provide a proof sketch of Theorem (ref) in this section. The proofs of technical lemmas are relegated to the online supplement.

The proof is divided into four steps. In the first step, we analyze the pilot estimator $\theta^*$ obtained from the pure exploration phase of Algorithm (ref), and show as a corollary that the true model $\theta_0$ is feasible to all subsequent local MLE formulations with high probability (see Corollary (ref)). In the second step, we use an $\varepsilon$-net argument to analyze the estimation error of the local MLE. Afterwards, we show in the third step that an upper bound on the estimation error $\widehat\theta_{t-1}-\theta_0$ implies an upper bound on the estimation error of the expected revenue $R_t(S)$, hence showing that $\overline R_t(S)$ are valid upper confidence bounds. Finally, we apply the elliptical potential lemma, which also plays a key role in linear stochastic bandit and its variants, to complete our proof.

Analysis of pure exploration and the pilot estimator

Our first step is to establish an upper bound on the estimation error $\|\theta^*-\theta_0\|_2$ of the pilot estimator $\theta^*$, built using pure exploration data. It should be noted that in the pure exploration phase ($t\in\{1,\cdots,T_0\}$), the assortments $\{S_t\}_{t=1}^{T_0}$ only consist of one item. Therefore the observation model reduces to a standard generalized linear model with the sigmoid function $\sigma(x)=1/(1+e^{-x})= e^x/(1+e^x)$ as the link function, which is essentially a logistic regression model of observing 1 if the customer makes a purchase.

Because the choice model in the pure exploration phase reduces to a generalized linear model, we can cite existing works to upper bound the error $\|\theta^*-\theta_0\|_2$. In particular, the following lemma is cited from li2017provably, adapted to our model and parameter settings. The details on how to adapt the result from li2017provably provided in the supplementary material.

The following corollary immediately follows Lemma (ref), by lower bounding $\lambda_{\min}(V)$ using standard matrix concentration inequalities. Its proof is again deferred to the supplementary material.

The purpose of Corollary (ref) is to establish a connection between the number of pure exploration iterations $T_0$ and the critical radius $\tau$ used in the local MLE formulation. It shows a lower bound on $T_0$ in order for the estimation error $\|\theta^*-\theta_0\|_2$ to be upper bounded by $\tau$ with high probability, which certifies that the true model $\theta_0$ is also a feasible local estimator in our MLE-UCB policy. This is an important property for later analysis of local MLE solutions $\widehat\theta_{t-1}$.

Analysis of the local MLE

The following lemma upper bounds a Mahalanobis distance between $\widehat\theta_t$ and $\theta_0$. For convenience, we adopt the notation that $r_{t0}=0$ and $v_{t0}=0$ for all $t$ throughout this section. We also define

where $\mathbb E_{\theta,t'}$ denotes the expectation evaluated under the law $j\sim p_{\theta,t'}(\cdot|S_{t'})$; that is, $p_{\theta,t'}(j|S_{t'}) =\exp\{v_{t'j}^\top\theta\}/(1+\sum_{k\in S_{t'}}\exp\{v_{t'j}^\top\theta\})$ for $j\in S_{t'}$ and $p_{\theta,t'}(j|S_{t'})=0$ for $j\notin S_{t'}$.

The complete proof of Lemma (ref) is given in the supplementary material, and here we provide some high-level ideas behind our proof.

Our proof is inspired by the classical convergence rate analysis of M-estimators van1998asymptotic. The main technical challenge is to provide finite-sample analysis of several components in the proof of van1998asymptotic.

In particular, for any $\theta\in\mathbb R^d$, consider $$ F_{t}(\theta) := \sum_{t'\leq t}f_{t'}(\theta)\;\;\;\;\text{where}\;\; f_{t'}(\theta) := \mathbb E_{\theta_0,t'}\left[\log\frac{p_{\theta,t'}(j|S_{t'})}{p_{\theta_0,t'}(j|S_{t'})}\right] = \sum_{j\in S_{t'}\cup\{0\}} p_{\theta_0,t'}(j|S_{t'})\log\frac{p_{\theta,t'}(j|S_{t'})}{p_{\theta_0,t'}(j|S_{t'})} $$ and its “sample” version $$ \widehat F_t(\theta) := \sum_{t'\leq t} \widehat f_{t'}(\theta)\;\;\;\;\text{where}\;\; \widehat f_{t'}(\theta) := \log\frac{p_{\theta,t'}(i_{t'}|S_{t'})}{p_{\theta_0,t'}(i_{t'}|S_{t'})}. $$

It is easy to verify by definition that $F_t(\widehat\theta_{t})\geq F_t(\theta_0)=0$ and $\widehat F_t(\widehat\theta_{t})\leq \widehat{F}_t(\theta_0)=0$, because $F_t(\cdot)$ is a Kullback-Leibler divergence, $\theta_0$ is feasible to the local MLE formulation and $\widehat\theta_{t-1}$ is the optimal solution. On the other hand, it can be proved that $|F_t(\theta)-\widehat F_t(\theta)|$ is small for all $\theta$ with high probability, by using concentration inequalities for self-normalized empirical process (note that $\mathbb E\widehat f_{t'}(\theta) = f_{t'}(\theta)$ for any $\theta$). Moreover, by constructing a local quadratic approximation of $F_t(\cdot)$ around $\theta_0$, we can show that $F_t(\theta)-F_t(\theta_0)$ is large when $\theta$ is far away from $\theta_0$.

{Following the above observations, we can use proof by contradiction to prove Lemma (ref), which essentially claims that $\widehat\theta_{t}$ and $\theta_0$ are close under the quadratic distance $\|\cdot\|_{I_t(\theta_0)}$. Suppose by contradiction that $\widehat\theta_{t}$ and $\theta_0$ are far apart, which implies that $|F_t(\widehat\theta_{t})-F_t(\theta_0)|$ is large. On the other hand, by the fact that $\widehat F_t(\widehat\theta_{t})\leq 0 = {F}_t(\theta_0) \leq F_t(\widehat\theta_{t})$, we have \[ |F_t(\widehat\theta_{t})-F_t(\theta_0)| = |F_t(\widehat\theta_{t})| \leq |F_t(\widehat\theta_{t})-\widehat F_t(\widehat\theta_{t}) |. \] By the established concentration result, we have $|F_t(\theta)-\widehat F_t(\theta)|$ is small for all $\theta$ with high probability (including $\theta=\widehat\theta_{t}$). This leads to the desired contradiction.}

Analysis of upper confidence bounds

The following technical lemma shows that the upper confidence bounds constructed in Algorithm (ref) are valid with high probability. Additionally, we establish an upper bound on the discrepancy between $\overline R_t(S)$ and the true value $R_t(S)$ defined in Eq. (ref).

At a higher level, the proof of Lemma (ref) can be regarded as a “finite-sample” version of the classical Delta's method, which upper bounds estimation error of some functional $\varphi$ of parameters, i.e., $|\varphi(\widehat\theta_{t-1})-\varphi(\theta_0)|$ using the estimation error of the parameters themselves $\widehat\theta_{t-1}-\theta_0$. The complete proof is relegated to the supplementary material.

The elliptical potential lemma

Let $S_t^*$ be the assortment that maximizes the expected revenue $R_t(\cdot)$ (defined in Eq. (ref)) at time period $t$, and $S_t$ be the assortment selected by Algorithm (ref). Because $R_t(S)\leq \overline R_t(S)$ for all $S$ (see Lemma (ref)), we have the following upper bound for each term in the regret (see Eq. (ref)):

where the last inequality holds because $\overline R_t(S_t^*)-\overline R_t(S_t) \leq 0$ (note that $S_t$ maximizes $\overline{R}_t(\cdot)$).

Subsequently, invoking Lemma (ref) and the Cauchy-Schwarz inequality, we have

The following lemma is a key result that upper bounds $\sum_{t=T_0+1}^T\min\{1,\|I_{t-1}^{-1/2}(\theta_0)M_t(\theta_0|S_t)I_{t-1}^{-1/2}(\theta_0)\|_\mathrm{op}^2\}$. It is usually referred to as the elliptical potential lemma and has found many applications in contextual bandit-type problems (see, e.g., Dani08stochastic,Rusmevichientong2010,filippi2010parametric,li2017provably).

The proof of Lemma (ref) is placed in the supplementary material. It is a routine proof following existing proofs of elliptical potential lemmas using matrix-determinant rank-1 updates.

We are now ready to give the final upper bound on $\mathrm{Regret}(\{S_t\}_{t=1}^T)$ defined in Eq. (ref). Note that the total regret incurred by the pure exploration phase is upper bounded by $T_0$, because the revenue parameters $r_{tj}$ are normalized so that they are upper bounded by 1. In addition, as the failure event of $\overline R_t(S)\leq R_t(S)$ for some $S$ occurs with probability $1-O(T^{-1})$, the total regret accumulated under the failure event is $O(T^{-1})\cdot T = O(1)$. Further invoking Eq. ((ref)) and Lemma (ref), we have

Lower bound

To complement our regret analysis in Sec. (ref), in this section we prove a lower bound for worst-case regret. Our lower bound is information theoretical, and therefore applies to any policy for dynamic assortment optimization with changing contextual features.

Theorem (ref) essentially implies that the $\widetilde O(d\sqrt{T})$ regret upper bound established in Theorem (ref) is tight (up to logarithmic factors) in $T$ and $d$. Although there is an $O(K)$ gap between the upper and lower regret bounds, in practical applications $K$ is usually small and can be generally regarded as a constant. It is an interesting technical open problem to close this gap of $O(K)$.

We also remark that an $\Omega(d\sqrt{T})$ lower bound was established in Dani08stochastic for contextual linear bandit problems. However, in assortment selection, the reward function is not coordinate-wise decomposable, making techniques in Dani08stochastic not directly applicable. In the following subsection, we provide a high-level proof sketch of Theorem (ref), with complete proofs of technical lemmas relegated to the supplementary material.

Proof sketch of Theorem (ref)

At a higher level, the proof of Theorem (ref) can be divided into three steps (separated into three different sub-sections below). In the first step, we construct an adversarial parameter set and reduce the task of lower bounding the worst-case regret of any policy to lower bounding the Bayes risk of the constructed parameter set. In the second step, we use a “counting argument” similar to the one developed in Chen:18tight to provide an explicit lower bound on the Bayes risk of the constructed adversarial parameter set, and finally we apply Pinsker's inequality (see, e.g., tsybakov2009introduction) to derive a complete lower bound.

Adversarial construction and the Bayes risk

Let $\epsilon\in(0, 1/d\sqrt{d})$ be a small positive parameter to be specified later. For every subset $W\subseteq[d]$, define the corresponding parameter $\theta_W\in\mathbb R^d$ as $[\theta_W]_i=\epsilon$ for all $i\in W$, and $[\theta_W]_i=0$ for all $i\notin W$. The parameter set we consider is

Note that $d/4$ is a positive integer because $d$ is divisible by 4, as assumed in Theorem (ref). Also, to simplify notation, we use $\mathcal W_k$ to denote the class of all subsets of $[d]$ whose size is $k$.

The feature vectors $\{v_{ti}\}$ are constructed to be invariant across time iterations $t$. For each $t$ and $U\in\mathcal W_{d/4}$, $K$ identical feature vectors $v_{U}$ are constructed as (recall that $K$ is the maximum allowed assortment capacity)

It is easy to check that with the condition $\epsilon\in(0,1/\sqrt{d})$, $\|\theta_W\|_2\leq 1$ and $\|v_U\|_2\leq 1$ for all $W,U\in\mathcal W_{d/4}$. Hence the worst-case regret of any policy $\pi$ can be lower bounded by the worst-case regret of parameters belonging to $\Theta$, which can be further lower bounded by the “average” regret over a uniform prior over $\Theta$:

Here $S_\theta^*$ is the optimal assortment of size at most $K$ that maximizes (expected) revenue under parameterization $\theta$. By construction, it is easy to verify that $S_{\theta_W}^*$ consists of all $K$ items corresponding to feature $v_W$. We also employ constant revenue parameters $r_{ti}\equiv 1$ for all $t\in[T]$, $i\in[N]$.

The counting argument

In this section we drive an explicit lower bound on the Bayes risk in Eq. ((ref)). For any sequences $\{S_t\}_{t=1}^T$ produced by the policy $\pi$, we first describe an alternative sequence $\{\widetilde S_t\}_{t=1}^T$ that provably enjoys less regret under parameterization $\theta_W$, while simplifying our analysis.

Let $v_{U_1},\cdots,v_{U_L}$ be the distinct feature vectors contained in assortment $S_t$ (if $S_t=\emptyset$ then one may choose an arbitrary feature $v_U$) with $U_1,\cdots,U_L\in\mathcal W_{d/4}$. Let $U^*$ be the subset among $U_1,\cdots,U_L$ that maximizes $\langle v_{U^*},\theta_W\rangle$, where $\theta_W$ is the underlying parameter. Let $\widetilde S_t$ be the assortment consisting of all $K$ items corresponding to feature $v_U^*$. We then have the following observation:

To simplify notation we also use $\widetilde U_t$ to denote the unique $U^*\in\mathcal W_{d/4}$ in $\widetilde S_t$. We also use $\mathbb E_W$ and $\mathbb P_W$ to denote the law parameterized by $\theta_W$ and policy $\pi$. The following lemma gives a lower bound on $R(\widetilde S_t)-R(S_{\theta_W}^*)$ by comparing it with $W$, which is also proved in the supplementary material.

Define random variables $\widetilde N_i := \sum_{t=1}^T\boldsymbol 1\{i\in\widetilde U_t\}$. Lemma (ref) immediately implies

Denote $\mathcal W_{d/4}^{(i)} := \{W\in\mathcal W_{d/4}: i\in W\}$ and $\mathcal W_{d/4-1} := \{W\subseteq[d]: |W|=d/4-1\}$. Averaging both sides of Eq. ((ref)) with respect to all $W\in\mathcal W_{d/4}$ and swapping the summation order, we have

Note that for any fixed $W$, $\sum_{i\notin W}\mathbb E_W[\widetilde N_i] \leq \sum_{i=1}^d\mathbb E_W[\widetilde N_i]\leq dT/4$. Also, $|\mathcal W_{d/4-1}|/|\mathcal W_{d/4}| = \binom{d}{d/4-1}/\binom{d}{d/4}=\frac{d/4}{3d/4+1} \leq 1/3$. Subsequently,

Pinsker's inequality

In this section we concentrate on upper bounding $|\mathbb E_{W\cup\{i\}}[\widetilde N_i]-\mathbb E_W[\widetilde N_i]|$ for any $W\in\mathcal W_{d/4-1}$. Let $P=\mathbb P_W$ and $Q=\mathbb P_{W\cup\{i\}}$ denote the laws under $\theta_W$ and $\theta_{W\cup\{i\}}$, respectively. Then

where $\|P-Q\|_{\mathrm{TV}}=\sup_A|P(A)-Q(A)|$ is the total variation distance between $P$, $Q$, $\mathrm{KL}(P\|Q)=\int(\log\mathrm d P/\mathrm d Q)\mathrm d P$ is the Kullback-Leibler (KL) divergence between $P$, $Q$, and the inequality $\|P-Q\|_{\mathrm{TV}} \leq \sqrt{\frac{1}{2}\mathrm{KL}(P\|Q)}$ is the celebrated Pinsker's inequality.

For every $i\in[d]$ define random variables $N_i := \sum_{t=1}^T \frac{1}{K}\sum_{v_{U}\in S_t}\boldsymbol 1\{i\in U\}$. The next lemma upper bound the KL divergence, which is proved in the supplementary material.

Combining Lemma (ref) and Eq. ((ref)), we have

Further using Cauchy-Schwartz inequality, we have $$\sum_{i=1}^d\sqrt{C_{\mathrm{KL}}\mathbb E_W[N_i]\epsilon^2/d} \leq \sqrt{d}\cdot \sqrt{\sum_{i=1}^d C_{\mathrm{KL}}\mathbb E_W[N_i]\epsilon^2/d},$$ which is further upper bounded by $\sqrt{d}\cdot \sqrt{C_{\mathrm{KL}}T\epsilon^2/4}$ because $\sum_{i=1}^d\mathbb E_W[N_i]\leq dT/4$. Subsequently,

where $C_{\mathrm{KL}}'=C_{\mathrm{KL}}/4$. Setting $\epsilon = \sqrt{d/144C_{\mathrm{KL}}'T}$ we complete the proof of Theorem (ref).

The combinatorial optimization subproblem

The major computational bottleneck of our algorithm is its Step (ref), which involves solving a combinatorial optimization problem. For notational simplicity, we equivalently reformulate this problem as follows:

Here $\widehat u_{tj} := \exp\{v_{tj}^\top\widehat\theta_{t-1}\}$ and $x_{tj} := \widehat I_{t-1}^{-1/2}(\widehat\theta_{t-1})v_{tj}$, both of which can be pre-computed before solving Eq. ((ref)).

A brute-force way to compute Eq. ((ref)) is to enumerate all subsets $S\subseteq[N]$, $|S|\leq K$ and select the one with the largest objective value. Such an approach is not an efficient (polynomial-time) algorithm and is therefore not scalable.

In this section we provide two alternative methods for (approximately) solving the combinatorial optimization problem in Eq. ((ref)). Our first algorithm is based on discretized dynamic programming and enjoys rigorous approximation guarantees. The second algorithm is a computationally efficient greedy heuristic. Although the greedy heuristic does not have rigorous guarantees, our numerical result suggests it works reasonably well (see Sec. (ref)).

Approximation algorithms for assortment optimization

In this section we introduce algorithms with polynomial running times and rigorous approximation guarantees for the optimization task described in Eq. ((ref)). We first formally introduce the concept of $(\alpha,\varepsilon,\delta)$-approximation to characterize the approximation performance, and show that such approximation guarantees imply certain upper bounds on the final regret.

The following lemma shows how $(\alpha,\varepsilon,\delta)$-approximation algorithms imply an upper bound on the accumulated. It is proved using standard analysis of UCB type algorithms, with the complete proof given in the supplementary material.

In the rest of this section we introduce our proposed approximation algorithm and the approximation guarantee. To highlight the main idea of the approximation algorithm, we only describe how the algorithm operates in the univariate ($d=1$) case, while leaving the general multivariate ($d>1$) case to the appendix.

Our approximation algorithm can be roughly divided into three steps. In the first step, we use a “discretization” trick to approximate the objective function using “rounded” parameter values. Such rounding motivates the second step, in which we define “reachable states” and present a simple yet computationally expensive brute-force method to enumerate all reachable states, and establish approximation guarantees for such methods. {This brute-force method is only presented for illustration purposes and will be replaced by a dynamic programing algorithm proposed in the third step.} In particular, a dynamic programming algorithm is developed to compute which states are “reachable” in polynomial time.

The discretization trick

In the univariate case, $\{x_{tj}\}$ are scalars and therefore $x_{tj}x_{tj}^\top$ is simply $x_{tj}^2$. Let $\Delta>0$ be a small positive discretization parameter to be specified later. For all $i\in[N]$, define

where $[a]$ denotes the nearest integer a real number $a$ is rounded into. Intuitively, $\mu_i$ is the real number closest to $\widehat u_{ti}$ that is an integer multiple of the discretization parameter $\Delta$, and similarly for $\alpha_i,\beta_i,\gamma_i$.

The motivation for the definitions of $\{\mu_i,\alpha_i,\beta_i,\gamma_i\}$ is their sufficiency in computing the objective function $\mathrm{ESTR}(S)+\min\{1,\omega\cdot \mathrm{CI}(S)\}$. Indeed, for any $S\subseteq[n]$, $|S|\leq K$, define $\mu=\sum_{j\in S}\mu_j$, $\alpha = \sum_{j\in S}\alpha_j$, $\beta=\sum_{j\in S}\beta_j$, $\gamma=\sum_{j\in S}\gamma_j$ and

Following the definition of $\mathrm{ESTR}(S)$ and $\mathrm{CI}(S)$, it is easy to see that $\widehat{\mathrm{ESTR}}(S)\to \mathrm{ESTR}(S)$ and $\widehat{\mathrm{CI}}(S)\to\mathrm{CI}(S)$ as $\Delta\to 0^+$. The following lemma gives a more precise control of the error between $\widehat{\mathrm{ESTR}}(S)$, $\widehat{\mathrm{CI}}(S)$ and $\mathrm{ESTR}(S)$, $\mathrm{CI}(S)$ using the values of $\Delta$ and the maximum utility parameter in $S$.

The complete proof of Lemma (ref) is relegated to the supplementary material.

Reachable states and a brute-force algorithm

To apply the estimation error bounds in Lemma (ref) one needs to first enumerate $q\in[N]$ giving rise to the item in $S$ with the largest utility parameter $\widehat u_{tq}$. After such an element $q$ is enumerated, the discretization parameter $\Delta=\epsilon_0 U/K=\epsilon_0\max\{1,\widehat u_{tq}\}/K$ can be determined and discretized values $\mu_i,\alpha_i,\beta_i,\gamma_i$ can be computed for all $i\in[N]/\backslash\{q\}$. It is also easy to verify that there are at most $O(K/\epsilon)$ possible values of $\mu_i,\gamma_i$, $O(K\nu/\epsilon)$ possible values of $\alpha_i$ and $O(K\nu^2/\epsilon)$ possible values of $\beta_i$ (recall that $\nu$ is the upper bound of $|x_{tj}$ for all $t$ and $j$).

For any $i\in[N]\cup\{0\}$, $k\in[K]\cup\{0\}$ and $\mu,\alpha,\beta,\gamma\geq 0$ being integer multiples of $\Delta$, we use a tuple $\varsigma_i^k(\mu,\alpha,\beta,\gamma)$ to denote a state. {Here the indices $i$ and $k$ mean that the assortment $S\subseteq\{1,2,\cdots,i\}$ and $|S|=k$.} Clearly there are at most $O(NK^5\nu^3/\epsilon^4)$ different types of states. A state $\varsigma_i^k(\mu,\alpha,\beta,\gamma)$ can be either reachable or non-reachable, as defined below:

A simple way to find all reachable states is to enumerate all $S\subseteq[N]$, $|S|\leq K$ and verify the three conditions in Definition (ref). While such a procedure is clearly computationally intractable, in the next section we will present a dynamic programming approach to compute all reachable states in polynomial time. After all reachable states are computed, enumerate over every $q\in[N]$ and reachable $\zeta_N^k(\cdot,\cdot,\cdot,\cdot)$ for $k\in[K]$ and find $\widehat S$ that maximizes $\widehat{\mathrm{ESTR}}(\widehat S)+\min\{1,\omega\cdot\widehat{\mathrm{CI}}(\widehat S)\}$. The following corollary establishes the approximation guarantee for $\widehat S$, following Lemma (ref).

Corollary (ref) follows easily by plugging in the upper bounds of estimation error in Lemma (ref). By setting $\epsilon_0=\min\{\varepsilon/12, \varepsilon^2/96\omega^2(1+\nu)^2\}$, the algorithm that produces $\widehat S$ satisfies $(1,\varepsilon,0)$-approximation as defined in Definition (ref).

A dynamic programming method for computation of reachable states

In this section we describe a dynamic programming algorithm to compute reachable states in polynomial time. The dynamic programming algorithm is exact and deterministic, therefore approximation guarantees in Corollary (ref) remain valid.

The first step is again to enumerate $q\in[N]$ corresponding to the item in $S$ with the largest utility parameter $\widehat u_{tq}$, and calculating the discretization parameter $\Delta=\epsilon\max\{1,\widehat u_{tq}\}/K$. Afterwards, reachable states are computed in an iterative manner, from $i=0,1,\cdots$ until $i=N$. The initialization is that $\varsigma_0^0(0,0,0,0)$ is reachable. Once a state $\varsigma_i^k(\mu,\alpha,\beta,\gamma)$ is determined to be reachable, the following two states are potentially reachable: $$ \varsigma_{i+1}^k(\mu,\alpha,\beta,\gamma) \;\;\;\;\;\text{and}\;\;\;\;\; \varsigma_{i+1}^{k+1}(\mu+\mu_{i+1},\alpha+\alpha_{i+1}, \beta+\beta_{i+1}, \gamma+\gamma_{i+1}). $$

The first future state $\varsigma_{i+1}^k(\mu,\alpha,\beta,\gamma)$ corresponds to the case of $i+1\notin S$. To determine when such a state is reachable, we review the conditions in Definition (ref) and observe that whenever $i+1\neq q$, the decision $i+1\notin S$ is legal because $q$ must belong to $S$ whenever $i\geq q$ {(note that $q$ is the item in $S$ with the largest estimated utility)}. The second future state $\varsigma_{i+1}^{k+1}(\mu+\mu_{i+1},\alpha+\alpha_{i+1}, \beta+\beta_{i+1}, \gamma+\gamma_{i+1})$ corresponds to the case of $i+1\in S$. Reviewing again the conditions listed in Definition (ref), such a state is reachable if $k+1\leq K$ (meaning that there is still room to include a new item in $S$) and $\widehat u_{t,i+1}\leq \widehat u_{tq}$ (meaning that the new item ($i+1$) to be included has an estimated utility smaller than $\widehat u_{tq}$). Combining both cases, we arrive at the following updated rule of reachability:

Algorithms (ref) and (ref) give pseudo-codes for the proposed dynamic programming approach of computing reachable states and an approximate optimizer of $\widehat{\mathrm{ESTR}}(S)+\min\{1,\omega\cdot\widehat{\mathrm{CI}}(S)\}$.

Finally, we remark on the time complexity of the proposed algorithm. Because the items $j$ we consider in the assortment satisfy $|\widehat u_{ti}| \leq U$, $|r_{ti}| \leq 1$, and $|x_{ti}| \leq \nu$, and all $\mu_i,\alpha_i,\beta_i,\gamma_i$ are integral multiples of $\Delta$, we have (1) $\mu_i$ and $\gamma_i$ take at most $O(K\epsilon_0^{-1})$ possible values; (2) $\alpha_i$ takes at most $(K \nu \epsilon_0^{-1})$ possible values; and (3) $\beta_i$ takes at most $(K \nu^2 \epsilon_0^{-1})$ values. Therefore, the total number of states $\varsigma_i^k(\cdot,\cdot,\cdot,\cdot)$ for fixed $i\in[N]\cup\{0\}$, $k\in[K]$ can be upper bounded by $O(K^8 \nu^3\epsilon_0^{-4})$. The time complexity of Algorithm (ref) is thus upper bounded by $O(K^9N \nu^3\epsilon_0^{-4})$. Alternatively, to achieve $(1,\varepsilon,0)$-approximation, one may set $\epsilon_0=\min\{\varepsilon/12,\varepsilon^2/(96(1+\nu)^2\omega^2)\}$ as suggested by Corollary (ref), resulting in a time complexity of $O(K^9 N \nu^3 \max\{\varepsilon^{-4}, (1 + \nu)^8 \omega^8\varepsilon^{-8}\})$.

{This dynamic programming based approximation algorithm can be extended to multivariate feature vector with $d>1$. The details are presented in Appendix (ref). }

Greedy swapping heuristics

{While the proposed approximation has rigorous approximation guarantees and runs in polynomial time, the large time complexity still prohibits its application to moderately large scale problem instances.} In this subsection, we consider a practically efficient greedy swapping heuristic to approximately solve the combinatorial optimization problem in Eq. ((ref)).

At a higher level, the heuristic algorithm is a “local search” method similar to the Lloyd's algorithm for K-means clustering lloyd1982least, which continuously tries to improve an assortment solution by considering local swapping/addition/deletions until no further improvements are possible. A pseudo-code description of our heuristic method is given in Algorithm (ref).

While the greedy heuristic does not have rigorous guarantees in general, we would like to mention a special case of $\omega=0$, in which Algorithm (ref) does converge to the optimal assortment $S$ maximizing $\mathrm{ESTR}(S)+\min\{1,\omega\cdot\mathrm{CI}(S)\}$ in polynomial time. More specifically, we have the following proposition which is proved in the supplementary material.

Numerical studies

In this section, we present numerical results of our proposed MLE-UCB algorithm. We use the greedy swapping heuristics (Algorithm (ref)) as the subroutine to solve the combinatorial optimization problem in Eq. ((ref)). We will also study the quality of the solution of the greedy swapping heuristics.

\paragraph{Experiment setup.} The unknown model parameter $\theta_0 \in \mathbb{R}^d$ is generated as a uniformly random unit $d$-dimensional vector. The revenue parameters $\{r_{tj}\}$ for $j \in [N]$ are independently and identically generated from the uniform distribution $[0.5, 0.8]$. For the feature vectors $\{v_{tj}\}$, each of them is independently generated as a uniform random vector $v$ such that $\|v\| = 2$ and $v^\top \theta_0 < -0.6$. Here we set an upper bound of $-0.6$ for the inner product so that the utility parameters $u_{tj} = \exp\{v_{tj}^\top \theta_0\}$ are upper bounded by $\exp(-0.6)\approx 0.55$. We set such an upper bound because if the utility parameters are uniformly large, the optimal assortment is likely to pick very few items, leading to degenerated problem instances. In the implementation of our MLE-UCB algorithm, we simply set $T_0 = \lfloor \sqrt{T} \rfloor$ and $\omega = \sqrt{d \ln (T K)}$.

\paragraph{The greedy swapping heuristics.} We first numerically evaluate the solution quality of the greedy swapping heuristic algorithm by focusing on the optimization problem in Eq. (ref). We compare the obtained objective values in Eq. (ref) to the proposed greedy heuristic and the optimal solution (obtained by brute-force search). Instead of generating purely random instances, we consider more realistic instances generated from a dynamic assortment planning process. In particular, for a given $T$, we generate a dynamic assortment optimization problem with parameters $N = 10$, $K = 4$ and $d = 5$, and run the MLE-UCB algorithm till the $T$-th time period. Now the combinatorial optimization problem in Eq. ((ref)) to be solved at the $T$-th time is kept as one testing instance for the greedy swapping algorithm.

For each $T \in \{50, 200, 800\}$, we generate $1000$ such test instances, and compare the solution of the greedy swapping heuristics with the optimal solution obtained by brute-force search in terms of the objective value in Eq. (ref). Table (ref) shows the relative differences between the two solutions at several percentiles, and the mean relative differences. We can see that the approximation quality of the greedy swapping algorithm has already been desirable when $T = 50$, and becomes even better as $T$ grows.

\paragraph{Performance of the MLE-UCB algorithm.} In Figure (ref) we plot the average regret (i.e.\ $\mathrm{regret}/T$) of MLE-UCB algorithm with $N = 1000, K = 10, d = 5$ for the first $T = 10000$ time periods. For each experiment (in both Figure (ref) and other figures), we repeat the experiment for 100 times and report the average value. In Figure (ref) we compare our algorithm with the UCB algorithm for multinomial logit bandit (MNL-UCB) from Agrawal16MNLBandit without utilizing the feature information. Since the MNL-UCB algorithm assumes fixed item utilities that do not change over time, in this experiment we randomly generate one feature vector for each of the $N=1000$ items and this feature vector will be fixed for the entire time span. We can observe that our MLE-UCB algorithm performs much better than MNL-UCB, which suggests the importance of taking the advantage of the contextual information.

\paragraph{Impact of the dimension size $d$.} We study how the dimension of the feature vector impacts the performance of our MLE-UCB algorithm. We fix $N = 1000$ and $K = 10$ and test our algorithm for dimension sizes in $5, 7, 9, 11, \dots, 25$. In Figure (ref), we report the average regret at times $T \in \{4000, 6000, 8000, 10000\}$. We can see that the average regret increases approximately linearly with $d$. This phenomenon matches the linear dependency on $d$ of the main term of the regret Eq. (ref) of the MLE-UCB.

\paragraph{Impact of the number of items $N$.} We compare the performance of our MLE-UCB algorithm for the varying number of items $N$. We fix $K = 10$ and $d = 5$, and test MLE-UCB for $N \in \{1000, 2000, 3000, 4000\}$. In Figure (ref), we report the average regret for the first $T = 10000$ time periods. We observe that the regret of the algorithm is almost not affected by a bigger $N$. This confirms the fact that the regret Eq. (ref) of MLE-UCB is totally independent of $N$.

Conclusion and future directions

In this paper, we study the dynamic assortment planning problem under a contextual MNL model, which incorporates rich feature information into choice modeling. We propose an upper confidence bound (UCB) algorithm based on the local MLE that simultaneously learns the underlying coefficient and makes the decision on the assortment selection. We establish both the upper and lower bounds of the regret. Moreover, we develop an approximation algorithm and a greedy heuristic for solving the key optimization problem in our UCB algorithm.

There are a few possibilities for future work. Technically, there is still a gap of $1/K$ between our upper and lower bounds on regret. Although the cardinality constraint of an assortment $K$ is usually small in practice, it is still a technically interesting question to close this gap. Second, introducing contextual information into choice model is a natural idea for many online applications. This paper explores the standard MNL model, and it would be interesting to extend this work to contextual nested logit and other popular choice models. Finally, it is interesting to incorporate other operational considerations into the model, such as prices or inventory constraints.