Applying Eligibility Traces to Q-Learning algorithm does not improve results (And might not function well)
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 &gt; 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)