Research map / Bandits and online learning / Online convex optimization and games
Bandits with Feedback Graphs and 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 adaptive mini-batches sized according to the probability of sampling revealing actions and explore an approximate dominating set | Online learning with a fixed undirected feedback graph and switching costs · Fixed feedback graph | pseudo-regret upper bound: \tilde O(\alpha(G)^{\frac 1 3} T^{\frac 2 3}) -> \tilde O(\gamma(G)^{\frac 1 3}T^{\frac 2 3}) | Helped |
| Use mini-batched corralling of star-graph algorithms instead of the general adaptive mini-batch algorithm | Online learning with a fixed feedback graph and switching costs · Fixed feedback graph | pseudo-regret upper bound: \tilde O\left(\sqrt{|R|} \, T^{\frac 2 3}\right) versus \tilde O(\gamma(G)^{\frac 1 3}T^{\frac 2 3}) | Hurt |
| Use partial counterfactual feedback with adaptive mini-batching | Policy regret algorithm · m-memory adaptive adversary | policy regret upper bound: \tilde O((m\gamma(G))^{\frac 1 3}T^{\frac 2 3}) | Helped |
| Use a revealing action as the exploration target and set its mini-batch size according to its sampling probability | Star-graph algorithm · Star graph | pseudo-regret upper bound: \tilde O(T^{\frac 2 3}) versus \tilde O(\alpha(G)^{\frac 1 3} T^{\frac 2 3}) | Helped |
Closest papers by meaning
- Simultaneously Learning Stochastic and Adversarial Bandits with General Graph Feedback (ICML 2022 · similarity 0.91)
- Adversarial Combinatorial Semi-bandits with Graph Feedback (ICML 2025 · similarity 0.91)
- Bandits with Ranking Feedback (NeurIPS 2024 · similarity 0.90)
- Stochastic contextual bandits with graph feedback: from independence number to MAS number (NeurIPS 2024 · similarity 0.89)
- Multi-Armed Bandits With Best-Action Queries (NeurIPS 2026 · similarity 0.89)
- Efficient Graph Bandit Learning with Side-Observations and Switching Constraints (AAAI 2025 · 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.