Reinforcement learning, question from Sutton's new book

Question

In Sutton's new RL book, in chapter 3, there is an exercise

Exercise 3.6 Suppose you treated pole-balancing as an episodic task but also used discounting, with all rewards zero except for −1 upon failure. What then would the return be at each time? How does this return differ from that in the discounted, continuing formulation of this task?

My answer is if it is episodic with discounting, the return at each time step is $$-\gamma^{K_1} - \gamma^{K_2} - \cdots - \gamma^{K_n},$$

where $K_i$ is the number of total time steps until it fails at episode $i$.

And for continuous tasks with discounting, the return at each time step is $-\gamma^K$, where $K$ is the number of time steps until it fails.

I am not sure whether my answer is right or not. Could you please help me?

Answer 1

I don't think so, rewriting book's eq. (3.7) with discounts, we would get

$$ G_t = R_{t+1} + \gamma \cdot R_{t+2} + \gamma^2 \cdot R_{t+3} + ... + \gamma^{T-1} \cdot R_{T} $$

where $T$ is the terminal state and $\gamma$ is the discount rate.

Given that all rewards zero ($R_{t+1}, R_{t+2}, R_{t+3}$) except for −1 upon failure ($R_T$), you can extract the expected return at each time, which is different than what you propose.

Answer 2

First of all, for the continuing case, the return would like something like: $$-\sum^{\infty}_{i=1}\gamma^{K_i-1}$$ where the $K_i$'s are the number of steps until the first $(i=1)$ failure, second failure $(i=2)$ and so on. To help with understanding why it's like that, imagine the following sequence of rewards:

$$0,0,0,-1,0,-1,0,...$$

which is equivalent to $$R_{t+1},R_{t+2},R_{t+3},R_{t+4},R_{t+5}, R_{t+6},R_{t+7}...$$

Since we have discounts, it turns into $$R_{t+1},\gamma R_{t+2},\gamma^2 R_{t+3},\gamma^3 R_{t+4},\gamma^4 R_{t+5},\gamma^5 R_{t+6},\gamma^6 R_{t+7}... \\ = 0,\gamma 0,\gamma^2 0,\gamma^3 (-1),\gamma^4 0,\gamma^5 (-1),\gamma^6 0,...$$

So you can see that we have $K=4$ timesteps until the first $-1$ and then the reward we get from it is $\gamma^{K-1} R_{t+4}=\gamma^{4-1}R_{t+4}=\gamma^3R_{t+4}=-\gamma^3$ and until the next $-1$ we have $K=6$ timesteps.

Now, for the episodic task the return looks like this: $$G_t = R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+...+\gamma^{T-t-1}R_T$$ so the return is $-\gamma^{T-t-1}$. Also note that $G_T=0$ since the next state is terminal $(R_{T+1}=0)$.

Answer 3

I would say this:

Knowing that the reward at time $T$ is -1, we can model the expected return until $T-1$ as usual and set the reward at the last time step of the episode as -1. Like this:

$G_{t} = \sum_{k = 1}^{T-1} - \gamma^{k-1} - 1$

Answer 4

In the discounted continuing case, the return is not merely $-\gamma^{k-1}$, but a sum of similar terms accounting for all future failures; it is even mentioned in the text

The return at each time would then be related to $-\gamma^{K-1}$ , where $K$ is the number of time steps before failure (as well as to the times of later failures).

In the discounted episodic formulation, the return at each time grows larger as you approach the point of failure (also the end of the episode). In this case, return at each time step would only have one term $-\gamma^{k-1}$. $G_T$ would also be zero.