Notice that operators L˜ and L¯ map value functions to a subset of all states - only states that are sampled. The values for other states are assumed to be *undefined*.

The samples can also be used to create an approximation of the initial distribution, or the distribution of visitation-frequencies of a given policy. The estimated initial distribution α¯ is defined as:

$$\bar{\alpha}(s)=\begin{cases}\alpha(s)&(s,\cdot,\cdot,\cdot)\in\bar{\Sigma}\\ 0&\mathrm{otherwise}\end{cases}.$$

The existing sampling bounds for approximate linear programming focus on bounding the probability that a large number of constraints is violated when assuming a distribution over the constraints (de Farias and van Roy, 2004). The difficulty with this approach is that the bounds on the number of violated constraints do not transform easily to the bounds on the quality of the value function, or the policy. In addition, the constraint distribution is often somewhat arbitrary because it is difficult to define and sampling from the appropriate distributions.

Our approach, on the other hand, is to define properties of the sampled operators that guarantee that the sampling error bounds are small. These bounds do not rely on distributions over constraints and transform directly to bounds on the policy loss. To define bounds on the sampling behavior, we propose the following assumptions.The first assumption limits the error due to missing transitions in the sampled Bellman operator L¯.

Assumption 29 (Constraint Sampling Behavior). For all representable value functions v ∈ M:

$$\mathcal{K}\subseteq\bar{\mathcal{K}}\subseteq\mathcal{K}(\epsilon_{p})$$

The second assumption quantifies the error on the estimation of the transitions of the estimated Bellman operator L˜.

Assumption 30 (Constraint Estimation Behavior). For all representable value functions v ∈ M the following holds:

$$\bar{\cal K}(-\epsilon_{s})\subseteq\tilde{\cal K}\subseteq\bar{\cal K}(\epsilon_{s}).$$

These assumptions are intentionally made generic so that they apply to a wide range of scenarios. Domain specific assumptions are likely to lead to much tighter bounds, but these are beyond the scope of this paper.

Although we define the sampled Bellman operator directly, in practice only its approximate version is typically estimated. The direct definitions are defined only for the sake of theoretical analysis. The sampled matrices used in bilinear program (ABP–L∞) are defined as follows for all (si, aj ) ∈ Σ. ˜

$$\tilde{A}\Phi=\begin{pmatrix}-&\phi(s_{i})^{\mathsf{T}}-\gamma\frac{1}{m}\sum_{s^{\prime}\in s^{\prime}_{1}\ldots s^{\prime}_{m}}P(s_{i},a_{j},s^{\prime})\phi(s^{\prime})^{\mathsf{T}}&-\\ &\vdots&-\end{pmatrix}\quad\tilde{b}=\begin{pmatrix}r(s_{i},a_{j})\\ \vdots\end{pmatrix}\,,$$ $$\tilde{B}(s^{\prime},(s_{i},a_{j}))=\mathrm{I}\left\{s^{\prime}=s_{i}\right\}\quad\forall s^{\prime}\in\tilde{\Sigma}$$
