Therefore, when the SAT is unsatisfiable, the Bellman residual is at least 1 −
γ 2 2
.

The NP-completeness of minv∈M kLv − vk∞ <  follows trivially from Proposition 40.

The proof for kv − Lvk∞ − α Tv is almost identical. The difference is a new state ˆs, such that φ(ˆs) = 1 and α(ˆs) = 1. In that case α Tv = 1 for all v ∈ M. The additional term thus has no effect on the optimization.

The proof can be similarly extended to the minimization of kv −Lvk1,u¯. Define ¯u(Ci) =
1/n and ¯u(lij ) = 0. Then the SAT problem is satisfiable if an only if kv − Lvk1,u¯ = 1 − γ 2.

Note that ¯u, as defined above, is not an upper bound on the visitation frequencies uπ. It is likely that the proof could be extended to cover the case ¯u ≥ uπ by more carefully designing the transitions from Ci. In particular, there needs to be high probability of returning to Ci and ¯u(lij > 0.

## A.3 Equivalence Of Oapi And Api

We first consider L∞-API2 as a modification of L∞-API. L∞-API2 is shown in algorithm 1, where f(π) is calculated using the following program:

$$\begin{array}{ll}\min&\phi\\ \phi,v&\\ \mbox{s.t.}&({\bf I}-\gamma P_{\pi})v+{\bf1}\phi\geq r_{\pi}\\ &-({\bf I}-\gamma P_{\pi})v+{\bf1}\phi\geq-r_{\pi}\\ &v\in{\cal M}\end{array}\tag{27}$$

Proposition 45. L∞-API and L∞-API2 generate the same sequence of policies if the initial policies and tie-breaking is the same.

Proof. The proposition follows simply by induction from Lemma 39. The basic step follows directly from the assumption. For the inductive step, let π 1 i = π 2 i
, where π 1 and π 2 are the policies with (4) and (27). Then from Lemma 39, we have that the corresponding value functions v 1 i = v 2 i + c1. Because π 1 i+1 and π 2 i+1 are chosen greedily, we have that π 1 i+1 = π 2 i+1.

We are ready now to prove the theorem.

Theorem 34. Assume that L∞-API converges to a policy π and a value function v *that* both satisfy: φ = kv − Lπvk∞ = kv − Lvk∞*. Then*

$${\tilde{v}}=v+{\frac{\phi}{1-\gamma}}\mathbf{1}$$

is feasible in the bilinear program (ABP–L∞)*, and it is a fixed point of OAPI. In addition,*
the greedy policies with respect to v˜ and v *are identical.*
Proof. From Proposition 45, L∞-API can be replaced by L∞-API2, which will converge to the same policy π. L∞-API2 will converge to the value function

$$\tilde{v}=v+\frac{\phi}{1-\gamma}{\bf1}.$$
