cs.LGNov 12, 2026

Near-Optimal Regret for Oracle-Efficient Adversarial Contextual Bandits

Authors: Kiarash Banihashem, MohammadTaghi Hajiaghayi

Organizations: University of Maryland, College Park

Abstract

We study contextual bandits with KK actions, a class of NN policies, and i.i.d.\ contexts from a distribution that the learner can sample. For any sequence of loss functions fixed before play, we give an oracle-efficient algorithm with expected regret O(KTlog⁡(2N) log⁡(2KT))O(\sqrt{KT\log(2N)}\,\log(2KT)) against the best policy in hindsight on the realized contexts. This improves the T2/3T^{2/3} dependence on the horizon in prior oracle-efficient bounds and achieves the optimal regret rate in this setting up to logarithmic factors. Our algorithm perturbs policy scores using a Poisson sample of auxiliary contexts. At each sampled context, the perturbation assigned to an action is a Laplace noise draw multiplied by a scale specific to that context and action. We show that choosing these scales to minimize a convex objective determined by past observations yields the stated regret bound. We further approximate the minimizing scales by projected stochastic gradient descent using only an exact offline cost-sensitive optimization oracle that returns the optimum value. Since the table of scales can be large, the algorithm represents the SGD iterates implicitly by storing the random draws that determine each update and evaluates the scales only at queried contexts. Both the oracle complexity and the remaining resource bounds are polynomial in TT, KK, and log⁡(2N)\log(2N).

Figures & tables

Explore similar work

May 7, 2026

Constrained Contextual Bandits with Adversarial Contexts

We study constrained contextual bandits with adversarial contexts, where each action yields a random reward and incurs a random cost. The conditional mean reward and cost belong to known function classes and are learned through online regression oracles. The benchmark is a stationary randomized policy whose expected cost is non-positive at every observed context. We extend the seminal SquareCB\mathsf{SquareCB} algorithm of Foster and Rakhlin (2020), which reduces the contextual bandits to a regression problem, to the constrained setting. A surrogate reward function is constructed which penalizes the positive part of the expected cost of an action distribution, and an auxiliary variable accumulates its predicted value. Then we use an exponential Lyapunov function to control both regret and cumulative constraint violation via a single inequality. If the cumulative squared prediction error is at most UTU_T, our algorithm achieves O(KTUT)O(\sqrt{KTU_T}) regret and O(KTUTlog⁡T)O(\sqrt{KTU_T}\log T) cumulative expected cost, with high probability, improving upon the previous O(T3/4)O(T^{3/4}) type bounds obtained in stochastic contextual settings with an unknown context distribution. Our results require neither additional margin conditions nor probabilistic assumptions on the context sequence.
Oct 13, 2026

Optimal Online Regret for Context-Lumpable Bandits

We study stochastic contextual bandits with an unknown context-lumpable structure. The SS contexts are partitioned into rr blocks, and every arm has the same mean reward across contexts in the same block. Under arbitrary context distributions and without separation assumptions, we design an algorithm with expected regret O~(r(S+K)T)\widetilde{O}(\sqrt{r(S+K)T}), matching the lower bound of Lee et al. (2023) up to logarithmic factors and improving their previous upper bound by a factor of rr. The algorithm operates over dyadic accuracy levels, using a baseline policy and confidence-based early stopping to control exploration. It then performs cross-context elimination: since rewards are identical within a block, one selected arm eliminates all surviving records from that block, requiring at most rr selections at each level. Multi-scale exploration assigns finer accuracies to frequent blocks and coarser accuracies to rare blocks, yielding a near-optimal arm for every block while keeping the weighted policy error small.
Feb 10, 2026

Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Bandits

We propose an algorithmic framework, Offline Estimation to Decisions (OE2D), that efficiently reduces contextual bandit learning with general reward function approximation to offline regression. The framework allows near-optimal regret for contextual bandits with large action spaces with O(log⁡T)O(\log T) calls to an offline regression oracle over TT rounds, and makes O(log⁡log⁡T)O(\log\log T) calls when TT is known. The design of OE2D algorithm generalizes Falcon~\citep{simchi2022bypassing} and its linear reward version~\citep[][Section 4]{xu2020upper} in that it finds an action distribution that we term ``exploitative F-design'' that simultaneously guarantees low regret and good coverage, striking a balance between exploration and exploitation. Central to our regret analysis is a new complexity measure, the Decision-Offline Estimation Coefficient (DOEC), which we show is small in many settings, including bounded Eluder dimension per-context and the smoothed regret setting. We also establish a relationship between DOEC and Decision Estimation Coefficient (DEC)~\citep{foster2021statistical}, bridging the design principles of offline- and online-oracle efficient contextual bandit algorithms for the first time.