Answers.Body: <p>I found out the problem of why the optimization process got stuck and never moved closer to the global optimum. It's because of the rate between 'explore' or 'exploit'.</p>
  <p>Basically, in RL, the agent <em>explores</em> by doing a random action and to find new solutions, <em>exploits</em> the existing so-called known max future rewards to do the max action.</p>
  <p>Initially, I put the agent to explore when <span class="math-container">$random() &lt; 1/(replay\_index+1)$</span>, exploration rate reduces too quick (&lt;10% after 10 iterations), and when the number of replays (number of times to play again from start) is not enough, the explore rate at the end of the loop is almost zero, and nothing new learned.</p>
  <p>The solution opted is allowing 'explore' and 'exploit' to have the same rate (or lower exploration a bit is also ok), pseudo-code:</p>
  <pre><code># Part 1 in a step: Choose action
  if random() &lt; 0.5: # 0.25 is also good, 25% for exploration
      action = random_action()
  else:
      action = choose_best_known_action()
  </code></pre>
  <p>Explore rate can be reduced correctly this way:</p>
  <pre><code>if random() &lt; 1-i/NUM_REPLAYS: # i is current train step index
      action = random_action()
  else:
      ...
  </code></pre>
  <p>With the half-explore/half-exploit scheme above, the agent will learn to infinity, so, it is kinda sure that the global optimum would be reached. When knowing from practice the number of iterations that should be used, 'exploit' may be utilized more for faster convergence.</p>
  <p>Note that the 'explore' and 'exploit' rates are put equal above, the but q-table or q-network is still better and better due to having another 'exploit'-kind when updating q-table or fitting q-network with Bellman equation, <strong>there's another 'exploit' here, the 'max' in Bellman equation</strong>:</p>
  <p>Pseudo-code:</p>
  <pre><code># Part 2 in a step: Update q-table or q-network
  q[s][a] += learning_rate * (reward + max(q[sNext][aNext]) - q[s][a])
  
  # Q-network
  # target = r + max(...
  <span class="math-container">```</span>
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-17T10:49:36.450Z
Answers.Text: what do you mean with "when the number of replays (number of times to play again from start) is not enough"?
Answers.UserDisplayName: malioboro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-17T10:54:41.030Z
Answers.Text: it's the outer most interation, RL plays from square 1, again and again a 'number of replays'
Answers.UserDisplayName: Dan D.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-17T12:17:04.767Z
Answers.Text: not enough replays --> not enough iterations (the outer most loop)
Answers.UserDisplayName: Dan D.
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-17T09:38:03.250Z
Answers.LastActivityDate: 2021-12-11T08:48:03.990Z
Answers.LastEditDate: 2021-12-11T08:48:03.990Z
Answers.UserDisplayName: Dan D.
Body: <p>When using the Bellman equation to update q-table or train q-network to fit greedy max values, the q-values very often get to the local optima and get stuck although randomization rate (<span class="math-container">$\epsilon$</span>) has already been applied since the start.</p>
  <p>The sum of q-values of all very first steps (of different actions at the original location of the agent) increases gradually until a local optimum is reached. It gets stuck and this sum of q-values starts decreasing slowly a bit by a bit.</p>
  <p><strong>How to avoid being stuck in a local optimum? and how to know if the local optimum is already the global optimum?</strong> I may think of this but it's chaotic: Switch on randomization again for a while, worse values may come at first but maybe better in the future.</p>
  
Tags: <machine-learning><reinforcement-learning><q-learning><optimization><bellman-equations>
Title: How to avoid being stuck local optima in q-learning and q-network
UserDisplayName: Dan D.
ThreadText: # How to avoid being stuck local optima in q-learning and q-network
  
  (Asked by: username_0 on 2021-03-17)
  
  When using the Bellman equation to update q-table or train q-network to fit greedy max values, the q-values very often get to the local optima and get stuck although randomization rate ($\epsilon$) has already been applied since the start.
  
  The sum of q-values of all very first steps (of different actions at the original location of the agent) increases gradually until a local optimum is reached. It gets stuck and this sum of q-values starts decreasing slowly a bit by a bit.
  
  **How to avoid being stuck in a local optimum? and how to know if the local optimum is already the global optimum?** I may think of this but it's chaotic: Switch on randomization again for a while, worse values may come at first but maybe better in the future.
  
  **Tags:** machine-learning, reinforcement-learning, q-learning, optimization, bellman-equations
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2021-03-17. Score: 1 | Accepted answer
  
  I found out the problem of why the optimization process got stuck and never moved closer to the global optimum. It's because of the rate between 'explore' or 'exploit'.
  
  Basically, in RL, the agent *explores* by doing a random action and to find new solutions, *exploits* the existing so-called known max future rewards to do the max action.
  
  Initially, I put the agent to explore when $random() < 1/(replay\\_index+1)$, exploration rate reduces too quick (<10% after 10 iterations), and when the number of replays (number of times to play again from start) is not enough, the explore rate at the end of the loop is almost zero, and nothing new learned.
  
  The solution opted is allowing 'explore' and 'exploit' to have the same rate (or lower exploration a bit is also ok), pseudo-code:
  
  ```
  # Part 1 in a step: Choose action
  if random() < 0.5: # 0.25 is also good, 25% for exploration
      action = random_action()
  else:
      action = choose_best_known_action()
  
  ```
  
  Explore rate can be reduced correctly this way:
  
  ```
  if random() < 1-i/NUM_REPLAYS: # i is current train step index
      action = random_action()
  else:
      ...
  
  ```
  
  With the half-explore/half-exploit scheme above, the agent will learn to infinity, so, it is kinda sure that the global optimum would be reached. When knowing from practice the number of iterations that should be used, 'exploit' may be utilized more for faster convergence.
  
  Note that the 'explore' and 'exploit' rates are put equal above, the but q-table or q-network is still better and better due to having another 'exploit'-kind when updating q-table or fitting q-network with Bellman equation, **there's another 'exploit' here, the 'max' in Bellman equation**:
  
  Pseudo-code:
  
  ```
  # Part 2 in a step: Update q-table or q-network
  q[s][a] += learning_rate * (reward + max(q[sNext][aNext]) - q[s][a])
  
  # Q-network
  # target = r + max(...
  ```
  
  ```
  
  > **Comments:**
  > **username_1**: what do you mean with "when the number of replays (number of times to play again from start) is not enough"?  
  > **username_0**: it's the outer most interation, RL plays from square 1, again and again a 'number of replays'  
  > **username_0**: not enough replays --> not enough iterations (the outer most loop)  
  
  ---
  
  