attainable for an offline-regression-oracle-based algorithm remains unknown in the literature.

More recently, [@foster2020beyond] propose an algorithm that achieves the optimal regret for contextual bandits using an *online* regression oracle. Their algorithm, namely `SquareCB`, is built on the `A`/`BW` algorithm of [@abe1999associative] (see also the journal version @abe2003reinforcement) originally developed for linear contextual bandits — specifically, `SquareCB` replaces the “Widrow-Hofff predictor” used in the `A`/`BW` algorithm by a general online regression predictor, then follows the same probabilistic action selection strategy as the `A`/`BW` algorithm. [@foster2020beyond] show that by using this simple strategy, contextual bandits can be (surprisingly) reduced to [online regression]{} in a black-box manner. While the implication that contextual bandits are no harder than online regression is important and insightful, online regression with a general function class itself is a challenging problem. Note that an online regression oracle is *not* an offline optimization oracle, which means that algorithms for solving this oracle are not direct and have to be designed on a case-by-case basis — while there is a beautiful theory characterizing the minimax regret rate of online regression with general function classes (@rakhlin2014online), to our knowledge computational efficient algorithms are only known for specific function classes. For example, consider 