Regret Bounds for Thompson Sampling in Episodic Restless Bandit Problems
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{\mathcal{O}}(\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.
Code (1)
Tasks
Multi-Armed BanditsThompson SamplingSimilar Papers 제목 키워드 기반
Thompson Sampling in Non-Episodic Restless Bandits
Restless bandit problems assume time-varying reward distributions of the arms, which adds flexibility to the model but makes the analysis more challenging. We study learning algorithms over the unknown reward distributio…
Open-Ended Question AnsweringThompson SamplingOn learning Whittle index policy for restless bandits with scalable regret
Reinforcement learning is an attractive approach to learn good resource allocation and scheduling policies based on data when the system model is unknown. However, the cumulative regret of most RL algorithms scales as $\…
SchedulingThompson SamplingSliding-Window Thompson Sampling for Non-Stationary Settings
$\textit{Restless Bandits}$ describe sequential decision-making problems in which the rewards evolve with time independently from the actions taken by the policy-maker. It has been shown that classical Bandit algorithms …
Decision MakingSequential Decision MakingThompson SamplingFeel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learning
Thompson Sampling has been widely used for contextual bandit problems due to the flexibility of its modeling power. However, a general theory for this class of methods in the frequentist setting is still lacking. In this…
Multi-Armed Banditsregressionreinforcement-learningReinforcement Learning+2Prior-free and prior-dependent regret bounds for Thompson Sampling
We consider the stochastic multi-armed bandit problem with a prior distribution on the reward distributions. We are interested in studying prior-free and prior-dependent regret bounds, very much in the same spirit as the…
Thompson Sampling