Answers.Body: <p>There exist other RL books which do a better job of talking about this but it's pretty simple at it's core.</p>
  
  <p>The discounting factor puts an upper limit on the difference in reward between a finite number of iterations and an infinite number, each time you add another iteration it decreases by <span class="math-container">$\gamma$</span> multiplied into the upper bound of the difference.</p>
  
  <p><span class="math-container">$V_\pi = E[\sum_{i=0}^{\infty} \gamma^iR_i]$</span>, <span class="math-container">$\Delta V_k = E[\sum_{i=k}^{\infty} \gamma^iR_i] = \gamma^k E[\sum_{i=0}^{\infty} \gamma^{i}R_{i+k}] &lt; \gamma^k \frac{1}{1-\gamma}R_{max}$</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-16T15:01:44.310Z
Answers.Text: This explanation isn't clear at all (to me). The discount factor may play a role, but that doesn't give much intuition behind the algorithm, what it does and why it converges, in my opinion. I think it would be nice if you could provide a full description of the proof (maybe taken from a book, that's fine!). I think a good answer would start from a description of the algorithm and what it does. Then it proves why it converges.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-16T15:43:30.380Z
Answers.Text: @SAGALPREETSINGH I may provide a more formal and complete answer later, if Fourier doesn't decide to do it.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-16T15:45:08.303Z
Answers.Text: @FourierFlux can you please be a bit more descriptive. I am not able to understand your answer. I think you didn't get my question right. I wanted to know, how policy evaluation works out and it happens that the algorithm converges. The intuition I formed for this is that everytime we iterate over current value function, we get closer to the actual one because after each iteration, our value function becomes more and more appropriate but how in the world does it go so close to the actual answer. What was the actual motivation behind using Bellman equation as an update rule.
Answers.UserDisplayName: SAGALPREET SINGH
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-16T14:54:20.743Z
Answers.LastActivityDate: 2020-04-16T17:23:43.040Z
Answers.LastEditDate: 2020-04-16T17:23:43.040Z
Answers.UserDisplayName: FourierFlux
Answers.Body: <p>First of all, <a href="https://en.wikipedia.org/wiki/Algorithmic_efficiency" rel="noreferrer">efficiency</a> and convergence are two different things. There's also the <a href="https://en.wikipedia.org/wiki/Rate_of_convergence" rel="noreferrer">rate of convergence</a>, so an algorithm may converge faster than another, so, in this sense, it may be more efficient. I will focus on the proof that policy evaluation (PE) converges. If you want to know about its efficiency, maybe ask another question, but the proof below also tells you about the rate of convergence of PE.</p>
  <blockquote>
  <p>What is the proof that policy evaluation converges to the optimal solution?</p>
  </blockquote>
  <p>To provide some context, I will briefly describe policy evaluation and what you need to know to understand the proof.</p>
  <h2>Policy evaluation</h2>
  <p>Policy evaluation (PE) is an iterative numerical algorithm to find the value function <span class="math-container">$v^\pi$</span> for a given (and arbitrary) policy <span class="math-container">$\pi$</span>. This problem is often called the <em>prediction problem</em> (i.e. you want to predict the rewards you will get if you behave in a certain way).</p>
  <h3>Two versions: synchronous and asynchronous</h3>
  <p>There are (at least) two versions of policy evaluation: a synchronous one and an asynchronous one.</p>
  <p>In the <strong>synchronous</strong> version (SPE), you maintain two arrays for the values of the states: one array holds the current values of the states and the other array will contain the next values of the states, so two arrays are used in order to be able to update the value of each state at the same time.</p>
  <p>In the <strong>asynchronous</strong> version (APE), you update the value of each state in place. So, first, you update the value of e.g. <span class="math-container">$s_1$</span>, then <span class="math-container">$s_2$</span>, etc., by changing your only array of values (so you do not require a second array).</p>
  <p>SPE is similar in style to the numerical method called <a href="https://en.wikipedia.org/wiki/Jacobi_method" rel="noreferrer">Jacobi method</a>, which is a general iterative method for finding a solution to a system of linear equations (which is exactly what PE is actually doing, and this is also explained in the cited book by Sutton and Barto). Similarly, APE is similar in style to <a href="https://en.wikipedia.org/wiki/Gauss%E2%80%93Seidel_method" rel="noreferrer">the Gauss–Seidel method</a>, which is another method to solve a system of linear equations.</p>
  <p>Both of these general numerical methods to solve a system of linear equations are studied in detail in <a href="https://labs.xjtudlc.com/labs/wldmt/reading%20list/books/Distributed%20and%20parallel%20algorithms/Parallel%20and%20Distributed%20Computation%20Numerical%20Methods.pdf" rel="noreferrer">Parallel and Distributed Computation Numerical Methods</a> (1989) by Bertsekas and Tsitsiklis, which I haven't read yet, but provides convergence results for these numerical methods.</p>
  <p>The book <a href="http://incompleteideas.net/book/RLbook2020.pdf" rel="noreferrer">Reinforcement learning: an introduction</a> by Sutton and Barto provides a more detailed description of policy evaluation (PE).</p>
  <h2>Proof of convergence</h2>
  <p>I will provide a proof for the SPE based on <a href="http://www.andrew.cmu.edu/course/10-703/slides/lecture4_valuePolicyDP-9-10-2018.pdf" rel="noreferrer">these slides</a> by <a href="http://www.cs.cmu.edu/%7Etom/" rel="noreferrer">Tom Mitchell</a>. Before proceeding, I suggest you read the following question  <a href="https://ai.stackexchange.com/q/11057/2444">What is the Bellman operator in reinforcement learning?</a> and its answer, and you should also get familiar with vector spaces, norms, fixed points and maybe contraction mappings.</p>
  <p>The proof that PE finds a unique fixed-point is based on the <strong>contraction mapping theorem</strong> and on the concept of <strong><span class="math-container">$\gamma$</span>-contractions</strong>, so let me first recall these definitions.</p>
  <blockquote>
  <p><strong>Definition (<span class="math-container">$\gamma$</span>-contraction)</strong>: An operator on a normed vector space <span class="math-container">$\mathcal{X}$</span> is a <span class="math-container">$\gamma$</span>-contraction, for <span class="math-container">$0 &lt; \gamma &lt; 1$</span>, provided for all  <span class="math-container">$x, y \in \mathcal{X}$</span></p>
  <p><span class="math-container">$$\| F(x) - F(y) \| \leq \gamma \| x - y\|$$</span></p>
  <p><strong>Contraction mapping theorem</strong>: For a <span class="math-container">$\gamma$</span>-contraction <span class="math-container">$F$</span> in a complete normed vector space <span class="math-container">$\mathcal{X}$</span></p>
  <ul>
  <li><p>Iterative application of <span class="math-container">$F$</span> converges to a <strong>unique</strong> fixed point in <span class="math-container">$\mathcal{X}$</span> independently of the starting point</p>
  </li>
  <li><p>at a linear convergence rate determined by <span class="math-container">$\gamma$</span></p>
  </li>
  </ul>
  </blockquote>
  <p>Now, consider the vector space <span class="math-container">$\mathcal{V}$</span> over state-value functions <span class="math-container">$v$</span> (i.e. <span class="math-container">$v \in \mathcal{V})$</span>. So, each point in this space fully specifies a value function <span class="math-container">$v : \mathcal{S} \rightarrow \mathbb{R}$</span> (where <span class="math-container">$\mathcal{S}$</span> is the state space of the MDP).</p>
  <p><strong>Theorem (convergence of PE)</strong>: The <a href="https://ai.stackexchange.com/q/11057/2444">Bellman operator</a> is a <span class="math-container">$\gamma$</span>-contraction operator, so an iterative application of it converges to a unique fixed-point in <span class="math-container">$\mathcal{V}$</span>. Given that PE is an iterative application of the Bellman operator (see <a href="https://ai.stackexchange.com/q/11057/2444">What is the Bellman operator in reinforcement learning?</a>), PE finds this unique fixed-point solution.</p>
  <p>So, we just need to show that the Bellman operator is a <span class="math-container">$\gamma$</span>-contraction operator in order to show that PE finds this unique fixed-point solution.</p>
  <h3>Proof</h3>
  <p>We will measure the distance between state-value functions <span class="math-container">$u$</span> and <span class="math-container">$v$</span> by the <span class="math-container">$\infty$</span>-norm, i.e. the largest difference between state values:</p>
  <p><span class="math-container">$$\|u - v\|_{\infty} = \operatorname{max}_{s \in \mathcal{S}} |u(s) - v(s)|$$</span></p>
  <p><strong>Definition (Bellman operator)</strong>: We define the Bellman expectation operator as</p>
  <p><span class="math-container">$$F^\pi(v) = \mathbf{r}^\pi + \gamma \mathbf{T}^\pi v$$</span></p>
  <p>where <span class="math-container">$v \in \mathcal{V}$</span>, <span class="math-container">$\mathbf{r}^\pi$</span> is an <span class="math-container">$|\mathcal{S}|$</span>-dimensional vector whose <span class="math-container">$j$</span>th entry gives <span class="math-container">$\mathbb{E} \left[ r \mid s_j, a=\pi(s_j) \right]$</span> and <span class="math-container">$\mathbf{T}^\pi$</span> is an <span class="math-container">$|\mathcal{S}| \times |\mathcal{S}|$</span> matrix whose <span class="math-container">$(j, k)$</span> entry gives <span class="math-container">$\mathbb{P}(s_k \mid s_j, a=\pi(s_j))$</span>.</p>
  <p>Now, let's measure the distance (with the <span class="math-container">$\infty$</span>-norm defined above) between any two value functions <span class="math-container">$u \in \mathcal{V}$</span> and <span class="math-container">$v \in \mathcal{V}$</span> after the application of the Bellman operator <span class="math-container">$F^\pi$</span></p>
  <p><span class="math-container">\begin{align}
  \| F^\pi(u) - F^\pi(v) \|_{\infty} 
  &amp;= \| (\mathbf{r}^\pi + \gamma \mathbf{T}^\pi u) - (\mathbf{r}^\pi + \gamma \mathbf{T}^\pi v)\|_{\infty} \\
  &amp;= \| \gamma \mathbf{T}^\pi (u - v)\|_{\infty} \\
  &amp;\leq \| \gamma \mathbf{T}^\pi ( \mathbb{1} \cdot \| u - v \|_{\infty})\|_{\infty} \\
  &amp;\leq \| \gamma (\mathbf{T}^\pi \mathbb{1}) \cdot \| u - v \|_{\infty}\|_{\infty} \\
  &amp;\leq \gamma \| u - v \|_{\infty}
  \end{align}</span></p>
  <p>where <span class="math-container">$\mathbb{1} = [1, \dots, 1]^T$</span>. Note that <span class="math-container">$\mathbf{T}^\pi \cdot \mathbb{1} = \mathbb{1}$</span> because <span class="math-container">$\mathbf{T}^\pi$</span> is a <a href="https://en.wikipedia.org/wiki/Stochastic_matrix" rel="noreferrer">stochastic matrix</a>.</p>
  <p>By the Bellman expectation equation (see Barto and Sutton's book and <a href="https://ai.stackexchange.com/q/11057/2444">What is the Bellman operator in reinforcement learning?</a>), <span class="math-container">$v^\pi$</span> is <strong>a</strong> fixed-point of the Bellman operator <span class="math-container">$F^\pi$</span>. Given the contraction mapping theorem, the iterative application of <span class="math-container">$F^\pi$</span> produces a <strong>unique</strong> solution, so <span class="math-container">$v^\pi$</span> must be this unique solution, i.e. SPE finds <span class="math-container">$v^\pi$</span>. <a href="https://ai.stackexchange.com/a/22970/2444">Here</a> is another version of the proof that the Bellman operator is a contraction.</p>
  <h2>Notes</h2>
  <p>I didn't prove the contraction mapping theorem, but you can find more info about the theorem and its proof in <a href="https://en.wikipedia.org/wiki/Banach_fixed-point_theorem" rel="noreferrer">the related Wikipedia article</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-16T17:19:43.513Z
Answers.LastActivityDate: 2022-01-22T21:45:31.967Z
Answers.LastEditDate: 2022-01-22T21:45:31.967Z
Answers.UserDisplayName: nbro
Body: <p>Although I know how the algorithm of iterative policy evaluation using dynamic programming works, I am having a hard time realizing how it actually converges.</p>
  
  <p>It appeals to intuition that, with each iteration, we get a better and better approximation for the value function and we can thus assure its convergence, but with this said simply, it seems that this method is very inefficient contrary to the reality that it actually is quite efficient.</p>
  
  <p>What is the rigorous mathematical proof of the convergence of the policy evaluation algorithm to the actual answer? How is it that the value function obtained this way is close to the actual values computed by solving the set of bellman equations?</p>
  
Tags: <reinforcement-learning><reference-request><proofs><bellman-equations><policy-evaluation>
Title: What is the proof that policy evaluation converges to the optimal solution?
UserDisplayName: SAGALPREET SINGH
ThreadText: # What is the proof that policy evaluation converges to the optimal solution?
  
  (Asked by: username_0 on 2020-04-16)
  
  Although I know how the algorithm of iterative policy evaluation using dynamic programming works, I am having a hard time realizing how it actually converges.
  
  It appeals to intuition that, with each iteration, we get a better and better approximation for the value function and we can thus assure its convergence, but with this said simply, it seems that this method is very inefficient contrary to the reality that it actually is quite efficient.
  
  What is the rigorous mathematical proof of the convergence of the policy evaluation algorithm to the actual answer? How is it that the value function obtained this way is close to the actual values computed by solving the set of bellman equations?
  
  **Tags:** reinforcement-learning, reference-request, proofs, bellman-equations, policy-evaluation
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2020-04-16. Score: 11 | Accepted answer
  
  First of all, [efficiency](https://en.wikipedia.org/wiki/Algorithmic_efficiency) and convergence are two different things. There's also the [rate of convergence](https://en.wikipedia.org/wiki/Rate_of_convergence), so an algorithm may converge faster than another, so, in this sense, it may be more efficient. I will focus on the proof that policy evaluation (PE) converges. If you want to know about its efficiency, maybe ask another question, but the proof below also tells you about the rate of convergence of PE.
  
  > What is the proof that policy evaluation converges to the optimal solution?
  
  To provide some context, I will briefly describe policy evaluation and what you need to know to understand the proof.
  
  ## Policy evaluation
  
  Policy evaluation (PE) is an iterative numerical algorithm to find the value function $v^\pi$ for a given (and arbitrary) policy $\pi$. This problem is often called the *prediction problem* (i.e. you want to predict the rewards you will get if you behave in a certain way).
  
  ### Two versions: synchronous and asynchronous
  
  There are (at least) two versions of policy evaluation: a synchronous one and an asynchronous one.
  
  In the **synchronous** version (SPE), you maintain two arrays for the values of the states: one array holds the current values of the states and the other array will contain the next values of the states, so two arrays are used in order to be able to update the value of each state at the same time.
  
  In the **asynchronous** version (APE), you update the value of each state in place. So, first, you update the value of e.g. $s\_1$, then $s\_2$, etc., by changing your only array of values (so you do not require a second array).
  
  SPE is similar in style to the numerical method called [Jacobi method](https://en.wikipedia.org/wiki/Jacobi_method), which is a general iterative method for finding a solution to a system of linear equations (which is exactly what PE is actually doing, and this is also explained in the cited book by Sutton and Barto). Similarly, APE is similar in style to [the Gauss–Seidel method](https://en.wikipedia.org/wiki/Gauss%E2%80%93Seidel_method), which is another method to solve a system of linear equations.
  
  Both of these general numerical methods to solve a system of linear equations are studied in detail in [Parallel and Distributed Computation Numerical Methods](https://labs.xjtudlc.com/labs/wldmt/reading%20list/books/Distributed%20and%20parallel%20algorithms/Parallel%20and%20Distributed%20Computation%20Numerical%20Methods.pdf) (1989) by Bertsekas and Tsitsiklis, which I haven't read yet, but provides convergence results for these numerical methods.
  
  The book [Reinforcement learning: an introduction](http://incompleteideas.net/book/RLbook2020.pdf) by Sutton and Barto provides a more detailed description of policy evaluation (PE).
  
  ## Proof of convergence
  
  I will provide a proof for the SPE based on [these slides](http://www.andrew.cmu.edu/course/10-703/slides/lecture4_valuePolicyDP-9-10-2018.pdf) by [Tom Mitchell](http://www.cs.cmu.edu/%7Etom/). Before proceeding, I suggest you read the following question [What is the Bellman operator in reinforcement learning?](https://ai.stackexchange.com/q/11057/2444) and its answer, and you should also get familiar with vector spaces, norms, fixed points and maybe contraction mappings.
  
  The proof that PE finds a unique fixed-point is based on the **contraction mapping theorem** and on the concept of **$\gamma$-contractions**, so let me first recall these definitions.
  
  > **Definition ($\gamma$-contraction)**: An operator on a normed vector space $\mathcal{X}$ is a $\gamma$-contraction, for $0 < \gamma < 1$, provided for all $x, y \in \mathcal{X}$
  >
  > $$\| F(x) - F(y) \| \leq \gamma \| x - y\|$$
  >
  > **Contraction mapping theorem**: For a $\gamma$-contraction $F$ in a complete normed vector space $\mathcal{X}$
  >
  > * Iterative application of $F$ converges to a **unique** fixed point in $\mathcal{X}$ independently of the starting point
  > * at a linear convergence rate determined by $\gamma$
  
  Now, consider the vector space $\mathcal{V}$ over state-value functions $v$ (i.e. $v \in \mathcal{V})$. So, each point in this space fully specifies a value function $v : \mathcal{S} \rightarrow \mathbb{R}$ (where $\mathcal{S}$ is the state space of the MDP).
  
  **Theorem (convergence of PE)**: The [Bellman operator](https://ai.stackexchange.com/q/11057/2444) is a $\gamma$-contraction operator, so an iterative application of it converges to a unique fixed-point in $\mathcal{V}$. Given that PE is an iterative application of the Bellman operator (see [What is the Bellman operator in reinforcement learning?](https://ai.stackexchange.com/q/11057/2444)), PE finds this unique fixed-point solution.
  
  So, we just need to show that the Bellman operator is a $\gamma$-contraction operator in order to show that PE finds this unique fixed-point solution.
  
  ### Proof
  
  We will measure the distance between state-value functions $u$ and $v$ by the $\infty$-norm, i.e. the largest difference between state values:
  
  $$\|u - v\|\_{\infty} = \operatorname{max}\_{s \in \mathcal{S}} |u(s) - v(s)|$$
  
  **Definition (Bellman operator)**: We define the Bellman expectation operator as
  
  $$F^\pi(v) = \mathbf{r}^\pi + \gamma \mathbf{T}^\pi v$$
  
  where $v \in \mathcal{V}$, $\mathbf{r}^\pi$ is an $|\mathcal{S}|$-dimensional vector whose $j$th entry gives $\mathbb{E} \left[ r \mid s\_j, a=\pi(s\_j) \right]$ and $\mathbf{T}^\pi$ is an $|\mathcal{S}| \times |\mathcal{S}|$ matrix whose $(j, k)$ entry gives $\mathbb{P}(s\_k \mid s\_j, a=\pi(s\_j))$.
  
  Now, let's measure the distance (with the $\infty$-norm defined above) between any two value functions $u \in \mathcal{V}$ and $v \in \mathcal{V}$ after the application of the Bellman operator $F^\pi$
  
  \begin{align}
  \| F^\pi(u) - F^\pi(v) \|\_{\infty}
  &= \| (\mathbf{r}^\pi + \gamma \mathbf{T}^\pi u) - (\mathbf{r}^\pi + \gamma \mathbf{T}^\pi v)\|\_{\infty} \\
  &= \| \gamma \mathbf{T}^\pi (u - v)\|\_{\infty} \\
  &\leq \| \gamma \mathbf{T}^\pi ( \mathbb{1} \cdot \| u - v \|\_{\infty})\|\_{\infty} \\
  &\leq \| \gamma (\mathbf{T}^\pi \mathbb{1}) \cdot \| u - v \|\_{\infty}\|\_{\infty} \\
  &\leq \gamma \| u - v \|\_{\infty}
  \end{align}
  
  where $\mathbb{1} = [1, \dots, 1]^T$. Note that $\mathbf{T}^\pi \cdot \mathbb{1} = \mathbb{1}$ because $\mathbf{T}^\pi$ is a [stochastic matrix](https://en.wikipedia.org/wiki/Stochastic_matrix).
  
  By the Bellman expectation equation (see Barto and Sutton's book and [What is the Bellman operator in reinforcement learning?](https://ai.stackexchange.com/q/11057/2444)), $v^\pi$ is **a** fixed-point of the Bellman operator $F^\pi$. Given the contraction mapping theorem, the iterative application of $F^\pi$ produces a **unique** solution, so $v^\pi$ must be this unique solution, i.e. SPE finds $v^\pi$. [Here](https://ai.stackexchange.com/a/22970/2444) is another version of the proof that the Bellman operator is a contraction.
  
  ## Notes
  
  I didn't prove the contraction mapping theorem, but you can find more info about the theorem and its proof in [the related Wikipedia article](https://en.wikipedia.org/wiki/Banach_fixed-point_theorem).
  
  
  ---
  
  ### Answer by username_1 on 2020-04-16. Score: -1
  
  There exist other RL books which do a better job of talking about this but it's pretty simple at it's core.
  
  The discounting factor puts an upper limit on the difference in reward between a finite number of iterations and an infinite number, each time you add another iteration it decreases by $\gamma$ multiplied into the upper bound of the difference.
  
  $V\_\pi = E[\sum\_{i=0}^{\infty} \gamma^iR\_i]$, $\Delta V\_k = E[\sum\_{i=k}^{\infty} \gamma^iR\_i] = \gamma^k E[\sum\_{i=0}^{\infty} \gamma^{i}R\_{i+k}] < \gamma^k \frac{1}{1-\gamma}R\_{max}$
  
  > **Comments:**
  > **username_2**: This explanation isn't clear at all (to me). The discount factor may play a role, but that doesn't give much intuition behind the algorithm, what it does and why it converges, in my opinion. I think it would be nice if you could provide a full description of the proof (maybe taken from a book, that's fine!). I think a good answer would start from a description of the algorithm and what it does. Then it proves why it converges.  
  > **username_2**: @username_0 I may provide a more formal and complete answer later, if Fourier doesn't decide to do it.  
  > **username_0**: @username_1 can you please be a bit more descriptive. I am not able to understand your answer. I think you didn't get my question right. I wanted to know, how policy evaluation works out and it happens that the algorithm converges. The intuition I formed for this is that everytime we iterate over current value function, we get closer to the actual one because after each iteration, our value function becomes more and more appropriate but how in the world does it go so close to the actual answer. What was the actual motivation behind using Bellman equation as an update rule.  
  
  ---
  
  