In reinforcement learning, an agent collects rewards at each timestep. The discounted return at timestep t is the sum of all future rewards, where each reward is discounted by a factor of gamma raised to the power of how far in the future it occurs. This captures the idea that immediate rewards are worth more than distant ones.
Given a list of rewards collected over T timesteps and a discount factor gamma, compute the discounted return for every timestep.
The discounted return at timestep t is:
Gt=rt+γ⋅rt+1+γ2⋅rt+2+⋯+γT−1−t⋅rT−1This can be computed efficiently using the backward recursive relation:
Gt=rt+γ⋅Gt+1 GT−1=rT−1Input:
rewards = [1, 1, 1], gamma = 1.0
Output:
[3.0, 2.0, 1.0]
With gamma = 1 there is no discounting. G[0] = 1 + 1 + 1 = 3, G[1] = 1 + 1 = 2, G[2] = 1.
Input:
rewards = [0, 0, 0, 10], gamma = 0.9
Output:
[7.29, 8.1, 9.0, 10.0]
Only the last timestep has a reward. The return at earlier steps is that reward discounted by gamma raised to the number of steps away: G[0] = 10 * 0.9^3 = 7.29.
Initialize an array G of the same length as rewards. Set G[T-1] = rewards[T-1]. Then loop from t = T-2 down to 0, computing G[t] = rewards[t] + gamma * G[t+1].
The key insight is to process the rewards from right to left. Each return only depends on the return one step ahead, which you have already computed.
Sign in to take notes on this problem
Accepts: array
Accepts: number
In reinforcement learning, an agent collects rewards at each timestep. The discounted return at timestep t is the sum of all future rewards, where each reward is discounted by a factor of gamma raised to the power of how far in the future it occurs. This captures the idea that immediate rewards are worth more than distant ones.
Given a list of rewards collected over T timesteps and a discount factor gamma, compute the discounted return for every timestep.
The discounted return at timestep t is:
Gt=rt+γ⋅rt+1+γ2⋅rt+2+⋯+γT−1−t⋅rT−1This can be computed efficiently using the backward recursive relation:
Gt=rt+γ⋅Gt+1 GT−1=rT−1Input:
rewards = [1, 1, 1], gamma = 1.0
Output:
[3.0, 2.0, 1.0]
With gamma = 1 there is no discounting. G[0] = 1 + 1 + 1 = 3, G[1] = 1 + 1 = 2, G[2] = 1.
Input:
rewards = [0, 0, 0, 10], gamma = 0.9
Output:
[7.29, 8.1, 9.0, 10.0]
Only the last timestep has a reward. The return at earlier steps is that reward discounted by gamma raised to the number of steps away: G[0] = 10 * 0.9^3 = 7.29.
Initialize an array G of the same length as rewards. Set G[T-1] = rewards[T-1]. Then loop from t = T-2 down to 0, computing G[t] = rewards[t] + gamma * G[t+1].
The key insight is to process the rewards from right to left. Each return only depends on the return one step ahead, which you have already computed.
Sign in to take notes on this problem
Accepts: array
Accepts: number