We next provide a high level explanation on why our reduction enables tighter regret bounds for contextual linear bandits with stochastic contexts. Using the Phased Elimination algorithm (PE) [1]} with modified confidence intervals to solve the misspecified linear bandit instance, we prove a high probability bound of \(O(d\sqrt{T\log T})\)  on the regret of the contextual bandit problem using our reduction. Existing analysis techniques for changing action sets suffer \(\log \)  factors due to several reasons, such as bounding the radius of an ellipsoid that contains the unknown parameter with high probability, bounding the regret by the radius of the ellipsoid, or summing the regret over multiple episodes; in contrast, the \(\log \)  factors in our analysis appear only from a union bound used to prove concentration of the estimated arm means with high probability.
