$K$ is the cardinality constraint of an offered assortment, which is usually small. When $K$ is a constant, our policy is optimal up to logarithmic factors. In the exploitation phase of the UCB algorithm, we need to solve a combinatorial optimization for assortment optimization based on the learned information. We further develop an approximation algorithm and an efficient greedy heuristic. The effectiveness of the proposed policy is further demonstrated by our numerical studies.

    **keywords**: Dynamic assortment optimization, regret analysis, contextual information, bandit learning, upper confidence bounds.
author:
- 'Xi Chen [^1]'
- Yining Wang
- Yuan Zhou
bibliography:
- 'refs.bib'
title:
- Dynamic Assortment Optimization with Changing Contextual Information
- 'Supplementary Material for: Dynamic Assortment Optimization with Changing Contextual Information'
---

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 