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

arXiv: https://arxiv.org/abs/2510.09127 · HTML: https://mlsanity.com/paper/2510.09127/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 43 references that are in the map.
- First posted on arXiv 10 Oct 2025.

## Builds on (most cited first, 26 of 26)

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles](https://mlsanity.com/paper/2002.04926/) (2020)
- [Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability](https://mlsanity.com/paper/2003.12699/) (2020)
- [Adapting to Misspecification in Contextual Bandits](https://mlsanity.com/paper/2107.05745/) (2021)
- [Delay and Cooperation in Nonstochastic Bandits](https://mlsanity.com/paper/1602.04741/) (2016)
- [Markov Decision Processes with Continuous Side Information](https://mlsanity.com/paper/1711.05726/) (2017)
- [Linear Bandits with Stochastic Delayed Feedback](https://mlsanity.com/paper/1807.02089/) (2018)
- [Stochastic Bandit Models for Delayed Conversions](https://mlsanity.com/paper/1706.09186/) (2017)
- [Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination](https://mlsanity.com/paper/2107.02237/) (2021)
- [Nonstochastic Multiarmed Bandits with Unrestricted Delays](https://mlsanity.com/paper/1906.00670/) (2019)
- [An Optimal Algorithm for Adversarial Bandits with Arbitrary Delays](https://mlsanity.com/paper/1910.06054/) (2019)
- [Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits](https://mlsanity.com/paper/2007.07876/) (2020)
- [Stochastic bandits with arm-dependent delays](https://mlsanity.com/paper/2006.10459/) (2020)
- [Stochastic Multi-Armed Bandits with Unrestricted Delay Distributions](https://mlsanity.com/paper/2106.02436/) (2021)
- [Learning Adversarial Markov Decision Processes with Delayed Feedback](https://mlsanity.com/paper/2012.14843/) (2020)
- [Contextual Bandits with Large Action Spaces: Made Practical](https://mlsanity.com/paper/2207.05836/) (2022)
- [Delayed Feedback in Generalised Linear Bandits Revisited](https://mlsanity.com/paper/2207.10786/) (2022)
- [Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedback](https://mlsanity.com/paper/2201.13172/) (2022)
- [Bandit Online Learning with Unknown Delays](https://mlsanity.com/paper/1807.03205/) (2018)
- [A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs](https://mlsanity.com/paper/2305.08629/) (2023)
- [Optimism in Face of a Context: Regret Guarantees for Stochastic Contextual MDP](https://mlsanity.com/paper/2207.11126/) (2022)
- [Eluder-based Regret for Stochastic Contextual MDPs](https://mlsanity.com/paper/2211.14932/) (2022)
- [Efficient Rate Optimal Regret for Adversarial Contextual MDPs Using Online Function Approximation](https://mlsanity.com/paper/2303.01464/) (2023)
- [Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoff](https://mlsanity.com/paper/2405.17796/) (2024)

## Built on by (most cited first, 5 of 5)

- [Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Bandits](https://mlsanity.com/paper/2602.09456/) (2026)
- [A Reduction from Delayed to Immediate Feedback for Online Convex Optimization with Improved Guarantees](https://mlsanity.com/paper/2602.02634/) (2026)
- [Online KL-Regularized Reinforcement Learning with Function Approximation under Misspecification](https://mlsanity.com/paper/2606.06053/) (2026)
- [Capacity-Constrained Online Convex Optimization with Delayed Feedback](https://mlsanity.com/paper/2606.11711/) (2026)
- [Pooling and Drift in Delayed Bandits](https://mlsanity.com/paper/2609.01761/) (2026)

## Abstract (arXiv)

We present regret minimization algorithms for the contextual multi-armed bandit (CMAB) problem over K actions in the presence of delayed feedback, a scenario where loss observations arrive with delays chosen by an adversary. As a preliminary result, assuming direct access to a finite policy class Pi we establish an optimal expected regret bound of  O (√KT log |Pi| + √D log |Pi|)  where D is the sum of delays. For our main contribution, we study the general function approximation setting over a (possibly infinite) contextual loss function class  F  with access to an online least-square regression oracle O over F. In this setting, we achieve an expected regret bound of O(√KTRT(O) + √ dmax D β) assuming FIFO order, where dmax is the maximal delay, RT(O) is an upper bound on the oracle's regret and β is a stability parameter associated with the oracle. We complement this general result by presenting a novel stability analysis of a Hedge-based version of Vovk's aggregating forecaster as an oracle implementation for least-square regression over a finite function class F and show that its stability parameter β is bounded by log |F|, resulting in an expected regret bound of O(√KT log |F| + √dmax D log |F|) which is a √dmax factor away from the lower bound of Omega(√KT log |F| + √D log |F|) that we also present.