Evaluation Of Approximate Policy Iteration

In this section will make two assumptions on our approximation. (Both of them are rather strong.) Assume the algorithm outputs $V_1,\pi_1,V_2,...$ such that

1.

$\forall k \vert\vert V_k - V^{\pi_{k}} \vert\vert < \epsilon$

2.

$\forall k \vert\vert L_{\pi_{k+1}}V_{k} - LV_k\vert\vert < \delta$

For some positive scalars $\epsilon$ and $\delta$.

Theorem 11.2   The sequence of policies $\pi_k$ generated by the approximate policy iteration algorithm satisfies

$$\lim_{k \rightarrow \infty}sup\vert\vert V^{\pi_{k}} - V^{*} ... ...t\vert \leq \frac{\delta + 2 \lambda \epsilon}{(1 - \lambda)^2}$$

Proof:We will first show that a policy generated by the policy update can not be much worse than the current policy. We will prove it by using the following lemmas

Lemma 11.3   Let $\pi$ be some policy and V is a value function satisfies $\vert\vert V - V^\pi\vert\vert \leq \epsilon$for some $\epsilon \geq 0$.
Let $\bar{\pi}$ be a policy that satisfies:

$$(L_{\bar{\pi}}V)(s) \geq (LV)(s) - \delta$$

for some $\delta \geq 0$then

$$V^{\bar{\pi}}(s) \geq V^{\pi}(s) - \frac{\delta + 2\lambda \epsilon}{(1 - \lambda)}$$

Proof:Let

$$\beta = \max_s\{V^{\pi}(s) - V^{\bar{\pi}}(s)\}$$

and

$$\vec{1} = (1,1,....1)^t$$

so

$$V^{\bar{\pi}} \geq V^{\pi} - \beta * \vec{1}$$

Hence we will have

$$V^{\bar{\pi}} = L_{\bar{\pi}}V^{\bar{\pi}}$$

$$\geq L_{\pi}(V^{\pi} - \beta * \vec{1}) = L_{\bar{\pi}}V - (\lambda \beta)*\vec{1}$$

Therefore we derive,

1.

$V^{\bar{\pi}} - L_{\bar{\pi}}V + (\lambda \beta)*\vec{1} \geq 0$
>From the hypothesis of the lemma we have,

2.

$0 \geq -L_{\bar{\pi}}V +LV - \delta *\vec{1} \geq -L_{\bar{\pi}}V +L_{\pi}V - \delta *\vec{1}$

Using inequality 1, we obtain

$$V^{\pi} - V^{\bar{\pi}} \leq V^{\pi} - L_{\bar{\pi}}V^{\pi} + (\lambda \beta)*\vec{1}$$

Using inequality 2, we obtain

$$V^{\pi} - V^{\bar{\pi}} \leq V^{\pi} - L_{\bar{\pi}}V^{\pi} +... ...da \beta)*\vec{1} + L_{\bar{\pi}}V - L_{\pi}V + \delta *\vec{1}$$

$$= (L_{\bar{\pi}}V - L_{\bar{\pi}}V^{\pi}) + (V^{\pi} - L_{\pi}V) +(\delta+\beta\lambda)*\vec{1}..$$

$$\leq \lambda\vert\vert V^{\pi} - V\vert\vert*\vec{1} + \lambd... ...V - V^{\pi}\vert\vert*\vec{1} + (\delta + \beta\lambda)*\vec{1}$$

$$= 2*\lambda*\epsilon + \delta + \beta\lambda$$

Thus we conclude the following:

$$\vert\vert V^{\pi} - V^{\bar{\pi}}\vert\vert = \beta \leq 2*\lambda*\epsilon + \delta + \beta\lambda$$

$$\beta \leq \frac{2\lambda\epsilon + \delta}{1 - \lambda}$$

and the desired result follows.
$\Box$$\beta_k$ be

$$\beta_k = \max_s(V^{\pi_{k+1}} - V^{\pi_{k}})$$

We apply the lemma above with $\pi = \pi_{k}$ and $\bar{\pi} = \pi_{k+1}$
As a result we have

$$\beta_k \leq \frac{2\lambda\epsilon + \delta}{1 - \lambda}$$

We now let $\gamma_k$ to be distance from the optimum. $\gamma_k = \max_s(V^*(s) - V^{\pi_k}(s))$

Lemma 11.4   $\forall k$ $\gamma_{k+1} \leq \lambda\gamma_k + \lambda\beta_k + \delta + 2\lambda\epsilon$

Proof:By the definition of $\gamma_k$:

$$V^{\pi_k} \geq V^* - \gamma_k.$$

$$LV^{\pi_k} \geq L(V^* - \gamma_k) = LV^* - \lambda\gamma_k*\vec{1}$$

we then have (assumption 1)

$$L_{\pi_{k+1}}V^{\pi_{k}} \geq L_{\pi_{k+1}}(V_k - \epsilon) = L_{\pi_{k+1}}V_k - \lambda\epsilon*\vec{1}$$

(assumption 2)

$$L_{\pi_{k+1}}V^{\pi_{k}} \geq LV_k - \delta*\vec{1} - \lambda\epsilon*\vec{1}$$

(assumption 1)

$$L_{\pi_{k+1}}V^{\pi_{k}} \geq L(V^{\pi_k} - \epsilon) +(-\del... ...silon)*\vec{1} = LV^{\pi_k} +(-\delta-2\lambda\epsilon)*\vec{1}$$

(definition of $\gamma_k$)

$$L_{\pi_{k+1}}V^{\pi_{k}} \geq L(V^* - \gamma_k) +(-\delta-2\l... ...1} = V^* + (-\delta-2\lambda\epsilon + \lambda\gamma_k)*\vec{1}$$

Thus
(fixed pint of the operator)

$$V^{\pi_{k+1}}= L_{\pi_{k+1}} V^{\pi_{k+1}}$$

(definition of $\beta_k$)

$$V^{\pi_{k+1}} \geq L_{\pi_{k+1}}( V^{\pi_{k}} - \beta_k) = L_{\pi_{k+1}}V^{\pi_{k}} -\lambda \beta_k*\vec{1})$$

(using the previous)

$$V^{\pi_{k+1}} \geq V^* +(-\delta-2\lambda\epsilon + \lambda\gamma_k -\lambda \beta_k )*\vec{1}$$

This implies that,

$$V^* - V^{\pi_{k+1}} \leq ( \delta +2\lambda\epsilon + \lambda\gamma_k +\lambda\beta_k)*\vec{1}.$$

$\Box$will use the former lemma and the $\beta_k$ definition to prove the theorem Since one can easily see from the equation

$$\beta_k \leq \frac{\delta + 2\epsilon\lambda}{1 - \lambda}$$

that bounding is not dependent on k. Therefore, we can define the following

$$\alpha = \frac{\delta + 2\epsilon\lambda}{1 - \lambda}\lambda... ...2\epsilon\lambda = \frac{\delta + 2\epsilon\lambda}{1- \lambda}$$

while $\alpha$ is constant, which is not dependent on K. Then we have

$$\gamma_{k+1} \leq \lambda\gamma_k + \alpha$$

By opening the recursion we will get

$$\lambda^k\gamma_1 + \sum_{i=0}^{k-1}\lambda^i\alpha$$

By taking the limit superior of the equation as $k \rightarrow \infty$ to obtain

$$\lim_{k \rightarrow \infty}\gamma_k = \frac{\alpha }{(1 - \lambda)^2} = \frac{\delta + 2\epsilon\lambda }{(1 - \lambda)^2}$$

which proves the theorem $\Box$