Answers.Body: <p>With tabular reinforcement learning (RL) methods, then catastrophic forgetting does not come into play, as it is a feature of online learning with approximators such as neural networks. Essentially your table never forgets anything, although it may become out of date for rarely-visited state/action pairs whilst an approximator will often still maintain them at least a little due to generalisation.</p>
  <p>The convergence time for RL methods is highly variable, and depends on many factors.</p>
  <p>Tabular methods have relatively simple requirements for state/action visits though, and if your two environments are very similar, then it might be reasonable to expect the amount of experience required for convergence to scale roughly according to <span class="math-container">$O(|\mathcal{S}| \times |\mathcal{A}|)$</span> - that assumes you have no guiding principle to generalise state/action features or skip explorations.</p>
  <p>Assuming your convergence sample size really is <span class="math-container">$O(|\mathcal{S}| \times |\mathcal{A}|)$</span> then extrapolating from your smaller to your larger environment implies you may need as many as 50 million iterations to get convergence on the larger instance. This is a crude aprpoximation, because so much depends on the nature of the changes - it may be that 5 million should be enough (and something is wrong with your implementation), or you may need 500 million. For instance one important factor I have left out of <em>very similar</em> is episode length (assuming you are solving for an episodic problem) - if that is also significantly larger, you may be looking at the 500 million case. Also critically important is how long the initial agent takes to find high scoring episodes.</p>
  <blockquote>
  <p>I also want to add that in this case there are state dependent actions, so for actions that cannot be taken I have created a dummy state and a negative reward. Is it the reason?</p>
  </blockquote>
  <p>Ideally you would not allow the agent to take actions that are not possible in a current state. You should check your library in case there is a way to inform the agent of its current set of actions instead of specifying an action space for the whole environment. If there are a lot of unavailable actions, it could be costing the agent a lot of time exploring them and learning not to take them.</p>
  <p>Instead of adding &quot;dummy&quot; states, one approach would be to give a negative reward and have the agent transition to its <em>current</em> state - i.e. no change. The negative reward should be larger than any negative reward possible for valid action choices (otherwise the agent may prefer to collect the slightly-less-negative reward than it predicts it will get from taking a real action).</p>
  <p>There are lots of changes you might consider to improve your agent to deal with harder-to-solve environments in reasonale time. I am not sure what you are able to consider, so here are a few open-ended ideas:</p>
  <ul>
  <li><p>Use function approximation to generalise state and action features. This does expose you to a whole different set of complications though, such as losing guarantees of convergence, and also catastrophic forgetting.</p>
  </li>
  <li><p>Use eligibility traces and either Q(<span class="math-container">$\lambda$</span>) or SARSA(<span class="math-container">$\lambda$</span>). This can help you find a sweet spot for learning efficiency by considering multiple trajectory lengths for estimating returns. Alternatively, you could consider n-step returns.</p>
  </li>
  <li><p>Use an experience replay table, or Dyna-Q with Q-learning, to extract more data from previous experience. Whether or not this is useful depends on how fast the environment simulation runs. If your learning time is limited mostly by simulation speed of the environment, this is a good choice. If it is limited by the time taken by the Q-learning process, you are better off generating fresh data as fast as possible.</p>
  </li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-18T06:20:01.963Z
Answers.Text: Hello and thanks for your answer. I run the 50 million episodes (yes, I'm working with episodic tasks) and it worked, so I'm sure my implementation is right and the extrapolation suposition was also right. My question now is: I have tried in the ``complex problem'' what is faster in the simple problem, so to speed up computations, should the same configurations be equally fast in both problems?
Answers.UserDisplayName: Aquila
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-16T16:47:15.843Z
Answers.LastActivityDate: 2022-05-16T16:55:11.170Z
Answers.LastEditDate: 2022-05-16T16:55:11.170Z
Answers.UserDisplayName: Neil Slater
Body: <p>I am new in the AI field and I am trying to use Reinforcement Learning. Specifically, I am using tabular Q-Learning and SARSA algorithms to solve a sequential decision making problem. (I am using <a href="https://github.com/JuliaPOMDP/TabularTDLearning.jl" rel="nofollow noreferrer"><code>TabularTDLearning.jl</code></a>, <a href="https://github.com/JuliaPOMDP/TabularTDLearning.jl/blob/master/src/q_learn.jl" rel="nofollow noreferrer"><code>q_learn.jl</code></a> and <a href="https://github.com/JuliaPOMDP/TabularTDLearning.jl/blob/master/src/sarsa.jl" rel="nofollow noreferrer"><code>sarsa.jl</code></a>, with 16 GB of RAM).</p>
  <p>When I apply those algorithms to a problem with 6.593 states and 169 actions, in less than a minute, it takes</p>
  <ul>
  <li>200.000 iterations with Q-Learning, and</li>
  <li>400.000 with SARSA</li>
  </ul>
  <p>If I try to solve a more complex problem with 125.231 states and 2.197 actions, it does not converge, in fact it gets worse as iterations increase (5.000.000 iterations).</p>
  <p>Is it possible learning convergence is lost as the state space grows?</p>
  <p>I have read about catastrophic forgetting. I do not know if it is the problem why convergence has not happened. Could catastrophic forgetting be the problem?</p>
  <p>For actions that cannot be taken, I have created a dummy state and a negative reward. Could this have affected the convergence of the algorithms?</p>
  
Tags: <reinforcement-learning><q-learning><convergence><sarsa><state-spaces>
Title: Is it possible learning convergence is lost in Reinforcement Learning as the state space grows?
UserDisplayName: Aquila
ThreadText: # Is it possible learning convergence is lost in Reinforcement Learning as the state space grows?
  
  (Asked by: username_0 on 2022-05-16)
  
  I am new in the AI field and I am trying to use Reinforcement Learning. Specifically, I am using tabular Q-Learning and SARSA algorithms to solve a sequential decision making problem. (I am using [`TabularTDLearning.jl`](https://github.com/JuliaPOMDP/TabularTDLearning.jl), [`q_learn.jl`](https://github.com/JuliaPOMDP/TabularTDLearning.jl/blob/master/src/q_learn.jl) and [`sarsa.jl`](https://github.com/JuliaPOMDP/TabularTDLearning.jl/blob/master/src/sarsa.jl), with 16 GB of RAM).
  
  When I apply those algorithms to a problem with 6.593 states and 169 actions, in less than a minute, it takes
  
  * 200.000 iterations with Q-Learning, and
  * 400.000 with SARSA
  
  If I try to solve a more complex problem with 125.231 states and 2.197 actions, it does not converge, in fact it gets worse as iterations increase (5.000.000 iterations).
  
  Is it possible learning convergence is lost as the state space grows?
  
  I have read about catastrophic forgetting. I do not know if it is the problem why convergence has not happened. Could catastrophic forgetting be the problem?
  
  For actions that cannot be taken, I have created a dummy state and a negative reward. Could this have affected the convergence of the algorithms?
  
  **Tags:** reinforcement-learning, q-learning, convergence, sarsa, state-spaces
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-05-16. Score: 1 | Accepted answer
  
  With tabular reinforcement learning (RL) methods, then catastrophic forgetting does not come into play, as it is a feature of online learning with approximators such as neural networks. Essentially your table never forgets anything, although it may become out of date for rarely-visited state/action pairs whilst an approximator will often still maintain them at least a little due to generalisation.
  
  The convergence time for RL methods is highly variable, and depends on many factors.
  
  Tabular methods have relatively simple requirements for state/action visits though, and if your two environments are very similar, then it might be reasonable to expect the amount of experience required for convergence to scale roughly according to $O(|\mathcal{S}| \times |\mathcal{A}|)$ - that assumes you have no guiding principle to generalise state/action features or skip explorations.
  
  Assuming your convergence sample size really is $O(|\mathcal{S}| \times |\mathcal{A}|)$ then extrapolating from your smaller to your larger environment implies you may need as many as 50 million iterations to get convergence on the larger instance. This is a crude aprpoximation, because so much depends on the nature of the changes - it may be that 5 million should be enough (and something is wrong with your implementation), or you may need 500 million. For instance one important factor I have left out of *very similar* is episode length (assuming you are solving for an episodic problem) - if that is also significantly larger, you may be looking at the 500 million case. Also critically important is how long the initial agent takes to find high scoring episodes.
  
  > I also want to add that in this case there are state dependent actions, so for actions that cannot be taken I have created a dummy state and a negative reward. Is it the reason?
  
  Ideally you would not allow the agent to take actions that are not possible in a current state. You should check your library in case there is a way to inform the agent of its current set of actions instead of specifying an action space for the whole environment. If there are a lot of unavailable actions, it could be costing the agent a lot of time exploring them and learning not to take them.
  
  Instead of adding "dummy" states, one approach would be to give a negative reward and have the agent transition to its *current* state - i.e. no change. The negative reward should be larger than any negative reward possible for valid action choices (otherwise the agent may prefer to collect the slightly-less-negative reward than it predicts it will get from taking a real action).
  
  There are lots of changes you might consider to improve your agent to deal with harder-to-solve environments in reasonale time. I am not sure what you are able to consider, so here are a few open-ended ideas:
  
  * Use function approximation to generalise state and action features. This does expose you to a whole different set of complications though, such as losing guarantees of convergence, and also catastrophic forgetting.
  * Use eligibility traces and either Q($\lambda$) or SARSA($\lambda$). This can help you find a sweet spot for learning efficiency by considering multiple trajectory lengths for estimating returns. Alternatively, you could consider n-step returns.
  * Use an experience replay table, or Dyna-Q with Q-learning, to extract more data from previous experience. Whether or not this is useful depends on how fast the environment simulation runs. If your learning time is limited mostly by simulation speed of the environment, this is a good choice. If it is limited by the time taken by the Q-learning process, you are better off generating fresh data as fast as possible.
  
  > **Comments:**
  > **username_0**: Hello and thanks for your answer. I run the 50 million episodes (yes, I'm working with episodic tasks) and it worked, so I'm sure my implementation is right and the extrapolation suposition was also right. My question now is: I have tried in the ``complex problem'' what is faster in the simple problem, so to speed up computations, should the same configurations be equally fast in both problems?  
  
  ---
  
  