Piecewise-Stationary Off-Policy Optimization

Joey Hong, Branislav Kveton, Manzil Zaheer, Yinlam Chow, Amr Ahmed

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 lead to optimal rewards. Often, this learning happens "off-policy," using historical logs to avoid the risks and costs of live experimentation. However, a major hurdle is that most off-policy methods assume a stationary environment—where user behavior remains constant over time.

In practice, environments are non-stationary. Global events or shifting user intents (e.g., moving from "browsing" to "buying") create abrupt changes in behavior. Standard offline policies trained on an "average" of all past data fail to specialize in these distinct phases. This paper introduces a framework to identify hidden "latent states" in historical logs and adaptively select the best sub-policy during live deployment.

Methodology: Latent State Modeling

The core of the proposed approach is modeling the environment as a sequence of latent states that influence both the context and the rewards.

Graphical model of the piecewise-stationary contextual bandit environment with latent state z_t.

The framework operates in two distinct phases:

1. Offline Learning Phase

The goal is to partition logged data into $k$ categorical latent states. The authors propose two primary mechanisms for this:

  • Change-Point Detector ($k$-CD): Identifies abrupt shifts in reward distributions over time.
  • Hidden Markov Model ($k$-HMM): A probabilistic model that treats the environment as a sequence of hidden states.

Once partitioned, a specific sub-policy is learned for each state using Inverse Propensity Scoring (IPS) to correct for the bias of the original logging policy.

2. Online Deployment Phase

During deployment, the system must determine which sub-policy to use without knowing the current latent state. The authors treat the learned sub-policies as "experts" and employ a mixture-of-experts approach. By using algorithms like an adapted Exp4.S or HMM posterior sampling, the system adaptively switches between sub-policies based on real-time performance.

Experimental Evaluation

The approach was evaluated on two benchmarks:

  • Synthetic Dataset: A non-contextual bandit with 5 actions and 5 latent states, featuring abrupt changes every 10,000 rounds.
  • Yahoo! Clickstream Dataset: A real-world dataset of user interactions. The authors simulated non-stationarity by estimating click-through rates (CTR) from sliding windows.

Key Results

The proposed methods, $k$-CD and $k$-HMM, significantly outperformed standard stationary baselines such as IPS, Doubly Robust (DR), and POEM.

Performance comparison on the synthetic dataset, showing mean reward as a function of the number of latent states k.

On the Yahoo! dataset, the $k$-HMM approach improved the relative CTR by up to 10% compared to stationary baselines. The HMM-based approach generally proved more robust than the change-point detector because it can map different time segments back to recurring latent states, effectively reusing learned knowledge.

Discussion and Insights

The primary insight is that modeling latent states prevents "policy blurring," where a single model tries to satisfy contradictory user intents simultaneously. Even without perfect knowledge of the latent state, regret-minimizing switching algorithms can effectively "discover" the optimal sub-policy in real-time.

While the framework is optimized for abrupt shifts (piecewise-stationary), it showed strong performance on the smoother transitions in the Yahoo! data. Future work includes explicitly modeling smooth transitions and automating the selection of the hyperparameter $k$, which currently involves a bias-variance trade-off.

Summary updated

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.
BibTeX
@inproceedings{hong2021piecewise,
  author = {Joey Hong and Branislav Kveton and Manzil Zaheer and Yinlam Chow and Amr Ahmed},
  title = {{Piecewise-Stationary Off-Policy Optimization}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=VxNQsNZNm73},
}

Loading related content...

Figure