Summary of Provably Efficient Reinforcement Learning For Adversarial Restless Multi-armed Bandits with Unknown Transitions and Bandit Feedback, by Guojun Xiong et al.
Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedback
by Guojun Xiong, Jian Li
First submitted to arxiv on: 2 May 2024
Categories
- Main: Machine Learning (cs.LG)
- Secondary: Artificial Intelligence (cs.AI); 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 The paper presents a novel reinforcement learning algorithm for restless multi-armed bandits (RMAB) under instantaneous activation constraints. The algorithm learns to maximize adversarial rewards while satisfying the constraint that at most B arms can be activated per decision epoch. The authors develop a biased adversarial reward estimator and a low-complexity index policy to deal with bandit feedback and unknown transitions. They demonstrate a regret bound of (H), where T is the number of episodes and H is the episode length. This is the first algorithm to achieve () regret for adversarial RMAB in challenging settings. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary The paper explains a new way for computers to make decisions when they can only pick some options at a time. This is useful for things like choosing which ads to show people or which products to recommend. The algorithm uses two key ideas: one helps the computer deal with not knowing what will happen if it chooses something, and the other helps it decide which options are best. The algorithm does well even when the rewards change each episode, and this is important because real-life situations can be like that. |
Keywords
» Artificial intelligence » Reinforcement learning
