The normkLπv − vkk,c can be expressed as the following linear program:

$$\begin{array}{ll}\max&y^{\top}XU(Av-b)\\ \mbox{s.t.}&y\leq1\\ &1^{\top}y\leq k\\ &y\geq0\end{array}\tag{15}$$

Here, the matrix X : *|S| × |S| · |A|* selects the subsets of the Bellman residuals that correspond the the policy as defined:

$$X(s,(s^{\prime},a^{\prime}))={\begin{cases}\pi(s^{\prime},a^{\prime})&{{\mathrm{when~}}s=s^{\prime}}\\ 0&{{\mathrm{otherwise}}}\end{cases}}.$$

It is easy to shows that v − Lπv = X(Av − b). Note that XU = UX from the definition of U.

Clearly, when π ∈ {0, 1} is deterministic the linear programs (14) and (15) are identical.

When the policy π is stochastic, assume an optimal solution y of (15) and let z = XTy.

Then, z is feasible in (14) with the identical objective value, which shows the inequality.

## 5. Solving Bilinear Programs

This section describes methods for solving approximate bilinear programs. Bilinear programs can be easily mapped to other global optimization problems, such as mixed integer linear programs (Horst and Tuy, 1996). We focus on a simple iterative algorithm for solving bilinear programs approximately, which also serves as a basis for many optimal algorithms.

Solving a bilinear program is an NP-complete problem (Bennett and Mangasarian, 1992). The membership in NP follows from the finite number of basic feasible solutions of the individual linear programs, each of which can be checked in polynomial time. The NP-hardness is shown by a reduction from the SAT problem.

There are two main approaches to solving bilinear programs optimally. In the first approach, a relaxation of the bilinear program is solved. The solution of the relaxed problem represents a lower bound on the optimal solution. The relaxation is then iteratively refined, for example by adding cutting plane constraints, until the solution becomes feasible. This is a common method used to solve integer linear programs. The relaxation of the bilinear program is typically either a linear or semi-definite program (Carpara and Monaci, 2009).

In the second approach, feasible, but suboptimal, solutions of the bilinear program are calculated approximately. The approximate algorithms are usually some variation of algorithm 2. The bilinear program formulation is then refined - using concavity cuts (Horst and Tuy, 1996) - to eliminate previously computed feasible solutions and solved again. This procedure can be shown to find the optimal solution by eliminating all suboptimal feasible solutions.

The most common and simplest approximate algorithm for solving bilinear programs is algorithm 2. This algorithm is shown for the general bilinear program (BP–m), where f(*w, x, y, z*) represents the objective function. The minimizations in the algorithm are linear