97
$\begingroup$

I'm teaching myself about reinforcement learning, and trying to understand the concept of discounted reward. So the reward is necessary to tell the system which state-action pairs are good, and which are bad. But what I don't understand is why the discounted reward is necessary. Why should it matter whether a good state is reached soon rather than later?

I do understand that this is relevant in some specific cases. For example, if you are using reinforcement learning to trade in the stock market, it is more beneficial to make profit sooner rather than later. This is because having that money now allows you to do things with that money now, which is more desirable than doing things with that money later.

But in most cases, I don't see why the discounting is useful. For example, let's say you wanted a robot to learn how to navigate around a room to reach the other side, where there are penalties if it collides with an obstacle. If there was no discount factor, then it would learn to reach the other side perfectly, without colliding with any obstacles. It may take a long time to get there, but it will get there eventually.

But if we give a discount to the reward, then the robot will be encouraged to reach the other side of the room quickly, even if it has to collide with objects along the way. This is clearly not a desirable outcome. Sure, you want the robot to get to the other side quickly, but not if this means that it has to collide with objects along the way.

So my intuition is that any form of discount factor, will actually lead to a sub-optimal solution. And the choice of the discount factor often seems arbitrary -- many methods I have seen simply set it to 0.9. This appears to be very naive to me, and seems to give an arbitrary trade-off between the optimum solution and the fastest solution, whereas in reality this trade-off is very important.

Please can somebody help me to understand all this? Thank you :)

$\endgroup$
3
  • 2
    $\begingroup$ You might be interested in the blog post I wrote about the discount factor. I tried to show two key intuitions behind it in a visual way with the usage of image, code, and video. $\endgroup$
    – Sajil C K
    Commented Nov 15, 2020 at 3:09
  • $\begingroup$ Perhaps, see arxiv.org/abs/2107.01348. (If I had enough reputation, I would add this as a comment) $\endgroup$
    – tor
    Commented Jul 7, 2021 at 0:31
  • $\begingroup$ I found this 6 min video helpful in understanding discount factor - youtube.com/watch?v=a-SnJtmBtyA. $\endgroup$ Commented Feb 25, 2022 at 18:46

5 Answers 5

76
$\begingroup$

TL;DR.

The fact that the discount rate is bounded to be smaller than 1 is a mathematical trick to make an infinite sum finite. This helps proving the convergence of certain algorithms.

In practice, the discount factor could be used to model the fact that the decision maker is uncertain about if in the next decision instant the world (e.g., environment / game / process ) is going to end.

For example:

If the decision maker is a robot, the discount factor could be the probability that the robot is switched off in the next time instant (the world ends in the previous terminology). That is the reason why the robot is short sighted and does not optimize the sum reward but the discounted sum reward.

Discount factor smaller than 1 (In Detail)

In order to answer more precisely, why the discount rate has to be smaller than one I will first introduce the Markov Decision Processes (MDPs).

Reinforcement learning techniques can be used to solve MDPs. An MDP provides a mathematical framework for modeling decision-making situations where outcomes are partly random and partly under the control of the decision maker. An MDP is defined via a state space $\mathcal{S}$, an action space $\mathcal{A}$, a function of transition probabilities between states (conditioned to the action taken by the decision maker), and a reward function.

In its basic setting, the decision maker takes and action, and gets a reward from the environment, and the environment changes its state. Then the decision maker senses the state of the environment, takes an action, gets a reward, and so on so forth. The state transitions are probabilistic and depend solely on the actual state and the action taken by the decision maker. The reward obtained by the decision maker depends on the action taken, and on both the original and the new state of the environment.

A reward $R_{a_i}(s_j,s_k)$ is obtained when taking action $a_i$ in state $s_j$ and the environment/system changes to state $s_k$ after the decision maker takes action $a_i$. The decision maker follows a policy, $\pi$ $\pi(\cdot):\mathcal{S}\rightarrow\mathcal{A}$, that for each state $s_j \in \mathcal{S}$ takes an action $a_i \in \mathcal{A}$. So that the policy is what tells the decision maker which actions to take in each state. The policy $\pi$ may be randomized as well but it does not matter for now.

The objective is to find a policy $\pi$ such that

\begin{equation} \label{eq:1} \max_{\pi:S(n)\rightarrow a_i} \lim_{T\rightarrow \infty } E \left\{ \sum_{n=1}^T \beta^n R_{x_i}(S(n),S(n+1)) \right\} (1), \end{equation} where $\beta$ is the discount factor and $\beta<1$.

Note that the optimization problem above, has infinite time horizon ($T\rightarrow \infty $), and the objective is to maximize the sum $discounted$ reward (the reward $R$ is multiplied by $\beta^n$). This is usually called an MDP problem with a infinite horizon discounted reward criteria.

The problem is called discounted because $\beta<1$. If it was not a discounted problem $\beta=1$ the sum would not converge. All policies that have obtain on average a positive reward at each time instant would sum up to infinity. The would be a infinite horizon sum reward criteria, and is not a good optimization criteria.

Here is a toy example to show you what I mean:

Assume that there are only two possible actions $a={0,1}$ and that the reward function $R$ is equal to $1$ if $a=1$, and $0$ if $a=0$ (reward does not depend on the state).

It is clear the the policy that get more reward is to take always action $a=1$ and never action $a=0$. I'll call this policy $\pi^*$. I'll compare $\pi^*$ to another policy $\pi'$ that takes action $a=1$ with small probability $\alpha << 1$, and action $a=0$ otherwise.

In the infinite horizon discounted reward criteria equation (1) becomes $\frac{1}{1-\beta}$ (the sum of a geometric series) for policy $\pi^*$ while for policy $\pi '$ equation (1) becomes $\frac{\alpha}{1-\beta}$. Since $\frac{1}{1-\beta} > \frac{\alpha}{1-\beta}$, we say that $\pi^*$ is a better policy than $\pi '$. Actually $\pi^*$ is the optimal policy.

In the infinite horizon sum reward criteria ($\beta=1$) equation (1) does not converge for any of the polices (it sums up to infinity). So whereas policy $\pi$ achieves higher rewards than $\pi'$ both policies are equal according to this criteria. That is one reason why the infinite horizon sum reward criteria is not useful.

As I mentioned before, $\beta<1$ makes the trick of making the sum in equation (1) converge.

Other optimality criteria

There are other optimality criteria that do not impose that $\beta<1$:

The finite horizon criteria case the objective is to maximize the discounted reward until the time horizon $T$ \begin{equation} \label{eq:2} \max_{\pi:S(n)\rightarrow a_i} E \left\{ \sum_{n=1}^T \beta^n R_{x_i}(S(n),S(n+1)) \right\}, \end{equation}

for $\beta \leq 1$ and $T$ finite.

In the infinite horizon average reward criteria the objective is \begin{equation} \max_{\pi:S(n)\rightarrow a_i} \lim_{T\rightarrow \infty } E \left\{ \sum_{n=1}^T \frac{1}{T} R_{x_i}(S(n),S(n+1)) \right\}, \end{equation}

End note

Depending on the optimality criteria one would use a different algorithm to find the optimal policy. For instances the optimal policies of the finite horizon problems would depend on both the state and the actual time instant. Most Reinforcement Learning algorithms (such as SARSA or Q-learning) converge to the optimal policy only for the discounted reward infinite horizon criteria (the same happens for the Dynamic programming algorithms). For the average reward criteria there is no algorithm that has been shown to converge to the optimal policy, however one can use R-learning which have good performance albeit not good theoretical convergence.

$\endgroup$
5
  • 3
    $\begingroup$ Any idea on what I should read to understand all the chinese in your answer? $\endgroup$ Commented Aug 28, 2017 at 11:40
  • 3
    $\begingroup$ @thibautnoah This is IMHO the best reference Reinforcement Learning: An introduction from Sutton and Barto. [people.inf.elte.hu/lorincz/Files/RL_2006/SuttonBook.pdf] $\endgroup$
    – PolBM
    Commented Aug 29, 2017 at 12:54
  • $\begingroup$ thanks mate, will probably need another book on mathematics but i guess it's a start ;) $\endgroup$ Commented Aug 29, 2017 at 12:56
  • $\begingroup$ really liked this explanation. Thanks a lot $\endgroup$ Commented Sep 8, 2021 at 22:45
  • $\begingroup$ @PolBM I'll add another link incompleteideas.net/book/RLbook2020.pdf. $\endgroup$
    – oxioxi
    Commented Dec 21, 2023 at 12:04
32
$\begingroup$

TL;DR: Discount factors are associated with time horizons. Longer time horizons have have much more variance as they include more irrelevant information, while short time horizons are biased towards only short-term gains.

The discount factor essentially determines how much the reinforcement learning agents cares about rewards in the distant future relative to those in the immediate future. If $\gamma = 0$, the agent will be completely myopic and only learn about actions that produce an immediate reward. If $\gamma = 1$, the agent will evaluate each of its actions based on the sum total of all of its future rewards.

So why wouldn't you always want to make $\gamma$ as high as possible? Well, most actions don't have long-lasting repercussions. For example, suppose that on the first day of every month you decide to treat yourself to a smoothie, and you have to decide whether you'll get a blueberry smoothie or a strawberry smoothie. As a good reinforcement learner, you judge the quality of your decision by how big your subsequent rewards are. If your time horizon is very short, you'll only factor in the immediate rewards, like how tasty your smoothie is. With a longer time horizon, like a few hours, you might also factor in things like whether or not you got an upset stomach. But if your time horizon lasts for the entire month, then every single thing that makes you feel good or bad for the entire month will factor into your judgement on whether or not you made the right smoothie decision. You'll be factoring in lots of irrelevant information, and therefore your judgement will have a huge variance and it'll be hard to learn.

Picking a particular value of $\gamma$ is equivalent to picking a time horizon. It helps to rewrite an agent's discounted reward $G$ as $$ G_t = R_{t} + \gamma R_{t+1} + \gamma^2 R_{t+2} + \cdots \\ = \sum_{k=0}^{\infty} \gamma^k R_{t+k} = \sum_{\Delta t=0}^{\infty} e^{-\Delta t / \tau} R_{t+\Delta t} $$ where I identify $\gamma = e^{-1/\tau}$ and $k \rightarrow \Delta t$. The value $\tau$ explicitly shows the time horizon associated with a discount factor; $\gamma = 1$ corresponds to $\tau = \infty$, and any rewards that are much more than $\tau$ time steps in the future are exponentially suppressed. You should generally pick a discount factor such that the time horizon contains all of the relevant rewards for a particular action, but not any more.

$\endgroup$
3
  • $\begingroup$ The formula at the end gives clear instructions on how to practically choose a discount factor! Your answer was the most useful for me, thank you very much! $\endgroup$
    – Ray Walker
    Commented Nov 1, 2020 at 9:35
  • $\begingroup$ Could you please provide a source for the formula at the end of your post? Would be useful to quote it in academic papers. $\endgroup$
    – Ray Walker
    Commented Nov 7, 2020 at 18:03
  • $\begingroup$ I actually don't know of another source that lays out this argument directly; it's just the way that I've picked the discount factor for my own experiments. If you do find a source for it, make sure to let me know and I'll edit the answer. $\endgroup$ Commented Nov 8, 2020 at 19:38
13
$\begingroup$

You're right that the discount factor (so-called $\gamma$ — note that this is different than $\lambda$ from TD-$\lambda$) acts like an "urgency of life" and is therefore part of the problem — just like it is in human lives: Some people live as if they'll live forever; some people live as if they're going to die tomorrow.

$\endgroup$
1
  • $\begingroup$ Is this really the gist of discount factors? So it makes greedy algorithm less greedy? So it makes people who live if they will die tomorrow , live like if they have to live for maybe a month or so? $\endgroup$ Commented Apr 13, 2020 at 18:19
2
$\begingroup$

Inspired by "PolBM"'s answer, an intuitive example helps understand the usefulness of the discount factor. Imagining that there are two stocks we can purchase.

Stock A: Rising ten dollars on Monday of every week and falling ten dollars on Tuesday of every week.

Stock B: Falling ten dollars on Monday of every week and rising ten dollars on Tuesday of every week.

Both stocks are unchanged on other days of a week. Now, we want to design a policy to purchase a stock on Sunday. In the long term (without discount factor), both stocks have zero expected rewards. Therefore, it seems like we can purchase either stock mentioned above.

However, Stock A is better than Stock B, because we will never lose money by purchasing the stock A.

For example, if we buy the stock A on Sunday and sell it on Monday, then we will earn ten dollars. And if we buy the stock A on Sunday and sell it on other days in a week, then we will not get any revenue. Similarly, if we buy the stock B on Sunday and sell it on Monday, then we will lose ten dollars. And if we buy the stock on Sunday and sell it on other days in a week, then we will not get any revenue.

This scenario is quite common in the reinforcement learning domain, such as the classical Multi-armed bandit problem. Even though the expectations of two slot machines are the same, the real rewards may be significantly different. Therefore, in these scenarios, the discount factor is necessary.

$\endgroup$
2
$\begingroup$

According to the paper: Markov games as a framework for multi-agent reinforcement learning by Michael Littman, 1994, the notion of discount factor is defined in terms of the probability that the game will be allowed to continue. Even thought this paper is talking about Markov games, I believe the abstract can be used to get a more general, intuition about the importance of discount factor. Here it is:

"As in MDP’s, the discount factor can be thought of as the probability that the game will be allowed to continue after the current move. It is possible to define a no- tion of undiscounted rewards [Schwartz, 1993], but not all Markov games have optimal strategies in the undiscounted case [Owen, 1982]. This is because, in many games, it is best to postpone risky actions indefinitely. For current pur- poses, the discount factor has the desirable effect of goading the players into trying to win sooner rather than later."

$\endgroup$

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