Related Work. A number of works have explored batched contextual linear bandits,
both in adversarial [1]}, [2]} and non-adversarial settings [3]}, [4]}.
The breakthrough work in [3]} achieved a nearly optimal in expectation regret upper bound \(O(d\sqrt{T\log d \log (T)}\log \log T)\)  using \(O(\log \log T)\)  batches for the stochastic contexts setting. The near-optimality follows
from the result in [6]} which shows that \(\Omega (\log \log T)\)  batches are required to achieve a \(O(\sqrt{T})\)  worst-case regret bound for multi-armed bandits with a finite number of arms (this is a special case of contextual linear bandits). If the contexts are chosen adversarially, \(\Omega (\sqrt{T})\)  batches are required to achieve a \(O(\sqrt{T})\)  regret bound [2]}.
