Answers.Body: <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>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-03-06T11:08:07.987Z
Answers.Text: why from 5 to 6 there is an inequality sign? shouldn't the sum of Pr(s'|s,pi(s)) be 1?
Answers.UserDisplayName: Sam
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-08-10T14:38:29.897Z
Answers.LastActivityDate: 2022-01-22T15:39:22.330Z
Answers.LastEditDate: 2022-01-22T15:39:22.330Z
Answers.UserDisplayName: nbro
Body: <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>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-31T09:32:15.650Z
Comments.Text: 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.
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-31T09:51:45.770Z
Comments.Text: @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
Comments.UserDisplayName: kevin
Tags: <reinforcement-learning><proofs><policy-iteration><bellman-equations><bellman-operators>
Title: Why are the Bellman operators contractions?
UserDisplayName: kevin
ThreadText: # 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**: @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  
  
  ---
  
  ## 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?  
  
  ---
  
  