Summary of Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox, by Raymond Zhang and Richard Combes
Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox
by Raymond Zhang, Richard Combes
First submitted to arxiv on: 7 Oct 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 Thompson Sampling (TS) algorithm is proposed for linear combinatorial semi-bandits and subgaussian rewards, addressing the challenge of finite-time regret scaling exponentially with the problem dimension. The algorithm achieves this by leveraging a carefully designed posterior distribution. Furthermore, the paper reveals an intriguing “mismatched sampling paradox” where a learner with knowledge of the reward distributions and correct posterior sampling can perform significantly worse than one without such knowledge, simply sampling from a well-chosen Gaussian posterior. This paradox highlights the importance of considering both the quality of information and the sampling strategy in reinforcement learning. The code used to generate the experiments is publicly available. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary Thompson Sampling (TS) is a new way to make decisions when there are many options and we’re not sure which one is best. In this case, it’s for a special type of problem where we have lots of possibilities and rewards that aren’t always good or bad. The algorithm helps us avoid making mistakes by learning from our choices. But here’s the surprising part: even if we know what rewards to expect, we can still make big mistakes if we don’t choose our samples carefully. |
Keywords
* Artificial intelligence * Reinforcement learning
