In dynamic assortment optimization problems, traditional approaches use sampling-based inventory-agnostic policies. These policies sample assortments of products from a fixed distribution at each time period for different types of customers. The inventory-agnostic nature means that the sampled assortments may include products without remaining inventories, resulting in customers leaving without purchases if they select those products. While this characteristic is usually not a concern, the sampling introduces another source of uncertainty in performance.
This paper presents an algorithm to de-randomize any sampling-based inventory-agnostic policy, ensuring the de-randomized policy offers a deterministic sequence of assortments without degrading performance. Additionally, we provide a variation of the de-randomization algorithm that searches for a deterministic sequence of assortments beyond the support of the original policy. We demonstrate that this variation can be implemented efficiently, provided we can solve the static assortment optimization problem under the choice model governing customer selection.
As a significant technical contribution, we investigate locally-optimal deterministic policies, where changing any single assortment in the policy does not enhance the total expected revenue. We show that any locally-optimal policy guarantees a performance of 1/2 - ε compared to the best sampling-based policy.
Blogger's Review: This paper marks a significant advancement in the field of dynamic assortment optimization by proposing a de-randomization strategy that notably reduces performance uncertainty and enhances predictability. This approach offers new insights into inventory management and customer choice processes, warranting further exploration and application.