Learning and Optimization with Seasonal Patterns

• 成果类型: Article
• 署名作者: Chen, Ningyuan; Wang, Chun; Wang, Longlin
• 署名单位: University of Toronto; University Toronto Mississauga; University of Toronto; Tsinghua University; Harvard University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2023.0017
• 发表日期: 2025

摘要

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 (O) over tilde(root T Sigma T-K(k-1)k), where T-k is the period of arm k. Moreover, we establish a general lower bound Omega(root T max(k){T-k}) for any policy. Therefore, our policy is near optimal up to a factor of root K.