Summary of Corruption-robust Linear Bandits: Minimax Optimality and Gap-dependent Misspecification, by Haolin Liu et al.
Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification
by Haolin Liu, Artin Tajdini, Andrew Wagenmaker, Chen-Yu Wei
First submitted to arxiv on: 10 Oct 2024
Categories
- Main: Machine Learning (cs.LG)
- Secondary: Machine Learning (stat.ML)
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 A unified framework is proposed to analyze corrupted rewards in linear bandits, comparing two types of corruptions: strong and weak. For stochastic linear bandits, the paper fully characterizes the gap between minimax regret under strong and weak corruptions. Upper and lower bounds are obtained for corrupted adversarial linear bandits with dependencies on corruption level. A connection is revealed between corruption-robust learning and learning with gap-dependent mis-specification, allowing for a general reduction that enables any corruption-robust algorithm to handle gap-dependent misspecification. A specialized algorithm is developed to achieve optimal bounds for gap-dependent misspecification in linear bandits. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary Linear bandits are used to learn when facing corrupted rewards. The paper compares strong and weak corruptions, which affect the rewards differently. For some types of corruption, it’s possible to fully understand how well a learner will do. The paper also connects this type of learning to other types that involve guessing what the best action is. |
