Best-of-Both Worlds for linear contextual bandits with paid observations

2025/10/08 by Nathan Boyer, Boyer, Nathan, Dorian Baudry +3
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Reinforcement Learning in Robotics #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2510.07424

openalex publication_date 2025/10/08 · openalex created_date 2025/10/11 · openalex updated_date 2026/07/28

Abstract

We study the problem of linear contextual bandits with paid observations, where at each round the learner selects an action in order to minimize its loss in a given context, and can then decide to pay a fixed cost to observe the loss of any arm. Building on the Follow-the-Regularized-Leader framework with efficient estimators via Matrix Geometric Resampling, we introduce a computationally efficient Best-of-Both-Worlds (BOBW) algorithm for this problem. We show that it achieves the minimax-optimal regret of Θ(T^2/3) in adversarial settings, while guaranteeing poly-logarithmic regret in (corrupted) stochastic regimes. Our approach builds on the framework from \citeBOBWhardproblems to design BOBW algorithms for ``hard problem'', using analysis techniques tailored for the setting that we consider.

Citations

• When and why randomised exploration works (in linear bandits)
• A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of Θ(T^2/3) and its Application to Best-of-Both-Worlds
• LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits
• Best-of-Both-Worlds Algorithms for Linear Contextual Bandits
• First- and Second-Order Bounds for Adversarial Linear Contextual Bandits
• Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Arms
• A Blackbox Approach to Best of Both Worlds in Bandits and Beyond
• Better Best of Both Worlds Bounds for Bandits with Switching Costs
• A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs
• Confidence-Budget Matching for Sequential Budgeted Learning
• Bandit Algorithms
• Structure Adaptive Algorithms for Stochastic Bandits
• Information Directed Sampling for Linear Partial Monitoring
• Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits
• Mostly Exploration-Free Algorithms for Contextual Bandits
• The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits
• Explore no more: Improved high-probability regret bounds for non-stochastic bandits
• From Bandits to Experts: A Tale of Domination and Independence
• An efficient algorithm for learning with semi-bandit feedback
• Thompson Sampling for Contextual Bandits with Linear Payoffs
• Decoupling Exploration and Exploitation in Multi-Armed Bandits
• From Bandits to Experts: On the Value of Side-Observations
• Contextual Bandit Algorithms with Supervised Learning Guarantees
• The Nonstochastic Multiarmed Bandit Problem

Related

• Best-of-Both-Worlds Linear Contextual Bandits
• Best-of-Both-Worlds Algorithms for Linear Contextual Bandits
• Optimal cross-learning for contextual bandits with unknown context distributions
• Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality
• A Blackbox Approach to Best of Both Worlds in Bandits and Beyond