Timezone: »

 
Poster
Phase Transitions and Cyclic Phenomena in Bandits with Switching Constraints
David Simchi-Levi · Yunzong Xu

Tue Dec 10 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #25
in Algorithms -- Bandit Algorithms »

We consider the classical stochastic multi-armed bandit problem with a constraint on the total cost incurred by switching between actions. Under the unit switching cost structure, where the constraint limits the total number of switches, we prove matching upper and lower bounds on regret and provide near-optimal algorithms for this problem. Surprisingly, we discover phase transitions and cyclic phenomena of the optimal regret. That is, we show that associated with the multi-armed bandit problem, there are equal-length phases defined by the number of arms and switching costs, where the regret upper and lower bounds in each phase remain the same and drop significantly between phases. The results enable us to fully characterize the trade-off between regret and incurred switching cost in the stochastic multi-armed bandit problem, contributing new insights to this fundamental problem. Under the general switching cost structure, our analysis reveals a surprising connection between the bandit problem and the shortest Hamiltonian path problem.

Keywords: Bandit Algorithms · Online Learning · Algorithms
[ Paper]  [ Slides] 

Author Information

David Simchi-Levi (MIT)
Yunzong Xu (MIT)

More from the Same Authors