Exploration Optimization for Dynamic Assortment Personalization under Linear Preferences
Abstract
We study dynamic assortment personalization, where an online retailer adaptively selects assortments based on customer attributes to learn preferences and maximize revenue. We assume that product utilities depend linearly on customer attributes through an unknown coefficient matrix, leading to an exploration–exploitation trade-off. We identify price-driven and linearity-driven exploration efficiencies, showing that not all products need to be offered to all customer profiles to recover optimal assortments. We establish an instance-dependent regret lower bound characterized by a linear program, which we call the Regret Lower Bound (RLB) problem. Because the RLB has a complex structure and depends non-trivially on unknown parameters, we introduce an alternative formulation, called the Exploration-Optimization problem, that yields an interpretable exploration structure and can be formulated as a tractable mixed-integer linear program. We develop learning policies that select efficient exploration sets by solving either problem and establish a regret upper bound for the Exploration-Optimization policy. Using data from a large Chilean retailer, we demonstrate that our policies substantially outperform Thompson sampling in terms of both regret and computational efficiency, while remaining scalable in practice.

