Answers.Body: <p>The thing is, that while I was posting the question, I tried to tweak with the parameters and it seems that my <code>discount rate</code> (set for 0.99) was causing these errors.</p>
  
  <p>Also - it seems that the <code>is_slippery</code> 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 <code>Eligibility Traces</code>. 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).</p>
  
  <p>After changing it to 0.9 I receive these results:</p>
  
  <pre><code>*** 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.        ]]
  </code></pre>
  
  <p>Comparing it to the original !-Learning algorithm by DeepLizard (<a href="https://deeplizard.com/learn/video/HGeI30uATws" rel="nofollow noreferrer">LINK</a>):</p>
  
  <pre><code>*** 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.        ]]
  </code></pre>
  
  <p>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).</p>
  
  <p>The bottom line is that the <code>Eligibility Traces</code> implementation can be done using these formulas:</p>
  
  <p>a. create the et_table:</p>
  
  <pre><code>et_table = np.zeros((state_space_size,action_space_size))
  </code></pre>
  
  <p>b. Set gamma for the decaying of the Eligibility Traces:</p>
  
  <pre><code>gamma = 0.9
  </code></pre>
  
  <p>c. At each step - apply these calculations:</p>
  
  <pre><code>#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]
  </code></pre>
  
  <p>d. After each episode - reset the et_table to zeros.</p>
  
  <p>Full code can be found here:</p>
  
  <pre><code>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)
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-05-02T20:35:08.377Z
Answers.LastActivityDate: 2020-05-02T20:35:08.377Z
Answers.UserDisplayName: Sahar Attia
Body: <p>I am trying to apply <code>Eligibility Traces</code> to a currently working Q-Learning algorithm.</p>
  
  <p>The reference code for the Q-Learning algorithm was taken from <a href="https://deeplizard.com/learn/video/HGeI30uATws" rel="nofollow noreferrer">this</a> great blog by DeepLizard, but does not include <code>Eligibility Traces</code>. <a href="https://colab.research.google.com/drive/1CHRhxjW4XejFy-Ae8OAKyxd8se_rcx74" rel="nofollow noreferrer">Link to the code</a> on Google Colab.</p>
  
  <p>I wish to add the <code>Eligibility Traces</code> by implementing this pseud code:</p>
  
  <pre><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
  </code></pre>
  
  <p>Taken from <a href="https://github.com/Hysperr/gridworld" rel="nofollow noreferrer">HERE</a></p>
  
  <p>This is my code as I have implemented the pseudo-code - <a href="https://colab.research.google.com/drive/1inWv4TUB6b81o0PShb1LDWYwz9pQS0Jf" rel="nofollow noreferrer">Link</a></p>
  
  <p>The part that needs to be improved is here:</p>
  
  <pre><code>#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)
  </code></pre>
  
  <p>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:</p>
  
  <pre><code>/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
  </code></pre>
  
Tags: <reinforcement-learning><q-learning><unsupervised-learning><eligibility-traces>
Title: Applying Eligibility Traces to Q-Learning algorithm does not improve results (And might not function well)
UserDisplayName: Sahar Attia
ThreadText: # Applying Eligibility Traces to Q-Learning algorithm does not improve results (And might not function well)
  
  (Asked by: username_0 on 2020-05-02)
  
  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](https://deeplizard.com/learn/video/HGeI30uATws) great blog by DeepLizard, but does not include `Eligibility Traces`. [Link to the code](https://colab.research.google.com/drive/1CHRhxjW4XejFy-Ae8OAKyxd8se_rcx74) 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](https://github.com/Hysperr/gridworld)
  
  This is my code as I have implemented the pseudo-code - [Link](https://colab.research.google.com/drive/1inWv4TUB6b81o0PShb1LDWYwz9pQS0Jf)
  
  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
  
  ```
  
  **Tags:** reinforcement-learning, q-learning, unsupervised-learning, eligibility-traces
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2020-05-02. Score: 1 | Accepted answer
  
  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](https://deeplizard.com/learn/video/HGeI30uATws)):
  
  ```
  *** 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)
  
  ```
  
  
  ---
  
  