<jupyter_start><jupyter_text>Crossentropy methodThis notebook will teach you to solve reinforcement learning problems with crossentropy method.     """    The Taxi Problem    from "Hierarchical Reinforcement Learning with the MAXQ Value Function Decomposition"    by <NAME>    Description:    There are four designated locations in the grid world indicated by R(ed), B(lue), G(reen), and Y(ellow). When the episode starts, the taxi starts off at a random square and the passenger is at a random location. The taxi drive to the passenger's location, pick up the passenger, drive to the passenger's destination (another one of the four specified locations), and then drop off the passenger. Once the passenger is dropped off, the episode ends.    Observations:     There are 500 discrete states since there are 25 taxi positions, 5 possible locations of the passenger (including the case when the passenger is the taxi), and 4 destination locations.         Actions:     There are 6 discrete deterministic actions:    - 0: move south    - 1: move north    - 2: move east     - 3: move west     - 4: pickup passenger    - 5: dropoff passenger        Rewards:     There is a reward of -1 for each action and an additional reward of +20 for delievering the passenger. There is a reward of -10 for executing actions "pickup" and "dropoff" illegally.        Rendering:    - blue: passenger    - magenta: destination    - yellow: empty taxi    - green: full taxi    - other letters: locations    """<jupyter_code>import gym
import numpy as np, pandas as pd

env = gym.make("Taxi-v2")
env.reset()
env.render()
n_states = env.observation_space.n
n_actions = env.action_space.n

print("n_states=%i, n_actions=%i"%(n_states, n_actions))<jupyter_output>n_states=500, n_actions=6<jupyter_text>Create stochastic policyThis time our policy should be a probability distribution.```policy[s,a] = P(take action a | in state s)```Since we still use integer state and action representations, you can use a 2-dimensional array to represent the policy.Please initialize policy __uniformly__, that is, probabililities of all actions should be equal.<jupyter_code>policy = np.ones((n_states, n_actions)) / n_actions
assert type(policy) in (np.ndarray,np.matrix)
assert np.allclose(policy,1./n_actions)
assert np.allclose(np.sum(policy,axis=1), 1)<jupyter_output><empty_output><jupyter_text>Play the gameJust like before, but we also record all states and actions we took.<jupyter_code>def generate_session(policy,t_max=10**4):
    """
    Play game until end or for t_max ticks.
    :param policy: an array of shape [n_states,n_actions] with action probabilities
    :returns: list of states, list of actions and sum of rewards
    """
    states,actions = [],[]
    total_reward = 0.
    
    s = env.reset()
    
    for t in range(t_max):
        
        a = np.random.choice(6, p=policy[s])
        
        new_s, r, done, info = env.step(a)
        
        #Record state, action and add up reward to states,actions and total_reward accordingly. 
        states.append(s)
        actions.append(a)
        total_reward += r
        
        s = new_s
        if done:
            break
    return states, actions, total_reward
        
s,a,r = generate_session(policy)
assert type(s) == type(a) == list
assert len(s) == len(a)
assert type(r) in [float,np.float]
#let's see the initial reward distribution
import matplotlib.pyplot as plt
%matplotlib inline

sample_rewards = [generate_session(policy,t_max=1000)[-1] for _ in range(200)]

plt.hist(sample_rewards,bins=20);
plt.vlines([np.percentile(sample_rewards, 50)], [0], [100], label="50'th percentile", color='green')
plt.vlines([np.percentile(sample_rewards, 90)], [0], [100], label="90'th percentile", color='red')
plt.legend()<jupyter_output><empty_output><jupyter_text>Crossentropy method steps (2pts)<jupyter_code>np.where(sample_rewards>=np.percentile(sample_rewards, 50))
np.array(sample_rewards)[sample_rewards>=np.percentile(sample_rewards, 50)]
def select_elites(states_batch,actions_batch,rewards_batch,percentile=50):
    """
    Select states and actions from games that have rewards >= percentile
    :param states_batch: list of lists of states, states_batch[session_i][t]
    :param actions_batch: list of lists of actions, actions_batch[session_i][t]
    :param rewards_batch: list of rewards, rewards_batch[session_i][t]
    
    :returns: elite_states,elite_actions, both 1D lists of states and respective actions from elite sessions
    
    Please return elite states and actions in their original order 
    [i.e. sorted by session number and timestep within session]
    
    If you're confused, see examples below. Please don't assume that states are integers (they'll get different later).
    """
    states_batch = np.array(states_batch)
    actions_batch = np.array(actions_batch)
    rewards_batch = np.array(rewards_batch)
    
    reward_threshold = np.percentile(rewards_batch, percentile)
    elite_idx = rewards_batch >= reward_threshold
    
    elite_states = []
    elite_actions = []
    for e, a in zip(states_batch[elite_idx], actions_batch[elite_idx]):
        elite_states.extend(e)
        elite_actions.extend(a)
    
    return elite_states,elite_actions
    
states_batch = [
    [1,2,3],   #game1
    [4,2,0,2], #game2
    [3,1]      #game3
]

actions_batch = [
    [0,2,4],   #game1
    [3,2,0,1], #game2
    [3,3]      #game3
]
rewards_batch = [
    3,         #game1
    4,         #game2
    5,         #game3
]

test_result_0 = select_elites(states_batch, actions_batch, rewards_batch, percentile=0)
test_result_40 = select_elites(states_batch, actions_batch, rewards_batch, percentile=30)
test_result_90 = select_elites(states_batch, actions_batch, rewards_batch, percentile=90)
test_result_100 = select_elites(states_batch, actions_batch, rewards_batch, percentile=100)

assert np.all(test_result_0[0] == [1, 2, 3, 4, 2, 0, 2, 3, 1])  \
   and np.all(test_result_0[1] == [0, 2, 4, 3, 2, 0, 1, 3, 3]),\
        "For percentile 0 you should return all states and actions in chronological order"
assert np.all(test_result_40[0] == [4, 2, 0, 2, 3, 1]) and \
        np.all(test_result_40[1] ==[3, 2, 0, 1, 3, 3]),\
        "For percentile 30 you should only select states/actions from two first"
assert np.all(test_result_90[0] == [3,1]) and \
        np.all(test_result_90[1] == [3,3]),\
        "For percentile 90 you should only select states/actions from one game"
assert np.all(test_result_100[0] == [3,1]) and\
       np.all(test_result_100[1] == [3,3]),\
        "Please make sure you use >=, not >. Also double-check how you compute percentile."
print("Ok!")
def update_policy(elite_states,elite_actions):
    """
    Given old policy and a list of elite states/actions from select_elites,
    return new updated policy where each action probability is proportional to
    
    policy[s_i,a_i] ~ #[occurences of si and ai in elite states/actions]
    
    Don't forget to normalize policy to get valid probabilities and handle 0/0 case.
    In case you never visited a state, set probabilities for all actions to 1./n_actions
    
    :param elite_states: 1D list of states from elite sessions
    :param elite_actions: 1D list of actions from elite sessions
    
    """
    
    new_policy = np.zeros([n_states,n_actions])
    
    for state, action in zip(elite_states, elite_actions):
        new_policy[state][action] += 1
            
    #Don't forget to set 1/n_actions for all actions in unvisited states.
    for i, state in enumerate(new_policy):
        sum_ = np.sum(state)
        new_policy[i] = 1./n_actions if sum_==0 else state/np.sum(state)

    return new_policy

elite_states, elite_actions = ([1, 2, 3, 4, 2, 0, 2, 3, 1], [0, 2, 4, 3, 2, 0, 1, 3, 3])


new_policy = update_policy(elite_states,elite_actions)

assert np.isfinite(new_policy).all(), "Your new policy contains NaNs or +-inf. Make sure you don't divide by zero."
assert np.all(new_policy>=0), "Your new policy can't have negative action probabilities"
assert np.allclose(new_policy.sum(axis=-1),1), "Your new policy should be a valid probability distribution over actions"
reference_answer = np.array([
       [ 1.        ,  0.        ,  0.        ,  0.        ,  0.        ],
       [ 0.5       ,  0.        ,  0.        ,  0.5       ,  0.        ],
       [ 0.        ,  0.33333333,  0.66666667,  0.        ,  0.        ],
       [ 0.        ,  0.        ,  0.        ,  0.5       ,  0.5       ]])
assert np.allclose(new_policy[:4,:5],reference_answer)
print("Ok!")<jupyter_output>Ok!<jupyter_text>Training loopGenerate sessions, select N best and fit to those.<jupyter_code>from IPython.display import clear_output

def show_progress(batch_rewards, log, percentile, title, reward_range=[-990,+10]):
    """
    A convenience function that displays training progress. 
    No cool math here, just charts.
    """
    
    mean_reward, threshold = np.mean(batch_rewards), np.percentile(batch_rewards, percentile)
    log.append([mean_reward,threshold])

    clear_output(True)
    print("mean reward = %.3f, threshold=%.3f"%(mean_reward, threshold))
    plt.figure(figsize=[8,4])
    plt.subplot(1,2,1)
    plt.title(title)
    plt.plot(list(zip(*log))[0], label='Mean rewards')
    plt.plot(list(zip(*log))[1], label='Reward thresholds')
    plt.legend()
    plt.grid()
    
    plt.subplot(1,2,2)
    plt.title(title)
    plt.hist(batch_rewards,range=reward_range);
    plt.vlines([np.percentile(batch_rewards, percentile)], [0], [100], label="percentile", color='red')
    plt.legend()
    plt.grid()

    plt.show()

#reset policy just in case
policy = np.ones([n_states, n_actions]) / n_actions 
n_sessions = 250  #sample this many sessions
percentile = 50  #take this percent of session with highest rewards
learning_rate = 0.5  #add this thing to all counts for stability

log = []

for i in range(100):
    sessions = [generate_session(policy=policy) for _ in range(n_sessions)]
    
    batch_states,batch_actions,batch_rewards = zip(*sessions)

    elite_states, elite_actions = select_elites(states_batch=batch_states,
                                               actions_batch=batch_actions,
                                               rewards_batch=batch_rewards,
                                               percentile=percentile)
    
    new_policy = update_policy(elite_states=elite_states, elite_actions=elite_actions)
    
    # no smoothing
    policy = new_policy
    
    #display results on chart
    show_progress(batch_rewards, log, percentile, 'no smoothing')
n_sessions = 250  #sample this many sessions
percentile = 50  #take this percent of session with highest rewards
learning_rate = 0.5  #add this thing to all counts for stability

log = []

for i in range(100):
    sessions = [generate_session(policy=policy) for _ in range(n_sessions)]
    
    batch_states,batch_actions,batch_rewards = zip(*sessions)

    elite_states, elite_actions = select_elites(states_batch=batch_states,
                                               actions_batch=batch_actions,
                                               rewards_batch=batch_rewards,
                                               percentile=percentile)
    
    new_policy = update_policy(elite_states=elite_states, elite_actions=elite_actions)
    
    # smoothing
    policy = learning_rate * new_policy + (1-learning_rate) * policy
    
    # no smoothing
    policy = new_policy
    
    #display results on chart
    show_progress(batch_rewards, log, percentile, 'smoothing')<jupyter_output>mean reward = -85.056, threshold=5.500<jupyter_text>Reflecting on resultsYou may have noticed that the taxi problem quickly converges from <-1000 to a near-optimal score and then descends back into -50/-100. This is in part because the environment has some innate randomness. Namely, the starting points of passenger/driver change from episode to episode.In case CEM failed to learn how to win from one distinct starting point, it will siply discard it because no sessions from that starting point will make it into the "elites".To mitigate that problem, you can either reduce the threshold for elite sessions (duct tape way) or  change the way you evaluate strategy (theoretically correct way). You can first sample an action for every possible state and then evaluate this choice of actions by running _several_ games and averaging rewards.<jupyter_code>s = env.reset()

i = 0
done = False
while not done:
    i += 1
    a = np.random.choice(6, p=policy[s])

    new_s, r, done, info = env.step(a)
    # env.render()
    s = new_s
    env.render()
    if done: print('success!')<jupyter_output>+---------+
|R: | :[43m [0m:G|
| : : : : |
| : : : : |
| | : | : |
|[35mY[0m| : |[34;1mB[0m: |
+---------+
  (North)
+---------+
|R: | : :G|
| : : :[43m [0m: |
| : : : : |
| | : | : |
|[35mY[0m| : |[34;1mB[0m: |
+---------+
  (South)
+---------+
|R: | : :G|
| : : : : |
| : : :[43m [0m: |
| | : | : |
|[35mY[0m| : |[34;1mB[0m: |
+---------+
  (South)
+---------+
|R: | : :G|
| : : : : |
| : : : : |
| | : |[43m [0m: |
|[35mY[0m| : |[34;1mB[0m: |
+---------+
  (South)
+---------+
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|[35mY[0m| : |[34;1m[43mB[0m[0m: |
+---------+
  (South)
+---------+
|R: | : :G|
| : : : : |
| : : : : |
| | : | : |
|[35mY[0m| : |[42mB[0m: |
+---------+
  (Pickup)
+---------+
|R: | : :G|
| : : : : |
| : : : : |
| | : |[42m_[0m: |
|[35mY[0m| : |B: |
+---------+
  (North)
+---------+
|R: | : :G|
| : : : : |
| : : :[42m_[0m: |
| | : | : |
|[35mY[0m| : |B: |
+---------+
  (North)
+---------+
|R: | : :G|
| : : : : |
| : :[42m_[...]<jupyter_text>Submit to coursera<jupyter_code>from submit import submit_taxi
submit_taxi(generate_session, policy, '<EMAIL>', 'TQitKBqZmERMqY8e')<jupyter_output>Submitted to Coursera platform. See results on assignment page!
{'fraction_non_alphanumeric': 0.13145201929306746, 'fraction_numerical': 0.02778777625800878, 'mean_word_length': 3.1210323346188074, 'pattern_counts': {'":': 0, '<': 27, '<?xml version=': 0, '>': 33, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '347024', 'license': 'MIT', 'n_tokens_mistral': 4836, 'n_tokens_neox': 4505, 'n_words': 1283, 'path': 'week1_intro/crossentropy_method.ipynb', 'repo_name': 'syuntoku14/PracticalRL_coursera_pytorch', 'size': '13912'}