Phase Transitions in Bandits with Switching Constraints
This work addresses a fundamental problem in online decision-making for researchers and practitioners, offering new insights into the trade-off between regret and switching costs, though it is incremental in extending classical bandit theory.
The paper tackles the stochastic multi-armed bandit problem with a switching cost constraint, proving matching upper and lower bounds on optimal regret and providing efficient algorithms. It reveals surprising phase transitions in how the optimal regret rate changes with the switching budget, characterized by abrupt changes or subtler transitions depending on the number of arms.
We consider the classical stochastic multi-armed bandit problem with a constraint that limits the total cost incurred by switching between actions to be no larger than a given switching budget. For this problem, we prove matching upper and lower bounds on the optimal (i.e., minimax) regret, and provide efficient rate-optimal algorithms. Surprisingly, the optimal regret of this problem exhibits a non-conventional growth rate in terms of the time horizon and the number of arms. Consequently, we discover surprising "phase transitions" regarding how the optimal regret rate changes with respect to the switching budget: when the number of arms is fixed, there are equal-length phases, where the optimal regret rate remains (almost) the same within each phase and exhibits abrupt changes between phases; when the number of arms grows with the time horizon, such abrupt changes become subtler and may disappear, but a generalized notion of phase transitions involving certain new measurements still exists. The results enable us to fully characterize the trade-off between the regret rate and the incurred switching cost in the stochastic multi-armed bandit problem, contributing new insights to this fundamental problem. Under the general switching cost structure, the results reveal interesting connections between bandit problems and graph traversal problems, such as the shortest Hamiltonian path problem.