Multi-Armed Bandits with Metric Movement Costs
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 O(max{C 1/3 T 2/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 Θ(max{k 1/3 T 2/3 , √ kT }) where C = Θ(k), and (ii) the interval metric with regret Θ(max{T 2/3 , √ kT }) where C = Θ(1). For infinite metrics spaces with Lipschitz loss functions, we derive a tight regret bound of Θ(T d+1 d+2 ) where d ≥ 1 is the Minkowski dimension of the space, which is known to be tight even when there are no switching costs.
The authors consider the setting of Multi-Armed Bandits with movement costs.
Basically, the set of arms is endowed with a metric and the player pays a price when she changes her action depending on the distance with the latest played action. 
The main contribution of the paper is to generalize previous work to general metrics. They prove matching (up to log factors) upper and lower bounds for the problem and adapt the Slowly-Moving Bandit Algorithm to general metrics (it was previously designed for intervals only). 
To my opinion the paper is pretty well written and pleasant to read. The literature is well cited. The analysis seem to be quite similar to the previous analysis of the SMB algorithm. The analysis and the algorithm are based on the same idea of hierarchical trees and the main ingredient of the proof seems to deal with non-binary trees. Though, I think it is a nice contribution.
Some remarks:
- your notion of complexity only deals with parametric spaces of arms. Do you think you can get results for non-parametric spaces, like Lipschitz functions?
- what is the complexity of the algorithm for instance if the space of arms is [0,1]^d? I.e. to build the correct tree and to run the algorithm
- your hierarchical tree remind me the chaining technique. Though the later cannot be used for bandits, I am wondering if there is any connexion.
- maybe some figures would help to understand the algorithm
- is it possible to calibrate eta and the depth of the tree in T?
- do you think it may be possible to learn the metric online? 
Typos:
- l171: a dot is missing
- l258: "actions K. and"
- Algo1: a space is missing; add eta > 0 to the input; 
- Eq (3): some formating issue
- l422: I did not understand the explanation on condition (2)c, don't we have $k > = C$ by definition of C?
- 476: tilde are missing