content_image/326798.jpg
the efficient variance of such an estimator. It is worth studying whether the high-probability, finite sample results in [1] can be extended in this direction, thereby demonstrating a criterion for which efficient value estimation is mathematically indispensable for obtaining the optimal regret decay. 

## 4 Extension of Main ERM Result and Three Examples 

## 4.1 Higher Level Result 

Suppose we observe ( O$_{1}$, . . . , O$_{n}$ ) drawn from a distribution ν$_{n}$ , where each O$_{i}$ ≡ ( X$_{i}$, A$_{i}$, Y$_{i}$ ) takes its values in O ≡ X ×A×Y with A ⊂ [ − 1 , 1]. Like in Section 1.3, X$_{i}$ ∈ X denotes a vec- tor of covariates describing the context preceding the i th action, A$_{i}$ ∈ A denotes the action undertaken in this context and Y$_{i}$ ∈ Y is the corresponding reward. Unlike in Section 1.3, there may be more than two actions and the observations are not necessarily independent and identically distributed (i.i.d.). This extends the setting introduced in Section 1.3, which can be recovered with A = {− 1 , 1 } and ν$_{n}$ equal to a product measure. Throughout we also assume that there exists a distribution P with support on O that will have to do with our limit process. The requirements of this distribution P will become clear in what fol- lows and the worked examples of Sections 4.2, 4.3 and 4.4. We let ‖·‖ denote the L $^{2}$( P ) norm. 

Let Π be a class of policies, i.e. , a set of mappings from X to A , and let Π be its L $^{2}$( P ) closure. We request that Π is not too large, in the sense that 

<img src='content_image/326798.jpg'>

The value of a policy π ∈ Π is quantified via V ( π ). As in our earlier result, the regret is defined as R ( π ) ≡ V ⋆ − V ( π ), where V ⋆ ≡ sup$_{π}$$_{∈}$$_{Π}$ V ( π ). 

