offline regression oracle here is that the algorithm’s action sequence is not i.i.d. — since offline regression oracles are designed for i.i.d. data, it is unclear how one can deal with dependent actions when she only has access to an offline regression oracle. We note that this hurdle lies at the heart of the “exploration-exploitation trade-offs” — essentially, any efficient algorithm’s actions may need to be dependent in a complicated way, as they are simultaneously used for exploration and exploitation.

Finally, we give a brief preview on how our approach gets around the above three technical hurdles. The answer is surprisingly simple: we access the offline regression oracle in a mostly “naive” way, without constructing any explicit optimization problems or confidence bounds, thus get around the first two hurdles; and we just go ahead to face the complex dynamics of evolving actions, but analyze them through a different lens (the “dual interpretation” in §\[sec:analysis\]), thus get around the third hurdle. The final algorithm is simple, but the ideas behind it are quite deep and are supported by novel analysis. The algorithmic details will be presented in §\[sec:alg\] and the key ideas will be explained in §\[sec:analysis\].

Main Results
------------

We 