Fully adaptive algorithm for pure exploration in linear bandits

2017/10/16 by Liyuan Xu, Xu, Liyuan, Junya Honda +3 · 18 citations
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Algorithm #Artificial intelligence #Computer science #Constant (computer programming) #FOS: Computer and information sciences #Machine Learning (stat.ML) #Machine Learning and Algorithms #Mathematical optimization #Mathematics #Reinforcement Learning in Robotics #Sample (material) #Sample complexity #Selection (genetic algorithm) #Task (project management) #Upper and lower bounds #stat.ML

paper · pdf · doi:10.48550/arxiv.1710.05552

published in arXiv (Cornell University) (Cornell University)

arxiv created 2017/10/16 · openalex publication_date 2017/10/16 · arxiv updated 2017/10/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We propose the first fully-adaptive algorithm for pure exploration in linear bandits---the task to find the arm with the largest expected reward, which depends on an unknown parameter linearly. While existing methods partially or entirely fix sequences of arm selections before observing rewards, our method adaptively changes the arm selection strategy based on past observations at each round. We show our sample complexity matches the achievable lower bound up to a constant factor in an extreme case. Furthermore, we evaluate the performance of the methods by simulations based on both synthetic setting and real-world data, in which our method shows vast improvement over existing methods.

Citations

• Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix

Cited by

• Inference-Time Personalized Alignment with a Few User Preference Queries
• Challenger-Based Combinatorial Bandits for Subcarrier Selection in OFDM Systems
• Price of Safety in Linear Best Arm Identification
• Sample Efficient Demonstration Selection for In-Context Learning
• Bandit Pareto Set Identification in a Multi-Output Linear Model
• Service Placement in Small Cell Networks Using Distributed Best Arm Identification in Linear Bandits
• Experimental Design for Semiparametric Bandits

Related

• Gamification of Pure Exploration for Linear Bandits
• Reward Maximization for Pure Exploration: Minimax Optimal Good Arm Identification for Nonparametric Multi-Armed Bandits
• Explicit Best Arm Identification in Linear Bandits Using No-Regret Learners
• Pure exploration in multi-armed bandits with low rank structure using oblivious sampler
• Near Instance Optimal Model Selection for Pure Exploration Linear Bandits