# Applying Eligibility Traces to Q-Learning algorithm does not improve results (And might not function well)

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_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


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_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)