# Multi-Armed Bandits with Metric Movement Costs

arXiv: https://arxiv.org/abs/1710.08997 · HTML: https://mlsanity.com/paper/1710.08997/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Oct 2017.

## Built on by (most cited first, 6 of 6)

- [Revisiting Smoothed Online Learning](https://mlsanity.com/paper/2102.06933/) (2021)
- [Lazy OCO: Online Convex Optimization on a Switching Budget](https://mlsanity.com/paper/2102.03803/) (2021)
- [Learning in Markov Games with Adaptive Adversaries: Policy Regret, Fundamental Barriers, and Efficient Algorithms](https://mlsanity.com/paper/2411.00707/) (2024)
- [Learning Revenue Maximization using Posted Prices for Stochastic Strategic Patient Buyers](https://mlsanity.com/paper/2202.06143/) (2022)
- [The Traveling Bandit: A Framework for Bayesian Optimization with Movement Costs](https://mlsanity.com/paper/2410.14533/) (2024)
- [Learning from Local Walks on Dynamic Graphs with Bandit Feedback](https://mlsanity.com/paper/2607.10571/) (2026)

## Abstract (arXiv)

We consider the non-stochastic Multi-Armed Bandit problem in a setting where there is a fixed and known metric on the action space that determines a cost for switching between any pair of actions. The loss of the online learner has two components: the first is the usual loss of the selected actions, and the second is an additional loss due to switching between actions. Our main contribution gives a tight characterization of the expected minimax regret in this setting, in terms of a complexity measure C of the underlying metric which depends on its covering numbers. In finite metric spaces with k actions, we give an efficient algorithm that achieves regret of the form widetildeO(maxC1/3T2/3,√kT), and show that this is the best possible. Our regret bound generalizes previous known regret bounds for some special cases: (i) the unit-switching cost regret widetildeTheta(maxk1/3T2/3,√kT) where C=Theta(k), and (ii) the interval metric with regret widetildeTheta(maxT2/3,√kT) where C=Theta(1). For infinite metrics spaces with Lipschitz loss functions, we derive a tight regret bound of widetildeTheta(T^fracd+1d+2) where d ≥ 1 is the Minkowski dimension of the space, which is known to be tight even when there are no switching costs.