Sequential Off-Policy Learning with Logarithmic Smoothing

Maxime Haddouche, Otmane Sakhi

TL;DR

This paper introduces and theoretically analyzes novel algorithms for sequential off-policy learning, a practical scenario where policies are continuously updated and redeployed using new interaction data. The proposed methods, based on Logarithmic Smoothing and PAC-Bayesian techniques, match state-of-the-art batch performance and significantly outperform existing approaches in the sequential setting, with one algorithm offering accelerated convergence.

What Problem Does This Paper Address?

In many real-world applications like recommender systems or ad placement, decision-making systems (policies) are not static. Instead, they are continuously updated and redeployed. This means a policy is trained on historical data, deployed to collect new interactions, and then retrained using all the accumulated data (old and new) to produce an improved policy. This "sequential off-policy learning" setting is common in practice but has been largely overlooked theoretically. Existing theoretical work often focuses on the "batch" setting (learning a single policy from a fixed dataset) or makes strong assumptions that don't align with practical sequential deployments. This paper aims to bridge this gap by developing and analyzing algorithms that are theoretically sound and practically relevant for sequential off-policy learning.

Methods

The core contribution is the development of two sequential off-policy learning algorithms.

  1. Sequential Logarithmic Smoothing (SeqLS): This algorithm extends the existing Logarithmic Smoothing (LS) PAC-Bayesian approach to the sequential setting. It leverages online PAC-Bayesian techniques to handle the continuous arrival of data batches and reuses all previously collected data for retraining. This approach provides theoretical guarantees and matches the performance of state-of-the-art batch methods.
  2. Sequential Adjusted Logarithmic Smoothing (SeqAdjLS): Recognizing a limitation in the convergence rate of SeqLS, the authors introduce a principled adjustment to the LS estimator. This adjustment leads to an algorithm with accelerated convergence rates to the optimal policy under mild conditions, outperforming SeqLS and other sequential methods.

Both algorithms are framed within the PAC-Bayesian learning theory, which provides generalization bounds and guides the optimization process. The theoretical analysis relies on controlling the risk of a policy through a combination of empirical risk estimation and a regularization term (KL divergence), adapted for the sequential setting.

Datasets

The paper evaluates its algorithms on standard benchmark datasets commonly used in machine learning and reinforcement learning:

  • MNIST
  • FashionMNIST
  • EMNIST
  • CIFAR100

These datasets are transformed into contextual bandit problems for evaluation.

Key Insights and Ideas

  • Sequential Learning is Crucial in Practice: The paper highlights that while batch learning is well-studied, real-world systems often operate in a sequential manner. Ignoring this can lead to suboptimal performance.
  • PAC-Bayesian Tools Adapt Well: The authors demonstrate that PAC-Bayesian techniques, particularly online variants, are powerful tools for deriving theoretical guarantees in the sequential off-policy learning setting.
  • A Simple Adjustment Yields Accelerated Convergence: The key insight for SeqAdjLS is that a specific adjustment to the objective function can significantly speed up convergence without sacrificing theoretical guarantees, a common challenge in sequential learning.
  • Coverage is Key, Not Uniformity: The theoretical analysis requires the policy class to "cover" optimal actions, a weaker assumption than the uniform coverage often needed in prior work, making the algorithms more broadly applicable.

Key Results

  • Theoretical Guarantees: Both SeqLS and SeqAdjLS are proven to converge to the optimal policy.
  • Matching Batch Performance: In the batch setting (equivalent to one sequential update), the proposed algorithms match the performance of state-of-the-art offline methods.
  • Outperforming Sequential Baselines: Empirically, SeqAdjLS consistently outperforms SeqLS and a recent sequential method (SCRM) across various datasets and configurations.
  • Accelerated Convergence: SeqAdjLS demonstrates faster convergence rates, particularly noticeable when the initial behavior policy is less informative. For instance, the paper shows accelerated rates of $O(1/\sqrt{mk})$ compared to $O(1/\sqrt{m})$ for the batch case, and $O(1/n)$ for the online case.
  • Effect of Initial Policy: The quality of the initial behavior policy ($\pi_0$) significantly impacts performance, with sequential updates providing substantial gains when $\pi_0$ is far from optimal.

Limitations and Future Work

  • Non-IID Contexts: While the paper presents a theoretical extension for non-IID contexts (Section C), the main algorithms and empirical evaluations focus on the IID assumption. An open question is whether the accelerated convergence guarantees can be extended to non-stationary settings.
  • Policy Class Coverage: The theoretical analysis relies on the assumption that the policy class sufficiently covers optimal actions. Investigating whether this requirement can be relaxed is a potential future direction.
  • Hyperparameter Tuning: While theoretical guidance is provided for parameter selection (e.g., $\lambda$), practical tuning might still be necessary. The paper notes a trade-off between convergence speed and the complexity of constants.

Summary updated

Abstract

Off-policy learning enables training policies from logged interaction data. Most prior work considers the batch setting, where a policy is learned from data generated by a single behavior policy. In real systems, however, policies are updated and redeployed repeatedly, each time training on all previously collected data while generating new interactions for future updates. This sequential off-policy learning setting is common in practice but remains largely unexplored theoretically. In this work, we present and study a simple algorithm for *sequential off-policy learning*, combining Logarithmic Smoothing (LS) estimation with online PAC-Bayesian tools. We further show that a principled adjustment to LS improves performance and accelerates convergence under mild conditions. The algorithms introduced generalize previous work: they match state-of-the-art offline approaches in the batch case and substantially outperform them when policies are updated sequentially. Empirical evaluations highlight both the benefits of the sequential framework and the strength of the proposed algorithms.
BibTeX
@inproceedings{haddouche2026sequential,
  author = {Maxime Haddouche and Otmane Sakhi},
  title = {{Sequential Off-Policy Learning with Logarithmic Smoothing}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2026},
  url = {https://openreview.net/forum?id=93CdBSCWoR},
}
Figure