Research map / Bandits and online learning / Online convex optimization and games
Multi-Armed Bandits with Metric Movement Costs
Tomer Koren, Roi Livni, Yishay Mansour
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 SMB with a tree metric dominating the finite action metric | Finite-metric bandits with movement costs · Finite metric spaces | movement regret: \wt{O}(\max\{\dimu^{1/3} T^{2/3}, \sqrt{kT}\}) | Improved |
| Allow arbitrary finite metric movement costs rather than only uniform switching costs | Finite-metric bandits · Finite metric spaces | movement regret: \wt{O}(\max\{\dimu^{1/3} T^{2/3}, \sqrt{kT}\}) | Mixed |
| Use SMB directly on a general HST instead of only a complete binary balanced HST | SMB · 2-HST metric spaces | movement regret: O\LR{ H \sqrt{2^H T \mathcal{C} \smash{\log\mathcal{C} }} + H 2^{-H} T } | Improved |
| Discretize the infinite metric space and use the finite-space algorithm under Lipschitz losses | Bandits with movement costs · Infinite metric spaces with 1-Lipschitz losses | movement regret: \wt{O}(T^\frac{d+1}{d+2}) | Improved |
| Add movement costs to the Lipschitz metric-space bandit setting | Lipschitz metric-space bandits · Infinite metric spaces with matching upper and lower Minkowski dimensions | regret: \wt{O}(T^\frac{d+1}{d+2}) | No clear effect |
Closest papers by meaning
- Phase Transitions and Cyclic Phenomena in Bandits with Switching Constraints (NeurIPS 2019 · similarity 0.90)
- Nonparametric Contextual Bandits in Metric Spaces with Unknown Metric (NeurIPS 2019 · similarity 0.90)
- Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards (NeurIPS 2025 · similarity 0.89)
- Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret (NeurIPS 2026 · similarity 0.89)
- Adaptive Regret for Bandits Made Possible: Two Queries Suffice (ICLR 2024 · similarity 0.89)
- Tracking Most Significant Shifts in Infinite-Armed Bandits (ICML 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.
