PNS

MAM5-INUM - Commande

TP 4

Q-Learning: Taxi

Credits: @felipelodur

This notebook presents an implementation of the Q-learning algorithm and applies it to the Taxi problem in order to obtain the optimal Q-table values for the problem.

Dependencies

from IPython.display import clear_output
import numpy as np
import random
import time
import gym

Envinroment: Taxi-v3

This task was introduced in Dietterich2000 to illustrate some issues in hierarchical reinforcement learning. There are 4 locations (labeled by different letters) and your job is to pick up the passenger at one location and drop him off in another. You receive +20 points for a successful dropoff, and lose 1 point for every timestep it takes. There is also a 10 point penalty for illegal pick-up and drop-off actions.

env = gym.make("Taxi-v3") # Create environment
env.render() # Show it
+---------+
|R: | : :G|
| : | : : |
| : : : : |
| | : | : |
|Y| : |B: |
+---------+

Q-table

In Q-learning the goal is to learn a policy that will tell an agent which action to take under each possible state. The Q-table is responsible to store score values for each (state, action) pair. These values can be initialized with zeros or randomly, and them they are updated as you perform exploration in your problem domain (which helps to discover which actions leads to a better stream of rewards)

# Number of possible actions
action_size = env.action_space.n 
print("Action size ", action_size) 

# Number of possible states
state_size = env.observation_space.n 
print("State size ", state_size)
Action size  6
State size  500
qtable = np.zeros((state_size, action_size))
print(qtable)
[[0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0.]
 ...
 [0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0.]
 [0. 0. 0. 0. 0. 0.]]

Hyper-parameters

episodes = 30000            # Total episodes
max_steps = 1000            # Max steps per episode
lr = 0.3                    # Learning rate
decay_fac = 0.00001         # Decay learning rate each iteration
gamma = 0.90                # Discounting rate - later rewards impact less

Exploration (Q-learning)

Since the goal here is to learn the optimal q-table, that is, best policy for each (state,action) pair: we need to perform exploration only. If the goal was to learn and solve the environment as quickly as possible, it would be necessary to implement an exploration-exploitation strategy. This kind of strategy would not work for this goal since we want to discover the optimal values for states that would not often/never be visited via the exploration-exploitation strategy.

The exploration strategy here implemented is straightforward: for each state we get to, take an action randomly. The randomness "guarantees" that we are going to visit each state action pair eventually.

for episode in range(episodes):
    
    state = env.reset() # Reset the environment
    done = False        # Are we done with the environment
    lr -= decay_fac     # Decaying learning rate
    step = 0
    
    if lr <= 0: # Nothing more to learn?
        break
        
    for step in range(max_steps):
        
        # Randomly Choose an Action
        action = env.action_space.sample()
        
        # Take the action -> observe new state and reward
        new_state, reward, done, info = env.step(action)
        
        # Update qtable values
        if done == True: # If last, do not count future accumulated reward
            qtable[state, action] = qtable[state, action]+lr*(reward+gamma*0-qtable[state,action])
            break
        else: # Consider accumulated reward of best decision stream
            qtable[state, action] = qtable[state,action] # UPDATE
        # moving states
        state = new_state
        
    episode += 1
    
    if (episode % 3000 == 0):
        print('episode = ', episode)
        print('learning rate = ', lr)
        print('-----------')
episode =  3000
learning rate =  0.26999999999997
-----------
episode =  6000
learning rate =  0.23999999999993998
-----------
episode =  9000
learning rate =  0.20999999999990998
-----------
episode =  12000
learning rate =  0.17999999999987998
-----------
episode =  15000
learning rate =  0.14999999999984998
-----------
episode =  18000
learning rate =  0.11999999999982693
-----------
episode =  21000
learning rate =  0.08999999999983856
-----------
episode =  24000
learning rate =  0.059999999999848445
-----------
episode =  27000
learning rate =  0.029999999999839697
-----------

Using Q-table

Now that we have the optimal values in the Q-table, we can use it to see our agent taking the best actions in this setting. You can re-run the code below to see it solving different environments.

# New environment
state = env.reset()
env.render()
done = False
total_reward = 0

while(done == False):
    action = 0 # UPDATE - Choose best action (Q-table)
    state, reward, done, info = env.step(action) # Take action
    total_reward += reward  # Sum of rewards
    
    # Display it
    time.sleep(0.5)
    clear_output(wait=True)
    env.render()
    print('Episode Reward = ', total_reward)
+---------+
|R: | : :G|
| : | : : |
| : : : : |
| | : | : |
|Y| : |B: |
+---------+
  (South)
Episode Reward =  -200