new contextual bandit problems.

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

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

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

**Agnostic setting.** Let $\Pi\subset{{\mathcal{A}}}^{{{\mathcal{X}}}}$ be a class of *policies* (i.e., decision functions) that map contexts $x\in{{\mathcal{X}}}$ to actions $a\in{{\mathcal{A}}}$, and 