The bilinear program formulation in (ABP–L1) can be further strengthened when an upper bound on the state-visitation frequencies is available.

$$\begin{array}{c c c}{{\min_{\pi\,\mid\lambda,v}}}&{{\pi^{\mathsf{T}}U\lambda-\alpha^{\mathsf{T}}v}}\\ {{\mathrm{s.t.}}}&{{B\pi=\mathbf{1}}}&{{A v-b\geq\mathbf{0}}}\\ {{}}&{{\pi\geq\mathbf{0}}}&{{\lambda\geq A v-b}}\\ {{}}&{{}}&{{\lambda\geq\mathbf{0}}}\\ {{}}&{{}}&{{v\in\mathcal{M}}}\end{array}$$ (ABP-$U$)
$$v\in{\mathcal{M}}$$

Here U : *|S| · |A| × |S| · |A|* is a matrix that maps a policy to bounds on state-action visitation frequencies. It must satisfy that:
π(*s, a*) = 0 ⇒ (π TU)(*s, a*) = 0 ∀s ∈ S ∀a ∈ A.

Remark 18. One simple option is to have U represent a diagonal matrix of ¯u, where ¯u is the bound for all policies π ∈ Π. That is:

$$U((s,a),(s^{\prime},a^{\prime}))=\begin{cases}\bar{u}(s)&s^{\prime}=s\\ 0&\mathrm{otherwise}\end{cases}\quad\forall s,s^{\prime}\in{\mathcal{S}}\;a,a^{\prime}\in{\mathcal{A}}.$$

The formal guarantees for this formulation are as follows.

Theorem 19. Given Assumption 10 *and that for all* π ∈ Π : Pa∈A(π TU)(*s, a*) ≥ u T
π(s),
any optimal solution (˜π, v, ˜ λ, ˜ λ˜0) *of the bilinear program* (ABP–U) *then satisfies:*

$${\tilde{\pi}}^{\mathsf{T}}U{\tilde{\lambda}}-\alpha^{\mathsf{T}}{\tilde{v}}=\|{\tilde{v}}-L{\tilde{v}}\|_{{\tilde{u}}}-\alpha^{\mathsf{T}}{\tilde{v}}\leq\operatorname*{min}_{v\in{\mathcal{K}}\cap{\mathcal{M}}}\left(\|v-L v\|_{{\tilde{u}}}-\alpha^{\mathsf{T}}v\right).$$

Assuming that U is defined as in Remark 18, there exists an optimal solution π˜ *that is* greedy with respect to v˜ *and:*

$$\|v^{*}-v_{\bar{\pi}}\|_{1,\alpha}\leq\operatorname*{min}_{v\in{\mathcal{M}}\cap{\mathcal{K}}}\left(\|v-L v\|_{1,\bar{u}(v)}-\|v^{*}-v\|_{1,\alpha}\right).$$

Here, u¯(v) represents an upper bound on the state-action visitation frequencies for a policy greedy with respect to value function v.

Unlike Theorem 13 and Theorem 17, the bounds in this theorem do not guarantee that the solution quality does not degrade by restricting the value function to be transitivefeasible.

To prove the theorem we first define the following linear program that solves for the L1 norm of the Bellman update Lπ for a value function v.

$$\begin{array}{l l}{{f_{1}(\pi,v)=\operatorname*{min}_{\lambda,\lambda^{\prime}}}}&{{\pi^{\mathsf{T}}U\lambda}}\\ {{\mathrm{s.t.}}}&{{\qquad\mathbf{1}\lambda^{\prime}+\lambda\geq A v-b}}\\ {{}}&{{}}\\ {{}}&{{\lambda\geq\mathbf{0}}}\end{array}$$
$$(10)$$

The linear program (6) corresponds to the bilinear program (ABP–U) with a fixed policy π and value function v. Notice, in particular, that α Tv is a constant.