Bellman Optimality Equation

1. Shiyu Zhao. Chapter 3: Bellman Optimality Equation. Mathematical Foundations of Reinforcement Learning.
2. --> Youtube: Bellman Optimality Equation
3. --> Youtube: How to Solve Bellman Optimality Equation

The previous chapter introduced the Bellman equation of any given policy. The present post introduces the Bellman optimality equation, which is a special Bellman equation whose corresponding policy is optimal. By solving

Optimal Policy

The state value could be used to evaluate if a policy is good or not: if $$v_{{\pi }_1}(s)\ge v_{{\pi }_2}(s)\text{ for all }s\in \mathcal{S}$$ then ${\pi }_1$ is "better" than ${\pi }_2$.

A policy ${\pi }^{\ast }$ is optimal if $v_{{\pi }^{\ast }}(s)\ge v_{\pi }(s)$ for all $s$ and for any other policy $\pi$.

The definition leads to many questions:

• Does the optimal policy exist?
• Is the optimal policy unique?
• Is the optimal policy stochastic or deterministic?
• How to obtain the optimal policy?

To answer these questions, we study the Bellman optimality equation.

BOE (elementwise form)

The tool for analyzing optimal policies and optimal state values is the Bellman optimality equation (BOE). By solving this equation, we can obtain optimal policies and optimal state values.

For every $s\in \mathcal{S}$, the elementwise expression of the BOE is $$\begin{array}{rl}v(s)& =\underset{\pi (s)\in \mathrm{\Pi }(s)}{max}(\mathbb{E}[R_{t+1}\mid S_t=s]+\gamma \mathbb{E}[G_{t+1}\mid S_t=s])\\ & =\underset{\pi (s)\in \mathrm{\Pi }(s)}{max}\sum _{a\in \mathcal{A}}\pi (a\mid s)(\sum _{r\in \mathcal{R}}p(r\mid s,a)r+\gamma \sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime }\mid s,a)v\left(s^{\prime }\right))\\ & =\underset{\pi (s)\in \mathrm{\Pi }(s)}{max}\sum _{a\in \mathcal{A}}\pi (a\mid s)q(s,a),\end{array}$$ where $v(s),v\left(s^{\prime }\right)$ are unknown variables to be solved and $$ q(s, a)

+ $$

Here, $\pi (s)$ denotes a policy for state $s$, and $\mathrm{\Pi }(s)$ is the set of all possible policies for $s$.

To get optimal state values (or optimal state value function) and optimal policies, we keep calculating BOE for each state $s\in \mathcal{S}$, which involves choose one policy $\pi (s)\in \mathrm{\Pi }(s)$. When the state values don't change too much, i.e., they have converged, the state value fucntion is the optimal state value function, and the policy it adopts during that computation is the the optimal policy.

Like before, the first term $$\sum _{r\in \mathcal{R}}p(r\mid s,a)r$$ is the mean of immediate rewards, and the second term $$\gamma \sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime }\mid s,a)v\left(s^{\prime }\right)$$ is the discounted mean of future rewards.

Remarks:

• $p(r\mid s,a)$ and $p(s^{\prime }\mid s,a)$ are known.
• $v(s),v\left(s^{\prime }\right)$ are unknown and to be calculated.

Maximize on the right-hand side of BOE

Here we talk about how to solve BOE. In practice we need to deal with the matrix-vector form since that is what we're faced with. But since each row in the matrix is actually a vector of the elementwise form, we start with the element form.

In fact, we can turn the problem into "solve the optimal $\pi$ on the right-hand side". Let's look at one example first:

---

Example 3.1. Consider two unknown variables $x,y\in \mathbb{R}$ that satisfy $$x=\underset{y\in \mathbb{R}}{max}(2x-1-y^2).$$

The first step is to solve $y$ on the right-hand side of the equation. Regardless of the value of $x$, we always have $\underset{y}{max}(2x-1-y^2)=2x-1$, where the maximum is achieved when $y=0$. The second step is to solve $x$. When $y=0$, the equation becomes $x=2x-1$, which leads to $x=1$. Therefore, $y=0$ and $x=1$ are the solutions of the equation.

---

We now turn to the maximization problem on the right-hand side of the BOE. The (elementwise) BOE can be written as $$v(s)=\underset{\pi (s)\in \mathrm{\Pi }(s)}{max}\sum _{a\in \mathcal{A}}\pi (a\mid s)q(s,a),s\in \mathcal{S}.$$

Inspired by Example 3.1, we can first solve the optimal $\pi$ on the right-hand side. How to do that? The following example demonstrates its basic idea.

---

Example 3.2. Given $q_1,q_2,q_3\in \mathbb{R}$, we would like to find the optimal values of $c_1,c_2,c_3$ to maximize $$\sum _{i=1}^3{c}_i{q}_i=c_1{q}_1+c_2{q}_2+c_3{q}_3,$$ where $c_1+c_2+c_3=1$ and $c_1,c_2,c_3\ge 0$. Without loss of generality, suppose that $q_3\ge q_1,q_2$. Then, the optimal solution is $c_3^{\ast }=1$ and $c_1^{\ast }=c_2^{\ast }=0$. This is because $$q_3=(c_1+c_2+c_3)q_3=c_1{q}_3+c_2{q}_3+c_3{q}_3\ge c_1{q}_1+c_2{q}_2+c_3{q}_3$$ for any $c_1,c_2,c_3$.

---

Inspired by the above example, considering that $\sum _a\pi (a\mid s)=1$, we have $$\begin{array}{}\text{(1)}& v(s)& =\underset{\pi }{max}\sum _a\pi (a\mid s)q(s,a)\text{(2)}& & =\underset{a\in \mathcal{A}(s)}{max}q(s,a)\end{array}$$ where the optimality is achieved when $$\pi (a\mid s)=\{\begin{array}{ll}1& a=a^{\ast }\\ 0& a\ne a^{\ast }\end{array}$$ where $a^{\ast }=\arg \underset{a}{max}q(s,a)$.

Now that we know the solution of BOE is to maximize the right-hand side, and we know how to do it as well --- just select the action with the largest action value. But we don't know action value or state value at this time, so this method doesn't work.

In fact, the solution of BOE derives from the contraction mapping theorem (see later) on the matrix-vector form. That's an iterative method

So why we introduce $\text{(2)}$ here? The reason at during every iteration, for every state $s$, the action value will already have been known, so we can use $\text{(2)}$ to get the maximized right-hand side, which is the maximized $v(s)$!

Matrix-vector form of the BOE

To leverage the contraction mapping theorem, we'll express the matrix-vector form as $v=f(v)$.

Since the optimal value of $\pi$ is determined by $v$, the right-hand side of BOE (matrix-vector form) is a function of $v$, denoted as $$\begin{array}{}\text{(3)}& f(v)\triangleq \underset{\pi }{max}(r_{\pi }+\gamma P_{\pi }v).\end{array}$$

where $v\in {\mathbb{R}}^{|\mathcal{S}|}$ and $\underset{\pi }{max}$ is performed in an elementwise manner. The structures of $r_{\pi }$ and $P_{\pi }$ are the same as those in the matrix-vector form of the normal Bellman equation: $${\left[r_{\pi }\right]}_s\doteq \sum _{a\in \mathcal{A}}\pi (a\mid s)\sum _{r\in \mathcal{R}}p(r\mid s,a)r,{\left[P_{\pi }\right]}_{s,s^{\prime }}=p(s^{\prime }\mid s)\doteq \sum _{a\in \mathcal{A}}\pi (a\mid s)p(s^{\prime }\mid s,a).$$

Then, the BOE can be expressed in a concise form as $$v=f(v)$$

Every row $[f(v){]}_s$ is the elementwise form of $s$.

Contraction mapping theorem

Now that the matrix-vector form is expressed as a nonlinear equation $v=f(v)$, we next introduce the contraction mapping theorem to analyze it.

Concepts: Fixed point and Contraction mapping

Fixed point: $x\in X$ is a fixed point of $f:X\to X$ if $$f(x)=x$$ ***

Contraction mapping (or contractive function): $f$ is a contraction mapping if $$\Vert f\left(x_1\right)-f\left(x_2\right)\Vert \le \gamma \Vert x_1-x_2\Vert$$ where $\gamma \in (0,1)$. - Note: $\gamma$ must be strictly less than 1 so that many limits such as ${\gamma }^k\to 0$ as $k\to 0$ hold. - Here, $\Vert \cdot \Vert$ can be any vector norm.

Example1

Givn euqation: $$x=f(x)=0.5x,x\in \mathbb{R}.$$ It is easy to verify that $x=0$ is a fixed point since $0=0.5\times 0$.

Moreover, $f(x)=0.5x$ is a contraction mapping because $$\Vert 0.5x_1-0.5x_2\Vert =0.5\Vert x_1-x_2\Vert \le \gamma \Vert x_1-x_2\Vert$$ for any $\gamma \in [0.5,1)$.

Example2

Given $x=f(x)=Ax$, where $x\in {\mathbb{R}}^n,A\in {\mathbb{R}}^{n\times n}$ and $\Vert A\Vert \le \gamma <1$. It is easy to verify that $x=0$ is a fixed point since $0=A0$. To see the contraction property, $$\Vert A{x}_1-A{x}_2\Vert =\Vert A(x_1-x_2)\Vert \le \Vert A\Vert \Vert x_1-x_2\Vert \le \gamma \Vert x_1-x_2\Vert .$$

Therefore, $f(x)=Ax$ is a contraction mapping.

Theorem: Contraction Mapping Theorem

Theorem (Contraction Mapping Theorem): For any equation that has the form of $x=f(x)$, if $f$ is a contraction mapping, then

• Existence: there exists a fixed point $x^{\ast }$ satisfying $f\left(x^{\ast }\right)=x^{\ast }$.
• Uniqueness: The fixed point $x^{\ast }$ is unique.
• Algorithm: Consider a sequence $\left\{x_k\right\}$ where $x_{k+1}=f\left(x_k\right)$, then $x_k\to x^{\ast }$ as $k\to \mathrm{\infty }$. Moreover, the convergence rate is exponentially fast.

-> See the proof

Contraction property of BOE

Theorem (Contraction Property):

$f(v)$ in $\text{(3)}$ is a contraction mapping satisfying $$\Vert f\left(v_1\right)-f\left(v_2\right)\Vert \le \gamma \Vert v_1-v_2\Vert$$ where $\gamma \in (0,1)$ is the discount rate, and $\Vert \cdot {\Vert }_{\mathrm{\infty }}$ is the maximum norm, which is the maximum absolute value of the elements of a vector.

-> See the proof

Solution of the BOE

Due to the contraction property of BOE, the matrix-vector form can be solved by computing following equation iteratively $$\begin{array}{}\text{(4)}& v_{k+1}=f\left(v_k\right)=\underset{\pi }{max}(r_{\pi }+\gamma P_{\pi }{v}_k).\end{array}$$

At every iteration, for each state, what we face is actually the elementwise form:

$$\begin{array}{rl}{v}_{k+1}(s)& =\underset{\pi }{max}\sum _a\pi (a\mid s)(\sum _{r}p(r\mid s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }\mid s,a)v_k\left(s^{\prime }\right))\\ & =\underset{\pi }{max}\sum _a\pi (a\mid s)q_k(s,a)\\ & =\underset{a}{max}{q}_k(s,a).\end{array}$$

As you can see, $\text{(2)}$ is leveraged here. (But I don't know why can I do it. There's no proof about the contraction property of elementwise form, only one for the matrix-vector form)

Procedure summary (value iteration algorithm):

• For every $s$, estimate(randomly select) current state value as $v_k(s)$

• For any $a\in \mathcal{A}(s)$, calculate $$q_k(s,a)=\sum _{r}p(r\mid s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }\mid s,a)v_k\left(s^{\prime }\right)$$

• Calculate the greedy policy ${\pi }_{k+1}$ for every $s$ as $${\pi }_{k+1}(a\mid s)=\{\begin{array}{cc}1& a=a_k^{\ast }(s)\\ 0& a\ne a_k^{\ast }(s)\end{array}$$ where $a_k^{\ast }(s)=\arg \underset{a}{max}{q}_k(s,a)$.

• Calculate $v_{k+1}(s)=\underset{a}{max}{q}_k(s,a)$

Example

Example: Manually solve the BOE.

Example

• Actions: $a_{\ell },a_0,a_r$ represent go left, stay unchanged, and go right.
• Reward: entering the target area: +1 ; try to go out of boundary -1.

---

The values of $q(s,a)$:

q-value table	$a_{\ell }$	$a_0$	$a_r$
$s_1$	$-1+\gamma v\left(s_1\right)$	$0+\gamma v\left(s_1\right)$	$1+\gamma v\left(s_2\right)$
$s_2$	$0+\gamma v\left(s_1\right)$	$1+\gamma v\left(s_2\right)$	$0+\gamma v\left(s_3\right)$
$s_3$	$1+\gamma v\left(s_2\right)$	$0+\gamma v\left(s_3\right)$	$-1+\gamma v\left(s_3\right)$

Consider $\gamma =0.9$.

Our objective is to find $v^{\ast }\left(s_i\right)$ and ${\pi }^{\ast }$:

$k=0$:

v-value: select $v_0\left(s_1\right)=v_0\left(s_2\right)=v_0\left(s_3\right)=0$

q-value (using the previous table):

q-value table	$a_{\ell }$	$a_0$	$a_r$
$s_1$	-1	0	1
$s_2$	0	1	0
$s_3$	1	0	-1

Greedy policy (select the greatest q-value) $$\pi (a_r\mid s_1)=1,\pi (a_0\mid s_2)=1,\pi (a_{\ell }\mid s_3)=1$$ v-value: $v_1(s)=\underset{a}{max}{q}_0(s,a)$ $$v_1\left(s_1\right)=v_1\left(s_2\right)=v_1\left(s_3\right)=1$$

$k=1$:

With $v_1(s)$ calculated in the last step, q-value:

q-value table	$a_{\ell }$	$a_0$	$a_r$
$s_1$	-0.1	0.9	1.9
$s_2$	0.9	1.9	0.9
$s_3$	1.9	0.9	-0.1

Greedy policy (select the greatest q-value): $$\pi (a_r\mid s_1)=1,\pi (a_0\mid s_2)=1,\pi (a_{\ell }\mid s_3)=1$$

The policy is the same as the previous one, which is already optimal. v-value: $v_2(s)=\dots$

$k=2,3,\dots$, iterate until the produced q-value doesn't change too much.

BOE: Optimality

Suppose $v^{\ast }$ is the solution to the Bellman optimality equation. It satisfies $$v^{\ast }=\underset{\pi }{max}(r_{\pi }+\gamma P_{\pi }{v}^{\ast })$$

Suppose $${\pi }^{\ast }=\arg \underset{\pi }{max}(r_{\pi }+\gamma P_{\pi }{v}^{\ast })$$

Then $$v^{\ast }=r_{{\pi }^{\ast }}+\gamma P_{{\pi }^{\ast }}{v}^{\ast }$$

Therefore, ${\pi }^{\ast }$ is a policy and $v^{\ast }=v_{{\pi }^{\ast }}$ is the corresponding state value.

Now we prove ${\pi }^{\ast }$ is the optilmal policy:

Theorem (Policy Optimality):

Suppose that $v^{\ast }$ is the unique solution to $v=\underset{\pi }{max}(r_{\pi }+\gamma P_{\pi }v)$, and $v_{\pi }$ is the state value function satisfying $v_{\pi }=r_{\pi }+\gamma P_{\pi }{v}_{\pi }$ for any given policy $\pi$, then $$v^{\ast }\ge v_{\pi },\mathrm{\forall }\pi$$ -> See the proof

What does ${\pi }^{\star }$ look like?

For any $s\in \mathcal{S}$, the deterministic greedy policy $${\pi }^{\ast }(a\mid s)=\{\begin{array}{ll}1& a=a^{\ast }(s)\\ 0& a\ne a^{\ast }(s)\end{array}$$ is an optimal policy solving the BOE. Here, $$a^{\ast }(s)=\arg \underset{a}{max}{q}^{\ast }(a,s)$$ where $$q^{\ast }(s,a):=\sum _{r}p(r\mid s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }\mid s,a)v^{\ast }\left(s^{\prime }\right).$$ Proof: Due to $${\pi }^{\ast }(s)=\arg \underset{\pi \in \mathrm{\Pi }}{max}\sum _{a\in \mathcal{A}}\pi (a\mid s)\underset{q^{\ast }(s,a)}{\underbrace{(\sum _{r\in \mathcal{R}}p(r\mid s,a)r+\gamma \sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime }\mid s,a)v^{\ast }\left(s^{\prime }\right))}},s\in \mathcal{S}.$$

It is clear that $\sum _{a\in \mathcal{A}}\pi (a\mid s)q^{\ast }(s,a)$ is maximized if $\pi (s)$ selects the action with the greatest $q^{\ast }(s,a)$.

Theorem: Optimal policy invariance

Theorem (Optimal policy invariance):

Consider a Markov decision process with $v^{\ast }\in {\mathbb{R}}^{|\mathcal{S}|}$ as the optimal state value satisfying $v^{\ast }=\underset{\pi \in \mathrm{\Pi }}{max}(r_{\pi }+\gamma P_{\pi }{v}^{\ast })$. If every reward $r\in \mathcal{R}$ is changed by an affine transformation to $\alpha r+\beta$, where $\alpha ,\beta \in \mathbb{R}$ and $\alpha >0$, then the corresponding optimal state value $v^{\prime }$ is also an affine transformation of $v^{\ast }$ : $$v^{\prime }=\alpha v^{\ast }+\frac{\beta }{1-\gamma }\mathbf{1}$$ where $\gamma \in (0,1)$ is the discount rate and $\mathbf{1}=[1,\dots ,1{]}^T$.

Consequently, the optimal policy derived from $v^{\prime }$ is invariant to the affine transformation of the reward values.

-> See the proof

Appendix

Proof of the contraction mapping theorem

Part 1

We prove that the consequence ${\left\{x_k\right\}}_{k=1}^{\mathrm{\infty }}$ with $x_k=f\left(x_{k-1}\right)$ is convergent.

The proof relies on Cauchy sequences:

A sequence $x_1,x_2,\cdots \in \mathbb{R}$ is called Cauchy if for any small $\epsilon >0$, there exists $N$ such that $\Vert x_m-x_n\Vert <\epsilon$ for all $m,n>N$.

It is guaranteed that a Cauchy sequence converges to a limit.

Note that we must have $\Vert x_m-x_n\Vert <\epsilon$ for all $m,n>N$. If we simply have $x_{n+1}-x_n\to 0$, it is insufficient to claim that the sequence is a Cauchy sequence. For example, it holds that $x_{n+1}-x_n\to 0$ for $x_n=\sqrt{n}$, but apparently, $x_n=\sqrt{n}$ diverges.

We next show that ${\{x_k=f\left(x_{k-1}\right)\}}_{k=1}^{\mathrm{\infty }}$ is a Cauchy sequence and hence converges.

First, since $f$ is a contraction mapping, we have $$\Vert x_{k+1}-x_k\Vert =\Vert f\left(x_k\right)-f\left(x_{k-1}\right)\Vert \le \gamma \Vert x_k-x_{k-1}\Vert .$$

Similarly, we have $\Vert x_k-x_{k-1}\Vert \le \gamma \Vert x_{k-1}-x_{k-2}\Vert ,\dots ,\Vert x_2-x_1\Vert \le \gamma \Vert x_1-x_0\Vert$. Thus, we have $$\begin{array}{rl}\Vert x_{k+1}-x_k\Vert & \le \gamma \Vert x_k-x_{k-1}\Vert \\ & \le {\gamma }^2\Vert x_{k-1}-x_{k-2}\Vert \\ & ⋮\\ & \le {\gamma }^k\Vert x_1-x_0\Vert .\end{array}$$

Since $\gamma <1$, we know that $\Vert x_{k+1}-x_k\Vert$ converges to zero exponentially fast as $k\to \mathrm{\infty }$ given any $x_1,x_0$.

Notably, the convergence of $\left\{\Vert x_{k+1}-x_k\Vert \right\}$ is not sufficient for implying the convergence of $\left\{x_k\right\}$.

Therefore, we need to further consider $\Vert x_m-x_n\Vert$ for any $m>n$. In particular, $$\begin{array}{rl}\Vert x_m-x_n\Vert & =\Vert x_m-x_{m-1}+x_{m-1}-\cdots -x_{n+1}+x_{n+1}-x_n\Vert \\ & \le \Vert x_m-x_{m-1}\Vert +\cdots +\Vert x_{n+1}-x_n\Vert \\ & \le {\gamma }^{m-1}\Vert x_1-x_0\Vert +\cdots +{\gamma }^n\Vert x_1-x_0\Vert \\ & ={\gamma }^n({\gamma }^{m-1-n}+\cdots +1)\Vert x_1-x_0\Vert \\ & \le {\gamma }^n(1+\cdots +{\gamma }^{m-1-n}+{\gamma }^{m-n}+{\gamma }^{m-n+1}+\dots )\Vert x_1-x_0\Vert \\ & =\frac{{\gamma }^n}{1-\gamma }\Vert x_1-x_0\Vert .\end{array}$$

As a result, for any $\epsilon$, we can always find $N$ such that $\Vert x_m-x_n\Vert <\epsilon$ for all $m,n>N$. Therefore, this sequence is Cauchy and hence converges to a limit point denoted as $x^{\ast }=\underset{k\to \mathrm{\infty }}{lim}{x}_k$. ### Part 2

We show that the limit $x^{\ast }=\underset{k\to \mathrm{\infty }}{lim}{x}_k$ is a fixed point. To do that, since $$\Vert f\left(x_k\right)-x_k\Vert =\Vert x_{k+1}-x_k\Vert \le {\gamma }^k\Vert x_1-x_0\Vert ,$$ we know that $\Vert f\left(x_k\right)-x_k\Vert$ converges to zero exponentially fast. Hence, we have $f\left(x^{\ast }\right)=x^{\ast }$ at the limit.

Part 3

We show that the fixed point is unique. Suppose that there is another fixed point $x^{\prime }$ satisfying $f\left(x^{\prime }\right)=x^{\prime }$. Then, $$\Vert x^{\prime }-x^{\ast }\Vert =\Vert f\left(x^{\prime }\right)-f\left(x^{\ast }\right)\Vert \le \gamma \Vert x^{\prime }-x^{\ast }\Vert .$$

Proof of the contraction property of BOE

Consider any two vectors $v_1,v_2\in {\mathbb{R}}^{|\mathcal{S}|}$, and suppose that ${\pi }_1^{\ast }\doteq \arg \underset{\pi }{max}(r_{\pi }+\gamma P_{\pi }{v}_1)$ and ${\pi }_2^{\ast }\doteq \arg \underset{\pi }{max}(r_{\pi }+\gamma P_{\pi }{v}_2)$. Then, $$\begin{array}{rl}& f\left(v_1\right)=\underset{\pi }{max}(r_{\pi }+\gamma P_{\pi }{v}_1)=r_{{\pi }_1^{\ast }}+\gamma P_{{\pi }_1^{\ast }}{v}_1\ge r_{{\pi }_2^{\ast }}+\gamma P_{{\pi }_2^{\ast }}{v}_1,\\ & f\left(v_2\right)=\underset{\pi }{max}(r_{\pi }+\gamma P_{\pi }{v}_2)=r_{{\pi }_2^{\ast }}+\gamma P_{{\pi }_2^{\ast }}{v}_2\ge r_{{\pi }_1^{\ast }}+\gamma P_{{\pi }_1^{\ast }}{v}_2,\end{array}$$ where $\ge$ is an elementwise comparison. As a result, $$\begin{array}{rl}f\left(v_1\right)-f\left(v_2\right)& =r_{{\pi }_1^{\ast }}+\gamma P_{{\pi }_1^{\ast }}{v}_1-(r_{{\pi }_2^{\ast }}+\gamma P_{{\pi }_2^{\ast }}{v}_2)\\ & \le r_{{\pi }_1^{\ast }}+\gamma P_{{\pi }_1^{\ast }}{v}_1-(r_{{\pi }_1^{\ast }}+\gamma P_{{\pi }_1^{\ast }}{v}_2)\\ & =\gamma P_{{\pi }_1^{\ast }}(v_1-v_2)\end{array}$$ Similarly, it can be shown that $f\left(v_2\right)-f\left(v_1\right)\le \gamma P_{{\pi }_2^{\ast }}(v_2-v_1)$.

Therefore, $$\gamma P_{{\pi }_2^{\ast }}(v_1-v_2)\le f\left(v_1\right)-f\left(v_2\right)\le \gamma P_{{\pi }_1^{\ast }}(v_1-v_2)$$

Define $$z\doteq max\{\left|\gamma P_{{\pi }_2^{\ast }}(v_1-v_2)\right|,\left|\gamma P_{{\pi }_1^{\ast }}(v_1-v_2)\right|\}\in {\mathbb{R}}^{|\mathcal{S}|},$$ where $max(\cdot ),|\cdot |$, and $\ge$ are all elementwise operators. By definition, $z\ge 0$. On the one hand, it is easy to see that $$-z\le \gamma P_{{\pi }_2^{\ast }}(v_1-v_2)\le f\left(v_1\right)-f\left(v_2\right)\le \gamma P_{{\pi }_1^{\ast }}(v_1-v_2)\le z,$$ which implies $$|f\left(v_1\right)-f\left(v_2\right)|\le z.$$

It then follows that $$\begin{array}{}\text{(5)}& {\Vert f\left(v_1\right)-f\left(v_2\right)\Vert }_{\mathrm{\infty }}\le \Vert z{\Vert }_{\mathrm{\infty }}\end{array}$$ where $\Vert \cdot {\Vert }_{\mathrm{\infty }}$ is the maximum norm. On the other hand, suppose that $z_i$ is the $i$ th entry of $z$, and $p_i^T$ and $q_i^T$ are the $i$ th row of $P_{{\pi }_1^{\ast }}$ and $P_{{\pi }_2^{\ast }}$, respectively. Then, $$z_i=max\{\gamma \left|p_i^T(v_1-v_2)\right|,\gamma \left|q_i^T(v_1-v_2)\right|\}.$$

Since $p_i$ is a vector with all nonnegative elements and the sum of the elements is equal to one, it follows that $$\left|p_i^T(v_1-v_2)\right|\le p_i^T|v_1-v_2|\le {\Vert v_1-v_2\Vert }_{\mathrm{\infty }}$$

Similarly, we have $\left|q_i^T(v_1-v_2)\right|\le {\Vert v_1-v_2\Vert }_{\mathrm{\infty }}$. Therefore, $z_i\le \gamma {\Vert v_1-v_2\Vert }_{\mathrm{\infty }}$ and hence $$\Vert z{\Vert }_{\mathrm{\infty }}=\underset{i}{max}\left|z_i\right|\le \gamma {\Vert v_1-v_2\Vert }_{\mathrm{\infty }}$$

Substituting this inequality to $\text{(5)}$ gives $${\Vert f\left(v_1\right)-f\left(v_2\right)\Vert }_{\mathrm{\infty }}\le \gamma {\Vert v_1-v_2\Vert }_{\mathrm{\infty }}$$ which concludes the proof of the contraction property of $f(v)$.

Q.E.D.

Proof of Theorem: Policy Optimality

For any policy $\pi$, it holds that $$v_{\pi }=r_{\pi }+\gamma P_{\pi }{v}_{\pi }$$

Since $$v^{\ast }=\underset{\pi }{max}(r_{\pi }+\gamma P_{\pi }{v}^{\ast })=r_{{\pi }^{\ast }}+\gamma P_{{\pi }^{\ast }}{v}^{\ast }\ge r_{\pi }+\gamma P_{\pi }{v}^{\ast }$$ we have $$v^{\ast }-v_{\pi }\ge (r_{\pi }+\gamma P_{\pi }{v}^{\ast })-(r_{\pi }+\gamma P_{\pi }{v}_{\pi })=\gamma P_{\pi }(v^{\ast }-v_{\pi })$$

Repeatedly applying the above inequality gives $$v^{\ast }-v_{\pi }\ge \gamma P_{\pi }(v^{\ast }-v_{\pi })\ge \cdots \ge {\gamma }^n{P}_{\pi }^n(v^{\ast }-v_{\pi })$$ It follows that $$v^{\ast }-v_{\pi }\ge \underset{n\to \mathrm{\infty }}{lim}{\gamma }^n{P}_{\pi }^n(v^{\ast }-v_{\pi })=0$$ where the last equality is true because $\gamma <1$ and $P_{\pi }^n$ is a nonnegative matrix with all its elements less than or equal to 1 (because $P_{\pi }^n\mathbf{1}=\mathbf{1}$ ). Therefore, $v^{\ast }\ge v_{\pi }$ for any $\pi$.

Proof of Theorem: Optimal policy invariance

For any policy $\pi$, define $r_{\pi }={[\dots ,r_{\pi }(s),\dots ]}^T$ where $$r_{\pi }(s)=\sum _{a\in \mathcal{A}}\pi (a\mid s)\sum _{r\in \mathcal{R}}p(r\mid s,a)r,s\in \mathcal{S}.$$

If $r\to \alpha r+\beta$, then $r_{\pi }(s)\to \alpha r_{\pi }(s)+\beta$ and hence $r_{\pi }\to \alpha r_{\pi }+\beta \mathbf{1}$, where $\mathbf{1}=$ $[1,\dots ,1{]}^T$. In this case, the BOE becomes $$\begin{array}{}\text{(6)}& v^{\prime }=\underset{\pi \in \mathrm{\Pi }}{max}(\alpha r_{\pi }+\beta \mathbf{1}+\gamma P_{\pi }{v}^{\prime })\end{array}$$ where $v^{\prime }$ is the new state value after the change of rewards.

We next solve the new BOE in $\text{(6)}$ by showing that $v^{\prime }=\alpha v^{\ast }+c\mathbf{1}$ with $c=\beta /(1-\gamma )$ is a solution of $\text{(6)}$. In particular, substituting $v^{\prime }=\alpha v^{\ast }+c\mathbf{1}$ into $\text{(6)}$ gives $$\alpha v^{\ast }+c\mathbf{1}=\underset{\pi \in \mathrm{\Pi }}{max}(\alpha r_{\pi }+\beta \mathbf{1}+\gamma P_{\pi }(\alpha v^{\ast }+c\mathbf{1}))=\underset{\pi \in \mathrm{\Pi }}{max}(\alpha r_{\pi }+\beta \mathbf{1}+\alpha \gamma P_{\pi }{v}^{\ast }+c\gamma \mathbf{1})$$ where the last equality is due to the fact that $P_{\pi }\mathbf{1}=\mathbf{1}$. The above equation can be reorganized as $$\alpha v^{\ast }=\underset{\pi \in \mathrm{\Pi }}{max}(\alpha r_{\pi }+\alpha \gamma P_{\pi }{v}^{\ast })+\beta \mathbf{1}+c\gamma \mathbf{1}-c\mathbf{1}$$ which is equivalent to $$\beta \mathbf{1}+c\gamma \mathbf{1}-c\mathbf{1}=0$$

Since $c=\beta /(1-\gamma )$, the above equation is valid and hence $v^{\prime }=\alpha v^{\ast }+c\mathbf{1}$ is the solution of $\text{(6)}$. Since $\text{(6)}$ is the BOE, $v^{\prime }$ is also the unique solution.

Finally, since $v^{\prime }$ is an affine transformation of $v^{\ast }$, the relative relationships between the action values remain the same.

Hence, the greedy optimal policy derived from $v^{\prime }$ is the same as that from $v^{\ast }:\arg \underset{\pi \in \mathrm{\Pi }}{max}(r_{\pi }+\gamma P_{\pi }{v}^{\prime })$ is the same as $\arg \underset{\pi }{max}(r_{\pi }+\gamma P_{\pi }{v}^{\ast })$.