Answers.Body: <blockquote>
  <p>The accuracy level is already very high, but how to motivate the agent to find the target as quickly as possible?</p>
  </blockquote>
  <p>You already are, in two different ways:</p>
  <ul>
  <li><p>A penalty (negative reward) for each time step taken.</p>
  </li>
  <li><p>A positive reward for completing a task, plus discounting.</p>
  </li>
  </ul>
  <p>Both of these choices are sufficient that action values will be maximised by taking the most direct route to complete a task, and minimise expected time steps from any starting point.</p>
  <p>In theory you could completely lose one of the two approaches, and the reward system would still work.</p>
  <p>For DQN I would lose the positive reward at the end and use a relatively high discount factor, e.g. <span class="math-container">$\gamma = 0.99$</span> - which is only required for numerical stability, and not really part of the problem definition. If your goal is to minimise number of time steps, then a simple count of number of remaining time steps is already a good cost function, and negating it to make a reinforcement learning return is close to ideal. It often works well with Q learning too because it will explore away from repetition, even if at the start of training it cannot reach the target state.</p>
  <blockquote>
  <p>What's the effect of <span class="math-container">$\gamma$</span> on the agent's task solving speed?</p>
  </blockquote>
  <p>This can be complex, but is a scenario with the only positive reward at the end and a discount factor, then expected reward will depend on expected future time steps in a geometric series. If in state <span class="math-container">$s_1$</span>, action choice <span class="math-container">$a_1$</span> would lead to the end goal in 3 time steps and action choice <span class="math-container">$a_2$</span> would lead to the end goal in 4 time steps, with the only reward <span class="math-container">$r_T$</span> for reaching the goal state, then <span class="math-container">$q(s_1, a_1) = \gamma^3 r_T \gt q(s_1, a_2) = \gamma^4 r_T$</span>, making <span class="math-container">$a_1$</span> the obvious choice.</p>
  <p>A stochastic environment may muddy this a little, but in general the agent is going to prefer the lower number of timesteps to get to the goal. If distribution of number of timesteps can be very different, then different <span class="math-container">$\gamma$</span> values may cause slightly different gambling options made by the agent to complete faster. This is the reason why I suggest dropping the positive reward at the end, if your goal is to minimise expected number of timesteps to complete. That is because technically a change to <span class="math-container">$\gamma$</span> is a change to the problem definition - muddied slightly by usually needing <span class="math-container">$\gamma \lt 1$</span> when training a DQN to improve stability.</p>
  <blockquote>
  <p>Which one is correct? I have tried training the network with <span class="math-container">$\gamma=0.1, 0.5, 0.9, 0.99$</span>, but the network can only learn with <span class="math-container">$\gamma=0.1, 0.5$</span>.</p>
  </blockquote>
  <p>Both are correct, although you do have to be concerned about <span class="math-container">$\gamma$</span>'s dual role as problem definition parameter and solution hyper-parameter when working with approximators.</p>
  <p>I think (but without looking at your code) that you have a problem with your neural network hyperparameters. A discount factor of <span class="math-container">$0.9$</span> or <span class="math-container">$0.99$</span> should work with DQN, and is a very common choice. I suggest try a few different architecture choices, and also DQN hyperparameters such as experience replay size, time between copying learning network to target network etc.</p>
  <p>Another thing that occurs to me, and may be specific to the environment that you are working with: If you are comparing the performance of your agent with a human, then a human may be able to apply their memory of previous attempts to this problem, and look for trends between time steps. If your state vector does not capture or summarise the history of guesses so far, and such &quot;trend&quot; information is actually useful for your problem, then you may need to add some kind of memory. You could modify the state to summarise attempts so far, or you could use an agent with memory, such as one based on a RNN.</p>
  <p>Whether an agent with memory would help depends on the nature of the different &quot;locations&quot; that are being guessed at, and the hints. A very simple example of where memory would make a huge difference is game where the locations are all the numbers between 1 and 100, and the agent is told &quot;higher&quot; or &quot;lower&quot; when it makes an incorrect guess. Storing (or learning to store) the bounds implied by guesses so far would be critical to good performance of the agent.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-07T22:19:14.110Z
Answers.Text: Thanks for the reply! 1. Regarding the memory, yes the agent has a memory in the state representations, so it won't check previously selected locations. 2. If I drop the positive reward and keeps the negative reward, do I still need prioritized experience replay (PER)? In the current setting, I find the agent stops learning when achieving accuracy of 0.8 without PER. 3. I find that $\gamma=0.9$ actually works, it just learns much slower, but ultimately still getting accuracy close to 1. Is the slower learning speed normal? And yes, I will continue tuning the hyperparameters.
Answers.UserDisplayName: Cloudy
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-08T07:17:14.490Z
Answers.Text: @Cloudy PER should still help. The slower learning may be normal, as with high gamma you have made the variance higher when sampling values over a non-deterministic behaviour. However, your stated goal is to make the agent better at completing the task with less time steps, and I think with a low $\gamma$ you have traded faster *initial* learning with worse performance at completing the task faster, You may find if you train for a much longer time with e.g. $\gamma=0.1$ vs $\gamma=0.9$ that both agents may have a similar accuracy, but the second one can use less time steps.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-10-07T12:08:34.780Z
Answers.LastActivityDate: 2021-10-07T15:05:09.170Z
Answers.LastEditDate: 2021-10-07T15:05:09.170Z
Answers.UserDisplayName: Neil Slater
Body: <p>I am trying to use reinforcement learning to solve a task and compare its performance to humans.</p>
  <p>The task is to find a single target in a fixed number of locations. At each step, the agent will pick one location, and check whether it contains the target. If the target is at this location, the agent will get a <span class="math-container">$+10$</span> reward and the trial ends; otherwise, the agent will get a hint at where the target is (with some stochastic noise), get a <span class="math-container">$-0.5$</span> reward, and it needs to pick another location in the next step. The trial will terminate if the agent cannot find the target within 40 steps (enough for humans). The goal is to solve the task as quickly and accurately as possible.</p>
  <p>I am now trying to solve this problem by Deep Q-Network with prioritized experience replay. With the discount factor <span class="math-container">$\gamma=0.5$</span>, the agent can learn quickly and solve the task with an accuracy close to 1.</p>
  <p>My current questions are:</p>
  <ol>
  <li><p>The accuracy level is already very high, but how to motivate the agent to find the target as quickly as possible?</p>
  </li>
  <li><p>What's the effect of <span class="math-container">$\gamma$</span> on the agent's task solving speed?</p>
  </li>
  </ol>
  <p>I am considering <span class="math-container">$\gamma$</span> because it relates to the time horizon of the agent's policy, but I now have two opposing ideas:</p>
  <ol>
  <li><p>With <span class="math-container">$\gamma \rightarrow 0$</span>, the agent is trying to maximize the immediate reward. Since the agent will only receive a positive reward when it finds the target, <span class="math-container">$\gamma \rightarrow 0$</span> motivates the agent to find the target in the immediate future, which means to solve the task quickly.</p>
  </li>
  <li><p>With <span class="math-container">$\gamma \rightarrow 1$</span>, the agent is trying to maximize the discounted sum of reward in the long term. This means to reduce the negative rewards as much as possible, which also means to solve the task quickly.</p>
  </li>
  </ol>
  <p>Which one is correct?</p>
  <p>I have tried training the network with <span class="math-container">$\gamma=0.1, 0.5, 0.9, 0.99$</span>, but the network can only learn with <span class="math-container">$\gamma=0.1, 0.5$</span>.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-10-07T00:12:30.243Z
Comments.Text: What crossed my mind is to give -1 reward (penalty) for every step, and if possible add more features to help the agent determine a location's potential
Comments.UserDisplayName: Sanyou
Tags: <reinforcement-learning><deep-rl><q-learning><reward-functions><discount-factor>
Title: How to encourage the reinforcement-learning agent to reach the goal as quickly as possible, and what's the effect of discount factor?
UserDisplayName: Cloudy
ThreadText: # How to encourage the reinforcement-learning agent to reach the goal as quickly as possible, and what's the effect of discount factor?
  
  (Asked by: username_0 on 2021-10-06)
  
  I am trying to use reinforcement learning to solve a task and compare its performance to humans.
  
  The task is to find a single target in a fixed number of locations. At each step, the agent will pick one location, and check whether it contains the target. If the target is at this location, the agent will get a $+10$ reward and the trial ends; otherwise, the agent will get a hint at where the target is (with some stochastic noise), get a $-0.5$ reward, and it needs to pick another location in the next step. The trial will terminate if the agent cannot find the target within 40 steps (enough for humans). The goal is to solve the task as quickly and accurately as possible.
  
  I am now trying to solve this problem by Deep Q-Network with prioritized experience replay. With the discount factor $\gamma=0.5$, the agent can learn quickly and solve the task with an accuracy close to 1.
  
  My current questions are:
  
  1. The accuracy level is already very high, but how to motivate the agent to find the target as quickly as possible?
  2. What's the effect of $\gamma$ on the agent's task solving speed?
  
  I am considering $\gamma$ because it relates to the time horizon of the agent's policy, but I now have two opposing ideas:
  
  1. With $\gamma \rightarrow 0$, the agent is trying to maximize the immediate reward. Since the agent will only receive a positive reward when it finds the target, $\gamma \rightarrow 0$ motivates the agent to find the target in the immediate future, which means to solve the task quickly.
  2. With $\gamma \rightarrow 1$, the agent is trying to maximize the discounted sum of reward in the long term. This means to reduce the negative rewards as much as possible, which also means to solve the task quickly.
  
  Which one is correct?
  
  I have tried training the network with $\gamma=0.1, 0.5, 0.9, 0.99$, but the network can only learn with $\gamma=0.1, 0.5$.
  
  **Tags:** reinforcement-learning, deep-rl, q-learning, reward-functions, discount-factor
  
  > **Comments:**
  > **username_1**: What crossed my mind is to give -1 reward (penalty) for every step, and if possible add more features to help the agent determine a location's potential  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-10-07. Score: 0 | Accepted answer
  
  > The accuracy level is already very high, but how to motivate the agent to find the target as quickly as possible?
  
  You already are, in two different ways:
  
  * A penalty (negative reward) for each time step taken.
  * A positive reward for completing a task, plus discounting.
  
  Both of these choices are sufficient that action values will be maximised by taking the most direct route to complete a task, and minimise expected time steps from any starting point.
  
  In theory you could completely lose one of the two approaches, and the reward system would still work.
  
  For DQN I would lose the positive reward at the end and use a relatively high discount factor, e.g. $\gamma = 0.99$ - which is only required for numerical stability, and not really part of the problem definition. If your goal is to minimise number of time steps, then a simple count of number of remaining time steps is already a good cost function, and negating it to make a reinforcement learning return is close to ideal. It often works well with Q learning too because it will explore away from repetition, even if at the start of training it cannot reach the target state.
  
  > What's the effect of $\gamma$ on the agent's task solving speed?
  
  This can be complex, but is a scenario with the only positive reward at the end and a discount factor, then expected reward will depend on expected future time steps in a geometric series. If in state $s\_1$, action choice $a\_1$ would lead to the end goal in 3 time steps and action choice $a\_2$ would lead to the end goal in 4 time steps, with the only reward $r\_T$ for reaching the goal state, then $q(s\_1, a\_1) = \gamma^3 r\_T \gt q(s\_1, a\_2) = \gamma^4 r\_T$, making $a\_1$ the obvious choice.
  
  A stochastic environment may muddy this a little, but in general the agent is going to prefer the lower number of timesteps to get to the goal. If distribution of number of timesteps can be very different, then different $\gamma$ values may cause slightly different gambling options made by the agent to complete faster. This is the reason why I suggest dropping the positive reward at the end, if your goal is to minimise expected number of timesteps to complete. That is because technically a change to $\gamma$ is a change to the problem definition - muddied slightly by usually needing $\gamma \lt 1$ when training a DQN to improve stability.
  
  > Which one is correct? I have tried training the network with $\gamma=0.1, 0.5, 0.9, 0.99$, but the network can only learn with $\gamma=0.1, 0.5$.
  
  Both are correct, although you do have to be concerned about $\gamma$'s dual role as problem definition parameter and solution hyper-parameter when working with approximators.
  
  I think (but without looking at your code) that you have a problem with your neural network hyperparameters. A discount factor of $0.9$ or $0.99$ should work with DQN, and is a very common choice. I suggest try a few different architecture choices, and also DQN hyperparameters such as experience replay size, time between copying learning network to target network etc.
  
  Another thing that occurs to me, and may be specific to the environment that you are working with: If you are comparing the performance of your agent with a human, then a human may be able to apply their memory of previous attempts to this problem, and look for trends between time steps. If your state vector does not capture or summarise the history of guesses so far, and such "trend" information is actually useful for your problem, then you may need to add some kind of memory. You could modify the state to summarise attempts so far, or you could use an agent with memory, such as one based on a RNN.
  
  Whether an agent with memory would help depends on the nature of the different "locations" that are being guessed at, and the hints. A very simple example of where memory would make a huge difference is game where the locations are all the numbers between 1 and 100, and the agent is told "higher" or "lower" when it makes an incorrect guess. Storing (or learning to store) the bounds implied by guesses so far would be critical to good performance of the agent.
  
  > **Comments:**
  > **username_0**: Thanks for the reply! 1. Regarding the memory, yes the agent has a memory in the state representations, so it won't check previously selected locations. 2. If I drop the positive reward and keeps the negative reward, do I still need prioritized experience replay (PER)? In the current setting, I find the agent stops learning when achieving accuracy of 0.8 without PER. 3. I find that $\gamma=0.9$ actually works, it just learns much slower, but ultimately still getting accuracy close to 1. Is the slower learning speed normal? And yes, I will continue tuning the hyperparameters.  
  > **username_2**: @username_0 PER should still help. The slower learning may be normal, as with high gamma you have made the variance higher when sampling values over a non-deterministic behaviour. However, your stated goal is to make the agent better at completing the task with less time steps, and I think with a low $\gamma$ you have traded faster *initial* learning with worse performance at completing the task faster, You may find if you train for a much longer time with e.g. $\gamma=0.1$ vs $\gamma=0.9$ that both agents may have a similar accuracy, but the second one can use less time steps.  
  
  ---
  
  