Our algorithm relies on \(\Lambda _\epsilon \) , an algorithm for linear bandits with \(\epsilon \)  misspecification. The misspecification reflects our confidence in our estimate of the function \(g\) , hence, decreases each epoch. We start with a large value of the misspecification parameter \(\epsilon _1=1\)  and a random initialization of the function \(g\)  (which we cal \(g^{(1)}\) ), and hence random initialization of \(\mathcal {X}\)  denoted \(\mathcal {X}_1\) . At time slot \(t\)  of epoch \(m\) , the algorithm asks \(\Lambda _{\epsilon _m}\)  for an action to play \(g^{(m)}(\theta _t)\in \mathcal {X}_m\)  given the history of action and rewards \(\lbrace (g^{(m)}(\theta _i),r_i)\rbrace _{i=t^{(m)}+1}^{t-1}\)  in epoch \(m\)  only. The algorithm pulls the action \(a_t=\arg \max _{a\in \mathcal {A}_t}{\langle a,\theta _t \rangle }\)  and observes \(r_t\) . The reward \(r_t\)  is then passed to the algorithm \(\Lambda _{\epsilon _m}\) . At the end of each epoch, the misspecification parameter, estimates \(g^{(m)}\) , and action set \(\mathcal {X}_m\)  are updated. The pseudo-code of our reduction is provided in Algorithm REF , and the proof in App. B. To achieve nearly optimal regret bounds, the misspecification \(\epsilon \)  need to be \(\tilde{O}(1/\sqrt{T})\)  (recall the \(\Omega (\sqrt{d}\epsilon T)\)  regret lower bound [1]}). Attempting to use \(M=2\)  to first estimate \(g\)  and then learn in the second epoch, would require the length of the first epoch to be \(\Omega (T)\) , to ensure the \(\tilde{O}(1/\sqrt{T})\)  misspecification, resulting in linear regret. Instead, as we clarify next, we use exponentially increasing epoch lengths to mix the learning with a gradual estimation of \(g\)  resulting in misspecification that is effectively \(\tilde{O}(1/\sqrt{T})\) .
