Summary of Beyond Primal-dual Methods in Bandits with Stochastic and Adversarial Constraints, by Martino Bernasconi et al.
Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints
by Martino Bernasconi, Matteo Castiglioni, Andrea Celli, Federico Fusco
First submitted to arxiv on: 25 May 2024
Categories
- Main: Machine Learning (cs.LG)
- Secondary: None
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 addresses a generalized bandit with knapsacks problem, where a learner aims to maximize rewards while satisfying long-term constraints. The goal is to design algorithms that perform optimally under both stochastic and adversarial constraints. Previous works have used primal-dual methods, requiring stringent assumptions such as Slater’s condition or knowledge of a lower bound on the parameter. This paper proposes an alternative approach based on optimistic constraint estimation using UCB-like techniques. The algorithm consists of two components: a regret minimizer working with moving strategy sets and an estimate of the feasible set as an optimistic weighted empirical mean of previous samples. The key challenge is designing adaptive weights for stochastic and adversarial constraints. The proposed algorithm has a simpler design and analysis compared to previous approaches, providing logarithmic bounds in the number of constraints and O(sqrt(T)) regret in stochastic settings without Slater’s condition. |
| Low | GrooveSquid.com (original content) | Low Difficulty Summary The paper looks at a problem where you want to make good decisions while also following certain rules or limits. Previous solutions required some specific conditions to be met, but this paper finds a different way to solve it using optimistic estimates. The new approach has two parts: one that makes good choices and another that figures out what’s allowed. The tricky part is finding the right balance between making good decisions and following the rules. This paper shows that its solution works well in both predictable and unpredictable situations, without needing those specific conditions. |
