Answers.Body: <p>In essence, your question is about convergence of <a href="https://en.wikipedia.org/wiki/Series_(mathematics)" rel="nofollow noreferrer">infinite series</a>. The mathematical discipline that studies such series is hundreds (if not thousands) years old an has nothing to do with &quot;hardware architecture&quot;.</p>
  <p>A basic example of an infinite series is the <a href="https://en.wikipedia.org/wiki/Geometric_series" rel="nofollow noreferrer">geometric series</a>:</p>
  <p><span class="math-container">$$ S = 1 + \gamma +  \gamma^2 + \gamma^3 + \dots$$</span></p>
  <p>Note that the series is infinite - no one says that <span class="math-container">$\gamma^k$</span> &quot;becomes zero at sufficiently large <span class="math-container">$k$</span>&quot;. To compute the infinite sum we represent it as a limit of partial sums:
  <span class="math-container">$$ S = \lim_{k\to\infty} ( 1 + \gamma +  \gamma^2 + \gamma^3 + \dots + \gamma^k)$$</span>
  The partial sum is called the <a href="https://en.wikipedia.org/wiki/Geometric_progression" rel="nofollow noreferrer">geometric progression</a> and has a well-known expression for it:
  <span class="math-container">$$ 1 + \gamma +  \gamma^2 + \gamma^3 + \dots + \gamma^k = \frac{1-\gamma^{k-1}}{1-\gamma}$$</span>
  As a result, the sum of our geometric series is:
  <span class="math-container">$$ S = \lim_{k\to\infty} \frac{1-\gamma^{k-1}}{1-\gamma} = \frac{1}{1-\gamma}\quad\text{if}\;|\gamma| &lt; 1$$</span></p>
  <p>In Reinforcement Learning we are dealing with similar infinite series. In partcular, when we are talking about returns:
  <span class="math-container">$$R_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \dots = \sum_{k=0}^\infty\gamma^kr_{t+k+1}$$</span>
  The convergence of this is acutally <a href="http://incompleteideas.net/book/ebook/node30.html" rel="nofollow noreferrer">discussed in the  Sutton and Barto's book</a>:</p>
  <blockquote>
  <p>If <span class="math-container">$\gamma &lt; 1$</span>, the infinite sum has a finite value as long as the reward sequence <span class="math-container">$\{r_k\}$</span> is bounded.</p>
  </blockquote>
  <p>I guess, the simplest way to prove that would be to use the <a href="https://en.wikipedia.org/wiki/Direct_comparison_test" rel="nofollow noreferrer">direct comparison test</a>. Having <span class="math-container">$\{r_k\}$</span> bounded means that there exist such number <span class="math-container">$C$</span> so that <span class="math-container">$|r_k| \leq C$</span> for all <span class="math-container">$k$</span>. So we've got the dominating series for the return :
  <span class="math-container">$$ \left|\gamma^kr_{t+k+1}\right| \leq C |\gamma^k|$$</span>
  And, since the <span class="math-container">$\gamma^k$</span> series absolutely converges for <span class="math-container">$0 \leq \gamma &lt; 1$</span>, so does <span class="math-container">$\gamma^kr_{t+k+1}$</span> series.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-12T11:51:00.820Z
Answers.LastActivityDate: 2021-05-12T11:58:26.660Z
Answers.LastEditDate: 2021-05-12T11:58:26.660Z
Answers.UserDisplayName: Kostya
Body: <p>Consider the following statement from <a href="http://incompleteideas.net/book/ebook/node41.html" rel="nofollow noreferrer">4.1 Policy Evaluation</a> of the first edition of Sutton and Barto's book.</p>
  <blockquote>
  <p>The existence and uniqueness of <span class="math-container">$V^{\pi}$</span> are guaranteed as long as
  either <span class="math-container">$\gamma  &lt; 1$</span> or eventual termination is guaranteed from all
  states under the policy <span class="math-container">$\pi$</span>.</p>
  </blockquote>
  <p>I have a doubt on the first condition <span class="math-container">$\gamma &lt; 1$</span>. If <span class="math-container">$\gamma &lt; 1$</span>, then it makes our task easy in a way that the <span class="math-container">$\gamma^k$</span> becomes zero for sufficiently higher <span class="math-container">$k$</span> and it is totally based on the hardware architecture. But, in theory, <span class="math-container">$\gamma^k$</span> can never be zero. It may approach zero.</p>
  <p>In this context, how can the condition <span class="math-container">$\gamma &lt; 1$</span> assure the existence and uniqueness of <span class="math-container">$V^{\pi}$</span> theoretically?</p>
  
Tags: <reinforcement-learning><proofs><value-functions><sutton-barto><policy-evaluation>
Title: Is the existence and uniqueness of the state-value function for $\gamma < 1$ theoretical?
UserDisplayName: hanugm
ThreadText: # Is the existence and uniqueness of the state-value function for $\gamma < 1$ theoretical?
  
  (Asked by: username_0 on 2021-05-12)
  
  Consider the following statement from [4.1 Policy Evaluation](http://incompleteideas.net/book/ebook/node41.html) of the first edition of Sutton and Barto's book.
  
  > The existence and uniqueness of $V^{\pi}$ are guaranteed as long as
  > either $\gamma < 1$ or eventual termination is guaranteed from all
  > states under the policy $\pi$.
  
  I have a doubt on the first condition $\gamma < 1$. If $\gamma < 1$, then it makes our task easy in a way that the $\gamma^k$ becomes zero for sufficiently higher $k$ and it is totally based on the hardware architecture. But, in theory, $\gamma^k$ can never be zero. It may approach zero.
  
  In this context, how can the condition $\gamma < 1$ assure the existence and uniqueness of $V^{\pi}$ theoretically?
  
  **Tags:** reinforcement-learning, proofs, value-functions, sutton-barto, policy-evaluation
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2021-05-12. Score: 3 | Accepted answer
  
  In essence, your question is about convergence of [infinite series](https://en.wikipedia.org/wiki/Series_(mathematics)). The mathematical discipline that studies such series is hundreds (if not thousands) years old an has nothing to do with "hardware architecture".
  
  A basic example of an infinite series is the [geometric series](https://en.wikipedia.org/wiki/Geometric_series):
  
  $$ S = 1 + \gamma + \gamma^2 + \gamma^3 + \dots$$
  
  Note that the series is infinite - no one says that $\gamma^k$ "becomes zero at sufficiently large $k$". To compute the infinite sum we represent it as a limit of partial sums:
  $$ S = \lim\_{k\to\infty} ( 1 + \gamma + \gamma^2 + \gamma^3 + \dots + \gamma^k)$$
  The partial sum is called the [geometric progression](https://en.wikipedia.org/wiki/Geometric_progression) and has a well-known expression for it:
  $$ 1 + \gamma + \gamma^2 + \gamma^3 + \dots + \gamma^k = \frac{1-\gamma^{k-1}}{1-\gamma}$$
  As a result, the sum of our geometric series is:
  $$ S = \lim\_{k\to\infty} \frac{1-\gamma^{k-1}}{1-\gamma} = \frac{1}{1-\gamma}\quad\text{if}\;|\gamma| < 1$$
  
  In Reinforcement Learning we are dealing with similar infinite series. In partcular, when we are talking about returns:
  $$R\_t = r\_{t+1} + \gamma r\_{t+2} + \gamma^2 r\_{t+3} + \dots = \sum\_{k=0}^\infty\gamma^kr\_{t+k+1}$$
  The convergence of this is acutally [discussed in the Sutton and Barto's book](http://incompleteideas.net/book/ebook/node30.html):
  
  > If $\gamma < 1$, the infinite sum has a finite value as long as the reward sequence $\{r\_k\}$ is bounded.
  
  I guess, the simplest way to prove that would be to use the [direct comparison test](https://en.wikipedia.org/wiki/Direct_comparison_test). Having $\{r\_k\}$ bounded means that there exist such number $C$ so that $|r\_k| \leq C$ for all $k$. So we've got the dominating series for the return :
  $$ \left|\gamma^kr\_{t+k+1}\right| \leq C |\gamma^k|$$
  And, since the $\gamma^k$ series absolutely converges for $0 \leq \gamma < 1$, so does $\gamma^kr\_{t+k+1}$ series.
  
  
  ---
  
  