1
$\begingroup$

I am trying to apply Eligibility Traces to a currently working Q-Learning algorithm.

The reference code for the Q-Learning algorithm was taken from this great blog by DeepLizard, but does not include Eligibility Traces. Link to the code on Google Colab.

I wish to add the Eligibility Traces by implementing this pseud code:

Initialize Q(s,a) arbitrarily and e(s,a) = 0, for all s,a
Repeat (for each episode):
    Initialize s,a
    Repeat (for each step of episode):
        Take action a, observe r,s’
        Choose a’ from s’ using policy derived from Q (e.g., ϵ-greedy)
        δ ← r + γ Q(s’,a’) – Q(s,a)
        e(s,a) ← e(s,a) + 1
        For all s,a:
            Q(s,a) ← Q(s,a) + α δ e(s,a)
            e(s,a) ← γ λ e(s,a)
        s ← s’ ; a ← a’
    until s is terminal

Taken from HERE

This is my code as I have implemented the pseudo-code - Link

The part that needs to be improved is here:

#Q learning algorithem
for episode in range(num_episodes):
  state = env.reset()
  et_table = np.zeros((state_space_size,action_space_size))
  done = False
  reward_current_episode = 0

  for steps in range(max_steps_per_episode):
    #Exploration-Explotation trade-off
    exploration_rate_thresh = random.uniform(0,1)
    if exploration_rate_thresh > exploration_rate:
      action = np.argmax(q_table[state,:])
    else:
      action = env.action_space.sample()

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

    #Update Q-table and Eligibility table
    delta = reward + discount_rate * np.max(q_table[new_state,:]) - q_table[state,action]
    et_table[state, action] = et_table[state, action] + 1

    for update_state in range(state_space_size):
      for update_action in range(action_space_size):
        q_table[update_state, update_action] = q_table[update_state, update_action] + learning_rate * delta * et_table[update_state, update_action]
        et_table[update_state, update_action] = discount_rate * gamma * et_table[update_state, update_action]

    state = new_state
    reward_current_episode = reward

    if done==True:
      break

  #Exploration rate decay
  exploration_rate = min_exploration_rate + (max_exploration_rate - min_exploration_rate) * np.exp(-exploration_decay_rate*episode)

  rewards_all_episodes.append(reward_current_episode)

For a while, I was getting pure results (avg. rewards for 1000 episodes were around 0.14 while the original NON-ET algorithm was averaging 0.69 on the last 1000 episodes), but now I get these errors:

/usr/local/lib/python3.6/dist-packages/ipykernel_launcher.py:27: RuntimeWarning: overflow encountered in double_scalars
/usr/local/lib/python3.6/dist-packages/ipykernel_launcher.py:22: RuntimeWarning: invalid value encountered in double_scalars
$\endgroup$
0
$\begingroup$

The thing is, that while I was posting the question, I tried to tweak with the parameters and it seems that my discount rate (set for 0.99) was causing these errors.

Also - it seems that the is_slippery argument passed to the environment (True - the agent's action will be fulfilled 33% of the times, the rest of the times will be in a random direction, False - the agent's action will be fulfilled 100% of the times) is crucial for Eligibility Traces. The results improve from 0.39 to 0.993. My assumption is that the randomness of the "Slippery" part of the environment is crucially hurting the Eligibility Traces due to the fact that it is relying on the actions that were taken (and assuming they were fulfilled and not randomly changed).

After changing it to 0.9 I receive these results:

*** Average award per 1000 episodes ***
1000 :  0.2640000000000002
2000 :  0.7560000000000006
3000 :  0.9140000000000007
4000 :  0.9600000000000007
5000 :  0.9820000000000008
6000 :  0.9870000000000008
7000 :  0.9860000000000008
8000 :  0.9830000000000008
9000 :  0.9930000000000008
10000 :  0.9930000000000008


******* Q-Table *******

[[0.53144572 0.59049007 0.59046218 0.53144103]
 [0.53292711 0.         0.65610941 0.5864814 ]
 [0.58892359 0.729037   0.59954581 0.6546992 ]
 [0.65324248 0.         0.53612877 0.55540024]
 [0.59049001 0.65610007 0.         0.53143728]
 [0.         0.         0.         0.        ]
 [0.         0.8099945  0.         0.65015572]
 [0.         0.         0.         0.        ]
 [0.65610004 0.         0.72900006 0.59049002]
 [0.65610024 0.81       0.80996651 0.        ]
 [0.73156036 0.9        0.         0.72830918]
 [0.         0.         0.         0.        ]
 [0.         0.         0.         0.        ]
 [0.         0.8100008  0.9        0.72900011]
 [0.81000015 0.89999998 1.         0.80998688]
 [0.         0.         0.         0.        ]]

Comparing it to the original !-Learning algorithm by DeepLizard (LINK):

*** Average award per 1000 episodes ***
1000 :  0.22900000000000018
2000 :  0.7250000000000005
3000 :  0.8990000000000007
4000 :  0.9610000000000007
5000 :  0.9860000000000008
6000 :  0.9900000000000008
7000 :  0.9870000000000008
8000 :  0.9970000000000008
9000 :  0.9870000000000008
10000 :  0.9890000000000008


******* Q-Table *******

[[0.94148015 0.95099005 0.93206533 0.94148015]
 [0.94148015 0.         0.71778349 0.84678222]
 [0.88367728 0.43945604 0.0084652  0.27374571]
 [0.15097126 0.         0.         0.        ]
 [0.95099005 0.96059601 0.         0.94148015]
 [0.         0.         0.         0.        ]
 [0.         0.98009092 0.         0.36957636]
 [0.         0.         0.         0.        ]
 [0.96059599 0.         0.970299   0.95099004]
 [0.96059598 0.98009932 0.9801     0.        ]
 [0.97029894 0.99       0.         0.97021962]
 [0.         0.         0.         0.        ]
 [0.         0.         0.         0.        ]
 [0.         0.89329522 0.99       0.91080933]
 [0.98009934 0.98999961 1.         0.98009962]
 [0.         0.         0.         0.        ]]

We see a bit better results (we can see that on the 10K episode our agent is making the right path at 0.993% of the times, in appose to 0.989% in the original algorithm).

The bottom line is that the Eligibility Traces implementation can be done using these formulas:

a. create the et_table:

et_table = np.zeros((state_space_size,action_space_size))

b. Set gamma for the decaying of the Eligibility Traces:

gamma = 0.9

c. At each step - apply these calculations:

#Update Q-table and Eligibility table
    delta = reward + discount_rate * np.max(q_table[new_state,:]) - q_table[state,action]
    et_table[state, action] = et_table[state, action] + 1

    for update_state in range(state_space_size):
      for update_action in range(action_space_size):
        q_table[update_state, update_action] = q_table[update_state, update_action] + learning_rate * delta * et_table[update_state, update_action]
        et_table[update_state, update_action] = discount_rate * gamma * et_table[update_state, update_action]

d. After each episode - reset the et_table to zeros.

Full code can be found here:

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

env = gym.make("FrozenLake-v0", is_slippery=False)

action_space_size = env.action_space.n
state_space_size = env.observation_space.n

q_table = np.zeros((state_space_size,action_space_size))
et_table = np.zeros((state_space_size,action_space_size))
print("Q Table:\n", q_table)
print("Eligibility Traces:\n", et_table)

num_episodes = 10000
max_steps_per_episode = 100

learning_rate = 0.1
discount_rate = 0.9
gamma = 0.9

exploration_rate = 1
max_exploration_rate = 1
min_exploration_rate = 0.01
exploration_decay_rate = 0.001

rewards_all_episodes = []
q_table = np.zeros((state_space_size,action_space_size))

#Q learning algorithem
for episode in range(num_episodes):
  state = env.reset()
  et_table = np.zeros((state_space_size,action_space_size))
  done = False
  reward_current_episode = 0

  for steps in range(max_steps_per_episode):
    #Exploration-Explotation trade-off
    exploration_rate_thresh = random.uniform(0,1)
    if exploration_rate_thresh > exploration_rate:
      action = np.argmax(q_table[state,:])
    else:
      action = env.action_space.sample()

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

    #Update Q-table and Eligibility table
    delta = reward + discount_rate * np.max(q_table[new_state,:]) - q_table[state,action]
    et_table[state, action] = et_table[state, action] + 1

    for update_state in range(state_space_size):
      for update_action in range(action_space_size):
        q_table[update_state, update_action] = q_table[update_state, update_action] + learning_rate * delta * et_table[update_state, update_action]
        et_table[update_state, update_action] = discount_rate * gamma * et_table[update_state, update_action]

    state = new_state
    reward_current_episode = reward

    if done==True:
      break

  #Exploration rate decay
  exploration_rate = min_exploration_rate + (max_exploration_rate - min_exploration_rate) * np.exp(-exploration_decay_rate*episode)

  rewards_all_episodes.append(reward_current_episode)

#Print average reward per thousend episodes
reward_per_thousend_episodes = np.split(np.array(rewards_all_episodes),num_episodes/1000)
count = 1000
print("*** Average award per 1000 episodes ***")
for r in reward_per_thousend_episodes:
  print(count, ": ", str(sum(r/1000)))
  count+=1000

#Print Q-Table
print("\n\n******* Q-Table *******\n")
print(q_table)

print("\n\n******* ET-Table *******\n")
print(et_table)
$\endgroup$

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.