Answers.Body: <p>If your intention is to learn make the agent learn which has the min arbitrary value, then you would need to modify your rewards a bit. </p>
  
  <p>The current reward structure provides the incentive to just move to a stage where it gets a reward. </p>
  
  <p>For example, if it is at state 0, it gets the same reward to go to either state 2 or state 3, since both of them have a higher inverse value.</p>
  
  <p>To make the agent learn to move to state 2, you would have to provide it with more incentives to go to state 2.</p>
  
  <pre><code>def reward(s,a,s_dash):
      if s_dash == 2:
          return 5
      elif inverse_values_for_states[s]&lt;inverse_values_for_states[s_dash]: 
          return 1
      elif inverse_values_for_states[s]&gt;inverse_values_for_states[s_dash]:
          return -1
      else:
          return 0
  </code></pre>
  
  <p>I tried using this and it converges to 2. This is a hard-coded version, but I guess you get the idea.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-02-11T08:25:26.963Z
Answers.Text: It's worse than you suggest. The OP's reward structure encourages the smallest possible incremental improvement on each action, because then it is possible for it to receive maximum rewards before finishing. It is better to score $[1,1,1,-1,1,1,1,-1....]$ starting from the worst state than score $[1,0,0...]$ and this is shown by the OP's converged values.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-21T18:54:02.640Z
Answers.LastActivityDate: 2020-05-21T18:54:02.640Z
Answers.UserDisplayName: pecey
Body: <p>This is an experiment in order to understand the working of Q table and Q learning.</p>
  
  <p>I have the states as </p>
  
  <p><code>states = [0,1,2,3]</code></p>
  
  <p>I have an arbitrary value for each of these states as shown below (assume index-based mapping) -</p>
  
  <p><code>arbitrary_values_for_states = [39.9,47.52,32.92,37.6]</code></p>
  
  <p>I want to find the minimum of the state which will give me the minimum value.
  So I have complimented the values to 50-arbitrary value.</p>
  
  <p><code>inverse_values_for_states = [50-x for x in arbitrary_values_for_states]</code></p>
  
  <p>Therefore, I defined reward function as -</p>
  
  <pre><code>def reward(s,a,s_dash):
      if inverse_values_for_states[s]&lt;inverse_values_for_states[s_dash]:
          return 1
      elif inverse_values_for_states[s]&gt;inverse_values_for_states[s_dash]:
          return -1
      else:
          return 0
  </code></pre>
  
  <p>Q table is initialized as - 
  <code>Q = np.zeros((4,4))</code> (np is numpy)</p>
  
  <p>The learning is carried out as -</p>
  
  <pre><code>episodes = 5
  steps = 10
  for episode in range(episodes):
      s = np.random.randint(0,4)
      alpha0 = 0.05
      decay = 0.005
      gamma = 0.6
      for step in range(steps):
          a = np.random.randint(0,4)
          action.append(a)
          s_dash = a
          alpha = alpha0/(1+step*decay)
          Q[s][a] = (1-alpha)*Q[s][a]+alpha*(reward(s,a,s_dash)+gamma*np.max(Q[s_dash]))
  
          s = s_dash
  </code></pre>
  
  <p>The problem is, the table doesn't converge.</p>
  
  <p>Example. For the above scenario - </p>
  
  <pre><code>np.argmax(Q[0]) gives 3
  np.argmax(Q[1]) gives 2
  np.argmax(Q[2]) gives 2
  np.argmax(Q[3]) gives 2
  </code></pre>
  
  <p>All of the states should give argmax as 2 (which is actually the index[state] of the minimum value).</p>
  
  <p>Another example, </p>
  
  <p>when I increase steps to 1000 and episodes to 50, </p>
  
  <pre><code>np.argmax(Q[0]) gives 3
  np.argmax(Q[1]) gives 0
  np.argmax(Q[2]) gives 1
  np.argmax(Q[3]) gives 2
  </code></pre>
  
  <p>More, steps and episodes should assure convergence, but this is not visible.</p>
  
  <p>I need help where I am going wrong. </p>
  
  <p>PS: This little experiment is needed to make Q-learning applicable to a larger combinatorial problem. Unless I understand this, I don't think I will be able to do that right.
  Also, there is no terminal state because this is an optimization problem. (And I have heard that Q-learning doesn't necessarily needs a terminal state)</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-06T08:50:41.507Z
Comments.Text: `for episode in range(episodes):`
  doesn't it should be `for steps in range(episodes)` ? Sorry, I'm a C++ guy, it's a bit daunting to me... :P
Comments.UserDisplayName: Abhas Kumar Sinha
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-06T14:45:25.583Z
Comments.Text: @abhas_RewCie range() is like a vector of integers. `episodes` specify the stop value for generating the integers. `episode` is like a candidate element (i) of that vector. So, it will loosely translate as `for(int episode=0; episode<episodes.size();episode++)`
Comments.UserDisplayName: Prabal Dev
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-05-06T14:50:06.723Z
Comments.Text: if you don't mind writing the algorithm....
Comments.UserDisplayName: Abhas Kumar Sinha
Tags: <reinforcement-learning><q-learning>
Title: Q table not converging for an arbitrary experiment
UserDisplayName: Prabal Dev
ThreadText: # Q table not converging for an arbitrary experiment
  
  (Asked by: username_0 on 2020-05-06)
  
  This is an experiment in order to understand the working of Q table and Q learning.
  
  I have the states as
  
  `states = [0,1,2,3]`
  
  I have an arbitrary value for each of these states as shown below (assume index-based mapping) -
  
  `arbitrary_values_for_states = [39.9,47.52,32.92,37.6]`
  
  I want to find the minimum of the state which will give me the minimum value.
  So I have complimented the values to 50-arbitrary value.
  
  `inverse_values_for_states = [50-x for x in arbitrary_values_for_states]`
  
  Therefore, I defined reward function as -
  
  ```
  def reward(s,a,s_dash):
      if inverse_values_for_states[s]<inverse_values_for_states[s_dash]:
          return 1
      elif inverse_values_for_states[s]>inverse_values_for_states[s_dash]:
          return -1
      else:
          return 0
  
  ```
  
  Q table is initialized as -
  `Q = np.zeros((4,4))` (np is numpy)
  
  The learning is carried out as -
  
  ```
  episodes = 5
  steps = 10
  for episode in range(episodes):
      s = np.random.randint(0,4)
      alpha0 = 0.05
      decay = 0.005
      gamma = 0.6
      for step in range(steps):
          a = np.random.randint(0,4)
          action.append(a)
          s_dash = a
          alpha = alpha0/(1+step*decay)
          Q[s][a] = (1-alpha)*Q[s][a]+alpha*(reward(s,a,s_dash)+gamma*np.max(Q[s_dash]))
  
          s = s_dash
  
  ```
  
  The problem is, the table doesn't converge.
  
  Example. For the above scenario -
  
  ```
  np.argmax(Q[0]) gives 3
  np.argmax(Q[1]) gives 2
  np.argmax(Q[2]) gives 2
  np.argmax(Q[3]) gives 2
  
  ```
  
  All of the states should give argmax as 2 (which is actually the index[state] of the minimum value).
  
  Another example,
  
  when I increase steps to 1000 and episodes to 50,
  
  ```
  np.argmax(Q[0]) gives 3
  np.argmax(Q[1]) gives 0
  np.argmax(Q[2]) gives 1
  np.argmax(Q[3]) gives 2
  
  ```
  
  More, steps and episodes should assure convergence, but this is not visible.
  
  I need help where I am going wrong.
  
  PS: This little experiment is needed to make Q-learning applicable to a larger combinatorial problem. Unless I understand this, I don't think I will be able to do that right.
  Also, there is no terminal state because this is an optimization problem. (And I have heard that Q-learning doesn't necessarily needs a terminal state)
  
  **Tags:** reinforcement-learning, q-learning
  
  > **Comments:**
  > **username_1**: `for episode in range(episodes):` doesn't it should be `for steps in range(episodes)` ? Sorry, I'm a C++ guy, it's a bit daunting to me... :P  
  > **username_0**: @abhas_RewCie range() is like a vector of integers. `episodes` specify the stop value for generating the integers. `episode` is like a candidate element (i) of that vector. So, it will loosely translate as `for(int episode=0; episode<episodes.size();episode++)`  
  > **username_1**: if you don't mind writing the algorithm....  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2020-05-21. Score: 1
  
  If your intention is to learn make the agent learn which has the min arbitrary value, then you would need to modify your rewards a bit.
  
  The current reward structure provides the incentive to just move to a stage where it gets a reward.
  
  For example, if it is at state 0, it gets the same reward to go to either state 2 or state 3, since both of them have a higher inverse value.
  
  To make the agent learn to move to state 2, you would have to provide it with more incentives to go to state 2.
  
  ```
  def reward(s,a,s_dash):
      if s_dash == 2:
          return 5
      elif inverse_values_for_states[s]<inverse_values_for_states[s_dash]: 
          return 1
      elif inverse_values_for_states[s]>inverse_values_for_states[s_dash]:
          return -1
      else:
          return 0
  
  ```
  
  I tried using this and it converges to 2. This is a hard-coded version, but I guess you get the idea.
  
  > **Comments:**
  > **username_3**: It's worse than you suggest. The OP's reward structure encourages the smallest possible incremental improvement on each action, because then it is possible for it to receive maximum rewards before finishing. It is better to score $[1,1,1,-1,1,1,1,-1....]$ starting from the worst state than score $[1,0,0...]$ and this is shown by the OP's converged values.  
  
  ---
  
  