arXiv Machine Learning
Jun 4
Offline-to-Online Learning in Linear Bandits
arXiv:2606. 04305v1 Announce Type: new Abstract: We study online learning with an additional offline dataset in the stochastic linear bandit setting.
Gaussian-Width Bounds for Offline-to-Online Linear Bandits
The paper investigates how offline data can improve online learning in stochastic linear bandits, focusing on the case where only a subset of feature directions is poorly covered. It shows that previous regret bounds of ≥O(√{dkT}) stem from loose reward prediction error control and derives tighter bounds using concentration of Lipschitz functions of Gaussian vectors. The authors propose a phased elimination algorithm achieving regret ≥O(k√T) and establish matching lower bounds for both partial and uniform coverage, while also addressing pure exploration with offline data and providing matching bounds for simple regret.
Related stories
arXiv Machine Learning
Jun 29
Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Bandits
arXiv:2602. 09456v2 Announce Type: replace Abstract: We propose an algorithmic framework, Offline Estimation to Decisions (OE2D), that efficiently reduces contextual bandit learning with general reward function approximation to offline regression.
arXiv Machine Learning
Jun 9
Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits
arXiv:2606. 08977v1 Announce Type: new Abstract: Motivated by the recency effect in online learning, we study algorithms for single-pass *sliding-window streaming multi-armed bandits (MABs)* in this paper.
arXiv Machine Learning
Jul 7
Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions
arXiv:2607. 02891v1 Announce Type: new Abstract: Many online decision-making problems involve both round-specific feasible actions and drifting reward models: eligible ad impressions, feasible prices, and available treatments can change over time, while user preferences, demand curves, and patient responses may evolve.
arXiv Machine Learning
Jun 30
Optimal Regret for Single Index Bandits
arXiv:2605. 09454v2 Announce Type: replace-cross Abstract: We study the $\textit{single-index bandit}$ problem, where rewards depend on an unknown one-dimensional projection of high-dimensional contexts through an unknown reward function.
arXiv Machine Learning
Jul 16
On the Sublinear Regret of Continuous K-Max Bandits
arXiv:2502. 13467v2 Announce Type: replace Abstract: The $K$-Max combinatorial multi-armed bandit problem arises in applications such as recommendation and distributed decision making, where the reward is determined by the maximum outcome among $K$ selected arms.
arXiv Machine Learning
1d ago
Near-Optimal Regret Bounds for UCB-Style Gaussian Process Bandits via Data Thinning
arXiv:2610.28136v1 Announce Type: cross Abstract: Gaussian process upper confidence bound (GP-UCB) has been widely studied, though its known regret upper bound is suboptimal. To obtain near-optimal r...
arXiv Machine Learning
Jul 8
No-Regret Gaussian Process Optimization of Time-Varying Functions
arXiv:2512. 00517v3 Announce Type: replace-cross Abstract: Sequential optimization of black-box functions from noisy evaluations has been widely studied, with Gaussian Process bandit algorithms such as GP-UCB guaranteeing no-regret in stationary settings.
arXiv Machine Learning
Sep 10
High-dimensional Linear Bandits with Knapsacks
The paper studies high‑dimensional linear contextual bandits with knapsack constraints (CBwK), aiming to exploit sparsity for tighter regret bounds. It introduces an online hard‑thresholding estimator integrated into a primal‑dual framework, achieving sub‑linear regret that grows only logarithmically with the feature dimension. Under either a diverse‑covariate or margin condition, the regret improves to τ‑dependent rates, and when both hold simultaneously, a dual resolving scheme yields an even tighter bound. The approach also recovers optimal rates for high‑dimensional contextual bandits without knapsacks, and experiments demonstrate its practical effectiveness.
arXiv Machine Learning
Aug 4
A Perturbation Approach to Unconstrained Linear Bandits
arXiv:2603. 28201v3 Announce Type: replace Abstract: We revisit the standard perturbation-based approach of Abernethy et al.
arXiv Machine Learning
23h ago
The Price of Current-Effect Inference in Nonstationary Multi-Armed Bandits
The paper studies the trade‑off between maximizing rewards and accurately estimating current treatment effects in nonstationary multi‑armed bandits. For $K$‑armed bandits with H"older‑smooth mean rewards, the authors derive minimax bounds on expected dynamic regret under a high‑probability simultaneous coverage requirement for all current effects. They propose the TRACE algorithm, which achieves a regret–precision trade‑off that separates reward‑learning regret from the unavoidable cost of refreshing current‑effect estimates, and extend the method with an empirical‑Bernstein e‑process to adapt exploration while preserving worst‑case guarantees.
arXiv Machine Learning
Jul 9
Nonlinear Bandit
arXiv:2607. 07304v1 Announce Type: new Abstract: In this paper we first study the problem of generalized linear bandit (GLB) under heavy-tailed noise.