Summary of Nearly Minimax Optimal Regret For Multinomial Logistic Bandit, by Joongkyu Lee et al.
Nearly Minimax Optimal Regret for Multinomial Logistic Bandit
by Joongkyu Lee, Min-hwan Oh
First submitted to arxiv on: 16 May 2024
Categories
- Main: Machine Learning (stat.ML)
- Secondary: Machine Learning (cs.LG)
GrooveSquid.com Paper Summaries
GrooveSquid.com’s goal is to make artificial intelligence research accessible by summarizing AI papers in simpler terms. Each summary below covers the same AI paper, written at different levels of difficulty. The medium difficulty and low difficulty versions are original summaries written by GrooveSquid.com, while the high difficulty version is the paper’s original abstract. Feel free to learn from the version that suits you best!
| Summary difficulty | Written by | Summary |
|---|---|---|
| High | Paper authors | High Difficulty Summary Read the original abstract here |
| Medium | GrooveSquid.com (original content) | Medium Difficulty Summary This paper tackles the contextual multinomial logit (MNL) bandit problem, where an agent selects an assortment based on context and user feedback follows an MNL choice model. The authors address the discrepancy between lower and upper regret bounds, particularly regarding maximum assortment size K. They establish a regret lower bound of O(d√T/K) under uniform rewards and propose the OFU-MNL+ algorithm, which achieves a matching upper bound. Instance-dependent minimax regret bounds are also provided for uniform rewards. Under non-uniform rewards, they prove a lower bound of O(d√T) and an upper bound of Õ(d√T), achieved by OFU-MNL+. Empirical studies support these findings. This work is the first to achieve minimax optimality in the contextual MNL bandit literature for both uniform and non-uniform reward settings, and proposes a computationally efficient algorithm that achieves this optimality up to logarithmic factors. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary This paper explores how a computer program can make good decisions based on what people like. It looks at a special problem called the contextual MNL bandit problem. The authors want to know how well the program can do when it chooses things for people based on context and gets feedback from those people. They find that there are some limits to how well the program can do, but they also come up with an efficient way for the program to make good choices most of the time. |
