In reinforcement learning, what is the correct mathematical definition of the discounted reward?

Question

I'm seeing several different definitions of discounted reward/return as it is used in MDP based RL. I am wondering which one is correct.

Let $r_t$ be the scalar-valued immediate reward at time $t$, $R_t$ be the discounted return starting at time $t$, then $R_t$ is,

1. $R_t = \sum\limits_{i = 0}^T \gamma^i r_{t+1}$
2. $R_t = \sum\limits_{i = 0}^T \gamma^{t+i-1} r_{t+i}$
3. $R_t = \sum\limits_{i = 0}^T \gamma^{i} r_{t+i+1}$

where $\gamma \in (0, 1]$ (or sometimes $(0,1)$).

Everybody basically has a different definition to the objective of RL, which is to maximize this object.

For example:

Carnegie Mellon University uses 1: https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15381-s06/www/mdp.pdf

McGill uses 2:https://www.cs.mcgill.ca/~dprecup/courses/AI/Lectures/ai-lecture16.pdf

Stanford uses 3: http://web.stanford.edu/class/cme241/lecture_slides/rich_sutton_slides/5-6-MDPs.pdf

Who is correct?

Answer 1

Your formula 3 is correct:

$$R_t = \sum_{i=0}^{T} \gamma^i r_{t+i+1}$$

I cannot find where Carnegie Mellon suggests formula 1, and the word "return" is not mentioned in the link you provided. That could be a misunderstanding on your part, from looking at other related formulae.

I think McGill's formula is a typo, if you remove the $t$ from $\gamma^{t+k-1}$ (to make $\gamma^{k-1}$) it is correct because $k$ is 1-indexed as opposed to 0-indexed $i$ in the above formula. So it is essentially the same if the $t$ is removed from the exponent on $\gamma$. You also made a typo (replacing 1 in McGill's version with 0 in yours) when you transcribed it here when writing option 2.

There is a convention that varies between sources, whether the immediate reward following state $s_t$ and action $a_t$ on time step $t$ is considered to be part of current timestep and noted $r_t$ or the next time step and noted $r_{t+1}$. I have used $r_{t+1}$ in the above equation because I consider it natural that the reward and next state are returned at the beginning of the next time step - a lot of people follow this convention too, but it is not universal.

Therefore, under the convention that the immediate reward is $r_t$ the following version is also correct:

$$R_t = \sum_{i=0}^{T} \gamma^i r_{t+i}$$

From your comments it looks like CMU follow this convention, and would use this variant of the formula for discounted return.

---

As an aside, there are other ways to measure performance - and therefore set objectives - in reinforcement learning. For instance, you can consider average reward to cope with non-episodic problems. However, discounted return has a definition matching your formula 3.