Research map / Bandits and online learning / Online convex optimization and games
A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use empirical drift-plus-penalty estimates with confidence-bound exploration under bandit feedback | Constrained bandit problem · Constrained bandit problem (theoretical) | regret: O(\sqrt{K B \log B}) | Helped |
| Use empirical drift-plus-penalty estimates with confidence-bound exploration under bandit feedback | Constrained bandit problem · Constrained bandit problem (theoretical) | constraint-violation: O(\frac{-1}{\sqrt{B}}) | Helped |
| Use known first-order statistics instead of learning them online | LyOff · Constrained bandit problem (theoretical) | regret: O(\sqrt{B}) | Helped |
| Use known first-order statistics instead of learning them online | LyOff · Constrained bandit problem (theoretical) | constraint-violation: O( \frac{-1}{\sqrt{B}} ) | Helped |
| Use the optimal stationary randomized policy as a static benchmark | Constrained bandit problem · Constrained bandit problem (theoretical) | regret: O(1) | Helped |
| Use the optimal stationary randomized policy as a static benchmark | Constrained bandit problem · Constrained bandit problem (theoretical) | constraint-violation: O(\frac{1}{B}) | Helped |
| Use LyOn rather than the optimal stationary randomized policy | K=2 Bernoulli-arm simulation · K=2 Bernoulli-arm simulation | reward rate | No clear effect |
| Use LyOn rather than the optimal stationary randomized policy | K=2 Bernoulli-arm simulation · K=2 Bernoulli-arm simulation | constraint-violation: \Tilde{O}(1/B) | Helped |
| Increase V and tune δ as specified for sufficiently large budgets (ablation) | LyOn · Constrained bandit problem (theoretical) | constraint-violation: O(\frac{-1}{\sqrt{B}}) | Helped |
| Increase V and tune δ as specified for sufficiently large budgets (ablation) | LyOn · Constrained bandit problem (theoretical) | regret: O(\sqrt{K B\log B}) | Mixed |
Closest papers by meaning
- Delay and Cooperation in Nonstochastic Linear Bandits (NeurIPS 2020 · similarity 0.87)
- Tight Rates for Bandit Control Beyond Quadratics (NeurIPS 2024 · similarity 0.85)
- Policy Optimization for CMDPs with Bandit Feedback: Learning Stochastic and Adversarial Constraints (ICML 2025 · similarity 0.85)
- Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits (NeurIPS 2025 · similarity 0.85)
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.85)
- Greedy Algorithms for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.