Answers.Body: <blockquote>
    <p>If we train a policy to maximize the immediate reward, will it also perform well in the long term?</p>
  </blockquote>
  
  <p>In general, no. The delay of long term reward in real world problems, and often a lack of easy-to-compute heuristics, is a key motivation for developing reinforcement learning in the first place.</p>
  
  <p>It is easy to construct a counter-example to demonstrate this. Any state where the transitions into it are high and positive, but the transitions out of it are higher and negative would "trap" an agent that only considered immediate reward. More complex traps include high immediate gains but ending an episode vs lower gains that continue for longer. </p>
  
  <p>Many real-world environments have sparse rewards where it is not possible to tell the difference between two action choices by immediate reward, but the consequences of being in one part of the state space rather than another early in a trajectory are critical. Consider any two-player strategy board game for instance, where the only goal is to win at the end. Only the last move in such a game is associated with an immediate reward, but there are often important differences between early moves.</p>
  
  <blockquote>
    <p>What properties would the reward function need to fulfill?</p>
  </blockquote>
  
  <p>In all states, the expected immediate reward for taking the correct long term action would need to be higher than the expected immediate reward for any other action choice.</p>
  
  <p>Solving a problem framed in this way could be done with discount factor <span class="math-container">$\gamma=0$</span>. If the action choices were always the same and valid in each state, then the problem could also be simplified to a <a href="https://en.wikipedia.org/wiki/Multi-armed_bandit#Contextual_bandit" rel="nofollow noreferrer">contextual bandit</a>, where the fact that the choices exist within a larger trajectory is not relevant.</p>
  
  <p>In practice you <em>can</em> construct environments like this. Simple ones are possible to do manually. Doing that is similiar to adding a heuristic function for search, but with different restrictions. For many search algorithms, <a href="https://en.wikipedia.org/wiki/Admissible_heuristic" rel="nofollow noreferrer">admissible heuristic functions</a> are allowed to over-estimate future gains (or under-estimate costs), because a planning/search algorithm will resolve longer-term differences. In your case, you can maybe consider stochastic reward functions, but the <em>expected</em> reward for the correct action must always be highest. </p>
  
  <p>Needing to know the correct optimal action in the first place is clearly a circular problem - if you knew it already you would have no need to perform reinforcement learning to discover the optimal policy. An exception might be if you constructed an easy environment in order to test an algorithm, and prove that it could find the optimal policy. Although even then usually you are interested in the algorithm solving a harder variant of your problem than one you have deliberately constructed to be easy.</p>
  
  <p>In brief, there is no way to create a shortcut here and avoid the need to solve a harder RL problem.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-22T12:29:48.063Z
Answers.Text: A good action is always the one that is good in the long-term, so using the immediate short-term reward will not help to find the optimal action. An exception would be a reward function that already rates the long-term effect of an action, but this seem to be hard and is the reason why we need RL.  
  
  Thank you for the always great, detailed, and deeply insightful answers!
Answers.UserDisplayName: Ray Walker
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-22T12:32:39.080Z
Answers.Text: Can previous actions actually influence the reward of the current action? It seems they can as in your example with the game, where the immediate reward is bigger zero only for the last action. It definitely makes sense but feels like a contradiction of the Markov Property. Can you please helpt me out?
Answers.UserDisplayName: Ray Walker
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-22T12:37:13.050Z
Answers.Text: When we use RL to [train an agent to follow reference trajectories](https://xbpeng.github.io/projects/DeepMimic/index.html), do you think we can estimate the long term effect of an action by looking at the current state and the reference trajectory?
Answers.UserDisplayName: Ray Walker
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-22T13:16:30.110Z
Answers.Text: Previous actions do influence the reward of a current action - but if your MDP has the markov property, that influence is encapsulated by the state - in some games this is very direct e.g. Tic Tac Toe stores all actions as a marks on the board, and the board is the full state. In some situations you may want to include previous actions as part of the state variable, but for simple perfect information games it should not be necessary. I don't know how the reference trajectories training works, so if you want an answer to that you should ask a new question.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-22T07:59:23.970Z
Answers.LastActivityDate: 2020-04-22T09:32:23.340Z
Answers.LastEditDate: 2020-04-22T09:32:23.340Z
Answers.UserDisplayName: Neil Slater
Body: <p>The goal of a reinforcement learning agent is to maximize the expected return which is often a discounted sum of future rewards. The return indeed is a <em>very noisy</em> random variable as future rewards depend on the state-transition-probabilities and the often stochastic policy. Lots of trajectories have to be sampled to approximate its expected value.</p>
  
  <p>The immediate reward indeed does not have these dependencies. Therefore the questions: </p>
  
  <p>If we train a policy to maximize the immediate reward, will it also perform well in the long term? What properties would the reward function need to fulfill?</p>
  
Tags: <reinforcement-learning><markov-decision-process><rewards><decision-theory>
Title: Can optimizing for immediate reward result in a policy maximizing the return?
UserDisplayName: Ray Walker
ThreadText: # Can optimizing for immediate reward result in a policy maximizing the return?
  
  (Asked by: username_0 on 2020-04-21)
  
  The goal of a reinforcement learning agent is to maximize the expected return which is often a discounted sum of future rewards. The return indeed is a *very noisy* random variable as future rewards depend on the state-transition-probabilities and the often stochastic policy. Lots of trajectories have to be sampled to approximate its expected value.
  
  The immediate reward indeed does not have these dependencies. Therefore the questions:
  
  If we train a policy to maximize the immediate reward, will it also perform well in the long term? What properties would the reward function need to fulfill?
  
  **Tags:** reinforcement-learning, markov-decision-process, rewards, decision-theory
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-04-22. Score: 1 | Accepted answer
  
  > If we train a policy to maximize the immediate reward, will it also perform well in the long term?
  
  In general, no. The delay of long term reward in real world problems, and often a lack of easy-to-compute heuristics, is a key motivation for developing reinforcement learning in the first place.
  
  It is easy to construct a counter-example to demonstrate this. Any state where the transitions into it are high and positive, but the transitions out of it are higher and negative would "trap" an agent that only considered immediate reward. More complex traps include high immediate gains but ending an episode vs lower gains that continue for longer.
  
  Many real-world environments have sparse rewards where it is not possible to tell the difference between two action choices by immediate reward, but the consequences of being in one part of the state space rather than another early in a trajectory are critical. Consider any two-player strategy board game for instance, where the only goal is to win at the end. Only the last move in such a game is associated with an immediate reward, but there are often important differences between early moves.
  
  > What properties would the reward function need to fulfill?
  
  In all states, the expected immediate reward for taking the correct long term action would need to be higher than the expected immediate reward for any other action choice.
  
  Solving a problem framed in this way could be done with discount factor $\gamma=0$. If the action choices were always the same and valid in each state, then the problem could also be simplified to a [contextual bandit](https://en.wikipedia.org/wiki/Multi-armed_bandit#Contextual_bandit), where the fact that the choices exist within a larger trajectory is not relevant.
  
  In practice you *can* construct environments like this. Simple ones are possible to do manually. Doing that is similiar to adding a heuristic function for search, but with different restrictions. For many search algorithms, [admissible heuristic functions](https://en.wikipedia.org/wiki/Admissible_heuristic) are allowed to over-estimate future gains (or under-estimate costs), because a planning/search algorithm will resolve longer-term differences. In your case, you can maybe consider stochastic reward functions, but the *expected* reward for the correct action must always be highest.
  
  Needing to know the correct optimal action in the first place is clearly a circular problem - if you knew it already you would have no need to perform reinforcement learning to discover the optimal policy. An exception might be if you constructed an easy environment in order to test an algorithm, and prove that it could find the optimal policy. Although even then usually you are interested in the algorithm solving a harder variant of your problem than one you have deliberately constructed to be easy.
  
  In brief, there is no way to create a shortcut here and avoid the need to solve a harder RL problem.
  
  > **Comments:**
  > **username_0**: A good action is always the one that is good in the long-term, so using the immediate short-term reward will not help to find the optimal action. An exception would be a reward function that already rates the long-term effect of an action, but this seem to be hard and is the reason why we need RL.    Thank you for the always great, detailed, and deeply insightful answers!  
  > **username_0**: Can previous actions actually influence the reward of the current action? It seems they can as in your example with the game, where the immediate reward is bigger zero only for the last action. It definitely makes sense but feels like a contradiction of the Markov Property. Can you please helpt me out?  
  > **username_0**: When we use RL to [train an agent to follow reference trajectories](https://xbpeng.github.io/projects/DeepMimic/index.html), do you think we can estimate the long term effect of an action by looking at the current state and the reference trajectory?  
  > **username_1**: Previous actions do influence the reward of a current action - but if your MDP has the markov property, that influence is encapsulated by the state - in some games this is very direct e.g. Tic Tac Toe stores all actions as a marks on the board, and the board is the full state. In some situations you may want to include previous actions as part of the state variable, but for simple perfect information games it should not be necessary. I don't know how the reference trajectories training works, so if you want an answer to that you should ask a new question.  
  
  ---
  
  