Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective

Introduction

How can we adaptively allocate measurements to exploit problem structure in the presence of rich, high-dimensional, and potentially stateful contextual information? In this paper, we investigate this question in the contextual bandit problem and its stateful relative, the problem of reinforcement learning with rich observations.

The contextual bandit is a fundamental problem in sequential decision making. At each round, the learner receives a context, selects an action, and receives a reward; their goal is to select actions so as to maximize the total long-term reward. This model has been successfully deployed in news article recommendation (Li et al., 2010; Agarwal et al., 2016), where actions represent articles to display and rewards represent clicks, and healthcare (Tewari and Murphy, 2017; Bastani and Bayati, 2020), where actions represent treatments to prescribe and rewards represent the patient’s response. Reinforcement learning with rich observations (Krishnamurthy et al., 2016; Jiang et al., 2017) is a substantially more challenging generalization in which the learner’s actions influence the evolution of the contexts, and serves as a stylized model for reinforcement learning with function approximation.

For both settings, our aim is to develop instance-dependent algorithms that adapt to gaps between actions in the underlying reward function to obtain improved regret. In the classical (non-contextual) multi-armed bandit problem, this issue has enjoyed extensive investigation beginning with the work of Lai and Robbins (1985). Here, it is well-understood that when the mean reward function admits a constant gap between the best and second-best action, well-designed algorithms can obtain logarithmic (in $T$, the number of rounds) regret, which offers significant improvement over the worst-case minimax rate of $\sqrt{T}$. Subsequent work has developed a sharp understanding of optimal instance-dependent regret, both asymptotically and with finite samples (Burnetas and Katehakis, 1996; Garivier et al., 2016; Kaufmann et al., 2016; Lattimore, 2018; Garivier et al., 2019). Beyond the obvious appeal of lower regret, instance-dependent algorithms are particularly compelling for applications such as clinical trials—where excessive randomization may be undesirable or unethical—because they identify and eliminate suboptimal actions more quickly than algorithms that only aim for worst-case optimality.

We take the first step towards developing a similar theory for contextual bandits and reinforcement learning with general function approximation. We focus on the “realizable” or “well-specified” setting in which the learner has access to a class of regression functions $\mathcal{F}$ that is flexible enough to capture the true reward function or value function. Our aim is to develop learning-theoretic guarantees for rich, potentially nonparametric function classes that 1) scale only with the statistical capacity of the class, and 2) are efficient in terms of basic computational primitives for the class.

For contextual bandits, instance-dependent regret bounds are not well-understood. Positive results are known for simple classes of functions such as linear classes (Dani et al., 2008; Abbasi-Yadkori et al., 2011; Hao et al., 2019) or nonparametric Lipschitz/Hölder classes (Rigollet and Zeevi, 2010; Perchet and Rigollet, 2013; Hu et al., 2020). On the other hand, for arbitrary finite function classes, it is known that gap-dependent regret bounds are not possible in general (Foster and Rakhlin, 2020). One line of work develops algorithms which attain instance-dependent bounds for general classes under additional structural assumptions or distributional assumptions (Russo and Van Roy, 2013; Bietti et al., 2018; Foster et al., 2018), but it is not clear whether these assumptions are fundamental (in particular, they are not required to obtain minimax rates). For reinforcement learning, the situation is more dire: while instance-dependent rates have been explored in the finite state/action setting (Burnetas and Katehakis, 1996; Tewari and Bartlett, 2008; Ok et al., 2018; Simchowitz and Jamieson, 2019), very little is known for the general setting with high dimensional states and function approximation.

Beyond the basic issue of what instance-dependent rates can be achieved for general function classes, an important question is whether they can be achieved efficiently, using practical algorithms. A recent line of work (Foster et al., 2018; Foster and Rakhlin, 2020; Simchi-Levi and Xu, 2020; Xu and Zeevi, 2020) develops algorithms that are efficient in terms calls to an oracle for (offline/online) supervised regression. A secondary goal in this work is to develop practical instance-dependent algorithms based on this primitive.

For contextual bandits and reinforcement learning with rich observations, what properties of the function class enable us to adapt to the gap, and what are the fundamental limits?

More ambitiously, can we get the best of both worlds: Adapt to the gap and obtain the minimax rate simultaneously?

For contextual bandits, we address each of these issues. We introduce a family of new complexity measures which are both necessary (in a certain sense) and sufficient to obtain fast gap-dependent regret bounds. We introduce new oracle-efficient algorithms which adapt to the gap and to these complexity measures whenever possible, while also obtaining the minimax rate. We prove new structural results which—in conjunction with our lower bounds—tie together a number of complexity measures previously proposed in contextual bandits, reinforcement learning, and active learning and provide new insight into their role in determining the optimal instance-dependent regret. We then extend these complexity measures to reinforcement learning with function approximation and give new oracle-efficient algorithms that adapt to them. Overall, our results for RL are somewhat less complete, but we believe they suggest a number of exciting new directions for future research.

We assume that the learner has access to a class of value functions $\mathcal{F}\subset(\mathcal{X}\times\mathcal{A}\to\left[0,1\right])$ (e.g., regression trees or neural networks) that is flexible enough to model the true reward distribution. In particular, we make the following standard realizability assumption (Chu et al., 2011; Agarwal et al., 2012; Foster et al., 2018).

For each regression function $f\in\mathcal{F}$, let $\pi_{f}(x)=\operatorname\star{arg\,max}_{a\in\mathcal{A}}f(x,a)$ denote the induced policy (with ties broken arbitrarily, but consistently), and let $\Pi=\left\{\pi_{f}\mid{}f\in\mathcal{F}\right\}$ be the induced policy class. The goal of the learner is to ensure low regret to the optimal policy:

where $\pi^{\star}\vcentcolon={}\pi_{f^{\star}}$. For simplicity, we assume that $\operatorname\star{arg\,max}_{a\in\mathcal{A}}f^{\star}(x,a)$ is unique for all $x$, but our results extend when this is not the case.

Consider the simple case where $\mathcal{F}$ is finite. For general finite classes $\mathcal{F}$ under 1, the minimax rate for contextual bandits is $\Theta(\sqrt{A{}T\log\lvert\mathcal{F}\rvert})$ (Agarwal et al., 2012). The main question we investigate is to what extent this rate can be improved when the instance has a uniform gapThis is sometimes referred to as the Massart noise condition, which has been widely studied in statistical learning theory in the context of obtaining faster rates for classification. in the sense that for all $x\in\mathcal{X}$,

This is impossible in a fairly strong sense: Foster and Rakhlin (2020) show that exist function classes $\mathcal{F}$ for which any algorithm must haveFoster and Rakhlin (2020) prove this lower bound for adversarial contexts. Our Theorem 2.2 implies an analogous lower bound for stochastic contexts.

Since $\mathcal{F}$ is exponentially large for most models, polynomial dependence on $\lvert\mathcal{F}\rvert$ is unacceptable. The natural question then, and the one we address, is what structural properties of $\mathcal{F}$ allow for bounds of the form Eq. 3 that scale only logarithmically with the size of the value function class. We primarily present results on finite classes for simplicity, but our lower bounds and structural results concern infinite classes, and our algorithms make no assumption on the structure.

We show that variants of the disagreement coefficient, a key parameter in empirical process theory and active learning (Alexander, 1987; Hanneke and Yang, 2015), play a fundamental role in determining the optimal gap-dependent regret bounds for contextual bandits with rich function classes.

Our most basic results concern a parameter we call the policy disagreement coefficient,In fact, for binary actions the policy disagreement coefficient is the same as the usual disagreement coefficient from active learning (Hanneke and Yang, 2015); we adopt the name policy disagreement coefficient only to distinguish from other parameters we introduce. defined as

Informally, the policy disagreement coefficient measures how likely we are to encounter a context on which some near-optimal policy disagrees with $\pi^{\star}$. Low disagreement coefficient means that all the near-optimal policies deviate from $\pi^{\star}$ only in a small, shared region of the context space, while large disagreement coefficient means that the points on which disagreement occurs are more prevalent throughout the context space (w.r.t $\mathcal{D}$), so that many samples are required to rule out all of these policies.

We introduce a new contextual bandit algorithm, AdaCB, which adapts to the gap whenever the policy disagreement coefficient is bounded. In particular, we show the following.

with no prior knowledge of $\Delta$ or $\boldsymbol{\theta}^{\mathsf{pol}}(\Pi,\varepsilon)$.

so that AdaCB enjoys logarithmic regret. We emphasize that while Theorem 2.1 concerns finite classes, this is only a stylistic choice: AdaCB places no assumption on the structure of $\mathcal{F}$, and the analysis trivially generalizes by replacing $\log\left\lvert\mathcal{F}\right\rvert$ with standard learning-theoretic complexity measures such as the pseudodimension.

While this is certainly encouraging, it is not immediately clear whether the rate in Eq. 5 is fundamental. To this end, we prove that dependence on the disagreement coefficient is qualitatively necessary.

Theorem 2.2 shows that the regret bound Eq. 5 attained by AdaCB cannot be improved without further assumptions on $\mathcal{F}$. However, it leaves the possibility of more refined complexity measures that are tighter than $\boldsymbol{\theta}^{\mathsf{pol}}(\Pi,\varepsilon)$ for most instances, yet coincide on the construction that realizes the lower bound in Theorem 2.2. To this end, we introduce a second complexity measure, the value function disagreement coefficient, which can exploit the scale-sensitive nature of the value function class $\mathcal{F}$ to provide tighter bounds. The value function disagreement coefficient is defined as

We show that AdaCB, with a slightly different parameter configuration, can adapt to value function disagreement coefficient in a best-of-both-worlds fashion.

where $\varepsilon_{T}\propto\sqrt{\log\lvert\mathcal{F}\rvert/T}$.

We show (Theorem 2.4) that this dependence on $\boldsymbol{\theta}^{\mathsf{val}}\left(\mathcal{F},\Delta,\varepsilon\right)$ is qualitatively necessary, meaning that AdaCB is adapts near-optimally without additional assumptions.

Beyond contextual bandits, our scale-sensitive generalization of the disagreement coefficient is new to both empirical process theory and active learning to our knowledge, and may be of independent interest.

While the distribution-dependent nature of our disagreement-based upper bounds can lead to tight guarantees for benign distributions, it is natural to ask: For what classes $\Pi$ (resp. $\mathcal{F}$) can we ensure the policy (resp. value) disagreement coefficient is bounded for any distribution $\mathcal{D}$? Hanneke and Yang (2015) show that the policy disagreement coefficient is always bounded by a combinatorial parameter for $\Pi$ called the (policy) star number.In fact, the star number exactly coincides with the worst-case value of the disagreement coefficient over all possible distributions and scale parameters. An immediate consequence (via Theorem 2.1) is that AdaCB enjoys logarithmic regret even in the distribution-free setting for classes with bounded policy star number. More interestingly, we show (Theorem 2.6) that for any class $\Pi$, bounded policy star number is necessary to obtain logarithmic regret in the worst-case (with respect to both $\mathcal{D}$ and the class $\mathcal{F}$ realizing $\Pi$). Thus, we have the following characterization.

For any policy class $\Pi$, bounded policy star number is necessary and sufficient to obtain logarithmic regret.

Compared to our disagreement-based lower bounds, which rely on specially designed function classes, this lower bound holds for any policy class.

This characterization motivates us to define a scale-sensitive analogue of the star number called the value function star number. The value function star number is a new combinatorial parameter even within the broader literature on active learning and empirical process theory, and we show (Theorem 2.7) that it bounds the value function disagreement coefficient for all choices of the context distribution $\mathcal{D}$ and scale parameter $\varepsilon$. We then show (Theorem 2.8) that a weak version of the value function disagreement coefficient is necessary to obtain logarithmic regret for worst-case context distributions, leading to the following characterization.

For any value function class $\mathcal{F}$, bounded value function star number is (weakly) necessary and sufficient to obtain logarithmic regret.

The value function star number is closely related to—and in particular always upper bounded by—the (value function) eluder dimension of Russo and Van Roy (2013). The eluder dimension was introduced to prove regret bounds for the generalized UCB algorithm and Thompson sampling for contextual bandits with adversarial contexts, and more recently has been used to analyze algorithms for reinforcement learning with function approximation (Osband and Van Roy, 2014; Wen and Van Roy, 2017; Ayoub et al., 2020; Wang et al., 2020). An immediate consequence of the (disagreement coefficient)$\;\leq\;$(star number)$\;\leq\;$(eluder dimension) connection is that boundedness of the eluder dimension suffices to obtain logarithmic regret with AdaCB. Unlike the star number though, bounded eluder dimension is not required for the stochastic setting we consider. However, building on our previous lower bounds, we show (Theorem 2.9) that a weak version of the eluder dimension is necessary to obtain logarithmic regret under adversarial contexts, and give a tighter analysis of the generalized UCB algorithm to show that it attains this rate (this is not a best-of-both-worlds guarantee). This result places the eluder dimension on more solid footing and shows that while it is not required for minimax rates, it plays a fundamental role for instance-dependent rates.

The relationship between all of our complexity measures, old and new, is summarized in Fig. 1. Beyond expanding the scope of settings for which logarithmic regret is achievable, we hope our structural results and lower bounds provide a new lens through which to understand existing algorithms and instance-dependent rates, and provide new clarity.

As a disclaimer, we mention that the primary goal of this work is to understand how contextual information shapes the optimal instance-dependent rates for contextual bandits. We believe that this question is challenging and interesting even in the finite-action regime (in fact, even when $A=2$!) and as such, we do not focus on obtaining optimal dependence on $A$ in our upper or lower bounds, nor do we handle infinite actions. Fully understanding the interplay between contexts and actions is a fascinating open problem, and we hope to see this addressed in future work.

Our main algorithm, AdaCB, is oracle-efficient. That is, it accesses the value function class $\mathcal{F}$ only through a weighted least squares regression oracle capable of solving problems of the form

We replicated the large-scale empirical contextual bandit evaluation setup of Bietti et al. (2018), which compares a number of state-of-the art general-purpose contextual bandit algorithms across more than 500 datasets. We found that our new algorithm, AdaCB, typically gives comparable or superior results to existing baselines, particularly on challenging datasets with many actions.

2 Overview of Results: Reinforcement Learning

Building on our contextual bandit results, we provide disagreement-based guarantees for episodic reinforcement learning with function approximation in a model called the block MDP (Krishnamurthy et al., 2016; Du et al., 2019a), which is an important type of contextual decision process (Jiang et al., 2017).

The block MDP may be thought of as a generalization of the contextual bandit problem. Each round of interaction is replaced by an episode of length $H$. While the initial context $x_{1}$ (now referred to as a state) in each episode is drawn i.i.d. as in the contextual bandit, the evolution of the subsequent states $x_{2},\ldots,x_{H}$ is influenced by the learner’s actions. Now, without further assumptions, this is simply a general MDP, and function approximation provides no benefits in the worst-case. To allow for sample-efficient learning guarantees, the block MDP model assumes there is an unobserved latent MDP with $S$ states, and that each observed state $x_{h}$ is drawn from an emission distribution for the current latent state $s_{h}$. When $H=1$ and $S=1$, this recovers the contextual bandit, and in general the goal is to use an appropriate value function class $\mathcal{F}$ to attain sample complexity guarantees that are polynomial in $S$, but not $\left\lvert\mathcal{X}\right\rvert$ (which, as in the contextual bandit, is typically infinite and high-dimensional).

More formally, the block MDP setup we consider is a layered episodic Markov decision process with horizon $H$, state space $\mathcal{X}=\mathcal{X}_{1}\cup\cdots\cup\mathcal{X}_{H}$ (with $\mathcal{X}_{i}\cap\mathcal{X}_{j}=\emptyset$), and action space $\mathcal{A}$ with $\left\lvert\mathcal{A}\right\rvert=A$. We proceed in $K$ episodes. Within each episode we observe rewards and observations through the following protocol, beginning with $x_{1}\sim\mu$.

Observe reward $r_{h}$ and next state $x_{h+1}\sim P^{\star}_{h}(\cdot\mid{}x_{h},a_{h})$.

As mentioned above, the state space is potentially rich and high-dimensional, and dependence on $\left\lvert\mathcal{X}\right\rvert$ is unacceptable. Hence, to enable sample-efficient reinforcement learning guarantees with function approximation, the block MDP model assumes the existence of a latent state space $\mathcal{S}=\mathcal{S}_{1}\cup\cdots\cup\mathcal{S}_{H}$, and assumes that each state $x\in\mathcal{X}$ can be uniquely attributed to a latent state $s\in\mathcal{S}$. More precisely, we assume that for each $h$, $P^{\star}_{h}$ factorizes, so that we can view $x_{h+1}$ as generated by the process $s_{h+1}\sim P^{\star}_{h}(\cdot\mid{}x_{h},a_{h})$, $x_{h+1}\sim\psi(s_{h+1})$, where $\psi:\mathcal{S}\to\Delta(\mathcal{X})$ is an (unknown) emission distribution, and $s_{h+1}$ is the latent state for layer $h+1$. We make the following standard decodability assumption (Krishnamurthy et al., 2016; Jiang et al., 2017; Du et al., 2019a).

This assumption implies that the optimal policy $\pi^{\star}$ depends only on the current context $x_{h}$. We write the optimal $Q$-function for layer $h$ as $\mathbf{Q}^{\star}_{h}(x,a)$ and let $\mathbf{V}^{\star}_{h}(x)=\max_{a\in\mathcal{A}}\mathbf{Q}^{\star}_{h}(x,a)$ be the optimal value function.

As in the contextual bandit setting, take as a given class of functions $\mathcal{F}$ that attempts to model the optimal value function. We let $\mathcal{F}_{h}\subseteq(\mathcal{X}\times\mathcal{A}\to\left[0,H\right])$ be the value function class for layer $h$ (with $\mathcal{F}=\mathcal{F}_{1}\times\cdots\times\mathcal{F}_{h}$), and we make the following optimistic completeness assumption (Jin et al., 2020; Wang et al., 2019, 2020).

For all $h$ and all functions $V:\mathcal{X}_{h+1}\to\left[0,H\right]$, we have that

3 implies that $\mathbf{Q}^{\star}_{h}\in\mathcal{F}_{h}$, generalizing the realizability assumption (1) but it is significantly stronger, as it requires that the function class contains Bellman backups for arbitrary functions.

We develop a new instance-dependent algorithm that adapts to the gap in the optimal value function $\mathbf{Q}^{\star}$ to attain improved sample complexity. Define $\Delta(x,a)=\mathbf{V}^{\star}_{h}(x)-\mathbf{Q}^{\star}_{h}(x,a)$, and define the worst-case gap as

Our main result is an oracle-efficient algorithm, RegRL, which attains a tight gap-dependent PAC-RL guarantee whenever an appropriate generalization of the value function disagreement coefficient $\boldsymbol{\theta}^{\mathsf{val}}$ is bounded.

This theorem has two key features. First, when $\boldsymbol{\theta}^{\mathsf{val}}=\widetilde{\mathcal{O}}(1)$, the scaling of $\varepsilon$ and $\Delta$ in the term $\frac{\log\left\lvert\mathcal{F}\right\rvert}{\varepsilon\cdot\Delta}$ is optimal even for in the special case of contextual bandits, and improves over the minimax rate, which scales as $\frac{1}{\varepsilon^{2}}$. Second, and perhaps more importantly, RegRL is computationally efficient, and only requires a regression oracle for the value function class. Previous works require stronger oracles and typically do not attain optimal dependence on $\varepsilon$, but are not fully comparable in terms of statistical assumptions (Krishnamurthy et al., 2016; Jiang et al., 2017; Dann et al., 2018; Du et al., 2019b, a; Misra et al., 2019; Feng et al., 2020; Agarwal et al., 2020); see Section 3 for a detailed comparison. At a conceptual level, the design and analysis of RegRL use several new techniques that leverage our disagreement-based perspective, and we hope that they will find broader use.

3 Additional Notation

4 Organization

Section 2 contains our main contextual bandit results. Sections 2.1, 2.2 and 2.3 contain our main algorithm, AdaCB, and disagreement-based best-of-both-worlds guarantees and lower bounds. Section 2.4 and Section 2.5 contain structural results and guarantees for worst-case distributions and adversarial contexts. Section 3 contains disagreement-based guarantees for reinforcement learning with function approximation. In Section 4 we show in detail how to implement all of our algorithms for contextual bandits and reinforcement learning using regression oracles for the value function class. Section 5 contains experiments with AdaCB, and we conclude in Section 6 with discussion and open problems. Proofs are deferred to the appendix.

Contextual Bandits

We now introduce our contextual bandit algorithm, AdaCB, and give regret bounds based on the policy and value function disagreement coefficients, as well as matching lower bounds. We then show how to relate these quantities to other structural parameters for the distribution-free and adversarial settings, and instantiate our bounds for concrete settings of interest.

Our main algorithm, AdaCB, is presented in Algorithm 1. Exploration in AdaCB is based on a probability selection strategy introduced by Abe and Long (1999) (see also Abe et al. (2003)) and extended to contextual bandits with general function classes by Foster and Rakhlin (2020) and Simchi-Levi and Xu (2020) for online and offline regression oracles, respectively. We utilize a general version of the Abe-Long strategy which we refer to by the more descriptive name “inverse gap weighting” (IGW). The strategy is parameterized by a learning rate $\gamma$ and a subset $\mathcal{A}^{\prime}\subseteq\mathcal{A}$ of actions. Given a context $x$ and reward predictor $\widehat{f}\in\mathcal{F}$, we define a probability distribution $\textsf{IGW}_{\mathcal{A}^{\prime},\gamma}(x;\widehat{f})\in\Delta(\mathcal{A})$ by

where $\widehat{a}\vcentcolon={}\operatorname\star{arg\,max}_{a\in\mathcal{A}^{\prime}}\widehat{f}(x,a)$. Both Foster and Rakhlin (2020) and Simchi-Levi and Xu (2020) apply this strategy with $\mathcal{A}^{\prime}=\mathcal{A}$, and with the learning rate $\gamma$ selected either constant or following a fixed non-adaptive schedule. Building on this approach, AdaCB follows the same general template as the FALCON algorithm of Simchi-Levi and Xu (2020), but with two key differences. First, rather than applying the IGW scheme to all actions, we restrict only to actions $a$ which are “plausible” in the sense that they are induced by a version space $\mathcal{F}_{m}$ maintained (implicitly) by the algorithm. Second, we choose the learning rate $\gamma_{m}$ in a data-driven fashion.

In more detail, we operate in a doubling epoch schedule. Letting $\tau_{m}=2^{m}$ with $\tau_{0}=0$, each epoch $m\geq{}1$ consists of rounds $\tau_{m-1}+1,\dots,\tau_{m}$, and there are $M=\lceil\log_{2}T\rceil$ epochs in total. At the beginning of each epoch $m$, we compute an estimator $\widehat{f}_{m}$ for the Bayes regression function $f^{\star}$ by performing least-squares regression on data collected so far (2). We also maintain a version space $\mathcal{F}_{m}$, which is the set of all plausible predictors that cannot yet be eliminated based on square loss confidence bounds (3). Based on $\mathcal{F}_{m}$, we select the learning rate $\gamma_{m}$ for the current epoch adaptively by estimating a parameter called the instance-dependent scale factor ($\lambda_{m}$) which is closely related to the policy disagreement coefficient (Option I) and the value function disagreement coefficient (Option II). Then, when a context $x_{t}$ in epoch $m$ arrives, AdaCB first computes the candidate action set $\mathcal{A}_{t}\vcentcolon={}\mathcal{A}(x_{t};\mathcal{F}_{m})$ (9), which is the set of actions that are optimal for some predictor $f\in\mathcal{F}_{m}$, and thus could plausibly be equal to $\pi^{\star}(x_{t})$. The algorithm then sets $p_{t}=\textsf{IGW}_{\mathcal{A}_{t},\gamma_{m}}(x_{t};\widehat{f}_{m})$ (10), samples $a_{t}\sim{}p_{t}$, and proceeds to the next round.

The adaptive learning rate $\gamma_{m}$ balances the algorithm’s efforts between exploration and exploitation: a larger learning rate leads to more aggressive exploitation (following the least-squares predictor $\widehat{f}_{m}$), while a smaller learning rate leads to more conservative exploration over the candidate action set. AdaCB’s learning rate $\gamma_{m}$ (6) has two components: the instance-dependent scale factor $\lambda_{m}$, which is adaptively determined by the collected data; and a non-adaptive component propositional to $\sqrt{An_{m-1}/\log|\mathcal{F}|}$, where $n_{m-1}$ is the length of the epoch $m-1$. While the non-adaptive component is the same as the learning rate in FALCON and is sufficient if one only aims to achieve the minimax regret, the adaptive factor $\lambda_{m}$, combined with the action elimination procedure above, is essential for AdaCB to achieve near-optimal instance-dependent regret. We offer two different schemes to select $\lambda_{m}$: The first adapts to the policy disagreement coefficient, while the second adapts to the value function disagreement coefficient.

Option I (policy-based exploration). This option selects $\lambda_{m}$ as a sample-based approximation to the quantity

Option II (value-based exploration). While the disagreement probability used in Option I is a useful quantity that provides information on the hardness of the problem instance, it does not fully utilize the value function structure. In particular, it is only sensitive to the occurrence of disagreement on each context, but is not sensitive to the scale of disagreement (i.e., how much it would cost if we chose a disagreeing action) on each context. This motivates Option II, which is based on a refined confidence width $w(x;\mathcal{F}_{m})$ that accounts for both the occurrence and the scale of disagreement. Specifically, $w(x;\mathcal{F}_{m})$ measures the worst-case cost of exploring a sub-optimal action in the candidate action set for $x$, and Option II selects $\lambda_{m}$ as a sample-based approximation to the quantity

We make a few additional remarks. First, the learning rate and confidence width parameters in Algorithm 1 (and consequently our main theorems) consider a general finite class $\mathcal{F}$. This is only a stylistic choice: AdaCB works as-is for general function classes, with the dependence on $\log|\mathcal{F}|$ in these parameters replaced by standard learning-theoretic complexity measures such as the pseudodimension; see Section 2.7. Second, Algorithm 1 takes $T$ as input. One can straightforwardly extend Algorithm 1 to work with unknown $T$ using the standard doubling trick. Finally, we emphasize that Option I and Option II are designed based on different techniques and lead to different instance-dependent guarantees. Designing a single option that simultaneously achieving the goals of Option I and Option II is an interesting future direction.

AdaCB can be implemented efficiently with a weighted least squares regression oracle Oracle (see Eq. RO) as follows.

At each epoch $m$, call Oracle to compute the square loss empirical risk minimizer $\widehat{f}_{m}$.

For any given context $x$, the candidate action set $\mathcal{A}(x;\mathcal{F}_{m})$ can be computed using either $\widetilde{\mathcal{O}}(A)$ oracle calls when $\mathcal{F}$ is convex or $\widetilde{\mathcal{O}}(AT^{2})$ oracle calls for general (in particular, finite) classes.

For Option II, the function $w(x;\mathcal{F}_{m})$ can be computed in a similar fashion to $\mathcal{A}(x;\mathcal{F}_{m})$ using $\widetilde{\mathcal{O}}(A)$ or $\widetilde{\mathcal{O}}(A{}T^{2})$ oracle calls in the convex and general case, respectively.

Altogether, since $\mathcal{A}(x;\mathcal{F}_{m})$ and $w(x;\mathcal{F}_{m})$ are computed for $\mathcal{O}(1)$ different contexts per round amortized, the algorithm requires $\mathcal{O}(AT)$ calls to Oracle overall when $\mathcal{F}$ is convex. The reduction is described in full in Section 4.

2 Disagreement-Based Guarantees

We are now ready to state our first main regret guarantee for AdaCB, which is based on the policy disagreement coefficient Eq. 4. The theorem also includes a more general result in terms of an intermediate quantity we call the cost-sensitive policy disagreement coefficient, which we define by

For any instance with uniform gap $\Delta$, Algorithm 1 with Option I ensures that

More generally, Algorithm 1 with Option I ensures that for every instance, without any gap assumption,

Let us describe some key features of Theorem 2.1.

For example, for the classical multi-armed bandit setup where $\mathcal{X}$ is a singleton, we have $\boldsymbol{\theta}^{\mathsf{pol}}(\Pi,\varepsilon)=1$, recovering the usual instance-dependent rate (up to logarithmic factors). We give some more examples where logarithmic regret can be attained in a moment.

More generally, since the function $\varepsilon\mapsto\varepsilon\Delta{}T$ is increasing in $\varepsilon$ and $\boldsymbol{\theta}^{\mathsf{pol}}(\Pi,\varepsilon)$ is decreasing, the best choice for the bound Eq. 9 (up to constant factors) is the critical radius $\varepsilon_{T}$ that satisfies the balance

For example, if $\boldsymbol{\theta}^{\mathsf{pol}}(\Pi,\varepsilon)\propto\varepsilon^{-\rho}$ for some $\rho\in(0,1)$, then choosing $\varepsilon_{T}\propto(A\log\lvert\mathcal{F}\rvert(\Delta^{2}T)^{-1})^{\frac{1}{1+\rho}}$, leads to

The critical radius also plays an important role in the proof of Theorem 2.1.

With no assumption on the gap or $\boldsymbol{\theta}^{\mathsf{pol}}$, we may always take $\boldsymbol{\theta}^{\mathsf{csc}}(\Pi,\varepsilon)\leq{}1/\varepsilon$, so that Eq. 10 implies the minimax rate $\sqrt{A{}T\log\left\lvert\mathcal{F}\right\rvert}$.

We now show that the regret bound attained by AdaCB in Theorem 2.1 is near-optimal, in the sense that it cannot be improved beyond log factors without making additional assumptions on the class $\mathcal{F}$ or the contextual bandit instance.

Formally, we model a contextual bandit algorithm A as a sequence of mappings $\textsf{A}_{t}:(\mathcal{X}\times\mathcal{A}\times{}\left[0,1\right])^{t-1}\times{}\mathcal{X}\to\Delta(\mathcal{A})$, so that

is the algorithm’s action distribution after observing context $x_{t}$ at round $t$.

For a given function class $\mathcal{F}$, we define

Our main lower bound shows that there exists a function class $\mathcal{F}$ for which the constrained minimax complexity matches the upper bound Eq. 9.

All $f\in\mathcal{F}$ have uniform gap $\Delta$.

The constrained minimax complexity is lower bounded by

where $\widetilde{\Omega}(\cdot)$ hides factors logarithmic in $A$ and $\varepsilon^{-1}$.

This lower bound has a simple interpretation: The term $\varepsilon\Delta{}T$ is the regret incurred if we commit to playing a particular policy $\pi\in\Pi_{\varepsilon}$ for any “simple” instance in which the gap is no larger than $\mathcal{O}(\Delta)$ for all actions, while the term $\frac{\boldsymbol{\theta}^{\mathsf{pol}}(\Pi,\varepsilon)A\log{}\left\lvert\mathcal{F}\right\rvert}{\Delta}$ is the cost of exploration to find such a policy.

The first implication of this lower bound is that without an assumption such as the disagreement coefficient, logarithmic regret is impossible even when the gap is constant; this alone is not surprising since Foster and Rakhlin (2020) already showed a similar impossibility for non-stochastic contexts, but Theorem 2.2 strengthens this result since it holds for stochastic contexts. More importantly, the lower bound shows that the tradeoff in Theorem 2.1 is tight as a function of $\Delta,\varepsilon,A,\log\left\lvert\mathcal{F}\right\rvert$, and $\boldsymbol{\theta}^{\mathsf{pol}}$, so additional assumptions are required to attain stronger instance-dependent regret bounds for specific classes. We explore such assumptions in the sequel.

We mention one important caveat: Compared to instance-dependent lower bounds for multi-armed bandits (e.g., Garivier et al. (2019)), the quantification for Theorem 2.2 is slightly weaker. Rather than lower bounding the regret for any particular instance (assuming uniformly good performance in a neighborhood), we only show existence of a particular realizable instance with gap for which the regret lower bound holds. We suspect that strengthening the lower bound in this regard will be difficult unless one is willing to sacrifice dependence on $\log{}F$.

The (policy) disagreement coefficient has been studied extensively in active learning, and many bounds are known for different function classes and distributions of interest. We refer to Hanneke (2014) for a comprehensive survey and summarize some notable examples here (restricting to the binary/two-action case, which has been the main focus of active learning literature).

When $\mathcal{F}$ is a $d$-dimensional linear function class, $\boldsymbol{\theta}^{\mathsf{pol}}(\Pi,\varepsilon)\leq{}\widetilde{\mathcal{O}}(d^{1/2}\log(1/\varepsilon))$ whenever $\mathcal{D}$ is isotropic log-concave (Balcan and Long, 2013). More generally, $\boldsymbol{\theta}^{\mathsf{pol}}(\Pi,\varepsilon)=o(1/\varepsilon)$ as long as $\mathcal{D}$ admits a density (Hanneke, 2014).

3 Scale-Sensitive Guarantees

We now give instance-dependent regret guarantees based on the value function disagreement coefficient, which is defined via

Compared to the policy disagreement coefficient, the value function disagreement coefficient is somewhat easier to bound directly when the value function class $\mathcal{F}$ has simple structure. For example, when $\mathcal{F}$ is linear, we can bound $\boldsymbol{\theta}^{\mathsf{val}}$ in terms of the dimension for any distribution with a simple linear algebraic calculation.

More generally—as we show in the next section—the value function disagreement coefficient is always bounded by the so-called eluder dimension for $\mathcal{F}$, allowing us to leverage existing results for this parameter (Russo and Van Roy, 2013). However, the value function disagreement coefficient can be significantly tighter because—among other reasons—it can leverage benign distributional structure.

We now show that AdaCB can simultaneously attain the minimax regret bound and adapt to the value function disagreement coefficient.

For any instance, Algorithm 1 with Option II ensures that

where $\varepsilon_{T}\propto\sqrt{{\log(\left\lvert\mathcal{F}\right\rvert T)}/{T}}$.

As with our policy disagreement-based result, we complement Theorem 2.3 with a lower bound. To state the result, we define

which is the value-based analogue of the constrained minimax complexity Eq. 13. Our main lower bound is as follows.

All $f\in\mathcal{F}$ have uniform gap $\Delta$.

The constrained minimax complexity is lower bounded by

where $\widetilde{\Omega}(\cdot)$ hides factors logarithmic in $A$ and $\Delta/\varepsilon$.

As with Theorem 2.2, the lower bound Eq. 17 has a simple interpretation: The term $\frac{\varepsilon^{2}}{\Delta{}}T$ is an upper bound on the regret of any policy $\pi_{f}$ for which the predictor $f$ is within $L_{2}$-radius $\varepsilon$ of $f^{\star}$ (under gap $\Delta$), and the term $\frac{\boldsymbol{\theta}^{\mathsf{val}}\left(\mathcal{F},\Delta/2,\varepsilon\right)A{}\log{}\left\lvert\mathcal{F}\right\rvert}{\Delta}$ is the exploration cost to find such a predictor.

This implies that the instance-dependent term in Eq. 15 is nearly optimal in this regime, in that the parameter $\varepsilon_{T}=\sqrt{{\log\left\lvert\mathcal{F}\right\rvert}/{T}}$ used by the algorithm can at most be increased by a sub-polynomial factor. In general, however, Eq. 15 does not exactly match the tradeoff in Eq. 17, but we suspect that AdaCB can be improved to close the gap.With a-priori knowledge of $\boldsymbol{\theta}^{\mathsf{val}}$, this is fairly straightforward.

4 Distribution-Free Guarantees

The disagreement coefficients introduced in the previous section depend strongly on the context distribution $\mathcal{D}$. On one hand, this is a desirable feature, since it means we may pay very little to adapt to the gap $\Delta$ for benign distributions. On the other hand, in practical applications, we may not have prior knowledge of how favorable $\mathcal{D}$ is, or whether we should expect to do any better than the minimax rate. A natural question then is for what function classes we can guarantee logarithmic regret for any distribution $\mathcal{D}$. An important result of Hanneke and Yang (2015) shows that in the binary setting, the policy disagreement coefficient is always bounded by a combinatorial parameter called the (policy) star number. We give distribution-free results based on two multiclass generalizations of this parameter

For any policy $\pi^{\star}$ and policy class $\Pi$, let the weak policy star number $\underline{\mathfrak{s}}^{\mathsf{pol}}_{\pi^{\star}}(\Pi)$ denote the largest number $m$ such that there exist contexts $x^{{\scriptscriptstyle(1)}},\ldots,x^{{\scriptscriptstyle(m)}}$ and policies $\pi^{{\scriptscriptstyle(1)}},\ldots,\pi^{{\scriptscriptstyle(m)}}$ such that for all $i$,

For any policy $\pi^{\star}$ and policy class $\Pi$, let the strong policy star number $\mathfrak{s}^{\mathsf{pol}}_{\pi^{\star}}(\Pi)$ denote the largest number $m$ such that there exist context-action pairs $(x^{{\scriptscriptstyle(1)}},a^{{\scriptscriptstyle(1)}}),\ldots,(x^{{\scriptscriptstyle(m)}},a^{{\scriptscriptstyle(m)}})$ and policies $\pi^{{\scriptscriptstyle(1)}},\ldots,\pi^{{\scriptscriptstyle(m)}}$ such that for all $i$,

These definitions are closely related: It is simple to see that

This result immediately implies that AdaCB enjoys logarithmic regret for any function class with bounded policy star number.

For any function class $\mathcal{F}$, AdaCB with Option I has

One slightly unsatisfying feature of our lower bounds based on the disagreement coefficient (Theorem 2.2/Theorem 2.4) is that they are worst-case in nature, and rely on an adversarially constructed policy class. Our next theorem shows that Eq. 20 is near-optimal for any policy class $\Pi$ (albeit, in the worst case over all value function classes $\mathcal{F}$ inducing $\Pi$). This means that if we take the policy class $\Pi$ as a given rather than the value function class $\mathcal{F}$, bounded policy star number is both necessary and sufficient for logarithmic regret.

Let a policy class $\Pi$, $\pi^{\star}\in\Pi$, and gap $\Delta\in(0,1/8)$ be given. Then there exists a value function class $\mathcal{F}$ such that

$\Pi=\left\{\pi_{f}\mid{}f\in\mathcal{F}\right\}$, and in particular some $f^{\star}\in\mathcal{F}$ has $\pi^{\star}=\pi_{f^{\star}}$.

Each $f\in\mathcal{F}$ has uniform gap $\Delta$.

This bound scales with the strong variant of the policy disagreement coefficient rather than the (smaller) weak variant, but does not directly scale with the number of actions. Hence, the dependence matches the upper bound of AdaCB in Eq. 20 whenever the second inequality in Eq. 18 saturates (since $\mathfrak{s}^{\mathsf{pol}}_{\pi^{\star}}(\Pi)$ can itself scale with the number of actions). We suspect that the lower bound is tight and that the upper bound can be improved to scale with $\mathfrak{s}^{\mathsf{pol}}_{\pi^{\star}}(\Pi)$, with no explicit dependence on the number of actions.

Unlike the upper bound Eq. 20, the lower bound Eq. 21 does not scale with $\log\left\lvert\mathcal{F}\right\rvert$. This does not appear to be possible to resolve without additional assumptions, as there are classes for which Eq. 21 is tight (consider $d$ independent multi-armed bandit problems), as well as classes for which Eq. 20 is tight (cf. Theorem 2.2). Similar issues arise in lower bounds for active learning (Hanneke and Yang, 2015). However in the full version of Theorem 2.6 (Section D.3), we are able to strengthen the lower bound to roughly \Omega\Big{(}\frac{\mathfrak{s}^{\mathsf{pol}}_{\pi^{\star}}(\Pi)+\log\left\lvert\mathcal{F}\right\rvert}{\Delta}\Big{)} for Natarajan classes.

We now extend our development based on the star number to give distribution-free upper bounds on the value function disagreement coefficient. Compared to the policy-based setting, where we were able to simply appeal to upper bounds from Hanneke and Yang (2015), scale-sensitive analogues of the star number have not been studied in the literature to our knowledge. This leads us to introduce the following definition.

Let $\check{\mathfrak{s}}^{\mathsf{val}}_{f^{\star}}(\mathcal{F},\Delta)$ be the length of the longest sequence of context-action pairs $(x^{{\scriptscriptstyle(1)}},a^{{\scriptscriptstyle(1)}}),\ldots,(x^{{\scriptscriptstyle(m)}},a^{{\scriptscriptstyle(m)}})$ such that for all $i$, there exists $f^{{\scriptscriptstyle(i)}}\in\mathcal{F}$ such that

The value function star number is defined as $\mathfrak{s}^{\mathsf{val}}_{f^{\star}}(\mathcal{F},\Delta_{0})\vcentcolon=\sup_{\Delta>\Delta_{0}}\check{\mathfrak{s}}^{\mathsf{val}}_{f^{\star}}(\mathcal{F},\Delta)$.

When the function class $\mathcal{F}$ is $\left\{0,1\right\}$-valued, the value function star number coincides with the policy star number, i.e. $\mathfrak{s}^{\mathsf{val}}_{f^{\star}}(\mathcal{F},1)=\mathfrak{s}^{\mathsf{pol}}_{f^{\star}}(\mathcal{F})$. In general though, for a given class $\mathcal{F}$, the policy star number for the induced class can be arbitrarily large compared to the value function star number.Interestingly, this construction also shows that in general, the value function star number for $\mathcal{F}$ can be arbitrarily small compared to the fat-shattering dimension. This is somewhat counterintuitive because the star number for a policy class always upper bounds its VC dimension.

Generalizing the result of Hanneke and Yang (2015), we show that the value function star number bounds the value function disagreement coefficient for all distributions and all scale levels.

For any uniform Glivenko-Cantelli class $\mathcal{F}$ and $f^{\star}:\mathcal{X}\times\mathcal{A}\to\left[0,1\right]$,

Compared to the bound for the policy star number (Theorem 2.5), Theorem 2.7 is worse by a quadratic factor when specialized to discrete function classes. Improving Eq. 22 to be linear in the star number is an interesting technical question. The assumption that $\mathcal{F}$ is uniform Glivenko-Cantelli is quite weak and arises for technical reasons: compared to the policy star number, which always bounds the VC/Natarajan dimension, boundedness of the value function star number is not sufficient to ensure that $\mathcal{F}$ enjoys uniform convergence.

The main takeaway from Theorem 2.7 is that AdaCB with Option II guarantees

for any distribution. Following our development for the policy star number, we now turn our attention to establishing the necessity of the value function star number for gap-dependent regret bounds. Our lower bound depends on the following “weak” variant of the parameter.

For any $\Delta\in(0,1)$ and $\varepsilon\in(0,\Delta/2)$, define $\underline{\mathfrak{s}}^{\mathsf{val}}_{f^{\star}}(\mathcal{F},\Delta,\varepsilon)$ be the length of the largest sequence of points $x^{{\scriptscriptstyle(1)}},\ldots,x^{{\scriptscriptstyle(m)}}$ such that for all $i$, there exists $f^{{\scriptscriptstyle(i)}}\in\mathcal{F}$, such that

$f^{{\scriptscriptstyle(i)}}(x^{{\scriptscriptstyle(i)}},\pi_{f^{{\scriptscriptstyle(i)}}}(x^{{\scriptscriptstyle(i)}}))\geq{}\max_{a\neq{}\pi_{f^{{\scriptscriptstyle(i)}}}(x^{{\scriptscriptstyle(i)}})}f^{{\scriptscriptstyle(i)}}(x^{{\scriptscriptstyle(i)}},a)+\Delta$ and $\pi_{f^{{\scriptscriptstyle(i)}}}(x^{{\scriptscriptstyle(i)}})\neq{}\pi^{\star}(x^{{\scriptscriptstyle(i)}})$.

$\max_{a}\left\lvert f^{{\scriptscriptstyle(i)}}(x^{{\scriptscriptstyle(i)}},a)-f^{\star}(x^{{\scriptscriptstyle(i)}},a)\right\rvert\leq{}2\Delta$

$\sum_{j\neq{}i}\max_{a}\left\lvert f^{{\scriptscriptstyle(i)}}(x^{{\scriptscriptstyle(j)}},a)-f^{\star}(x^{{\scriptscriptstyle(j)}},a)\right\rvert^{2}<\varepsilon^{2}$.

Relative to the basic value function star number, the key difference above is that we allow a separate scale parameter to control the sum constraint in Item 3 above. This is important to prevent passive information leakage in our lower bound construction, but we suspect this condition can be relaxed to more closely match Definition 2.3. Our main lower bound is as follows.To avoid technical conditions involving the boundary of the interval $\left[0,1\right]$, we allow for unit Gaussian rewards with means in $\left[0,1\right]$ for this lower bound.

Let a function class $\mathcal{F}$ and $f^{\star}\in\mathcal{F}$ with uniform gap $\Delta$ be given. Let $\varepsilon_{T}\in(0,\Delta/4)$ be the largest solution to the equationThere is always at least one solution to Eq. 24, since we can take $\varepsilon_{T}=0$.

As mentioned before, we suspect that the linear scaling in Eq. 25 is correct and that Eq. 23 can be improved to match. The dependence on the additional scale parameter $\varepsilon_{T}$ is more subtle, and requires further investigation.

5 Adversarial Contexts and the Eluder Dimension

Let $\check{\mathfrak{e}}^{\mathsf{val}}_{f^{\star}}(\mathcal{F},\Delta)$ be the length of the longest sequence of context-action pairs $(x^{{\scriptscriptstyle(1)}},a^{{\scriptscriptstyle(1)}}),\ldots,(x^{{\scriptscriptstyle(m)}},a^{{\scriptscriptstyle(m)}})$ such that for all $i$, there exists $f^{{\scriptscriptstyle(i)}}\in\mathcal{F}$ such that

The value function eluder dimension is defined as $\mathfrak{e}^{\mathsf{val}}_{f^{\star}}(\mathcal{F},\Delta_{0})=\sup_{\Delta>\Delta_{0}}\check{\mathfrak{e}}^{\mathsf{val}}(\mathcal{F},\Delta)$.

The only difference between the value function star number and the value function eluder dimension is whether the sum in Eq. 26 takes the form “$\sum_{j\neq{}i}$” or “$\sum_{j<i}$”; the latter reflects the stronger sequential structure present when contexts are adversarial. It is immediate that

However, the separation between the two parameters can be arbitrarily large in general.

While Eq. 27 shows that boundedness of the eluder dimension is sufficient for AdaCB achieve logarithmic regret for stochastic contexts (via Eq. 23), Proposition 2.3, shows that it may lead to rather pessimistic upper bounds. This is not surprising, since the eluder dimension was designed to accomodate adversarially chosen contexts. The next result, which is a small refinement of the analysis of Russo and Van Roy (2013), shows that bounded eluder dimension indeed suffices to guarantee logarithmic regret for the adversarial setting; we defer a precise description of the algorithm to the proof.

For the adversarial context setting, the general function class UCB algorithm—when configured appropriately—guarantees that

for any instance with uniform gap $\Delta$.

Paralleling our results for the value function star number, we show that boundedness of a weak variant of the value function eluder dimension is required for logarithmic regret with adversarial contexts.

For any $\Delta\in(0,1)$ and $\varepsilon\in(0,\Delta/4)$, define $\underline{\mathfrak{e}}^{\mathsf{val}}_{f^{\star}}(\mathcal{F},\Delta,\varepsilon)$ be the length of the largest sequence of contexts $x^{{\scriptscriptstyle(1)}},\ldots,x^{{\scriptscriptstyle(m)}}$ such that for all $i$, there exists $f^{{\scriptscriptstyle(i)}}\in\mathcal{F}$, such that

$f^{{\scriptscriptstyle(i)}}(x^{{\scriptscriptstyle(i)}},\pi_{f^{{\scriptscriptstyle(i)}}}(x^{{\scriptscriptstyle(i)}}))\geq{}\max_{a\neq{}\pi_{f^{{\scriptscriptstyle(i)}}}(x^{{\scriptscriptstyle(i)}})}f^{{\scriptscriptstyle(i)}}(x^{{\scriptscriptstyle(i)}},a)+\Delta$ and $\pi_{f^{{\scriptscriptstyle(i)}}}(x^{{\scriptscriptstyle(i)}})\neq{}\pi^{\star}(x^{{\scriptscriptstyle(i)}})$.

$\max_{a}\left\lvert f^{{\scriptscriptstyle(i)}}(x^{{\scriptscriptstyle(i)}},a)-f^{\star}(x^{{\scriptscriptstyle(i)}},a)\right\rvert\leq{}2\Delta$

$\sum_{j<i}\max_{a}\left\lvert f^{{\scriptscriptstyle(i)}}(x^{{\scriptscriptstyle(j)}},a)-f^{\star}(x^{{\scriptscriptstyle(j)}},a)\right\rvert^{2}<\varepsilon^{2}$.

Our main lower bound here shows that—with the same caveats as Theorem 2.8—the scaling in Eq. 28 is near-optimal.As with Theorem 2.8, we allow for unit Gaussian rewards with means in $\left[0,1\right]$ for this lower bound.

Let a function class $\mathcal{F}$ and $f^{\star}\in\mathcal{F}$ with uniform gap $\Delta$ be given. Let $\varepsilon_{T}\in(0,\Delta/4)$ be the largest solution to the equation

An immediate consequence of Theorem 2.7 and Eq. 27 is that we always have $\boldsymbol{\theta}^{\mathsf{val}}\left(\mathcal{F},\Delta,\varepsilon\right)\leq\mathcal{O}(\mathfrak{e}^{\mathsf{val}}(\mathcal{F},\Delta)^{2})$. While this bound scales quadratically, we can show through a more direct argument that the value function disagreement coefficient grows at most linearly with the eluder dimension.

For any uniform Glivenko-Cantelli class $\mathcal{F}$ and $f^{\star}:\mathcal{X}\times\mathcal{A}\to\left[0,1\right]$,

This result strongly suggests that the quadratic dependence on the value function star number in Theorem 2.7 can be improved.

Previous work which uses the eluder dimension to analyze algorithms for contextual bandits and reinforcement learning (Russo and Van Roy, 2013; Osband and Van Roy, 2014; Ayoub et al., 2020; Wang et al., 2020) only works with the value function-based formulation in Definition 2.5. In light of our results for the disagreement coefficient and star number, we propose the following policy-based variant of the eluder dimension.

For any policy $\pi^{\star}$ and policy class $\Pi$, let the policy eluder dimension $\mathfrak{e}^{\mathsf{pol}}_{\pi^{\star}}(\Pi)$ denote the largest number $m$ such that there exist context-action pairs $(x^{{\scriptscriptstyle(1)}},a^{{\scriptscriptstyle(1)}}),\ldots,(x^{{\scriptscriptstyle(m)}},a^{{\scriptscriptstyle(m)}})$ and policies $\pi^{{\scriptscriptstyle(1)}},\ldots,\pi^{{\scriptscriptstyle(m)}}$ such that for all $i$,

We are not yet aware of any upper bounds based on the policy eluder dimension, but we can show that boundedness of this parameter is indeed necessary for logarithmic regret in the adversarial context setting (in a worst-case sense).

Consider the adversarial context setting. Let a policy class $\Pi$, $\pi^{\star}\in\Pi$, and gap $\Delta\in(0,1/8)$ be given. Then there exists a value function class $\mathcal{F}$ such that:

$\Pi=\left\{\pi_{f}\mid{}f\in\mathcal{F}\right\}$, and in particular some $f^{\star}\in\mathcal{F}$ has $\pi^{\star}=\pi_{f^{\star}}$.

Each $f\in\mathcal{F}$ has uniform gap $\Delta$.

6 Discussion

Our proof of Theorem 2.1 builds on the regret analysis framework established in Simchi-Levi and Xu (2020), which interprets IGW as maintaining a distribution over policies in the universal policy space $\mathcal{A}^{\mathcal{X}}$, and shows that the induced distribution of policies is a solution to an implicit optimization problem which (when configured appropriately) provides a sufficient condition for minimax contextual bandit learning. Following this framework, we also view AdaCB’s sequential IGW procedure as implicitly maintaining a sequence of distributions over policies, but with an additional key property: the support of the implicit distribution over policies is adaptively shrinking. This is enabled by AdaCB’s elimination procedure and is essential to our instance-dependent analysis. We show that the implicit distribution over policies given by AdaCB is a solution to a novel data-driven implicit optimization problem (Lemma C.6), which, when configured appropriately by adaptively selecting the learning rate with Option I, provides a sufficient condition for optimal policy disagreement-based instance-dependent contextual bandit learning. Our proof introduces several new techniques to instance-dependent analysis of contextual bandits, including using disagreement-based indicators and disagreement probability to obtain faster policy convergence rates (Lemmas C.8, C.10 and C.11). We also remark that the selection of the adaptive learning rate is non-trivial, and we derive the schedule Option I by carefully balancing key quantities appearing in our analysis.

Our lower bounds build on the work of Raginsky and Rakhlin (2011), which provides information-theoretic lower bounds for passive and active learning in terms of the disagreement coefficient. As in this work, we rely on a specialized application of the Fano method using the reverse KL-divergence, but with some refinements to make the technique more suited for regret lower bounds. For Theorem 2.2, we also incorporate improvements to the method suggested by Hanneke (2014) to obtain the correct dependence on $\log\lvert\mathcal{F}\rvert$.

The proof of Theorem 2.7 is somewhat different from the proof of the analogous policy-based result by Hanneke and Yang (2015). The key step toward proving LABEL:{thm:disagreement_to_star} is to prove an empirical analogue of the result that holds whenever $\mathcal{D}$ is uniform over a finite sequence of examples. This result is given in Lemma E.1, and is motivated by a property of the eluder dimension established in Proposition 3 of Russo and Van Roy (2013), with their “$\sum_{j<i}$”-based definition changed to our “$\sum_{j\neq i}$”-based definition. The proof of Lemma E.1 trickier, however, as our “$\sum_{j\neq i}$”-based definition breaks several combinatorial properties utilized in the proof of Russo and Van Roy (2013). We address this challenge by proving a new combinatorial lemma (Lemma E.3), which is fairly general and may be interesting on its own right. Nevertheless, our upper bound is quadratic in $\mathfrak{s}^{\mathsf{val}}_{f^{\star}}(\mathcal{F},\Delta)$ rather than linear, and we hope that this dependence can be improved in future work.

Gap-dependent regret bounds for contextual bandits have not been systematically studied at the level of generality we consider here, and we are not aware of any prior lower bounds beyond the linear setting. Most prior work has focused on structured function classes such as linear (Dani et al., 2008; Abbasi-Yadkori et al., 2011; Hao et al., 2019) and nonparametric Lipschitz/Hölder classes (Rigollet and Zeevi, 2010; Perchet and Rigollet, 2013; Hu et al., 2020).

Our work draws inspiration from Krishnamurthy et al. (2017), who defined variants of the disagreement coefficient which depend on scale-sensitive properties of the class $\mathcal{F}$ in the context of cost-sensitive multiclass active learning. Compared to these results, the key difference is that our value function disagreement coefficient is defined in terms of the $L_{2}$ ball for the class $\mathcal{F}$ rather than the excess risk ball for the induced policy class. This change is critical to ensure that the value function disagreement coefficient is bounded by the value function star number, and in particular that it is always bounded for linear classes.

Our work also builds on Foster et al. (2018), who give instance-dependent guarantees for the generalized UCB algorithm and an action elimination variant for general function classes based on the cost-sensitive multiclass disagreement coefficients introduced in Krishnamurthy et al. (2017). We improve upon this result on several fronts: 1) As mentioned above, our notion of value function disagreement coefficient is tighter, and is always bounded by the value function star number and value function eluder dimension 2) we attain optimal dependence on the gap, 3) our algorithms are guaranteed to attain the minimax rate in the worst case, and 4) we complement these results with lower bounds.

Lastly, we mention that while there are no prior lower bounds for contextual bandits based on the eluder dimension, Wen and Van Roy (2017) give an eluder-based lower bound for reinforcement learning with deterministic transitions and known rewards. This result is closer in spirit to our disagreement-based lower bounds (Theorems 2.2 and 2.4), is it applies to a carefully constructed function class rather than holding for all function classes, and mainly serves to demonstrate the worst-case tightness of a particular upper bound.

7 Extensions

We conclude this section by presenting some basic extensions of our contextual bandit results, including extensions of our regret bounds to handle infinite classes and weaker noise conditions.

As we have mentioned, Algorithm 1, Theorem 2.1 and Theorem 2.3 trivially extend to infinite $\mathcal{F}$, with the dependence on $\log|\mathcal{F}|$ in the algorithm’s parameters and the regret bounds replaced by standard learning-theoretic complexity measures such as the pseudodimension, (localized) Rademacher complexity, or metric entropy. This is because the analysis of AdaCB (see Appendix C) does not rely on any complexity assumptions for $\mathcal{F}$, except for Lemma C.1, which uses a standard uniform martingale concentration bound for the square loss to show that the empirical risk minimizer $\widehat{f}_{m}$ has low excess risk at each epoch. Therefore, to extend our results to infinite $\mathcal{F}$, one only needs to replace Lemma C.1 with an analogous uniform martingale concentration inequality for infinite classes. Such results have already been established in the literature, see, e.g., Krishnamurthy et al. (2017) and Foster et al. (2018).

Beyond uniform gap, AdaCB can also adapt to the Tsybakov noise condition (Mammen and Tsybakov, 1999; Tsybakov, 2004; Audibert et al., 2007; Rigollet and Zeevi, 2010; Hu et al., 2020), as the following proposition shows.

Suppose there exist constants $\alpha,\beta\geq 0$ such that

Then Algorithm 1 with Option I ensures that

The supremum over the action distribution $p$ in the definition Eq. 14 of the value function disagreement coefficient is more pessimistic than what is actually required to analyze AdaCB. Consider the following action distribution-dependent definition:

The regret bound in Theorem 2.3 can be tightened to depend on $\sup_{p\in\mathcal{P}}\boldsymbol{\theta}^{\mathsf{val}}_{\mathcal{D},p;f^{\star}}(\mathcal{F},\Delta/2,\varepsilon_{T})$, where $\mathcal{P}$ is a set of action distributions with favorable properties that can lead to tighter bounds. In particular, the proof of Theorem 2.3 implies that for any instance with uniform gap $\Delta$, if $\boldsymbol{\theta}^{\mathsf{val}}_{\mathcal{D},p;f^{\star}}(\mathcal{F},\Delta/2,\varepsilon_{T})\leq\theta$ for all $p$ such that $p(\pi^{\star}(x)|x)\geq A^{-1}$ for all $x$, then AdaCB with Option II ensures that

The following result shows that this property leads to dimension-independent bounds for sparse linear function classes.

for all $p$ such that $p(\pi^{\star}(x)|x)\geq{}\alpha$ for all $x$.

For simplicity, we assume that $\arg\max_{a\in\mathcal{A}}f^{\star}(x,a)$ is unique for all $x$ in the main body of the paper. When such assumption does not hold, we keep the original definition of $\pi^{\star}(x)$ (which makes $\pi^{\star}(x)$ unique for each $x\in\mathcal{X}$), while defining

We then make the following modifications to our framework. First, we modify the uniform gap condition Eq. 2 to require that for all $x\in\mathcal{X}$,

Second, we modify the definition of policy disagreement coefficient to

Reinforcement Learning

We now give disagreement-based guarantees for reinforcement learning with function approximation in the block MDP setting (cf. Section 1.2.1). Before proceeding, let us introduce some additional notation.

We also define the Bayes reward function as

1 The Algorithm

Our main reinforcement learning algorithm, RegRL, is presented in Algorithm 2. The algorithm follows the optimistic least-squares value iteration framework (Jin et al., 2020; Wang et al., 2019, 2020), with few key changes that allow us to prove guarantees based on a suitable notion of value function disagreement coefficient rather than stronger complexity measures such as the eluder dimension. The most interesting aspect of the algorithm is a feature we call the star hull upper confidence bound: Compared to the classical UCB approach, which computes an optimistic $Q$-function by taking largest predicted reward amongst all value function in an $L_{2}$ ball around an empirical risk minimizer, we add an additional step which first “lightly convexifies” this set. This step is based on techniques from the literature on aggregation in least squares (Audibert, 2008; Liang et al., 2015), and leads to more stable predictions.

In more detail, the algorithm proceeds in $K$ iterations.We use the term “iteration” distinctly from the term “episode”, as each iteration consists of multiple episodes. In each iteration $k$, we compute an optimistic Q-function $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}^{{\scriptscriptstyle(k)}}$ such that

We then take the greedy argmax policy defined by $\pi^{{\scriptscriptstyle(k)}}(x)=\operatorname\star{arg\,max}_{a\in\mathcal{A}}\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}_{h}^{{\scriptscriptstyle(k)}}(x,a)$ for $x\in\mathcal{X}_{h}$, and gather $H$ trajectories as follows: For each $h$, we roll in to layer $h$ with $\pi^{{\scriptscriptstyle(k)}}$, then choose actions uniformly at random for the rest of the episode. These trajectories are used to refine our value function estimates for subsequent iterations, with the $h$th trajectory used for estimation at layer $h$. Choosing actions uniformly ensures that the data gathered from these trajectories is useful regardless of the action distribution in subsequent iterations.

Let us now elaborate on the upper confidence bound computation. Let iteration $k$ and layer $h$ be fixed, and suppose we have already computed $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}_{h+1}^{{\scriptscriptstyle(k)}}$ and $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}_{h+1}^{{\scriptscriptstyle(k)}}(x)\vcentcolon={}\max_{a\in\mathcal{A}}\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}_{h+1}^{{\scriptscriptstyle(k)}}(x,a)$. The first step, following the usual optimistic LSVI schema, is to estimate a value function for layer $h$ by regressing onto the empirical Bellman backups from the next layer (5):

At this point, the usual optimistic value function for layer $h$ (cf. Russo and Van Roy (2013); Foster et al. (2018) for contextual bandits and Jin et al. (2020); Wang et al. (2019, 2020) for RL) is defined as

where $\beta_{h}$ is a confidence parameter. As observed in Jin et al. (2020); Wang et al. (2020), however, this UCB function can be unstable, leading to issues with generalization when we use it as a target for least squares at layer $h-1$. Our approach to address this problem is to expand the supremum above to include the star hull of $\mathcal{F}_{h}$ centered at $\widehat{f}_{h}^{{\scriptscriptstyle(k)}}$. Define the star hull of $\mathcal{F}_{h}$ centered at $f\in\mathcal{F}_{h}$ by

We define the star hull upper confidence bound (7) by

RegRL is oracle-efficient, and can be implemented using an offline regression oracle as follows.

At each iteration, the empirical risk minimizer in 5 can be computed with a single oracle call.

For any $(x,a)$ pair, the star hull UCB function in 7 can be computed by reduction to a regression oracle. In particular, to compute an $\varepsilon$-approximate UCB:

For convex function classes, $\mathcal{O}(\log(1/\varepsilon))$ calls are required.

For general (in particular, finite) classes, $\widetilde{\mathcal{O}}(\varepsilon^{-3})$ oracle calls are required. The key idea here is that we can reduce ERM over the star hull to ERM over the original class.

2 Main Result

We now state the main guarantee for RegRL. Our guarantee depends on the following “per-state” gap and worst-case gap:

and define $\boldsymbol{\theta}^{\mathsf{val}}_{\max}(\mathcal{F},\varepsilon)=\max_{h}\max_{s\in\mathcal{S}_{h}}\boldsymbol{\theta}^{\mathsf{val}}_{s}(\mathcal{F}_{h},\varepsilon)$.

Our main theorem bounding the error of RegRL is as follows. As with our contextual bandit results, we focus on finite classes $\mathcal{F}$ for simplicity, but the result trivially extends to general function classes.

and does so using at most $HK$ trajectories. More generally, the algorithm guarantees that

where $C_{\mathcal{M}}\vcentcolon=\sum_{h=1}^{H}\sum_{s\in\mathcal{S}_{h}}\frac{\boldsymbol{\theta}_{s}^{\mathsf{val}}(\mathcal{F}_{h},\beta_{h}K^{-1/2})}{\Delta(s)}$.

Let us describe a few key features of this theorem and interpret the result.

In light of the results in Section 2 this implies that one can attain the fast $\frac{1}{\Delta_{\min}\varepsilon}$ rate whenever the value function star number for $\mathcal{F}$ is bounded.

We emphasize that while the dependence on all of the parameters in Theorem 3.1 can almost certainly be improved, we hope this result will open the door for further disagreement-based algorithms and analysis techniques in reinforcement learning.

3 Discussion

The proof of Theorem 3.1 has two main components. The first part of the proof shows that with high probability, for all iterations $k$ and layers $h$, the set \mathcal{F}_{h}^{{\scriptscriptstyle(k)}}\vcentcolon=\big{\{}f\in\mathcal{F}_{h}\mid{}\|f-\widehat{f}_{h}^{{\scriptscriptstyle(k)}}\|_{\mathcal{Z}_{h}^{{\scriptscriptstyle(k)}}}\leq{}\beta_{h}\big{\}} contains the Bellman backup $\left[P^{\star}_{h}\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}_{h+1}^{{\scriptscriptstyle(k)}}\right](x,a)+f^{\star}(x,a)$ of the value function from the next layer, which ensures that $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}_{h}^{{\scriptscriptstyle(k)}}$ is optimistic in the sense of Eq. 35 and leads to exploration. Then, in the second part, we prove a regret decomposition which shows that whenever the optimistic property holds, the suboptimality of $\pi^{{\scriptscriptstyle(k)}}$ is controlled by the gap $\Delta$ and the value function disagreement coefficient $\boldsymbol{\theta}^{\mathsf{val}}$.

The first part of the proof (Appendix G) boils down to showing that the empirical risk minimizer in $\widehat{f}_{h}^{{\scriptscriptstyle(k)}}$ in Eq. 36 has favorable concentration properties. This is highly non-trivial because the targets $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}_{h+1}^{{\scriptscriptstyle(k)}}$ in Eq. 36 depend on the entire dataset, which breaks the independence assumptions required to apply standard generalization bounds for least squares. Instead, following Jin et al. (2020); Wang et al. (2020), we opt for a uniform generalization bound which holds uniformly over all possible choices of $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}_{h+1}^{{\scriptscriptstyle(k)}}$. To do so, we must show that $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}_{h+1}^{{\scriptscriptstyle(k)}}$ is approximated by a relatively low complexity function class, which we accomplish as follows. First, we show that—thanks to a certain Lipschitz property granted by the star hull—$\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}_{h+1}^{{\scriptscriptstyle(k)}}$ is well approximated by a function

where $\widetilde{\beta}_{h+1}\approx\beta_{h+1}$, and where

is the latent state norm, which measures the expected squared error conditioned on the sequence of latent states $\mathcal{L}_{h+1}^{{\scriptscriptstyle(k)}}\vcentcolon=(s^{{\scriptscriptstyle(1,h+1)}},\ldots,s^{{\scriptscriptstyle(k-1,h+1)}})$ encountered in the trajectories gathered for layer $h+1$. This approximation argument is rather non-trivial, and involves a recursion across all layers that we manage using the disagreement coefficient. With this taken care of, the next step is to use the block MDP structure to argue that $\widetilde{\mathbf{Q}}_{h+1}^{{\scriptscriptstyle(k)}}$ has low complexity. To see this, observe that $\widetilde{\mathbf{Q}}_{h+1}^{{\scriptscriptstyle(k)}}$ is completely determined by the center $\widehat{f}^{{\scriptscriptstyle(k)}}_{h+1}$ and the latent state sequence above. Since the latent state constraint does not depend on the ordering of the latent states, we can use a counting argument to show that there are at most $\left\lvert\mathcal{F}\right\rvert K^{\mathcal{O}(S)}$ possible choices for $\widetilde{\mathbf{Q}}_{h+1}^{{\scriptscriptstyle(k)}}$ overall. This suffices to prove the desired concentration guarantee.

The second part of the proof (Appendix F) proceeds as follows. Define the Bellman surplus as

which measures the width for our upper confidence bound. We use a “clipped” regret decomposition from Simchowitz and Jamieson (2019) to show that whenever the concentration event from the first part of the proof holds, the suboptimality of $\pi^{{\scriptscriptstyle(k)}}$ is controlled by the confidence widths:

In particular, let $n^{{\scriptscriptstyle(k,h)}}(s)$ denote the number of times the latent state $s$ was encountered in the layer $h$ trajectories prior to iteration $k$. Our key observation is that bounded disagreement coefficient implies that for each state $s$,

In other words, the disagreement coefficient controls the rate at which the confidence width shrinks. Moreover, since the width for latent state $s$ is proportional to the number of times we have visited the state (even though the algorithm cannot observe this quantity), we can bound the overall suboptimality across all iterations using similar arguments to those employed in the tabular setting (Azar et al., 2017; Simchowitz and Jamieson, 2019).

Our result is closely related to that of Wang et al. (2020), who gave regret bounds for a variant of optimistic LSVI based on the eluder dimension of $\mathcal{F}$. Compared to this result, we require the additional block MDP assumption and finite actions, but our bounds scale with the value function disagreement coefficient, which can be arbitrarily small compared to the eluder dimension (Proposition 2.3). On the technical side, their algorithm stabilizes the upper confidence bounds using a sensitivity sampling procedure, whereas we address this issue using the star hull. Ayoub et al. (2020) give similar eluder dimension-based guarantees for a model-based algorithm, though the notion of eluder dimension is somewhat stronger, and it is not clear whether this algorithm can be made oracle-efficient.

Reinforcement learning with function approximation in block MDPs has been the subject of extensive recent investigation (Krishnamurthy et al., 2016; Jiang et al., 2017; Dann et al., 2018; Du et al., 2019b, a; Misra et al., 2019; Feng et al., 2020; Agarwal et al., 2020). In terms of assumptions, we require the rather strong optimistic completeness condition, but do not require any reachability conditions or any clusterability-type assumptions that facilitate the use of unsupervised learning. The main advantages of our results are 1) we require only a basic regression oracle for the value function class, and 2) we attain the optimal $\varepsilon^{-1}$ fast rate in the presence of the gap and bounded disagreement coefficient.

We should also mention that the gap for $\mathbf{Q}^{\star}$ has been used in a number of recent results on reinforcement learning with function approximation (Du et al., 2019b, 2020a, 2020b), albeit for a somewhat different purpose. These results use the gap to prove that certain “non-optimistic” algorithms succeed, whereas we use it to beat the minimax rate.

Lastly, we note that the value function disagreement coefficient is similar to the “low variance” parameter used in Du et al. (2019b) to give guarantees for reinforcement learning with linear function approximation, but can be considerably smaller when applied to block MDPs. For example, in the trivial case in which each emission distribution $\psi(s)$ is a singleton, the value function disagreement coefficient is automatically bounded by $1$, while the low variance assumption may not be satisfied unless the latent MDP is near-deterministic.

Implementing the Algorithms with Regression Oracles

In Section 2.1 and Section 3.1, we mentioned that both AdaCB (Algorithm 1) and RegRL (Algorithm 2) can be efficiently implemented with an offline regression oracle. In this section, we provide more details on this implementation, and on the overall computational complexity of our algorithms. Throughout this section, we deal with general (possibly infinite) function classes.

To start with, we introduce the regression oracle that we assume. Let us first consider the contextual bandit setup where $\mathcal{F}$ is the value function class. Given $\mathcal{F}$, we assume a weighted least squares regression oracle, which is an offline optimization oracle capable of solving problems of the form

When one solves the regression problem Eq. RO using gradient-based methods like stochastic gradient descent (SGD), the convergence rate typically depends on the Lipschitz constants of gradients, which further depend on the range of weights and targets. Motivated by this fact, we further define a range parameter $b$ which describes the range of weights and targets that our oracle accepts. Formally, for all $b>0$, we define

Clearly $\textsf{Oracle}_{b}$ becomes a stronger as $b$ increases. While access to $\textsf{Oracle}_{b}$ is generally a very mild assumption even when $b$ is large, in order to achieve better computational efficiency, in this section we will be precise about $b$ and aim to invoke $\textsf{Oracle}_{b}$ with $b$ as small as possible.

In the block MDP setup, there are multiple value function classes $\mathcal{F}_{1},\cdots,\mathcal{F}_{H}$. For this setting, we assume access to the regression oracle Eq. RO for each of the classes $\mathcal{F}_{1},\ldots,\mathcal{F}_{H}$.For notational convenience, in this section, when we use the notation $\mathcal{F}$ in the block MDP setting, it can stand for any one of $\mathcal{F}_{1},\dots,\mathcal{F}_{H}$, rather than the full function class $\mathcal{F}_{1}\times\cdots\times\mathcal{F}_{H}$ defined in Section 3. Again, we use $\textsf{Oracle}_{b}$ to denote our oracle, where $b$ denotes that the oracle accepts $[-b,b]$-valued weights and targets.

We first show how to implement AdaCB with the regression oracle. There are three computational tasks in the algorithm which require us to invoke the oracle.

2 requires computing the empirical risk minimizer $\widehat{f}_{m}$.

9 and Option I (4) require computing the candidate action set $\mathcal{A}(x;\mathcal{F}_{m})$ for any given $x$.

Option II (4) requires computing the confidence width $w(x;\mathcal{F}_{m})$ for any given $x$.

The first task is exactly a least squares problem, and we directly solve it using $\textsf{Oracle}_{1}$. The second and third tasks are more complicated, and we need to design additional subroutines to reduce them to weighted least squares regression. Lying at the heart of the reductions are two basic computational subroutines: ConfBound and ConfBoundDiff, which we present in Algorithm 3 and Algorithm 4 respectively. Specifically,

ConfBound is designed to efficiently compute the upper confidence bound

for any given context-action pair $(x,a)\in\mathcal{X}\times\mathcal{A}$, based on a sample history $\mathcal{H}$ and confidence radius $\beta$. It can be efficiently implemented with $\textsf{Oracle}_{\beta/\alpha}$ given precision $\alpha$, as pointed out in Krishnamurthy et al. (2017) and Foster et al. (2018).

ConfBoundDiff is designed to efficiently compute the action difference lower confidence bound

for any given context $x\in\mathcal{X}$ and actions $a_{1},a_{2}\in\mathcal{A}$, based on a sample history $\mathcal{H}$ and confidence radius $\beta$. It can be used to identify whether an action $a_{1}$ is guaranteed to dominate another action $a_{2}$ on a context $x$, and can be efficiently implemented with $\textsf{Oracle}_{\beta/\alpha}$ given precision $\alpha$.

Building on ConfBound and ConfBoundDiff, we design a subroutine CandidateSet (see Algorithm 5) that accomplishes the the second task above, i.e., (approximately) computing $\mathcal{A}(x;\mathcal{F}_{m})$ for any $x$. Then, building further on CandidateSet and ConfBound, we design a subroutine ConfWidth (see Algorithm 6) that accomplishes the third task above, i.e., computing $w(x;\mathcal{F}_{m})$ for any $x$. Therefore, by applying ConfBound, ConfBoundDiff, CandidateSet and ConfWidth as subroutines, we can efficiently implement AdaCB using $\textsf{Oracle}_{\beta/\alpha}$.

We now show how to implement RegRL with the regression oracle. There are two computational tasks in RegRL which require us to invoke the oracle.

5 requires computing the empirical risk minimizer $\widehat{f}_{m}$.

7 requires computing the star hull upper confidence bound $\macc@depth\char 1\relax\frozen@everymath{\macc@group}\macc@set@skewchar\macc@nested@a 111{}_{h}^{(k)}(x,a)$ for any given $(x,a)$ pair.

The first task is exactly a least squares problem, and we directly solve it using $\textsf{Oracle}_{1}$. The second task can be accomplished by the subroutine ConfBound (Algorithm 3), as long as we can solve weighted least squares regression over the star hull of each $\mathcal{F}_{h}$

Suppose weights in Eq. Star-RO are bounded by $W$ and targets are bounded by $B$. Then for any $\alpha>0$, we can find an $\alpha$-approximate solution to Eq. Star-RO using $\mathcal{O}(BW/\alpha)$ calls to $\textsf{Oracle}_{\mathcal{O}(BW/\alpha)}$ for Eq. RO.

Therefore, by applying ConfBound with the reduction above as a subroutine, RegRL can be efficiently implemented with $\textsf{Oracle}_{\beta/\alpha^{2}}$.

2 Computational Complexity

Theoretical guarantees for the subroutines ConfBound, ConfBoundDiff, CandidateSet and ConfWidth are deferred to Appendix A. Here we summarize the total computational complexity for our algorithms based on these reductions.

For AdaCB, we set the precision $\alpha=\mathcal{O}(1/T)$ for ConfBound, ConfBoundDiff, CandidateSet and ConfWidth so that the error does not degrade the algorithm’s instance-dependent performance beyond additive constants. In total, when $\mathcal{F}$ is convex, AdaCB calls $\textsf{Oracle}_{\widetilde{\mathcal{O}}(T)}$ for $\widetilde{\mathcal{O}}(AT)$ times over $T$ rounds, and when $\mathcal{F}$ is non-convex, AdaCB calls $\textsf{Oracle}_{\widetilde{\mathcal{O}}(T)}$ for $\widetilde{\mathcal{O}}(AT^{3})$ times over $T$ rounds. We remark that the total time spent by AdaCB outside of these regression oracle calls is $O(A)$ in each round.

Experiments

To evaluate the empirical performance of AdaCB, we replicated a simplified version of the large-scale contextual bandit evaluation setup of Bietti et al. (2018), which compares a number of contextual bandit algorithms based on either cost-sensitive classification oracles or regression oracles on over 500 multiclass, multi-label, and cost-sensitive classification datasets. We found that AdaCB typically enjoys superior performance, especially on challenging datasets with many actions.

Following Bietti et al. (2018), we use a collection of 516 multiclass classification datasets from the openml.org platform.We omit datasets $\{8,189,197,209,223,227,287,294,298\}$ from the collection used in Bietti et al. (2018), as these are regression datasets that were rounded to integer targets. This brings the count from 525 to 516. This collection includes many standard datasets, including the UCI datasets used in Foster et al. (2018); see Bietti et al. (2018) for details. Beyond this collection, Bietti et al. (2018) also used 5 multilabel datasets and 3 cost-sensitive datasets; we omit these for simplicity.

For each dataset, we simulate bandit feedback by withholding the true label. We work with losses rather than rewards, and provide a loss of if the learner predicts the correct label, and $1$ otherwise. We randomly shuffle the examples in each dataset, but use the same fixed shuffle across all algorithms.

All of our baseline algorithms are based on classification or regression oracles. We use their implementations in VW, which incorporate modifications to allow them to run in an online fashion with the oracle above. For the classification-based algorithms, VW uses an additional reduction layer which reduces classification to regression. Following Bietti et al. (2018), we use the following algorithms.

The standard $\varepsilon$-Greedy exploration strategy (Langford and Zhang, 2008), as well as a purely greedy variant, Greedy.

Bagging, also known as bootstrap Thompson sampling (Agarwal et al., 2014; Eckles and Kaptein, 2014; Osband et al., 2016), which attempts to approximate the Thompson sampling algorithm.

Online Cover, a heuristic version of the ILTCB strategy of Agarwal et al. (2014). ILTCB itself provides an optimal and efficient reduction from stochastic contextual bandits to cost-sensitive classification, and represents the state of the art from that line of research.

RegCB (Russo and Van Roy, 2013; Foster et al., 2018), an approximate version of the general function class UCB algorithm based on regression oracles. This algorithm was found to have the best overall performance in Bietti et al. (2018), though it does not achieve the minimax rate for contextual bandits. We only evaluate the optimistic variant (RegCB-Opt), not the elimination-based variant (RegCB-Elim), as the former typically performs much better.

We refer to Bietti et al. (2018) for more details on the algorithm configurations and hyperparameters.

Beyond these algorithms, we also evaluate against SquareCB (Foster and Rakhlin, 2020), which is the first optimal online regression oracle-based contextual bandit algorithm. SquareCB applies the inverse gap weighting strategy in Eq. 7, but uses all actions rather than adaptively narrowing to a smaller candidate set as in AdaCB. Our implementation applies IGW at each step $t$ with a learning rate $\gamma_{t}$. We set $\gamma_{t}=\gamma_{0}t^{\rho}$, where $\gamma_{0}\in\{10,50,100,400,700,10^{3}\}$ and $\rho\in\left\{.25,.5\right\}$ are hyperparameters.

We implemented a variant of AdaCB in VW, with a few practical simplifications.The precise version of VW used to run the experiments may be found at https://github.com/canondetortugas/vowpal_wabbit/tree/. First, rather than using an offline ERM oracle (as in Eq. RO), we modify the algorithm to work with the online regression oracle provided in VW by following the strategy of Foster and Rakhlin (2020). The protocol for the oracle is as follows: At each round, we provide the context $x_{t}$, the oracle provides a predicted reward $\hat{y}_{t}(a)$ for each action, then we select an action $a_{t}$ and update the oracle with $(x_{t},a_{t},r_{t}(a_{t}))$. Instead than applying IGW to the empirical risk minimizer as in Algorithm 1, we simply apply it to $\hat{y}_{t}$. This strategy is natural because the protocol above is exactly what is implemented by the base learner in VW, and thus allows us to take advantage of VW’s fast online regression implementation.

For our second simplification, rather than computing $\mathcal{A}_{t}(x;\mathcal{F}_{t})$ using the reductions from Section 4 (which also require an offline oracle), we use a sensitivity-based heuristic that takes advantage of the online oracle. This is described in Section 7.1 of Krishnamurthy et al. (2017), and is also used by the VW implementation of RegCB.

Finally, rather than using a data-dependent learning rate, we set $\gamma_{t}=\gamma_{0}t^{\rho}$, where $\gamma_{0}\in\{10,50,100,400,700,10^{3}\}$ and $\rho\in\left\{.25,.5\right\}$ are hyperparameters (the same as for SquareCB). We set the confidence radius as $\beta^{2}_{t}=c_{0}\log(Kt)$, where $c_{0}\in\{10^{-1},10^{-2},10^{-3}\}$ is another hyperparameter.

We evaluate the performance of each algorithm on a given dataset using the progressive validation (PV) loss (Blum et al., 1999). For each algorithm above, we choose the best hyperparameter configuration for a given dataset based on the PV loss.

To compare each pair of algorithms on a given dataset, we use the notion of a statistically significant win or loss defined in Bietti et al. (2018), which is based on an approximate Z-test. For each algorithm pair, we count the total number of significant wins / losses, using the best configuration for each dataset.

To evaluate performance on hard exploration problems, we restricted only to datasets with $A\geq{}3$ actions. Head-to-head results are displayed in Table 1. For this subset of datasets, we find that AdaCB has the best overall performance, and has a (large) positive win-loss difference against all of the baselines. This suggests that AdaCB may be a promising approach for solving challenging exploration problems.

Head-to-head results across all datasets are displayed in Table 2. We find that for the full collection of datasets, RegCB (Foster et al., 2018) has the best overall performance, with a positive win-loss difference against every algorithm. AdaCB has strong performance overall, but narrowly loses to RegCB and Online Cover, with a positive win-loss difference against all other algorithms. The strong performance of RegCB mirrors the findings of Bietti et al. (2018). They observed that many of the datasets in the OpenML collection are “easy” for exploration in the sense that 1) they have few actions (in fact, around 400 datasets have only 2 actions), and 2) even the simple greedy strategy performs well; RegCB seems to be good at exploiting this. It would be interesting to understand whether we can make AdaCB eliminate actions even more aggressively for the easy problems on which RegCB excels, and whether we can develop theory to support this.

Discussion

We have developed efficient, instance-dependent algorithms for contextual bandits and reinforcement learning with function approximation. We showed that disagreement coefficients and related combinatorial parameters play a fundamental role in determining the optimal instance-dependent rates, and that algorithms that adapt to these parameters can be simple and practically effective. Our results suggest many fruitful directions for future research.

For contextual bandits, there are a number of very interesting and practically relevant questions:

For adversarial contexts, can we develop instance-dependent algorithms that are efficient in terms of online regression oracles, as in Foster and Rakhlin (2020)?

Can we extend our algorithms and complexity measures to optimally handle infinite actions?

Beyond these questions, we hope to see the various gaps between our upper and lower bounds closed.

For reinforcement learning, we are excited to see whether our analysis techniques can be applied more broadly, and to develop more refined lower bounds that better reflect the role of disagreement in determining the difficulty of exploration. On the technical side, there are many possible improvements to Theorem 3.1. For example, is it possible to develop best-of-both-worlds guarantees similar to those attained by AdaCB, or even to efficiently attain the minimax rate in the absence of bounded gap and disagreement coefficient? Can we improve the dependence on $S$, $A$, and so forth to match the optimal rates for the tabular setting?

We thank Alekh Agarwal, Haipeng Luo, Akshay Krishnamurthy, Max Simchowitz, and Yunbei Xu for helpful discussions. We thank Alberto Bietti for help with replicating the setup from Bietti et al. (2018). DF acknowledges the support of NSF Tripods grant #1740751. AR acknowledges the support of ONR awards #N00014-20-1-2336 and #N00014-20-1-2394. DSL and YX acknowledge the support of the MIT-IBM Watson AI Lab.

References

Organization of Appendix

This appendix is organized as follows. Appendix A contains details for the computational results presented in Section 4. Part I contains proofs for our contextual bandit results, and Part II contain proofs for our reinforcement learning results.

Appendix A Computational Guarantees

In what follows, we establish computational guarantees for the subroutines ConfBound, ConfBoundDiff, CandidateSet and ConfWidth.

We first provide guarantees for ConfBound and ConfBoundDiff, in Lemma A.1 and Lemma A.2 respectively. Lemma A.1 is adapted from known results in the literature. The proof of Lemma A.2 can be found in Section A.1.

Consider the AdaCB setting. Let $\mathcal{H}_{m}=\{(x_{t},a_{t},r_{t}(a_{t}))\}_{t=1}^{t_{m-1}}$. If the function class $\mathcal{F}$ is convex and closed under pointwise convergence, then for any $x\in\mathcal{X}$, the computation procedures

terminate after $\mathcal{O}(\log(1/\alpha))$ calls to $\textsf{Oracle}_{1}$, and the returned values satisfy

If the function class $\mathcal{F}$ is non-convex, then the required number of oracle calls is $\mathcal{O}(1/\alpha^{2}\log(1/\alpha))$.

Consider the AdaCB setting. Let $\mathcal{H}_{m}=\{(x_{t},a_{t},r_{t}(a_{t}))\}_{t=1}^{t_{m-1}}$. If the function class $\mathcal{F}$ is convex and closed under pointwise convergence, then for any $x\in\mathcal{X}$ and $a_{1},a_{2}\in\mathcal{A}$, the computation procedure

terminates after $\mathcal{O}(\log(1/\alpha))$ calls to $\textsf{Oracle}_{1/\alpha}$, and the returned values satisfy

If the function class $\mathcal{F}$ is non-convex, then the required number of oracle calls is $\mathcal{O}(1/\alpha^{2}\log(1/\alpha))$.

Lemma A.1 and Lemma A.2 show that ConfBound and ConfBoundDiff compute the desired confidence bounds up to a precision of $\alpha$ in $\mathcal{O}(\log(1/\alpha))$ or $\mathcal{O}(1/\alpha^{2}\log(1/\alpha))$ iterations. Note that both Lemma A.1 and Lemma A.2 are stated in the AdaCB setting. For the sake of brevity, we omit the guarantee of ConfBound for the RegRL setting here, as it is essentially the same as Lemma A.1, with only notations changing.

We now provide guarantees for ConfBoundDiff and ConfWidth. All the results in this part are stated in the AdaCB setting, as CandidateSet and ConfWidth are only required for AdaCB.

We discuss two cases: when $\mathcal{F}$ is a product function class, it is possible for CandidateSet to precisely compute $\mathcal{A}(x;\mathcal{F}_{m})$; when $\mathcal{F}$ is not a product function class, precisely computing $\mathcal{A}(x;\mathcal{F}_{m})$ becomes difficult, yet it is possible for CandidateSet to precisely determine whether $|\mathcal{A}(x;\mathcal{F}_{m})|>1$, which is already sufficient for ConfWidth to precisely compute $w(x;\mathcal{F}_{m})$ and for AdaCB to achieve all the statistical guarantees stated in Section 2.

When $\mathcal{F}$ is a product function class, i.e. $\mathcal{F}=\mathcal{G}^{\mathcal{A}}$ for some function class $\mathcal{G}$, it is possible for AdaCB to maintain each version space $\mathcal{F}_{m}$ as a product function class, which makes it especially simple to compute $\mathcal{A}(x;\mathcal{F}_{m})$. To ensure the product structure of $\mathcal{F}_{m}$, we need to make slight modifications to the definition of $\mathcal{F}_{m}$ in 3 of AdaCB.

If $\mathcal{F}$ is a product function class, i.e., $\mathcal{F}=\mathcal{G}^{\mathcal{A}}$ for some $\mathcal{G}$, then at 3 of Algorithm 1, we define $\mathcal{F}_{m}=\prod_{a\in\mathcal{A}}\mathcal{G}_{m,a}$, where

It is not difficult to see that the above modifications do not affect AdaCB’s statistical guarantees in Section 2,In order to achieve the same regret bound, we need to adjust the configuration of $\beta_{m}$ from $16(M-m+1)\log(2|\mathcal{F}|T^{2}/\delta)$ to $16(M-m+1)\log(2|\mathcal{G}|AT^{2}/\delta)$. or ConfBound’s computational guarantee in Lemma A.1. The following lemma demonstrates the value of the product structure of $\mathcal{F}_{m}$.

If $\mathcal{F}^{\prime}\subset\mathcal{F}$ is a product function class, then for any $x\in\mathcal{X}$,

Lemma A.3 implies that if $\mathcal{F}$ is a product function class (and thus $\mathcal{F}_{m}$ is a product function class under Definition A.1), then both $\mathcal{A}(x;\mathcal{F}_{m})$ and $w(x;\mathcal{F}_{m})$ can be explicitly expressed in terms of the upper and lower confidence bounds $\sup_{f\in\mathcal{F}_{m}}f(x,a)$ and $\inf_{f\in\mathcal{F}_{m}}f(x,a)$. Since ConfBound enables us to compute $\sup_{f\in\mathcal{F}_{m}}f(x,a)$ and $\inf_{f\in\mathcal{F}_{m}}f(x,a)$ for all $a\in\mathcal{A}$ with high accuracy (see Lemma A.1), we can precisely compute $\mathcal{A}(x;\mathcal{F}_{m})$ and $w(x;\mathcal{F}_{m})$ by calling $\textsf{CandidateSet}(x,\mathcal{H}_{m},\beta_{m},\alpha)$ and $\textsf{ConfWidth}(x,\mathcal{H}_{m},\beta_{m},\alpha)$ with sufficiently small $\alpha$, which can be efficiently implemented with $\textsf{Oracle}_{\beta/\alpha}$ (as ConfBound can be efficiently implemented with $\textsf{Oracle}_{\beta/\alpha}$).