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

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

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

### Agnostic Approaches

Papers studying contextual bandits in the agnostic setting aim to design general-purpose and computationally-tractable algorithms that are provably efficient for any given policy class $\Pi$ while avoiding the computational complexity of enumerating over $\Pi$ (as the size of $\Pi$ is 