An Optimal Greedy Heuristic with Minimal Learning Regret for the Markov Chain Choice Model

We study the assortment optimization problem and show that local optima are global optima for all discrete choice models that can be represented by the Markov Chain model. We develop a forward greedy heuristic that finds an optimal assortment for the Markov Chain model and runs in $O(n^2)$ iterations. The heuristic has performance bound $1/n$ for any regular choice model which is best possible among polynomial heuristics. We also propose a backward greedy heuristic that is optimal for Markov chain model and requires fewer iterations. Numerical results show that our heuristics performs significantly better than the estimate then optimize method and the revenue-ordered assortment heuristic when the ground truth is a latent class multinomial logit choice model. Based on the greedy heuristics, we develop a learning algorithm that enjoys asymptotic optimal regret for the Markov chain choice model and avoids parameter estimations, focusing instead on binary comparisons of revenues