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

Question

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.

Answer 1

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.