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

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

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

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

We make some remarks on the above two settings from a pure modeling perspective. First, the agnostic setting does not require realizability and is more general than the realizable setting. Indeed, given any function class 