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.
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.
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