Our reduction has a byproduct; it limits the size of available actions in each round to the minimum between \(|\mathcal {A}|\)  and the size of the parameter set \(\Theta \)  (recall that we construct an action \(g(\theta )\)  for each \(\theta \in \Theta \) ). While in general a discretization of size \(T^{\Omega (d)}\)  is required to guarantee a good action in the discrete set, if the unknown parameter follows some structure, a discretization of smaller size can be sufficient. For example, for contextual linear bandits with \(s\) -sparse unknown parameter, we show that a discretization of size \(T^{O(s)}\)  is sufficient. This directly implies a high probability \(O(\sqrt{dsT\log T})\)  regret bound as opposed to the best known \(O(\sqrt{dsT}\log T)\)  bound [1]} that loses extra \(\log \)  factors due to solving a linear regression problem over the space of sparse unknown parameters.
