Research map / Bandits and online learning / Online convex optimization and games
Better Best of Both Worlds Bounds for Bandits with Switching Costs
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 a switch-count stopping rule to leave Tsallis-INF and then run a block no-regret algorithm | Tsallis-INF for bandits with switching costs · Stochastically constrained adversarial regime | expected pseudo-regret with switching cost: \mathcal{O}\brk2{\sum_{i\ne i^\star} \frac{(\lambda K)^{2/3}T^{1/3}+\log T}{\Delta_i}} -> \mathcal{O}\brk[]2{\min\brk[c] | Helped |
| Use a switch-count stopping rule and a block-algorithm fallback | Tsallis-INF for bandits with switching costs · Oblivious adversarial regime | expected pseudo-regret with switching cost: \mathcal{O}\left((\lambda K)^{1/3}T^{2/3}\right) | No clear effect |
| Use a switch-count stopping rule and a block-algorithm fallback | Switch Tsallis, Switch! · Stochastically constrained adversarial regime, K=2 | pseudo-regret with switching cost lower bound: \tilde\Omega\brk1{\min\brk[c]1{1/\Delta^2,K^{1/3}T^{2/3}}} | Mixed |
Closest papers by meaning
- An Algorithm for Stochastic and Adversarial Bandits with Switching Costs (ICML 2021 · similarity 0.94)
- Phase Transitions and Cyclic Phenomena in Bandits with Switching Constraints (NeurIPS 2019 · similarity 0.91)
- Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback (NeurIPS 2025 · similarity 0.91)
- Taming Heavy-Tailed Losses in Adversarial Bandits and the Best-of-Both-Worlds Setting (NeurIPS 2024 · similarity 0.89)
- Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.88)
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.88)
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.