Timezone: »

 
Poster
Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits
Siwei Wang · Longbo Huang · John C. S. Lui

Tue Dec 08 09:00 AM -- 11:00 AM (PST) @ Poster Session 1 #239
in Poster Session 2 »
We study the online restless bandit problem, where the state of each arm evolves according to a Markov chain, and the reward of pulling an arm depends on both the pulled arm and the current state of the corresponding Markov chain. In this paper, we propose Restless-UCB, a learning policy that follows the explore-then-commit framework. In Restless-UCB, we present a novel method to construct offline instances, which only requires $O(N)$ time-complexity ($N$ is the number of arms) and is exponentially better than the complexity of existing learning policy. We also prove that Restless-UCB achieves a regret upper bound of $\tilde{O}((N+M^3)T^{2\over 3})$, where $M$ is the Markov chain state space size and $T$ is the time horizon. Compared to existing algorithms, our result eliminates the exponential factor (in $M,N$) in the regret upper bound, due to a novel exploitation of the sparsity in transitions in general restless bandit problems. As a result, our analysis technique can also be adopted to tighten the regret bounds of existing algorithms. Finally, we conduct experiments based on real-world dataset, to compare the Restless-UCB policy with state-of-the-art benchmarks. Our results show that Restless-UCB outperforms existing algorithms in regret, and significantly reduces the running time.

Author Information

Siwei Wang (Tsinghua University)
Longbo Huang (IIIS, Tsinghua Univeristy)
John C. S. Lui (The Chinese University of Hong Kong)

More from the Same Authors