For the next part of the proof, we adapt a lemma of Bertsekas and Tsitsiklis (1996, Lemma 6.2, p.277) to fit into our framework. After some manipulation, this lemma can be reformulated as:

$$\left\|\mathcal{V}^{*}-\mathcal{V}_{\pi^{(t+1)}}\right\|_{\infty}\leq\gamma\left\|\mathcal{V}^{*}-\mathcal{V}_{\pi^{(t)}}\right\|_{\infty}+\frac{2\gamma}{1-\gamma}\left\|\mathcal{V}_{\pi^{(t)}}-\mathrm{H}\mathbf{w}^{(t)}\right\|_{\infty}.\tag{25}$$

The proof is concluded by substituting Equation (24) into Equation (25) and, finally, induction on t.

## A.3 Proof Of Theorem 4.4

First, note that the equality constraints represent a simple change of variable. Thus, we can rewrite Equation (12) in terms of these new LP variables u fi zi as:

$$\phi\geq\operatorname*{max}_{\mathbf{x}}\sum_{i}u_{\mathbf{z}_{i}}^{f_{i}},$$
$$(26)$$

, **(26)**
where any assignment to the weights w **implies an assignment for each** u fi zi**. After this stage,**
we only have LP variables.

It remains to show that the factored LP construction is equivalent to the constraint in Equation (26). For a system with n variables {X1, . . . , Xn}**, we assume, without loss of**
generality, that variables are eliminated starting from Xn down to X1**. We now prove the**
equivalence by induction on the number of variables.

The base case is n = 0, so that the functions ci(x) and b(x**) in Equation (12) all have**
empty scope. In this case, Equation (26) can be written as:

$$\phi\geq\sum_{i}u^{e_{i}}.$$
i
ei. **(27)**
In this case, no transformation is done on the constraint, and equivalence is immediate.

Now, we assume the result holds for systems with i−**1 variables and prove the equivalence**
for a system with i **variables. In such a system, the maximization can be decomposed into**
two terms: one with the factors that do not depend on Xi**, which are irrelevant to the**
maximization over Xi, and another term with all the factors that depend on Xi**. Using this**
decomposition, we can write Equation (26) as:

$$\begin{array}{r c l}{{\phi}}&{{\geq}}&{{\operatorname*{max}_{x_{1},\ldots,x_{i}}\sum_{j}u_{{\bf z}_{j}}^{e_{j}};}}\\ {{}}&{{}}&{{}}\\ {{}}&{{}}&{{\geq}}&{{\operatorname*{max}_{x_{1},\ldots,x_{i-1}}\left[\sum_{l\,:\,x_{i}\not\in{\bf z}_{l}}u_{{\bf z}_{l}}^{e_{l}}+\operatorname*{max}_{x_{i}}\sum_{j\,:\,x_{i}\in{\bf z}_{j}}u_{{\bf z}_{j}}^{e_{j}}\right].}}\end{array}$$
$$(27)$$
$$(28)$$
$$(29)$$

At this point we can define new LP variables u ez**corresponding to the second term on**
the right hand side of the constraint. These new LP variables **must satisfy the following** constraint:

$$u_{\bf z}^{e}\geq\operatorname*{max}_{x_{i}}\sum_{j=1}^{e}u_{({\bf z},x_{i})}^{e_{j}}[{\bf z}_{j}]\,.$$
ℓ
. **(29)**
463