Answers.Body: <p>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.</p>
  <p>To see why, let's denote <span class="math-container">$G_k$</span> the cumulative discounted reward starting from timestep <span class="math-container">$k$</span> in an episode of length <span class="math-container">$T$</span>. Then, by definition, <span class="math-container">$G_k = \sum_{k=0}^T \gamma^k r_k$</span>.</p>
  <p>Then, if all rewards are 1, <span class="math-container">$G_k \approx \frac{1}{1-\gamma}$</span>. If <span class="math-container">$\gamma$</span> is close to 1, then <span class="math-container">$G_k$</span> will be large, because it will take into account all future rewards almost at their full value, whereas if <span class="math-container">$\gamma$</span> is close to 0, <span class="math-container">$G_k$</span> will be close to 1, i.e. it will take into account just the first reward</p>
  <p>Now, in REINFORCE (according to the <a href="https://github.com/pytorch/examples/blob/main/reinforcement_learning/reinforce.py" rel="nofollow noreferrer">implementation OP mentions in their comment to this answer</a>) at the end of each episode of length <span class="math-container">$T$</span>, the parameter update looks like <span class="math-container">$$\theta \leftarrow \theta + \alpha \nabla_{\theta}\sum_{k=0}^T\ln (\pi(a_k | s_k, \theta))G_k$$</span>.</p>
  <p>In your example, at timestep 0, <span class="math-container">$G_0 = 0.99 ^0 * 2 + 0.99 * 3 + 0.99^ 2 * 1 + 0.99^3 * 3$</span>.</p>
  <p>Then at timestep 1, <span class="math-container">$G_1 = 0.99 ^0 * 3 + 0.99 * 1 + 0.99^ 2 * 3$</span>.</p>
  <p>And so on.</p>
  <p><a href="https://github.com/pytorch/examples/blob/main/reinforcement_learning/reinforce.py#L71-L72" rel="nofollow noreferrer">L71-72 of the algorithm</a> is constructing the list <span class="math-container">$$[\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]$$</span>, which then gets summed to construct the fimal loss.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-09-05T21:44:59.257Z
Answers.Text: 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: https://github.com/pytorch/examples/blob/main/reinforcement_learning/reinforce.py . 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.
Answers.UserDisplayName: Josh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-09-06T22:15:13.277Z
Answers.Text: 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.
Answers.UserDisplayName: Raphael Lopez Kaufman
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-09-07T02:15:51.510Z
Answers.Text: 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.
Answers.UserDisplayName: Josh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-09-07T19:11:27.987Z
Answers.Text: The [code](https://github.com/pytorch/examples/blob/main/reinforcement_learning/reinforce.py#L66-L68) 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]$.
Answers.UserDisplayName: Raphael Lopez Kaufman
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-09-07T20:59:31.473Z
Answers.Text: 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).
Answers.UserDisplayName: Josh
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-09-05T18:38:20.287Z
Answers.LastActivityDate: 2022-09-06T22:13:28.630Z
Answers.LastEditDate: 2022-09-06T22:13:28.630Z
Answers.UserDisplayName: Raphael Lopez Kaufman
Body: <p>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:</p>
  <p>Say you have a reward array of length <code>n</code> and a discount hyperparam <code>gamma</code>. You might calculate the discount factors like:
  <code>gamma^i for i in range(n)</code>
  ex: [0.99^0, 0.99^1, ... 0.99^n]</p>
  <p>Then get the discounted rewards by multiplying each discount factor by the corresponding reward and doing a cumulative sum.</p>
  <p>However, this results in an array of the same length as rewards, but this seems incorrect to me?</p>
  <p>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.</p>
  <p>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:</p>
  <p>[2, 3, 1, 3]</p>
  <p>[3, 1, 3]</p>
  <p>[1, 3]</p>
  <p>[3]</p>
  <p>and I should have 4 discount factor arrays also:</p>
  <p>[0.99^0, 0.99^1, 0.99^2, 0.99^3]</p>
  <p>[0.99^0, 0.99^1, 0.99^2]</p>
  <p>[0.99^0, 0.99^1]</p>
  <p>[0.99^0]</p>
  <p>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.</p>
  <p>If we don't do something like this, isn't our agent being updated on a system that always keys on the first state?</p>
  
Tags: <reinforcement-learning><rewards><reinforce><discount-factor>
Title: Should the concept of discounted rewards result in multiple arrays per episode in RL?
UserDisplayName: Josh
ThreadText: # Should the concept of discounted rewards result in multiple arrays per episode in RL?
  
  (Asked by: username_0 on 2022-09-05)
  
  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?
  
  **Tags:** reinforcement-learning, rewards, reinforce, discount-factor
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-09-05. Score: 2 | Accepted answer
  
  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](https://github.com/pytorch/examples/blob/main/reinforcement_learning/reinforce.py)) 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](https://github.com/pytorch/examples/blob/main/reinforcement_learning/reinforce.py#L71-L72) 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.
  
  > **Comments:**
  > **username_0**: 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: https://github.com/pytorch/examples/blob/main/reinforcement_learning/reinforce.py . 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.  
  > **username_1**: 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.  
  > **username_0**: 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.  
  > **username_1**: The [code](https://github.com/pytorch/examples/blob/main/reinforcement_learning/reinforce.py#L66-L68) 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]$.  
  > **username_0**: 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).  
  
  ---
  
  