Learning and Optimization with Seasonal Patterns

Abstract

A standard assumption adopted in the multi-armed bandit (MAB) framework is that the mean rewards are constant over time. This assumption can be restrictive in the business world as decision-makers often face an evolving environment where the mean rewards are time-varying. In this paper, we consider a non-stationary MAB model with $K$ arms whose mean rewards vary over time in a periodic manner. The unknown periods can be different across arms and scale with the length of the horizon $T$ polynomially. We propose a two-stage policy that combines the Fourier analysis with a confidence-bound-based learning procedure to learn the periods and minimize the regret. In stage one, the policy correctly estimates the periods of all arms with high probability. In stage two, the policy explores the periodic mean rewards of arms using the periods estimated in stage one and exploits the optimal arm in the long run. We show that our learning policy incurs a regret upper bound $\tilde{O}(\sqrt{T{\sum }_{k=1}^K{T}_k})$ where $T_k$ is the period of arm $k$. Moreover, we establish a general lower bound $\Omega (\sqrt{T{\max }_k\{T_k\}})$ for any policy. Therefore, our policy is near-optimal up to a factor of $\sqrt{K}$.

References in corpus (10)

• Provably Optimal Algorithms for Generalized Linear Contextual Bandits
• Efficient Contextual Bandits in Non-stationary Worlds
• Taming Non-stationary Bandits: A Bayesian Approach
• Hedging the Drift: Learning to Optimize under Non-Stationarity
• Rotting Bandits
• Regime Switching Bandits
• A Linear Bandit for Seasonal Environments
• Bandits with adversarial scaling
• Periodic-GP: Learning Periodic World with Gaussian Process Bandits
• Regulating Greed Over Time in Multi-Armed Bandits

Cited by in corpus (6)

• Hedging the Drift: Learning to Optimize under Non-Stationarity
• Regime Switching Bandits
• Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in Multi-Agent RL and Inventory Control
• Periodic-GP: Learning Periodic World with Gaussian Process Bandits
• Lifelong Learning in Multi-Armed Bandits
• Multi-armed Bandit Requiring Monotone Arm Sequences