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 :)



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.

| cite | improve this answer | |
  • 3
    $\begingroup$ Any idea on what I should read to understand all the chinese in your answer? $\endgroup$ – thibaut noah Aug 28 '17 at 11:40
  • 1
    $\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 Aug 29 '17 at 12:54
  • $\begingroup$ thanks mate, will probably need another book on mathematics but i guess it's a start ;) $\endgroup$ – thibaut noah Aug 29 '17 at 12:56

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.

| cite | improve this answer | |
  • $\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$ – GENIVI-LEARNER Apr 13 at 18:19

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.

| cite | improve this answer | |

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.

| cite | improve this answer | |

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.