Periodic-GP: Learning Periodic World with Gaussian Process Bandits

Hengrui Cai, Zhihao Cen, Ling Leng, Rui SongarXiv 2021 · arXiv

Abstract

Periodic-GP is a Gaussian Process (GP) bandit framework designed for environments with repeating temporal patterns, such as daily traffic cycles or weekly retail demand. By incorporating a specialized periodic kernel, the algorithm achieves significantly lower regret than standard methods by effectively modeling and exploiting seasonal laws.

Introduction

Most multi-armed bandit algorithms assume a static environment where optimal actions remain constant over time. In reality, many scenarios are non-stationary, with rewards for actions changing dynamically. Existing solutions often rely on piecewise stationarity, which fails in "periodic stationary" environments where conditions change smoothly in repeating cycles. Periodic-GP-UCB addresses this by treating time as a periodic context, allowing the model to share information across cycles and adapt much faster than standard methods.

Methods

Periodic-GP-UCB utilizes a composite kernel to model the reward function $f(a, t)$. The core innovation is the temporal periodic kernel:

$$k_\tau(t, t') = \exp\left(-\frac{2}{l^2} \sin^2\left[\frac{\pi|t-t'|}{\tau}\right]\right)$$

where $\tau$ is the known period (e.g., 24 hours). This kernel is combined with an action-space kernel (such as Squared Exponential) via a product. The algorithm employs the Upper Confidence Bound (UCB) strategy to balance exploration and exploitation, leveraging a "memory" that prioritizes data from similar points in previous cycles rather than discarding historical data.

Experimental Evaluation

The framework was evaluated on synthetic data and a real-world Madrid Traffic Pollution dataset. The Madrid dataset contains hourly nitric oxide (NO) levels from 24 sensors over 10 days, exhibiting strong 24-hour periodicity.

Nitric oxide levels across sensor locations in Madrid, illustrating the 24-hour periodic pattern.

Results

Periodic-GP-UCB consistently outperformed state-of-the-art GP bandit methods in both synthetic and real-world tests. On the Madrid dataset, it reduced cumulative regret by 13% compared to the second-best method, standard GP-UCB. Unlike piecewise-stationary models that struggle with rapid periodic changes, Periodic-GP-UCB's regret curve remains significantly lower and flatter, demonstrating the benefit of explicitly modeling the seasonal law.

Cumulative regret comparison on the Madrid traffic dataset, showing Periodic-GP-UCB's superior performance compared to stationary and non-stationary baselines.

Conclusion

By leveraging the "seasonal law" of periodic environments, Periodic-GP-UCB provides a robust solution for sequential decision-making in cyclic worlds. Future work will focus on handling unknown periods and integrating additional external contexts like weather or special events.

Summary updated

Abstract

We consider the sequential decision optimization on the periodic environment, that occurs in a wide variety of real-world applications when the data involves seasonality, such as the daily demand of drivers in ride-sharing and dynamic traffic patterns in transportation. In this work, we focus on learning the stochastic periodic world by leveraging this seasonal law. To deal with the general action space, we use the bandit based on Gaussian process (GP) as the base model due to its flexibility and generality, and propose the Periodic-GP method with a temporal periodic kernel based on the upper confidence bound. Theoretically, we provide a new regret bound of the proposed method, by explicitly characterizing the periodic kernel in the periodic stationary model. Empirically, the proposed algorithm significantly outperforms the existing methods in both synthetic data experiments and a real data application on Madrid traffic pollution.
BibTeX
@misc{cai2021periodic,
  author = {Hengrui Cai and Zhihao Cen and Ling Leng and Rui Song},
  title = {{Periodic-GP: Learning Periodic World with Gaussian Process Bandits}},
  year = {2021},
  eprint = {2105.14422},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2105.14422},
}
Figure