<jupyter_start><jupyter_text>DAT257x: Reinforcement Learning Explained Lab 4: Dynamic Programming Exercise 4.1 Policy Evaluation with 2 Arrays Policy Evaluation calculates the value function for a policy, given the policy and the full definition of the associated Markov Decision Process.  The full definition of an MDP is the set of states, the set of available actions for each state, the set of rewards, the discount factor, and the state/reward transition function.<jupyter_code>import test_dp               # required for testing and grading your code
import numpy as np
import gridworld_mdp as gw   # defines the MDP for a 4x4 gridworld<jupyter_output><empty_output><jupyter_text>The gridworld MDP defines the probability of state transitions for our 4x4 gridworld using a "get_transitions()" function.  Let's try it out now, with state=2 and all defined actions.<jupyter_code># try out the gw.get_transitions(state, action) function

state = 2
actions = gw.get_available_actions(state)

for action in actions:
    transitions = gw.get_transitions(state=state, action=action)

    # examine each return transition (only 1 per call for this MDP)
    for (trans) in transitions:
        next_state, reward, probability = trans    # unpack tuple
        print("transition("+ str(state) + ", " + action + "):", "next_state=", next_state, ", reward=", reward, ", probability=", probability)<jupyter_output>transition(2, up): next_state= 2 , reward= -1 , probability= 1
transition(2, down): next_state= 6 , reward= -1 , probability= 1
transition(2, left): next_state= 1 , reward= -1 , probability= 1
transition(2, right): next_state= 3 , reward= -1 , probability= 1<jupyter_text>**Implement the algorithm for Iterative Policy Evaluation using the 2 array approach**.  In the 2 array approach, one array holds the value estimates for each state computed on the previous iteration, and one array holds the value estimates for the states computing in the current iteration.A empty function **policy_eval_two_arrays** is provided below; implement the body of the function to correctly calculate the value of the policy using the 2 array approach.  The function defines 5 parameters - a definition of each parameter is given in the comment block for the function.  For sample parameter values, see the calling code in the cell following the function.<jupyter_code># try out the gw.get_transitions(state, action) function
def local_search(state):
    actions = gw.get_available_actions(state)
    branches = [];
    for action in actions:
        branches.append(gw.get_transitions(state=state, action=action)[0])
    return branches
b = local_search(2);
print(b)
for bb in b:
    next_state, reward, probability = bb    # unpack tuple
    print("transition("+ str(state) + ", " + action + "):", "next_state=", next_state, ", reward=", reward, ", probability=", probability)
for bb in b:
    next_state, reward, probability = bb    # unpack tuple
    print("transition("+ str(state) + ", " + action + "):", "next_state=", bb[0], ", reward=", reward, ", probability=", probability)
def policy_eval_two_arrays(state_count, gamma, theta, get_policy, get_transitions):
    """
    This function uses the two-array approach to evaluate the specified policy for the specified MDP:
    
    'state_count' is the total number of states in the MDP. States are represented as 0-relative numbers.
    
    'gamma' is the MDP discount factor for rewards.
    
    'theta' is the small number threshold to signal convergence of the value function (see Iterative Policy Evaluation algorithm).
    
    'get_policy' is the stochastic policy function - it takes a state parameter and returns list of tuples, 
        where each tuple is of the form: (action, probability).  It represents the policy being evaluated.
        
    'get_transitions' is the state/reward transiton function.  It accepts two parameters, state and action, and returns
        a list of tuples, where each tuple is of the form: (next_state, reward, probabiliity).  
        
    """
    V = state_count*[0]
    V_new = state_count*[0]
    while True:
        delta = 0 
        V_new = state_count*[0]
        for s in range(state_count):
            v = V[s];
            
            # Look at the possible next actions
            policy = get_policy(s);           
            for a, action_prob in policy:
                # Local search of states
                transitions = gw.get_transitions(state=s, action=a);
                #print(transitions)
                for  t in transitions:
                    next_state, reward, prob = t; # unpack
                    # Calculate the expected value. Ref: Sutton book eq. 4.6.
                    V_new[s] += action_prob * prob * (reward + gamma*V[next_state])            
            delta = max(delta, np.abs(v - V_new[s]))
        V = V_new;
        # Stop evaluating once our value function change is below a threshold
        if delta < theta:
            break
        
    return V<jupyter_output><empty_output><jupyter_text>First, test our function using the MDP defined by gw.* functions.<jupyter_code>def get_equal_policy(state):
    # build a simple policy where all 4 actions have the same probability, ignoring the specified state
    policy = ( ("up", .25), ("right", .25), ("down", .25), ("left", .25))
    return policy

n_states = gw.get_state_count()

# test our function
values = policy_eval_two_arrays(state_count=n_states, gamma=.9, theta=.001, get_policy=get_equal_policy, \
    get_transitions=gw.get_transitions)

print("Values=", values)<jupyter_output>Values= [0.0, -5.274709263277986, -7.123800104889248, -7.64536148969558, -5.274709263277987, -6.602238720082915, -7.17604178238719, -7.1238001048892485, -7.1238001048892485, -7.176041782387191, -6.602238720082915, -5.274709263277986, -7.645361489695581, -7.1238001048892485, -5.274709263277986]<jupyter_text>**Expected output from running above cell:**`Values= [0.0, -5.274709263277986, -7.123800104889248, -7.64536148969558, -5.274709263277987, -6.602238720082915, -7.17604178238719, -7.1238001048892485, -7.1238001048892485, -7.176041782387191, -6.602238720082915, -5.274709263277986, -7.645361489695581, -7.1238001048892485, -5.274709263277986]`<jupyter_code>import numpy as np
a = np.append(values, 0)
np.reshape(a, (4,4))<jupyter_output><empty_output><jupyter_text>Now, test our function using the test_dp helper.  The helper also uses the gw MDP, but with a different gamma value.If our function passes all tests, a passcode will be printed.<jupyter_code># test our function using the test_db helper
test_dp.policy_eval_two_arrays_test( policy_eval_two_arrays )<jupyter_output>Testing: Policy Evaluation (two-arrays)
passed test: return value is list
passed test: length of list = 15
passed test: values of list elements
PASSED: Policy Evaluation (two-arrays) passcode = 9986-145
{'fraction_non_alphanumeric': 0.09224501673214026, 'fraction_numerical': 0.07609486396042485, 'mean_word_length': 3.7472375690607733, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 22, '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': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '146102', 'license': 'Unlicense', 'n_tokens_mistral': 2381, 'n_tokens_neox': 2039, 'n_words': 726, 'path': 'Module 4/Ex4.1 Policy Evaluation 2 Arrays.ipynb', 'repo_name': 'r-keller/dat257x', 'size': '6873'}