As it is enough to make only batch updates to our estimates of the actions \(g(\theta )\) , our algorithm can be modified to provide improved regret bounds for contextual linear bandits with \(O(\log \log T)\)  batches. We use batch lengths that were introduced in [1]} which grow as \(T^{1-2^{-m}}\) . In each batch, as action set is fixed, we utilize elimination algorithms with the G-optimal design. However, at batch \(m\) , the gaps of sub-optimal actions depend on the confidence of our estimates in batch \(m-1\) , which rely on the G-optimal design using the estimates of \(g\)  from batch \(m-2\) . As a result, the regret in batch \(m\)  can be at most the ratio between the length of batch \(m\)  and batch \(m-2\) . Considering the growth rate of the batch lengths, this ratio can be large, especially in the first few batches. To fix this, we modify the batch lengths to grow in length only at the batches with odd index, while even batches use the same length as the previous batch. Our algorithm results in an \(O(d\sqrt{T\log T}\log \log T)\)  regret bound using \(O(\log \log T)\)  batches, improving a \(\sqrt{\log d}\)  factor (that appeared due to the distributional G-optimal design proposed in [2]}) in the regret bound over the best known result [2]}. Our result also provides the first high probability bound under the \(O(\log \log T)\)  batches limitation.
