Body: <p>In building my first Q-learning algorithm for OpenAI gym's CartPole problem, many of my states remain unvisited. I believe it is the reason that my agent does not learn.</p>
  <p>Can I be told of the reasons I can look into why that may happen? I have read and seen tutorials and I know a lot has already been done for this problem. My goal here is to learn and hence this simple implementation with Q-learning.</p>
  <p>PS. The specific question to my problem is asked <a href="https://ai.stackexchange.com/questions/22710/openai-gyms-cartpole-problem-system-does-not-learn?noredirect=1#comment34679_22710">here</a>.</p>
  <p>PSS. As an edit, I am inserting my whole code in the following.</p>
  <pre><code>import numpy as np
  import gym
  import matplotlib.pyplot as plt
  
  env = gym.make('MountainCar-v0')
  
  EPISODES = 5000
  LEARNING_RATE = 0.1
  SHOW_AFTER = 1500
  DISCOUNT_FACTOR = 0.95
  EPSILON = 0.1
  NUMBER_OF_BINS = 10
  OBSERVATION_SPACE = 2
  MAX_STATES = 100 # e.g. 23 means obs one is 2, obs two is 3
  
  '''This function breaks the continuous states into discrete form'''
  def digitize_states():
      bins = np.zeros((OBSERVATION_SPACE,NUMBER_OF_BINS))
      bins[0] = np.linspace(-1.2, 0.6, NUMBER_OF_BINS)
      bins[1] = np.linspace(-.07, 0.07, NUMBER_OF_BINS)
      return bins
  
  '''This function assign the observations into discrete bins using 
     digitize function and the bins that we created using digitize_states()
  '''
  def assign_obs_to_bins(obs, bins):
      states = np.zeros((OBSERVATION_SPACE))
      states[0] = np.digitize(obs[0], bins[0]) 
      states[1] = np.digitize(obs[1], bins[1]) 
      return states
  
  '''This function merely make the states in form of the strings so that we can
     later use those strings (i.e. number of states) as the KEYs in our q-table 
     dictionary.
  '''
  def get_all_states_as_strings():
      states = []
      for i in range(MAX_STATES):
          states.append(str(i).zfill(OBSERVATION_SPACE))
      return states
  
  '''Convert the current state into string so that it can be used as key for dictionary '''
  def current_state_to_string(state):
      current_state = ''.join(str(int(e)) for e in state)
      return current_state
  
  '''This function iniquation the q-table to zeros'''
  def initialize_q():
      states = get_all_states_as_strings()
      q = {}
      for state in states:
          q[state] = {}
          for action in range(env.action_space.n):
              q[state][action] = 0 
      return q
  
  def initialize_Q():
      Q = {}
  
      all_states = get_all_states_as_strings()
      for state in all_states:
          Q[state] = {}
          for action in range(env.action_space.n):
              Q[state][action] = np.random.uniform(-.5, 0.5, 1)
      return Q
  
  '''This function returns the maximum Q-value from Q-table'''
  def return_max_from_dict(dict_var, action = None):
      '''    Arguments
      # dict_var: Dictionary variable, which represent the q-table.
      
      # Return
      # max_key: Best Action
      # max_val: max q-value for the current state, taking best action
      '''
      if(action == None):
          max_val = float('-Inf')
          for key, val in dict_var.items():
              if val &gt; max_val:
                  max_val = val
                  max_key = key
          return max_key, max_val
      else:
          return dict_var[action]   
          
  
  '''Main code starts here'''
  
  bins = digitize_states()
  all_states = get_all_states_as_strings()
  
  q = initialize_Q()    
  
  Total_reward_matrix = []
  _testing_action_matrix = []
  _testing_state_matrix = [] 
  _testing_states = []
  _testing_random = 0
  _testing_greedy = 0
  
  for episode in range(EPISODES):
      
      done = False
      cnt = 0
      
      # Reset the observations -&gt; then assign them to bins
      obs = env.reset()
      
      if episode%SHOW_AFTER == 0:
          print(episode)
      
      total_reward = 0
      
      while not done:
          current_state = current_state_to_string(assign_obs_to_bins(obs, bins))
          _testing_state_matrix.append(int(current_state))
  
          if np.random.uniform() &lt; EPSILON:
              act = env.action_space.sample()
              best_q_value = return_max_from_dict(q[current_state], action = act)
              _testing_random+=1
          else:
              act, best_q_value = return_max_from_dict(q[current_state])
              _testing_greedy+=1
          
          obs, reward, done, _  = env.step(act)
          _testing_action_matrix.append(act)
          
          q[current_state][act] = (1-LEARNING_RATE)*q[current_state][act] + LEARNING_RATE * (reward + DISCOUNT_FACTOR * best_q_value)
          cnt+=1
          total_reward += reward
      
          if done and cnt &gt; 200:
              print(f'reached at episode: {episode} in count {cnt}') 
              Total_reward_matrix.append(total_reward)
          elif done:
  #             print('Failed to reach flag in episode ', episode)
              Total_reward_matrix.append(total_reward)
          
      
  env.close()
  </code></pre>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-28T08:37:20.650Z
Comments.Text: Could you please add: How have you discretised the state? What approach are you using for exploration?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-28T15:21:09.177Z
Comments.Text: I am using epsilon-greedy method. The states are divided into 10 bins (later I tried 100 bins as well) each. They are discretised using standard Pythong function with the help of number of bins.
Comments.UserDisplayName: SJa
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-28T16:16:39.093Z
Comments.Text: Thanks. I think we need more than that. When you say the states "are divided into 10 bins" I want to see in more detail how you are doing that - are there 10,000 states here (10 in each dimension of position and velocity for cart and pole?), and what are you treating as extremes for each one? IIRC CartPole reports incorrectly +-Inf for one or more of these dimensions which would be a problem if you use it as-is. Also, what values of epsilon are you using? Pleae use [edit] to add to your question
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-28T16:24:29.943Z
Comments.Text: In fact this answer by me might answer your original question and this one: https://ai.stackexchange.com/questions/21872/why-do-my-rewards-fall-using-tabular-q-learning-as-i-perform-more-episodes/21878#21878 - it  could be that you are hitting the same problem.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-28T20:18:32.603Z
Comments.Text: I have edited my question. the problem I am facing a similar problem with the CatPole as well. There is something very seriously wrong that I am doing, and I cannot put my finger on that. I have seen my code so many times that I have lost the count and could not find anything wrong in the logic and algorithm (following straight from the book of Sutton and Barta)
Comments.UserDisplayName: SJa
Tags: <reinforcement-learning><q-learning><open-ai><gym>
Title: Most of state-action pairs remain unvisited in the q-table
UserDisplayName: SJa
ThreadText: # Most of state-action pairs remain unvisited in the q-table
  
  (Asked by: username_0 on 2020-07-28)
  
  In building my first Q-learning algorithm for OpenAI gym's CartPole problem, many of my states remain unvisited. I believe it is the reason that my agent does not learn.
  
  Can I be told of the reasons I can look into why that may happen? I have read and seen tutorials and I know a lot has already been done for this problem. My goal here is to learn and hence this simple implementation with Q-learning.
  
  PS. The specific question to my problem is asked [here](https://ai.stackexchange.com/questions/22710/openai-gyms-cartpole-problem-system-does-not-learn?noredirect=1#comment34679_22710).
  
  PSS. As an edit, I am inserting my whole code in the following.
  
  ```
  import numpy as np
  import gym
  import matplotlib.pyplot as plt
  
  env = gym.make('MountainCar-v0')
  
  EPISODES = 5000
  LEARNING_RATE = 0.1
  SHOW_AFTER = 1500
  DISCOUNT_FACTOR = 0.95
  EPSILON = 0.1
  NUMBER_OF_BINS = 10
  OBSERVATION_SPACE = 2
  MAX_STATES = 100 # e.g. 23 means obs one is 2, obs two is 3
  
  '''This function breaks the continuous states into discrete form'''
  def digitize_states():
      bins = np.zeros((OBSERVATION_SPACE,NUMBER_OF_BINS))
      bins[0] = np.linspace(-1.2, 0.6, NUMBER_OF_BINS)
      bins[1] = np.linspace(-.07, 0.07, NUMBER_OF_BINS)
      return bins
  
  '''This function assign the observations into discrete bins using 
     digitize function and the bins that we created using digitize_states()
  '''
  def assign_obs_to_bins(obs, bins):
      states = np.zeros((OBSERVATION_SPACE))
      states[0] = np.digitize(obs[0], bins[0]) 
      states[1] = np.digitize(obs[1], bins[1]) 
      return states
  
  '''This function merely make the states in form of the strings so that we can
     later use those strings (i.e. number of states) as the KEYs in our q-table 
     dictionary.
  '''
  def get_all_states_as_strings():
      states = []
      for i in range(MAX_STATES):
          states.append(str(i).zfill(OBSERVATION_SPACE))
      return states
  
  '''Convert the current state into string so that it can be used as key for dictionary '''
  def current_state_to_string(state):
      current_state = ''.join(str(int(e)) for e in state)
      return current_state
  
  '''This function iniquation the q-table to zeros'''
  def initialize_q():
      states = get_all_states_as_strings()
      q = {}
      for state in states:
          q[state] = {}
          for action in range(env.action_space.n):
              q[state][action] = 0 
      return q
  
  def initialize_Q():
      Q = {}
  
      all_states = get_all_states_as_strings()
      for state in all_states:
          Q[state] = {}
          for action in range(env.action_space.n):
              Q[state][action] = np.random.uniform(-.5, 0.5, 1)
      return Q
  
  '''This function returns the maximum Q-value from Q-table'''
  def return_max_from_dict(dict_var, action = None):
      '''    Arguments
      # dict_var: Dictionary variable, which represent the q-table.
      
      # Return
      # max_key: Best Action
      # max_val: max q-value for the current state, taking best action
      '''
      if(action == None):
          max_val = float('-Inf')
          for key, val in dict_var.items():
              if val > max_val:
                  max_val = val
                  max_key = key
          return max_key, max_val
      else:
          return dict_var[action]   
          
  
  '''Main code starts here'''
  
  bins = digitize_states()
  all_states = get_all_states_as_strings()
  
  q = initialize_Q()    
  
  Total_reward_matrix = []
  _testing_action_matrix = []
  _testing_state_matrix = [] 
  _testing_states = []
  _testing_random = 0
  _testing_greedy = 0
  
  for episode in range(EPISODES):
      
      done = False
      cnt = 0
      
      # Reset the observations -> then assign them to bins
      obs = env.reset()
      
      if episode%SHOW_AFTER == 0:
          print(episode)
      
      total_reward = 0
      
      while not done:
          current_state = current_state_to_string(assign_obs_to_bins(obs, bins))
          _testing_state_matrix.append(int(current_state))
  
          if np.random.uniform() < EPSILON:
              act = env.action_space.sample()
              best_q_value = return_max_from_dict(q[current_state], action = act)
              _testing_random+=1
          else:
              act, best_q_value = return_max_from_dict(q[current_state])
              _testing_greedy+=1
          
          obs, reward, done, _  = env.step(act)
          _testing_action_matrix.append(act)
          
          q[current_state][act] = (1-LEARNING_RATE)*q[current_state][act] + LEARNING_RATE * (reward + DISCOUNT_FACTOR * best_q_value)
          cnt+=1
          total_reward += reward
      
          if done and cnt > 200:
              print(f'reached at episode: {episode} in count {cnt}') 
              Total_reward_matrix.append(total_reward)
          elif done:
  #             print('Failed to reach flag in episode ', episode)
              Total_reward_matrix.append(total_reward)
          
      
  env.close()
  
  ```
  
  **Tags:** reinforcement-learning, q-learning, open-ai, gym
  
  > **Comments:**
  > **username_1**: Could you please add: How have you discretised the state? What approach are you using for exploration?  
  > **username_0**: I am using epsilon-greedy method. The states are divided into 10 bins (later I tried 100 bins as well) each. They are discretised using standard Pythong function with the help of number of bins.  
  > **username_1**: Thanks. I think we need more than that. When you say the states "are divided into 10 bins" I want to see in more detail how you are doing that - are there 10,000 states here (10 in each dimension of position and velocity for cart and pole?), and what are you treating as extremes for each one? IIRC CartPole reports incorrectly +-Inf for one or more of these dimensions which would be a problem if you use it as-is. Also, what values of epsilon are you using? Pleae use [edit] to add to your question  
  > **username_1**: In fact this answer by me might answer your original question and this one: https://ai.stackexchange.com/questions/21872/why-do-my-rewards-fall-using-tabular-q-learning-as-i-perform-more-episodes/21878#21878 - it  could be that you are hitting the same problem.  
  > **username_0**: I have edited my question. the problem I am facing a similar problem with the CatPole as well. There is something very seriously wrong that I am doing, and I cannot put my finger on that. I have seen my code so many times that I have lost the count and could not find anything wrong in the logic and algorithm (following straight from the book of Sutton and Barta)  
  
  ---
  
  ## 0 answers
  
  