Should the concept of discounted rewards result in multiple arrays per episode in RL?

Question

Note that I'm coming from mostly only working with the REINFORCE algorithm, but I've typically seen discounted rewards calculated in a way that looks like below:

Say you have a reward array of length n and a discount hyperparam gamma. You might calculate the discount factors like: gamma^i for i in range(n) ex: [0.99^0, 0.99^1, ... 0.99^n]

Then get the discounted rewards by multiplying each discount factor by the corresponding reward and doing a cumulative sum.

However, this results in an array of the same length as rewards, but this seems incorrect to me?

I understand discounted rewards as a way to deal with the uncertainty of past actions on future awards. It would seem to me that uncertainty should result in multiple different contexts and then multiple different arrays with their own discounts.

For instance, say I have 4 states with 4 rewards that looks like [2, 3, 1, 3]. It would seem to me I should then have 4 reward arrays:

[2, 3, 1, 3]

[3, 1, 3]

[1, 3]

[3]

and I should have 4 discount factor arrays also:

[0.99^0, 0.99^1, 0.99^2, 0.99^3]

[0.99^0, 0.99^1, 0.99^2]

[0.99^0, 0.99^1]

[0.99^0]

because of the different contexts. For instance, in the first state reward value 2 is certain and reward value 3 slightly less so. But once we're in the second state, reward value 3 is certain and reward value 1 slightly less so.

If we don't do something like this, isn't our agent being updated on a system that always keys on the first state?

Answer 1

The discount factor is not used to take into account uncertainty, but to encourage the agent to have a longer term view when it takes an action. If the discount factor is close to 0, the agent is encouraged to maximise the immediate reward it gets, whereas if the discount is close to 1, the agent is encouraged to take the action which will lead to high rewards in the future too.

To see why, let's denote $G_k$ the cumulative discounted reward starting from timestep $k$ in an episode of length $T$. Then, by definition, $G_k = \sum_{k=0}^T \gamma^k r_k$.

Then, if all rewards are 1, $G_k \approx \frac{1}{1-\gamma}$. If $\gamma$ is close to 1, then $G_k$ will be large, because it will take into account all future rewards almost at their full value, whereas if $\gamma$ is close to 0, $G_k$ will be close to 1, i.e. it will take into account just the first reward

Now, in REINFORCE (according to the implementation OP mentions in their comment to this answer) at the end of each episode of length $T$, the parameter update looks like $$\theta \leftarrow \theta + \alpha \nabla_{\theta}\sum_{k=0}^T\ln (\pi(a_k | s_k, \theta))G_k$$.

In your example, at timestep 0, $G_0 = 0.99 ^0 * 2 + 0.99 * 3 + 0.99^ 2 * 1 + 0.99^3 * 3$.

Then at timestep 1, $G_1 = 0.99 ^0 * 3 + 0.99 * 1 + 0.99^ 2 * 3$.

And so on.

L71-72 of the algorithm is constructing the list $$[\ln (\pi(a_0 | s_0, \theta))G_0, \ln (\pi(a_1 | s_1, \theta))G_1, ..., \ln (\pi(a_T | s_T, \theta))G_T]$$, which then gets summed to construct the fimal loss.