Abstract
Modern recommendation systems face the challenge of non-stationary user interests. This paper introduces PSLinUCB, a contextual bandit framework designed for piecewise-stationary environments where user preferences shift abruptly and asynchronously. By employing a sliding-window change detection mechanism and efficient model restarts, the proposed algorithm achieves sublinear regret and demonstrates superior performance on real-world news and music datasets compared to stationary and global non-stationary baselines.
Introduction
Contextual bandits are the "engine" behind many personalized recommenders, balancing the exploration of new items with the exploitation of known user preferences. However, most existing models assume a stationary environment. In reality, user interests are dynamic; a user might suddenly lose interest in a specific product category due to a life event while maintaining interest in others. This paper addresses the realistic scenario where changes are asynchronous and distinct across different items, a condition traditional models struggle to handle.
Methodology: The PSLinUCB Algorithm
The authors propose PSLinUCB (Piecewise-Stationary LinUCB), which tracks changes at the individual item (arm) level rather than globally.
Reward Models
- Disjoint Payoff Model: Assumes each item has its own unique preference vector that can change independently over time.
- Hybrid Payoff Model: Rewards depend on both an arm-specific (time-varying) vector and a joint (time-invariant) vector shared across all arms, capturing both fleeting and stable preferences.
Change Detection and Adaptation
PSLinUCB maintains a sliding window of recent observations for each arm. It constantly compares actual rewards against model predictions. If the prediction error exceeds a threshold, the algorithm signals a change and "warm-starts" a new model using the data currently in the sliding window. This approach prevents the "cold start" problem typically associated with model resets.
Experimental Results
The authors evaluated PSLinUCB on the Yahoo! Today Module (news) and LastFM (music) datasets.
As shown in the performance trends, PSLinUCB variants consistently maintain higher Click-Through Rates (CTR) compared to stationary baselines like standard LinUCB and UCB. Specifically, PSLinUCB-Disjoint achieved a 2.7% CTR gain on the Yahoo! dataset, while the Hybrid model showed a 2.4% gain on LastFM.
Crucially, PSLinUCB outperformed DenBand, a state-of-the-art non-stationary bandit. Because DenBand assumes global changes, it often discards useful knowledge about items whose preferences haven't shifted. By tracking changes at the arm level, PSLinUCB avoids this inefficiency.
Key Insights and Future Work
- Asynchronicity Matters: Avoiding global resets allows the model to retain valuable information about stable user interests.
- Theoretical Guarantees: The authors proved that PSLinUCB achieves sublinear regret $O(\sqrt{T})$, ensuring long-term convergence to the optimal strategy.
- Scalability: A limitation of the current model is its computational complexity ($O(K \cdot d^2)$) when dealing with millions of items. Future work suggests clustering similar arms to reduce the parameter space.
In conclusion, PSLinUCB provides a robust and theoretically sound solution for recommendation in dynamic environments, offering significant performance lifts in real-world applications.
Summary updated