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

$\endgroup$

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .