Poster
Breaking the log(1/Δ2) Barrier: Better Batched Best Arm Identification with Adaptive Grids
Tianyuan Jin · Qin Zhang · Dongruo Zhou
Hall 3 + Hall 2B #597
[
Abstract
]
Fri 25 Apr 7 p.m. PDT
— 9:30 p.m. PDT
Abstract:
We investigate the problem of batched best arm identification in multi-armed bandits, where we want to find the best arm from a set of n arms while minimizing both the number of samples and batches. We introduce an algorithm that achieves near-optimal sample complexity and features an instance-sensitive batch complexity, which breaks the log(1/Δ2) barrier. The main contribution of our algorithm is a novel sample allocation scheme that effectively balances exploration and exploitation for batch sizes. Experimental results indicate that our approach is more batch-efficient across various setups. We also extend this framework to the problem of batched best arm identification in linear bandits and achieve similar improvements.
Live content is unavailable. Log in and register to view live content