Answers.Body: <p>My first impression is that the proofs are correct, but there is a shorter way. If you first prove that the Bellman optimality operator is a contraction, then it is a corollary that the other two operators are also contractions. For the state-value function, let the set over which you maximize in (9) and (11) be a singleton. For the action-value function, let the set over which you maximize in (9) and (11) be a singleton containing a Dirac measure. By the way, you did not specify the set of admissible policies and a few other things.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-10-28T19:07:47.433Z
Answers.LastActivityDate: 2022-10-28T19:07:47.433Z
Answers.UserDisplayName: bigdatadan
Body: <h2>Introduction</h2>
  <p>I'm studying Reinforcement Learning, and in order to increase my understanding I've been challenging myself by trying to write proofs that show that the right hand side of the Bellman equations and Bellman optimality equations for state-value and action-value functions are contraction operators. The fact that the Bellman operators are contractions is of great importance, since this proves that the Bellman equations have unique fixed points that can be solved for iteratively, due to the Banach fixed-point theorem.</p>
  <p>Below are my attempts at the proofs, my questions are:</p>
  <ol>
  <li>Are the proofs correct?</li>
  <li>Any feedback on what can be improved (I'm very inexperienced in writing proofs and would like to get better)?</li>
  </ol>
  <p>I will assume some knowledge about finite Markov Decision Processes (MDPs), please let me know if you want me to elaborate.</p>
  <h2>Bellman equations</h2>
  <p>Let <span class="math-container">$\mathcal{S}$</span> denote the finite set of all states, <span class="math-container">$\mathcal{R} \subset \mathbb{R}$</span> the finite set of all rewards, and <span class="math-container">$\mathcal{A}(s)$</span> the finite set of all available actions <span class="math-container">$a$</span> in state <span class="math-container">$s$</span>. Let <span class="math-container">$r_\pi(s)$</span> denote the expected immediate reward and <span class="math-container">$p_\pi(s^\prime | s)$</span> the probability of transitioning to state <span class="math-container">$s^\prime$</span> when following policy <span class="math-container">$\pi$</span> from state <span class="math-container">$s$</span>. Let <span class="math-container">$\gamma \in (0, 1)$</span> denote the discount rate for future rewards. The Bellman equation for the state-value function for policy <span class="math-container">$\pi$</span> can be defined as follows:</p>
  <p><span class="math-container">$$
  \begin{aligned}
  v_{\pi}(s) &amp;= \mathbb{E}_\pi \big[R_{t+1} + \gamma v_{\pi}(S_{t+1}) | S_t = s \big] \\
  &amp;= \sum_{a \in \mathcal{A}(s)} \pi(a | s) \bigg[\sum_{r \in \mathcal{R}} p(r | s, a) r + \gamma \sum_{s^\prime \in \mathcal{S}} p(s^\prime | s, a) v_{\pi}(s^\prime) \bigg] \\
  &amp;= r_\pi(s) + \gamma \sum_{s^\prime \in \mathcal{S}} p_\pi(s^\prime | s) v_{\pi}(s^\prime)
  \end{aligned} \tag 1
  $$</span></p>
  <p>for all <span class="math-container">$s \in \mathcal{S}$</span>. Let <span class="math-container">$n = |\mathcal{S}|$</span>, we can write the equation in matrix form:</p>
  <p><span class="math-container">$$
  \begin{bmatrix}
  v_\pi(1) \\
  \vdots \\
  v_\pi(n)
  \end{bmatrix}=
  \begin{bmatrix}
  r_\pi(1) \\
  \vdots \\
  r_\pi(n)
  \end{bmatrix}
  +\gamma
  \begin{bmatrix}
  p_\pi(1 | 1) &amp; \dots &amp; p_\pi(n | 1) \\
  \vdots &amp; \ddots &amp; \vdots\\
  p_\pi(1 | n) &amp; \dots &amp; p_\pi(n | n)
  \end{bmatrix}
  \begin{bmatrix}
  v_\pi(1) \\
  \vdots \\
  v_\pi(n)
  \end{bmatrix} \tag 2
  $$</span></p>
  <p>More compactly:</p>
  <p><span class="math-container">$$
  v_\pi = r_\pi + \gamma P_\pi v_\pi \tag 3
  $$</span></p>
  <p>We can define an expected Bellman operator <span class="math-container">$\mathcal{T}^\pi : \mathbb{R}^n \to \mathbb{R}^n$</span> as:</p>
  <p><span class="math-container">$$
  \mathcal{T}^\pi(v) = r_\pi + \gamma P_\pi v \tag 4
  $$</span></p>
  <p>for any <span class="math-container">$v \in \mathbb{R}^n$</span>.</p>
  <p>Let <span class="math-container">$||\cdot||$</span> be a norm in <span class="math-container">$\mathbb{R}^n$</span>. If there exists a <span class="math-container">$\gamma \in (0, 1)$</span> such that <span class="math-container">$||\mathcal{T}^\pi(v_1) - \mathcal{T}^\pi(v_2)|| \leq \gamma ||v_1 - v_2||$</span> for all <span class="math-container">$v_1, v_2 \in \mathbb{R}^n$</span>, then <span class="math-container">$\mathcal{T}^\pi$</span> is a contraction mapping. In all proofs in this post <span class="math-container">$|\cdot|$</span> and <span class="math-container">$\leq$</span> are elementwise, and the norm used is the max norm <span class="math-container">$||x||_\infty = \max(|x|) = \max(|x_1|, \dots, |x_n|)$</span>, where <span class="math-container">$\max(\cdot) : \mathbb{R}^n \to \mathbb{R}$</span> chooses the largest element in a vector.</p>
  <p><span class="math-container">$$
  \begin{aligned}
  ||\mathcal{T}^\pi(v_1) - \mathcal{T}^\pi(v_2)||_\infty &amp;= \max \big(|r_\pi + \gamma P_\pi v_1 - (r_\pi + \gamma P_\pi v_2)| \big) \\
  &amp;= \gamma \max \big(|P_\pi(v_1 - v_2)| \big) \\
  &amp;\leq \gamma \max \big(P_\pi|v_1 - v_2| \big) \\
  &amp;\leq \gamma \max \big(|v_1 - v_2| \big) \\
  &amp;= \gamma ||v_1 - v_2||_\infty
  \end{aligned}
  \tag 5
  $$</span></p>
  <p>Thus <span class="math-container">$\mathcal{T}^\pi$</span> is a contraction. The last inequality is due to the rows of <span class="math-container">$P_\pi$</span> containing only non-negative elements that sum to 1.</p>
  <p>Let <span class="math-container">$r(s, a)$</span> denote the expected immediate reward when selecting action <span class="math-container">$a$</span> in state <span class="math-container">$s$</span>, and <span class="math-container">$p_\pi(s^\prime, a^\prime | s, a)$</span> the probability of transitioning to state <span class="math-container">$s^\prime$</span> and selecting action <span class="math-container">$a^\prime$</span> when selecting action <span class="math-container">$a$</span> in state <span class="math-container">$s$</span> and following policy <span class="math-container">$\pi$</span> after. The Bellman equation for the action-value function for policy <span class="math-container">$\pi$</span> can be defined as follows:</p>
  <p><span class="math-container">$$
  \begin{aligned}
  q_{\pi}(s, a) &amp;= \mathbb{E}_\pi \big[R_{t+1} + \gamma q_{\pi}(S_{t+1}, A_{t+1}) | S_t = s, A_t = a \big] \\
  &amp;=  \sum_{r \in \mathcal{R}} p(r | s, a) r + \gamma \sum_{s^\prime \in \mathcal{S}} p(s^\prime | s, a) \sum_{a^\prime \in \mathcal{A}(s^\prime)} \pi(a^\prime | s^\prime) q_{\pi}(s^\prime, a^\prime) \\
  &amp;= r(s, a) + \gamma \sum_{s^\prime \in \mathcal{S}} \sum_{a^\prime \in \mathcal{A}(s^\prime)} p_\pi(s^\prime, a^\prime | s, a) q_{\pi}(s^\prime, a^\prime)
  \end{aligned} \tag 6
  $$</span></p>
  <p>for all <span class="math-container">$s \in \mathcal{S}$</span>, <span class="math-container">$a \in \mathcal{A}(s)$</span>. Let <span class="math-container">$n_s = |\mathcal{A}(s)|$</span>, we can write the equation in matrix form:</p>
  <p><span class="math-container">$$
  \begin{bmatrix}
  q_\pi(1, 1) \\
  q_\pi(1, 2) \\
  \vdots \\
  q_\pi(n, n_n)
  \end{bmatrix}=
  \begin{bmatrix}
  r_\pi(1, 1) \\
  r_\pi(1, 2) \\
  \vdots \\
  r_\pi(n, n_n)
  \end{bmatrix}
  +\gamma
  \begin{bmatrix}
  p_\pi(1, 1 | 1, 1) &amp; p_\pi(1, 2 | 1, 1) &amp; \dots &amp; p_\pi(n, n_n | 1, 1) \\
  p_\pi(1, 1 | 1, 2) &amp; p_\pi(1, 2 | 1, 2) &amp; \dots &amp; p_\pi(n, n_n | 1, 2) \\
  \vdots &amp; \vdots &amp; \ddots &amp; \vdots \\
  p_\pi(1, 1 | n, n_n) &amp; p_\pi(1, 2 | n, n_n) &amp; \dots &amp; p_\pi(n, n_n | n, n_n)
  \end{bmatrix}
  \begin{bmatrix}
  q_\pi(1, 1) \\
  q_\pi(1, 2) \\
  \vdots \\
  q_\pi(n, n_n)
  \end{bmatrix} \tag 7
  $$</span></p>
  <p>More compactly:</p>
  <p><span class="math-container">$$
  q_\pi = r_\pi + \gamma P_\pi q_\pi \tag 8
  $$</span></p>
  <p>The only difference compared to the equation for the state-value function is that the vectors and matrices are larger. Thus, we can define an expected Bellman operator in identical fashion (with <span class="math-container">$n$</span> denoting the number of state-action pairs rather than the number of states) and the proof will be identical (the rows of <span class="math-container">$P_\pi$</span> still contain only non-negative elements that sum to 1).</p>
  <h2>Bellman optimality equations</h2>
  <p>For brevity I will go directly into the compact matrix form of the Bellman optimality equation for the optimal state-value function:</p>
  <p><span class="math-container">$$
  v_* = \max_\pi(r_\pi + \gamma P_\pi v_*) \tag 9
  $$</span></p>
  <p>We can define an expected Bellman optimality operator <span class="math-container">$\mathcal{T}^* : \mathbb{R}^n \to \mathbb{R}^n$</span> as:</p>
  <p><span class="math-container">$$
  \mathcal{T}^*(v) = \max_\pi(r_\pi + \gamma P_\pi v) \tag {11}
  $$</span></p>
  <p>The rest of the post will focus on trying to prove that this is a contraction operator, because once again I believe that an identical proof works for the action-value function (please correct me if this is wrong).</p>
  <p>Consider any two vectors <span class="math-container">$v_1, v_2 \in \mathbb{R}^n$</span>, and let <span class="math-container">$\pi_1^* = \text{argmax}_\pi(r_\pi + \gamma P_\pi v_1)$</span> and <span class="math-container">$\pi_2^* = \text{argmax}_\pi(r_\pi + \gamma P_\pi v_2)$</span>. Then we have:</p>
  <p><span class="math-container">$$
  \mathcal{T}^*(v_1) = \max_\pi(r_\pi + \gamma P_\pi v_1) = r_{\pi_1^*} + \gamma P_{\pi_1^*} v_1 \geq r_{\pi_2^*} + \gamma P_{\pi_2^*} v_1 \\
  \mathcal{T}^*(v_2) = \max_\pi(r_\pi + \gamma P_\pi v_2) = r_{\pi_2^*} + \gamma P_{\pi_2^*} v_2 \geq r_{\pi_1^*} + \gamma P_{\pi_1^*} v_2 \tag{12}
  $$</span></p>
  <p><span class="math-container">$$
  \begin{aligned}
  \mathcal{T}^*(v_1) - \mathcal{T}^*(v_2) &amp;= r_{\pi_1^*} + \gamma P_{\pi_1^*} v_1 - (r_{\pi_2^*} + \gamma P_{\pi_2^*} v_2) \\
  &amp;\leq r_{\pi_1^*} + \gamma P_{\pi_1^*} v_1 - (r_{\pi_1^*} + \gamma P_{\pi_1^*} v_2) \\
  &amp;= \gamma P_{\pi_1^*} (v_1 - v_2)
  \end{aligned}
  $$</span></p>
  <p>Similarly we have <span class="math-container">$\mathcal{T}^*(v_2) - \mathcal{T}^*(v_1) \leq \gamma P_{\pi_2^*} (v_2 - v_1)$</span>, which implies that <span class="math-container">$\mathcal{T}^*(v_1) - \mathcal{T}^*(v_2) \geq \gamma P_{\pi_2^*} (v_1 - v_2)$</span>, and thus we have:</p>
  <p><span class="math-container">$$
  \gamma P_{\pi_2^*} (v_1 - v_2) \leq \mathcal{T}^*(v_1) - \mathcal{T}^*(v_2) \leq \gamma P_{\pi_1^*} (v_1 - v_2) \tag{13}
  $$</span></p>
  <p>Let <span class="math-container">$\max\{\cdot, \cdot \} : \mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}^n$</span> choose the largest values between two vectors elementwise, we have:</p>
  
  <span class="math-container">$$
  \begin{aligned}
  |\mathcal{T}^*(v_1) - \mathcal{T}^*(v_2)| &amp;\leq \max \{|\gamma P_{\pi_2^*} (v_1 - v_2)|, |\gamma P_{\pi_1^*} (v_1 - v_2)| \} \\
  &amp;\leq \gamma \max \{P_{\pi_2^*} |v_1 - v_2|, P_{\pi_1^*} |v_1 - v_2| \}
  \end{aligned}
  $$</span>
  
  <p>Let <span class="math-container">$\max(\cdot) : \mathbb{R}^n \to \mathbb{R}$</span> choose the largest element in a vector (as previously defined), we have:</p>
  
  <span class="math-container">$$
  \begin{aligned}
  ||\mathcal{T}^*(v_1) - \mathcal{T}^*(v_2)||_\infty &amp;= \max \big(|\mathcal{T}^*(v_1) - \mathcal{T}^*(v_2)| \big) \\
  &amp;\leq \gamma \max \big(\max \{P_{\pi_2^*} |v_1 - v_2|, P_{\pi_1^*} |v_1 - v_2| \} \big) \\
  &amp;\leq \gamma \max \big(|v_1 - v_2| \big) \\
  &amp;= \gamma ||v_1 - v_2||_\infty
  \end{aligned}
  $$</span>
  
  <p>Thus <span class="math-container">$\mathcal{T}^*$</span> is a contraction. Note that the last inequality is once again due to the rows of <span class="math-container">$P_\pi$</span> containing only non-negative elements that sum to 1.</p>
  <p>Thank you for reading this far! If you have the time, please let me know if the proofs are correct, if the proofs for the state-value and action-value functions are identical as I suggest, and any other feedback.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-12-31T12:37:12.447Z
Comments.Text: This post is way too long. You should have simplified it or split it into multiple ones, for example, if you're concerned about multiple proofs, which seems to be the case.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><math><proofs><bellman-equations><bellman-operators>
Title: Are my proofs that the Bellman operators are contractions correct?
UserDisplayName: cfml
ThreadText: # Are my proofs that the Bellman operators are contractions correct?
  
  (Asked by: username_0 on 2022-10-13)
  
  ## Introduction
  
  I'm studying Reinforcement Learning, and in order to increase my understanding I've been challenging myself by trying to write proofs that show that the right hand side of the Bellman equations and Bellman optimality equations for state-value and action-value functions are contraction operators. The fact that the Bellman operators are contractions is of great importance, since this proves that the Bellman equations have unique fixed points that can be solved for iteratively, due to the Banach fixed-point theorem.
  
  Below are my attempts at the proofs, my questions are:
  
  1. Are the proofs correct?
  2. Any feedback on what can be improved (I'm very inexperienced in writing proofs and would like to get better)?
  
  I will assume some knowledge about finite Markov Decision Processes (MDPs), please let me know if you want me to elaborate.
  
  ## Bellman equations
  
  Let $\mathcal{S}$ denote the finite set of all states, $\mathcal{R} \subset \mathbb{R}$ the finite set of all rewards, and $\mathcal{A}(s)$ the finite set of all available actions $a$ in state $s$. Let $r\_\pi(s)$ denote the expected immediate reward and $p\_\pi(s^\prime | s)$ the probability of transitioning to state $s^\prime$ when following policy $\pi$ from state $s$. Let $\gamma \in (0, 1)$ denote the discount rate for future rewards. The Bellman equation for the state-value function for policy $\pi$ can be defined as follows:
  
  $$
  \begin{aligned}
  v\_{\pi}(s) &= \mathbb{E}\_\pi \big[R\_{t+1} + \gamma v\_{\pi}(S\_{t+1}) | S\_t = s \big] \\
  &= \sum\_{a \in \mathcal{A}(s)} \pi(a | s) \bigg[\sum\_{r \in \mathcal{R}} p(r | s, a) r + \gamma \sum\_{s^\prime \in \mathcal{S}} p(s^\prime | s, a) v\_{\pi}(s^\prime) \bigg] \\
  &= r\_\pi(s) + \gamma \sum\_{s^\prime \in \mathcal{S}} p\_\pi(s^\prime | s) v\_{\pi}(s^\prime)
  \end{aligned} \tag 1
  $$
  
  for all $s \in \mathcal{S}$. Let $n = |\mathcal{S}|$, we can write the equation in matrix form:
  
  $$
  \begin{bmatrix}
  v\_\pi(1) \\
  \vdots \\
  v\_\pi(n)
  \end{bmatrix}=
  \begin{bmatrix}
  r\_\pi(1) \\
  \vdots \\
  r\_\pi(n)
  \end{bmatrix}
  +\gamma
  \begin{bmatrix}
  p\_\pi(1 | 1) & \dots & p\_\pi(n | 1) \\
  \vdots & \ddots & \vdots\\
  p\_\pi(1 | n) & \dots & p\_\pi(n | n)
  \end{bmatrix}
  \begin{bmatrix}
  v\_\pi(1) \\
  \vdots \\
  v\_\pi(n)
  \end{bmatrix} \tag 2
  $$
  
  More compactly:
  
  $$
  v\_\pi = r\_\pi + \gamma P\_\pi v\_\pi \tag 3
  $$
  
  We can define an expected Bellman operator $\mathcal{T}^\pi : \mathbb{R}^n \to \mathbb{R}^n$ as:
  
  $$
  \mathcal{T}^\pi(v) = r\_\pi + \gamma P\_\pi v \tag 4
  $$
  
  for any $v \in \mathbb{R}^n$.
  
  Let $||\cdot||$ be a norm in $\mathbb{R}^n$. If there exists a $\gamma \in (0, 1)$ such that $||\mathcal{T}^\pi(v\_1) - \mathcal{T}^\pi(v\_2)|| \leq \gamma ||v\_1 - v\_2||$ for all $v\_1, v\_2 \in \mathbb{R}^n$, then $\mathcal{T}^\pi$ is a contraction mapping. In all proofs in this post $|\cdot|$ and $\leq$ are elementwise, and the norm used is the max norm $||x||\_\infty = \max(|x|) = \max(|x\_1|, \dots, |x\_n|)$, where $\max(\cdot) : \mathbb{R}^n \to \mathbb{R}$ chooses the largest element in a vector.
  
  $$
  \begin{aligned}
  ||\mathcal{T}^\pi(v\_1) - \mathcal{T}^\pi(v\_2)||\_\infty &= \max \big(|r\_\pi + \gamma P\_\pi v\_1 - (r\_\pi + \gamma P\_\pi v\_2)| \big) \\
  &= \gamma \max \big(|P\_\pi(v\_1 - v\_2)| \big) \\
  &\leq \gamma \max \big(P\_\pi|v\_1 - v\_2| \big) \\
  &\leq \gamma \max \big(|v\_1 - v\_2| \big) \\
  &= \gamma ||v\_1 - v\_2||\_\infty
  \end{aligned}
  \tag 5
  $$
  
  Thus $\mathcal{T}^\pi$ is a contraction. The last inequality is due to the rows of $P\_\pi$ containing only non-negative elements that sum to 1.
  
  Let $r(s, a)$ denote the expected immediate reward when selecting action $a$ in state $s$, and $p\_\pi(s^\prime, a^\prime | s, a)$ the probability of transitioning to state $s^\prime$ and selecting action $a^\prime$ when selecting action $a$ in state $s$ and following policy $\pi$ after. The Bellman equation for the action-value function for policy $\pi$ can be defined as follows:
  
  $$
  \begin{aligned}
  q\_{\pi}(s, a) &= \mathbb{E}\_\pi \big[R\_{t+1} + \gamma q\_{\pi}(S\_{t+1}, A\_{t+1}) | S\_t = s, A\_t = a \big] \\
  &= \sum\_{r \in \mathcal{R}} p(r | s, a) r + \gamma \sum\_{s^\prime \in \mathcal{S}} p(s^\prime | s, a) \sum\_{a^\prime \in \mathcal{A}(s^\prime)} \pi(a^\prime | s^\prime) q\_{\pi}(s^\prime, a^\prime) \\
  &= r(s, a) + \gamma \sum\_{s^\prime \in \mathcal{S}} \sum\_{a^\prime \in \mathcal{A}(s^\prime)} p\_\pi(s^\prime, a^\prime | s, a) q\_{\pi}(s^\prime, a^\prime)
  \end{aligned} \tag 6
  $$
  
  for all $s \in \mathcal{S}$, $a \in \mathcal{A}(s)$. Let $n\_s = |\mathcal{A}(s)|$, we can write the equation in matrix form:
  
  $$
  \begin{bmatrix}
  q\_\pi(1, 1) \\
  q\_\pi(1, 2) \\
  \vdots \\
  q\_\pi(n, n\_n)
  \end{bmatrix}=
  \begin{bmatrix}
  r\_\pi(1, 1) \\
  r\_\pi(1, 2) \\
  \vdots \\
  r\_\pi(n, n\_n)
  \end{bmatrix}
  +\gamma
  \begin{bmatrix}
  p\_\pi(1, 1 | 1, 1) & p\_\pi(1, 2 | 1, 1) & \dots & p\_\pi(n, n\_n | 1, 1) \\
  p\_\pi(1, 1 | 1, 2) & p\_\pi(1, 2 | 1, 2) & \dots & p\_\pi(n, n\_n | 1, 2) \\
  \vdots & \vdots & \ddots & \vdots \\
  p\_\pi(1, 1 | n, n\_n) & p\_\pi(1, 2 | n, n\_n) & \dots & p\_\pi(n, n\_n | n, n\_n)
  \end{bmatrix}
  \begin{bmatrix}
  q\_\pi(1, 1) \\
  q\_\pi(1, 2) \\
  \vdots \\
  q\_\pi(n, n\_n)
  \end{bmatrix} \tag 7
  $$
  
  More compactly:
  
  $$
  q\_\pi = r\_\pi + \gamma P\_\pi q\_\pi \tag 8
  $$
  
  The only difference compared to the equation for the state-value function is that the vectors and matrices are larger. Thus, we can define an expected Bellman operator in identical fashion (with $n$ denoting the number of state-action pairs rather than the number of states) and the proof will be identical (the rows of $P\_\pi$ still contain only non-negative elements that sum to 1).
  
  ## Bellman optimality equations
  
  For brevity I will go directly into the compact matrix form of the Bellman optimality equation for the optimal state-value function:
  
  $$
  v\_\* = \max\_\pi(r\_\pi + \gamma P\_\pi v\_\*) \tag 9
  $$
  
  We can define an expected Bellman optimality operator $\mathcal{T}^\* : \mathbb{R}^n \to \mathbb{R}^n$ as:
  
  $$
  \mathcal{T}^\*(v) = \max\_\pi(r\_\pi + \gamma P\_\pi v) \tag {11}
  $$
  
  The rest of the post will focus on trying to prove that this is a contraction operator, because once again I believe that an identical proof works for the action-value function (please correct me if this is wrong).
  
  Consider any two vectors $v\_1, v\_2 \in \mathbb{R}^n$, and let $\pi\_1^\* = \text{argmax}\_\pi(r\_\pi + \gamma P\_\pi v\_1)$ and $\pi\_2^\* = \text{argmax}\_\pi(r\_\pi + \gamma P\_\pi v\_2)$. Then we have:
  
  $$
  \mathcal{T}^\*(v\_1) = \max\_\pi(r\_\pi + \gamma P\_\pi v\_1) = r\_{\pi\_1^\*} + \gamma P\_{\pi\_1^\*} v\_1 \geq r\_{\pi\_2^\*} + \gamma P\_{\pi\_2^\*} v\_1 \\
  \mathcal{T}^\*(v\_2) = \max\_\pi(r\_\pi + \gamma P\_\pi v\_2) = r\_{\pi\_2^\*} + \gamma P\_{\pi\_2^\*} v\_2 \geq r\_{\pi\_1^\*} + \gamma P\_{\pi\_1^\*} v\_2 \tag{12}
  $$
  
  $$
  \begin{aligned}
  \mathcal{T}^\*(v\_1) - \mathcal{T}^\*(v\_2) &= r\_{\pi\_1^\*} + \gamma P\_{\pi\_1^\*} v\_1 - (r\_{\pi\_2^\*} + \gamma P\_{\pi\_2^\*} v\_2) \\
  &\leq r\_{\pi\_1^\*} + \gamma P\_{\pi\_1^\*} v\_1 - (r\_{\pi\_1^\*} + \gamma P\_{\pi\_1^\*} v\_2) \\
  &= \gamma P\_{\pi\_1^\*} (v\_1 - v\_2)
  \end{aligned}
  $$
  
  Similarly we have $\mathcal{T}^\*(v\_2) - \mathcal{T}^\*(v\_1) \leq \gamma P\_{\pi\_2^\*} (v\_2 - v\_1)$, which implies that $\mathcal{T}^\*(v\_1) - \mathcal{T}^\*(v\_2) \geq \gamma P\_{\pi\_2^\*} (v\_1 - v\_2)$, and thus we have:
  
  $$
  \gamma P\_{\pi\_2^\*} (v\_1 - v\_2) \leq \mathcal{T}^\*(v\_1) - \mathcal{T}^\*(v\_2) \leq \gamma P\_{\pi\_1^\*} (v\_1 - v\_2) \tag{13}
  $$
  
  Let $\max\{\cdot, \cdot \} : \mathbb{R}^n \times \mathbb{R}^n \to \mathbb{R}^n$ choose the largest values between two vectors elementwise, we have:
  
  $$
  \begin{aligned}
  |\mathcal{T}^\*(v\_1) - \mathcal{T}^\*(v\_2)| &\leq \max \{|\gamma P\_{\pi\_2^\*} (v\_1 - v\_2)|, |\gamma P\_{\pi\_1^\*} (v\_1 - v\_2)| \} \\
  &\leq \gamma \max \{P\_{\pi\_2^\*} |v\_1 - v\_2|, P\_{\pi\_1^\*} |v\_1 - v\_2| \}
  \end{aligned}
  $$
  
  Let $\max(\cdot) : \mathbb{R}^n \to \mathbb{R}$ choose the largest element in a vector (as previously defined), we have:
  
  $$
  \begin{aligned}
  ||\mathcal{T}^\*(v\_1) - \mathcal{T}^\*(v\_2)||\_\infty &= \max \big(|\mathcal{T}^\*(v\_1) - \mathcal{T}^\*(v\_2)| \big) \\
  &\leq \gamma \max \big(\max \{P\_{\pi\_2^\*} |v\_1 - v\_2|, P\_{\pi\_1^\*} |v\_1 - v\_2| \} \big) \\
  &\leq \gamma \max \big(|v\_1 - v\_2| \big) \\
  &= \gamma ||v\_1 - v\_2||\_\infty
  \end{aligned}
  $$
  
  Thus $\mathcal{T}^\*$ is a contraction. Note that the last inequality is once again due to the rows of $P\_\pi$ containing only non-negative elements that sum to 1.
  
  Thank you for reading this far! If you have the time, please let me know if the proofs are correct, if the proofs for the state-value and action-value functions are identical as I suggest, and any other feedback.
  
  **Tags:** reinforcement-learning, math, proofs, bellman-equations, bellman-operators
  > **Comments:**
  > **username_1**: This post is way too long. You should have simplified it or split it into multiple ones, for example, if you're concerned about multiple proofs, which seems to be the case.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2022-10-28. Score: 1 | Accepted answer
  
  My first impression is that the proofs are correct, but there is a shorter way. If you first prove that the Bellman optimality operator is a contraction, then it is a corollary that the other two operators are also contractions. For the state-value function, let the set over which you maximize in (9) and (11) be a singleton. For the action-value function, let the set over which you maximize in (9) and (11) be a singleton containing a Dirac measure. By the way, you did not specify the set of admissible policies and a few other things.
  
  
  ---
  
  