Greedy policy improvement and finite policy-iteration termination

If $S=\mathrm{\varnothing }$, all statewise inequalities are vacuous and the unique empty policy has no update; assume for the remaining steps that $S\mathrm{\ne }\mathrm{\varnothing }$. [A1] supplies the choice assumption for the path-law value in [F2], and [F3] gives its Bellman fixed-point identity. For each state $s$, [F3] and [F4] give $V^{\pi }(s)={\sum }_{a\in A(s)}\pi (a\mid s)Q_{V^{\pi }}(s,a)\le {\max }_{a\in A(s)}{Q}_{V^{\pi }}(s,a)=(T^{\ast }{V}^{\pi })(s)\mathrm{.}$ The inequality holds because a probability-weighted average of finitely many real numbers is at most their attained maximum [F1, F9].

For every stationary policy $\nu$, the operator $T^{\nu }$ is monotone: if $U(s)\le W(s)$ for every $s$, then each coefficient $\nu (a\mid s)P(s^{\mathrm{\prime }}\mid s,a)$ is nonnegative and $\gamma \ge 0$, so $(T^{\nu }U)(s)\le (T^{\nu }W)(s)$ for every $s$.

If ${\pi }^{\mathrm{\prime }}$ is greedy, its action attains that maximum at every state, so $(T^{{\pi }^{\mathrm{\prime }}}{V}^{\pi })(s)=(T^{\ast }{V}^{\pi })(s)\ge V^{\pi }(s)$ for all $s$.

Define $U_0=V^{\pi }$ and $U_{n+1}=T^{{\pi }^{\mathrm{\prime }}}{U}_n$. Step 2.1 gives $U_0\le U_1$ pointwise; if $U_n\le U_{n+1}$ then step 1.2 gives $U_{n+1}=T^{{\pi }^{\mathrm{\prime }}}{U}_n\le T^{{\pi }^{\mathrm{\prime }}}{U}_{n+1}=U_{n+2}$. By [F11], $(U_n)$ is pointwise nondecreasing.

The zero function belongs to ${\mathbb{R}}^S$, so $({\mathbb{R}}^S,d_{\mathrm{\infty }})$ is nonempty; [F6] makes it complete. By [F5], $T^{{\pi }^{\mathrm{\prime }}}$ is a contraction, so Banach iteration [F7] makes $U_n$ converge in $d_{\mathrm{\infty }}$ to its unique fixed point. By [F3] and uniqueness in [F5], that fixed point is $V^{{\pi }^{\mathrm{\prime }}}$. Since $\mathrm{\mid }{U}_n(s)-V^{{\pi }^{\mathrm{\prime }}}(s)\mathrm{\mid }\le d_{\mathrm{\infty }}(U_n,V^{{\pi }^{\mathrm{\prime }}})$ for every $s$, the convergence is coordinatewise; from $U_n\ge U_0=V^{\pi }$, [F10] yields $V^{{\pi }^{\mathrm{\prime }}}\ge V^{\pi }$ pointwise. This proves the first value comparison.

If $(T^{{\pi }^{\mathrm{\prime }}}{V}^{\pi })(s_0)>V^{\pi }(s_0)$, then $U_1(s_0)>U_0(s_0)$. Step 3.1 makes $U_n(s_0)\ge U_1(s_0)$ for every $n\ge 1$; passing to the limit with [F10] gives $V^{{\pi }^{\mathrm{\prime }}}(s_0)\ge U_1(s_0)>V^{\pi }(s_0)$.

Consider one update in the stated policy-iteration procedure. Exact evaluation returns $V^{{\pi }_k}$ because it is the unique fixed point of $T^{{\pi }_k}$ by [F3] and [F5]. At each state the updated action maximizes $Q_{V^{{\pi }_k}}$; if the old action is already a maximizer it is retained, and otherwise its value is strictly below the attained maximum. Therefore $T^{{\pi }_{k+1}}{V}^{{\pi }_k}\ge V^{{\pi }_k}$ at all states, with strict inequality wherever the policy changed. Steps 4.1–4.2 show that every changed policy weakly improves all state values and strictly improves at least one.

List the finite states as $s_1,\dots ,s_n$ and each action set as $A(s_i)=\{a_{i,1},\dots ,a_{i,m_i}\}$. A deterministic policy is one tuple of indices $(j_1,\dots ,j_n)$ with $1\le j_i\le m_i$, so the set of such policies is a finite Cartesian product by [F12]; for $S=\mathrm{\varnothing }$ it is the singleton empty product. By step 5.1, each changed iteration strictly increases some coordinate and never decreases any, so no policy can recur, since a repeated policy has the same unique exact value vector. Hence at most $N_{\mathrm{d}\mathrm{e}\mathrm{t}}-1$ changes occur and the procedure terminates.

At termination, the update leaves every action unchanged, which by [F8] means the terminal deterministic policy is greedy with respect to its exact value $V^{\pi }$. Thus $T^{\pi }{V}^{\pi }=T^{\ast }{V}^{\pi }$ by [F4]; with [F3], this says $T^{\ast }{V}^{\pi }=V^{\pi }$, so uniqueness in [F5] gives $V^{\pi }=V^{\ast }$.

For any stationary policy $\mu$, $T^{\mu }{V}^{\ast }\le T^{\ast }{V}^{\ast }=V^{\ast }$ because the former is a probability-weighted average of the same action values. Iterating $W_0=V^{\ast }$, $W_{n+1}=T^{\mu }{W}_n$, monotonicity as in step 1.2 makes $W_n$ nonincreasing. The domain is nonempty by step 4.1 and complete by [F6], so [F5]–[F7] make these iterates converge to the unique fixed point of $T^{\mu }$, which equals $V^{\mu }$ by [F3]. Since $\mathrm{\mid }{W}_n(s)-V^{\mu }(s)\mathrm{\mid }\le d_{\mathrm{\infty }}(W_n,V^{\mu })$ for every $s$, convergence is coordinatewise; [F10] gives $V^{\mu }\le V^{\ast }$. Therefore the terminal policy's value dominates every stationary policy.