rounds from $\tau_{m-1}+1$ to $\tau_m$ as epoch $m$. As a concrete example, consider $\tau_m=2^m$, then for any (possibly unknown) $T$, our algorithm runs in $O(\log T)$ epochs. As another example, when $T$ is known in advance, consider $\tau_m=\left\lceil T^{1-2^{-m}}\right\rceil$, then our algorithm runs in $O(\log\log T)$ epochs.

At the start of each epoch $m$, our algorithm makes two updates. First, it updates a (epoch-varying) learning rate $\gamma_m\simeq \sqrt{K\tau_{m-1}/\log(|{{\mathcal{F}}}|\tau_{m-1}/\delta)}$, which aims to strike a balance between exploration and exploitation. Second, it computes a “greedy” predictor $\widehat{f}_m$ from ${{\mathcal{F}}}$ that minimizes the empirical square loss $\sum_{t=1}^{\tau_{m-1}}(f(x_t,a_t)-r_t(a_t))^2$. This predictor can be computed via a single call to the offline regression oracle — notably, $\min_{f\in{{\mathcal{F}}}}\sum_{t=1}^{\tau_{m-1}}(f(x_t,a_t)-r_t(a_t))^2$ is almost the best way that we can imagine for our oracle to be called, with no augmented data generated, no weights maintained, and no additional optimization problem constructed.

The decision rule in epoch $m$ is then completely determined by $\gamma_m$ and $\widehat{f}_m$. For each round $t$ in epoch $m$, given a context $x_t$, the algorithm uses $\widehat{f}_m$ to predict each action’s reward and finds a greedy action $\widehat{a}_t$ that maximizes the predicted reward. Yet the algorithm does not direct select $\widehat{a}_t$ — instead, it randomizes over all actions 