<jupyter_start><jupyter_text>On-policy learning and SARSA_This notebook builds upon `qlearning.ipynb`, or to be exact your implementation of QLearningAgent._The policy we're gonna use is epsilon-greedy policy, where agent takes optimal action with probability $(1-\epsilon)$, otherwise samples action at random. Note that agent __can__ occasionally sample optimal action during random sampling by pure chance.<jupyter_code>import sys, os
if 'google.colab' in sys.modules and not os.path.exists('.setup_complete'):
    !wget -q https://raw.githubusercontent.com/yandexdataschool/Practical_RL/spring20/setup_colab.sh -O- | bash

    !wget -q https://raw.githubusercontent.com/yandexdataschool/Practical_RL/coursera/grading.py -O ../grading.py
    !wget -q https://raw.githubusercontent.com/yandexdataschool/Practical_RL/coursera/week3_model_free/submit.py

    !touch .setup_complete

# This code creates a virtual display to draw game images on.
# It will have no effect if your machine has a monitor.
if type(os.environ.get("DISPLAY")) is not str or len(os.environ.get("DISPLAY")) == 0:
    !bash ../xvfb start
    os.environ['DISPLAY'] = ':1'
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline<jupyter_output><empty_output><jupyter_text>You can copy your `QLearningAgent` implementation from previous notebook.**Q-Leaning*** Sample  from environment* Compute $\hat{Q}(s,a) = r(s,a) + \gamma \max_{a_i \sim\pi(a|s')}Q(s',a_i)$ * Update $Q(s,a) \leftarrow (1-\alpha)*Q(s,a) + \alpha*\hat{Q}(s,a)$<jupyter_code>from collections import defaultdict
import random
import math
import numpy as np


class QLearningAgent:
    def __init__(self, alpha, epsilon, discount, get_legal_actions):
        """
        Q-Learning Agent
        based on https://inst.eecs.berkeley.edu/~cs188/sp19/projects.html
        Instance variables you have access to
          - self.epsilon (exploration prob)
          - self.alpha (learning rate)
          - self.discount (discount rate aka gamma)

        Functions you should use
          - self.get_legal_actions(state) {state, hashable -> list of actions, each is hashable}
            which returns legal actions for a state
          - self.get_qvalue(state,action)
            which returns Q(state,action)
          - self.set_qvalue(state,action,value)
            which sets Q(state,action) := value

        !!!Important!!!
        Note: please avoid using self._qValues directly. 
            There's a special self.get_qvalue/set_qvalue for that.
        """

        self.get_legal_actions = get_legal_actions
        self._qvalues = defaultdict(lambda: defaultdict(lambda: 0))
        self.alpha = alpha
        self.epsilon = epsilon
        self.discount = discount

    def get_qvalue(self, state, action):
        """ Returns Q(state,action) """
        return self._qvalues[state][action]

    def set_qvalue(self, state, action, value):
        """ Sets the Qvalue for [state,action] to the given value """
        self._qvalues[state][action] = value

    #---------------------START OF YOUR CODE---------------------#

    def get_value(self, state):
        """
        Compute your agent's estimate of V(s) using current q-values
        V(s) = max_over_action Q(state,action) over possible actions.
        Note: please take into account that q-values can be negative.
        """
        possible_actions = self.get_legal_actions(state)

        # If there are no legal actions, return 0.0
        if len(possible_actions) == 0:
            return 0.0

        # <YOUR CODE>
        value = max([self.get_qvalue(state,a) for a in possible_actions])

        return value

    def update(self, state, action, reward, next_state):
        """
        You should do your Q-Value update here:
           Q(s,a) := (1 - alpha) * Q(s,a) + alpha * (r + gamma * V(s'))
        """

        # agent parameters
        gamma = self.discount
        learning_rate = self.alpha

        # <YOUR CODE>
        qvalue = (1-learning_rate)*self.get_qvalue(state,action) + learning_rate*(reward+gamma*self.get_value(next_state))

        # self.set_qvalue(state, action, <YOUR CODE: Q-value> )
        self.set_qvalue(state, action, qvalue)

    def get_best_action(self, state):
        """
        Compute the best action to take in a state (using current q-values). 
        """
        possible_actions = self.get_legal_actions(state)

        # If there are no legal actions, return None
        if len(possible_actions) == 0:
            return None

        # <YOUR CODE>
        q_dict = {a: self.get_qvalue(state,a) for a in possible_actions}
    
        max_q = max(q_dict.values())
        best_actions = [action for action, q in q_dict.items() if q == max_q]
        best_action = random.choice(best_actions)

        return best_action

    def get_action(self, state):
        """
        Compute the action to take in the current state, including exploration.  
        With probability self.epsilon, we should take a random action.
            otherwise - the best policy action (self.getPolicy).

        Note: To pick randomly from a list, use random.choice(list). 
              To pick True or False with a given probablity, generate uniform number in [0, 1]
              and compare it with your probability
        """

        # Pick Action
        possible_actions = self.get_legal_actions(state)
        action = None

        # If there are no legal actions, return None
        if len(possible_actions) == 0:
            return None

        # agent parameters:
        epsilon = self.epsilon

        # <YOUR CODE>
        if random.random() < self.epsilon:
            chosen_action = random.choice(possible_actions)
        else:
            chosen_action = self.get_best_action(state)

        return chosen_action<jupyter_output><empty_output><jupyter_text>Now we gonna implement Expected Value SARSA on top of it.* Sample  from environment* Compute $\hat{Q}(s,a) = r(s,a) + \gamma\mathbb{E}_{a_i \sim\pi(a|s')}Q(s',a_i)$ with probability of $a_i \sim\pi(a|s')$ being $(1-\epsilon)$ optimal action and $\epsilon$ random action.* Update $Q(s,a) \leftarrow (1-\alpha)*Q(s,a) + \alpha*\hat{Q}(s,a)$<jupyter_code>class EVSarsaAgent(QLearningAgent):
    """ 
    An agent that changes some of q-learning functions to implement Expected Value SARSA. 
    Note: this demo assumes that your implementation of QLearningAgent.update uses get_value(next_state).
    If it doesn't, please add
        def update(self, state, action, reward, next_state):
            and implement it for Expected Value SARSA's V(s')
    """

    def get_value(self, state):
        """ 
        Returns Vpi for current state under epsilon-greedy policy:
          V_{pi}(s) = sum _{over a_i} {pi(a_i | s) * Q(s, a_i)}

        Hint: all other methods from QLearningAgent are still accessible.
        """
        epsilon = self.epsilon
        possible_actions = self.get_legal_actions(state)

        # If there are no legal actions, return 0.0
        if len(possible_actions) == 0:
            return 0.0

        # <YOUR CODE: see docstring>
        best_action = self.get_best_action(state)
        state_value = (1-epsilon)*self.get_qvalue(state,best_action)

        num_action = len(possible_actions)
        for action in possible_actions:
            state_value += epsilon/num_action*self.get_qvalue(state,action)

        return state_value<jupyter_output><empty_output><jupyter_text>Cliff WorldLet's now see how our algorithm compares against q-learning in case where we force agent to explore all the time.image by cs188<jupyter_code>import gym
import gym.envs.toy_text
env = gym.envs.toy_text.CliffWalkingEnv()
n_actions = env.action_space.n

print(env.__doc__)
# Our cliffworld has one difference from what's on the image: there is no wall.
# Agent can choose to go as close to the cliff as it wishes. x:start, T:exit, C:cliff, o: flat ground
env.render()
def play_and_train(env, agent, t_max=10**4):
    """This function should 
    - run a full game, actions given by agent.getAction(s)
    - train agent using agent.update(...) whenever possible
    - return total reward"""
    total_reward = 0.0
    s = env.reset()

    for t in range(t_max):
        a = agent.get_action(s)

        next_s, r, done, _ = env.step(a)
        agent.update(s, a, r, next_s)

        s = next_s
        total_reward += r
        if done:
            break

    return total_reward
agent_sarsa = EVSarsaAgent(alpha=0.25, epsilon=0.2, discount=0.99,
                           get_legal_actions=lambda s: range(n_actions))

agent_ql = QLearningAgent(alpha=0.25, epsilon=0.2, discount=0.99,
                          get_legal_actions=lambda s: range(n_actions))

# agent_sarsa.epsilon = 0
# agent_ql.epsilon = 0
from IPython.display import clear_output
import pandas as pd

def moving_average(x, span=100):
    return pd.DataFrame({'x': np.asarray(x)}).x.ewm(span=span).mean().values

rewards_sarsa, rewards_ql = [], []

for i in range(5000):
    rewards_sarsa.append(play_and_train(env, agent_sarsa))
    rewards_ql.append(play_and_train(env, agent_ql))
    
    # Note: agent.epsilon stays constant in the first half of epsiod
    if i > 5000/5:
        agent_sarsa.epsilon *= 0.9
        agent_ql.epsilon *= 0.9

    if i % 100 == 0:
        clear_output(True)
        print('EVSARSA mean reward =', np.mean(rewards_sarsa[-100:]))
        print('QLEARNING mean reward =', np.mean(rewards_ql[-100:]))
        plt.title("epsilon = %s" % agent_ql.epsilon)
        plt.plot(moving_average(rewards_sarsa), label='ev_sarsa')
        plt.plot(moving_average(rewards_ql), label='qlearning')
        plt.grid()
        plt.legend()
        plt.ylim(-500, 0)
        plt.show()<jupyter_output>EVSARSA mean reward = -17.0
QLEARNING mean reward = -13.0<jupyter_text>Let's now see what did the algorithms learn by visualizing their actions at every state.<jupyter_code>def draw_policy(env, agent):
    """ Prints CliffWalkingEnv policy with arrows. Hard-coded. """
    n_rows, n_cols = env._cliff.shape

    actions = '^>v<'

    for yi in range(n_rows):
        for xi in range(n_cols):
            if env._cliff[yi, xi]:
                print(" C ", end='')
            elif (yi * n_cols + xi) == env.start_state_index:
                print(" X ", end='')
            elif (yi * n_cols + xi) == n_rows * n_cols - 1:
                print(" T ", end='')
            else:
                print(" %s " %
                      actions[agent.get_best_action(yi * n_cols + xi)], end='')
        print()
print("Q-Learning")
draw_policy(env, agent_ql)

print("SARSA")
draw_policy(env, agent_sarsa)<jupyter_output>Q-Learning
 ^  <  >  v  >  >  v  >  >  >  >  v 
 v  >  v  v  v  >  v  v  v  v  v  v 
 >  >  >  >  >  >  >  >  >  >  >  v 
 X  C  C  C  C  C  C  C  C  C  C  T 
SARSA
 >  >  >  >  >  >  >  >  >  >  >  v 
 >  >  >  >  >  >  >  >  >  >  >  v 
 ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  >  v 
 X  C  C  C  C  C  C  C  C  C  C  T<jupyter_text>My NoteWith some experiment, I found the following:1.   With a **constant epsilon=0**, both agent achieved optimal reward of -13.2.   With a **constant epsilon=0.2**, both agent converged under 100 epsiodes. SARSA agent achieved reward about -25; while Q-learnign agent achieved about -128. Q-learning is walking next to the clift and might fall with random exploration. 3.   With a **decaying epsilon** (start at 0.2 and decay with 99.99%/epsiode after 1000th epsiode), the Q-learnign achieved optimal reward with no exploration; while SARSA agent is converging toward optimal policy but couldn't achieve it after 20000 epsiodes. SARSA eventually achieve -15. This is because walking next to clift is to hard to explore for SARSA after the first convergnece to the safer path. 4.   With a **faster decaying epsilon** (0.9 this case), the Q-learning agenet could still converge to optimal reward of -13; while the SARSA agent could only converge to -17, coresponding to walking farest from the clift.With a converged policy under exploration, the SARSA is hard to converge to optimal policy when there is no need for exploration anymore. It might be achieved by a super slow decaying epsilon, but will take a lot of epsiode in order to achieve optimal policy. **Exploration is always needed if the environment is not constant with respect to time!**  Submit to Coursera<jupyter_code>from submit import submit_sarsa
submit_sarsa(rewards_ql, rewards_sarsa, <EMAIL>, <TOKEN>)<jupyter_output><empty_output><jupyter_text>MoreHere are some of the things you can do if you feel like it:* Play with epsilon. See learned how policies change if you set epsilon to higher/lower values (e.g. 0.75).* Expected Value SASRSA for softmax policy:$$ \pi(a_i|s) = softmax({Q(s,a_i) \over \tau}) = {e ^ {Q(s,a_i)/ \tau}  \over {\sum_{a_j}  e ^{Q(s,a_j) / \tau }}} $$* Implement N-step algorithms and TD($\lambda$): see [Sutton's book](http://incompleteideas.net/book/bookdraft2018jan1.pdf) chapter 7 and chapter 12.* Use those algorithms to train on CartPole in previous / next assignment for this week.  Expected Value SASRSA for softmax policy$$ \pi(a_i|s) = softmax({Q(s,a_i) \over \tau}) = {e ^ {Q(s,a_i)/ \tau}  \over {\sum_{a_j}  e ^{Q(s,a_j) / \tau }}} $$* Sample  from environment* Compute $\hat{Q}(s,a) = r(s,a) + \gamma\mathbb{E}_{a_i \sim\pi(a|s')}Q(s',a_i)$ with a probability of {a_i \sim\pi(a|s')} being **softmax policy*** Update $Q(s,a) \leftarrow (1-\alpha)*Q(s,a) + \alpha*\hat{Q}(s,a)$<jupyter_code>class EVSoftmaxSarsaAgent(QLearningAgent):
    """ 
    An agent that changes some of q-learning functions to implement Expected Value SARSA. 
    Note: this demo assumes that your implementation of QLearningAgent.update uses get_value(next_state).
    If it doesn't, please add
        def update(self, state, action, reward, next_state):
            and implement it for Expected Value SARSA's V(s')
    """

    def get_value(self, state):
        """ 
        Returns Vpi for current state under epsilon-greedy policy:
          V_{pi}(s) = sum _{over a_i} {pi(a_i | s) * Q(s, a_i)}

        Hint: all other methods from QLearningAgent are still accessible.
        """
        epsilon = self.epsilon
        possible_actions = self.get_legal_actions(state)

        # If there are no legal actions, return 0.0
        if len(possible_actions) == 0:
            return 0.0

        # <YOUR CODE: see docstring>
        Qvalues = np.array([self.get_qvalue(state,action) for action in possible_actions])

        exp_sum = sum(np.exp(Qvalues))
        probs = [np.exp(q)/exp_sum for q in Qvalues]

        state_value = 0
        for idx, action in enumerate(possible_actions):
            state_value += probs[idx]*Qvalues[idx]

        return state_value
agent_sarsa = EVSarsaAgent(alpha=0.25, epsilon=0.2, discount=0.99,
                           get_legal_actions=lambda s: range(n_actions))

agent_ql = QLearningAgent(alpha=0.25, epsilon=0.2, discount=0.99,
                          get_legal_actions=lambda s: range(n_actions))

agent_softmax = EVSoftmaxSarsaAgent(alpha=0.25, epsilon=0.2, discount=0.99,
                          get_legal_actions=lambda s: range(n_actions))

# agent_sarsa.epsilon = 0
# agent_ql.epsilon = 0
from IPython.display import clear_output
import pandas as pd

def moving_average(x, span=100):
    return pd.DataFrame({'x': np.asarray(x)}).x.ewm(span=span).mean().values

rewards_sarsa, rewards_ql = [], []
rewards_softmax = []

for i in range(5000):
    rewards_sarsa.append(play_and_train(env, agent_sarsa))
    rewards_ql.append(play_and_train(env, agent_ql))
    rewards_softmax.append(play_and_train(env, agent_softmax))
    
    # Note: agent.epsilon stays constant in the first half of epsiod
    # if i > 5000/5:
    #     agent_sarsa.epsilon *= 0.9
    #     agent_ql.epsilon *= 0.9

    if i % 100 == 0:
        clear_output(True)
        print('EVSARSA mean reward =', np.mean(rewards_sarsa[-100:]))
        print('QLEARNING mean reward =', np.mean(rewards_ql[-100:]))
        print('SOFTMAX mean reward =', np.mean(rewards_softmax[-100:]))

        plt.title("epsilon = %s" % agent_ql.epsilon)
        plt.plot(moving_average(rewards_sarsa), label='ev_sarsa')
        plt.plot(moving_average(rewards_ql), label='qlearning')
        plt.plot(moving_average(rewards_softmax), label='ev_softmax')
        plt.grid()
        plt.legend()
        plt.ylim(-500, 0)
        plt.show()
print("Q-Learning")
draw_policy(env, agent_ql)

print("SARSA")
draw_policy(env, agent_sarsa)

print("Softmax-SARSA")
draw_policy(env, agent_softmax)<jupyter_output>Q-Learning
 v  >  v  >  >  >  v  >  v  v  v  v 
 >  v  >  v  >  v  v  v  >  >  >  v 
 >  >  >  >  >  >  >  >  >  >  >  v 
 X  C  C  C  C  C  C  C  C  C  C  T 
SARSA
 >  >  >  >  >  >  >  >  >  >  >  v 
 ^  ^  ^  >  >  >  >  >  >  >  >  v 
 ^  ^  ^  ^  ^  ^  ^  ^  ^  ^  >  v 
 X  C  C  C  C  C  C  C  C  C  C  T 
Softmax-SARSA
 >  >  >  >  >  >  >  >  v  v  v  v 
 >  >  >  >  >  >  >  >  >  >  v  v 
 >  >  >  >  >  >  >  >  >  >  >  v 
 X  C  C  C  C  C  C  C  C  C  C  T
{'fraction_non_alphanumeric': 0.11624633431085044, 'fraction_numerical': 0.012434017595307918, 'mean_word_length': 2.710772578890098, 'pattern_counts': {'":': 0, '<': 38, '<?xml version=': 0, '>': 153, 'https://': 4, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '419732', 'license': 'MIT', 'n_tokens_mistral': 5934, 'n_tokens_neox': 5601, 'n_words': 1598, 'path': 'Week3_Model Free Methods/sarsa.ipynb', 'repo_name': 'shih-chi-47/Practical_RL', 'size': '17050'}