  We consider a dynamic assortment selection problem where a seller has a fixed
inventory of $N$ substitutable products and faces an unknown demand that
arrives sequentially over $T$ periods. In each period, the seller needs to
decide on the assortment of products (of cardinality at most $K$) to offer to
the customers. The customer's response follows an unknown multinomial logit
model (MNL) with parameters $v$. The goal of the seller is to maximize the
total expected revenue given the fixed initial inventory of $N$ products. We
give a policy that achieves a regret of $\tilde O\Big(K \sqrt{KN
T}\Big(\sqrt{v_{\text{max}}} + \frac{1}{q_{\text{min}}}\text{OPT}\Big)\Big)$,
where $v_{\text{max}}\leq 1$ is the maximum utility for any product and
$q_{\text{min}}$ the minimum inventory level, under a mild assumption on the
model parameters. In particular, our policy achieves a near-optimal $\tilde
O(\sqrt{T})$ regret in a large-inventory setting.
  Our policy builds upon the UCB-based approach for MNL-bandit without
inventory constraints in [1] and addresses the inventory constraints through an
exponentially sized LP for which we present a tractable approximation while
keeping the $\tilde O(\sqrt{T})$ regret bound.

Machine Learning;Data Structures and Algorithms