Dynamic Assortment Selection under the Nested Logit Models
share
We study a stylized dynamic assortment planning problem during a selling season of finite length T, by considering a nested multinomial logit model with M nests and N items per nest. Our policy simultaneously learns customers' choice behavior and makes dynamic decisions on assortments based on the current knowledge. It achieves the regret at the order of Õ(√(MNT)+MN^2), where M is the number of nests and N is the number of products in each nest. We further provide a lower bound result of Ω(√(MT)), which shows the optimality of the upper bound when T>M and N is small. However, the N^2 term in the upper bound is not ideal for applications where N is large as compared to T. To address this issue, we further generalize our first policy by introducing a discretization technique, which leads to a regret of Õ(√(M)T^2/3+MNT^1/3) with a specific choice of discretization granularity. It improves the previous regret bound whenever N>T^1/3. We provide numerical results to demonstrate the empirical performance of both proposed policies.
READ FULL TEXT