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