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

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]



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?

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.

• I do not believe the REINFORCE algorithm updates parameters at each timestep though but rather at the end of the episode. I take most of my opinion from PyTorch's implementation here: github.com/pytorch/examples/blob/main/reinforcement_learning/… . I view the "long term" take as synonymous with "uncertainty" in that at each timestep, we want long term rewards to tie back to our preceding action, but the discount factor allows some uncertainty for the extent. My concern or confusion then comes in with REINFORCE doing one update with an array of length n timesteps.
– Josh
Sep 5, 2022 at 21:44
• I see, instead of updating at every time step, they calculate the loss as the sum over timesteps in the episode. I've updated my answer. Sep 6, 2022 at 22:15
• I appreciate the edit, but I feel it doesn't exclude my worry. My contention is that what is a "far future" reward at timestep 1 is not necessarily a far future reward at timestep n - 1. As I read the implementation, it does not rerun the discount factor from the perspective of teach timestep as I suggest and is recapitulated by the G_0 and G_1 notes above. By working with the rewards across the whole episode as a single array as the implementation I believe does, it must seem to me that the reward (and thereby reward * -logprobs) takes the reference frame of the first action only.
– Josh
Sep 7, 2022 at 2:15
• The code is a bit difficult to interpret but it's doing the thing describe in the answer. Make an empty array $returns$ and initialise R to 0. Loop in reverse order over the rewards, set $R = r_t + \gamma R$ and prepend it to $returns$. So the first iteration of the loop does $R = r_T = G_T$ and $returns = [G_T]$, the second iteration does $R = r_{T-1} + \gamma R = r_{T-1} + \gamma r_T = G_{T-1}$ and $returns = [G_{T-1}, G_T]$, and so on, so at the end you have $returns = [G_0, G_1, ..., G_T]$. Sep 7, 2022 at 19:11
• I see it now. The implementation is indeed doing what I felt like should be the case, but I missed it in expecting a double loop (that clearly isn't necessary).
– Josh
Sep 7, 2022 at 20:59