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

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.

  • $\begingroup$ 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? $\endgroup$ Apr 11 '21 at 11:20
  • $\begingroup$ 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) $\endgroup$
    – Kashan
    Apr 11 '21 at 11:33
  • $\begingroup$ 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. $\endgroup$
    – Kashan
    Apr 11 '21 at 11:35
  • $\begingroup$ 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? $\endgroup$ Apr 11 '21 at 11:49
  • $\begingroup$ 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). $\endgroup$
    – Kashan
    Apr 12 '21 at 2:36

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
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()
        _,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)):
    #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:
            elif 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;
        if e%100 == 0:
            print('Episode : {}, Episode reward: {}, Epsilon: {}'.format(e, ep_reward, epsilon))
        if epsilon >= min_epsilon:

plt.ylabel('episodic reward')
running_avg = plotRunningAverage(Running_reward, EPISODES, 50)
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))

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.