Regime Switching Bandits

Abstract

We study a multi-armed bandit problem where the rewards exhibit regime switching. Specifically, the distributions of the random rewards generated from all arms are modulated by a common underlying state modeled as a finite-state Markov chain. The agent does not observe the underlying state and has to learn the transition matrix and the reward distributions. We propose a learning algorithm for this problem, building on spectral method-of-moments estimations for hidden Markov models, belief error control in partially observable Markov decision processes and upper-confidence-bound methods for online learning. We also establish an upper bound $O(T^{2/3}\sqrt{\log T})$ for the proposed learning algorithm where $T$ is the learning horizon. Finally, we conduct proof-of-concept experiments to illustrate the performance of the learning algorithm.

References in corpus (8)

• A Survey on Practical Applications of Multi-Armed and Contextual Bandits
• Bounded Regret for Finite-Armed Structured Bandits
• Online Regret Bounds for Undiscounted Continuous Reinforcement Learning
• Discretized Approximations for POMDP with Average Cost
• Rotting Bandits
• Learning and Optimization with Seasonal Patterns
• Exploration Bonus for Regret Minimization in Undiscounted Discrete and Continuous Markov Decision Processes
• Multi-Armed Bandits for Correlated Markovian Environments with Smoothed Reward Feedback

Cited by in corpus (4)

• Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism
• Restless Bandits with Many Arms: Beating the Central Limit Theorem
• Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in Multi-Agent RL and Inventory Control
• Learning and Optimization with Seasonal Patterns