= \frac{\sum_{j\in S}r_{tj}\exp\{v_{tj}^\top\theta_0\}}{1+\sum_{j\in S}\exp\{v_{tj}^\top \theta_0\}}.$$ [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. .]{}

Our objective is to design policy $\pi$ such that the regret $$\label{eq:regret}
\mathrm{Regret}(\{S_t\}_{t=1}^T) =\mathbb E^\pi\sum_{t=1}^T R_t(S_t^*) - R_t(S_t) \;\;\;\;\;\text{where}\;\;S_t^*=\arg\max_{S\subseteq[N], |S|\leq K} R_t(S)$$ 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).]{}

An MLE-UCB policy and its regret {#sec:UCB}
================================

[[Pure exploration]{}]{}: for $t=1,\cdots,T_0$, pick $S_t=\{\ell_t\}$ for a single product $\ell_t$ sampled uniformly at random from $\{1,\cdots,N\}$ and record purchasing actions $(i_1,\cdots,i_{T_0})$

Compute a pilot estimator using global MLE: $\theta^*\in\arg\max_{\theta\in\mathbb R^d} \sum_{t'=1}^{T_0} \log p_{\theta,t}(i_{t'}|S_{t'})$

Remark: the expectations admit the following closed-form expressions: $\mathbb E_{\theta,t}[r_{tj}|S] = \sum_{j\in S} p_{\theta,t}(j|S)r_{tj} =\frac{\sum_{j\in S}r_{tj}\exp\{v_{tj}^\top\theta\}}{1+\sum_{j\in S}\exp\{v_{tj}^\top\theta\}}$; $\mathbb E_{\theta,t}[v_{tj}|S] = \sum_{j\in S}p_{\theta,t}(j|S)v_{tj} = \frac{\sum_{j\in S}v_{tj}\exp\{v_{tj}^\top\theta\}}{1+\sum_{j\in S}\exp\{v_{tj}^\top\theta\}}$; $\mathbb E_{\theta,t}[v_{tj}v_{tj}^\top|S] = \sum_{j\in S}p_{\theta,t}(j|S)v_{tj}v_{tj}^\top = \frac{\sum_{j\in S}v_{tj}v_{tj}^\top\exp\{v_{tj}^\top\theta\}}{1+\sum_{j\in S}\exp\{v_{tj}^\top\theta\}}$.

We propose an MLE-UCB policy, described in Algorithm \[alg:mle-ucb\].

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 