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

• URL: http://arxiv.org/abs/2510.09127v1
• Date: Fri, 10 Oct 2025 08:28:23 GMT
• Title: Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback
• Authors: Orin Levy, Liad Erez, Alon Cohen, Yishay Mansour,
• Abstract summary: We present regret algorithms for the contextual multi-armed bandit (CMAB) problem over $K$ actions.<n>We establish an optimal expected regret bound of $ O (sqrtKT log |Pi| + sqrtD log |Pi|) $ where $D$ is the sum of delays.
• Score: 43.017740308285845
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 $\Pi$ we establish an optimal expected regret bound of $ O (\sqrt{KT \log |\Pi|} + \sqrt{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 $ \mathcal{F} $ with access to an online least-square regression oracle $\mathcal{O}$ over $\mathcal{F}$. In this setting, we achieve an expected regret bound of $O(\sqrt{KT\mathcal{R}_T(\mathcal{O})} + \sqrt{ d_{\max} D \beta})$ assuming FIFO order, where $d_{\max}$ is the maximal delay, $\mathcal{R}_T(\mathcal{O})$ is an upper bound on the oracle's regret and $\beta$ 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 $\mathcal{F}$ and show that its stability parameter $\beta$ is bounded by $\log |\mathcal{F}|$, resulting in an expected regret bound of $O(\sqrt{KT \log |\mathcal{F}|} + \sqrt{d_{\max} D \log |\mathcal{F}|})$ which is a $\sqrt{d_{\max}}$ factor away from the lower bound of $\Omega(\sqrt{KT \log |\mathcal{F}|} + \sqrt{D \log |\mathcal{F}|})$ that we also present.

Related papers

• A Mathematical Theory of Top-$k$ Sparse Attention via Total Variation Distance [7.014801584517052]
  We develop a unified framework certified Top-$k$ attention truncation that quantifies error at both the distribution and output levels.<n>We show that the total-variation distance coincides with the discarded softmax tail mass and satisfies $mathrmTV(P,hat P)=1-e-mathrmTV(P,hat P)=1-e-mathrmTV(P,hat P)$.
  arXiv  Detail & Related papers  (2025-12-08T15:36:41Z)
• Sharp Gap-Dependent Variance-Aware Regret Bounds for Tabular MDPs [54.28273395444243]
  We show that the Monotonic Value Omega (MVP) algorithm achieves a variance-aware gap-dependent regret bound of $$tildeOleft(left(sum_Delta_h(s,a)>0 fracH2 log K land mathttVar_maxtextc$.
  arXiv  Detail & Related papers  (2025-06-06T20:33:57Z)
• An Information-Theoretic Analysis of Thompson Sampling for Logistic Bandits [36.37704574907495]
  We study the performance of the Thompson Sampling algorithm for logistic bandit problems.<n>We derive a bound order $O(d/alphaqrtT log(beta T/d))$ of regret incurred after $T$ expected of Sampling steps.
  arXiv  Detail & Related papers  (2024-12-03T21:55:41Z)
• Eluder-based Regret for Stochastic Contextual MDPs [43.19667415823089]
  We present the E-UC$3$RL algorithm for regret minimization in Contextual Markov Decision Processes (CMDPs) Our algorithm is efficient (assuming efficient offline regression oracles) and enjoys a regret guarantee of $ widetildeO(H3 sqrtT |S| |A|d_mathrmE(mathcalP)$.
  arXiv  Detail & Related papers  (2022-11-27T20:38:47Z)
• Optimism in Face of a Context: Regret Guarantees for Stochastic Contextual MDP [46.86114958340962]
  We present regret algorithms for contextual MDPs under minimum reachability assumption. Our approach is the first optimistic approach applied to contextual MDPs with general function approximation.
  arXiv  Detail & Related papers  (2022-07-22T15:00:15Z)
• A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback [25.68113242132723]
  We present a modified tuning of the algorithm of Zimmert and Seldin [2020] for adversarial multiarmed bandits with delayed feedback. We simultaneously achieves a near-optimal adversarial regret guarantee in the setting with fixed delays. We also present an extension of the algorithm to the case of arbitrary delays.
  arXiv  Detail & Related papers  (2022-06-29T20:49:45Z)
• On Submodular Contextual Bandits [92.45432756301231]
  We consider the problem of contextual bandits where actions are subsets of a ground set and mean rewards are modeled by an unknown monotone submodular function. We show that our algorithm efficiently randomizes around local optima of estimated functions according to the Inverse Gap Weighting strategy.
  arXiv  Detail & Related papers  (2021-12-03T21:42:33Z)
• Scale-Free Adversarial Multi-Armed Bandit with Arbitrary Feedback Delays [21.94728545221709]
  We consider the Scale-Free Adversarial Multi Armed Bandit (MAB) problem with unrestricted feedback delays. textttSFBanker achieves $mathcal O(sqrtK(D+T)L)cdot rm polylog(T, L)$ total regret, where $T$ is the total number of steps and $D$ is the total feedback delay.
  arXiv  Detail & Related papers  (2021-10-26T04:06:51Z)
• The planted matching problem: Sharp threshold and infinite-order phase transition [25.41713098167692]
  We study the problem of reconstructing a perfect matching $M*$ hidden in a randomly weighted $ntimes n$ bipartite graph. We show that if $sqrtd B(mathcalP,mathcalQ) ge 1+epsilon$ for an arbitrarily small constant $epsilon>0$, the reconstruction error for any estimator is shown to be bounded away from $0$.
  arXiv  Detail & Related papers  (2021-03-17T00:59:33Z)
• Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
  We study online learning with bandit feedback (i.e. learner has access to only zeroth-order oracle) where cost/reward functions admit a "pseudo-1d" structure. We show a lower bound of $min(sqrtdT, T3/4)$ for the regret of any algorithm, where $T$ is the number of rounds. We propose a new algorithm sbcalg that combines randomized online gradient descent with a kernelized exponential weights method to exploit the pseudo-1d structure effectively.
  arXiv  Detail & Related papers  (2021-02-15T08:16:51Z)
• $Q$-learning with Logarithmic Regret [60.24952657636464]
  We prove that an optimistic $Q$-learning enjoys a $mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of states, $A$ is the number of actions, $H$ is the planning horizon, $T$ is the total number of steps, and $Delta_min$ is the minimum sub-optimality gap.
  arXiv  Detail & Related papers  (2020-06-16T13:01:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.