<p>The inequality
<span class="math-container">\begin{align}
\left\|T^{\pi} V-T^{\pi} U\right\|_{\infty} &amp; \leq \gamma\|V-U\|_{\infty} \label{1}\tag{1},
\end{align}</span>
where <span class="math-container">$U$</span> and <span class="math-container">$V$</span> are two value functions, follows from the definition of <em>Bellman <strong>policy</strong> operator</em> (at <a href="http://web.archive.org/web/20210506172558/https://rlchina.org/lectures/lecture2.pdf#page=16" rel="nofollow noreferrer">slide  16</a>)</p>
<p><span class="math-container">\begin{align}
T^{\pi} V(s) 
&amp;\triangleq 
R(s, a)+\gamma \sum_{s^{\prime}} \operatorname{Pr}\left(s^{\prime} \mid s, a\right) V\left(s^{\prime}\right) \\
&amp;=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}</span>
where <span class="math-container">$\triangleq$</span> means &quot;defined as&quot;. Note the <span class="math-container">$\pi$</span> in the definition, hence the name <em>Bellman <strong>policy</strong> operator</em> (BPO), and note that the BPO holds for all <span class="math-container">$s$</span>.</p>
<p>To prove (\ref{1}), first recall that</p>
<p><span class="math-container">\begin{align}
\left\|\mathbf {x} \right\|_{\infty } \triangleq \max _{i}\left|x_{i}\right| \label{3}\tag{3}.
\end{align}</span></p>
<p>In the case of value functions <span class="math-container">$V$</span> and <span class="math-container">$U$</span>, we have</p>
<p><span class="math-container">\begin{align}
\left\|V - U \right\|_{\infty } \triangleq \max_{s \in S}\left|V(s) - U(s) \right|.
\label{4}\tag{4}
\end{align}</span></p>
<p>Note also that <span class="math-container">$Pr$</span> is always non-negative (specifically, between <span class="math-container">$0$</span> and <span class="math-container">$1$</span>).</p>
<p>Successively, we expand the <strong>left-hand side</strong> of (\ref{1}) by applying the definition (\ref{2}) and using the properties just mentioned</p>
<p><span class="math-container">\begin{align}
&amp;\left\|T^{\pi} V-T^{\pi} U\right\|_{\infty}
= 
\\
&amp;\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} 
=\\
&amp;\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|
= 
\\
&amp; \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|
= 
\\
&amp; \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|
= 
\\
&amp; \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|
= 
\\
&amp; \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| \\
&amp; \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}
\\
&amp; \leq 
\gamma \max _{x \in \mathcal{S}}\left|V\left(x\right)-U\left(x\right)\right| 
\label{6}\tag{6}
\\
&amp;=
\gamma \| V - U \|_{_{\infty}} 
\label{7}\tag{7}
\end{align}</span></p>
<p>Here are a few notes to help you understand this derivation</p>
<ul>
<li><p>Equation \ref{7} is just the direct application of the definition of the <span class="math-container">$\infty$</span>-norm in equation \ref{4}</p>
</li>
<li><p>The inequalities \ref{5} and \ref{6} come from the fact that <span class="math-container">$\mathbb{E}[f(x)] \leq \max_x f(x)$</span>. When we take <span class="math-container">$\max_s$</span>, we choose among all conditional distributions <span class="math-container">$p$</span> (which are conditioned on <span class="math-container">$s$</span>), but the differences <span class="math-container">$\left| V\left(s^{\prime}\right) - U\left(s^{\prime}\right) \right|$</span> don't change in that process. So, no matter which <span class="math-container">$p$</span> we choose, i.e. no matter which distribution of the function <span class="math-container">$\left| V\left(s^{\prime}\right) - U\left(s^{\prime}\right) \right|$</span> we choose, we know that <span class="math-container">$\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|$</span></p>
</li>
</ul>

CC BY-SA 4.0
2024-03-06T11:08:07.987Z
why from 5 to 6 there is an inequality sign? shouldn't the sum of Pr(s'|s,pi(s)) be 1?
Sam
CC BY-SA 4.0
2020-08-10T14:38:29.897Z
2022-01-22T15:39:22.330Z
2022-01-22T15:39:22.330Z
nbro
<p>In <a href="https://rlchina.org/lectures/lecture2.pdf#page=17" rel="noreferrer">these slides</a>, it is written</p>
<p><span class="math-container">\begin{align}
\left\|T^{\pi} V-T^{\pi} U\right\|_{\infty} &amp; \leq \gamma\|V-U\|_{\infty} \tag{9} \label{9} \\
\|T V-T U\|_{\infty} &amp; \leq \gamma\|V-U\|_{\infty} \tag{10} \label{10}
\end{align}</span>
where</p>
<ul>
<li><span class="math-container">$F$</span> is the space of functions on domain <span class="math-container">$\mathbb{S}$</span>.</li>
<li><span class="math-container">$T^{\pi}: \mathbb{F} \mapsto \mathbb{F}$</span> is the Bellman
<em>policy</em> operator</li>
<li><span class="math-container">$T: \mathbb{F} \mapsto \mathbb{F}$</span> is the Bellman
<strong>optimality</strong> operator</li>
</ul>
<p>In <a href="https://rlchina.org/lectures/lecture2.pdf#page=19" rel="noreferrer">slide 19</a>, they say that equality <span class="math-container">$9$</span> follows from</p>
<p><span class="math-container">\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}</span></p>
<p>Why is that? Can someone explain to me this derivation?</p>
<p>They also write that inequality \ref{10} follows from</p>
<p><span class="math-container">\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}</span></p>
<p>Can someone explain to me also this derivation?</p>

CC BY-SA 4.0
2020-07-31T09:32:15.650Z
Which particular bits do you not understand? It would also be good if you introduced some of the notation, e.g. what is $T$ here? I assume it is some kind of bellman backup operator but that is just a guess. Also, what is $U$ here? it looks like it'll be a value function but without specifics it is hard to comment.
David
CC BY-SA 4.0
2020-07-31T09:51:45.770Z
@DavidIreland the first inequality in (10) can be understood using _|maxA - maxB| <= max| A - B|_   However, I am not sure about the two inequalities at the very last line of the proof
kevin
<reinforcement-learning><proofs><policy-iteration><bellman-equations><bellman-operators>
Why are the Bellman operators contractions?
kevin
# Why are the Bellman operators contractions?

(Asked by: username_0 on 2020-07-31)

In [these slides](https://rlchina.org/lectures/lecture2.pdf#page=17), 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](https://rlchina.org/lectures/lecture2.pdf#page=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?

**Tags:** reinforcement-learning, proofs, policy-iteration, bellman-equations, bellman-operators

> **Comments:**
> **username_1**: Which particular bits do you not understand? It would also be good if you introduced some of the notation, e.g. what is $T$ here? I assume it is some kind of bellman backup operator but that is just a guess. Also, what is $U$ here? it looks like it'll be a value function but without specifics it is hard to comment.  
> **username_0**: @username_1Ireland the first inequality in (10) can be understood using _|maxA - maxB| <= max| A - B|_   However, I am not sure about the two inequalities at the very last line of the proof  

---

## 1 answers

### Answer by username_2 on 2020-08-10. Score: 6

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](http://web.archive.org/web/20210506172558/https://rlchina.org/lectures/lecture2.pdf#page=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|$

> **Comments:**
> **username_3**: why from 5 to 6 there is an inequality sign? shouldn't the sum of Pr(s'|s,pi(s)) be 1?  

---

