Timezone: »

 
Poster
Regret Bounds for Thompson Sampling in Episodic Restless Bandit Problems
Young H Jung · Ambuj Tewari

Tue Dec 10 05:30 PM -- 07:30 PM (PST) @ East Exhibition Hall B + C #21
in Algorithms -- Bandit Algorithms »
Restless bandit problems are instances of non-stationary multi-armed bandits. These problems have been studied well from the optimization perspective, where the goal is to efficiently find a near-optimal policy when system parameters are known. However, very few papers adopt a learning perspective, where the parameters are unknown. In this paper, we analyze the performance of Thompson sampling in episodic restless bandits with unknown parameters. We consider a general policy map to define our competitor and prove an $\tilde{\bigO}(\sqrt{T})$ Bayesian regret bound. Our competitor is flexible enough to represent various benchmarks including the best fixed action policy, the optimal policy, the Whittle index policy, or the myopic policy. We also present empirical results that support our theoretical findings.
Keywords: Bandit Algorithms · Online Learning · Algorithms
[ Paper]  [ Poster] 

Author Information

Young H Jung (University of Michigan)
Ambuj Tewari (University of Michigan)

More from the Same Authors