Summary of Stochastic Bandits with Linear Constraints, by Aldo Pacchiano et al.
Stochastic Bandits with Linear Constraints
by Aldo Pacchiano, Mohammad Ghavamzadeh, Peter Bartlett, Heinrich Jiang
First submitted to arxiv on: 17 Jun 2020
Categories
- Main: Machine Learning (cs.LG)
- Secondary: 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 A machine learning algorithm, called optimistic pessimistic linear bandit (OPLB), is proposed to solve a constrained contextual linear bandit setting. The goal is to maximize the expected cumulative reward over T rounds while keeping each policy’s expected cost below a certain threshold tau. OPLB is shown to have an upper bound on its T-round regret of (), where d is the number of contextual features and c_0 is the cost of a known feasible action. The algorithm is also specialized for multi-armed bandits, achieving a regret bound of () in K-armed bandits. This represents a improvement over the regret bound obtained by casting multi-armed bandits as an instance of contextual linear bandits. Theoretical results are validated through simulations. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary The paper studies a type of machine learning problem called constrained contextual linear bandit, where the goal is to make good decisions while following certain rules. The proposed algorithm, OPLB, helps solve this problem by balancing reward and cost. It’s shown that OPLB can achieve good results quickly and efficiently, especially when dealing with many different options (multi-armed bandits). This matters because it could be used in real-life situations where decisions need to be made based on incomplete information. |
Keywords
* Artificial intelligence * Machine learning
