Summary of Bridging Rested and Restless Bandits with Graph-triggering: Rising and Rotting, by Gianmarco Genalti and Marco Mussi and Nicola Gatti and Marcello Restelli and Matteo Castiglioni and Alberto Maria Metelli
Bridging Rested and Restless Bandits with Graph-Triggering: Rising and Rotting
by Gianmarco Genalti, Marco Mussi, Nicola Gatti, Marcello Restelli, Matteo Castiglioni, Alberto Maria Metelli
First submitted to arxiv on: 9 Sep 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 A novel framework called Graph-Triggered Bandits (GTBs) is proposed to generalize and extend traditional rested and restless bandit settings. The GTB model introduces a graph defined over arms, where edges represent trigger effects between arm pulls. This unifying framework encompasses both rested and restless bandits as special cases for specific graphs. Two case studies are explored: rising and rotting monotonic bandits, where the expected reward of an arm grows or decreases with the number of triggers. The paper discusses optimal policies, algorithms, and theoretical guarantees for these scenarios, highlighting the complexity of instance-dependent terms that depend on graph structure. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary Graph-Triggered Bandits (GTBs) is a new way to make decisions in situations where the reward changes over time because of what we do or the environment. This model combines two older ideas, rested and restless bandits, which are useful for real-world problems like choosing the best ad to show someone online. The GTB framework uses a special graph that shows how different actions affect each other. For example, if you choose one ad, it might make another ad more or less appealing. The paper looks at two specific types of situations where this happens: when the reward gets better and worse over time, and when it stays the same. |
