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 Õ( p T ) with high probability, and uses O(log log T ) batches, matching the lower bound on the number of batches [13] . When specialized to linear bandits, our algorithm can achieve a high probability gap-dependent regret bound of Õ(1/ min ) with the optimal log T number of batches, where min is the minimum reward gap between a suboptimal arm and the optimal. Our result is achieved via a novel soft elimination approach, that entails "shaping" the action sets at each batch so that we can efficiently identify (near) optimal actions. 37th Conference on Neural Information Processing Systems (NeurIPS 2023).