Research map / Bandits and online learning / Online convex optimization and games

Near-Optimal Regret in Adversarial Kernel Bandits

NeurIPS 2026 · Bandits and online learning › Online convex optimization and games · approach: Best-of-both-worlds bandit algorithms · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes an exponential-weights algorithm with a ridge-regularized importance-weighted RKHS loss estimator plus a bias-cancelling correction term, giving regret O~(sqrt(T d*(λ) log|X|)) for adversarial kernel bandits with arbitrary bounded RKHS losses.

Problem

Adversarial kernel bandits, where per-round losses are arbitrary bounded RKHS functions and only the chosen action's scalar loss is observed; existing bounds are loose for polynomial eigendecay (e.g., Matérn) and require a rank-one adversary.

Approach

Exp2-style exponential weights with a ridge-regularized importance-weighted estimator, debiased by an explicit additive correction term B√λ||Φ(x)||_{(Σ_t+λI)^{-1}} that turns comparator-side bias into a non-positive residual, with regret controlled by effective dimension instead of ambient dimension.

Key results

• Regret O~(B sqrt(T d*(λ) log|X|)), matching the stochastic kernel bandit rate up to logs.
• Matérn(ν,d) regret O~(T^{(ν+d)/(2ν+d)}), improving prior O~(T^{(2ν+d)/(4ν)}) and removing the rank-one assumption.
• Under exponential eigendecay regret O~(sqrt T); under polynomial decay with exponent β>1, regret O~(T^{(β+1)/(2β)}).

Limitations

• Polynomial and exponential eigendecay corollaries require a decay condition that holds uniformly over all distributions on X.
• Results are in expectation only; high-probability bounds left for future work.
• Analysis restricted to finite action sets with a covering argument for continuous domains; per-round computation is cubic in |X|.

Experimental setup

Metrics: expected regret (theoretical bound)

Baselines: rank-one adversarial kernel bandit algorithm (prior work) misspecified linear bandit reduction for kernel bandits log-barrier FTRL kernel contextual bandit

Builds on: Exp2 G-optimal design maximum information gain

Closest papers by meaning

• Taming Heavy-Tailed Losses in Adversarial Bandits and the Best-of-Both-Worlds Setting (NeurIPS 2024 · similarity 0.90)
• Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback (NeurIPS 2025 · similarity 0.90)
• Sparsity-Agnostic Linear Bandits with Adaptive Adversaries (NeurIPS 2024 · similarity 0.90)
• Faster Rates for Private Adversarial Bandits (ICML 2025 · similarity 0.90)
• Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback (NeurIPS 2025 · similarity 0.89)
• Stochastic Bandits Robust to Adversarial Attacks (ICLR 2025 · similarity 0.89)