Fully adaptive algorithm for pure exploration in linear bandits

2017/10/16 by Liyuan Xu, Xu, Liyuan, Junya Honda +3 · 3 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (stat.ML) #Machine Learning and Algorithms #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.1710.05552

openalex publication_date 2017/10/16 · 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

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