1
$\begingroup$

I know that $G_t = R_{t+1} + G_{t+1}$.

Suppose $\gamma = 0.9$ and the reward sequence is $R_1 = 2$ followed by an infinite sequence of $7$s. What is the value of $G_0$?

As it's infinite, how can we deduce the value of $G_0$? I don't see the solution. It's just $G_0 = 5 + 0.9*G_1$. And we don't know $G_1$ value, and we don't know $R_2, R_3, R_4, ...$

$\endgroup$
0
2
$\begingroup$

You know all the rewards. They're 5, 7, 7, 7, and 7s forever. The problem now boils down to essentially a geometric series computation.

$$ G_0 = R_0 + \gamma G_1 $$

$$ G_0 = 5 + \gamma\sum_{k=0}^\infty 7\gamma^k $$

$$ G_0 = 5 + 7\gamma\sum_{k=0}^\infty\gamma^k $$

$$ G_0 = 5 + \frac{7\gamma}{1-\gamma} = \frac{5 + 2\gamma}{1-\gamma} $$

$\endgroup$
1
  • $\begingroup$ Thanks a lot for explanation $\endgroup$ – Thom Jul 8 '20 at 18:52
1
$\begingroup$

There are a few ways to resolve values of infinite sums. In this case, we can use a simple technique of self-reference to create a solvable equation.

I will show how to do it for the generic case here of an MDP with same reward $r$ on each timestep:

$$G_t = \sum_{k=0}^{\infty} \gamma^k r$$

We can "pop off" the first item:

$$G_t = r + \sum_{k=1}^{\infty} \gamma^k r$$

Then we can note that the second term is just $\gamma$ times the orginal term:

$$G_t = r + \gamma G_t$$

(There are situations where this won't work, such as when $\gamma \ge 1$ - essentially we are taking advantage that the high order terms are arbitrarily close to zero, so can be ignored)

Re-arrange it again:

$$G_t = \frac{r}{1 - \gamma}$$

This means that you can get the value for a return for the discounted sum of repeating rewards. Which allows you to calculate your $G_1$. I will leave that last part as an execrise for you, as you already figured the first part out.

$\endgroup$
1
  • $\begingroup$ Thanks a lot for explanation $\endgroup$ – Thom Jul 8 '20 at 18:53

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.