Efficient Batched Algorithm for Contextual Linear Bandits with Large Action Space via Soft Elimination

In this paper, we provide the first efficient batched algorithm for contextual linear bandits with large action spaces. Unlike existing batched algorithms that rely on action elimination, which are not implementable for large action sets, our algorithm only uses a linear optimization oracle over the action set to design the policy. The proposed algorithm achieves a regret upper bound Õ( T) with high probability, and uses O(log log T) batches, matching the lower bound on the number of batches [13].