<jupyter_start><jupyter_text>Every-visit MC algo<jupyter_code>def ev_mc_prediction(policy, env, num_episodes, discount_factor=1.0):
    """
    Monte Carlo prediction algorithm. Calculates the value function
    for a given policy using sampling.
    
    Args:
        policy: A function that maps an observation to action probabilities.
        env: OpenAI gym environment.
        num_episodes: Number of episodes to sample.
        discount_factor: Gamma discount factor.
    
    Returns:
        A dictionary that maps from state -> value.
        The state is a tuple and the value is a float.
    """

    # Keeps track of sum and count of returns for each state
    # to calculate an average. We could use an array to save all
    # returns (like in the book) but that's memory inefficient.
    returns_count = defaultdict(float)
    
    # The final value function
    V = defaultdict(float)
    
    # Implement this!
    
    for i in range(num_episodes):
        state = env.reset()
        episodes = list()
        while True:
            # On each step take action and save state with appropriate reward
            action = policy(state)
            new_state, reward, done, _ = env.step(action)
            episodes.append((state, reward))
            state = new_state
            if done:
                break
                
        gain = 0
        # Add discounted returns following all visited states
        for step, episode in enumerate(episodes[::-1]):
            state, reward = episode
            gain = gain * discount_factor + reward
            returns_count[state] += 1
            V[state] += (gain - V[state]) / returns_count[state]
    return V    
def sample_policy(observation):
    """
    A policy that sticks if the player score is > 20 and hits otherwise.
    """
    score, dealer_score, usable_ace = observation
    return 0 if score >= 20 else 1
V_10k = ev_mc_prediction(sample_policy, env, num_episodes=10000)
plotting.plot_value_function(V_10k, title="10,000 Steps Every visit")

V_500k = ev_mc_prediction(sample_policy, env, num_episodes=500000)
plotting.plot_value_function(V_500k, title="500,000 Steps Every visit")<jupyter_output><empty_output><jupyter_text>First-visit MC algo<jupyter_code>def fv_mc_prediction(policy, env, num_episodes, discount_factor=1.0):
    """
    Monte Carlo prediction algorithm. Calculates the value function
    for a given policy using sampling.
    
    Args:
        policy: A function that maps an observation to action probabilities.
        env: OpenAI gym environment.
        num_episodes: Number of episodes to sample.
        discount_factor: Gamma discount factor.
    
    Returns:
        A dictionary that maps from state -> value.
        The state is a tuple and the value is a float.
    """

    # Keeps track of count of returns for each state
    # to calculate an average. We could use an array to save all
    # returns (like in the book) but that's memory inefficient.
    returns_count = defaultdict(float)
    
    # The final value function
    V = defaultdict(float)
    
    # Implement this!
    
    for i in range(num_episodes):
        state = env.reset()
        episodes = list()
        observation_count = defaultdict(int)
        while True:
            # On each step take action and save state with appropriate reward
            action = policy(state)
            new_state, reward, done, _ = env.step(action)
            episodes.append((state, reward))
            # Count observations to determine first visit to the state
            observation_count[state] += 1
            state = new_state
            if done:
                break
        
        gain = 0
        # Add discounted returns following all visited states
        for step, episode in enumerate(episodes[::-1]):
            state, reward = episode
            gain = gain * discount_factor + reward
            # If current observation was visited first time, add the return following it
            observation_count[state] -= 1
            if observation_count[state] == 0:
                returns_count[state] += 1
                V[state] += (gain - V[state]) / returns_count[state]
    return V    
V_10k = fv_mc_prediction(sample_policy, env, num_episodes=10000)
plotting.plot_value_function(V_10k, title="10,000 Steps Every visit")

V_500k = fv_mc_prediction(sample_policy, env, num_episodes=500000)
plotting.plot_value_function(V_500k, title="500,000 Steps Every visit")<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.07301375943186862, 'fraction_numerical': 0.01841988459831336, 'mean_word_length': 2.4404580152671755, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 13, 'https://': 0, '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': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '622214', 'license': 'MIT', 'n_tokens_mistral': 1306, 'n_tokens_neox': 1242, 'n_words': 429, 'path': 'MC/MC Prediction.ipynb', 'repo_name': 'MChaus/reinforcement-learning', 'size': '4506'}