Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits
Zihan Zhang Xiangyang Ji Yuan Zhou
We study the optimal batch-regret tradeoff for batch linear contextual bandits. For this problem, we design batch learning algorithms and prove that they achieve the optimal regret bounds (up to logarithmic factors) for any batch number $M$, number of actions $K$, time horizon $T$, and dimension $d$. Therefore, we establish the \emph{full-parameter-range} (almost) optimal batch-regret tradeoff for the batch linear contextual bandit problem. 

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.
contextual linear bandit, online batch learning
We establish near-optimal batch-regret trade-off for contextual linear bandit problem.