Approximate Value Iteration

We will make the following assumption.

$$\vert\vert V_{k+1} - LV_k\vert\vert \leq \epsilon$$

$$LV_0 - \epsilon*\vec{1} \leq V_1 \leq LV_0 - \epsilon*\vec{1}$$

This implies that using L operator on the inequality

$$LV_0^2 - \lambda \epsilon*\vec{1} \leq LV_1 \leq LV_0^2 -\lambda \epsilon*\vec{1}$$

We have also the next inequality

$$LV_1 - \epsilon*\vec{1} \leq V_2 \leq LV_1 - \epsilon*\vec{1}$$

Using both inequalities

$$LV_0^2 - (\lambda \epsilon + \epsilon)*\vec{1} \leq LV_1 \leq LV_0^2 -(\lambda \epsilon+\epsilon)*\vec{1}$$

Thus for each k we have

$$\vert\vert V_k - L^kV_0\vert\vert \leq \epsilon \sum_{i=0}^{k-1}\lambda^i \leq \frac{\epsilon}{1-\lambda}$$

If we look at Therefore,

$$\vert\vert\tilde{V} - V^*\vert\vert \leq \frac{\epsilon}{1-\lambda}.$$

Although calculations are much simpler than in PI. The method is less natural.