📘

Reward-to-Go for Every Timestep

MediumReinforcement Learning 📚 RL 1: Foundations

Problem Statement

Return the discounted reward-to-go G_t for every timestep of an episode, not just the first:

$G_t = \sum_{k=0}^{T-t-1} \gamma^{k} R_{t+k+1}$

Implement rewards_to_go(rewards, gamma) returning a list the same length as rewards, where element t is G_t.

Example:

Input:

rewards_to_go([1.0, 2.0, 3.0], 1.0)

Output:

[6.0, 5.0, 3.0]

Reasoning:

We compute the reward-to-go $G_t$ in reverse order (from the last timestep to the first) because each $G_t$ depends on the subsequent $G_{t+1}$ via the recurrence $G_t = R_{t+1} + \gamma G_{t+1}$ .
Starting at the final timestep $t=2$ with reward $R_3 = 3.0$ and no future rewards, the accumulated value is simply $G_2 = 3.0 + 1.0 \cdot 0 = 3.0$ .
Moving to $t=1$ with reward $R_2 = 2.0$ , we add the current reward to the discounted future value: $G_1 = 2.0 + 1.0 \cdot 3.0 = 5.0$ .
At the initial timestep $t=0$ with reward $R_1 = 1.0$ , we again combine the current reward with the discounted next value: $G_0 = 1.0 + 1.0 \cdot 5.0 = 6.0$ .
The final output is [6.0, 5.0, 3.0]

Constraints:

0 <= len(rewards) <= 10000, 0.0 <= gamma <= 1.0
Compute in a single backward pass (O(n)).
Empty input returns an empty list.

More from RL 1: Foundations

GAE Over a Full TrajectoryHard PPO Clipped Objective (Single Sample)Medium TD Residuals for GAEMedium Return Standardization BaselineMedium REINFORCE Loss TermMedium

1. Background Knowledge

In reinforcement learning, the return is the cumulative discounted reward an agent receives from a given state onward. The reward-to-go (also called the future return or cumulative discounted reward) at timestep $t$ is defined as:

G_t = \sum_{k=0}^{T-t-1} \gamma^{k} R_{t+k+1}

Here, $R_{t+k+1}$ is the reward received after taking an action at step $t+k$ , and $\gamma \in [0, 1]$ is the discount factor that reduces the influence of distant rewards. When $\gamma = 1$ , the agent values all future rewards equally; when $\gamma$ is small, the agent is myopic and prioritizes immediate rewards.

The reward-to-go is central to policy gradient methods (e.g., REINFORCE) and actor-critic algorithms, where it serves as a baseline-free estimate of the value of being in a particular state-action pair. Unlike the state-value function $V(s)$ , which is an expectation over all possible futures, $G_t$ is a single-sample estimate computed from one observed trajectory.

A key insight is that $G_t$ and $G_{t+1}$ are related by a simple recurrence:

G_t = R_{t+1} + \gamma \, G_{t+1}

with the boundary condition $G_T = 0$ (no rewards remain after the episode ends). This backward recurrence is the foundation of an efficient $O(T)$ algorithm.

2. Algorithm Approach

Use a backward dynamic programming sweep. Instead of computing each $G_t$ independently (which would be $O(T^2)$ ), exploit the recurrence relation above:

Start at the last timestep where $G_T = 0$ .
Iterate backward from $t = T-1$ down to $t = 0$ .
At each step, compute $G_t = R_{t+1} + \gamma \cdot G_{t+1}$ .

This is analogous to computing a suffix sum with a multiplicative decay factor. The pattern is: maintain a running accumulator that you update as you walk backward through the reward sequence.

3. Step-by-Step Strategy

👑

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

🔒

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.