Answers.Body: <p>I think that you should use quite different approaches when training on environments with sparse rewards compared to training on environments with dense rewards. It is not just the learning rate.</p>
  <p>With dense rewards you can make progress even with partial trajectories. Because you get some reward signal, you can update the weights of the model after some steps (even at every step if you want to). In general, training on dense rewards is much easier and that is why most of the times people try to design a dense reward function for their environment.</p>
  <p>With sparse rewards you cannot really make progress with partial trajectories. You <strong>need</strong> a full rollout that has reached a terminal state, so that you can propagate the reward signal from that terminal state. Algorithms like DQN, and PPO that use partial trajectories (n-step return) will not really work on an environment with a sparse reward func. You could try Monte-Carlo Policy Gradient, which works on full trajectories, but this algo is quite ineffective and I wouldn't recommend it.</p>
  <p>Most of the times when you have a sparse reward function, your environment is actually fully observable (think Go, Chess, Rubik's cube). In the case of a fully-observable environment people tend to use some kind of a policy-guided tree-search algorithm, instead of model-free algorithms. So you would create full rollouts until a terminal state is reached and then update the weights of the policy. See for example <a href="https://vk.com/doc-44016343_437229031?dl=56ce06e325d42fbc72" rel="nofollow noreferrer">AlphaGo</a> and <a href="https://deepcube.igb.uci.edu/static/files/SolvingTheRubiksCubeWithDeepReinforcementLearningAndSearch_Final.pdf" rel="nofollow noreferrer">Rubik's cube</a>.</p>
  <p><em><strong>Regarding your question about any research on this topic:</strong></em></p>
  <p>I think that you are looking at this the wrong way. It is not about &quot;Here are some RL algos, lets see how to tweak them so that they work on this and that environment&quot;... It is about &quot;I have this problem, let's see what solution I can use to solve it&quot;.</p>
  <ul>
  <li>If the problem is fully-observable, then you shouldn't be looking at model-free algorithms. There are other <strong>much more appropriate</strong> solutions, like tree-search, value iteration, dynamic programming, etc.</li>
  <li>If the problem is partially-observable, then try to design a good dense reward function. If you manage to do that, then model-free RL (PPO, DQN, etc.) is a good fit.</li>
  <li>If the problem is partially-observable and you cannot design a dense reward function, then you could either try imitation learning, which is quite similar to supervised learning from data (I wouldn't really call this RL), or you could try learning from human feedback, which again involves learning from data, but you are actually learning the reward func instead of the policy.</li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-07-01T10:14:15.290Z
Answers.Text: I'm quite familiar with all those techniques to handle environments with dense or sparse rewards. The previous answer raise the idea of "common sense" that we should use higher learning rates for problems with sparse rewards, but why and when this would work? I'm looking for studies to support it, if there's any.
Answers.UserDisplayName: HenDoNR
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-07-01T11:21:45.780Z
Answers.Text: I think that your learning rate depends mostly on the neural net architecture that you are using, whether u have normalization layers, the optimizer that you are using (adam, sgd, etc.). Regarding rewards, in order to stabilize your training, you would usually scale/clip your rewards, and you would also normalize your returns. No need to adjust learning rate depending on sparsity/density of rewards.
Answers.UserDisplayName: pi-tau
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-07-01T12:26:10.630Z
Answers.Text: I guess that the more intricate the task, the bigger the network should be to accommodate the knowledge required. However, since it is hard to find rewards in environments with sparse ones, it would make sense to "shake" things a bit whenever you get them. Usually, I see higher learning rates for environments involving grid worlds, for instance.
Answers.UserDisplayName: HenDoNR
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-07-04T10:17:29.570Z
Answers.Text: If you don't find any rewards, then you shouldn't propagate anything because your model will learn to predict only 0s (already mentioned in the other answer). You should learn only from trajects that contain a reward. There's nothing to "shake up", you should just throw away anything that doesn't contain a reward. Since you have very few trajects that contain rewards, you get to make very few updates. Naturally this would mean that you should use a higher learning rate, so that you could learn things with fewer updates. However, this is unstable, that is why people use small learning rates.
Answers.UserDisplayName: pi-tau
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-07-04T10:26:17.600Z
Answers.Text: Grid worlds are considered baby environments in RL and are only used for teaching purposes. You see higher learning rates in this tasks because the state space is really small and everything can be learned easily. If the model has more parameters than the size of the state space then this actually reduces down to a using a table method. If you want to do somewhat of a fair comparison, then take the LunarLander env and modify the reward space so that you get `1` when the spacecraft lands and `0` otherwise (or sth similar). Try to see if model-free RL can solve this task and what LR you need
Answers.UserDisplayName: pi-tau
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-07-01T09:27:22.790Z
Answers.LastActivityDate: 2024-07-01T09:27:22.790Z
Answers.UserDisplayName: pi-tau
Answers.Body: <p>If you have sparse binary reward, most of the rewards are <span class="math-container">$0$</span>, so if you are using DQN, the network quickly learns to always predict <span class="math-container">$0$</span> (and the gradient would be 0 since there is no error), and in case of Actor critic methods, same happens when you do <span class="math-container">$G\ln(p(a|s))$</span>... so there it not much to observe, is the expected behavior</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-06-30T19:40:23.890Z
Answers.Text: Yes, but I'm looking for a more formal definition, perhaps a paper diving into theory or empirical results to support it.
Answers.UserDisplayName: HenDoNR
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-06-30T21:42:11.877Z
Answers.Text: @HenDoNR to support what?... usually you don't publish a paper that "dives" in something that aligns with the expectation
Answers.UserDisplayName: Alberto
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-06-30T19:09:00.177Z
Answers.LastActivityDate: 2024-06-30T19:09:00.177Z
Answers.UserDisplayName: Alberto
Body: <p>In environments with sparse and (sometimes) binary rewards such as Taxi Cab, Mountain Car and Frozen Lake, where agents rarely encounter positive outcomes, I've observed that the gradient descent's learning rate is typically higher than in environments with dense reward functions. This makes sense because when a positive outcome is finally achieved, it is crucial to make significant updates to the policy. Conversely, finer adjustments are preferable to refine the policy in more intricate tasks. However, I haven't found any research papers addressing this observation. Are my thoughts accurate, and is there any literature that supports them?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-07-01T11:22:43.373Z
Comments.Text: Could you provide examples of RL agents used for sparse reward environments ?
Comments.UserDisplayName: pi-tau
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-07-01T12:29:43.060Z
Comments.Text: I added them in the question.
Comments.UserDisplayName: HenDoNR
Tags: <reinforcement-learning><deep-rl><dqn>
Title: Learning rate and rewards in Deep Reinforcement Learning
UserDisplayName: HenDoNR
ThreadText: # Learning rate and rewards in Deep Reinforcement Learning
  
  (Asked by: username_0 on 2024-06-30)
  
  In environments with sparse and (sometimes) binary rewards such as Taxi Cab, Mountain Car and Frozen Lake, where agents rarely encounter positive outcomes, I've observed that the gradient descent's learning rate is typically higher than in environments with dense reward functions. This makes sense because when a positive outcome is finally achieved, it is crucial to make significant updates to the policy. Conversely, finer adjustments are preferable to refine the policy in more intricate tasks. However, I haven't found any research papers addressing this observation. Are my thoughts accurate, and is there any literature that supports them?
  
  **Tags:** reinforcement-learning, deep-rl, dqn
  > **Comments:**
  > **username_1**: Could you provide examples of RL agents used for sparse reward environments ?  
  > **username_0**: I added them in the question.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2024-07-01. Score: 1
  
  I think that you should use quite different approaches when training on environments with sparse rewards compared to training on environments with dense rewards. It is not just the learning rate.
  
  With dense rewards you can make progress even with partial trajectories. Because you get some reward signal, you can update the weights of the model after some steps (even at every step if you want to). In general, training on dense rewards is much easier and that is why most of the times people try to design a dense reward function for their environment.
  
  With sparse rewards you cannot really make progress with partial trajectories. You **need** a full rollout that has reached a terminal state, so that you can propagate the reward signal from that terminal state. Algorithms like DQN, and PPO that use partial trajectories (n-step return) will not really work on an environment with a sparse reward func. You could try Monte-Carlo Policy Gradient, which works on full trajectories, but this algo is quite ineffective and I wouldn't recommend it.
  
  Most of the times when you have a sparse reward function, your environment is actually fully observable (think Go, Chess, Rubik's cube). In the case of a fully-observable environment people tend to use some kind of a policy-guided tree-search algorithm, instead of model-free algorithms. So you would create full rollouts until a terminal state is reached and then update the weights of the policy. See for example [AlphaGo](https://vk.com/doc-44016343_437229031?dl=56ce06e325d42fbc72) and [Rubik's cube](https://deepcube.igb.uci.edu/static/files/SolvingTheRubiksCubeWithDeepReinforcementLearningAndSearch_Final.pdf).
  
  ***Regarding your question about any research on this topic:***
  
  I think that you are looking at this the wrong way. It is not about "Here are some RL algos, lets see how to tweak them so that they work on this and that environment"... It is about "I have this problem, let's see what solution I can use to solve it".
  
  * If the problem is fully-observable, then you shouldn't be looking at model-free algorithms. There are other **much more appropriate** solutions, like tree-search, value iteration, dynamic programming, etc.
  * If the problem is partially-observable, then try to design a good dense reward function. If you manage to do that, then model-free RL (PPO, DQN, etc.) is a good fit.
  * If the problem is partially-observable and you cannot design a dense reward function, then you could either try imitation learning, which is quite similar to supervised learning from data (I wouldn't really call this RL), or you could try learning from human feedback, which again involves learning from data, but you are actually learning the reward func instead of the policy.
  
  > **Comments:**
  > **username_0**: I'm quite familiar with all those techniques to handle environments with dense or sparse rewards. The previous answer raise the idea of "common sense" that we should use higher learning rates for problems with sparse rewards, but why and when this would work? I'm looking for studies to support it, if there's any.  
  > **username_1**: I think that your learning rate depends mostly on the neural net architecture that you are using, whether u have normalization layers, the optimizer that you are using (adam, sgd, etc.). Regarding rewards, in order to stabilize your training, you would usually scale/clip your rewards, and you would also normalize your returns. No need to adjust learning rate depending on sparsity/density of rewards.  
  > **username_0**: I guess that the more intricate the task, the bigger the network should be to accommodate the knowledge required. However, since it is hard to find rewards in environments with sparse ones, it would make sense to "shake" things a bit whenever you get them. Usually, I see higher learning rates for environments involving grid worlds, for instance.  
  > **username_1**: If you don't find any rewards, then you shouldn't propagate anything because your model will learn to predict only 0s (already mentioned in the other answer). You should learn only from trajects that contain a reward. There's nothing to "shake up", you should just throw away anything that doesn't contain a reward. Since you have very few trajects that contain rewards, you get to make very few updates. Naturally this would mean that you should use a higher learning rate, so that you could learn things with fewer updates. However, this is unstable, that is why people use small learning rates.  
  > **username_1**: Grid worlds are considered baby environments in RL and are only used for teaching purposes. You see higher learning rates in this tasks because the state space is really small and everything can be learned easily. If the model has more parameters than the size of the state space then this actually reduces down to a using a table method. If you want to do somewhat of a fair comparison, then take the LunarLander env and modify the reward space so that you get `1` when the spacecraft lands and `0` otherwise (or sth similar). Try to see if model-free RL can solve this task and what LR you need  
  
  ---
  
  ### Answer by username_2 on 2024-06-30. Score: 0
  
  If you have sparse binary reward, most of the rewards are $0$, so if you are using DQN, the network quickly learns to always predict $0$ (and the gradient would be 0 since there is no error), and in case of Actor critic methods, same happens when you do $G\ln(p(a|s))$... so there it not much to observe, is the expected behavior
  
  > **Comments:**
  > **username_0**: Yes, but I'm looking for a more formal definition, perhaps a paper diving into theory or empirical results to support it.  
  > **username_2**: @HenDoNR to support what?... usually you don't publish a paper that "dives" in something that aligns with the expectation  
  
  ---
  
  