Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback

Orin Levy, Liad Erez, Alon Cohen, Yishay Mansour

Introduction

In the landscape of online learning, the Contextual Multi-Armed Bandit (CMAB) framework serves as a cornerstone for decision-making under uncertainty. Real-world applications—ranging from personalized medicine to real-time ad bidding—frequently encounter two significant hurdles: the need for complex function approximation to handle high-dimensional contexts and the presence of delayed feedback. While previous literature has addressed these challenges in isolation or within restricted linear settings, this research provides the first theoretical regret bounds for adversarial CMAB with general function approximation and delayed feedback.

Problem Formulation

The paper investigates an adversarial setting where an environment chooses a sequence of contexts and losses. Unlike stochastic bandits, the adversarial model makes no assumptions about the distribution of losses, allowing for a more robust but mathematically challenging analysis.

In this specific problem, at each round $t$, the learner observes a context $x_t$, chooses an action $a_t$, and incurs a loss. However, the feedback (the loss value) is not revealed until round $t + d_t$, where $d_t$ represents the delay. The goal is to minimize the cumulative regret—the difference between the learner's total loss and the loss of the best fixed policy in hindsight—while utilizing a general function class $\mathcal{F}$ to model the relationship between contexts and losses.

Algorithmic Frameworks

1. Policy Class Learning (EXP4-DALE)

For scenarios involving a finite set of policies $\Pi$, the authors introduce a variant of the EXP4 algorithm. The key innovation here is the use of "delay-adapted loss estimators" (DALE). These estimators are specifically designed to correct for the drift caused by delays by coupling the context of the current round with sampling distributions from future rounds. This mechanism ensures that the learner's updates remain relevant even when based on stale information.

2. General Function Approximation (DA-FA)

The primary contribution of the paper is the Delay-Adapted Function Approximation (DA-FA) algorithm. This algorithm utilizes an online least-squares regression oracle to predict losses. To maintain theoretical tractability, the authors assume a First-In-First-Out (FIFO) feedback order, where observations arrive in the order they were generated.

The Necessity of Stability

A pivotal insight of this work is the identification of oracle stability as a prerequisite for learning under delay. The authors prove a significant negative result: without a stability constraint, any algorithm will suffer linear regret (failing to learn) even if the delay is as small as a single round.

To address this, they define $\beta$-stability, requiring that the oracle's predictions do not fluctuate excessively upon receiving a single new data point. They demonstrate that a Hedge-based version of Vovk’s aggregating forecaster satisfies this stability requirement under the "realizability" assumption (where the true loss function is contained within $\mathcal{F}$). Their analysis shows that the expected sum of KL-divergences between consecutive iterates of the Vovk oracle is bounded by $\log |\mathcal{F}|$, independent of the total time horizon $T$.

Theoretical Results

The paper establishes several key regret bounds that characterize the difficulty of the delayed adversarial setting:

  • Finite Policy Class: For a class $\Pi$, the regret is bounded by $O(\sqrt{KT \log |\Pi|} + \sqrt{D \log |\Pi|})$, where $D = \sum d_t$ is the total delay. The authors provide a matching lower bound, confirming this result is minimax optimal.
  • General Function Approximation: For a function class $\mathcal{F}$, the DA-FA algorithm achieves an expected regret of $O(\sqrt{KTR_T(\mathcal{O})} + \sqrt{d_{max}D\beta})$.
  • Vovk Oracle Performance: When instantiated with the Vovk aggregating forecaster, the bound becomes $O(\sqrt{KT \log |\mathcal{F}|} + \sqrt{d_{max}D \log |\mathcal{F}|})$.

While these results represent a breakthrough, a theoretical gap remains: the upper bound for function approximation includes a factor of $\sqrt{d_{max}}$ (the maximum delay) that is absent from the lower bound, suggesting potential for further refinement.

Limitations and Future Directions

While this work sets a new theoretical benchmark, it operates under specific constraints:

  1. FIFO Feedback: The assumption that feedback arrives in order may be violated in highly distributed systems.
  2. Realizability: The current stability analysis of the Vovk oracle relies on the true function existing within $\mathcal{F}$. Extending these results to "agnostic" settings remains an open challenge.
  3. Tightening Bounds: Future research is needed to determine if the $\sqrt{d_{max}}$ factor is a fundamental requirement or an artifact of the current analysis that can be removed.

Summary updated

BibTeX
@inproceedings{levy2025regret,
  author = {Orin Levy and Liad Erez and Alon Cohen and Yishay Mansour},
  title = {{Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=McPNQEDEZE},
}
Figure