Why are the Bellman operators contractions?

Question

In these slides, it is written

\begin{align} \left\|T^{\pi} V-T^{\pi} U\right\|_{\infty} & \leq \gamma\|V-U\|_{\infty} \tag{9} \label{9} \\ \|T V-T U\|_{\infty} & \leq \gamma\|V-U\|_{\infty} \tag{10} \label{10} \end{align} where

• $F$ is the space of functions on domain $\mathbb{S}$.
• $T^{\pi}: \mathbb{F} \mapsto \mathbb{F}$ is the Bellman policy operator
• $T: \mathbb{F} \mapsto \mathbb{F}$ is the Bellman optimality operator

In slide 19, they say that equality $9$ follows from

\begin{align} {\scriptsize \left\| T^{\pi} V-T^{\pi} U \right\|_{\infty} = \max_{s} \gamma \sum_{s^{\prime}} \operatorname{Pr} \left( s^{\prime} \mid s, \pi(s) \right) \left| V\left(s^{\prime}\right) - U \left(s^{\prime}\right) \right| \\ \leq \gamma \left(\sum \operatorname{Pr} \left(s^{\prime} \mid s, \pi(s)\right)\right) \max _{s^{\prime}}\left|V\left(s^{\prime}\right)-U\left(s^{\prime}\right)\right| \\ \leq \gamma\|U-V\|_{\infty} } \end{align}

Why is that? Can someone explain to me this derivation?

They also write that inequality \ref{10} follows from

\begin{align} {\scriptsize \|T V-T U\|_{\infty} = \max_{s} \left| \max_{a} \left\{ R(s, a) + \gamma \sum_{s^{\prime}} \operatorname{Pr} \left( s^{\prime} \mid s, a \right) V \left( s^{\prime} \right) \right\} -\max_{a} \left\{R(s, a)+\gamma \sum_{s^{\prime}} \operatorname{Pr}\left(s^{\prime} \mid s, a\right) U\left(s^{\prime}\right)\right\} \right| \\ \leq \max _{s, a}\left|R(s, a)+\gamma \sum_{s^{\prime}} \operatorname{Pr}\left(s^{\prime} \mid s, a\right) V\left(s^{\prime}\right) -R(s, a)-\gamma \sum \operatorname{Pr}\left(s^{\prime} \mid s, a\right) V\left(s^{\prime}\right) \right| \\ = \gamma \max _{s, a}\left|\sum_{s^{\prime}} \operatorname{Pr}\left(s^{\prime} \mid s, a\right)\left(V\left(s^{\prime}\right)-U\left(s^{\prime}\right)\right)\right| \\ \leq \gamma\left(\sum_{s^{\prime}} \operatorname{Pr}\left(s^{\prime} \mid s, a\right)\right) \max _{s^{\prime}}\left|\left(V\left(s^{\prime}\right)-U\left(s^{\prime}\right)\right)\right| \\ \leq \gamma\|V-U\|_{\infty} } \end{align}

Can someone explain to me also this derivation?

Answer 1

The inequality \begin{align} \left\|T^{\pi} V-T^{\pi} U\right\|_{\infty} & \leq \gamma\|V-U\|_{\infty} \label{1}\tag{1}, \end{align} where $U$ and $V$ are two value functions, follows from the definition of Bellman policy operator (at slide 16)

\begin{align} T^{\pi} V(s) &\triangleq R(s, a)+\gamma \sum_{s^{\prime}} \operatorname{Pr}\left(s^{\prime} \mid s, a\right) V\left(s^{\prime}\right) \\ &=R(s, \pi(s))+\gamma \sum_{s^{\prime}} \operatorname{Pr}\left(s^{\prime} \mid s, \pi(s)\right) V\left(s^{\prime}\right), \; \forall s \in S \tag{2}\label{2}, \end{align} where $\triangleq$ means "defined as". Note the $\pi$ in the definition, hence the name Bellman policy operator (BPO), and note that the BPO holds for all $s$.

To prove (\ref{1}), first recall that

\begin{align} \left\|\mathbf {x} \right\|_{\infty } \triangleq \max _{i}\left|x_{i}\right| \label{3}\tag{3}. \end{align}

In the case of value functions $V$ and $U$, we have

\begin{align} \left\|V - U \right\|_{\infty } \triangleq \max_{s \in S}\left|V(s) - U(s) \right|. \label{4}\tag{4} \end{align}

Note also that $Pr$ is always non-negative (specifically, between $0$ and $1$).

Successively, we expand the left-hand side of (\ref{1}) by applying the definition (\ref{2}) and using the properties just mentioned

\begin{align} &\left\|T^{\pi} V-T^{\pi} U\right\|_{\infty} = \\ &\left\| \left( R(s, \pi(s))+\gamma \sum_{s^{\prime}} \operatorname{Pr}\left(s^{\prime} \mid s, \pi(s) \right) V\left(s^{\prime}\right) \right) - \\ \left( R(s, \pi(s))+\gamma \sum_{s^{\prime}} \operatorname{Pr}\left(s^{\prime} \mid s, \pi(s) \right) U\left(s^{\prime}\right) \right) \right\|_{\infty} =\\ &\max_{s \in S} \left| \left( R(s, \pi(s))+\gamma \sum_{s^{\prime}} \operatorname{Pr}\left(s^{\prime} \mid s, \pi(s) \right) V\left(s^{\prime}\right) \right) - \\ \left( R(s, \pi(s))+\gamma \sum_{s^{\prime}} \operatorname{Pr}\left(s^{\prime} \mid s, \pi(s) \right) U\left(s^{\prime}\right) \right) \right| = \\ & \max_{s \in S} \left| \gamma \sum_{s^{\prime}} \operatorname{Pr}\left(s^{\prime} \mid s, \pi(s) \right) V\left(s^{\prime}\right) - \gamma \sum_{s^{\prime}} \operatorname{Pr}\left(s^{\prime} \mid s, \pi(s) \right) U\left(s^{\prime}\right) \right| = \\ & \gamma \max_{s \in S} \left| \sum_{s^{\prime}} \operatorname{Pr}\left(s^{\prime} \mid s, \pi(s) \right) V\left(s^{\prime}\right) - \sum_{s^{\prime}} \operatorname{Pr}\left(s^{\prime} \mid s, \pi(s) \right) U\left(s^{\prime}\right) \right| = \\ & \gamma \max_{s \in S} \left| \sum_{s^{\prime}} \operatorname{Pr}\left(s^{\prime} \mid s, \pi(s)\right) \left ( V\left(s^{\prime}\right) - U\left(s^{\prime}\right) \right) \right| = \\ & \gamma \max_{s \in S} \sum_{s^{\prime}} \operatorname{Pr}\left(s^{\prime} \mid s, \pi(s)\right) \left| V\left(s^{\prime}\right) - U\left(s^{\prime}\right) \right| \\ & \leq \gamma \max_{s \in S} \sum_{s^{\prime}} \operatorname{Pr}\left(s^{\prime} \mid s, \pi(s)\right) \max_{x \in S }\left| V\left(x\right) - U\left(x\right) \right| \label{5}\tag{5} \\ & \leq \gamma \max _{x \in \mathcal{S}}\left|V\left(x\right)-U\left(x\right)\right| \label{6}\tag{6} \\ &= \gamma \| V - U \|_{_{\infty}} \label{7}\tag{7} \end{align}

Here are a few notes to help you understand this derivation

• Equation \ref{7} is just the direct application of the definition of the $\infty$-norm in equation \ref{4}

• The inequalities \ref{5} and \ref{6} come from the fact that $\mathbb{E}[f(x)] \leq \max_x f(x)$. When we take $\max_s$, we choose among all conditional distributions $p$ (which are conditioned on $s$), but the differences $\left| V\left(s^{\prime}\right) - U\left(s^{\prime}\right) \right|$ don't change in that process. So, no matter which $p$ we choose, i.e. no matter which distribution of the function $\left| V\left(s^{\prime}\right) - U\left(s^{\prime}\right) \right|$ we choose, we know that $\mathbb{E} \left[ \left| V\left(s^{\prime}\right) - U\left(s^{\prime}\right) \right| \right] \leq \max _{x \in \mathcal{S}}\left|V\left(x\right)-U\left(x\right)\right|$

Answer 2

I am assuming you are aware of the meaning of the notations. I will provide an informal explanation.

From your comment I am guessing you have difficulty in this portion in the 1st equation:

\begin{align} {\scriptsize \max_{s} \gamma \sum_{s^{\prime}} \operatorname{Pr} \left( s^{\prime} \mid s, \pi(s) \right) \left| V\left(s^{\prime}\right) - U \left(s^{\prime}\right) \right| \\ \leq \gamma \left(\sum \operatorname{Pr} \left(s^{\prime} \mid s, \pi(s)\right)\right) \max _{s^{\prime}}\left|V\left(s^{\prime}\right)-U\left(s^{\prime}\right)\right| \\ \leq \gamma\|U-V\|_{\infty} } \end{align}

The first inequality arises simply due to the fact that you are assigning a probability $1$ to the succesor state which has the maximum difference under the $2$ value functions, whereas previously you wee maximizing the entire equation with respect to a state $s$, and hence certain probabilities get assigned to low value diiference states as well (i.e $|U(s') - V(s')|$ is small compared to the largest value difference), whereas now you just pick the maximum difference between a succesor state, under the 2 value functions $V,U$ and assign the entire probability to it i.e ($(\sum_{s'}Pr(s'|s, \pi(s))) = 1$).

The second inequality is due to the fact, that now instead of selecting from a successor state, you select the maximum difference under the 2 value functions ($U(s),V(s)$) from the entire state space.

In the 2nd equation:

\begin{align} {\scriptsize \gamma \max _{s, a}\left|\sum_{s^{\prime}} \operatorname{Pr}\left(s^{\prime} \mid s, a\right)\left(V\left(s^{\prime}\right)-U\left(s^{\prime}\right)\right)\right| \\ \leq \gamma\left(\sum_{s^{\prime}} \operatorname{Pr}\left(s^{\prime} \mid s, a\right)\right) \max _{s^{\prime}}\left|\left(V\left(s^{\prime}\right)-U\left(s^{\prime}\right)\right)\right| \\ \leq \gamma\|V-U\|_{\infty} } \end{align}

The first inequality is again due to the same reasoning as above, that you assign the entire probability to the succesor state with highest value difference (under $U,V$) the maximum probability. And the second inequality is also due to the same reasoning as the 1st equation. You look for the maximum difference in the entire state space instead of just among successor states.

NOTE: In general succesor states can be the entire state space with those unreachable from state having $Pr(s'|s) = 0$, in that case the last inequality will become equality in both the equations.