Logarithmic Smoothing for Adaptive PAC-Bayesian Off-Policy Learning

Maxime Haddouche, Otmane Sakhi

Introduction

Off-policy learning (OPL) is a cornerstone of modern decision-making systems, from recommendation engines to personalized medicine. Traditionally, OPL is viewed through a static lens: a fixed dataset is used to derive a single improved policy. However, real-world systems are inherently iterative. Policies are deployed, data is collected, and the policy is updated in a continuous loop. This "adaptive" setting offers the potential for significantly faster learning but introduces complex statistical dependencies that challenge standard theoretical guarantees.

The Adaptive Challenge

In adaptive OPL, the data used to train a policy at step $t$ depends on the policies deployed at steps $1$ through $t-1$. This feedback loop invalidates the independent and identically distributed (i.i.d.) assumptions required by many off-policy estimators. Existing methods often resort to "uniform coverage" assumptions—requiring the logging policy to explore all actions equally—which is impractical in high-dimensional spaces. Without careful handling, these dependencies lead to slow convergence rates, typically capped at $O(1/\sqrt{n})$.

Proposed Framework: From adaLS to adaAdjLS

The authors leverage PAC-Bayesian theory to provide tight generalization bounds for these iterative procedures. They introduce two primary algorithms:

  1. adaLS (Algorithm 1): An extension of static Logarithmic Smoothing (LS) to the adaptive case. By utilizing online PAC-Bayesian tools like supermartingales, it handles the sequential nature of the data. However, it remains limited by a "pseudo-variance" term that prevents it from exceeding the $1/\sqrt{n}$ rate.
  2. adaAdjLS (Algorithm 2): The core innovation of the paper. This algorithm introduces an Adjusted LS estimator. By mathematically correcting the linear regularizer, the authors ensure that as the behavior policy converges toward the optimal policy, the variance-like terms in the bound actually diminish.

Theoretical Advancements

The theoretical breakthrough of adaAdjLS is its ability to achieve accelerated convergence rates of $O(1/n^\alpha)$ where $\alpha > 1/2$, assuming a standard "margin condition." This implies that the adaptive process acts as a "data quality multiplier"—as the behavior policy improves, the data it collects becomes more informative for further refinement, allowing the learner to close the gap to the optimal policy faster than static methods.

Empirical Evaluation

The methods were tested by converting standard multiclass classification tasks (MNIST, FashionMNIST, EMNIST, and CIFAR100) into contextual bandit problems. These datasets allow for controlled experiments where the ground truth reward is known, enabling precise measurement of policy risk.

Key Results

  • Deployment Frequency: Fixing the total data budget ($N$) and increasing the number of intermediate deployments ($k$) consistently improved the final policy's performance. This confirms that adaptivity itself is a powerful tool for optimization.
  • Comparison with State-of-the-Art: adaAdjLS significantly outperformed Sequential Counterfactual Risk Minimization (SCRM). While SCRM tended to be overly conservative in early rounds, adaAdjLS balanced exploration and exploitation more effectively.
  • High-Dimensional Scaling: On CIFAR100 (100 actions), the gap between the adjusted and non-adjusted estimators was most pronounced. adaAdjLS achieved a risk of -0.558, compared to -0.508 for the baseline adaLS (where lower is better), demonstrating the advantage of the adjusted estimator in complex action spaces.

Discussion and Limitations

While the framework provides a significant speedup, it is not without limitations. The algorithm still requires the initial behavior policy ($\pi_0$) to provide some level of exploration; if the starting policy never tries an optimal action, the adaptive loop may never discover it. Furthermore, the current theory assumes a stationary context distribution, whereas real-world environments often experience distribution shifts over time.

Conclusion

This work provides a rigorous foundation for adaptive off-policy learning, demonstrating that logarithmic smoothing, when properly adjusted, can break through traditional convergence bottlenecks. By treating adaptivity as a means to improve data quality rather than just a statistical hurdle, the authors offer a path toward more efficient and robust production learning systems.

Summary updated

BibTeX
@inproceedings{haddouche2026logarithmic,
  author = {Maxime Haddouche and Otmane Sakhi},
  title = {{Logarithmic Smoothing for Adaptive PAC-Bayesian Off-Policy Learning}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2026},
  url = {https://openreview.net/forum?id=93CdBSCWoR},
}
Figure