Answers.Body: <p>The code to my question is as below, for reference:</p>
  <pre><code>import gym
  import numpy as np
  import matplotlib.pyplot as plt
  
  # Discretize the contiuous space
  DISCRETE_POINTS = 50
  X_position = np.linspace(-2.4, 2.4, DISCRETE_POINTS)
  Velocity = np.linspace(-5, 5, DISCRETE_POINTS)
  Angle = np.linspace(-0.7295476, 0.7295476, DISCRETE_POINTS)
  Angular_vel = np.linspace(-5,5,DISCRETE_POINTS)
  
  # Fit the instantnous state into any discrete box
  def get_state(_state):
      
      X, X_bar, Angle_, Angle_bar = _state
      
      X = int(np.digitize(X, X_position))
      X_bar = int(np.digitize(X_bar, Velocity))
      Angle_ = int(np.digitize(Angle_, Angle))
      Angle_bar = int(np.digitize(Angle_bar, Angular_vel))
      
      return (X, X_bar, Angle_, Angle_bar)
  
  def epsilon_greedy_action(s, epsilon):
      
      '''   Input argument: state 's' tuple in the form (4,0,1,0)    '''
      # if np.random.uniform() &lt; epsilon:
      if np.random.random() &gt; epsilon:
          a = env.action_space.sample()
      else: 
          _,a = find_maxQ_value(s)
      
      return a
  
  def find_maxQ_value(state):
      '''
      Input argument: 
      state: should be a tuple of form (0,0,0,0) or (1,0,0,1) etc.
      
      Output argument:
      best_value: best q-value of the current state-action pair
      choosen_action: best action corresponding to current state. It depends on the best q-value
      '''
      
      for act_ in range(env.action_space.n):
          A = [Q[state,0], Q[state, 1]]
          best_value = np.max(A)
          choosen_action = np.argmax(A) 
      
      return best_value, choosen_action
   
  
  def plotRunningAverage(totalrewards, N, n_avg):
    
      running_avg = np.empty(N)
      for t in range(N):
          running_avg[t] = np.mean(totalrewards[max(0, t-N):(t+1)])
      return running_avg 
  
  
  if __name__ == '__main__':
  
      env = gym.make('CartPole-v0');
      
      EPISODES = 1000;
      no_actions = env.action_space.n
      
      # Hyper parameters
      alpha = 0.001 # Learning rate
      gamma = 0.99 #Discount Factor
      epsilon = 1 # For Epsilon-Greedy algorithm
      epsilon_decay_factor = 0.99;
      min_epsilon = 0.1;    
  
      states = []
      for i in range(len(X_position)):
          for j in range(len(Velocity)):
              for k in range(len(Angle)):
                  for l in range(len(Angular_vel)):
                      states.append((i,j,k,l))
                      
      #Initialize Q-table : 
      # 1. We make the Q-table in form of a dictionary
      # 2. We initialize Q-table values as zero in this
      Q = {}
      for s in states:
          for n_a in range(no_actions):
              Q[s, n_a] = 0
      
      Running_reward = [];
      l_action_cnt = 0;
      r_action_cnt = 0;
      wrong_action =0;
      
      #Q-Learning agent episodes    
      for e in range(EPISODES):
              
          cn_state = env.reset()
          ds_state = get_state(cn_state)
          
          done = False
          ep_reward = 0
          ep_len = 0
           
          while not done:
              
              action = epsilon_greedy_action(ds_state, epsilon)   
              if action == 0:
                  l_action_cnt+=1
              elif action == 1:
                  r_action_cnt+=1;
              else:
                  wrong_action+=1;
                  
              cn_next_state, reward , done , ep_len = env.step(action)
              ep_reward += reward
              
              ds_next_state = get_state(cn_next_state)
              
              # Update the Q-table based on the action
              Val_Q_bar, _ = find_maxQ_value(ds_next_state);
               
              Q[ds_state, action] = (1-alpha)*Q[ds_state, action] + alpha*(reward + gamma*Val_Q_bar)
              
              ds_state = ds_next_state;
           
          Running_reward.append(ep_reward)
          
          if e%100 == 0:
              print('Episode : {}, Episode reward: {}, Epsilon: {}'.format(e, ep_reward, epsilon))
                  
          if epsilon &gt;= min_epsilon:
              epsilon*=epsilon_decay_factor;
  
  plt.plot(Running_reward);
  plt.xlabel('episodes')
  plt.ylabel('episodic reward')
  plt.grid('ON') 
  running_avg = plotRunningAverage(Running_reward, EPISODES, 50)
  plt.plot(running_avg);
  plt.legend(['Episodic rewards', '50-Episode moving-average reward'])
  
  print('The ratio of left to right action is : {}'.format(l_action_cnt/r_action_cnt))
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-12T02:34:56.447Z
Answers.LastActivityDate: 2021-04-12T02:34:56.447Z
Answers.UserDisplayName: SJa
Body: <p>I have implemented the simple Q-Learning based solution for AI-gym's Cartpole-v0.</p>
  <p>However, despite changing hyper-parameters, and rechecking my code, I cannot get an average reward (N-running reward) of more than 30. My question is, is it not possible to get successful completion of Cartpole without using sophisticated algorithms such as Deep learning etc.?</p>
  <p>I am glad to share my code, but I am sure no one would have time to check it.</p>
  <p><a href="https://i.sstatic.net/5ILeF.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/5ILeF.png" alt="Sample reward outcomes" /></a></p>
  <p>PS. I know there are many implementations out there, but I have learned from them but I want to implement my own code for learning purpose and do not just want to copy-paste.</p>
  <p>PSS (Edit): I have added the code in the answer to this question for reference.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-11T11:20:46.530Z
Comments.Text: The problem has continuous states. Probably the most critical part of your implementation using tabular Q learning is how you have approximated these states into discrete values. Could you add an explanation for that?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-11T11:33:08.923Z
Comments.Text: I discretize them into 50 discrete blocks as below
  
  X_position = np.linspace(-2.4, 2.4, 50)
  Velocity = np.linspace(-5, 5, 50)
  Angle = np.linspace(-0.7295476, 0.7295476, 50)
  Angular_vel = np.linspace(-5,5,50)
Comments.UserDisplayName: SJa
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-11T11:35:53.997Z
Comments.Text: Then fitting any continuous state value into the respective discrete block isn't hard. For example if X is continuous state for location, then int(np.digitize(X, X_position)) can do the continuous to discrete conversion.
Comments.UserDisplayName: SJa
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-11T11:49:08.833Z
Comments.Text: OK, so you have done that for all 4 state variables, giving a discrete state space size of ~ 6 million? Is your choice of 50 a hyper-parameter that you can easily change in your code?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-04-12T02:36:54.410Z
Comments.Text: Yes. It's a hyper-parameter that can be changed easily. For reference, I have added the code in the answer ( adding code to the question would make it difficult to read and understand).
Comments.UserDisplayName: SJa
Tags: <q-learning><rewards><open-ai><gym>
Title: Is is not possible to achieve average reward of more than 20-40 with simple Q-Learning
UserDisplayName: SJa
ThreadText: # Is is not possible to achieve average reward of more than 20-40 with simple Q-Learning
  
  (Asked by: username_0 on 2021-04-11)
  
  I have implemented the simple Q-Learning based solution for AI-gym's Cartpole-v0.
  
  However, despite changing hyper-parameters, and rechecking my code, I cannot get an average reward (N-running reward) of more than 30. My question is, is it not possible to get successful completion of Cartpole without using sophisticated algorithms such as Deep learning etc.?
  
  I am glad to share my code, but I am sure no one would have time to check it.
  
  [![Sample reward outcomes](https://i.sstatic.net/5ILeF.png)](https://i.sstatic.net/5ILeF.png)
  
  PS. I know there are many implementations out there, but I have learned from them but I want to implement my own code for learning purpose and do not just want to copy-paste.
  
  PSS (Edit): I have added the code in the answer to this question for reference.
  
  **Tags:** q-learning, rewards, open-ai, gym
  
  > **Comments:**
  > **username_1**: The problem has continuous states. Probably the most critical part of your implementation using tabular Q learning is how you have approximated these states into discrete values. Could you add an explanation for that?  
  > **username_0**: I discretize them into 50 discrete blocks as below  X_position = np.linspace(-2.4, 2.4, 50) Velocity = np.linspace(-5, 5, 50) Angle = np.linspace(-0.7295476, 0.7295476, 50) Angular_vel = np.linspace(-5,5,50)  
  > **username_0**: Then fitting any continuous state value into the respective discrete block isn't hard. For example if X is continuous state for location, then int(np.digitize(X, X_position)) can do the continuous to discrete conversion.  
  > **username_1**: OK, so you have done that for all 4 state variables, giving a discrete state space size of ~ 6 million? Is your choice of 50 a hyper-parameter that you can easily change in your code?  
  > **username_0**: Yes. It's a hyper-parameter that can be changed easily. For reference, I have added the code in the answer ( adding code to the question would make it difficult to read and understand).  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2021-04-12. Score: -1
  
  The code to my question is as below, for reference:
  
  ```
  import gym
  import numpy as np
  import matplotlib.pyplot as plt
  
  # Discretize the contiuous space
  DISCRETE_POINTS = 50
  X_position = np.linspace(-2.4, 2.4, DISCRETE_POINTS)
  Velocity = np.linspace(-5, 5, DISCRETE_POINTS)
  Angle = np.linspace(-0.7295476, 0.7295476, DISCRETE_POINTS)
  Angular_vel = np.linspace(-5,5,DISCRETE_POINTS)
  
  # Fit the instantnous state into any discrete box
  def get_state(_state):
      
      X, X_bar, Angle_, Angle_bar = _state
      
      X = int(np.digitize(X, X_position))
      X_bar = int(np.digitize(X_bar, Velocity))
      Angle_ = int(np.digitize(Angle_, Angle))
      Angle_bar = int(np.digitize(Angle_bar, Angular_vel))
      
      return (X, X_bar, Angle_, Angle_bar)
  
  def epsilon_greedy_action(s, epsilon):
      
      '''   Input argument: state 's' tuple in the form (4,0,1,0)    '''
      # if np.random.uniform() < epsilon:
      if np.random.random() > epsilon:
          a = env.action_space.sample()
      else: 
          _,a = find_maxQ_value(s)
      
      return a
  
  def find_maxQ_value(state):
      '''
      Input argument: 
      state: should be a tuple of form (0,0,0,0) or (1,0,0,1) etc.
      
      Output argument:
      best_value: best q-value of the current state-action pair
      choosen_action: best action corresponding to current state. It depends on the best q-value
      '''
      
      for act_ in range(env.action_space.n):
          A = [Q[state,0], Q[state, 1]]
          best_value = np.max(A)
          choosen_action = np.argmax(A) 
      
      return best_value, choosen_action
   
  
  def plotRunningAverage(totalrewards, N, n_avg):
    
      running_avg = np.empty(N)
      for t in range(N):
          running_avg[t] = np.mean(totalrewards[max(0, t-N):(t+1)])
      return running_avg 
  
  if __name__ == '__main__':
  
      env = gym.make('CartPole-v0');
      
      EPISODES = 1000;
      no_actions = env.action_space.n
      
      # Hyper parameters
      alpha = 0.001 # Learning rate
      gamma = 0.99 #Discount Factor
      epsilon = 1 # For Epsilon-Greedy algorithm
      epsilon_decay_factor = 0.99;
      min_epsilon = 0.1;    
  
      states = []
      for i in range(len(X_position)):
          for j in range(len(Velocity)):
              for k in range(len(Angle)):
                  for l in range(len(Angular_vel)):
                      states.append((i,j,k,l))
                      
      #Initialize Q-table : 
      # 1. We make the Q-table in form of a dictionary
      # 2. We initialize Q-table values as zero in this
      Q = {}
      for s in states:
          for n_a in range(no_actions):
              Q[s, n_a] = 0
      
      Running_reward = [];
      l_action_cnt = 0;
      r_action_cnt = 0;
      wrong_action =0;
      
      #Q-Learning agent episodes    
      for e in range(EPISODES):
              
          cn_state = env.reset()
          ds_state = get_state(cn_state)
          
          done = False
          ep_reward = 0
          ep_len = 0
           
          while not done:
              
              action = epsilon_greedy_action(ds_state, epsilon)   
              if action == 0:
                  l_action_cnt+=1
              elif action == 1:
                  r_action_cnt+=1;
              else:
                  wrong_action+=1;
                  
              cn_next_state, reward , done , ep_len = env.step(action)
              ep_reward += reward
              
              ds_next_state = get_state(cn_next_state)
              
              # Update the Q-table based on the action
              Val_Q_bar, _ = find_maxQ_value(ds_next_state);
               
              Q[ds_state, action] = (1-alpha)*Q[ds_state, action] + alpha*(reward + gamma*Val_Q_bar)
              
              ds_state = ds_next_state;
           
          Running_reward.append(ep_reward)
          
          if e%100 == 0:
              print('Episode : {}, Episode reward: {}, Epsilon: {}'.format(e, ep_reward, epsilon))
                  
          if epsilon >= min_epsilon:
              epsilon*=epsilon_decay_factor;
  
  plt.plot(Running_reward);
  plt.xlabel('episodes')
  plt.ylabel('episodic reward')
  plt.grid('ON') 
  running_avg = plotRunningAverage(Running_reward, EPISODES, 50)
  plt.plot(running_avg);
  plt.legend(['Episodic rewards', '50-Episode moving-average reward'])
  
  print('The ratio of left to right action is : {}'.format(l_action_cnt/r_action_cnt))
  
  ```
  
  
  ---
  
  