Why do my rewards fall using tabular Q-learning as I perform more episodes?

Using the tutorial from: SentDex - Python Programming I added Q Learning to my script that was previously just picking random actions. His script uses the MountainCar Environment so I had to amend it to the CartPole env I am using. Initially, the rewards seem sporadic but, after a while, they just drop off and oscillate between 0-10. Does anyone know why this is?

Learning_rate = 0.1
Discount_rate = 0.95
episodes = 200

# Exploration settings
epsilon = 1  # not a constant, qoing to be decayed
START_EPSILON_DECAYING = 1
END_EPSILON_DECAYING = episodes//2
epsilon_decay_value = epsilon/(END_EPSILON_DECAYING - START_EPSILON_DECAYING)

env = gym.make("CartPole-v0") #Create the environment. The name of the environments can be found @ https://gym.openai.com/envs/#classic_control
#Each environment has a number of possible actions. In this case there are two discrete actions, left or right

#Each environment has some integer characteristics of the state.
#In this case we have 4:

#env = gym.wrappers.Monitor(env, './', force=True)

DISCRETE_OS_SIZE = [20, 20, 20, 20]

discrete_os_win_size = (env.observation_space.high - env.observation_space.low)/ DISCRETE_OS_SIZE

def get_discrete_state(state):
discrete_state = (state - env.observation_space.low)/discrete_os_win_size
return tuple(discrete_state.astype(np.int))

q_table = np.random.uniform(low = -2, high = 0, size = (20, 20, 20, 20, env.action_space.n))

plt.figure() #Instantiate the plotting environment
rewards_list = [] #Create an empty list to add the rewards to which we will then plot
for i in range(episodes):
discrete_state = get_discrete_state(env.reset())
done = False
rewards = 0
frames = []

while not done:
#frames.append(env.render(mode = "rgb_array"))

if np.random.random() > epsilon:
# Get action from Q table
action = np.argmax(q_table[discrete_state])

else:
# Get random action
action = np.random.randint(0, env.action_space.n)

new_state, reward, done, info = env.step(action)

new_discrete_state = get_discrete_state(new_state)

# If simulation did not end yet after last step - update Q table
if not done:

# Maximum possible Q value in next step (for new state)
max_future_q = np.max(q_table[new_discrete_state])

# Current Q value (for current state and performed action)
current_q = q_table[discrete_state, action]

# And here's our equation for a new Q value for current state and action
new_q = (1 - Learning_rate) * current_q + Learning_rate * (reward + Discount_rate * max_future_q)

# Update Q table with new Q value
q_table[discrete_state, action] = new_q

else:
q_table[discrete_state + (action,)] = 0

discrete_state = new_discrete_state

rewards += reward
rewards_list.append(rewards)
#print("Episode:", i, "Rewards:", rewards)
#print("Observations:", obs)

# Decaying is being done every episode if episode number is within decaying range
if END_EPSILON_DECAYING >= i >= START_EPSILON_DECAYING:
epsilon -= epsilon_decay_value

plt.plot(rewards_list)
plt.show()
env.close()


It becomes even more pronounced when I increase episodes to 20,000 so I don't think it's related to not giving the model enough training time.

If I set START_EPSILON_DECAYING to say 200 then it only drops to < 10 rewards after episode 200 which made me think it was the epsilon that was causing the problem. However, if I remove the epsilon/exploratory then the rewards at every episode are worse as it gets stuck in picking the argmax value for each state.

• Note that our site focuses more on answering theoretical questions. Please, read our on-topic page: ai.stackexchange.com/help/on-topic. Your question could just be a bug in the code, so that would be considered off-topic. Nevertheless, given that this is related to RL, which is a very important topic in AI, then I will not close this post. – nbro Jun 14 '20 at 14:15
• The guys on Stack Overflow don't know the details of our scope. That's why I suggest you read our on-topic page. Your post is on-topic here. But if it turns out that your problem is just a programming bug, then that could be considered off-topic (but don't worry about that!). If you read our on-topic page, hopefully, this will become clearer. Please, let me know if our on-topic page is clear enough! – nbro Jun 14 '20 at 14:20
• @nbro: Looks like classic catastrophic forgetting, and I think we already have a Q&A for that that this is a duplicate for - I'm searching now – Neil Slater Jun 14 '20 at 14:21
• @nbro Thank you. I have looked at the on-topic page and see that it suggests: "General programming questions are off-topic. For example, if you have a question like "Why am I getting this exception?" So I agree this is probably more appropriate on SO. Should I delete the post here or post there also? I don't want to create too much clutter. – BlueTurtle Jun 14 '20 at 14:23
• @NeilSlater Many thanks. I am new(ish) to all of this so I may be wrong but given that I am using just a basic Q Table lookup rather than a DDQN then is the catastrophic forgetting applicable? I am now wondering if it's a numerical error somewhere that is getting propegated through over episodes and distorting my Q values. It seems strange that it starts off okay but then diminishes. Compared to that post which increases and then decreases. – BlueTurtle Jun 14 '20 at 14:32

The problem here is likely related to the state approximations you are using.

Unfortunately, OpenAI's gym does not always give reasonable bounds when using env.observation_space, and that seems to be the case for CartPole:

>>> env = gym.make('CartPole-v0')
>>> env.observation_space.high
array([4.8000002e+00, 3.4028235e+38, 4.1887903e-01, 3.4028235e+38],
dtype=float32)
>>> env.observation_space.low
array([-4.8000002e+00, -3.4028235e+38, -4.1887903e-01, -3.4028235e+38],
dtype=float32)


Processing this, similarly to your code:

>>> discrete_os_win_size = (env.observation_space.high - env.observation_space.low)/ DISCRETE_OS_SIZE
__main__:1: RuntimeWarning: overflow encountered in subtract
>>> discrete_os_win_size
array([0.48000002,        inf, 0.0418879 ,        inf])

>>> discrete_state = (state - env.observation_space.low)/discrete_os_win_size
>>> discrete_state
array([11.27318768,  0.        , 19.50682776,  0.        ])


That means that all the velocities will get squashed down to $$0$$ in your approximation. Your agent cannot tell the difference between a nearly static balancing position (generally the goal) and transitioning through it really fast - it will think that both are equally good. It is also not able to tell difference between moving towards balance point, or moving away from it.

I suggest you check for what reasonable bounds are on the space (a quick look suggests +/- 2.0 might be a reasonable starting point) and use that instead.

The approximation approach of discrete grid is also very crude, although it does allow you do use tabular approaches. If you want to stick with a linear system (and avoid trying neural networks and DQN) then the next step up would be some form of tile coding, which uses multiple offset grids to obtain smoother interpolation between states.

• This is fantastic thank you! It's not that I want to stick with a linear system I just want to tackle similar problems with various approaches to help me understand which approaches work best where, and more importantly why. From all of this I have learn that tabular approaches are not useful for continuous spaces. – BlueTurtle Jun 14 '20 at 15:21