Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits

We study the optimal batch-regret tradeoff for batch linear contextual bandits. For any batch number M, number of actions K, time horizon T, and dimension d, we provide an algorithm and prove its regret guarantee, which, due to technical reasons, features a two-phase expression as the time horizon T grows. We also prove a lower bound theorem that surprisingly shows the optimality of our two-phase regret upper bound (up to logarithmic factors) in the full range of the problem parameters, therefore establishing the exact batch-regret tradeoff. Compared to the recent work citepruan2020linear which showed that M = O(log log T) batches suffice to achieve the asymptotically minimax-optimal regret without the batch constraints, our algorithm is simpler and easier for practical implementation. Furthermore, our algorithm achieves the optimal regret for all T ≥ d, while citepruan2020linear requires that T greater than an unrealistically large polynomial of d. Along our analysis, we also prove a new matrix concentration inequality with dependence on their dynamic upper bounds, which, to the best of our knowledge, is the first of its kind in literature and maybe of independent interest.