Summary of Restless Linear Bandits, by Azadeh Khaleghi
Restless Linear Bandits
by Azadeh Khaleghi
First submitted to arxiv on: 17 May 2024
Categories
- Main: Machine Learning (stat.ML)
- Secondary: Information Theory (cs.IT); 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 A more general formulation of the linear bandit problem is considered, allowing for dependencies over time. Specifically, an unknown stationary sequence of parameters gives rise to payoffs, which can be viewed as a generalization of both classical linear bandits with iid noise and finite-armed restless bandits. An approximation is proposed whose error is controlled by the dependence between consecutive parameters. The LinMix-UCB algorithm is introduced for exponential mixing rates, shown to incur a sub-linear regret of O(sqrt(dnpolylog(n))) compared to an oracle that always plays a multiple of the expected parameter. The main challenge is ensuring exploration-exploitation robustness against long-range dependencies, addressed through Berbee’s coupling lemma. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary In this paper, researchers solve a complex problem called linear bandits by allowing for dependencies over time. This makes it more realistic and challenging. They propose an algorithm that balances exploring new options with exploiting known good ones, while being robust to these dependencies. The results are impressive, showing that the algorithm can make decisions quickly without sacrificing too much performance. |
Keywords
» Artificial intelligence » Generalization
