In Policy Iteration, why the successive value vector monotonically increases?

Let $$\mathcal{X}=:\{x_1, x_2, x_3,...,x_n\}$$ be the state space. Let $$\mathcal{U}:=\{u_1, u_2, u_3,...,u_m\}$$ be the set of actions. Let $$A^{u_1}, A^{u_2}, A^{u_3},...,A^{u_m}$$ be the state transition matrices corresponding to the actions $$u_1, u_2, u_3,...,u_m$$ respectively. Let $$a^{u_k}_{i,j}$$ denotes the $$(i,j)^{th}$$ entry of matrix $$A^{u_k}$$, i.e., $$a^{u_k}_{i,j}=(A^{u_k})_{i,j}$$, where $$k\in\{1,2,3,...,m\}$$. Let $$\mathcal{R}(x_i,u_k)\in\mathbb{R}$$ denotes the reward associated with the state $$x_i$$ and action $$u_k$$. Define the Bellman iteration map $$\mathcal{B}:\mathbb{R}^n\rightarrow \mathbb{R}^n$$ as: $$(Bv)_i=\max_{u_k\in\mathcal{U}} \{ \mathcal{R}(x_i,u_k)+\sum_{j=1}^{n}a^{u_k}_{i,j}(v)_i\},$$ for an arbitrary vector $$v\in\mathbb{R}^n$$, where $$(v)_i$$ denotes the $$i^{th}$$ entry of $$v$$. Let $$\pi_{0}:\mathcal{X}\rightarrow \mathcal{U}$$ be a deterministic policy. Let $$v_{\pi_{0}}$$ is the value vector corresponding to the policy $$\pi_{0}$$. Now update the policy as follows: $$\pi_{1}(x_i)=\arg \max_{u_k\in\mathcal{U}} \{\mathcal{R}(x_i,u_k)+\sum_{j=1}^{n} a^{u_k}_{i,j}(v_{\pi_0})_j\}.$$ Now calculate the value vector $$v_{\pi_1}$$ corresponding to the policy $$\pi_1$$. Again update the policy as follows: $$\pi_{2}(x_i)=\arg \max_{u_k\in\mathcal{U}} \{\mathcal{R}(x_i,u_k)+\sum_{j=1}^{n} a^{u_k}_{i,j}(v_{\pi_1})_j\}.$$ Now calculate the value vector $$v_{\pi_2}$$ corresponding the policy $$\pi_2$$ and again update the policy as follows: $$\pi_{3}(x_i)=\arg \max_{u_k\in\mathcal{U}} \{\mathcal{R}(x_i,u_k)+\sum_{j=1}^{n} a^{u_k}_{i,j}(v_{\pi_2})_j\}.$$

We keep iterating the policy in this manner, i.e., $$\pi_{k+1}(x_i)=\arg \max_{u_k\in\mathcal{U}} \{\mathcal{R}(x_i,u_k)+\sum_{j=1}^{n} a^{u_k}_{i,j}(v_{\pi_k})_j\}.$$

Now, how I can prove the following:

(1) $$v_{\pi_{k+1}}\geq v_{\pi_{k}}$$

(2) $$v_{\pi_{k}}$$ converges to optimal value vector $$v^{*}$$ as $$k$$ tends to $$\infty$$

(3) $$v_{\pi_{k+1}}= Bv_{\pi_{k}}$$

• Not that it affects the math, but are you allowing all actions in all states? I'm used to having the set of actions be state-dependent. Aug 25, 2022 at 7:57