In this subsection, we show that our reduction leads to the first \(O(d\sqrt{T\log T})\)  high probability upper bound for linear bandits with changing action sets. We rely on the Phased Elimination (PE) [1]} as our linear bandit algorithm \(\Lambda _\epsilon \) . PE is the same as Algorithm REF , that we will use next in the batched setting, except that \(\mathcal {X}, g\)  are fixed (recall that we apply PE within an epoch that fixes the estimate of \(g\) ). The parameter \(\gamma _m\)  in Algorithm REF  is called the confidence interval; we will specify its value in our theorems. In Algorithm REF , setting \(t^{(m)}=2^{m-1}\)  and \(\Lambda _\epsilon \)  to be PE with modified confidence intervals [1]} to account for the misspecification we get the following corollary.
