Learning and Optimization with Seasonal Patterns

A standard assumption adopted in the multiarmed 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 in which the mean rewards are time-varying. In this paper, we consider a nonstationary 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}\left(\sqrt{T{\sum }_{k=1}^K{T}_k}\right)$, where T_k is the period of arm k. Moreover, we establish a general lower bound $\mathrm{\Omega }(\sqrt{T {\text{max}}_k\{T_k\}})$ for any policy. Therefore, our policy is near optimal up to a factor of $\sqrt{K}$.

Funding: The research of N. Chen is partly supported by the Natural Sciences and Engineering Research Council of Canada [Discovery Grant RGPIN-2020-04038]. C. Wang acknowledges support from the National Natural Science Foundation of China [Grants 72293561 and 71802115] and the Tsinghua University Initiative Scientific Research Program.

Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2023.0017.