---
bibliography:
- 'bibliography.bib'
---

Introduction
============

The contextual bandit problem is a fundamental framework for online decision making and interactive machine learning, with diverse applications ranging from hearthcare to electronic commerce, see a NIPS 2013 tutorial ([https://hunch.net/$\sim$jl/interact.pdf](https://hunch.net/~jl/interact.pdf)) for the theoretical background, and a recent ICML 2017 tutorial ([https://hunch.net/$\sim$rwil/](https://hunch.net/~rwil/)) for further illustrations on its practical importance.

Broadly speaking, approaches to contextual bandits can be put into two groups (see @foster2018practical): *realizability-based* approaches which rely on weak or strong assumptions on the model representation, and *agnostic* approaches which are completely model-free. While many different contextual bandit algorithms (realizability-based or agnostic) have been proposed over the past twenty years, most of them suffer from either theoretical or practical issues (see @bietti2018contextual). Existing algorithms built on upper confidence bounds (e.g., @filippi2010parametric [@abbasi2011improved; @chu2011contextual; @li2017provably]) and Thompson sampling (e.g., @agrawal2013thompson [@russo2018tutorial]) rely on strong assumptions on the model representation and are only tractable for specific parametrized families of models like generalized linear models. Meanwhile, algorithms that make no assumption on the model representation (e.g., @dudik2011efficient [@agarwal2014taming]) may lead to overly conservative exploration in practice (@bietti2018contextual), and their reliance on an *offline cost-sensitive classification oracle* as a subroutine typically causes implementation difficulties as the oracle itself is computationally intractable in general. At this moment, designing a provably optimal contextual bandit algorithm that is applicable for large-scale real-world deployments is still widely deemed a very challenging task (see @agarwal2016making [@foster2020beyond]).

Recently, [@foster2018practical] propose an approach to solve contextual bandits with general model representations (i.e., general function classes) using an *offline regression oracle* — an oracle that can typically be implemented efficiently and has wide availability for numerous function classes due to its core role in modern machine learning. In particular, the (weighted) least-squares regression oracle assumed in the algorithm of [@foster2018practical] is highly practical as it has a strongly convex loss function and is amenable to gradient-based methods. As [@foster2018practical] point out, designing offline-regression-oracle-based algorithms is a promising direction for making contextual bandits practical, as they seem to combine the advantages of both realizability-based and agnostic algorithms: they are general and flexible enough to work with any given function class, while using a more realistic and reasonable oracle than the computationally-expensive classification oracle. Indeed, according to multiple experiments and extensive empirical evaluations conducted by [@bietti2018contextual] and [@foster2018practical], the algorithm of [@foster2018practical] “works the best overall” compared with almost all existing approaches.

Despite its empirical success, the algorithm of [@foster2018practical] is, however, theoretically sub-optimal — it could incur $\widetilde{\Omega}(T)$ regret in the worst case. Whether the optimal regret of contextual bandits can be attained via an offline-regression-oracle-based algorithm is listed as an open problem in [@foster2018practical]. In fact, this problem has been open to the bandit community since 2012 — it dates back to [@agarwal2012contextual], where the authors propose a computationally *inefficient* contextual bandit algorithm that achieves the optimal $O(\sqrt{KT\log|{{\mathcal{F}}}|})$ regret for a general *finite* function class ${{\mathcal{F}}}$, but leave designing computationally tractable algorithms as an open problem.

More recently, [@foster2020beyond] propose an algorithm that achieves the optimal regret for contextual bandits using an *online regression oracle* (which is not an offline optimization oracle and has to work with an adaptive adversary). Their finding that contextual bandits can be completely reduced to online regression is novel and important, and their result is also very general: it requires only the minimal realizability assumption, works with possibly nonparametric function classes, and holds true even when the contexts are chosen adversarially. However, the online regression oracle that they appeal to is still much stronger than an offline regression oracle, and to our knowledge computationally efficient algorithms for online regression are only known for specific function classes. Whether the optimal regret of contextual bandits can be attained via a reduction to an offline regression oracle is listed as an open problem again in [@foster2020beyond].

In this paper, we give an affirmative answer to the above open problem repeatedly mentioned in the literature (@agarwal2012contextual [@foster2018practical; @foster2020beyond]). Specifically, we provide the first optimal black-box reduction from contextual bandits to offline regression, with only the minimal realizability assumption. The significance of this result is that it reduces contextual bandits, a prominent online decision-making problem, to offline regression, a very basic and common offline optimization task that serves as the building block of modern machine learning. A direct consequence of this result is that any advances in solving offline regression problems immediately translate to contextual bandits, statistically and computationally. Note that such online-to-offline reduction is highly nontrivial (and impossible without specialized structures) for online learning problems in general (@hazan2016computational).

Our reduction is accomplished by a surprisingly fast and simple algorithm that achieves the optimal ${O}(\sqrt{KT\log(|{{\mathcal{F}}}|T)})$ regret for general finite function class ${{\mathcal{F}}}$ with only $O(\log T)$ calls to an offline least-squares regression oracle over $T$ rounds. The number of oracle calls can be further reduced to $O(\log\log T)$ if $T$ is known. Notably, this can be understood as a “triply exponential” speedup over previous work: (1) compared with the previously known regret-optimal algorithm [@agarwal2012contextual] for this setting, which requires enumerating over ${{\mathcal{F}}}$ at each round, our algorithm accesses the function class only through an offline regression oracle, thus typically avoids an exponential cost at each round; (2) compared with the sub-optimal algorithm of [@foster2018practical] which requires $\widetilde{O}(\sqrt{T})$ calls for non-convex ${{\mathcal{F}}}$, and the classification-oracle-based algorithm of [@agarwal2014taming] which requires $\widetilde{O}(\sqrt{KT/\log|{{\mathcal{F}}}|})$ calls to a computationally expensive classification oracle, our algorithm requires only $O(\log T)$ calls to a simple regression oracle, which implies an exponential speedup over all existing provably optimal oracle-efficient algorithms, even when we ignore the difference between regression and classification oracles; (3) when the number of rounds $T$ is known in advance, our algorithm can further reduce the number of oracle calls to $O(\log\log T)$, which is an exponential speedup by itself. Our algorithm is thus highly computational efficient.

The statistical analysis of our algorithm is also quite interesting. Unlike existing analysis of other realizability-based algorithms in the literature, we do not directly analyze the decision outcomes of our algorithm — instead, we find a dual interpretation of our algorithm as sequentially maintaining a *dense* distribution over *all* (possibly *improper*) policies, where a policy is defined as a deterministic decision function mapping contexts to actions. We analyze how the realizability assumption enables us to establish uniform-convergence-type results for some *implicit* quantities in the universal policy space, regardless of the huge capacity of the universal policy space. Note that while the dual interpretation itself is not easy to compute in the universal policy space, it is only applied for the purpose of analysis and has nothing to do with our original algorithm’s implementation. Through this lens, we find that our algorithm’s dual interpretation satisfies a series of sufficient conditions for optimal contextual bandit learning. Our identified sufficient conditions for optimal contextual bandit learning in the universal policy space are built on the previous work of [@dudik2011efficient], [@agarwal2012contextual] and [@agarwal2014taming] — the first one is colloquially referred to as the “monster paper” by its authors due to its complexity ([link](https://hunch.net/~jl/projects/interactive/index.html)), and the third one is titled as “taming the monster” by its authors due to its improved computational efficiency. Since our algorithm achieve all the conditions required for regret optimality in the universal policy space in a completely *implicit* way (which means that all the requirements are automatically satisfied without explicit computation), our algorithm comes with significantly reduced computational cost compared with previous work (thanks to the realizability assumption), and we thus title our paper as “bypassing the monster”.

Finally, we extend all the above results to the case of general infinite function class ${{\mathcal{F}}}$. For this case, we state our results in a more general way: for any function class ${{\mathcal{F}}}$, given an arbitrary offline regression oracle with an arbitrary offline *estimation error* (or *excess risk*) guarantee, we propose a fast and simple contextual bandit algorithm whose regret can be bounded by a function of the offline estimation error, through only $O(\log T)$ calls (or $O(\log\log T)$ calls if $T$ is known) to the offline regression oracle. We show that our algorithm is statistically optimal as long as the offline regression oracle is statistically optimal. Notably, the above results provide a universal and optimal “converter” from results of offline/batch learning with general function classes to results of contextual bandits with general function classes. This leads to improved algorithms with tighter regret bounds for many existing contextual bandit problems, as well as practical algorithms for many new contextual bandit problems.

Overall, our algorithm is fast and simple, and our analysis is quite general. We believe that our algorithm has the potential to be implemented on a large scale, and our approach may contribute to deeper understanding of contextual bandits. We will go over the details in the rest of this article.

Learning Setting {#sec:setting}
----------------

The stochastic contextual bandit problem can be stated as follows. Let ${{\mathcal{A}}}$ be a finite set of $K$ actions and ${{\mathcal{X}}}$ be an arbitrary space of contexts (e.g., a feature space). The interaction between the learner and nature happens over $T$ rounds, where $T$ is possibly unknown. At each round $t$, nature sample a context $x_t\in{{\mathcal{X}}}$ and a (context-dependent) reward vector $r_t\in[0,1]^{{{\mathcal{A}}}}$ i.i.d. according to a fixed but unknown distribution ${{\mathcal{D}}}$, with component $r_t(a)$ denoting the reward for action $a\in{{\mathcal{A}}}$; the learner observes $x_t$, picks an action $a_t\in{{\mathcal{A}}}$, and observes the reward for her action $r_t(a_t)$. Depending on whether there is an assumption about nature’s reward model, prior literature studies the contextual bandit problem in two different but closely related settings.

**Agnostic setting.** Let $\Pi\subset{{\mathcal{A}}}^{{{\mathcal{X}}}}$ be a class of *policies* (i.e., decision functions) that map contexts $x\in{{\mathcal{X}}}$ to actions $a\in{{\mathcal{A}}}$, and $\pi_*:=\argmax_{\pi\in\Pi}{{\mathbb{E}}}_{(x,r)\in{{\mathcal{D}}}}[r(\pi(x))]$ be the optimal policy in $\Pi$ that maximizes the expected reward. The learner’s goal is to compete with the (in-class) optimal policy $\pi_*$ and minimizes her (empirical cumulative) *regret* after $T$ rounds, which is defined as $$\sum_{t=1}^T(r_t(\pi_*(x_t))-r_t(a_t)).$$ The above setting is called *agnostic* in the sense that it imposes no assumption on nature.

**Realizable setting.** Let ${{\mathcal{F}}}$ be a class of *predictors* (i.e., reward functions), where each predictor is a function $f:{{\mathcal{X}}}\times{{\mathcal{A}}}\rightarrow[0,1]$ describing a potential reward model ${{\mathbb{E}}}[r(a)|x,a]=f(x,a)$. The standard realizability assumption is as follows:

There exists a predictor $f^*\in{{\mathcal{F}}}$ such that $${{\mathbb{E}}}[r(a)|x,a]=f^*(x,a),~~~\forall x\in{{\mathcal{X}}}, a\in{{\mathcal{A}}}.$$

Given a predictor $f\in{{\mathcal{F}}}$, the associated reward-maximizing policy $\pi_{f}$ always picks the action with the highest predicted reward, i.e., $\pi_{f}(x)=\arg\max_{a\in{{\mathcal{A}}}}f(x,a)$. The learner’s goal is to compete with the “ground truth” optimal policy $\pi_{f^*}$ and minimizes her (empirical cumulative) *regret* after $T$ rounds, which is defined as $$\sum_{t=1}^T(r_t(\pi_{f^*}(x_t))-r_t(a_t)).$$ The above setting is called *realizable* in the sense that it assumes that nature can be well-specified by a predictor in ${{\mathcal{F}}}$.

We make some remarks on the above two settings from a pure modeling perspective. First, the agnostic setting does not require realizability and is more general than the realizable setting. Indeed, given any function class ${{\mathcal{F}}}$, one can construct an *induced* policy class $\Pi_{{{\mathcal{F}}}}:=\{\pi_f|f\in{{\mathcal{F}}}\}$, thus any realizable contextual bandit problem can be reduced to an agnostic contextual bandit problem. Second, the realizable setting has its own merit, as the additional realizability assumption enables stronger performance guarantees: once the realizability assumption holds, the learner’s competing policy $\pi_{f^*}$ is guaranteed to be the “ground truth” (i.e., no policy can be better than $\pi_{f^*}$), thus small regret necessarily means large total reward. By contrast, in the no-realizability agnostic setting, the “optimal policy in $\Pi$” is not necessarily an effective policy if there are significantly more effective polices outside of $\Pi$. More comparisons between the two settings regarding theoretical tractability, computational efficiency and practical implementability will be provided in §\[sec:lit\].

Related Work {#sec:lit}
------------

Contextual bandits have been extensively studied for nearly twenty years, see Chapter 5 of [@lattimore2018bandit] and Chapter 8 of [@slivkins2019introduction] for detailed surveys. Here we mention some important and closely related work.

### Agnostic Approaches

Papers studying contextual bandits in the agnostic setting aim to design general-purpose and computationally-tractable algorithms that are provably efficient for any given policy class $\Pi$ while avoiding the computational complexity of enumerating over $\Pi$ (as the size of $\Pi$ is usually extremely large). The primary focus of prior literature is on the case of general finite $\Pi$, as this is the starting point for further studies of infinite (parametric or nonparametric) $\Pi$. For this case, the EXP4-family algorithms (@auer2002nonstochastic [@mcmahan2009tighter; @beygelzimer2011contextual]) achieve the optimal $O(\sqrt{KT\log|\Pi|})$ regret but requires $\Omega(|\Pi|)$ running time at each round, which makes the algorithms intractable for large $\Pi$. In order to circumvent the $\Omega(|\Pi|)$ running time barrier, researchers (e.g., @langford2008epoch [@dudik2011efficient; @agarwal2014taming]) restrict their attention to *oracle-based* algorithms that access the policy space only through an *offline optimization oracle* — specifically, an offline cost-sensitive classification oracle that solves $$\label{eq:csc}
\arg\max_{\pi\in\Pi}\sum_{s=1}^t \tilde{r}_{s}(\pi(x_s))$$ for any given sequence of context and reward vectors $(x_1,\tilde{r}_1),\cdots,(x_t,\tilde{r}_t)\in{{\mathcal{X}}}\times\mathbb{R}_{+}^{{{\mathcal{A}}}}$. An *oracle-efficient* algorithm refers to an algorithm whose number of oracle calls is polynomial in $T$ over $T$ rounds.

The first provably optimal oracle-efficient algorithm is the `Randomized UCB` algorithm of [@dudik2011efficient], which achieves the optimal regret with $\widetilde{O}(T^6)$ calls to the cost-sensitive classification oracle. A breakthrough is achieved by the `ILOVETOCONBANDITS` algorithm in the celebrated work of [@agarwal2014taming], where the number of oracle calls is significantly reduced to $\widetilde{O}(\sqrt{KT/\log|\Pi|})$. The above results are fascinating in theory because they enable a “online-to-offline reduction” from contextual bandits to cost-sensitive classification, which is highly non-trivial for online learning problems in general (@hazan2016computational). However, the practibility of the above algorithms is heavily restricted due to their reliance on the cost-sensitive classification oracle (\[eq:csc\]), as this task is computationally intractable even for simple policy classes (@klivans2009cryptographic) and typically involves solving NP-hard problems. As a result, the practical implementations of the above classification-oracle-based algorithms typically resort to heuristics (@agarwal2014taming [@foster2018practical; @bietti2018contextual]). Moreover, the above algorithms are memory hungry: since they must feed *augmented* versions of the dataset (rather than the original version of the dataset) into the oracle, they have to repeatedly create auxiliary data and store them in memory. We refer to [@foster2018practical] and [@foster2020beyond] for more detailed descriptions on the drawbacks of these approaches in terms of computational efficiency and practical implementability.

### Realizibility-based Approaches

In contrast to the agnostic setting where research primarily focuses on designing general-purpose algorithms that work for any given $\Pi$, a majority of research in the realizable setting tends to design specialized algorithms that work well for a particular parametrized family of ${{\mathcal{F}}}$. Two of the dominant strategies for the realizable setting are upper confidence bounds (e.g., @filippi2010parametric [@abbasi2011improved; @chu2011contextual; @li2017provably; @li2019nearly]) and Thompson sampling (e.g., @agrawal2013thompson [@russo2018tutorial]). While these approaches have received practical success in several scenarios (@li2010contextual), their theoretical guarantee and computational tractability critically rely on their strong assumptions on ${{\mathcal{F}}}$, which restrict their usage in other scenarios (@bietti2018contextual).

To our knowledge, [@agarwal2012contextual] is the first paper studying contextual bandits with a general finite ${{\mathcal{F}}}$, under the minimal realizability assumption. They propose a eliminaton-based algorithm, namely `Regressor Elimination`, that achieves the optimal $\widetilde{O}(\sqrt{KT\log|{{\mathcal{F}}}|})$ regret. However, their algorithm is computational inefficient, as it enumerates over the whole function class and requires $\Omega(|{{\mathcal{F}}}|)$ computational cost at each round (note that the size of ${{\mathcal{F}}}$ is typically extremely large). The computational issues of [@agarwal2012contextual] are resolved by [@foster2018practical], who propose an oracle-efficient contextual bandit algorithm `RegCB`, which always accesses the function class through a weighted least-squares regression oracle that solves $$\label{eq:wlsr}
\arg\min_{f\in{{\mathcal{F}}}}\sum_{s=1}^t w_s(f(x_s,a_s)-y_s)^2$$ for any given input sequence $(w_1,x_1,a_1,y_1),\cdots,(w_t,x_t,a_t,y_t)\in\mathbb{R}_{+}\times{{\mathcal{X}}}\times{{\mathcal{A}}}\times[0,1]$. As [@foster2018practical] mention, the above oracle can often be solved efficiently and is very common in machine learning practice, far more reasonable than the cost-sensitive classification oracle (\[eq:csc\]). However, unlike `Regressor Elimination`, the `RegCB` algorithm is not minimax optimal — its worst-case regret could be as large as $\widetilde{\Omega}(T)$. Whether the optimal $\widetilde{O}(\sqrt{KT\log|{{\mathcal{F}}}|})$ regret is 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 the case of general finite ${{\mathcal{F}}}$, the online algorithm given by [@rakhlin2014online] actually requires $\Omega(|{{\mathcal{F}}}|)$ computational cost at each round. As a result, in parallel with the excellent work of [@foster2020beyond], a more thorough “online-to-offline reduction” from contextual bandits to offline regression is highly desirable.

### Empirical Evaluation and Summary

Recently, [@bietti2018contextual] and [@foster2018practical] conduct some extensive empirical evaluations on different approaches to contextual bandits. The experimental results show that offline-regression-oracle-based algorithms like `RegCB` typically outperforms other algorithms (including classification-oracle-based algorithms like `ILOVETOCONBANDITS`) across multiple datasets, statistically and computationally. Given the empirical success of `RegCB`, a huge gap between the theory and practice of contextual bandits is that, however, a provable optimal offline-regression-oracle-based algorithm is still unknown. This is the major motivation of our study, and we hope that our work can contribute to closing this gap.

Research Question {#sec:rq}
-----------------

In this paper, we study the following open question which is repeatedly mentioned in the contextual bandit literature (@agarwal2012contextual [@foster2018practical; @foster2020beyond]): *Is there an offline-regression-oracle-based algorithm that achieves the optimal regret for contextual bandits?*

Similar to [@dudik2011doubly; @agarwal2012contextual; @agarwal2014taming], we mainly focus on the case of general finite ${{\mathcal{F}}}$, as this is the starting point for further studies of infinite ${{\mathcal{F}}}$ (we will extend our results to general infinite ${{\mathcal{F}}}$ in §\[sec:extension\]). For this case, the gold standard is an algorithm that achieves $\widetilde{O}(\sqrt{KT\log|{{\mathcal{F}}}|})$ regret with the total number of oracle calls being polynomial/sublinear in $T$ (see @agarwal2012contextual [@foster2018practical]). As for the optimization oracle, we assume access to the following (unweighted) least-sqaures regression oracle that solves $$\label{eq:lsr}
\arg\min_{f\in{{\mathcal{F}}}}\sum_{s=1}^t (f(x_s,a_s)-y_s)^2$$ for any input sequence $(x_1,a_1,y_1),\cdots,(x_t,a_t,y_t)\in{{\mathcal{X}}}\times{{\mathcal{A}}}\times[0,1]$. Without loss of generality[^1], we assume that the oracle (\[eq:lsr\]) always return a same solution for two input sequences that are completely the same. Note that the above least-squares regression oracle that we assume is even simpler than the weighted one (\[eq:wlsr\]) assumed in [@foster2018practical], as it does not need to consider the weights.

Key Challenges
--------------

Before we proceed to present our results, we would like to illustrate the key technical hurdles of using offline regression oracles to achieve the optimal regret for contextual bandits. We will then provide a few comments explaining how our approach gets around these technical hurdles.

As was pointed out before, three excellent papers [@agarwal2012contextual; @foster2018practical; @foster2020beyond] have made important progress towards solving contextual bandits via regression approaches. Understanding the gap between the existing results and our desired result is important for understanding the key technical hurdles. Below we discuss three challenges. **Computational hurdle.** [@agarwal2012contextual] propose a provably optimal but computational algorithm for contextual bandits with a general finite ${{\mathcal{F}}}$. At each round $t$, their algorithm maintains a subset ${{\mathcal{F}}}_t\subset{{\mathcal{F}}}$ based on successive elimination and solves a complicated optimization problem over ${{\mathcal{F}}}_t$. Here, the key difficulty of using an offline regression oracle like (\[eq:lsr\]) is that one cannot reformulate the complicated optimization problem over ${{\mathcal{F}}}_t$ in the form of (\[eq:lsr\]), as its objective function is far more complicated than a sum of squares. This is essentially why using an offline regression oracle (\[eq:lsr\]) is more challenging than using an offline cost-sensitive classification oracle (\[eq:csc\]): reformulating an optimization problem as (\[eq:lsr\]) is much harder than reformulating an optimization problem as (\[eq:csc\]).

**Statistical hurdle associated with constructing confidence bounds.** [@foster2018practical] propose a computationally efficient confidence-bounds-based algorithm using an offline regression oracle. However, their algorithm only has statistical guarantees under some strong distributional assumptions. An important reason is that confidence-bounds-based algorithms typically rely on accurate confidence intervals constructed for *each context*. While this is possible for a simple ${{\mathcal{F}}}$ like a linear class, it is impossible for a general ${{\mathcal{F}}}$. Here, the difficulty originates from the fact that all the statistical learning guarantees for offline regression with a general ${{\mathcal{F}}}$ require one to take an expectation over contexts. In other words, context-dependent statistical guarantees are generally impossible for an offline regression oracle.

**Statistical hurdle associated with analyzing dependent actions.** [@foster2020beyond] propose an optimal and efficient contextual bandit algorithm assuming access to an online regression oracle, which is quite different from an offline regression oracle. Statistically, the difference between offline and online regression oracles is that, offline regression oracles only assume statistical guarantees for an i.i.d. data sequence (see §\[sec:extension\] for our definition of a general offline regression oracle), while online regression oracles assume statistical guarantees for an arbitrary data sequence possibly generated by an adaptive adversary. Evidently, access to an online regression oracle is a stronger assumption than access to an offline regression oracle. As [@foster2020beyond] mention, their algorithm requires an online regression oracle because “the analysis critically uses that the regret bound (of the online regression oracle) holds when the actions $a_1,\dots,a_T$ are chosen adaptively, since actions selected in early rounds are used by `SquareCB` to determine the action distribution at later rounds”. That is, the technical hurdle of using an 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 give an affirmative answer to the open question in §\[sec:rq\], by providing the first optimal black-box reduction from contextual bandits to offline regression, with only the minimal realizability assumption. As we mention before, a direct consequence of this result is that (stochastic) contextual bandits become no harder than offline regression: any advances in solving offline regression problems immediately translate to contextual bandits, statistically and computationally.

Moreover (and quite surprisingly), we go far beyond the conventional “polynomial/sublinear oracle calls” criteria of computational efficiency: we propose an algorithm achieving the optimal regret using only $O(\log T)$ calls to the regression oracle, and the number of oracle calls can be further reduced to $O(\log\log T)$ if $T$ is known. As we mention before, this can be understood as a “triply exponential” speedup over existing algorithms. Overall, our algorithm is fast, simple, memory-efficient, and has the potential to be implemented on a large scale. We compare our algorithm’s properties with existing (general-purpose) contextual bandit algorithms[^2] in Table \[tab\].

  -------------------------- ------------------------ --------------------------------------------------------------
  Algorithm                  Statistical optimality   Computational complexity
  `Regressor Elimination`    **optimal**              $\Omega(|{{\mathcal{F}}}|)$
  (@agarwal2012contextual)                            [intractable]{}
  `ILOVETOCONBANDITS`        **optimal**              $\widetilde{O}(\sqrt{KT/\log|{{\mathcal{F}}}|})$ calls to an
  (@agarwal2014taming)                                offline [classification]{} oracle
  `RegCB`                    [suboptimal]{}           $O(\sqrt{T})$ calls to an
  (@foster2018practical)                              **offline regression** oracle
  `SquareCB`                 **optimal**              $O(T)$ calls to an
  (@foster2020beyond)                                 [online]{} regression oracle
  `FALCON`                   **optimal**              $\bm{O(\log T)}$ or $\bm{O(\log{} \log T)}$ calls to an
  (this paper)                                        **offline regression** oracle
  -------------------------- ------------------------ --------------------------------------------------------------

  : Algorithms’ performance with general finite ${{\mathcal{F}}}$. Advantages are marked in bold.[]{data-label="tab"}

Our approach is closely related to (and reveals connections between) three lines of research in contextual bandits over twenty years: (1) a celebrated theory of optimal contextual bandit learning in the agnostic setting using a (seemingly unavoidable) classification oracle, represented by [@dudik2011efficient] (the “monster paper”) and [@agarwal2014taming] (“taming the monster”); (2) a simple probabilistic selection strategy mapping the predicted rewards of actions to the probabilities of actions, pioneered by [@abe1999associative] (see also @abe2003reinforcement) and followed up by [@foster2020beyond]; and (3) some technical preliminaries developed in an early work of [@agarwal2012contextual]. In particular, we rethink the philosophy behind [@dudik2011efficient] and [@agarwal2014taming], reform it with our own understanding of the value of realizability, and come up with a new idea of “bypassing” the classification oracle under realizability — our algorithm is essentially a direct consequence of this new idea, see the derivation of our algorithm in §\[sec:born\]. Interestingly, our derived algorithm turns out to use a different but similar probabilistic selection strategy like [@abe1999associative] and [@foster2020beyond] — this is kind of surprising, as the idea behind the derivation of our algorithm is very different from the ideas behind [@abe1999associative] and [@foster2020beyond]. This suggests that such simple probabilistic selection strategies might be more intriguing and more essential for bandits than people previously think, and we believe that they worth further attention from the bandit community. We hope that our work, together with [@abe1999associative] and [@foster2020beyond], can provide diverse perspectives on how to understand such strategies.

As a final remark, we emphasize that compared with each line of research that we mention above, our approach has new contributions beyond them which seem necessary for our arguments to hold. We will elaborate on such new contributions in §\[sec:alg\] and §\[sec:analysis\].

Organization and Notations
--------------------------

The rest of the paper is organized as follows. We begin our study focusing on the case of finite function classes in §\[sec:alg\] and §\[sec:analysis\]. In §\[sec:alg\], we introduce our algorithm and state its properties as well as theoretical guarantees. In §\[sec:analysis\], we present our statistical analysis and explain the idea behind our algorithm. In §\[sec:extension\], we extend our results to the case of infinite function classes. We conclude our paper in §\[sec:conclusion\]. All the proofs of our results are deferred to the appendix.

Throughout the paper, we use $O(\cdot)$ to hide constant factors, and $\widetilde{O}(\cdot)$ to hide logarithmic factors. Given ${{\mathcal{D}}}$, Let ${{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}$ denote the marginal distribution over ${{\mathcal{X}}}$. We use $\sigma(Y)$ to denote the $\sigma$-algebra generated by a random variable $Y$, and use ${\mathcal{B}}(E)$ to denote the power set of a discrete set $E$. We use ${\mathbb{N}}$ to denote the set of all positive integers, and $\mathbb{R}_{+}$ to denote the set of all non-negative real numbers. Without loss of generality, we assume that $|{{\mathcal{F}}}|\ge4$.

The Algorithm {#sec:alg}
=============

We present our algorithm, “FAst Least-squares-regression-oracle CONtextual bandits” (`FALCON`), in Algorithm \[alg:cbor\]. Note that this algorithm is specialized for the case of general finite ${{\mathcal{F}}}$. In §\[sec:extension\], we will propose a more general algorithm that works for general infinite ${{\mathcal{F}}}$, which is derived from the same idea but has some slight differences due to technical reasons.

[**input** epoch schedule $0=\tau_0<\tau_1<\tau_2<\cdots$, confidence parameter $\delta$.]{}

. . Define $$p_t(a)=\begin{cases}
        \frac{1}{K+\gamma_m\left(\widehat{f}_m(x_t,\widehat{a}_t)-\widehat{f}_m(x_t,a)\right)},&\text{for all }a\ne \widehat{a}_t,\\
        1-\sum_{a\ne\widehat{a}_t}p_t(a),&\text{for }a=\widehat{a}_t.
        \end{cases}$$

Our algorithm runs in an epoch schedule to reduce oracle calls, i.e., it only calls the oracle on certain pre-specified rounds $\tau_1,\tau_2,\tau_3,\dots$. For $m\in{\mathbb{N}}$, we refer to the 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 according to a probabilistic selection strategy that picks each action other than $\widehat{a}_t$ with probability roughly inversely proportional to how much worse it is predicted to be as compared with $\widehat{a}_t$, as well as roughly inversely proportional to the learning rate $\gamma_m$. The effects of this strategy are twofold. First, *at each round*, by assigning the greedy action the highest probability and each non-greedy action a probability roughly inverse to the predicted reward gap, we ensure that the better an action is predicted to be, the more likely it will be selected. Second, *across different epochs*, by controlling the probabilites of non-greedy actions roughly inverse to the gradually increasing learning rate $\gamma_m$, we ensure that the algorithm “explores more” in the beginning rounds where the learning rate is small, and gradually “exploits more” in later rounds where the learning rate becomes larger — this is why we view our learning rate a sequential balancer between exploration and exploitation.

Algorithmic Components and Comparisons with Literature
------------------------------------------------------

`FALCON` is a very simple algorithm, and can be viewed a novel combination of three algorithmic components: (i) an epoch schedule, (ii) the greedy use of an offline least-squares regression oracle, and (iii) a probabilistic selection strategy that maps reward predictions to action probabilities, controlled by an epoch-varying learning rate. While each component alone is not entirely new in the literature (see, e.g., @cesa2014regret [@agarwal2014taming; @foster2018practical] for the use of epoch schedules, @langford2008epoch [@bastani2017mostly] for similar ideas of making greedy predictions, and @abe1999associative [@foster2020beyond] for similar probabilisitc selection strategies), the combination of the above three components has not been considered in the literature before, and it is far from obvious that this particular combination should be effective. In fact, it is quite surprising that such a simple algorithm would work well for general contextual bandits. While there is definitely more to this algorithm than meets the eye (we will explain the essential idea behind `FALCON` in §\[sec:bypass\] and §\[sec:born\]), let us first give a few quick comments on component (ii) and (iii), and compare them to existing literature.

We start from component (iii). As we mention before, the idea of mapping the predicted action rewards to action probabilities via an “inverse proportional to the gap” rule is not new: a similar probabilistic selection strategy is firstly proposed by [@abe1999associative] in their study of linear contextual bandits, and recently adopted by [@foster2020beyond] in their reduction from contextual bandits to *online* regression. Compared with the existing strategies used in [@abe1999associative] and [@foster2020beyond], the strategy that we use here has an important difference: while the above two papers adopt a constant learning rate $\gamma$ that does not change in the running process of their algorithms (specifically, @abe1999associative set $\gamma\simeq \sqrt{K}T^{1/4}$ and @foster2020beyond set $\gamma\simeq\sqrt{KT/\log(|{{\mathcal{F}}}|/\delta}$), we appeal to an epoch-varying (or time-varying) learning rate $\gamma_m\simeq\sqrt{K\tau_{m-1}/\log(|{{\mathcal{F}}}|\tau_{m-1}/\delta)}$ that gradually increases as our algorithm proceeds. This epoch-varying learning rate plays a important role in our statistical analysis, as the proof of our regret guarantee relies on an inductive argument which requires the learning rate to change carefully with respect to epochs and gradually increase over time, see §\[sec:ocbl\].

**Remark.** [While such an epoch-varying learning rate is not necessary when $T$ is known in advance and the oracle calls are “frequent” enough, an epoch-varying learning rate brings certain benefits to the algorithm: first, in the case of unknown $T$, it is required; second, in the case of known $T$, it is necessary whenever one seeks to control the total number of oracle calls within $o(\log T)$ (a fixed learning rate could lead to sub-optimal regret in this setting); third, in our analysis it always leads to tighter regret bounds with a better dependency on logarithmic factors. As a result, it seems that an epoch-varying learning rate always dominates a fixed learning rate in our problem.]{}

Component (ii) of our algorithm is particularly interesting. Indeed, our algorithm makes predictions in a surprisingly simple and straightforward way: it always picks the greedy predictor and directly applies it on contexts without any modification — that is, in terms of making predictions, the algorithm is fully greedy. This seems to contradict the conventional idea that greedy-prediction-based algorithms are typically sub-optimal (e.g., @langford2008epoch), and is in sharp contrast to previous elimination-based algorithms (e.g., @dudik2011doubly [@agarwal2012contextual]) and confidence-bounds-based algorithms (e.g., @abbasi2011improved [@chu2011contextual]) ubiquitous in the bandit literature, which spend a lot of efforts and computation resources maintaining complex confidence intervals, version spaces, or distributions over predictors. Even when one compares our algorithm’s prediction strategy with [@abe1999associative] and [@foster2020beyond] which share some common features on how to select actions after predictions are made, one can find that neither of them trust greedy predictors: [@abe1999associative] appeal to the “Widrow-Hofff predictor” (equivalent to an online gradient descent oracle) and [@foster2020beyond] appeal to a general online regression oracle. Both of their analysis critically relies on the *online* nature of their oracles, i.e., the oracles can efficiently minimize regret against an adaptive adversary — essentially, this means that a majority of the heavy lifting regarding exploration-exploitation trade-offs are taken care by the online oracles, not the algorithms. Seemingly counter-intuitive, we claim that making “naive” greedy predictions is sufficient for optimal contextual bandit learning, which means that our oracle does not care about exploration-exploitation trade-offs at all. This surprising finding suggests that a rigorous analysis of our algorithm should contain some new ideas beyond existing bandit literature. Indeed, we will provide a quite interesting analysis of our algorithm in §\[sec:analysis\], which seem to be conceptually novel.

**Remark.** Readers who are interested in the difference between an offline oracle and an online oracle may compare the regret analysis approach in this paper with the approaches in [@abe1999associative] and [@foster2020beyond]. The analysis of [@abe1999associative] and [@foster2020beyond] is essentially per-round analysis: at each round, the instantaneous bandit regret is upper bounded by the instantaneous online regression regret, with no structure shared across different rounds, so the final regret bound follows from taking a sum over all rounds. By contrast, our analysis has to deal with the shared structure across different rounds, i.e., we have to figure out how the exploration happened in early rounds benefits the exploitation in later rounds.

Statistical Optimality
----------------------

\[thm:finite\] Consider an epoch schedule such that $\gamma_{m}\le2\gamma_{m-1}$ for $m>1$ and $\gamma_1=O(1)$. For any $T\in{\mathbb{N}}$, with probability at least $1-\delta$, the regret of the `FALCON` algorithm after $T$ rounds is at most $$O\left(\sqrt{KT\log(|{{\mathcal{F}}}|T/\delta)}\right).$$

The proof is deferred to Appendix \[app:thm1\]. This upper bound matches the lower bound in [@agarwal2012contextual] up to logarithmic factors. The `FALCON` algorithm is thus statistically optimal. We will discuss more about the regret analysis of `FALCON` in §\[sec:analysis\].

Computational Efficiency
------------------------

Consider the epoch schedule $\tau_m=2^m$, $\forall m\in{\mathbb{N}}$. For any possibly unknown $T$, our algorithm runs in $O(\log T)$ epochs, and in each epoch our algorithm only calls the oracle for once. Therefore, our algorithm’s computational complexity is $O(\log T)$ calls to a least-squares regression oracle plus linear net computational cost across all $T$ rounds. This outperforms previous algorithms. Note that `ILOVETOCONBANDITS` requires $\tilde{O}(\sqrt{KT/\log(|{{\mathcal{F}}}|/\delta)})$ calls to an offline cost-sensitive classification oracle, and `SquareCB` requires $O(T)$ calls to an [online]{} regression oracle — compared with our algorithm, both of them require exponentially more calls to a harder-to-implement oracle. Also, since a general finite ${{\mathcal{F}}}$ is not a convex function class, `RegCB` requires $O(\sqrt{T})$ calls to a weighted least-squares regression oracle for this setting — this is still exponentially slower than our algorithm.

When the total number of rounds $T$ is known to the learner, we can make the computational cost of `FALCON` even lower. For any $T\in{\mathbb{N}}$, consider an epoch schedule used in [@cesa2014regret]: $\tau_m=\left\lceil{T^{1-2^{-m}}}\right\rceil$, $\forall m\in{\mathbb{N}}$. Then `FALCON` will run in $O(\log\log T)$ epochs, calling the oracle for only $O(\log\log T)$ times over $T$ rounds. In this case, we still have the same regret guarantee (up to logarithmic factors), see Corollary \[cor:finite\] below. The proof is at the end of Appendix \[app:thm1\].

\[cor:finite\] For any $T\in{\mathbb{N}}$, consider an epoch schedule $\tau_m=\left\lceil T^{1-2^{-m}}\right\rceil$, $\forall m\in{\mathbb{N}}$. Then with probability at least $1-\delta$, the regret of the `FALCON` algorithm after $T$ rounds is at most $$O\left(\sqrt{KT\log(|{{\mathcal{F}}}|T/\delta)}\log\log T\right).$$

Regret Analysis {#sec:analysis}
===============

In this section, we elaborate on how our simple algorithm achieves the optimal regret. We first analyze our algorithm (through an interesting dual interpretation) and provide in §\[sec:tale\] to §\[sec:ocbl\] a proof sketch of Theorem \[thm:finite\]. Finally, in §\[sec:bypass\], we explain the key idea behind `FALCON`, and in §\[sec:born\], we show how this idea leads to `FALCON`.

Since some notations appearing in Algorithm \[alg:cbor\] are shorthand and do not explicitly reveal the dependencies between different quantities (e.g., $\widehat{a}_t$ and $p_t(\cdot)$ should be written as a function and a conditional distribution explicitly depending on the random context $x_t$), we introduce some new notations which can describe the decision generating process of Algorithm \[alg:cbor\] in a more systematic way. For each epoch $m\in{\mathbb{N}}$, given the learning rate $\gamma_m\in\mathbb{R}_+$ and the greedy predictor $\widehat{f}_m:{{\mathcal{X}}}\times{{\mathcal{A}}}\rightarrow[0,1]$ (which are uniquely determined by the data from the first $m-1$ epochs), we can explicitly represent the algorithm’s decision rule using $\gamma_m$ and $\widehat{f}_m$. In particular, define $$\widehat{a}_m(x)=\max_{a\in{{\mathcal{A}}}}\widehat{f}_m(x,a),$$ $$p_m(a|x)=\frac{1}{K+\gamma_m\left(\widehat{f}_m(x,\widehat{a}_m(x))-\widehat{f}_m(x,a)\right)},~~~\forall a\ne \widehat{a}_m(x),$$ $$p_m(\widehat{a}_m(x)|x)=1-\sum_{a\ne \widehat{a}_m(x)}p_m(a|x).$$ Then $p_m(\cdot|\cdot)$ is a well-defined probability kernel ${\mathcal{B}}({{\mathcal{A}}})\times{{\mathcal{X}}}\rightarrow[0,1]$ that completely characterizes the algorithm’s decision rule in epoch $m$. Specifically, at each round $t$ in epoch $m$, the algorithm first observes a random context $x_t$, then samples its action $a_t$ according to the conditional distribution $p_m(\cdot|x_t)$. Therefore, we call $p_m(\cdot|\cdot)$ the *action selection kernel* of epoch $m$. Note that $p_m(\cdot|\cdot)$ depends on all the randomness up to round $\tau_{m-1}$ (including round $\tau_{m-1}$), which means that $p_m(\cdot|\cdot)$ depends on $p_1(\cdot|\cdot),p_2(\cdot|\cdot),\dots,p_{m-1}(\cdot|\cdot)$, and will affect $p_{m+1}(\cdot|\cdot),p_{m+2}(\cdot|\cdot),\dots$ in later epochs.

A Tale of Two Processes {#sec:tale}
-----------------------

The conventional way of analyzing our algorithm’s behavior at round $t$ in epoch $m$ is to study the following *original* process:

1.  Nature generates $x_t\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}$.

2.  Algorithm samples $a_t\sim p_m(\cdot|x_t)$.

The above process is however difficult to analyze, because the algorithm’s sampling procedure *depends on* the external randomness of nature. That is, the algorithm’s probabilistic selection strategy among actions, as a conditional distribution $p_{m}(\cdot|x_t)$, depends on the random context $x_t$, and cannot be evaluated in advance before observing $x_t$.

A core idea of our analysis is to get rid of thinking about the above process. Instead, we look at the following *virtual* process at round $t$ in epoch $m$:

1.  Algorithm samples $\pi_t\sim Q_m(\cdot)$, where $\pi_t:{{\mathcal{X}}}\rightarrow{{\mathcal{A}}}$ is a *policy*, and $Q_m(\cdot): {{\mathcal{A}}}^{{{\mathcal{X}}}}\rightarrow[0,1]$ is a probability distribution over all policies in ${{\mathcal{A}}}^{{{\mathcal{X}}}}$.

2.  Nature generates $x_t\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}$.

3.  Algorithm selects $a_t=\pi_t(x_t)$ deterministically.

The merit of the above process is that the algorithm’s sampling procedure is *independent of* the external randomness of nature. While the algorithm still has to select an action based on the random context $x_t$ in step 3, this is completely deterministic and easier to analyze. As a result, the algorithm’s internal randomness all comes from a stationary distribution $Q_m(\cdot)$ which is already determined at the beginning of epoch $m$.

The second process is however a *virtual* process because it is not how our algorithm directly proceeds. An immediate question is whether we can always find a distribution over policies $Q_m(\cdot)$, such that our algorithm behaves exactly the same as the process in epoch $m$?

Recall that the algorithm’s decision rule in epoch $m$ is completely characterized by the action selection kernel $p_m(\cdot|\cdot)$. To answer the above question, we have to “translate” any possible probability kernel $p_m(\cdot|\cdot)$ into an “equivalent” distribution over policies $Q_m(\cdot)$ such that we can study our algorithm’s behavior through the virtual process. We complete this translation in §\[sec:translation\].

From Kernel to Randomized Policy {#sec:translation}
--------------------------------

We define the *universal* policy space as $$\Psi={{{\mathcal{A}}}}^{{{\mathcal{X}}}},$$ which contains all possible policies. We consider a product probability measure on $\Psi$ such that for all $\pi\in\Psi$, $$Q_m(\pi)=\Pi_{x\in{{\mathcal{X}}}}p_m(\pi(x)|x).$$ Of course, ${{\mathcal{X}}}$ can be an infinite set, and hence, one may wonder whether an infinite product of probability measures really exists. Fortunately, due to the structure of $p_m(\cdot|\cdot)$ and ${{\mathcal{A}}}$, the existence of a unique product probability measure $Q_m(\cdot)$ is guaranteed by the Kolmogorov extension theorem. We give a proof in Lemma \[lm:map\] in Appendix \[app:thm1\]. The unique $Q_m(\cdot)$ that we find in Lemma \[lm:map\] satisfies that for every $x\in{{\mathcal{X}}},a\in{{\mathcal{A}}}$, we have $$\label{eq:translation}
p_m(a|x)=\sum_{\pi\in\Psi}{\mathbb{I}}\{\pi(x)=a\}Q_m(\pi).$$ That is, for any arbitrary context $x$, the algorithm’s action generated by $p_m(\cdot|x)$ is probabilistically equivalent to the action generated by $Q_m(\cdot)$ through the virtual process in §\[sec:tale\]. Since $Q_m(\cdot)$ is a dense distribution over all *deterministic* policies in the universal policy space, we refer to $Q_m(\cdot)$ as the “equivalent *randomized* policy” induced by $p_m(\cdot|\cdot)$. Through Lemma \[lm:map\] and equation (\[eq:translation\]), we establish a *one-to-one* mapping between any possible probability kernel $p_m(\cdot|\cdot)$ and an equivalent randomized policy $Q_m(\cdot)$. Since $p_m(\cdot|\cdot)$ is uniquely determined by $\gamma_m$ and $\hat{f}_m$, we know that $Q_m(\cdot)$ is also uniquely determined by $\gamma_m$ and $\hat{f}_m$.

We emphasize that our algorithm does not compute $Q_m(\cdot)$, but implicitly maintains $Q_m(\cdot)$ through $\gamma_m$ and $\widehat{f}_m$. This is important, as even in the simple case of finite known ${{\mathcal{X}}}$ where $Q_m(\cdot)$ is directly a finite product of known probability measures, computing $Q_m(\cdot)$ requires $\Omega(|{{\mathcal{X}}}|)$ computational cost which is intractable for large $|{{\mathcal{X}}}|$. Remember that all of our arguments based on $Q_m(\cdot)$ are only applied for the purpose of statistical analysis and have nothing to do with the algorithm’s original implementation.

Dual Interpretation in the Universal Policy Space {#sec:dualnew}
-------------------------------------------------

Through the lens of the virtual process, we find a [dual interpretation]{} of our algorithm: *it sequentially maintains a dense distribution $Q_m(\cdot)$ over all the policies in the universal policy space $\Psi$, for epoch $m=1,2,3\dots$*. The analysis of the behavior of our algorithm thus could hopefully reduce to the analysis of an evolving sequence $\{Q_m\}_{m\in{\mathbb{N}}}$ (which is still non-trivial because it still depends on all the interactive data). All our analysis from now on will be based on the above dual interpretation.

As we start to explore how $\{Q_m\}_{m\in{\mathbb{N}}}$ evolves in the universal policy space, let us first define some *implicit* quantities in this world which are useful for our statistical analysis — they are called “[implicit]{}” because our algorithm does not really compute or estimate them at all, yet they are all well-defined and implicitly exist as long as our algorithm proceeds.

Define the “implicit reward” of a policy $\pi\in\Psi$ as $${{\mathcal{R}}}(\pi):={{\mathbb{E}}}_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}}\left[f^*(x,\pi(x))\right]$$ and define the “implicit regret”[^3] of a policy $\pi\in\Psi$ as $${{\mathrm{Reg}}}(\pi)={{\mathcal{R}}}(\pi_{f^*})-{{\mathcal{R}}}(\pi).$$ Given a predictor $\widehat{f}_m$, define the “predicted implicit reward” of a policy $\pi\in\Psi$ as $${\widehat{\mathcal{R}}}_t(\pi):={{\mathbb{E}}}_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}}\left[\widehat{f}_{m(t)}(x,\pi(x))\right]$$ and define the “predicted implicit regret” of a policy $\pi\in\Psi$ as[^4] $${\widehat{\mathrm{Reg}}}_t(\pi)={\widehat{\mathcal{R}}}_t(\pi_{\widehat{f}_{m(t)}})-{\widehat{\mathcal{R}}}_t(\pi).$$ The idea of defining the above quantities is motivated by the celebrated work of [@agarwal2014taming], which studies policy-based optimal contextual bandit learning in the agnostic setting (in which setting the above quantities are not implicit but play obvious roles and are directed estimated by their algorithm). There are some differences in the definitions though. For example, [@agarwal2014taming] define the above quantities for all policies $\pi$ in a given finite policy class $\Pi$, while we define the above quantities for all policies in the universal policy space $\Psi$ (which is strictly larger than $\Pi$). Also, [@agarwal2014taming] define ${\widehat{\mathcal{R}}}_t(\pi)$ and ${\widehat{\mathrm{Reg}}}_t(\pi)$ based on the inverse propensity scoring estimates, while we define them based on a single predictor. We will revisit these differences later.

After defining the above quantities, we make a simple yet powerful observation, which is an immediate consequence of (\[eq:translation\]): for any epoch $m\in{\mathbb{N}}$ and any round $t$ in epoch $m$, we have $${{\mathbb{E}}}_{(x_t,r_t)\sim{{\mathcal{D}}},a_t\sim p_m(\cdot|x_t)}\left[r_t(\pi_{f^*})-r_t(a_t)|\gamma_m, \widehat{f}_m\right]=\sum_{\pi\in\Psi}Q_m(\pi){{\mathrm{Reg}}}(\pi),$$ see Lemma \[lm:equi\] in Appendix \[app:thm1\]. This means that (under any possible realization of $\gamma_m,\widehat{f}_m$) the expected instantaneous regret incurred by our algorithm equals to the “implicit regret” of the randomized policy $Q_m$ (as a weighted sum over the implicit regret of every deterministic policy $\pi\in\Psi$). Since ${{\mathrm{Reg}}}(\pi)$ is a fixed deterministic quantity for each $\pi\in\Psi$, the above equation indicates that to analyze our algorithm’s expected regret in epoch $m$, we only need to analyze the how the distribution $Q_m(\cdot)$ looks like. This property shows the advantage of our dual interpretation: compared with the original process in §\[sec:tale\] where it is hard to evaluate our algorithm without $x_t$, now we can evaluate our algorithm’s behavior regardless of $x_t$.

Optimal Contextual Bandit Learning in the Universal Policy Space {#sec:ocbl}
----------------------------------------------------------------

Once we realize that in order to understand the behavior of our algorithm we only need understand the properties of $Q_m(\cdot)$, the analysis of our algorithm is not difficult anymore. We first state an immediate observation based on the equivalence relationship between $p_m(\cdot|\cdot)$ and $Q_m(\cdot)$ in equation (\[eq:translation\]).

For any deterministic policy $\pi\in\Psi$, the quantity ${{\mathbb{E}}}_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}}\left[{\frac{1}{p_m(\pi(x)|x)}}\right]$ is the expected inverse probability that “the decision generated by the randomized policy $Q_m$ is the same as the decision generated by the deterministic policy $\pi$”, over the randomization of context $x$. This quantity can be intuitively understood as a measure of the “decisional divergence” between the randomized policy $Q_m$ and the deterministic policy $\pi$.

Now let us utilize the closed-form structure of $p_m(\cdot|x)$ in our algorithm and point out a most important property of $Q_m(\cdot)$ stated below (see Lemma \[lm:op1\] and Lemma \[lm:op2\] in Appendix $\ref{app:thm1}$ for details).

\[obs:2\] For any epoch $m\in{\mathbb{N}}$ and any round $t$ in epoch $m$, for any possible realization of $\gamma_m$ and $\widehat{f}_m$, $Q_m(\cdot)$ is a feasible solution to the following “[Implicit Optimization Problem]{}” (`IOP`): $$\begin{aligned}
    &\sum_{\pi\in\Psi}Q_m(\pi){\widehat{\mathrm{Reg}}}_{t}(\pi)\le {K}/{\gamma_m},\label{eq:op11}\\
    \forall \pi\in\Psi,~~~&{{\mathbb{E}}}_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}}\left[\frac{1}{p_m(\pi(x)|x)}\right]\le K+\gamma_m{\widehat{\mathrm{Reg}}}_{t}(\pi).\label{eq:op22}\end{aligned}$$

We give some interpretations for the “[Implicit Optimization Problem]{}” (`IOP`) defined above. (\[eq:op11\]) says that $Q_m$ controls its predicted implicit regret (as a weighted sum over the predicted implicit regret of every policy $\pi\in\Psi$, based on the predictor $\widehat{f}_m$) within $K/\gamma_m$. This can be understood as an “exploitation constraint” because it require $Q_m$ to put more mass on “good policies” with low predicted implicit regret (as judged by the current predictor $\widehat{f}_m$). (\[eq:op22\]) says that the decisional divergence between $Q_m(\cdot)$ and any policy $\pi\in\Psi$ is controlled by the predicted implicit regret of policy $\pi$ (times a learning rate $\gamma_m$ and plus a constant $K$). This can be understood as an “adaptive exploration constraint”, as it requires that $Q_m$ behaves similarly to *every* policy $\pi\in\Psi$ at some level (which means that there should be sufficient exploration), while allowing $Q_m$ to be more similar to “good policies” with low predicted implicit regret and less similar to “bad policies” with high predicted implicit regret (which means that the exploration can be conducted adaptively based on the judgement of the predictor $\widehat{f}_m$). Combining (\[eq:op11\]) and (\[eq:op22\]), we conclude that $Q_m$ elegantly strikes a balance between exploration and exploitation — it is surprising that this is done completely implicitly, as the original algorithm does not explicitly consider these constraints at all.

There are still a few important tasks to complete. The first task is to figure out what exactly the decisional divergence ${{\mathbb{E}}}_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}}\left[{\frac{1}{p_m(\pi(x)|x)}}\right]$ means. We give an answer in Lemma \[lm:reward-estimates\], which shows that with high probability, for any epoch $m\in{\mathbb{N}}$ and any round $t$ in epoch $m$, for all $\pi\in\Psi$, $$|{\widehat{\mathcal{R}}}_t(\pi)-{{\mathcal{R}}}(\pi)|\le\frac{\sqrt{K}}{2\gamma_{m}}\sqrt{\max_{1\le n \le m-1}{{\mathbb{E}}}_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}}\left[{\frac{1}{p_n(\pi(x)|x)}}\right]}.$$ That is, the prediction error of the implicit reward of every policy $\pi\in\Psi$ can be bounded by the (maximum) decisional divergence between $\pi$ and all previously used randomized policies $Q_1,\dots,Q_{m-1}$. This is consistent with our intuition, as the more similar a policy is to the previously used randomized policies, the more likely that this policy is implicitly explored in the past, and thus the more accurate our prediction on this policy should be. We emphasize that the above inequality relies on our specification of the learning rate $\gamma_m$: we can bound the prediction error using $1/\gamma_m$ because $1/\gamma_m$ is proportional to $1/\sqrt{\tau_{m-1}}$ and proportional to $\sqrt{\log|{{\mathcal{F}}}|}$ — the first quantity $1/\sqrt{\tau_{m-1}}$ is related to the length of the history, and the second quantity $\sqrt{\log|{{\mathcal{F}}}|}$ is related to the generalization ability of function class ${{\mathcal{F}}}$. This is the first place that our proof requires an epoch-varying learning rate.

The second task is to further bound (the order of) the prediction error of the implicit regret of every policy $\pi$, as the implicit regret is an important quantity that can be directly used to bound our algorithm’s expected regret (see §\[sec:dualnew\]). We do this in Lemma \[lm:regret-estimates\], where we show that with high probability, for any epoch $m\in{\mathbb{N}}$ and any round $t$ in epoch $m$, for all $\pi\in\Psi$, $${{\mathrm{Reg}}}(\pi)\le 2{\widehat{\mathrm{Reg}}}_t(\pi)+5.15K/\gamma_{m},$$ $${\widehat{\mathrm{Reg}}}_t(\pi)\le 2{{\mathrm{Reg}}}(\pi)+5.15K/\gamma_{m}$$ through an inductive argument. While this is a uniform-convergence-type result, we would like to clarify that this does not mean that there is a uniform convergence of $|{{\mathrm{Reg}}}(\pi)-{\widehat{\mathrm{Reg}}}_t(\pi)|$ for all $\pi\in\Psi$, which is too strong and unlikely to be true. Instead, we use a smart design of ${{\mathrm{Reg}}}(\pi)-2{\widehat{\mathrm{Reg}}}_t(\pi)$ and ${\widehat{\mathrm{Reg}}}_t(\pi)-2{{\mathrm{Reg}}}(\pi)$ (the design is motivated by Lemma 13 in @agarwal2014taming), which enables us to characterize the fact that the predicted implicit regret of “good policies” are becoming more and more accurate, while the predicted implicit regret of “bad policies” do not need to be accurate (as their orders directly dominate $K/\gamma_m$). We emphasize that the above result relies on the fact that our learning rate $\gamma_m$ is gradually increasing from $O(1)$ to $O(\sqrt{T})$, as we use an inductive argument and in order to let the hypothesis hold for initial cases we have to let $\gamma_m$ be very small for small $m$. This is the second place that our proof requires a epoch-varying learning rate.

We have elaborated on how our algorithm implicitly strikes a balance between exploration and exploitation, and how our algorithm implicitly enables some nice uniform-convergence-type results to happen in the universal policy space. This is already enough to guarantee that the dual interpretation of our algorithm achieves optimal contextual bandit learning in the universal policy space. The rest of the proof is standard and can be found in Appendix \[app:thm1\].

Key Idea: Bypassing the Monster {#sec:bypass}
-------------------------------

For readers who are familiar with the research line of optimal contextual bandits learning in the agnostic setting using an offline cost-sensitive classification oracle (represented by @dudik2011efficient [@agarwal2014taming]), they may find a surprising connection between the `IOP` (\[eq:op11\]) (\[eq:op22\]) that we introduce in Observation \[obs:2\] and the so-called “Optimization Problem” (`OP`) in [@dudik2011efficient] and [@agarwal2014taming] — in particular, if one takes a look at the `OP` defined in page 5 of [@agarwal2014taming], she will find that it is almost the same as our `IOP` (\[eq:op11\]) (\[eq:op22\]), except for two fundamental differences:

1.  The `OP` of [@dudik2011efficient] and [@agarwal2014taming] is defined on a given finite policy class $\Pi$, which may have an arbitrary shape. As a result, to get a solution to `OP`, the algorithm must explicitly solve a complicated (non-convex) optimization problem over a possibly complicated policy class — this requires considerable number of calls to a cost-sensitive classification oracle, and is the major computational burden of [@dudik2011efficient] and [@agarwal2014taming]. Although [@agarwal2014taming] “tame the monster” and reduce the computational cost by only strategically maintaining a *sparse* distribution over policies in $\Pi$, solving `OP` still requires $\widetilde{O}(\sqrt{KT/\log|\Pi|})$ calls to the classification oracle and is computationally expensive — the monster is still there.

    By contrast, our `IOP` is defined on the universal policy space $\Psi$, which is a nice product topological space. The `IOP` can thus be viewed as a very “slack” relaxation of `OP` which is extremely easy to solve. In particular, as §\[sec:analysis\] suggests, the solution to `IOP` can have a completely decomposed form which enables our algorithm to solve it in a complete *implicit* way. This means that our algorithm can implicitly and confidently maintain a *dense* distribution over all policies in $\Psi$, while solving `IOP` in closed forms with no computational cost — there is no monster any more as we simply bypass it.

2.  In [@dudik2011efficient] and [@agarwal2014taming], the quantities ${\widehat{\mathcal{R}}}_t(\pi)$ and ${\widehat{\mathrm{Reg}}}_t(\pi)$ are explicitly calculated based on the model-free inverse propensity scoring estimates. As a result, their regret guarantees do not require the realizability assumption.

    By contrast, in our paper, the quantities ${\widehat{\mathcal{R}}}_t(\pi)$ and ${\widehat{\mathrm{Reg}}}_t(\pi)$ are implicitly calculated based on a single greedy predictor $\widehat{f}\in{{\mathcal{F}}}$ — we can do this because we have the realizability assumption $f^*\in{{\mathcal{F}}}$. As a result, we make a single call to a least-squares regression oracle here, and this is the main computational cost of our algorithm.

A possible question could then be that, given the fact that the main computational burden of [@dudik2011efficient] and [@agarwal2014taming] is solving `OP`, why can’t they simply relax `OP` as what we do in our `IOP`? The answer is that without the realizability assumption, they have to rely on the capacity control of their policy space, i.e., the boundedness of $\Pi$, to obtain their statistical guarantees. Indeed, as their $\widetilde{O}(\sqrt{KT\log|\Pi|})$ regret bound suggests, if one let $\Pi={{\mathcal{A}}}^{{\mathcal{X}}}$, then the regret could be as large as $\Omega(|{{\mathcal{X}}}|)$. Specifically, their analysis requires the boundedness (or more generally the limited complexity) of $\Pi$ in two places: first, a generalization guarantee of the inverse propensity scoring requires limited $|\Pi|$; second, since they have to explicitly compute ${\widehat{\mathcal{R}}}_t(\pi)$ and ${\widehat{\mathrm{Reg}}}_t(\pi)$ without knowing the true context distribution ${{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}$, they try to approximate it based on the historical data, which also requires limited $|\Pi|$ to enable statistical guarantees.

Our algorithm bypasses the above two requirements simultaneously: first, since we use model-based regression rather than model-free inverse propensity scoring to make predictions, we do not care about the complexity of our policy space in terms of prediction (i.e., the generalization guarantee of our algorithm comes from the boundedness of ${{\mathcal{F}}}$ not $\Psi$); second, since our algorithm does not require explicit computation of ${\widehat{\mathcal{R}}}_t(\pi)$ and ${\widehat{\mathrm{Reg}}}_t(\pi)$, we do not care about what ${{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}$ looks like. Essentially, all of these nice properties originate from the realizability assumption. This is how we understand the value of realizability: it does not only (statistically) give us better predictions, but also (computationally) enables us to remove the restrictions in the policy space , which helps us to bypass the monster.

The Born of `FALCON` {#sec:born}
--------------------

Seemingly intriguing and tricky, `FALCON` is actually an algorithm that can be derived from systematical analysis. The idea of “bypassing the monster”, as explained in §\[sec:bypass\], is exactly what leads to the derivation of the `FALCON` algorithm. Before we close this section, we introduce how `FALCON` is derived. We hope that this derivation process can motivate further discovery of new algorithms for other bandits / reinforcement learning problems.

1.  We do a thought experiment, considering how `ILOVETOCONBANDITS` (@agarwal2014taming) can solve our problem without the realizability assumption, given an induced policy class $\Pi=\{\pi_f|f\in{{\mathcal{F}}}\}$.

2.  `ILOVETOCONBANDITS` uses an inverse propensity scoring approach to compute the predicted reward and predicted regret of policies. This can be equivalently viewed as first computing an “inverse propensity predictor” $\widehat{f}_m(x,a)=\frac{1}{t}\sum_{s=1}^t\frac{r_s(a_s){\mathbb{I}}\{a_s=a\}}{{\mathbb{P}}(a_s|x_s,\sigma(H_{s-1}))}$, then using our definition in §\[sec:dualnew\] to compute ${\widehat{\mathcal{R}}}_t(\pi)$ and ${\widehat{\mathrm{Reg}}}_t(\pi)$ if ${{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}$ is known.

3.  The computational burden in the above thought experiment is to solve `OP` over $\Pi$, which requires repeated calls to a cost-sensitive classification oracle.

4.  When we have realizability, we can use a regression oracle to obtain predictor $\widehat{f}_m$, thus we do not need to use the model-free inverse propensity scoring predictor. As a result, we do not need our policy space to be bounded to ensure generalization ability.

5.  An early technical result of Lemma 4.3 in [@agarwal2012contextual] is very interesting. It shows that when one tries to solve contextual bandits using regression approaches, one should try to bound a quantity like “the expected inverse probability of choosing the same action” — note that a very similar quantity also appears in `OP` in [@agarwal2014taming]. This suggests that an offline-regression-oracle-based algorithm should try to satisfy some requirements similar to `OP`. (Lemma 4.3 in [@agarwal2012contextual] also motivates our Lemma \[lm:reward-estimates\]. But our Lemma \[lm:reward-estimates\] goes a significant step beyond Lemma 4.3 in [@agarwal2012contextual] by unbinding the relationship between a predictor and a policy and moving forward to the universal policy space.)

6.  Motivated by 3, 4, and 5, we relax the domain of `OP` from $\Pi$ to $\Psi$, and obtain the relaxed problem `IOP`. Since the new domain $\Psi={{\mathcal{A}}}^{{\mathcal{X}}}$ is a product space, we consider the per-context decomposed version of `IOP`, i.e., a problem “conditional on a single $x$”: $$\begin{aligned}
        \sum_{\pi(x)\in{{\mathcal{A}}}}p_m(\pi(x)|x){\gamma_m}\left(\widehat{f}_m(\pi_{\widehat{f}_m}(x))-\widehat{f}_m(\pi(x))\right)\le {K},\\
        \forall \pi(x)\in{{\mathcal{A}}},~~~\frac{1}{p_m(\pi(x)|x)}\le K+\gamma_m\left(\widehat{f}_m(\pi_{\widehat{f}_m}(x))-\widehat{f}_m(\pi(x))\right).\end{aligned}$$ Clearly, there is a closed-form solution to the above problem: the conditional probability of selecting an action $\pi(x)$ should be inversely proportional to the predicted reward gap of $\pi(x)$ times $\gamma_m$. This leads to `FALCON`’s decision generating process in epoch $m$.

Extension to Infinite Function Classes {#sec:extension}
======================================

We now extend our results to the case of infinite function classes. While we can still assume a least-squares regression oracle as before (which corresponds to the *empirical risk minimization* (ERM) procedure under square loss in offline statistical learning), for different ${{\mathcal{F}}}$, some other types of offline regression oracles may be preferred. For example, from a computational point of view, it is often more convenient to implement oracles based on explicit penalization or regularization terms (i.e., regularized least squares), see, e.g., Chapter 13.4 in [@wainwright2019high]; meanwhile, from a statistical point of view, least-squares regression oracle (i.e. ERM under square loss) may be statistically sub-optimal for various ${{\mathcal{F}}}$, and in these cases some aggregation-based oracles may be preferred, see, e.g., Section 6 and 7 in [@rakhlin2017empirical]. Therefore, in this section, we state our results in a more general way: we assume access to an arbitrary offline regression oracle with an arbitrary statistical learning guarantee, and design an algorithm that makes calls to this arbitrary oracle and utilizes its statistical learning guarantees. Recall that the goal of this paper is to accomplish an online-to-offline reduction from contextual bandits to offline regression. So ultimately, we want to provide a universal and optimal “offline-to-online converter”, such that any results for statistical learning with a general function class can be immediately translated to contextual bandits with a general function class.

Given a general function class ${{\mathcal{F}}}$ and a predictor $\widehat{f}:{{\mathcal{X}}}\times{{\mathcal{A}}}\rightarrow[0,1]$, in statistical learning theory, the quality of $\widehat{f}$ is typically measured by its *estimation error* (or *excess risk*): $$\begin{aligned}
    &{{\mathbb{E}}}_{(x,a,r(a))\sim{{\mathcal{D}}}_{data}}\left[(\widehat{f}(x,a)-r(a))^2\right]-\inf_{f\in{{\mathcal{F}}}}{{\mathbb{E}}}_{(x,a,r(a))\sim{{\mathcal{D}}}_{data}}\left[(f(x,a)-r(a))^2\right]\\
    =&{{\mathbb{E}}}_{(x,a,r(a))\sim{{\mathcal{D}}}_{data}}\left[(\widehat{f}(x,a)-r(a))^2\right]-{{\mathbb{E}}}_{(x,a,r(a))\sim{{\mathcal{D}}}_{data}}\left[(f^*(x,a)-r(a))^2\right]\\
    =&{{\mathbb{E}}}_{(x,a,r(a))\sim{{\mathcal{D}}}_{data}}\left[(\widehat{f}(x,a)-f^*(x,a))^2\right].\end{aligned}$$ where ${{\mathcal{D}}}_{data}$ is an arbitrary (possibly unknown) distribution, and the first equality follows from the realizability assumption. A generic *offline regression oracle* for function class ${{\mathcal{F}}}$, denoted by $\texttt{OffReg}_{{{\mathcal{F}}}}$, is defined as a procedure that generates a predictor $\widehat{f}:{{\mathcal{X}}}\times{{\mathcal{A}}}\rightarrow[0,1]$ based on input data.[^5] Note that here we do not require $\widehat{f}\in{{\mathcal{F}}}$. We make the following generic assumption on the statistical learning guarantee of $\texttt{OffReg}_{{{\mathcal{F}}}}$.

Given $n$ data samples $\{((x_1,a_1,r_1(a_1)),\cdots,(x_n,a_n,r_n(a_n)\}$ generated i.i.d. from an arbitrary distribution ${{\mathcal{D}}}_{data}$, the offline regression oracle $\texttt{OffReg}_{{{\mathcal{F}}}}$ returns a function $\widehat{f}$. For all $\delta>0$, with probability at least $1-\delta$, we have $${{\mathbb{E}}}_{(x,a,r(a))\sim{{\mathcal{D}}}_{data}}\left[(\widehat{f}(x,a)-f^*(x,a))^2\right]\le\xi_{{{\mathcal{F}}},\delta}(n).$$

We call $\xi_{{{\mathcal{F}}},\delta}(n)$ the estimation error guarantee of $\texttt{OffReg}_{{{\mathcal{F}}}}$. Clearly, $\xi_{{{\mathcal{F}}},\delta}(n)$ is a decreasing function of $n$.

The Algorithm {#the-algorithm}
-------------

We provide an algorithm, namely `FALCON+`, in Algorithm \[alg:falcon+\]. The key differences between Algorithm \[alg:falcon+\] and Algorithm \[alg:cbor\] lie in step 2 and step 3. In step 2, we define a new epoch-varying learning rate based on the estimation error guarantee of $\texttt{OffReg}_{{{\mathcal{F}}}}$ — this is direct generalization of the learning rate defined in Algorithm \[alg:cbor\]. In step 3, instead of feeding all the previous data into the oracle, we [only feed the data in epoch $m-1$ into the oracle]{}. We make two comments here. First, while we do not feed all the previous data into the oracle any more, this is still a greedy-type call to the offline oracle, as we do not make any exploration consideration in this step. Second, the strategy of only feeding the data in the last epoch into the oracle is purely due to technical reasons, as we want to avoid more complicated analysis of a martingale process. Note that as a consequence of this strategy, our algorithm must run in gradually increasing epochs, e.g., $\tau_m=2^m$ or $\tau_m=\left\lceil T^{1-2^{-m}}\right\rceil$.

[**input** epoch schedule $0=\tau_0<\tau_1<\tau_2<\cdots$, confidence parameter $\delta$.]{}

. . Define $$p_t(a)=\begin{cases}
        \frac{1}{K+\gamma_m\left(\widehat{f}_m(x_t,\widehat{a}_t)-\widehat{f}_m(x_t,a)\right)},&\text{for all }a\ne \widehat{a}_t,\\
        1-\sum_{a\ne\widehat{a}_t}p_t(a),&\text{for }a=\widehat{a}_t.
        \end{cases}$$

Regret Guarantee
----------------

Define $m(T):=\min\{m\in{\mathbb{N}}:T\le\tau_m\}$, which is the total number of epochs that Algorithm \[alg:falcon+\] executes. The regret guarantee of Algorithm \[alg:falcon+\] is stated in Theorem \[thm:inf\]. The proof of Theorem 2 is deferred to Appendix \[app:thm2\].

\[thm:inf\] Consider an epoch schedule such that $\tau_m\ge2^m$ for $m\in{\mathbb{N}}$. Without loss of generality, assume that $\gamma_1\le\cdots\le\gamma_{m(T)}$. For any $T\in{\mathbb{N}}$, with probability at least $1-\delta$, the regret of Algorithm \[alg:falcon+\] after $T$ rounds is at most $$O\left(\sqrt{K}\sum_{m=2}^{m(T)}\sqrt{\xi_{{{\mathcal{F}}},\delta/(2T)}(\tau_{m-1}-\tau_{m-2})}(\tau_m-\tau_{m-1})\right).$$

The above regret bound is general and it typically has the same rate as $O\left(\sqrt{K{\xi_{{{\mathcal{F}}},\delta/(2T)}(T)}})T\right)$. Therefore, given an arbitrary offline regression oracle with an arbitrary estimation guarantee $\xi_{{{\mathcal{F}}},\delta}(\cdot)$, we know that our algorithm’s regret is upper bounded by $O\left(\sqrt{K{\xi_{{{\mathcal{F}}},\delta/(2T)}(T)}})T\right)$. We give some examples below.

Consider a general function class ${{\mathcal{F}}}$ whose *empirical entropy* is $O(\varepsilon^{-p})$, $\forall \varepsilon>0$ for some constant $p>0$. [@yang1999information] and [@rakhlin2017empirical] provide several offline regression oracles that achieves the optimal $\xi_{{{\mathcal{F}}}}(n)=O(n^{-2/(2+p)})$ estimation error rate. By letting $\tau_{m}=2^m$ for $m\in{\mathbb{N}}$, the regret of `FALCON+` is upper bounded by $O(T^{\frac{1+p}{2+p}})$ when one ignores the dependency on $K$. Combined with an $\widetilde{\Omega}(T^{\frac{1+p}{2+p}})$ lower bound proved in [@foster2020beyond], we know that `FALCON+` is statisticaly optimal as long as the offline regression oracle is statistical optimal. We thus accomplish a universal and optimal reduction from contextual bandits to offline regression.

Consider the linear contextual bandit setting of [@chu2011contextual] with stochastic contexts. This corresponds to setting ${{\mathcal{F}}}$ to be the linear class $${{\mathcal{F}}}=\{(x,a)\mapsto \theta^\top x_a \mid \theta\in\mathbb{R}^d, \|\theta\|_2\le 1\},$$ where $x=(x_a)_{a\in{{\mathcal{A}}}}$, $x_a\in\mathbb{R}^d$ and $\|x_a\|_2\le1$. In this case, by using the least squares regression oracle, `FALCON+` achieves the regret $O(\sqrt{KT(d+\log T)})$. Compared with the best known upper bound for this problem, $\text{poly}(\log\log KT)O(\sqrt{Td\log T\log K})$ in [@li2019nearly], `FALCON+` has a worse dependency on $K$, but saves a $\sqrt{\log T}$ factor on $T$, which means that `FALCON+` improves the best known regret upper bound for this problem when $K<< T$. To the best of our knowledge, this is the first time that an algorithm gets over the $\Omega(\sqrt{Td\log T})$ barrier for this problem — notably, our new upper bound even “breaks” the $\Omega(\sqrt{T d\log T\log K})$ lower bound proved in [@li2019nearly]. The caveat here is that [@li2019nearly] study the setting where contexts are chosen by an *oblivious* adversary, while we are considering the setting where contexts are stochastic. We think that our finding that the $\Omega(\sqrt{Td\log T})$ barrier does not exist for linear contextual bandits with stochastic contexts is quite interesting.

In general, one can set ${{\mathcal{F}}}$ to be any parametric or noparametric function class, e.g., high-dimensional parametric class, Liptschitz function class, reproducing kernel Hilbert spaces, and even neural networks. For any function class ${{\mathcal{F}}}$, we can obtain a practical algorithm achieving the optimal regret for the corresponding contextual bandit problem, as long as we can find a computationally-efficient and statisitcally-optimal offline regression oracle. This usually leads to faster algorithms with improved regret bounds. In particular, our regret upper bounds’ dependencies on $T$ are usually better than previous upper bounds in the literature, thanks to the fact that we lose very little factors on $T$ when we directly convert an offline estimation error bound to a regret bound. Moreover, our results enable people to tackle broader classes of new contextual bandits problems, such as contextual bandits with neural networks. Finally, we would like to mention that if one compares `FALCON+` with `SqaureCB` (@foster2020beyond), which also works for general function classes as long as one has access to an efficient online regression oracle, the two approaches seem to have different advantages and disadvantages. On the one hand, we believe that `FALCON+` may be the more effective one when the contexts are stochastic, as efficient offline regression oracles are available for more function classes and they may lead to tighter regret bounds. On the other hand, `SquareCB` has the merit of working robustly when the contexts are chosen adversarially.

Conclusion {#sec:conclusion}
==========

In this paper, we propose the first provably optimal offline-regression-oracle-based algorithm for contextual bandits, solving an important open problem for realizable contextual bandits. Our algorithm is surprisingly fast and simple, and our analysis is quite general. We hope that our findings can motivate future research on contextual bandits and reinforcement learning.

Proof of Theorem \[thm:finite\] {#app:thm1}
===============================

Definitions
-----------

For notational convenience, we make some definitions. Some of the definitions have appeared in the main article. $$V(p,\pi):={{\mathbb{E}}}_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}}\left[\frac{1}{p(\pi(x)|x)}\right].$$ $$m(t):=\min\{m\in{\mathbb{N}}:t\le\tau_m\}.$$ $${{\mathcal{V}}}_t(\pi):=\max_{1\le m \le m(t)-1}\{V(p_m,\pi)\}.$$ $${{\mathcal{R}}}(\pi):={{\mathbb{E}}}_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}}\left[f^*(x,\pi(x))\right].$$ $${\widehat{\mathcal{R}}}_t(\pi):={{\mathbb{E}}}_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}}\left[\widehat{f}_{m(t)}(x,\pi(x))\right].$$ $${{\mathrm{Reg}}}(\pi)={{\mathcal{R}}}(\pi_{f^*})-{{\mathcal{R}}}(\pi).$$ $${\widehat{\mathrm{Reg}}}_t(\pi)={\widehat{\mathcal{R}}}_t(\pi_{\widehat{f}_{m(t)}})-{\widehat{\mathcal{R}}}_t(\pi).$$ $$\Upsilon_t=\sigma((x_1,r_1,a_1),\cdots,(x_t,r_t,a_t)).$$

Basic Lemmas
------------

We start from some basic “generic” lemmas that hold true for any algorithms, see Lemma \[lm:ag12-1\] and Lemma \[lm:ag12-2\]. Note that these lemmas do not rely on any specific property of an algorithm — in particular, while Lemma \[lm:ag12-2\] involve some definitions like $\{\tau_m\}$ and $\{\widehat{f}_m\}$, these quantities are well-defined for any algorithm, regardless of whether the algorithm uses them to make decisions.

\[lm:ag12-1\] Fix a function $f\in{{\mathcal{F}}}$. Suppose we sample $x,r$ from the data distribution ${{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}$, and an action $a$ from an arbitrary distribution such that $r$ and $a$ are conditionally independent given $x$. Define the random variable $$Y=(f(x,a)-r(a))^2-(f^*(x,a)-r(a))^2.$$ Then we have $${{\mathbb{E}}}_{x,r,a}[Y]={{\mathbb{E}}}_{x,a}[(f(x,a)-f^*(x,a))^2],$$ $${\bm{\mathrm{Var}}}_{x,r,a}[Y]\le 4{{\mathbb{E}}}_{x,r,a}[Y].$$

\[lm:ag12-2\]For all $m\ge2$, with probability at least $1-{\delta}/{(4(\tau_{m-1})^2)}$, we have: $$\begin{aligned}
&\sum_{t=1}^{\tau_{m-1}}{{\mathbb{E}}}_{x_t,r_t,a_t}\left[(\widehat{f}_{m}(x_t,a_t)-r_t(a_t))^2-(f^*(x_t,a_t)-r_t(a_t))^2|\Upsilon_{t-1}\right]\\
=&\sum_{t=1}^{\tau_{m-1}}{{\mathbb{E}}}_{x_t,a_t}\left[(\widehat{f}_{m}(x_t,a_t)-f^*(x_t,a_t))^2|\Upsilon_{t-1}\right]\\\le& 100\log\left(\frac{4|{{\mathcal{F}}}|(\tau_{m-1})^2\log_2(\tau_{m-1})}{\delta}\right).\end{aligned}$$ Therefore (by a union bound), the following event ${{\mathcal{E}}}$ holds with probability at least $1-\delta/2$: $$\label{eq:clean-event}
{{\mathcal{E}}}:=\left\{\forall m\ge2,\sum_{t=1}^{\tau_{m-1}}{{\mathbb{E}}}_{x_t,a_t}\left[(\widehat{f}_{m}(x_t,a_t)-f^*(x_t,a_t))^2|\Upsilon_{t-1}\right]\le 100\log\left(\frac{4|{{\mathcal{F}}}|(\tau_{m-1})^2\log_2(\tau_{m-1})}{\delta}\right)\right\}.$$

The proofs of Lemma \[lm:ag12-1\] and Lemma \[lm:ag12-2\] can be found in [@agarwal2012contextual] and are omitted here. For notational simplicity, in the definition of ${{\mathcal{E}}}$, we may further relax $100\log\left({4|{{\mathcal{F}}}|(\tau_{m-1})^2\log_2(\tau_{m-1})}/{\delta}\right)$ to $225\log\left({|{{\mathcal{F}}}|\tau_{m-1}}/{\delta}\right)$.

Per-Epoch Properties of the Algorithm
-------------------------------------

We start to utilize the specific properties of our algorithm to prove our regret bound. We start from some per-epoch properties that always hold for our algorithm regardless of its performance in other epochs.

As we mentioned in the main article, a starting point of our proof is to translate the action selection kernel $p_m(\cdot|\cdot)$ into an “equivalent” distribution over policies $Q_m(\cdot)$. Lemma \[lm:map\] provides a justification of such translation by showing the existence of a probabilitically-equivalent $Q_m$ for every $p_m(\cdot|\cdot)$.

\[lm:map\] Fix any epoch $m\in{\mathbb{N}}$. The action selection scheme $p_m(\cdot|\cdot)$ is a valid probability kernel ${\mathcal{B}}({{\mathcal{A}}})\times{{\mathcal{X}}}\rightarrow[0,1]$. There exists a probability measure $Q_m:\Psi\rightarrow[0,1]$ such that $$\forall a\in{{\mathcal{A}}},\forall x\in{{\mathcal{X}}},~~~p_{m}(a|x)=\sum_{\pi\in{\Psi}}{\mathbb{I}}\{\pi(x)=a\}Q_m(\pi).$$

For each $x\in{{\mathcal{X}}}$, since ${{\mathcal{A}}}$ is discrete and finite, $({{\mathcal{A}}},{\mathcal{B}}({{\mathcal{A}}}),p_m(\cdot|x))$ is a probability space satisfying the requirements of Theorem 2.4.4 in [@tao2013introduction] (the theorem is essentially a corollary of the Kolmogorov extension theorem). By Theorem 2.4.4 in [@tao2013introduction], there exists a unique probability measure $Q_m=\Pi_{x\in{{\mathcal{X}}}}p_m(\cdot|x)$ on $(\Psi,({\mathcal{B}}({{\mathcal{A}}}))^{{\mathcal{X}}})$ with the property that $$Q_m(\Pi_{x\in{{\mathcal{X}}}}E_x)=\Pi_{x\in{{\mathcal{X}}}}p_m(E_x|x)$$whenever one has $E_x\in{\mathcal{B}}({{\mathcal{A}}})$ for all $x\in{{\mathcal{X}}}$ and one has $E_x={{\mathcal{A}}}$ for all but finitely many of the $x$. For any $a_0\in{{\mathcal{A}}},x_0\in{{\mathcal{X}}}$, by letting $E_{x_0}=\{a_0\}$ and $E_{x_0}={{\mathcal{A}}}$ for all $x\ne x_0$, we prove Lemma \[lm:map\].

We call the $Q_m$ determined in the proof of Lemma \[lm:map\] the “equivalent randomized policy” induced by $p_m(\cdot|\cdot)$. Lemma \[lm:equi\] states a key property of $Q_m$: the expected instantaneous regret incurred by $p_m(\cdot|\cdot)$ equals to the implicit regret of the randomized policy $Q_m$. Thus, to analyze our algorithm’s expected regret, we only need to analyze the induced randomized policies’ implicit regret.

\[lm:equi\] Fix any epoch $m\in{\mathbb{N}}$, for any round $t$ in epoch $m$, we have $${{\mathbb{E}}}_{x_t,r_t,a_t}\left[r_t(\pi_{f^*})-r_t(a_t)|\Upsilon_{t-1}\right]=\sum_{\pi\in\Psi}Q_m(\pi){{\mathrm{Reg}}}(\pi).$$

By Lemma \[lm:equi\], we have $$\begin{aligned}
&{{\mathbb{E}}}_{x_t,r_t,a_t}\left[r_t(\pi_{f^*})-r_t(a_t)|\Upsilon_{t-1}\right]\\
=&{{\mathbb{E}}}_{x_t,a_t}\left[f^*(x_t,\pi_{f^*}(x_t))-f^*(x_t,a_t)|\Upsilon_{t-1}\right]\\
=&{{\mathbb{E}}}_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}},a\sim p_m(\cdot|x)}\left[f^*(x,\pi_{f^*}(x))-f^*(x,a)\right]\\=&{{\mathbb{E}}}_x\left[\sum_{a\in{{\mathcal{A}}}}p_m(a|x)\left(f^*(x,\pi_{f^*}(x))-f^*(x,a)\right)\right]\\
=&{{\mathbb{E}}}_x\left[\sum_{a\in{{\mathcal{A}}}}\sum_{\pi\in\Psi}{\mathbb{I}}\{\pi(x)=a\}Q_m(\pi)\left(f^*(x,\pi_{f^*}(x))-f^*(x_t,\pi(x))\right)\right]\\
=&\sum_{\pi\in\Psi}Q_m(\pi){{\mathbb{E}}}_x\left[\sum_{a\in{{\mathcal{A}}}}{\mathbb{I}}\{\pi(x)=a\}\left(f^*(x_t,\pi_{f^*}(x))-f^*(x,\pi(x))\right)\right]\\
=&\sum_{\pi\in\Psi}Q_m(\pi){{\mathbb{E}}}_x\left[f^*(x_t,\pi_{f^*}(x))-f^*(x,\pi(x))\right]\\
=&\sum_{\pi\in\Psi}Q_m(\pi){{\mathrm{Reg}}}(\pi).\end{aligned}$$

Lemma \[lm:op1\] states another key property of $Q_m(\cdot)$. It says that $Q_m$ controls its predicted implicit regret (relative to the greedy policy based on $\widehat{f}_m$) within $K/\gamma_m$. Note that the controlled error $K/\gamma_m$ is gradually shrinking as the algorithm finishes more epochs.

\[lm:op1\]Fix any epoch $m\in{\mathbb{N}}$, for all round $t$ in epoch $m$, we have $$\sum_{\pi\in\Psi}Q_m(\pi){\widehat{\mathrm{Reg}}}_{t}(\pi)\le\frac{K}{\gamma_m}.$$

We have $$\begin{aligned}
    \sum_{\pi\in\Psi}Q_{m}(\pi){\widehat{\mathrm{Reg}}}_{t}(\pi)&=\sum_{\pi\in\Psi}Q_m(\pi){{\mathbb{E}}}_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}}\left[\widehat{f}_{m}(x,\widehat{a}_m(x))-\widehat{f}_m(x,\pi(x))\right]\\
    &=E_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}}\left[\sum_{\pi\in\Psi}Q_m(\pi)\left(\widehat{f}_{m}(x,\widehat{a}_m(x))-\widehat{f}_m(x,\pi(x))\right)\right]\\
    &=E_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}}\left[\sum_{a\in{{\mathcal{A}}}}\sum_{\pi\in\Psi}{\mathbb{I}}\{\pi(x)=a\}Q_m(\pi)\left(\widehat{f}_{m}(x,\widehat{a}_m(x))-\widehat{f}_m(x,a)\right)\right]\\
    &=E_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}}\left[\sum_{a\in{{\mathcal{A}}}}p_m(a|x)\left(\widehat{f}_{m}(x,\widehat{a}_m(x))-\widehat{f}_m(x,a)\right)\right].\end{aligned}$$ Given any context $x\in{{\mathcal{X}}}$, $$\sum_{a\in{{\mathcal{A}}}}p_m(a|x)\left(\widehat{f}_{m}(x,\widehat{a}_m(x))-\widehat{f}_m(x,a)\right)=\sum_{a\ne\widehat{a}_m(x)}\frac{\widehat{f}_{m}(x,\widehat{a}_m(x))-\widehat{f}_m(x,a)}{K+\gamma_m\left(\widehat{f}_{m}(x,\widehat{a}_m(x))-\widehat{f}_m(x,a)\right)}\le\frac{K-1}{\gamma_m}.$$ Lemma \[lm:op1\] follows immediately.

Lemma \[lm:op2\] states another key per-epoch property of our algorithm. For any deterministic policy $\pi\in\Psi$, the quantity $V(p_m,\pi)={{\mathbb{E}}}_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}}\left[{\frac{1}{p_m(\pi(x)|x)}}\right]$ is the expected inverse probability that the algorithm’s decision generated by $p_m$ (i.e., the decision generated by the randomized policy $Q_m$) is the same as the decision generated by the deterministic policy $\pi$, over the randomization of context $x$. This can be intuitively understood as a measure of the “decisional divergence” between the randomized policy $Q_m$ and the deterministic policy $\pi$. Lemma \[lm:op2\] states that this divergence can be bounded by the predicted implicit regret of policy $\pi$.

\[lm:op2\]Fix any epoch $m\in{\mathbb{N}}$, for all round $t$ in epoch $m$, for all policy $\pi\in\Psi$, $$V(p_m,\pi)\le K+\gamma_m{\widehat{\mathrm{Reg}}}_{t}(\pi).$$

For any policy $\pi\in\Psi$, given any context $x\in{{\mathcal{X}}}$, $$\frac{1}{p_m(\pi(x)|x)}\begin{cases}=K+\gamma_m\left(\widehat{f}_{m}(x,\widehat{a}_m(x))-\widehat{f}_m(x,\pi(x))\right),&\text{if }\pi(x)\ne\widehat{a}_m(x);\\
\le \frac{1}{1/K}=K=K+\gamma_m\left(\widehat{f}_{m}(x,\widehat{a}_m(x))-\widehat{f}_m(x,\pi(x))\right),&\text{if }\pi(x)=\widehat{a}_m(x).
\end{cases}$$ Thus $$V(p_m,\pi)={{\mathbb{E}}}_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}}\left[\frac{1}{p_m(\pi(x)|x)}\right]\le K+\gamma_m{{\mathbb{E}}}_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}}\left[\widehat{f}_{m}(x,\widehat{a}_m(x))-\widehat{f}_m(x,\pi(x))\right]=K+\gamma_m{\widehat{\mathrm{Reg}}}_t(\pi)$$ for all round $t$ in epoch $m$.

Bounding the Prediction Error of Implicit Rewards
-------------------------------------------------

Lemma \[lm:reward-estimates\] relates the prediction error of the implicit reward of any policy $\pi$ at round $t$ to the value of ${{\mathcal{V}}}_t(\pi)$.

\[lm:reward-estimates\] Assume that ${{\mathcal{E}}}$ holds. For any round $t>\tau_1$, for any $\pi\in\Psi$, $$|{\widehat{\mathcal{R}}}_t(\pi)-{{\mathcal{R}}}(\pi)|\le15\sqrt{{{\mathcal{V}}}_t(\pi)}\sqrt{\frac{\log\left({|{{\mathcal{F}}}|\tau_{m(t)-1}}/{\delta}\right)}{\tau_{m(t)-1}}}\le\frac{\sqrt{{{\mathcal{V}}}_t(\pi)}\sqrt{K}}{2\gamma_{m(t)}}.$$

Fix any policy $\pi\in\Psi$, and any round $t>\tau_1$. Since ${{\mathcal{E}}}$ holds, we have $$\sum_{s=1}^{\tau_{m(t)-1}}{{\mathbb{E}}}_{x_s,a_s}\left[(\widehat{f}_{m(t)}(x_s,a_s)-f^*(x_s,a_s))^2|\Upsilon_{s-1}\right]\le 225\log\left(\frac{|{{\mathcal{F}}}|\tau_{m(t)-1}}{\delta}\right).$$ By the definitions of ${\widehat{\mathcal{R}}}_t(\pi)$ and ${{\mathcal{R}}}(\pi)$, we have $${\widehat{\mathcal{R}}}_t(\pi)-{{\mathcal{R}}}(\pi)={{\mathbb{E}}}_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}}\left[\widehat{f}_{m(t)}(x,\pi(x))-f^*(x,\pi(x))\right].$$ Given a context $x$, define $$\Delta_x=\widehat{f}_{m(t)}(x,\pi(x))-f^*(x,\pi(x)),$$ then ${\widehat{\mathcal{R}}}_t(\pi)-{{\mathcal{R}}}(\pi)={{\mathbb{E}}}_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}}[\Delta_x]$. For all $s=1,2,\dots,\tau_{m(t)-1}$, we have $$\begin{aligned}
{{\mathbb{E}}}_{a_s|x_s}\left[\left(\widehat{f}_{m(t)}(x_s,a_s)-f^*(x_s,a_s)\right)^2|\Upsilon_{s-1}\right]=&\sum_{a\in{{\mathcal{A}}}}p_{m(s)}(a|x_s)\left(\widehat{f}_{m(t)}(x_s,a)-f^*(x_s,a)\right)^2\notag\\\ge&p_{m(s)}(\pi(x_s)|x_s)\left(\widehat{f}_{m(t)}(x_s,\pi(x_s))-f^*(x_s,\pi(x_s))\right)^2\notag\\=&p_{m(s)}(\pi(x_s)|x_s)\left(\Delta_{x_s}\right)^2.\label{eq:reward-estimation}\end{aligned}$$ Thus we have $$\begin{aligned}
&{{\mathcal{V}}}_t(\pi)\cdot225\log\left({|{{\mathcal{F}}}|\tau_{m(t)-1}}/{\delta}\right)\\
\ge&{{\mathcal{V}}}_t(\pi)\sum_{s=1}^{\tau_{m(t)-1}}{{\mathbb{E}}}_{x_s,a_s}\left[(\widehat{f}_{m(t)}(x_s,a_s)-f^*(x_s,a_s))^2|\Upsilon_{s-1}\right]\\
\ge&\sum_{s=1}^{\tau_{m(t)-1}}V(p_{m(s)},\pi){{\mathbb{E}}}_{x_s,a_s}\left[(\widehat{f}_{m(t)}(x_s,a_s)-f^*(x_s,a_s))^2|\Upsilon_{s-1}\right]\\
    =&\sum_{s=1}^{\tau_{m(t)-1}}{{\mathbb{E}}}_{x_s}\left[\frac{1}{p_{m(s)}(\pi(x_s)|x_s)}\right]{{\mathbb{E}}}_{x_s}{{\mathbb{E}}}_{a_s|x_s}\left[\left(\widehat{f}_{m(t)}(x_s,a_s)-f^*(x_s,a_s)\right)^2|\Upsilon_{s-1}\right]\\
    \ge&\sum_{s=1}^{\tau_{m(t)-1}}\left({{\mathbb{E}}}_{x_s}\left[\sqrt{\frac{1}{p_{m(s)}(\pi(x_s)|x_s)}{{\mathbb{E}}}_{a_s|x_s}\left[\left(\widehat{f}_{m(t)}(x_s,a_s)-f^*(x_s,a_s)\right)^2|\Upsilon_{s-1}\right]}\right]\right)^2\\
    \ge&\sum_{s=1}^{\tau_{m(t)-1}}\left({{\mathbb{E}}}_{x_s}\left[\sqrt{\frac{1}{p_{m(s)}(\pi(x_s)|x_s)}p_{m(s)}(\pi(x_s)|x_s)\left(\Delta_{x_s}\right)^2}~\right]\right)^2\\
    =&\sum_{s=1}^{\tau_{m(t)-1}}\left({{\mathbb{E}}}_{x_s}\left[|\Delta_{x_s}|\right]\right)^2\ge\sum_{s=1}^{\tau_{m(t)-1}}|{\widehat{\mathcal{R}}}_t(\pi)-{{\mathcal{R}}}(\pi)|^2=\tau_{m(t)-1}|{\widehat{\mathcal{R}}}_t(\pi)-{{\mathcal{R}}}(\pi)|^2,\end{aligned}$$ where the first inequality follows from the definitions of ${{\mathcal{E}}}$, the second inequality follows from the definition of ${{\mathcal{V}}}_t(\pi)$, the third inequality follows from the Cauchy-Schwarz inequality, the fourth inequality follows from (\[eq:reward-estimation\]), and the fifth inequality follows from the convexity of the $\ell_1$ norm. From the above inequality we obtain Lemma \[lm:reward-estimates\].

Bounding the Prediction Error of Implicit Regret
------------------------------------------------

Lemma \[lm:regret-estimates\] establishes an important relationship between the predicted implicit regret and the true implicit regret of any policy $\pi$ at round $t$. This lemma ensures that the predicted implicit regret of “good policies” are becoming more and more accurate, while the predicted implicit regret of “bad policies” do not need to have such property.

\[lm:regret-estimates\] Assume that ${{\mathcal{E}}}$ holds. Let $c_0:=5.15$. For all epochs $m\in{\mathbb{N}}$, all rounds $t$ in epoch $m$, and all policies $\pi\in\Psi$, $${{\mathrm{Reg}}}(\pi)\le 2{\widehat{\mathrm{Reg}}}_t(\pi)+c_0K/\gamma_{m},$$ $${\widehat{\mathrm{Reg}}}_t(\pi)\le 2{{\mathrm{Reg}}}(\pi)+c_0K/\gamma_{m}.$$

We prove Lemma \[lm:regret-estimates\] via induction on $m$. We first consider the base case where $m=1$ and $1\le t\le \tau_1$. In this case, since $\gamma_1=1$, we know that $\forall\pi\in\Psi$, $${{\mathrm{Reg}}}(\pi)\le 1\le c_0 K/\gamma_1,$$ $${\widehat{\mathrm{Reg}}}_t(\pi)\le1\le c_0K/\gamma_1.$$ Thus the claim holds in the base case.

For the inductive step, fix some epoch $m>1$. We assume that for all epochs $m'<m$, all rounds $t'$ in epoch $m'$, and all $\pi\in\Psi$, $$\label{eq:ind1}
{{\mathrm{Reg}}}(\pi)\le 2{\widehat{\mathrm{Reg}}}_{t'}(\pi)+c_0K/\gamma_{m'},$$ $$\label{eq:ind2}
{\widehat{\mathrm{Reg}}}_{t'}(\pi)\le 2{{\mathrm{Reg}}}(\pi)+c_0K/\gamma_{m'}.$$

We first show that for all rounds $t$ in epoch $m$ and all $\pi\in\Psi$, $${{\mathrm{Reg}}}(\pi)\le 2{\widehat{\mathrm{Reg}}}_{t}(\pi)+c_0K/\gamma_{m}.$$ We have $$\begin{aligned}
\label{eq:ind-dif}
{{\mathrm{Reg}}}(\pi)-{\widehat{\mathrm{Reg}}}_t(\pi)&=({{\mathcal{R}}}(\pi_{f^*})-{{\mathcal{R}}}(\pi))-({\widehat{\mathcal{R}}}_t(\pi_{\widehat{f}_{m}})-{\widehat{\mathcal{R}}}_t(\pi))\notag\\
&\le({{\mathcal{R}}}(\pi_{f^*})-{{\mathcal{R}}}(\pi))-({\widehat{\mathcal{R}}}_t(\pi_{f^*})-{\widehat{\mathcal{R}}}_t(\pi))\notag\\
&\le |{\widehat{\mathcal{R}}}_t(\pi)-{{\mathcal{R}}}(\pi)|+|{\widehat{\mathcal{R}}}_t(\pi_{f^*})-{{\mathcal{R}}}(\pi_{f^*})|\notag\\
&\le {\frac{\sqrt{{{\mathcal{V}}}_t(\pi)}\sqrt{K}}{2\gamma_{m}}}+\frac{\sqrt{{{\mathcal{V}}}_t(\pi_{f^*})}\sqrt{K}}{2\gamma_{m}}\notag\\
&\le\frac{{{\mathcal{V}}}_t(\pi)}{5\gamma_{m}}+\frac{{{\mathcal{V}}}_t(\pi_{f^*})}{5\gamma_{m}}+\frac{5K}{8\gamma_{m}}\end{aligned}$$ where the first inequality is by the optimality of $\pi_{\widehat{f}_{m}}$ for ${\widehat{\mathcal{R}}}_t(\cdot)$, the second inequality is by the triangle inequality, the third inequality is by Lemma \[lm:reward-estimates\], and the fourth inequality is by the AM-GM inequality. By the definitions of ${{\mathcal{V}}}_t(\pi),{{\mathcal{V}}}_t(\pi_{f^*})$ and Lemma \[lm:op2\], there exist epochs $i,j< m$ such that $${{\mathcal{V}}}_t(\pi)=V(p_i,\pi)={{\mathbb{E}}}_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}}\left[\frac{1}{p_i(\pi(x)|x)}\right]\le K+\gamma_{i}{\widehat{\mathrm{Reg}}}_{\tau_{i}}(\pi),$$ $${{\mathcal{V}}}_t(\pi_{f^*})=V(p_j,\pi_{f^*})={{\mathbb{E}}}_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}}\left[\frac{1}{p_j(\pi_{f^*}(x)|x)}\right]\le K+\gamma_{j}{\widehat{\mathrm{Reg}}}_{\tau_j}(\pi_{f^*}).$$ Combining the above two inequalities with (\[eq:ind2\]), we have $$\begin{aligned}
\label{eq:ind3}
\frac{{{\mathcal{V}}}_t(\pi)}{5\gamma_{m}}\le \frac{K+\gamma_i{\widehat{\mathrm{Reg}}}_{\tau_i}(\pi)}{5\gamma_{m}}\le \frac{K+\gamma_{i}(2{{\mathrm{Reg}}}(\pi)+c_0K/\gamma_{i})}{5\gamma_{m}}\le\frac{(1+c_0)K}{5\gamma_{m}}+\frac{2}{5}{{\mathrm{Reg}}}(\pi),\end{aligned}$$ $$\begin{aligned}
\label{eq:ind4}
\frac{{{\mathcal{V}}}_t(\pi_{f^*})}{5\gamma_{m}}\le \frac{K+\gamma_j{\widehat{\mathrm{Reg}}}_{\tau_j}(\pi_{f^*})}{5\gamma_{m}}\le \frac{K+\gamma_{j}(2{{\mathrm{Reg}}}(\pi_{f^*})+c_0K/\gamma_{j})}{5\gamma_{m}}=\frac{(1+c_0)K}{5\gamma_{m}},\end{aligned}$$ where the last inequality in (\[eq:ind3\]) follows from $\gamma_i\le\gamma_m$ and the last inequality in (\[eq:ind4\]) follows from ${{\mathrm{Reg}}}(\pi_{f^*})=0$. Combining (\[eq:ind-dif\]), (\[eq:ind3\]) and (\[eq:ind4\]), we have $$\label{eq:ind5}
{{\mathrm{Reg}}}(\pi)\le\frac{5}{3}{\widehat{\mathrm{Reg}}}_t(\pi)+\frac{2c_0K}{3\gamma_{m}}+\frac{1.71K}{\gamma_{m}}\le 2{\widehat{\mathrm{Reg}}}_t(\pi)+\frac{c_0K}{\gamma_{m}}.$$

We then show that for all rounds $t$ in epoch $m$ and all $\pi\in\Psi$, $${\widehat{\mathrm{Reg}}}_t(\pi)\le 2{{\mathrm{Reg}}}_{t}(\pi)+c_0K/\gamma_{m}.$$ Similar to (\[eq:ind-dif\]), we have $$\begin{aligned}
\label{eq:ind-dif'}
{\widehat{\mathrm{Reg}}}_t(\pi)-{{\mathrm{Reg}}}(\pi)&=({\widehat{\mathcal{R}}}(\pi_{\widehat{f}_{m}})-{\widehat{\mathcal{R}}}_t(\pi))-({{\mathcal{R}}}(\pi_{f^*})-{{\mathcal{R}}}(\pi))\notag\\
&\le({\widehat{\mathcal{R}}}_t(\pi_{\widehat{f}_{m}})-{\widehat{\mathcal{R}}}_t(\pi))-({{\mathcal{R}}}(\pi_{\pi_{\widehat{f}_{m}}})-{{\mathcal{R}}}(\pi))\notag\\
&\le |{\widehat{\mathcal{R}}}_t(\pi)-{{\mathcal{R}}}(\pi)|+|{\widehat{\mathcal{R}}}_t(\pi_{\widehat{f}_{m}})-{{\mathcal{R}}}(\pi_{\widehat{f}_{m}})|\notag\\
&\le {\frac{\sqrt{{{\mathcal{V}}}_t(\pi)}\sqrt{K}}{\gamma_{m}}}+\frac{\sqrt{{{\mathcal{V}}}_t(\pi_{\widehat{f}_{m}})}\sqrt{K}}{\gamma_{m}}\notag\\
&\le\frac{{{\mathcal{V}}}_t(\pi)}{5\gamma_{m}}+\frac{{{\mathcal{V}}}_t(\pi_{\widehat{f}_{m}})}{5\gamma_{m}}+\frac{5K}{8\gamma_{m}}.\end{aligned}$$ By the definition of ${{\mathcal{V}}}_t(\pi_{\widehat{f}_m})$ and Lemma \[lm:op2\], there exist epoch $l< m$ such that $${{\mathcal{V}}}_t(\pi_{\widehat{f}_m})=V(p_l,\pi_{\widehat{f}_m})={{\mathbb{E}}}_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}}\left[\frac{1}{p_l(\pi_{\widehat{f}_m}|x)}\right]\le K+\gamma_{l}{\widehat{\mathrm{Reg}}}_{\tau_{l}}(\pi_{\widehat{f}_m}).$$ Using (\[eq:ind2\]), $\gamma_l\le\gamma_{m}$, (\[eq:ind5\]) and ${\widehat{\mathrm{Reg}}}_{t}(\pi_{\widehat{f}_m})=0$, we have $$\begin{aligned}
\label{eq:ind6}
\frac{{{\mathcal{V}}}_t(\pi_{\widehat{f}_m})}{5\gamma_{m}}&\le \frac{K+\gamma_l{\widehat{\mathrm{Reg}}}_{\tau_l}(\pi_{\widehat{f}_m})}{5\gamma_{m}}\le \frac{K+\gamma_{l}(2{{\mathrm{Reg}}}(\pi_{\widehat{f}_m})+c_0K/\gamma_{l})}{5\gamma_{m}}\le\frac{(1+c_0)K}{5\gamma_{m}}+\frac{2}{5}{{\mathrm{Reg}}}(\pi_{\widehat{f}_m})\notag\\
&\le\frac{(1+c_0)K}{5\gamma_{m}}+\frac{2}{5}\left({\widehat{\mathrm{Reg}}}_t(\pi_{\widehat{f}_m})+\frac{c_0K}{\gamma_{m}}\right)=\frac{(1+3c_0)K}{5\gamma_{m}}.\end{aligned}$$ Combining (\[eq:ind3\]), (\[eq:ind-dif’\]) and (\[eq:ind6\]), we have $$\begin{aligned}
    {\widehat{\mathrm{Reg}}}_t(\pi)\le\frac{7}{5}{{\mathrm{Reg}}}(\pi)+\frac{4c_0K}{5\gamma_{m}}+\frac{1.03}{\gamma_{m}}\le{{\mathrm{Reg}}}(\pi)+\frac{c_0K}{\gamma_{m}}.\end{aligned}$$ Thus we complete the inductive step, and the claim proves to be true for all $m\in{\mathbb{N}}$.

Bounding the True Regret
------------------------

\[lm:true-reg\] Assume that ${{\mathcal{E}}}$ holds. For every epoch $m\in{\mathbb{N}}$, $$\sum_{\pi\in\Psi}Q_m(\pi){{\mathrm{Reg}}}(\pi)\le7.15K/\gamma_m.$$

Fix any epoch $m\in{\mathbb{N}}$. Since $\tau_{m-1}+1$ belongs to epoch $m$, we have $$\begin{aligned}
    \sum_{\pi\in\Pi}Q_m(\pi){{\mathrm{Reg}}}(\pi)&\le\sum_{\pi\in\Pi}Q_m(\pi)\left(2{{\widehat{\mathrm{Reg}}}}_{\tau_{m-1}+1}(\pi)+\frac{c_0K}{\gamma_{m}}\right)\\
    &=2\sum_{\pi\in\Pi}Q_m(\pi){{\widehat{\mathrm{Reg}}}}_{\tau_{m-1}+1}(\pi)+\frac{c_0K}{\gamma_m}\\
    &\le\frac{(2+c_0)K}{\gamma_m},\end{aligned}$$ where the first inequality follows from Lemma \[lm:regret-estimates\], the second inequality follows from Lemma $\ref{lm:op1}$. We then take in $c_0=5.15$.

\[lm:final\] Consider an epoch schedule such that $\gamma_{m}\le2\gamma_{m-1}$ for $m>1$ and $\gamma_1=O(1)$. For any $T\in{\mathbb{N}}$, with probability at least $1-\delta$, the regret after $T$ rounds is at most $$608.5 \sqrt{KT\log(|{{\mathcal{F}}}|T/\delta)}+\sqrt{8T\log(2/\delta)}+\tau_1.$$

Fix $T\in{\mathbb{N}}$. For each round $t\in\{1,\dots,T\}$, define $M_t:=r_t(\pi_{f^*})-r_t(a_t)-\sum_{\pi\in\Psi}Q_{m(t)}(\pi){{\mathrm{Reg}}}(\pi)$. By Lemma \[lm:equi\] we have $${{\mathbb{E}}}_{x_t,r_t,a_t}\left[r_t(\pi_{f^*})-r_t(a_t)|\Upsilon_{t-1}\right]=\sum_{\pi\in\Psi}Q_{m(t)}(\pi){{\mathrm{Reg}}}(\pi),~~~{{\mathbb{E}}}_{x_t,r_t,a_t}[M_t|\Upsilon_{t-1}]=0,$$ Since $|M_t|\le 2$, $M_t$ is a martingale difference sequence. By Azuma’s inequality, $$\label{eq:net}
\sum_{t=1}^T M_t\le2\sqrt{2T\log(2/\delta)}$$ with probability at least $1-{\delta}/{2}$. By Lemma \[lm:ag12-2\], with probability at least $1-\delta/2$, the event ${{\mathcal{E}}}$ holds. By a union bound, with probability at least $1-\delta$, the event ${{\mathcal{E}}}$ holds and $$\begin{aligned}
\sum_{t=1}^T\left(r_t(\pi_{f^*})-r_t(a_t)\right)&\le\sum_{t=1}^T\sum_{\pi\in\Psi}Q_{m(t)}(\pi){{\mathrm{Reg}}}(\pi)+\sqrt{8T\log(2/\delta)}\\
&\le\sum_{t=\tau_1+1}^{T}7.15K/\gamma_{m(t)}+\tau_1+\sqrt{8T\log(2/\delta)}\\
&=215\sum_{m=2}^{m(T)}\sqrt{\frac{K\log(|{{\mathcal{F}}}|\tau_{m-1}/\delta)}{\tau_{m-1}}}(\tau_m-\tau_{m-1})+\tau_1+\sqrt{8T\log(2/\delta)}\\
&=215\sqrt{K\log(|{{\mathcal{F}}}|\tau_{m-1}/\delta)}\sum_{m=2}^{m(T)}\frac{\tau_m-\tau_{m-1}}{\sqrt{\tau_{m-1}}}+\sqrt{8T\log(2/\delta)}+\tau_1\\
&\le215\sqrt{K\log(|{{\mathcal{F}}}|T/\delta)}\sum_{m=2}^{m(T)}\int_{\tau_{m-1}}^{\tau_m}\frac{dx}{\sqrt{x}}+\sqrt{8T\log(2/\delta)}+\tau_1\\
&=215\sqrt{K\log(|{{\mathcal{F}}}|T/\delta)}\int_{\tau_{1}}^{\tau_{m(T)}}\frac{dx}{\sqrt{x}}+\sqrt{8T\log(2/\delta)}+\tau_1\\
&=430\sqrt{\tau_{m(T
)}K\log(|{{\mathcal{F}}}|T/\delta)}+\sqrt{8T\log(2/\delta)}+\tau_1\\
&\le608.5 \sqrt{KT\log(|{{\mathcal{F}}}|T/\delta)}+\sqrt{8T\log(2/\delta)}+\tau_1,\end{aligned}$$ where the first inequality follows from (\[eq:net\]), the second inequality follows from Lemma (\[lm:true-reg\]), the third inequality follows from an integral bound, and the fourth inequality follows from $\tau_{m(T)}\le2\tau_{m(T)-1}<2T$.

Lemma \[lm:final\] directly leads to Theorem \[thm:finite\]. We thus finish our proof of Theorem \[thm:finite\].

We also provide a proof of Corollary \[cor:finite\] below. For any $T>1000$, consider an epoch schedule $\tau_m=\left\lceil T^{1-2^{-m}}\right\rceil$, $\forall m\in{\mathbb{N}}$.

We note that Lemma \[lm:ag12-1\] to Lemma \[lm:true-reg\] still hold, as they do not rely on any properties of the epoch schedule. For Lemma \[lm:final\], all the arguments up to equation (\[eq:net\]) still hold. Therefore, we only need to re-analyze the last block of equations in the proof of Lemma \[lm:final\]. We do this below. $$\begin{aligned}
\sum_{t=1}^T\left(r_t(\pi_{f^*})-r_t(a_t)\right)&\le\sum_{t=1}^T\sum_{\pi\in\Psi}Q_{m(t)}(\pi){{\mathrm{Reg}}}(\pi)+\sqrt{8T\log(2/\delta)}\\
&\le\sum_{t=\tau_1+1}^{T}7.15K/\gamma_{m(t)}+\tau_1+\sqrt{8T\log(2/\delta)}\\
&=215\sum_{m=2}^{m(T)}\sqrt{\frac{K\log(|{{\mathcal{F}}}|\tau_{m-1}/\delta)}{\tau_{m-1}}}(\tau_m-\tau_{m-1})+\tau_1+\sqrt{8T\log(2/\delta)}\\
&=215\sqrt{K\log(|{{\mathcal{F}}}|\tau_{m-1}/\delta)}\sum_{m=2}^{m(T)}\frac{\tau_m-\tau_{m-1}}{\sqrt{\tau_{m-1}}}+\sqrt{8T\log(2/\delta)}+\tau_1\\
&\le 215\sqrt{K\log(|{{\mathcal{F}}}|\tau_{m-1}/\delta)}\sum_{m=2}^{m(T)}\frac{\tau_m}{\sqrt{\tau_{m-1}}}+\sqrt{8T\log(2/\delta)}+\tau_1\\
&\le 215\sqrt{K\log(|{{\mathcal{F}}}|\tau_{m-1}/\delta)}\left(\sqrt{T}+\frac{1}{\sqrt{T}}\right)(m(T)-1)+\sqrt{8T\log(2/\delta)}+\sqrt{T}+1,\end{aligned}$$ where the last inequality follows from $$\frac{\tau_m}{\sqrt{\tau_{m-1}}}\le\frac{T^{1-2^{-m}}+1}{T^{\frac{1}{2}(1-2^{-m+1})}}=\sqrt{T}+\frac{1}{\sqrt{T}},~~~\forall m>1$$ and $\tau_1\le\sqrt{T}+1$. Corollary \[cor:finite\] follows from the fact that $m(T)=O(\log\log T)$.

Proof of Theorem \[thm:inf\] {#app:thm2}
============================

\[lm:oracle\]Consider an epoch schedule such that $\tau_m\ge2^m$ for $m\in{\mathbb{N}}$. For all $m\ge2$, with probability at least $1-{\delta}/(2\tau_{m-1})$, we have: $$\begin{aligned}
\forall t\in\{\tau_{m-2}+1,\cdots,\tau_{m-1}\},~~~~&{{\mathbb{E}}}_{x_t,a_t}\left[(\widehat{f}_{m}(x_t,a_t)-f^*(x_t,a_t))^2|\Upsilon_{t-1}\right]\\
=&{{\mathbb{E}}}_{x_t,r_t,a_t}\left[(\widehat{f}_{m}(x_t,a_t)-r_t(a_t))^2-(f^*(x_t,a_t)-r_t(a_t))^2|\Upsilon_{t-1}\right]\\\le& \xi_{{{\mathcal{F}}},\delta/(2\tau_{m-1})}(\tau_{m-1}-\tau_{m-2}).\end{aligned}$$ Therefore (by a union bound), the following event $\Gamma$ holds with probability at least $1-\delta/2$: $$\label{eq:clean-event-inf}
\Gamma:=\left\{\forall t>\tau_1,~~{{\mathbb{E}}}_{x_t,a_t}\left[(\widehat{f}_{m}(x_t,a_t)-f^*(x_t,a_t))^2|\Upsilon_{t-1}\right]\le \xi_{{{\mathcal{F}}},\delta/(2\tau_{m-1})}(\tau_{m-1}-\tau_{m-2})\right\}.$$

By the specification of Algorithm \[alg:falcon+\], we have $\forall t\in\{\tau_{m-2}+1,\cdots,\tau_{m-1}\}$, $$\begin{aligned}
&{{\mathbb{E}}}_{x_t,r_t,a_t}\left[(\widehat{f}_{m}(x_t,a_t)-r_t(a_t))^2-(f^*(x_t,a_t)-r_t(a_t))^2|\Upsilon_{t-1}\right]\\
=&{{\mathbb{E}}}_{x_t,r_t,a_t}\left[(\widehat{f}_{m}(x_t,a_t)-r_t(a_t))^2-(f^*(x_t,a_t)-r_t(a_t))^2|\gamma_m,\widehat{f}_{m}\right].\end{aligned}$$ The rest of the lemma simply follows from the definition of estimation error / excess risk.

We note that Lemma \[lm:map\] to Lemma \[lm:op2\] still hold for Algorithm \[alg:falcon+\].

\[lm:reward-estimates-inf\] Assume that $\Gamma$ holds. For any round $t>\tau_1$, for any $\pi\in\Psi$, $$|{\widehat{\mathcal{R}}}_t(\pi)-{{\mathcal{R}}}(\pi)|\le \sqrt{V(p_{m(t)-1},\pi)}\sqrt{\xi_{{{\mathcal{F}}},\delta/(2\tau_{m-1})}(\tau_{m-1}-\tau_{m-2})}=\sqrt{V(p_{m(t)-1},\pi)}\frac{\sqrt{K}}{2\gamma_m}.$$

Fix any policy $\pi\in\Psi$, and any round $t>\tau_1$. Since $\Gamma$ holds, we have $${{\mathbb{E}}}_{x_s,a_s}\left[(\widehat{f}_{m(t)}(x_s,a_s)-f^*(x_s,a_s))^2|\Upsilon_{s-1}\right]\le \xi_{{{\mathcal{F}}},\delta/(2\tau_{m-1})}(\tau_{m-1}-\tau_{m-2}).$$ By the definitions of ${\widehat{\mathcal{R}}}_t(\pi)$ and ${{\mathcal{R}}}(\pi)$, we have $${\widehat{\mathcal{R}}}_t(\pi)-{{\mathcal{R}}}(\pi)={{\mathbb{E}}}_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}}\left[\widehat{f}_{m(t)}(x,\pi(x))-f^*(x,\pi(x))\right].$$ Given a context $x$, define $$\Delta_x=\widehat{f}_{m(t)}(x,\pi(x))-f^*(x,\pi(x)),$$ then ${\widehat{\mathcal{R}}}_t(\pi)-{{\mathcal{R}}}(\pi)={{\mathbb{E}}}_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}}[\Delta_x]$. For all $s=\tau_{m(t)-2}+1,\dots,\tau_{m(t)-1}$, we have $$\begin{aligned}
{{\mathbb{E}}}_{a_s|x_s}\left[\left(\widehat{f}_{m(t)}(x_s,a_s)-f^*(x_s,a_s)\right)^2|\Upsilon_{s-1}\right]=&\sum_{a\in{{\mathcal{A}}}}p_{m(t)-1}(a|x_s)\left(\widehat{f}_{m(t)}(x_s,a)-f^*(x_s,a)\right)^2\notag\\\ge&p_{m(t)-1}(\pi(x_s)|x_s)\left(\widehat{f}_{m(t)}(x_s,\pi(x_s))-f^*(x_s,\pi(x_s))\right)^2\notag\\=&p_{m(t)-1}(\pi(x_s)|x_s)\left(\Delta_{x_s}\right)^2.\label{eq:reward-estimation-inf}\end{aligned}$$ Thus we have $$\begin{aligned}
&V(p_{m(t)-1},\pi)\xi_{{{\mathcal{F}}},\delta/(2\tau_{m-1})}(\tau_{m-1}-\tau_{m-2})\\
\ge&V(p_{m(t)-1},\pi){{\mathbb{E}}}_{x_s,a_s}\left[(\widehat{f}_{m(t)}(x_s,a_s)-f^*(x_s,a_s))^2|\Upsilon_{s-1}\right]\\
    =&{{\mathbb{E}}}_{x_s}\left[\frac{1}{p_{m(t)-1}(\pi(x_s)|x_s)}\right]{{\mathbb{E}}}_{x_s}{{\mathbb{E}}}_{a_s|x_s}\left[\left(\widehat{f}_{m(t)}(x_s,a_s)-f^*(x_s,a_s)\right)^2|\Upsilon_{s-1}\right]\\
    \ge&\left({{\mathbb{E}}}_{x_s}\left[\sqrt{\frac{1}{p_{m(t)-1}(\pi(x_s)|x_s)}{{\mathbb{E}}}_{a_s|x_s}\left[\left(\widehat{f}_{m(t)}(x_s,a_s)-f^*(x_s,a_s)\right)^2|\Upsilon_{s-1}\right]}\right]\right)^2\\
    \ge&\left({{\mathbb{E}}}_{x_s}\left[\sqrt{\frac{1}{p_{m(t)-1}(\pi(x_s)|x_s)}p_{m(t)-1}(\pi(x_s)|x_s)\left(\Delta_{x_s}\right)^2}~\right]\right)^2\\
    =&\left({{\mathbb{E}}}_{x_s}\left[|\Delta_{x_s}|\right]\right)^2\\\ge&|{\widehat{\mathcal{R}}}_t(\pi)-{{\mathcal{R}}}(\pi)|^2,\end{aligned}$$ where the first inequality follows from the definitions of $\Gamma$, the second inequality follows from the Cauchy-Schwarz inequality, the third inequality follows from (\[eq:reward-estimation-inf\]), and the fourth inequality follows from the convexity of the $\ell_1$ norm. From the above inequality we obtain Lemma \[lm:reward-estimates-inf\].

\[lm:regret-estimates-inf\] Assume that $\Gamma$ holds. Let $c_0:=5.15$. For all epochs $m\in{\mathbb{N}}$, all rounds $t$ in epoch $m$, and all policies $\pi\in\Psi$, $${{\mathrm{Reg}}}(\pi)\le 2{\widehat{\mathrm{Reg}}}_t(\pi)+c_0K/\gamma_{m},$$ $${\widehat{\mathrm{Reg}}}_t(\pi)\le 2{{\mathrm{Reg}}}(\pi)+c_0K/\gamma_{m}.$$

We prove Lemma \[lm:regret-estimates-inf\] via induction on $m$. We first consider the base case where $m=1$ and $1\le t\le \tau_1$. In this case, since $\gamma_1=1$, we know that $\forall\pi\in\Psi$, $${{\mathrm{Reg}}}(\pi)\le 1\le c_0 K/\gamma_1,$$ $${\widehat{\mathrm{Reg}}}_t(\pi)\le1\le c_0K/\gamma_1.$$ Thus the claim holds in the base case.

For the inductive step, fix some epoch $m>1$. We assume that for epoch $m-1$, all rounds $t'$ in epoch $m-1$, and all $\pi\in\Psi$, $$\label{eq:ind1-inf}
{{\mathrm{Reg}}}(\pi)\le 2{\widehat{\mathrm{Reg}}}_{t'}(\pi)+c_0K/\gamma_{m-1},$$ $$\label{eq:ind2-inf}
{\widehat{\mathrm{Reg}}}_{t'}(\pi)\le 2{{\mathrm{Reg}}}(\pi)+c_0K/\gamma_{m-1}.$$

We first show that for all rounds $t$ in epoch $m$ and all $\pi\in\Psi$, $${{\mathrm{Reg}}}(\pi)\le 2{\widehat{\mathrm{Reg}}}_{t}(\pi)+c_0K/\gamma_{m}.$$ We have $$\begin{aligned}
\label{eq:ind-dif-inf}
{{\mathrm{Reg}}}(\pi)-{\widehat{\mathrm{Reg}}}_t(\pi)&=({{\mathcal{R}}}(\pi_{f^*})-{{\mathcal{R}}}(\pi))-({\widehat{\mathcal{R}}}_t(\pi_{\widehat{f}_{m}})-{\widehat{\mathcal{R}}}_t(\pi))\notag\\
&\le({{\mathcal{R}}}(\pi_{f^*})-{{\mathcal{R}}}(\pi))-({\widehat{\mathcal{R}}}_t(\pi_{f^*})-{\widehat{\mathcal{R}}}_t(\pi))\notag\\
&\le |{\widehat{\mathcal{R}}}_t(\pi)-{{\mathcal{R}}}(\pi)|+|{\widehat{\mathcal{R}}}_t(\pi_{f^*})-{{\mathcal{R}}}(\pi_{f^*})|\notag\\
&\le {\frac{\sqrt{V(p_{m-1},\pi)}\sqrt{K}}{2\gamma_{m}}}+\frac{\sqrt{V(p_{m-1},\pi_{f^*})}\sqrt{K}}{2\gamma_{m}}\notag\\
&\le\frac{V(p_{m-1},\pi)}{5\gamma_{m}}+\frac{V(p_{m-1},\pi_{f^*})}{5\gamma_{m}}+\frac{5K}{8\gamma_{m}}\end{aligned}$$ where the first inequality is by the optimality of $\pi_{\widehat{f}_{m}}$ for ${\widehat{\mathcal{R}}}_t(\cdot)$, the second inequality is by the triangle inequality, the third inequality is by Lemma \[lm:reward-estimates-inf\], and the fourth inequality is by the AM-GM inequality. By Lemma \[lm:op2\], $$V(p_{m-1},\pi)={{\mathbb{E}}}_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}}\left[\frac{1}{p_{m-1}(\pi(x)|x)}\right]\le K+\gamma_{m-1}{\widehat{\mathrm{Reg}}}_{\tau_{m-1}}(\pi),$$ $$V(p_{m-1},\pi_{f^*})={{\mathbb{E}}}_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}}\left[\frac{1}{p_{m-1}(\pi_{f^*}(x)|x)}\right]\le K+\gamma_{m-1}{\widehat{\mathrm{Reg}}}_{\tau_{m-1}}(\pi_{f^*}).$$ Combining the above two inequalities with (\[eq:ind2-inf\]), we have $$\begin{aligned}
\label{eq:ind3-inf}
\frac{V(p_{m-1},\pi)}{5\gamma_{m}}\le \frac{K+\gamma_{m-1}{\widehat{\mathrm{Reg}}}_{\tau_{m-1}}(\pi)}{5\gamma_{m}}\le \frac{K+\gamma_{m-1}(2{{\mathrm{Reg}}}(\pi)+c_0K/\gamma_{m-1})}{5\gamma_{m}}\le\frac{(1+c_0)K}{5\gamma_{m}}+\frac{2}{5}{{\mathrm{Reg}}}(\pi),\end{aligned}$$ $$\begin{aligned}
\label{eq:ind4-inf}
\frac{V(p_{m-1},\pi_{f^*})}{5\gamma_{m}}\le \frac{K+\gamma_{m-1}{\widehat{\mathrm{Reg}}}_{\tau_{m-1}}(\pi_{f^*})}{5\gamma_{m}}\le \frac{K+\gamma_{m-1}(2{{\mathrm{Reg}}}(\pi_{f^*})+c_0K/\gamma_{m-1})}{5\gamma_{m}}=\frac{(1+c_0)K}{5\gamma_{m}},\end{aligned}$$ where the last inequality in (\[eq:ind3-inf\]) follows from $\gamma_{m-1}\le\gamma_m$ and the last inequality in (\[eq:ind4-inf\]) follows from ${{\mathrm{Reg}}}(\pi_{f^*})=0$. Combining (\[eq:ind-dif-inf\]), (\[eq:ind3-inf\]) and (\[eq:ind4-inf\]), we have $$\label{eq:ind5-inf}
{{\mathrm{Reg}}}(\pi)\le\frac{5}{3}{\widehat{\mathrm{Reg}}}_t(\pi)+\frac{2c_0K}{3\gamma_{m}}+\frac{1.71K}{\gamma_{m}}\le 2{\widehat{\mathrm{Reg}}}_t(\pi)+\frac{c_0K}{\gamma_{m}}.$$

We then show that for all rounds $t$ in epoch $m$ and all $\pi\in\Psi$, $${\widehat{\mathrm{Reg}}}_t(\pi)\le 2{{\mathrm{Reg}}}_{t}(\pi)+c_0K/\gamma_{m}.$$ Similar to (\[eq:ind-dif-inf\]), we have $$\begin{aligned}
\label{eq:ind-dif'-inf}
{\widehat{\mathrm{Reg}}}_t(\pi)-{{\mathrm{Reg}}}(\pi)&=({\widehat{\mathcal{R}}}(\pi_{\widehat{f}_{m}})-{\widehat{\mathcal{R}}}_t(\pi))-({{\mathcal{R}}}(\pi_{f^*})-{{\mathcal{R}}}(\pi))\notag\\
&\le({\widehat{\mathcal{R}}}_t(\pi_{\widehat{f}_{m}})-{\widehat{\mathcal{R}}}_t(\pi))-({{\mathcal{R}}}(\pi_{\pi_{\widehat{f}_{m}}})-{{\mathcal{R}}}(\pi))\notag\\
&\le |{\widehat{\mathcal{R}}}_t(\pi)-{{\mathcal{R}}}(\pi)|+|{\widehat{\mathcal{R}}}_t(\pi_{\widehat{f}_{m}})-{{\mathcal{R}}}(\pi_{\widehat{f}_{m}})|\notag\\
&\le {\frac{\sqrt{V(p_{m-1},\pi)}\sqrt{K}}{\gamma_{m}}}+\frac{\sqrt{V(p_{m-1},\pi_{\widehat{f}_m})}\sqrt{K}}{\gamma_{m}}\notag\\
&\le\frac{V(p_{m-1},\pi)}{5\gamma_{m}}+\frac{V(p_{m-1},\pi_{\widehat{f}_m})}{5\gamma_{m}}+\frac{5K}{8\gamma_{m}}.\end{aligned}$$ By Lemma \[lm:op2\], $$V(p_{m-1},\pi_{\widehat{f}_m})={{\mathbb{E}}}_{x\sim{{\mathcal{D}_{\mathcal{{{\mathcal{X}}}}}}}}\left[\frac{m-1}{p_l(\pi_{\widehat{f}_m}|x)}\right]\le K+\gamma_{m-1}{\widehat{\mathrm{Reg}}}_{\tau_{m-1}}(\pi_{\widehat{f}_m}).$$ Using (\[eq:ind2-inf\]), $\gamma_{m-1}\le\gamma_{m}$, (\[eq:ind5-inf\]) and ${\widehat{\mathrm{Reg}}}_{t}(\pi_{\widehat{f}_m})=0$, we have $$\begin{aligned}
\label{eq:ind6-inf}
\frac{V(p_{m-1},\pi_{\widehat{f}_m})}{5\gamma_{m}}&\le \frac{K+\gamma_{m-1}{\widehat{\mathrm{Reg}}}_{\tau_{m-1}}(\pi_{\widehat{f}_m})}{5\gamma_{m}}\le \frac{K+\gamma_{m-1}(2{{\mathrm{Reg}}}(\pi_{\widehat{f}_m})+c_0K/\gamma_{m-1})}{5\gamma_{m}}\\&\le\frac{(1+c_0)K}{5\gamma_{m}}+\frac{2}{5}{{\mathrm{Reg}}}(\pi_{\widehat{f}_m})\notag
\le\frac{(1+c_0)K}{5\gamma_{m}}+\frac{2}{5}\left({\widehat{\mathrm{Reg}}}_t(\pi_{\widehat{f}_m})+\frac{c_0K}{\gamma_{m}}\right)=\frac{(1+3c_0)K}{5\gamma_{m}}.\end{aligned}$$ Combining (\[eq:ind3-inf\]), (\[eq:ind-dif’-inf\]) and (\[eq:ind6-inf\]), we have $$\begin{aligned}
    {\widehat{\mathrm{Reg}}}_t(\pi)\le\frac{7}{5}{{\mathrm{Reg}}}(\pi)+\frac{4c_0K}{5\gamma_{m}}+\frac{1.03}{\gamma_{m}}\le{{\mathrm{Reg}}}(\pi)+\frac{c_0K}{\gamma_{m}}.\end{aligned}$$ Thus we complete the inductive step, and the claim proves to be true for all $m\in{\mathbb{N}}$.

We note that Lemma \[lm:true-reg\] still holds for Algorithm \[alg:falcon+\].

\[lm:final-inf\] Consider an epoch schedule such that $\tau_m\ge2^m$ for $m\in{\mathbb{N}}$. For any $T\in{\mathbb{N}}$, with probability at least $1-\delta$, the regret of Algorithm \[alg:falcon+\] after $T$ rounds is at most $$14.3\sqrt{K}\sum_{m=2}^{m(T)}\sqrt{\xi_{{{\mathcal{F}}},\delta/(2T)}(\tau_{m-1}-\tau_{m-2})}(\tau_m-\tau_{m-1})+\sqrt{8T\log(2/\delta)}+\tau_1.$$

Fix $T\in{\mathbb{N}}$. For each round $t\in\{1,\dots,T\}$, define $M_t:=r_t(\pi_{f^*})-r_t(a_t)-\sum_{\pi\in\Psi}Q_{m(t)}(\pi){{\mathrm{Reg}}}(\pi)$. By Lemma \[lm:equi\] we have $${{\mathbb{E}}}_{x_t,r_t,a_t}\left[r_t(\pi_{f^*})-r_t(a_t)|\Upsilon_{t-1}\right]=\sum_{\pi\in\Psi}Q_{m(t)}(\pi){{\mathrm{Reg}}}(\pi),~~~{{\mathbb{E}}}_{x_t,r_t,a_t}[M_t|\Upsilon_{t-1}]=0,$$ Since $|M_t|\le 2$, $M_t$ is a martingale difference sequence. By Azuma’s inequality, $$\label{eq:net-inf}
\sum_{t=1}^T M_t\le2\sqrt{2T\log(2/\delta)}$$ with probability at least $1-{\delta}/{2}$. By Lemma \[lm:oracle\], with probability at least $1-\delta/2$, the event $\Gamma$ holds. By a union bound, with probability at least $1-\delta$, the event $\Gamma$ holds and $$\begin{aligned}
\sum_{t=1}^T\left(r_t(\pi_{f^*})-r_t(a_t)\right)&\le\sum_{t=1}^T\sum_{\pi\in\Psi}Q_{m(t)}(\pi){{\mathrm{Reg}}}(\pi)+\sqrt{8T\log(2/\delta)}\\
&\le\sum_{t=\tau_1+1}^{T}7.15K/\gamma_{m(t)}+\tau_1+\sqrt{8T\log(2/\delta)}\\
&=14.3\sum_{m=2}^{m(T)}\sqrt{K\xi_{{{\mathcal{F}}},\delta/(2\tau_{m-1})}(\tau_{m-1}-\tau_{m-2})}(\tau_m-\tau_{m-1})+\tau_1+\sqrt{8T\log(2/\delta)}\\
&\le14.3\sqrt{K}\sum_{m=2}^{m(T)}\sqrt{\xi_{{{\mathcal{F}}},\delta/(2T)}(\tau_{m-1}-\tau_{m-2})}(\tau_m-\tau_{m-1})+\sqrt{8T\log(2/\delta)}+\tau_1,\end{aligned}$$ where the first inequality follows from (\[eq:net-inf\]), the second inequality follows from Lemma (\[lm:true-reg\]), and the last equality follows from $\tau_{m(T)-1}\le T$.

We thus finish our proof of Theorem \[thm:inf\].

[^1]: This is just for ease of presentation. If there are some (unknown) internal randomness (inside the oracle) when there are multiple optimal solutions for (\[eq:lsr\]), then we can just incorporate such randomness into the sigma field generated by the history, and all our proofs will still hold.

[^2]: While we focus on stochastic contextual bandits in the realizable setting, we would like to point out that [@agarwal2014taming] and [@foster2020beyond] have their own merits outside of this setting. The algorithm of [@agarwal2014taming] works when there is no realizability assumption. The algorithm of [@foster2020beyond] works when the contexts are chosen adversarially.

[^3]: Note that this is an “instantaneous” quantity in $[0,1]$, not a sum over multiple rounds.

[^4]: Note that in §\[sec:setting\] we have defined $\pi_f$ as the reward-maximizing policy induced by a reward function $f$, i.e., $\pi_f(x)=\arg\max_{a\in{{\mathcal{A}}}}f(x,a)$ for all $x\in{{\mathcal{X}}}$. Also note that *not all* policies in $\Psi$ can be written as $\pi_f$ for some $f\in{{\mathcal{F}}}$.

[^5]: Again, without loss of generality, we assume that $\texttt{OffReg}_{{{\mathcal{F}}}}$ always return a same predictor for two input sequences that are completely the same.
