Technical Summary: Sequential Off-Policy Learning with Logarithmic Smoothing

Problem Statement

Off-policy learning enables the training of policies from logged interaction data generated by a behavior policy. While the theoretical foundations of off-policy learning are well-established in the batch setting (where a single policy is learned from a static dataset generated by one behavior policy), real-world systems operate differently. In practice, policies are updated and redeployed repeatedly in a sequential manner: a policy is trained on all historical data, deployed to generate new interactions, and then retrained on the expanded dataset for the next iteration.

Despite the ubiquity of this sequential paradigm in applications like recommender systems and ad placement, it remains largely unexplored theoretically. Existing sequential approaches often rely on strong assumptions, such as uniform coverage of the action space or unrealistic data collection strategies (e.g., exponentially growing batch sizes). Furthermore, current state-of-the-art offline algorithms, which utilize the pessimism principle and PAC-Bayesian frameworks, have not been successfully extended to the sequential setting with rigorous convergence guarantees. This paper addresses the gap between practical sequential deployment and theoretical guarantees, aiming to develop sequential off-policy learning algorithms that are both theoretically sound and empirically effective.

Methodology

The authors propose a framework based on Contextual Bandits where an agent interacts with a data stream over time steps $k \geq 0$. At each step, a new behavior policy $\pi_k$ is deployed to collect a batch of data $S_k$, and the agent updates its policy using the cumulative history $S_{0:k}$.

The methodology is built upon two main algorithmic contributions, both leveraging Online PAC-Bayesian learning tools and Logarithmic Smoothing (LS) estimators:

1. Sequential Logarithmic Smoothing (Algorithm 1)

The first contribution extends the offline Logarithmic Smoothing estimator (introduced by Sakhi et al., 2024) to the sequential setting.

• Estimator: The algorithm uses the standard LS regularizer $h_{LS}(p, q, c) = -\frac{p}{\lambda} \log(1 - \frac{\lambda c}{q})$.
• Mechanism: At each step $k$, the algorithm minimizes a PAC-Bayesian upper bound on the risk, combining the empirical LS risk over all accumulated data $S_{0:k}$ and a KL-divergence term relative to a prior $P$.
• Theoretical Guarantee: Theorem 3.2 establishes a generalization bound for the sequential output $\pi_{k+1}$. The convergence rate is shown to be $O(1/\sqrt{N_k})$, where $N_k$ is the total number of samples. This matches the optimal rate of the batch setting but applies to the sequential accumulation of data.
• Limitation: The authors identify that the pseudo-variance term in the convergence bound does not vanish even if the behavior policy approaches the optimal policy, leading to a convergence rate that does not accelerate beyond $O(1/\sqrt{N_k})$.

2. Sequential Adjusted Logarithmic Smoothing (Algorithm 2)

To overcome the slow convergence of Algorithm 1, the authors introduce a novel Adjusted Logarithmic Smoothing (AdjLS) estimator.

• Estimator: A new regularizer is defined: $h_{adj}(p, q, c) = -\frac{p}{\lambda} \log(1 - \frac{\lambda c}{q(1+\lambda c)})$. This adjustment modifies the performance objective to control the difference between the current policy's risk and a weighted average of past risks.
• Mechanism: Algorithm 2 minimizes the adjusted risk estimator over the cumulative data.
• Theoretical Guarantee: Theorem 4.4 proves that under mild assumptions (specifically, that the optimal actions are covered by the policy class and that the problem has a certain degree of separability, quantified by $\Delta_u > 0$), Algorithm 2 achieves an accelerated convergence rate of $O(1/N_k^\alpha)$ for any $\alpha \in [0.5, 1)$.
• Key Insight: Unlike the standard LS estimator, the adjusted estimator's error term $L(\pi^*, \pi_j)$ vanishes as the behavior policy $\pi_j$ approaches the optimal policy $\pi^*$, enabling faster convergence.

Key Contributions

1. First Sequential PAC-Bayes Algorithms: The paper presents the first off-policy PAC-Bayesian algorithms designed specifically for the sequential setting, providing theoretical convergence guarantees that interpolate between fully batch and fully online regimes.
2. Accelerated Convergence via Adjustment: The authors identify a fundamental limitation in applying standard offline estimators sequentially and propose a principled adjustment (AdjLS) that yields provably accelerated convergence rates under reasonable assumptions.
3. Relaxed Assumptions: The theoretical analysis requires only that the policy class covers the optimal actions (Assumption 3.4), which is strictly weaker than the uniform coverage assumptions required by previous sequential works (e.g., Zenati et al., 2023).
4. Generalization to Non-IID Contexts: The framework is shown to be adaptable to non-stationary environments where context distributions evolve over time, relaxing the i.i.d. assumption on contexts.

Empirical Results

The authors evaluate their methods on standard multiclass datasets (MNIST, FashionMNIST, EMNIST, CIFAR100) converted into contextual bandit problems.

• Sequential vs. Batch: Experiments demonstrate that increasing the number of intermediate policy updates ($k$) consistently improves the final policy performance compared to a single batch update ($k=1$). This validates the benefit of the sequential framework.
• Algorithm Comparison:
  • SeqAdjLS (Algorithm 2) consistently outperforms SeqLS (Algorithm 1), confirming the theoretical advantage of the adjusted estimator.
  • Both proposed methods significantly outperform SCRM (Sequential Counterfactual Risk Minimization, Zenati et al., 2023). The authors note that SCRM tends to be overly conservative, especially in early rounds with small batch sizes, and relies on unrealistic data collection strategies (exponentially growing batches) that discard historical data.
• Impact of Initial Policy: The sequential approach shows substantial gains when the initial behavior policy is far from optimal, particularly in high-dimensional action spaces (e.g., CIFAR100 with 100 actions).

Significance and Claims

The paper claims to close the theoretical gap between practical sequential off-policy learning and rigorous guarantees. By combining online PAC-Bayes techniques with a novel logarithmic smoothing estimator, the authors provide algorithms that:

• Generalize state-of-the-art offline approaches (matching their performance in the batch limit).
• Accelerate learning in sequential settings by leveraging the progressive refinement of the behavior policy.
• Avoid unrealistic assumptions (like uniform coverage) that hinder the applicability of existing sequential methods.

The authors emphasize that while their theoretical analysis relies on the policy class covering optimal actions, this is a significant relaxation compared to prior work. They conclude that the combination of online PAC-Bayes and sequential contextual bandits offers a promising direction for robust, efficient learning in dynamic real-world systems.