These inequalities can be represented using matrix notation as follows.

$$\begin{array}{c}{{B\pi={\bf1}}}\\ {{\pi\geq{\bf0},}}\end{array}$$
4
where the matrix B : |S| × (*|S| · |A|*) is defined as follows.

$$B(s^{\prime},(s,a))=\begin{cases}1&s=s^{\prime}\\ 0&\mathrm{otherwise}\end{cases}.$$

We use 0 and 1 to denote vectors of all zeros or ones of the appropriate size respectively.

The symbol I denotes an identity matrix of the appropriate dimension.

In addition, a policy π induces a state visitation frequency uπ : S → R, defined as follows:

$$u_{\pi}=\left(\mathbf{I}-\gamma P_{\pi}^{\mathsf{T}}\right)^{-1}\alpha.$$

The return of a policy depends on the state-action visitation frequencies and α Tvπ = r Tuπ.

The optimal state-action visitation frequency is uπ∗ . *State-action visitation frequency* u :
S × A → R is defined for all states and actions. Notice the missing subscript. We use ua to denote the part of u that corresponds to action a ∈ A. State-action visitation frequencies must satisfy:

$$\sum_{a\in{\mathcal{A}}}(\mathbf{I}-\gamma P)^{\mathsf{T}}u_{a}=\alpha.$$

To formulate approximate linear and bilinear programs, it is necessary to restrict the value functions so that their Bellman residuals are non-negative (or at least bounded from below). We call such value functions transitive-feasible and define them as follows.

Definition 3. A value function is *transitive-feasible* when v ≥ Lv. The set of transitivefeasible value functions is:
K = {v ∈ R
|S| v ≥ Lv}.

Given some  ≥ 0, the set of -*transitive-feasible* value functions is:

$${\mathcal{K}}(\epsilon)=\{v\in\mathbb{R}^{|{\mathcal{S}}|}\,|\,v\geq L v-\epsilon{\bf1}\}.$$

Notice that the optimal value function v
∗is transitive-feasible. The following lemma summarizes the key property of transitive-feasible value functions:
Lemma 4. *Transitive feasible value functions form an upper bound on the optimal value* function. If v ∈ K() is an *-transitive-feasible value function, then*

$$v\geq v^{*}-\frac{\epsilon}{1-\gamma}{\bf1}.$$
