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 