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

2025/10/10 by Orin Levy, Liad Erez, Levy, Orin +5
Decision Sciences · Computer Science · #Advanced Bandit Algorithms Research #Game Theory and Applications #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2510.09127

Abstract

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 Π we establish an optimal expected regret bound of O (√(KT log |Π|) + √(D log |Π|)) 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(√(KTR_T(O)) + √ d_max D β) assuming FIFO order, where d_max is the maximal delay, R_T(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|) + √d_max D log |F|) which is a √d_max factor away from the lower bound of Ω(√(KT log |F|) + √(D log |F|)) that we also present.

Citations

• Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoff
• A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPs
• Efficient Rate Optimal Regret for Adversarial Contextual MDPs Using Online Function Approximation
• Eluder-based Regret for Stochastic Contextual MDPs
• Optimism in Face of a Context: Regret Guarantees for Stochastic Contextual MDP
• Delayed Feedback in Generalised Linear Bandits Revisited
• Contextual Bandits with Large Action Spaces: Made Practical
• Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedback
• The Statistical Complexity of Interactive Decision Making
• Adapting to Misspecification in Contextual Bandits
• Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination
• Stochastic Multi-Armed Bandits with Unrestricted Delay Distributions
• Learning Adversarial Markov Decision Processes with Delayed Feedback
• Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits
• Bandit Algorithms
• Stochastic bandits with arm-dependent delays
• Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizability
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
• An Optimal Algorithm for Adversarial Bandits with Arbitrary Delays
• Nonstochastic Multiarmed Bandits with Unrestricted Delays
• Introduction to Multi-Armed Bandits
• Bandit Online Learning with Unknown Delays
• Linear Bandits with Stochastic Delayed Feedback
• Stochastic Bandit Models for Delayed Conversions
• Delay and Cooperation in Nonstochastic Bandits
• Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
• Contextual Bandit Learning with Predictable Rewards
• Efficient Optimal Learning for Contextual Bandits
• Contextual Bandit Algorithms with Supervised Learning Guarantees
• The Nonstochastic Multiarmed Bandit Problem

Related

• Adapting to Delays and Data in Adversarial Multi-Armed Bandits
• A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback
• Improved Regret Bounds for Oracle-Based Adversarial Contextual Bandits
• Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback
• Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits