# Most of state-action pairs remain unvisited in the q-table

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.

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 = np.linspace(-1.2, 0.6, NUMBER_OF_BINS)
bins = 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 = np.digitize(obs, bins)
states = np.digitize(obs, bins)
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()

• Could you please add: How have you discretised the state? What approach are you using for exploration? Jul 28 '20 at 8:37
• 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. Jul 28 '20 at 15:21
• 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 Jul 28 '20 at 16:16
• In fact this answer by me might answer your original question and this one: ai.stackexchange.com/questions/21872/… - it could be that you are hitting the same problem. Jul 28 '20 at 16:24
• 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) Jul 28 '20 at 20:18