
## Appendix A. Proofs A.1 Properties Of Transitive-Feasible Value Functions

Basic properties of the Bellman operator, which we often use without a reference are the following.

Lemma 36. Let v be any value function and let c *be a scalar. Then:*
L(v + c1) = Lv + γc1.

Lemma 37 (Monotonicity). Let P *be a stochastic matrix. Then both the linear operators* P and (I − γP)
−1 *are monotonous:*

$$\begin{array}{l}{{x\geq y\Rightarrow P x\geq P y}}\\ {{x\geq y\Rightarrow(I-\gamma P)^{-1}x\geq(I-\gamma P)^{-1}y}}\end{array}$$

for all x and y.

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}.$$

Proof. Let P
∗ and r
∗ be the transition matrix and the reward vector of the policy. Then, we have using Lemma 37:

$$\begin{array}{c}{{v\geq L v-\epsilon{\bf1}}}\\ {{v\geq\gamma P^{*}v+r^{*}-\epsilon{\bf1}}}\\ {{({\bf I}-\gamma P^{*})v\geq r^{*}-\epsilon{\bf1}}}\\ {{v\geq({\bf I}-\gamma P^{*})^{-1}\,r^{*}-\frac{\epsilon}{1-\gamma}}}\end{array}$$

Lemma 38. A value function v satisfies Av ≥ b if an only if v ≥ Lv*. In addition, if* v is feasible in (ABP–L∞)*, then* v ≥ v
∗.

Proof. The backward implication of the first part of the lemma follows directly from the definition. The forward implication follows by an existence of λ = 0, λ 0 = k [Av − r]+ k∞,
which satisfy the constraints. The constraints on π are independent and therefore can be satisfied independently. The second part of the lemma also holds in ALPs (de Farias, 2002) and is proven identically.

$$\square$$
