0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks. Essentially what CMU did was that they also add the current reward $r_t$ (page 5, discounting, they denoted it as $R_0$, but you can replace $0$ with the current time $t$). So you are saying that the current reward should not be specified as a part of the discounted reward? $\endgroup$ – Rodrigo Amarante Nov 27 '20 at 17:47
  • $\begingroup$ Also see page 6, slide titled "the basic decision problem" $\endgroup$ – Rodrigo Amarante Nov 27 '20 at 17:50
  • $\begingroup$ @Bajie: On page 5, they give the utility for state $s_0$, which is another name for return. However, they do that without explaining further context (such as how the equation generalises to other time steps). Your formula 1 is an attempt to generalise from it for any time step, but is not quite correct, so it is your misunderstanding. In addition, there is a real difference: Whether you notate immediate reward following $(s_t, a_t)$ as $r_t$ or $r_{t+1}$ is a matter of converntion. They appear to have used the first convention $r_t$, so there's another off-by-one difference due to that. $\endgroup$ – Neil Slater Nov 27 '20 at 18:28
  • $\begingroup$ I guess a simpler way of putting it is you cannot maximize the reward you have already gotten $\endgroup$ – Rodrigo Amarante Nov 27 '20 at 19:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.