Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits

Introduction

Algorithms that rely on the “optimism principle” have been a major cornerstone in the study of multi-armed bandit (MAB) and reinforcement learning problems. Roughly speaking, optimistic algorithms are those that choose a deterministic action at each round, based on some optimistic estimate of future rewards. Perhaps the most representative example is the celebrated Upper Confidence Bounds (UCB) algorithm and its many variants. Popularity of optimistic algorithms stems from their simplicity and effectiveness: the analysis of UCB-type algorithms are usually more straightforward than alternative approaches, so they have become the “meta-algorithms” for more complex settings. They are also often preferable to weighted allocations among actions because of the ability to discard sub-optimal actions and achieve superior instance-dependent empirical performances.

Despite their prevalent use in traditional bandit problems, existing UCB-type algorithms have a glaring drawback in contextual MAB settings: their regret often scales with the cardinality of the context space. (Notable exceptions are the special “linear payoff” formulation and its generalized-linear variant .) In particular, despite encouraging empirical observations , optimism-based algorithms provably achieve sub-linear regret only under restrictive distributional assumptions . This motivates the main problem studied in the paper:

Is there a generic principle that ensures that optimistic algorithms are optimal and efficient for general contextual bandit problems?

Interestingly, whether computationally efficient or not, almost all existing solutions to general contextual bandits rely on weighted, randomized allocations among actions at each round—we refer to these as “randomized algorithms” in the paper. Moreover, there is little focus on contextual MAB with infinite actions, which we believe to be a natural setting to illustrate simplicity and universality of optimism-based algorithms. These observations motivate us to search for a new optimism principle in the presence of large context spaces.e is little focus on contextual MAB with infinite actions, which we believe to be a natural setting to illustrate simplicity and universality of optimism-based algorithms. These observations motivate us to search for a new optimism principle in the presence of large context spaces.

2 The contextual MAB problem

The canonical stochastic contextual bandit problem can be described as follows. Let $\mathcal{A}$ be the action set (in the initial parts of the paper, one can think of $\mathcal{A}$ as the integer set $\{1,\dots,K\}$, which we generalize later on), and $\mathcal{X}$ be the space of contexts that supports the distribution $\mathcal{D}_{\mathcal{X}}$ (e.g., $\mathcal{X}$ can be a subset of Euclidean space). For all $x\in\mathcal{X},a\in\mathcal{A}$, denote $\mathcal{D}_{x,a}$ a reward distribution determined by context $x$ and action $a$. At each round $t=1,\dots,T$, the agent first observes a context $x_{t}$ drawn i.i.d. according to $\mathcal{D}_{\mathcal{X}}$. She then chooses an action $a_{t}\in\mathcal{A}$ based on $x_{t}$ and the history $H_{t-1}$ generated by $\{x_{i},a_{i},r_{i}(x_{i},a_{i})\}_{i=1}^{t-1}$, and finally observes the reward $r_{t}(x_{t},a_{t})$, which is conditionally independent and distributed according to the distribution $\mathcal{D}_{x_{t},a_{t}}$. We assume the rewards take values in the interval $$. An admissible contextual bandit algorithm Alg is a (possibly randomized) procedure that associates each realization of$\{H_{t-1},x_{t}\}$with an action$a_{t}$to employ at round$t$.

Previous literature on contextual MAB problems can be sorted into two categories: the realizable setting and the agnostic setting. In the realizable setting, the agent has access to a function class $\mathcal{F}$, with its members $f\in\mathcal{F}$ being mappings from $\mathcal{X}\times\mathcal{A}$ to $$. The following is referred to as the realizability condition :

We call a mapping $\pi:\mathcal{X}\rightarrow\mathcal{A}$ from the context space $\mathcal{X}$ to the action set $\mathcal{A}$ a “policy.” (Those mappings may be referred to more precisely as “deterministic stationary policies;” in this paper we often just refer to them as “policies” with slight abuse of terminology.) Let $\pi_{f^{*}}$, defined by $\pi_{f^{*}}(x)=\argmax f^{*}(x,a)$, be the “ground truth” optimal policy. The cumulative (pathwise) regret of a contextual bandit algorithm Alg compared with the optimal policy $\pi_{f^{*}}$ after $T$ rounds is

and the agent aims to minimize this cumulative regret. The agnostic setting , on the other hand, does not make such realizability assumption; instead, algorithms are compared with the best policy within a given policy class. In this paper we focus on the realizable setting which lends itself more naturally to the design of optimism-based algorithms.

We present some examples of the realizable setting. The most well-studied contextual MAB problems are simple variants of the “linear payoff” model

One motivation towards general function classes is to encompass models of the form

On the computation side, we make the rather benign assumption the the agent has access to a pre-specified least square oracle over $\mathcal{F}$. Formally, after the agent inputs the historical data $\{x_{i},a_{i},r_{i}(x_{i},a_{i})\}_{i=1}^{t-1}$, the least square oracle outputs a solution $\widehat{f}_{t}\in\mathcal{F}$ that provides the best fit, namely,

This is the simplest optimization oracle assumed in the contextual bandit literature. We assume the least square oracle to be deterministic, for simplicity, as there may be multiple solutions to (1.3).

3 Introducing UCCB: two equivalent viewpoints

This subsection will describe the UCCB principle introduced in this paper from two equivalent viewpoints: 1) implicitly, it is an upper confidence bound rule in policy space; and 2) explicitly, it calculates the upper confidence bound via simulating counterfactual action trajectories rather than using the original action trajectory. For illustration purpose we focus on the finite-action setting where $\mathcal{A}=\{1,\dots,K\}$; extension to infinite action spaces will be discussed later in Section 4.

Let $\Pi$ be the policy space that contains all deterministic stationary policies $\pi:\mathcal{X}\rightarrow\{1,\dots,K\}$. The core idea of UCCB is to choose policies that maximize certain upper confidence bounds in the policy space $\Pi$. After initialization, for each round $t$, data $\{(x_{i},a_{i}),r_{i}\}_{i=1}^{t-1}$ is sent to an offline least square oracle to compute the estimator $\widehat{f}_{t}\in\mathcal{F}$. Without the need to “see” $x_{t}$, the agent selects the optimistic policy $\pi_{t}\in\Pi$ (which is a mapping from $\mathcal{X}$ to the action set $\{1,\dots,K\}$) such that

The distribution $\mathcal{D}_{\mathcal{X}}$ is unknown so there are both statistical and computational challenges in the optimization over policies. However, since our proposed policy optimization problem (1.4) is decomposable across contexts, there is an equivalent strategy where no explicit policy optimization is required: at round $t$, after observing $x_{t}$, the agent selects the optimistic action

(ties broken by choosing the action with the smallest index), where $\{\widetilde{a}_{t,i}\}_{i=1}^{t-1}$ is the counterfactual action trajectory for context $x_{t}$, defined as realizations of all past chosen policies $\{\pi_{i}\}_{i=1}^{t-1}$ on the context $x_{t}$. To recover the counterfactual actions, at round $t$, the agent runs an inner loop to sequentially generate $\widetilde{a}_{t,1},\dots,\widetilde{a}_{t,t-1}$: for $i=1,\dots,t-1$,

(ties are broken by choosing the action with the smallest index). Our approach is clearly quite distinct from previous variants of UCB, as we construct confidence bounds by using simulated counterfactual actions rather than using the actual selected actions.

The UCCB principle leads to provably efficient optimism-based algorithms for general function classes: their regret bounds do not scale with the cardinality of the context spaces, and the required offline least square oracle is feasible for most natural function classes.

4 Related literature

We review previous works in the following three areas.

In this paper, we focus on the realizable contextual bandits setting. Here, the minimax regret of stochastic contextual bandits is $O(\sqrt{KT\log|\mathcal{F}|})$ for a general finite function class $\mathcal{F}$. In the non-efficient algorithm Regressor Elimination was proposed to achieve optimal regret. proposed the use of an online regression oracle and gave an optimal and oracle-efficient algorithm called SquareCB, however the online regression oracle is only computationally efficient for specific function classes.

The open problem of optimal realizable contextual MAB with an offline least square oracle was first solved by , with a randomized algorithm called FALCON. One very inspiring aspect of FALCON is that weighted allocation in policy space can be implicitly achieved by weighted allocation over actions under the realizability assumption—this implication was referred to as “bypassing the monster” in . This motivates the investigation in the present paper that considers implicit optimization over policies when designing optimistic algorithms. Unlike the FALCON algorithm, our approach is predicated on computing counterfactual action trajectories.

Variants of LinUCB are well-known to be regret-optimal and efficient for simple variants of (1.1). However, for general function classes, existing variants of UCB typically have their regret scaling with $|\mathcal{X}|$ , except under strong assumptions on the data distribution . UCB has also been used as a subroutines in contextual bandits when the functions in $\mathcal{F}$ admit smoothness or Lipchitz continuity over $\mathcal{X}$ . These works are usually based on discretization of $\mathcal{X}$.

There is far less discussion of the infinite-action contextual bandit problem with general function classes. studies how to reduce realizable contextual MAB with infinite actions to an online learning oracle called knows-what-it-knows (KWIK), but this oracle is only known to exist for restricted function classes. studies how to combine general function classes with a linear action model (our illustrative example (4.1) in Section 4). However, their results crucially rely on the restrictive assumption that the action set $\mathcal{A}$ is the unit ball, and they assume access to the online regression oracle which is not computationally efficient in general. Lastly, studies infinite-action contextual bandits in a quite general agnostic setting. Their formulation and results are quite different from ours, and they do not provide a computationally efficient algorithm.

5 Organization

In Section 2 we introduce an optimal and efficient optimistic algorithm in the finite-action setting, and explain the key ideas underlying its principles. For illustrative purpose we assume the function class $\mathcal{F}$ to be finite in Section 2, and present extensions to infinite function classes in Section 3. In Section 4 we introduce a unified framework for contextual bandits with infinite action spaces, and present several interesting examples for which our work gives rise to the first efficient solutions. In Section 5 we propose an optimistic subroutine to generalize randomized algorithms to the infinite-action setting.

Upper counterfactual confidence bounds

Under Assumption 1 and fixing $\delta\in(0,1)$, set the parameter $\beta_{t}$ in Algorithm 1 to be

Then with probability at least $1-\delta$, for all $T\geq 1$, the regret of Algorithm 1 after $T$ rounds is upper bounded by

Remark: Recall that our offline regression step can be solved by first-order algorithms and does not require any computation related to the confidence interval (i.e., maintaining a subset of $\mathcal{F}$ or inverting the Hessian). Therefore, despite having much broader applicability, Algorithm 1 is also simpler than many variants of UCB from a computational perspective. The only comparable algorithm to Algorithm 1 is a randomized algorithm—FALCON in , which requires $O(T)$ maximizations over actions and $O(\log T)$ calls to the offline least square oracle. However, we believe our optimistic solution should be preferable in many practical settings as we do not require randomization and our regret bound exhibits much smaller constants.

2 Key ideas underlying UCCB

We now explain three key ideas underlying UCCB.

Previous literature typically refers to the optimism principle as choosing the optimistic action that has the largest estimate on the current context —optimism is analyzed in the action space. In contrast, we view policies as decisions and build confidence bounds in policy space. The key step in our approach is to characterize the confidence bounds of the function estimate $\hat{f_{t}}$, which is the output of the least square oracle given the history $H_{t-1}$.

For an admissible non-randomized contextual bandit algorithm, at each round $t$ there exists a deterministic stationary policy $\pi_{t}$ such that the chosen action $a_{t}$ is equal to $\pi_{t}(x_{t})$ for any realization of $x_{t}$. Equivalently, the algorithm selects $\pi_{t}$ based on $H_{t-1}$ and chooses the action $a_{t}=\pi_{t}(x_{t})$ at round $t$. Through this viewpoint, the following lemma is applicable to all admissible non-randomized contextual bandit algorithms:

Consider an admissible non-randomized contextual bandit algorithm that selects $\pi_{t}$ based on $H_{t-1}$ (and chooses the action $a_{t}=\pi_{t}(x_{t})$) at each round $t$. Then $\forall\delta\in(0,1)$, with probability at least $1-\delta/2$, for all $t>K$ and all $\pi\in\Pi$, the estimation error on the expected reward of $\pi$ is bounded by

The proof of Lemma 1 may be interesting in its own right; a proof ketch will be presented in Section 2.3, and full details are deferred to Appendix A.2.

Let $\pi_{t}$ be the policy that chooses action $t$ regardless of $x$ for $t=1,\dots,K$, and from round $K+1$ up to $T$, its actions are given by any deterministic stationary policy. Then for all $T>K$,

The above lemma applies to all admissible non-randomized contextual bandit algorithms that choose each action once at the first $K$ rounds, regardless of the order by which they are chosen. Proof of this lemma follows from the observation that for every $x\in\mathcal{X}$, the historical sum of $\mathds{1}\{\pi_{t}(x)=\pi_{j}(x)\}$ will never exceeds a “per-context entropy” $O(K\log T)$. In short, analyzing confidence bounds in policy space helps us take expectation over the “per-context entropy,” and successfully avoid the dependence on $|\mathcal{X}|$.

Following Lemma 1 and Lemma 2, a natural “upper confidence bound” strategy is to choose the policy that maximizes the following (unrelaxed) upper confidence bound:

where $\Pi_{\mathcal{F}}$ is the policy class defined by $\Pi_{\mathcal{F}}=\{\pi_{f}:\pi_{f}(x)\in\argmax_{a\in\mathcal{A}}f(x,a),\forall x\in\mathcal{X}\}$, which contains $\pi_{f^{*}}$. While we can prove this strategy leads to optimal regret bounds, it is not directly feasible: 1) the distribution $\mathcal{D}_{\mathcal{X}}$ is unknown; and 2) the optimization over policies is computationally intractable. To solve this issue, we introduce two relaxations: we “agnostically” optimize over the full policy space $\Pi$ rather than $\Pi_{\mathcal{F}}$; and we use a simple inequality to relax the confidence bound proved in Lemma 1, which we call the “square trick”.

The inequality (2.1) can be further relaxed to

Simply relax (2.1) by the Arithmetic Mean-Geometric Mean inequality. ∎

By performing the two relaxations stated above, we only need to consider the optimization problem

This is a “per context” optimization problem, where optimality at every context implies optimality of $\pi_{t}$ over the full policy space $\Pi$. The algorithm does not need to calculate $\pi_{t}$ explicitly in every step. Instead, the algorithm observes $x_{t}$, and calculates all the counterfactual actions $\pi_{1}(x_{t}),\pi_{2}(x_{t}),\dots,\pi_{t-1}(x_{t})$ as if the past policies were applied at $x_{t}$. Using these counterfactual actions, the algorithm calculates a counterfactual confidence, and chooses an optimistic action $a_{t}$ that maximize the upper confidence bound stated in (2.3).

The formula to calculate the counterfactual action $\pi_{i}(x_{t})$,

requires us to the compute the sequence $\{\widetilde{a}_{t,i}\}_{i=1}^{t}$ in a recursive manner: for $i=1,\dots,t$, compute

And finally we take $a_{t}=\pi_{t}(x_{t})=\widetilde{a}_{t,t}$. Therefore, we can explain the explicit steps in Algorithm 1 via the following (obvious) equivalence:

After the first $K$ initialization rounds, Algorithm 1 produce the same pathwise actions as those produced by the policies $\{\pi_{t}\}_{t>K}$ chosen by the upper-confidence-bound rule (2.3) and a specific tie-breaking rule (i.e., when there are multiple solutions to (2.3), taking $\pi_{t}$ to be the unique solution such that for all other solutions $\pi^{\prime}$ to (2.3) and all $x\in\mathcal{X}$, the index of the action $\pi_{t}(x)$ is smaller than the index of the action $\pi^{\prime}(x)$).

Based on all the lemmas that we introduce in this subsection, one can prove the $\widetilde{O}(\sqrt{KT\log|\mathcal{F}|})$ regret bound for Algorithm 1 through relatively standard techniques. The full proof is deferred to Appendix A, and a sketch is provided below.

3 Proof sketch of Theorem 1 and Lemma 1

In this subsection we present a proof sketch of Theorem 1 (the cumulative regret of Algorithm 1) and Lemma 1 (confidence bounds in policy space, whose relaxation leads to Lemma 3).

From Lemma 4, we know Algorithm 1 implicitly chooses the optimistic policy $\pi_{t}$ (i.e., solution of (2.3)) at each round $t$. We prove the regret bound on the event where the inequality (2.2) holds true for all $\pi\in\Pi$. From Lemma 3, the measure of this event is at least $1-\frac{\delta}{2}$.

Optimism of Algorithm 1 in policy space suggests that for all $t>K$,

where the first and the last inequality are due to Lemma 3; and the second inequality due to maximization over policies. Therefore, the expected regret incurred at round $t$ is bounded by

Taking the telescoping sum of (2.4) and applying the contextual potential lemma (Lemma 2), we can prove

By Azuma’s inequality and Lemma 4, with probability at least $1-\delta/2$, we can bound the regret by

Finally we combine (2.5) and (2.6) by a union bound to finish the proof.

The proof of Lemma 1 includes three key steps: characterization of the estimation error (inequality (5)); a counting argument (inequality (2.3)); and applying Cauchy-Schwartz inequality to (2.3). Now we describe these key steps.

The following lemma, which holds for arbitrary algorithms, characterizes the estimation errors of an arbitrary sequence of estimators.

For an arbitrary contextual bandit algorithm, $\forall\delta\in(0,1)$, with probability at least $1-{\delta}/2$,

uniformly over all $t\geq 2$ and all fixed sequence $f_{2},f_{3},\dots\in\mathcal{F}$.

Proof of Lemma (5) can be found in Appendix A.2.

We then apply Cauchy-Schwartz inequality to lower bound the left hand side of (2.3), and take $f_{t}=\widehat{f}_{t}$ be the least square solutions to upper bound the right hand side of (2.3).

Generalization to infinite ℱ\mathcal{F}

Extensions of our theory to “infinite” $\mathcal{F}$ with statistical complexity notions of covering number and parametric dimension are straightforward. Technically speaking, we only require some standard uniform convergence arguments to modify Lemma 5. We will first show that our results trivially generalizes to parametric $\mathcal{F}$ with suitable continuity, and then extend our results to general function classes following some more careful covering arguments.

uniformly over $x\in\mathcal{X}$ and $a\in\mathcal{A}$. This case clearly covers many previous structured models (variants of the “linear payoff” formulation (1.1)).

Under Assumption 1 and the assumption (3.1) and fixing $\delta\in(0,1)$, set the parameter $\beta_{t}$ in Algorithm 1 to be

Then Algorithm 1 satisfies that with probability at least $1-\delta$, for all $T\geq 1$,

Remark: While this regret bound has a worse dependence on $K$ in the “linear payoff” formulation (1.1) compared with SupLinUCB in (whose regret is logarithmic in $K$), Algorithm 1 can be applied in more general parametric settings and enjoys much lower computational demands (there is no need to invert any Hessian). While the square-root dependence on $K$ can not be improved for general $\mathcal{F}$ (see the lower bound in ), we can improve this dependence for structured models by applying our results in Section 4.

Our results can be extended to general (possibly non-parametric) function classes via covering numbers and standard uniform convergence techniques. We consider formulation (3.2)—a major target of previous works on general contextual bandits . We assume access to a general function class $\mathcal{G}$ that contains mappings from $\mathcal{X}$ to $$, and assume

Given careful covering arguments proved in , the following extension is straightforward:

Under Assumption 1 and the assumption (3.2), given $T\geq 1$ and $\delta\in(0,1)$, by setting all the parameters $\beta_{t}$ in Algorithm 1 to be a fixed value

Then, Algorithm 1 satisfies that with probability at least $1-\delta$,

A unified framework for infinite action spaces

In this section we study infinite-action contextual bandits to illustrate the simplicity and applicability of the UCCB principle. In context-free settings, discussion on infinite actions can be sorted into two streams. The first stream studies variants of the linear action model. Prominent examples include linearly parametrized bandit , and parametrized bandit with generalized linear model . The second stream is based on discretization over actions and reduction to the finite-action setting (e.g., Lipchitz bandit (). We focus on the first stream here, as it exhibits additional challenges of efficient exploration beyond the finite-action setting.

To focus on the core messages, we assume $\mathcal{F}$ to be finite and function in $\mathcal{F}$ take values in $$. We propose a generic algorithm (Algorithm 2) that achieves

Consider a broader choice of models, which contains generalized linear action models and allows a mapping $\varphi$:

Many real-world, customized pricing and personalized healthcare applications have a high dimensional action set $\mathcal{A}$, but the “effective dimension” of available actions after observing $x$ is usually much smaller. To model these applications, consider the reward model

where for all $x\in\mathcal{X}$ we assume a compact action set $\mathcal{A}(x)\subset\mathcal{A}$, and assume $\mathcal{A}(x)$ is contained in a $d_{x}-$dimensional subspace. When the agent observes context $x$, she can only choose her action from $\mathcal{A}(x)$.

2 Counterfactual action divergence

The main modification required for infinite-action settings is predicated on a central concept called “counterfactual action divergence,” which generalizes the term $({\sum_{i=1}^{n}\mathds{1}\{a=a_{i}\}})^{-1}$ that was used in Algorithm 1. This new concept characterizes “how much information” is learned from action $a$ given a sequence $\{a_{i}\}_{i=1}^{n}$, on the “fixed-$x$-model.”

For fixed integer $n$, a context $x$, an action $a$ and a sequence of actions $\{a_{i}\}_{i=1}^{n}$, we say $V_{x}(a||\{a_{i}\}_{i=1}^{n})$ is a proper choice of the counterfactual action divergence between $a$ and $\{a_{i}\}_{i=1}^{n}$ evaluated at $x$, if

We define $V_{x}(a||\emptyset)=\infty$ in the case $n=1$.

Using the definition of counterfactual action divergence, the expectation

can be used to construct an upper confidence bound on the expected reward of policy $\pi$ given the past chosen policies $\{\pi\}_{i=1}^{t-1}$. Similar to the finite-action setting, the agent chooses the optimistic policy $\pi_{t}$ that maximizes this confidence bound, and chooses $a_{t}=\pi_{t}(x_{t})$ without explicitly computing $\pi_{t}$—this is achieved by sequentially recovering counterfactual actions, as will be illustrated in our proposed Algorithm.

Convenient choices of $V_{x}(a||\{a_{i}\}_{i=1}^{n}\}_{i=1}^{n})$ should be taken case by case for different problems. In the following lemma, we present closed-form choices of $V_{x}(a||\{a_{i}\}_{i=1}^{n}\}_{i=1}^{n})$ in all our illustrative examples.

In the illustrative examples, the counterfactual action divergences are given as follows (and taken as $\infty$ when inverse of matrices is not well-defined):

generalized linear action model with heterogeneous action sets (4.3):

where $b_{x,a}$ is the coefficient vector of $a$ with a basis $\{A_{x,1},\dots,A_{x,d_{x}}\}$ of $\mathcal{A}(x)$, i.e.,

3 The algorithm and regret bound

Algorithm 2 essentically provide a reduction from contextual models to the “fixed-$x$-models.” The regret of an optimistic algorithm is usually upper bounded by the sum of confidence bounds. In our case, the sum of expectations (4.4) is decomposable over contexts, so tractability of the “fixed-$x$-models” suffices to make Algorithm 2 provably efficient. Formally, we require regularity conditions so that the “fixed-$x$-models” are solvable by the optimism principle. Motivated by the standard potential arguments used in the linear bandit literature, we make Assumption 2 below. Verification of this assumption on Examples 1-3 will be presented in the next section.

There exists counterfactual action divergences such that the following are satisfied:

i)for all $x\in\mathcal{X}$, there exists $d_{x}$ actions $A_{x,1},\dots,A_{x,d_{x}}\in\mathcal{A}(x)$ such that $V_{x}(a||\{A_{x,i}\}_{i=1}^{d_{x}})<\infty$ for all $a\in\mathcal{A}(x)$.

ii) For all $x\in\mathcal{X}$, there exists $\mathcal{E}_{x}>0$ such that for all $T\geq 1$ and all sequences $\{a_{t}\}_{t=1}^{T}$ that satisfy $\{a_{t}\}_{t=1}^{d_{x}\land T}=\{A_{x,t}\}_{t=1}^{d_{x}\land T}$, we have

for all $x\in\mathcal{X}$, where $\textup{poly}(\cdot)$ is a fixed polynomial-scale function.

Besides the least-square oracle, Algorithm 2 uses two other optimization oracles that are necessary in the infinite-action setting: 1) a deterministic initialization oracle which returns $\{A_{x,i}\}_{i=1}^{d_{x}}$ satisfying Assumption 2 after inputting $\mathcal{A}(x)$ (this is standard for Examples 1-3 using the theory of barycentric spanners, see the next subsection); and 2) a deterministic action maximization oracle whose output is a maximizer of a function over the feasible region $\mathcal{A}(x)$.

After imposing the regularity conditions proposed in Assumption 2, the regret of Algorithm 2 can be bounded as the follows.

Under Assumptions 1 and 2 and fixing $\delta\in(0,1)$, let

Then with probability at least $1-\delta$, for all $T\geq 1$ the regret of Algorithm 2 after $T$ rounds is upper bounded by

This theorem immediately provides regret bounds for all our illustrative examples, which we will discuss in the next subsection.

Finally, we give a high-level interpretation of the average decision entropy $\mathcal{E}$: if the expectation (4.4) is the “discrete” partial gradient of a potential function, then the historical sum has the path independence property—that is, the historical sum of (4.4) can be bounded by the maximum value of a potential function, which is characterized by the average decision entropy $\mathcal{E}$. Since $\mathcal{E}$ is the average rather than the sum of the effective complexities of all “fixed-$x$-models,” UCCB provides a generic solution to achieve optimal regret bounds that do not scale with $|\mathcal{X}|$.

4 Applications in illustrative examples

In this subsection we will carefully go through the three illustrative examples. We summarize the conclusions in the following corollary:

Examples 1-3 satisfy Assumptions 2 with the average decision entropy given by

linear action model (4.1): $\mathcal{E}=d$.

Now we give a verification in the remaining parts of this subsection.

We begin with contextual bandits with linear action model (4.1), with the homogeneous action set $\mathcal{A}$. For this problem, Algorithm 1 only needs to compute the initialization actions $A_{1},\dots,A_{d}$ once, and use them during the first $d$ rounds. This suffices to complete the required initialization for all contexts.

Based on well-known results in the linear bandit literature, it is straightforward to show that $\mathcal{E}=d$, because we can take $\mathcal{E}_{x}=d$ for every per-context model. The details are as follows.

As shown in Statement 1, for all $x\in\mathcal{X}$, we choose the counterfactual action divergence between any $a_{t}$ and any sequence $\{a_{i}\}_{i=1}^{t-1}$ evaluated at $x$ to be

Following the standard approach in the linear bandit literature (e.g., see ), we choose the $d$ initialization actions $\{A_{i}\}_{i=1}^{d}$ to be the barycentric spanner of $\mathcal{A}$. A barycentric spanner is a set of $d$ vectors, all contained in $\mathcal{A}$, such that every vector in $\mathcal{A}$ can be expressed as a linear combination of the spanner with coefficients in $$. An efficient algorithm to find the barycentric spanner for an arbitrary compact set is given in .

Therefore, we obtain for all $T\geq 1$ and all $x\in\mathcal{X}$,

By taking $\{A_{i}\}_{i=1}^{d}$ to be a barycentric spanner of $\mathcal{A}$, setting $\mathcal{E}=d$, and taking $\textup{poly}(\log T)=3\log T$, Assumption 2 holds for problem (4.1). Despite the illustration here, we also note that our Assumption 2 is not restricted to any particular choice of initialization actions and $\mathcal{E}$: there are other ways to choose linearly independent initialization actions, giving rise to a slightly different $\textup{poly}(\log T)$ term in Assumption 2 (see, e.g. [1, Lemma 11]).

4.2 Contextual bandits with generalized linear action model (Example 2).

As shown in Statement 1, given $x\in\mathcal{X}$, we choose the counterfactual action divergence between any $a_{t}$ and any sequence $\{a_{i}\}_{i=1}^{t-1}$ evaluated at $x$ to be

Given $x\in\mathcal{X}$, we take $\{A_{x,i}\}_{i=1}^{d}$ such that $\{\varphi(x,A_{x,i})\}_{i=1}^{d}$ consists of a barycentric spanner of $\{\varphi(x,a):a\in\mathcal{A}\}$ in formulation (4.2) we have asked $\varphi$ to preserve compactness with respect to $a$ (e.g. the continuous ones), so such barycentric spanner must exists.. Note that a different basis $\{A_{x,i}\}_{i=1}^{d}$ should be computed for each $x$. From our previous result (4.6) and the fact $\kappa_{x}\geq 1$, for all $T\geq 1$ and all sequences $\{a_{i}\}_{i=1}^{T}$ that satisfy $\{a_{i}\}_{i=1}^{d_{x}\land T}=\{A_{x,i}\}_{i=1}^{d_{x}\land T}$,

4.3 Contextual bandits with heterogeneous action set (Example 3)

We consider the problem formulation (4.3) where the action set $\mathcal{A}(x)$ is heterogeneous for different $x\in\mathcal{X}$. Note that $\mathcal{A}(x)$ is a compact set contained in a $d_{x}-$dimensional subspace. Given $x\in\mathcal{X}$, we choose $\{A_{x,i}\}_{i=1}^{d_{x}}$ as the barycentric spanner of $\mathcal{A}(x)$ and take $a_{i}=A_{x,i}$ for $i=1,\dots,d_{x}$. As stated in Statement 1, given $x\in\mathcal{X}$, the counterfactual action divergence between $a_{t}$ and $\{a_{i}\}_{i=1}^{t-1}$ evaluated at $x$ is

where $b_{x,a_{t}}$ is the coefficient vector of $a_{t}$ with respect to the basis $\{A_{x,i}\}_{i=1}^{d_{x}}$. From our previous result (4.6) and the fact $\kappa_{x}\geq 1$, for all $T\geq 1$ and all sequences $\{a_{i}\}_{i=1}^{T}$ that satisfy $\{a_{i}\}_{i=1}^{d_{x}\land T}=\{A_{x,i}\}_{i=1}^{d_{x}\land T}$,

Using “optimistic subroutines” to generalize randomized algorithms

What is the connection between our proposed optimistic algorithms and existing randomized algorithms? In this section, we show that by combining the idea of counterfactual confidence bounds and a non-trivial “optimistic subroutine,” we can also generalize an existing randomized algorithm to the infinite-action setting. However, the analysis and implementation of the resulting randomized algorithm is much more complex than the optimistic algorithm we introduced before. Through this extension, we see the simplicity and importance of the optimism principle for complex settings like infinite-action spaces.

The first least-square-oracle-efficient randomized algorithm in the general realizable contextual bandits, FALCON from , is restricted to the finite-action setting. FALCON performs implicit optimization in policy space, but the allocation of policies reduces to a closed-form weighted allocation rule for actions (this design principle also influences the design of UCCB). We find that it becomes more crucial to exploit the counterfactual confidence bounds in the infinite-action setting: the optimization of weighted allocation rules no longer has closed-form solutions, and we need to design a technical “optimistic subroutine” to find feasible weighted allocations.

Algorithm 3 runs in an epoch schedule and only calls the least square oracle at the pre-specified rounds $\tau_{1},\tau_{2},\dots$. We take $\tau_{m}=2^{m}$ for all $m\geq 1$ to simplify the statement of the theorem, though other choices of the epoch schedule are also possible .

Consider the problem formulation (4.1) stated in Example 1, under Assumption 1. Take the epoch schedule $\tau_{m}=2^{m}$ for $m\geq 1$. Let

for $m=2,\dots$, and $\beta_{1}=1$. Then with probability at least $1-\delta$, for all $T\geq 1$, the regret of Algorithm 3 after $T$ rounds is upper bounded by

Theorem 6 can be obtained by modifying the regret analysis of the original FALCON algorithm. (We refer the readers to for the background and intuition of the original FALCON algorithm, especially the “Observation 2” in that paper.) However, the key challenge is to provide an efficient algorithm to find a weighted allocation rule that satisfy both (5.1) and (5.2) in Algorithm 3.

At each round within epoch $m$, Algorithm 4 outputs a probability distribution that satisfies (5.1) and (5.2) within at most $\lceil\frac{4}{\beta_{m}}+8d(\log d+1)\rceil$ iterations.

According to this proposition, the optimistic subroutine outputs an efficient solution that satisfies the requirements (5.1) and (5.2) within finite number of iterations at every rounds. One advantage of Algorithm 3 is that it requires only $O(\log T)$ calls to the least-square oracle. However, the design and analysis of the optimistic subroutine becomes challenging in the infinite-action setting, especially for complex problem formulations. On the other hand, Algorithm 2 exhibits much cleaner structure and a principled analysis that covers many problem formulations of interest.

Conclusion and future directions

In this paper we propose UCCB, a simple generic principle to design optimistic algorithms in the presence of large context spaces. Key ideas underlying UCCB include: 1) confidence bounds in policy space rather than in action space; and 2) the potential function perspective that explains the power of optimism in the contextual setting. We present the first optimal and efficient optimistic algorithm for realizable contextual bandits with general function classes. Besides the traditional finite-action setting, we also discuss the infinite-action setting and provide the first solutions to many interesting models of practical interest.

Moving forward, there are many interesting future directions that may leverage the ideas presented in this work. The principle of optimism in the face of uncertainty plays an essential role in reinforcement learning. Currently the majority of existing provably efficient algorithms are developed for the “tabular” case, and their regret scales with the cardinality of the state space. However, empirical reinforcement learning problems typically have a large state space and rely on function approximation . Motivated by this challenge, a natural next step is to adapt the UCCB principle to reinforcement learning problems with large state space. This paper can be viewed as an initial step towards this goal, as the contextual MAB problem is a special case of episodic reinforcement learning where the episode length is equal to one. Within the scope of bandit problems, UCB-type algorithms are often the “meta-algorithms” for many complex formulations when there is no contextual information. Since UCCB improves over UCB-type algorithms in several fundamental contextual settings, this work may be a building block to combine contextual information and function approximation with more complex formulations such as Gaussian process optimization , bandits with long-term constraints , and bandits in non-stationary environments . We leave these directions to future work.

References

Appendix A Proofs for the finite-action setting

We prove the theorem on the clean event stated in Lemma 3, whose measure is at least $1-\delta/2$. For all $t>K$,

where the first and the last inequality are due to Lemma 3; the second inequality due to maximization over policies.

where the first line uses the equivalence proved in Lemma 4; the second line is due to (A.1); the third line is due to $\beta_{t}\leq\beta_{T}$ and $\sum_{K+1}^{T}1/\sqrt{t}\leq\sqrt{T}$; and the last line is due to the contextual potential lemma (Lemma 2).

By Azuma’s inequality, with probability at least $1-\delta/2$, we can bound the regret by

Therefore, by a union bound and inequalities (A.1) (A.3), with probability at least $1-\delta$, the regret of Algorithm 1 after $T$ rounds is upper bounded by

A.2 Analysis on the confidence

The main goal of this subsection is to prove Lemma 1. For a fixed $f$, we denote $Y_{f,i}=(f(x_{i},a_{i})-r_{i}(x_{i},a_{i}))^{2}-(f^{*}(x_{i},a_{i})-r_{i}(x_{i},a_{i}))^{2}$, $i=1,2,\dots$.

For a fixed $f\in\mathcal{F}$, when conditioned on $\Upsilon_{i-1}$, we have

where the first equation is because $a_{i}=\pi_{i}(x_{i})$ and the fact that $\pi_{i}$ is completely determined by $H_{t-1}$; the second equation is because the independence between $x_{i}$ and $H_{i-1}$; and the third inequality is because $(f(x_{i},\pi_{i}(x))-f^{*}(x_{i},\pi_{i}(x_{i})))^{2}$ depends on $H_{i-1}$ only through $\pi_{i}$.

Applying Lemma 5, we know that $\forall\delta\in(0,1)$, with probability at least $1-{\delta}/2$,

uniformly over all $t\geq K$ and all fixed sequence $f_{K},f_{K+1},\dots\in\mathcal{F}$.

where the first inequalities are due to $\mathds{1}\{\pi(x)=\pi_{i}(x)\}\leq 1$ and the second inequality is (A.4).

Since Algorithm 1 pick all actions exactly once during the first $K$ rounds, $t>K$ will ensure $\sum_{i=1}^{t-1}\mathds{1}\{\pi(x)=\pi(x)\}\geq 1,\forall x\in\mathcal{X}$.

From Cauchy-Schwarz’s inequality, $\forall t>K$, $\forall\pi\in\Pi$,

Combine the above inequality with (A.2.1), we prove

Taking $f_{t}=\widehat{f}_{t}$ in the above inequality, and use the fact $\sum_{i=1}^{t-1}Y_{\widehat{f}_{t},i}\leq 0$ (as the least square solution $\widehat{f}_{t}$ minimizes $\sum_{i=1}^{t-1}(f(x_{i},a_{i})-r_{i}(x_{i},a_{i}))^{2}$), we obtain: with probability at least $1-\delta/2$, $\forall t>K$, $\forall\pi\in\Pi$,

A.2.2 Proof of Lemma 5

We now prove Lemma 5 and the supporting lemmas required to prove Lemma 5.

Fix a $\delta\in(0,1)$. Take $\delta_{t}=\delta/2t^{3}$, and apply a union bound to Lemma 6 with all $t\geq 2$. From

we know that with probability at least $1-\delta/2$,

uniformly over all $t\geq 2$ and all fixed sequence $f_{2},f_{3},\dots\in\mathcal{F}$. $\square$

For a fixed $t\geq 2$ and a fixed $\delta_{t}\in(0,1/e^{2})$, with probability at least $1-\log_{2}(t-1){\delta_{t}}$, we have

We have $|Y_{f,i}|\leq 1,\forall i$. From Lemma 7, for $\delta_{t}/|\mathcal{F}|\leq\delta_{t}<1/e^{2}$, with probability at least $1-\log_{2}(t-1)\delta_{t}/|\mathcal{F}|$,

Applying union bound to all $f\in\mathcal{F}$, we obtain that with probability at least $1-\log_{2}(t-1)\delta_{t}\geq 1-\log_{2}t\delta_{t}$,

which further implies $\forall f\in\mathcal{F}$,

This finish the proof to Lemma 6. $\square$

The following two lemmas are used in the proof of Lemma 6.

Suppose $Z_{1},Z_{2},\dots,Z_{t}$ is a martingale difference sequence with $|Z_{i}|\leq b$ for all $i=1,\dots,t$. Then for any $\delta<1/e^{2}$, with probability at least $1-(\log_{2}t)\delta$,

Fix a function $f\in\mathcal{F}$. Suppose we sample $x$ from the data distribution $\mathcal{D}_{\mathcal{X}}$, and $r(x,a)$ from $\mathcal{D}_{x,a}$. Define the random variable

A.3 Proof of Lemma 2

where the last inequality is due to Jensen’s inequality. By taking expectation on both sides of the above inequality, we prove the lemma. $\square$

Appendix B Proofs for the extensions to infinite function classes

From the well-known result on the covering of $d-$dimensional balls , the covering number of a $d-$dimensional ball with radius $\frac{\Delta}{2}$ and discretization error $\frac{1}{Lt}$ is bounded by $(1+{\Delta}{Lt})^{d}$, so there exists a set $V_{t}$ of size no more than $(1+{\Delta}{Lt})^{d}+1\leq(2+{\Delta}{Lt})^{d}$ that contains $\theta^{*}$ and satisfies

We see $\log|V_{t}|\leq d\log(2+{\Delta}{Lt})$. $\forall f_{\theta}\in\mathcal{F},x\in\mathcal{X},a\in\mathcal{A}$, take $v$ to be the closest point to $\theta$ in $V_{t}$, we have

Sine $V_{t}$ is a finite function class, we can prove a slight modification of Lemma 6, with the result (A.6) becomes

Following the same path in the proof of Lemma 5, we can prove a slight modification of Lemma 5: with probability at least $1-\frac{\delta}{2}$,

uniformly over all $t\geq 2$ and all fixed sequence $f_{2},f_{3},\dots\in\mathcal{F}$.

By setting the parameter $\beta_{t}$ to be

in Algorithm 1, we can prove a slight modification of Theorem 1, with the result being

B.2 Proof of Corollary 3

We introduce the following Lemma adopt from :

$\forall\delta\in(0,1)$, with probability at least $1-\delta$,

for all $1\leq\tau_{1}\leq\tau_{2}\leq T$ and $g\in\mathcal{G}$.

We then prove a slight modification of Lemma 5, with the result (5) becomes

uniformly over all $t\geq 2$ and all fixed sequence $f_{2},f_{3},\dots\in\mathcal{F}$.

By setting the parameter $\beta_{t}$ in Algorithm 1 to be the fixed value

we can prove a slight modification of Theorem 1, with the result being

Appendix C Proofs for the infinite-action setting

We prove the theorem on the clean event stated in Lemma 10, whose measure is at least $1-\delta/2$. For all $t\geq 2$,

where the first and the last inequalities are due to Lemma 10; the second inequality is due to the definition of $\pi_{t}$ in Lemma 11. The above argument implies that for all $t\geq 2$

When $t=1$, inequality (C.1) trivially holds true, because $V_{x}(\pi_{1}(x)||\emptyset)=\infty$ by definition. So inequality (C.1) holds true for all $t\geq 1$.

When $T\leq\mathcal{E}$, we can bound the regret by $\mathcal{E}$. We now give the regret bound for the case $T>\mathcal{E}$. We have the following:

where the first line uses the equivalence proved in Lemma 11; the second line is due to (C.1); the third line is due to $\sum_{t=1}^{T}1/\sqrt{t}\leq\sqrt{T}$; the fourth line is due to $\beta_{T}>\beta_{t}$ and $\beta_{T}>1$ when $T>\mathcal{E}$; and the sixth line is due to the condition II in Assumption 2. By Azuma’s inequality, with probability at least $1-\delta/2$, we can bound the regret by

Therefore, by a union bound and inequalities (C) (C.3), with probability at least $1-\delta$, the regret of Algorithm 1 after $T$ rounds is upper bounded by

Combine the case $T\leq\mathcal{E}$ and $T>\mathcal{E}$ we finish the proof. $\square$

Consider a non-randomized contextual bandit algorithm that selects $\pi_{t}$ based on $H_{t-1}$ and chooses the action $a_{t}=\pi_{t}(x_{t})$ at all rounds $t$. Then $\forall\delta\in(0,1)$, with probability at least $1-{\delta}/2$, we have

uniformly over all $\pi\in\Pi$ and all $t\geq 2$.

For a fixed $f$, we denote $Y_{f,i}=(f(x_{i},a_{i})-r_{i}(x_{i},a_{i}))^{2}-(f^{*}(x_{i},a_{i})-r_{i}(x_{i},a_{i}))^{2}$, $i=1,2,\dots$. From Lemma 5, $\forall\delta\in(0,1)$ , with probability at least $1-{\delta}/2$, we have

uniformly over all $t\geq 2$ and all fixed sequence $f_{2},f_{3},\dots f_{t+1},\dots\in\mathcal{F}$.

Use the fact that $\pi_{i}$ is completely determined by $H_{i-1}$ and independent with $x_{i}$, we obtain:

From the definition of counterfactual action divergence, we know $\forall x\in\mathcal{X}$,

Applying the AM-GM inequality to the above inequality, we obtain

Since $\mathcal{F}$ is bounded by $$, we further obtain

By taking expectation on both side of (C) and using (C.5), we obtain that with probability at least $1-\delta/2$,

uniformly over all $\pi\in\Pi$, all $t\geq 2$ and all fixed sequence $f_{2},f_{3},\dots,\in\mathcal{F}$. Here the first inequality is due to the triangle inequality; the second inequality is due to (C); the last inequality is due to (C.5).

By taking $f_{t}=\widehat{f}_{t}$ the the least square solution that minimizes $\sum_{i=1}^{t-1}(f(x_{i},a_{i})-r_{i}(x_{i},a_{i}))^{2}$, we have $Y_{f_{t},i}\leq 0$ and finish the proof. $\square$

Consider an algorithm that choose policy $\pi_{t}$ by

($A_{x,t}$ is determined the initialization oracle and the input $\mathcal{A}(x)$; the “argmax” problem when $t>d_{x}$ is computed via the action maximization oracle.) Then this algorithm produces the same actions as those produced by Algorithm 2.

The proof to this lemma is straightforward. ∎

Appendix D Proofs for the “optimistic subroutine” in Section 5

In this subsection we prove Proposition 1. Our proof is motivated by Agarwal et. al. [4, Lemma 6, Lemma 7].

We aim to minimize the potential function

where $b_{a}$ is the coefficient vector of $a$ when the basis is the barycentric spanner $\{A_{i}\}_{i=1}^{d}$. We prove that after each iteration, either Algorithm 4 outputs a desired distribution that satisfies both (5.1) and (5.2), or

Since $\Phi$ function is bounded the algorithm must halt within finite iterations. (D.2) is a consequence of the following two lemmas:

If Algorithm 4 does not halt at round $t$, then after the coordinate descent step (5.5) in Algorithm 4, we always have

Now we present the proof of Proposition 1, as well as proofs of Lemma 12 and Lemma 13.

Proof of Proposition 1. From Lemma 12 and Lemma 13 we know that if the algorithm does not halt at round $t$, then $\Phi(q_{t})\leq\Phi(q_{t-\frac{1}{2}})-\frac{1}{4}$. Assume Algorithm 4 does not halt after $t$ rounds. Then we have

Since the initialization actions consist of a barycentric spanner of $\mathcal{A}$, all coordinates of $b_{a}$ is within $$,$\forall a\in\mathcal{A}$. Clearly$\|b_{a}\|\leq\sqrt{d}$for all$a\in\mathcal{A}$. We know that$q_{t}$is a improper distribution with at most$d+t$non-zero supports, so we assume$q_{t}=\sum_{i=1}^{d+t}q_{t}(A_{i})\mathds{1}_{A_{i}}$.

So Algorithm 4 must halt within at most $\lceil\frac{4}{\beta_{m}}+8d(\log d+1)\rceil$ iterations. When it halts, it is straightforward to verify that the output distribution is proper and satisfies both (5.1) and (5.2). $\square$

Proof of Lemma 12. Denote $w(a)=(\widehat{h}(\widehat{a})-\widehat{h}(a))/\beta$. Given an arbitrary improper distribution $q$, we view $\Phi(c\cdot q)$ as a function on the scaling factor $c$. By the chain rule, we can compute the derivative of this function with respect to $c$,

then the coordinate descent step (5.5) is $q_{t}=q_{t-\frac{1}{2}}+\Delta_{t}\mathds{1}_{a_{t}}$.

Combine this inequality with (D.6) we obtain