Oracle-Efficient Hybrid Online Learning with Unknown Distribution
Changlong Wu Jin Sima Wojciech Szpankowski
We study the problem of oracle-efficient hybrid online learning when the
features are generated by an unknown i.i.d. process and the labels are
generated adversarially. Assuming access to an (offline) ERM oracle, we show
that there exists a computationally efficient online predictor that achieves a
regret upper bounded by $\tilde{O}(T^{\frac{3}{4}})$ for a finite-VC class, and
upper bounded by $\tilde{O}(T^{\frac{p+1}{p+2}})$ for a class with $\alpha$
fat-shattering dimension $\alpha^{-p}$. This provides the first known
oracle-efficient sublinear regret bounds for hybrid online learning with an
unknown feature generation process. In particular, it confirms a conjecture of
Lazaric and Munos (JCSS 2012). We then extend our result to the scenario of
shifting distributions with $K$ changes, yielding a regret of order
$\tilde{O}(T^{\frac{4}{5}}K^{\frac{1}{5}})$. Finally, we establish a regret of
$\tilde{O}((K^{\frac{2}{3}}(\log|\mathcal{H}|)^{\frac{1}{3}}+K)\cdot
T^{\frac{4}{5}})$ for the contextual $K$-armed bandits with a finite policy set
$\mathcal{H}$, i.i.d. generated contexts from an unknown distribution, and
adversarially generated costs.