Computing Finite-Horizon and Discounted Returns

From Rewards to Return

First, let's formalize the idea of an immediate reward. In an MDP, when an agent in state $s_t$ takes an action $a_t$ and transitions to state $s_{t+1}$, it receives a scalar reward, $R_{t+1}$. This reward is determined by a reward function. The most general form depends on the full transition, $R(s_t,a_t,s_{t+1})$, but it's often simplified to depend only on the state-action pair, $R(s_t,a_t)$, or even just the new state, $R(s_{t+1})$.

An agent's goal is not to maximize a single, immediate reward, but rather the cumulative rewards it collects over a trajectory. This cumulative reward is what we call the return. Let's denote the return from time step $t$ onwards as $G_t$.

The OpenAI Spinning Up documentation provides a concise introduction to both rewards and the two primary forms of return.

As you saw, there are two main ways to aggregate rewards into a return. Let's examine each one.

1. Finite-Horizon Undiscounted Return

This is the simplest way to calculate a return. For a process that is known to terminate after a fixed number of steps, called the horizon $H$, the total return is simply the sum of all rewards received.

The return from time step $t$ in a horizon of length $H$ is:
$G_t=R_{t+1}+R_{t+2}+\cdots +R_{t+H}={\sum }_{k=1}^H{R}_{t+k}$

If we are considering a full trajectory (or episode) of length $T$, the return from the beginning ($t=0$) is:
$G_0={\sum }_{k=0}^{T-1}{R}_{k+1}$

Example:
Suppose an agent completes a task in 4 steps and receives the following reward sequence: $R_1=0,R_2=0,R_3=0,R_4=+10$. The finite-horizon undiscounted return for this trajectory is simply $G_0=0+0+0+10=10$. This approach is common in episodic tasks where only the final outcome matters, like winning a game of chess.

2. Infinite-Horizon Discounted Return

What happens if the process doesn't have a clear endpoint? If an agent could potentially operate forever, summing the rewards could lead to an infinite, and therefore useless, value. This is a common problem in "continuing" tasks, like balancing a robot or managing an investment portfolio.

The solution is to introduce a discount factor, $\gamma$ (gamma), where $0\le \gamma <1$. The idea is that rewards received sooner are more valuable than the same rewards received further in the future.

The discounted return from time step $t$ is defined as:
$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots ={\sum }_{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}$

With this formula, a reward received $k$ steps in the future is multiplied by ${\gamma }^k$. Since $\gamma <1$, this weight gets exponentially smaller as $k$ increases, ensuring that the infinite sum converges to a finite value, provided the rewards are bounded.

Let's watch a short video that explains these two concepts with clear examples and visuals.

Why Discount?

The use of a discount factor might seem like a mathematical convenience, and it certainly is, but there are deeper reasons for it. The following reading and video lecture explain the issues with simple additive utility in infinite horizons and justify the use of discounting.

As the reading highlights, your background with geometric series is directly applicable here. If the agent were to receive a constant maximum reward $R_{\text{max}}$ at every step, the discounted return would be ${\sum }_{t=0}^{\infty }{\gamma }^t{R}_{\text{max}}$. This is a geometric series that converges to $R_{\text{max}}/(1-\gamma )$, guaranteeing that the total return is finite.

David Silver's lecture provides a broader perspective on the motivations for discounting, which extend beyond mathematical convenience.

As Silver discusses, the key reasons for discounting include:

• Mathematical convenience: It prevents infinite returns in cyclic MDPs and ensures convergence.
• Model uncertainty: The future is uncertain. A discount factor implicitly reduces the importance of rewards that depend on distant, and therefore less reliable, predictions of our model.
• Economic and biological analogy: Interest rates in finance and the preference for immediate gratification in humans and animals both reflect a form of discounting.

Computing a Discounted Return: An Example

Let's solidify this with the same reward sequence as before: $R_1=0,R_2=0,R_3=0,R_4=+10$. We'll assume the episode ends after step 4. Let's use a discount factor of $\gamma =0.9$.

The discounted return from the start ($t=0$) is:

Notice that the return is no longer 10. The reward of +10 was "discounted" because it was received four steps into the future (at $t=4$, which corresponds to the ${\gamma }^{4-1}={\gamma }^3$ term).

If we calculate the return from a later time step, say $t=2$, we are looking for the discounted sum of rewards from that point on:

From the perspective of $t=2$, the reward of +10 is only two steps away, so it is discounted less heavily.

Conclusion

In this lesson, we have defined how to measure the "goodness" of a trajectory by accumulating the rewards it generates. This accumulated reward is called the return.

Here are the key takeaways:

• The return ($G_t$) is the sum of rewards from time step $t$ onwards, forming the basis for an agent's objective.
• Finite-horizon undiscounted return is the simple sum of rewards over a fixed number of steps. It is suitable for clearly defined episodic tasks.
• Infinite-horizon discounted return is a weighted sum of all future rewards, where the discount factor $\gamma$ makes distant rewards less valuable. This is essential for continuing tasks and provides mathematical stability.
• The choice of $\gamma$ reflects a preference for immediate versus future rewards. A $\gamma$ close to 0 creates a "myopic" agent focused on immediate rewards, while a $\gamma$ close to 1 creates a "farsighted" agent that values future rewards almost as much as present ones.

We have introduced the discount factor $\gamma$ as a critical parameter. In the next lesson, we will delve deeper into its role and formally explore how changing $\gamma$ alters the agent's effective planning horizon.