Online Nonstationary and Nonlinear Bandits with Recursive Weighted Gaussian Process

Real-world problems in e-commerce and other practical services are framed as nonstationary and contextual multi-armed bandit (MAB) problems, driving the active development of MAB policies. Current MAB policies leverage nonlinear regression models, such as neural networks and Gaussian processes (GP). However, these regression models lack a recursive learning mechanism in nonstationary environments. As a result, MAB policies must consider all training data amassed over an extended period of time, leading to escalating computational complexity in sequential decision-making as the volume of training data grows. To address this online performance issue, we propose an online nonstationary and nonlinear contextual MAB policy using a GP regression model that employs Random Fourier Features and weighted Recursive Least Squares with regularization. The proposed policy enables fast decision-making based on recursive learning and accurately corrects the estimation error of the predictive distribution of the GP caused by recursive weighting the regularization at any given time. Simulation results of the nonstationary and nonlinear contextual MAB problem show that the proposed policy significantly reduces the computation time while maintaining the cumulative reward, and the proposed error correction method resolves the trade-off between the estimation accuracy of the prediction distribution and the computation time.