Summary of Stochastic Contextual Bandits with Graph Feedback: From Independence Number to Mas Number, by Yuxiao Wen et al.
Stochastic contextual bandits with graph feedback: from independence number to MAS number
by Yuxiao Wen, Yanjun Han, Zhengyuan Zhou
First submitted to arxiv on: 12 Feb 2024
Categories
- Main: Machine Learning (cs.LG)
- Secondary: Computer Science and Game Theory (cs.GT); Statistics Theory (math.ST)
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 In this paper, researchers investigate a class of interactive learning problems called contextual bandits with graph feedback. In these problems, taking an action reveals rewards not just for that action but also for neighboring actions in the feedback graph under various contexts. The study establishes a regret lower bound of Ω(√βM(G)T), where βM(G) is a proposed graph-theoretic quantity characterizing the learning limit for this class of problems. The researchers also provide algorithms achieving near-optimal regret for important classes of context sequences and feedback graphs, including transitively closed graphs with applications in auctions and inventory control. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary This paper explores a new type of interactive learning problem called contextual bandits with graph feedback. In these problems, taking an action reveals rewards not just for that action but also for neighboring actions in the feedback graph under various contexts. The study establishes a regret lower bound, which shows how well a learner can do without knowing the best action beforehand. The researchers also provide algorithms to help learners make good choices and achieve near-optimal results. |
