<jupyter_start><jupyter_text>Dynamic programming solutions to student toy example: policy evaluation and value iterationImplementation of policy evaluation and value iteration algorithms are copied directly from [<NAME>](https://github.com/dennybritz/reinforcement-learning/blob/master/DP), with very minor modifications for compatibility with the `StudentEnv` class.  The student example itself is taken from <NAME>'s lecture 2 [notes](http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/MDP.pdf) on RL.<jupyter_code>import numpy as np
import matplotlib.pyplot as plt

import sys
if "./" not in sys.path:
    sys.path.append("./")
from discrete_limit_env import StudentEnv

%matplotlib inline<jupyter_output><empty_output><jupyter_text>The student MDP:![image](student_mdp.png) Map integers used in the environment for states/actions to names for pretty printing<jupyter_code># mapping from integer to state names
obs = {0: 'FACEBOOK', 1: 'CLASS1', 2: 'CLASS2', 3: 'CLASS3', 4: 'SLEEP'}

# allowed actions per state 
actions_for_obs = {
    0: {0: 'facebook', 1: 'quit'},
    1: {0: 'facebook', 1: 'study'},
    2: {0: 'sleep', 1: 'study'},
    3: {0: 'pub', 1: 'study'},
    4: {0: 'sleep'}
}
# Create an instance of the student environment
env = StudentEnv()<jupyter_output><empty_output><jupyter_text>Policy evaluationEvaluate the value function for a given policy.<jupyter_code># Random policy: agent chooses action randomly in each state
random_policy = dict()
for s, actions in actions_for_obs.items():
    n_actions = len(actions)
    random_policy[s] = np.ones(n_actions) / n_actions
    # equivalent to pi(a|s)=0.5 for all states except the terminal sleep state
    
print(random_policy)
#Copied from https://github.com/dennybritz/reinforcement-learning/blob/master/DP/Value%20Iteration%20Solution.ipynb
# note: no modifications needed for use with the DiscreteLimitActionsEnv.

def policy_eval(policy, env, discount_factor=1.0, theta=0.00001):
    """
    Evaluate a policy given an environment and a full description of the environment's dynamics.
    
    Args:
        policy: [S, A] shaped matrix representing the policy.
        env: OpenAI env. env.P represents the transition probabilities of the environment.
            env.P[s][a] is a list of transition tuples (prob, next_state, reward, done).
            env.nS is a number of states in the environment. 
            env.vA is a vector of the number of actions per state in the environment.
        theta: We stop evaluation once our value function change is less than theta for all states.
        discount_factor: Gamma discount factor.
    
    Returns:
        Vector of length env.nS representing the value function.
    """
    # Start with a random (all 0) value function
    V = np.zeros(env.nS)
    while True:
        delta = 0
        # For each state, perform a "full backup"
        for s in range(env.nS):
            v = 0
            # Look at the possible next actions
            for a, action_prob in enumerate(policy[s]):
                # For each action, look at the possible next states...
                for  prob, next_state, reward, done in env.P[s][a]:
                    # Calculate the expected value. Ref: Sutton book eq. 4.6.
                    v += action_prob * prob * (reward + discount_factor * V[next_state])
            # How much our value function changed (across any states)
            delta = max(delta, np.abs(v - V[s]))
            V[s] = v
        # Stop evaluating once our value function change is below a threshold
        if delta < theta:
            break
    return np.array(V)
value_fxn = policy_eval(random_policy, env)
for s, value in enumerate(value_fxn):
    print(f"optimal state-value in state {obs[s]}: ", round(value,1))<jupyter_output>optimal state-value in state FACEBOOK:  -2.3
optimal state-value in state CLASS1:  -1.3
optimal state-value in state CLASS2:  2.7
optimal state-value in state CLASS3:  7.4
optimal state-value in state SLEEP:  0.0<jupyter_text>![image](student_mdp_values_random_policy.png)  Value iterationSimultaneously solve for the optimal value function and optimal policy.<jupyter_code># Copied from https://github.com/dennybritz/reinforcement-learning/blob/master/DP/Value%20Iteration%20Solution.ipynb
# with slight alterations for compatibility with the action_space in DiscreteLimitActionsEnv.

def value_iteration(env, theta=0.0001, discount_factor=1.0):
    """
    Value Iteration Algorithm.
    
    Args:
        env: OpenAI env. env.P represents the transition probabilities of the environment.
            env.P[s][a] is a list of transition tuples (prob, next_state, reward, done).
            env.nS is a number of states in the environment. 
            env.vA is a vector of the number of actions per state in the environment.
        theta: We stop evaluation once our value function change is less than theta for all states.
        discount_factor: Gamma discount factor.
        
    Returns:
        A tuple (policy, V) of the optimal policy and the optimal value function.
    """
    
    def one_step_lookahead(state, V):
        """
        Helper function to calculate the value for all action in a given state.
        
        Args:
            state: The state to consider (int)
            V: The value to use as an estimator, Vector of length env.nS
        
        Returns:
            A vector of length env.vA[state] containing the expected value of each action.
        """
        A = np.zeros(env.vA[state])
        for a in range(env.vA[state]):
            for prob, next_state, reward, _ in env.P[state][a]:
                A[a] += prob * (reward + discount_factor * V[next_state])
        return A
    
    V = np.zeros(env.nS)
    while True:
        # Stopping condition
        delta = 0
        # Update each state...
        for s in range(env.nS):
            # Do a one-step lookahead to find the best action
            A = one_step_lookahead(s, V)
            best_action_value = np.max(A)
            # Calculate delta across all states seen so far
            delta = max(delta, np.abs(best_action_value - V[s]))
            # Update the value function. Ref: Sutton book eq. 4.10. 
            V[s] = best_action_value        
        # Check if we can stop 
        if delta < theta:
            break
    
    # Create a deterministic policy using the optimal value function
    policy = [np.zeros(nA) for nA in env.vA]
    for s in range(env.nS):
        # One step lookahead to find the best action for this state
        A = one_step_lookahead(s, V)
        best_action = np.argmax(A)
        # Always take the best action
        policy[s][best_action] = 1.0
    return policy, V
optimal_policy, optimal_value_fxn = value_iteration(env)
optimal_value_fxn
optimal_policy
for s, actions in enumerate(optimal_policy):
    print(f"In state {obs[s]}")
    print(f"optimal state-value: ", optimal_value_fxn[s])
    print(f"action for optimal policy: ", actions_for_obs[s][np.argmax(actions)], '\n')<jupyter_output>In state FACEBOOK
optimal state-value:  6.0
action for optimal policy:  quit 

In state CLASS1
optimal state-value:  6.0
action for optimal policy:  study 

In state CLASS2
optimal state-value:  8.0
action for optimal policy:  study 

In state CLASS3
optimal state-value:  10.0
action for optimal policy:  study 

In state SLEEP
optimal state-value:  0.0
action for optimal policy:  sleep
{'fraction_non_alphanumeric': 0.08852061438965239, 'fraction_numerical': 0.011856642414443546, 'mean_word_length': 2.856103896103896, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 17, 'https://': 3, 'lorem ipsum': 0, 'www.': 1, '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': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '391526', 'license': 'MIT', 'n_tokens_mistral': 2280, 'n_tokens_neox': 2162, 'n_words': 795, 'path': '02-dynamic-programming/student_MDP_dynamic_programming_solutions.ipynb', 'repo_name': 'frangipane/reinforcement-learning', 'size': '7433'}