Abstract
Off-policy learning is a framework for evaluating and optimizing policies without deploying them, from data collected by another policy. Real-world environments are typically non-stationary and the offline learned policies should adapt to these changes. To address this challenge, we study the novel problem of off-policy optimization in piecewise-stationary contextual bandits. Our proposed solution has two phases. In the offline learning phase, we partition logged data into categorical latent states and learn a near-optimal sub-policy for each state. In the online deployment phase, we adaptively switch between the learned sub-policies based on their performance. This approach is practical and analyzable, and we provide guarantees on both the quality of off-policy optimization and the regret during online deployment. To show the effectiveness of our approach, we compare it to state-of-the-art baselines on both synthetic and real-world datasets. Our approach outperforms methods that act only on observed context.
Introduction
In recommendation systems and search engines, contextual bandits are a standard tool for learning which actions—such as displaying a specific advertisement—maximize rewards like user clicks. Traditional off-policy optimization methods typically assume a stationary environment, where the underlying reward distribution remains constant over time.
However, real-world user behavior is often non-stationary. User intent can shift abruptly; for instance, a user might transition from "shopping mode" to "news-seeking mode" within hours. Standard offline learning algorithms that ignore these shifts often produce "one-size-fits-all" policies that are suboptimal across different contexts. While previous work has addressed non-stationary evaluation, this paper focuses on non-stationary optimization: learning an adaptive policy from historical, non-stationary logs.
Methodology
The authors propose a two-phase framework to handle piecewise-stationary environments:
1. Offline Learning Phase
The objective is to "de-mix" the logged data into distinct regimes. The data is partitioned into categorical latent states using one of two "oracles":
- Change-Point Detector (CD): Identifies specific timestamps where the reward distribution shifts significantly.
- Hidden Markov Model (HMM): A flexible approach that can recognize recurring states (e.g., "weekend" vs. "weekday" patterns).
Once the data is partitioned, a near-optimal sub-policy is learned for each latent state using Inverse Propensity Scoring (IPS).
2. Online Deployment Phase
During live deployment, the agent does not have direct access to the current latent state. To manage this, the sub-policies are treated as "experts." The agent employs a mixture-of-experts algorithm (a variant of Exp4.S) or HMM Posterior Sampling to adaptively switch between sub-policies based on observed real-time performance.
Experimental Results
The approach was evaluated on both synthetic and real-world datasets:
- Synthetic Dataset: A non-contextual bandit with 5 latent states changing every 10,000 rounds over a 100,000-round horizon.
- Yahoo! Clickstream Dataset: A large-scale dataset of user-news interactions. Non-stationarity was modeled by estimating click-through rates (CTR) using a rolling half-day window to capture natural drift.
Key Findings
- Performance Gains: On synthetic data, the HMM-based approach achieved a mean reward of 0.621, outperforming the stationary IPS baseline of 0.545. On the Yahoo! dataset, the proposed methods improved relative CTR by approximately 10% over stationary baselines like POEM and Doubly Robust learning.
- The Bias-Variance Trade-off: The choice of the number of latent states ($k$) is critical. As shown in the results, a small $k$ leads to high bias (under-partitioning), while an excessively large $k$ increases variance due to data sparsity in each slice.
- HMM Superiority: While change-point detectors are theoretically easier to analyze, HMMs often perform better empirically because they can pool data from non-contiguous time segments that share the same latent state.
Conclusion
This work demonstrates that off-policy optimization in non-stationary environments can be effectively decomposed into unsupervised state identification and state-specific optimization. While the HMM approach shows strong empirical results, future work remains to bridge the gap in theoretical guarantees for HMM inference in this setting and to extend the framework to handle smooth, continuous environmental drift.
Summary updated