EvoClusterBandit: Adaptive Partitioned Bandit Algorithm for Dynamic Environments with Latent Variable Modeling

Maynooth International Engineering College, Fuzhou University, Fuzhou, China

^* Corresponding author: This email address is being protected from spambots. You need JavaScript enabled to view it.

Abstract

Existing multi-armed bandit algorithms struggle in dynamic environments with latent shifts such as abrupt changes in user behavior or contextual features. Traditional methods like sliding-window UCB and discounted UCB passively adapt, leading to suboptimal regret bounds and degraded performance in real-world tasks like advertising and recommendation. We propose EvoClusterBandit, a framework that integrates three key innovations: (1) proactive environment partitioning through incremental clustering to capture latent shifts, (2) region-specific optimization with adaptive LinUCB, and (3) cross-region knowledge transfer to avoid strategy fragmentation. Theoretical analysis proves improved regret bounds, achieving an ((√T)) reduction over global strategies under non-stationarity. Experiments show consistent gains: 12.7% CTR on Criteo, 9.2% on MovieLens, and 14.6% on synthetic datasets, with regret reduced by up to 71% compared to SW-UCB. By bridging unsupervised clustering with contextual bandits, EvoClusterBandit offers an effective solution to dynamic decision-making in non-stationary environments, a long-standing challenge in applications requiring adaptive exploration and exploitation.