2
$\begingroup$

Consider the following statement from 4.1 Policy Evaluation 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 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?

$\endgroup$
3
$\begingroup$

In essence, your question is about convergence of infinite series. 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:

$$ 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 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:

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. 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.