<jupyter_start><jupyter_text>Defining Print Options<jupyter_code># Configures numpy print options
@contextlib.contextmanager
def _printoptions(*args, **kwargs):
    original = np.get_printoptions()
    np.set_printoptions(*args, **kwargs)
    try:
        yield
    finally:
        np.set_printoptions(**original)<jupyter_output><empty_output><jupyter_text>Tabular Model Based Algorithms  Bellman Equation<jupyter_code>def calcluate_value(env, gamma, values, s, a):
    """
    V_pi(s) = sum ( Pass' * [ Rass' + gamma*V_pi(s') ] )
    """
    value = sum(
                [ env.p(next_s, s, a) * 
                ( env.r(next_s, s, a) + gamma * values[next_s] )
                for next_s in range(env.n_states) ]
                ) 
    
    return value<jupyter_output><empty_output><jupyter_text>Policy Iteration<jupyter_code>def policy_evaluation(env, policy, gamma, theta, max_iterations):
    """
    Update value of each state, until max_iterations or delta < theta
    """
    values = np.zeros(env.n_states, dtype=np.float)
    for _ in range(max_iterations):
        delta = 0
        for s in range(env.n_states):
            v = values[s]
            values[s] = calcluate_value(env, gamma, values, s, policy[s])
            delta = max(delta, abs(v - values[s]))
        if delta < theta:   
            break
            
    return values


def policy_improvement(env, values, gamma):
    """
    Updates policy: for each state, replace current action with the highest value rewarding action
    """
    policy = np.zeros(env.n_states, dtype=int)
    for s in range(env.n_states):
        policy[s] = np.argmax( [ calcluate_value(env, gamma, values, s, a) for a in range(env.n_actions) ] )

    return policy


def policy_iteration(env, gamma, theta, max_iterations, policy=None):
    """
    Create a random policy. Alternatively evaluate and improve the policy until no improvement can be made.
    """
    if policy is None:
        policy = np.zeros(env.n_states, dtype=int)
    else:
        policy = np.array(policy, dtype=int)
        
    policy_initial = None
    
    while(np.array_equal(policy_initial, policy)==False):
        policy_initial = policy
        value = policy_evaluation(env, policy, gamma, theta, max_iterations)
        policy = policy_improvement(env, value, gamma)
        
    return policy, value<jupyter_output><empty_output><jupyter_text>Run Policy iteration<jupyter_code>print('# Model-based algorithms')
gamma = 0.9
theta = 0.001
max_iterations = 100000

print('')

print('## Policy iteration')
policy, values = policy_iteration(env, gamma, theta, max_iterations)
env.render(policy, values)<jupyter_output># Model-based algorithms

## Policy iteration
Lake:
[['&' '.' '.' '.']
 ['.' '#' '.' '#']
 ['.' '.' '.' '#']
 ['#' '.' '.' '$']]
Policy:
[['↓' '→' '↓' '←']
 ['↓' '↑' '↓' '↑']
 ['→' '↓' '↓' '↑']
 ['↑' '→' '→' '↑']]
Value:
[[0.455 0.504 0.579 0.505]
 [0.508 0.    0.653 0.   ]
 [0.584 0.672 0.768 0.   ]
 [0.    0.771 0.887 1.   ]]<jupyter_text>Value Iteration<jupyter_code>def value_iteration(env, gamma, theta, max_iterations, values=None):
    """
    Start with random values and iterate until optimal values have been found.
    Calculate policy in one sweep based on optimal values.
    """
    if values is None:
        values = np.zeros(env.n_states)
    else:
        values = np.array(values, dtype=np.float)

    for _ in range(max_iterations):
        delta = 0
        for s in range(env.n_states):
            v = values[s]
            values[s] = max( [ calcluate_value(env, gamma, values, s, a) for a in range(env.n_actions) ] )
            delta = max(delta, abs(v - values[s]))
        if delta < theta:
            break

    policy = np.zeros(env.n_states, dtype=int)
    for s in range(env.n_states):
        policy[s] = np.argmax( [ calcluate_value(env, gamma, values, s, a) for a in range(env.n_actions) ] )

    return policy, values<jupyter_output><empty_output><jupyter_text>Run Value Iteration<jupyter_code>print('## Value iteration')
optimal_policy, values = value_iteration(env, gamma, theta, max_iterations)
env.render(optimal_policy, values)<jupyter_output>## Value iteration
Lake:
[['&' '.' '.' '.']
 ['.' '#' '.' '#']
 ['.' '.' '.' '#']
 ['#' '.' '.' '$']]
Policy:
[['↓' '→' '↓' '←']
 ['↓' '↑' '↓' '↑']
 ['→' '↓' '↓' '↑']
 ['↑' '→' '→' '↑']]
Value:
[[0.455 0.504 0.579 0.505]
 [0.508 0.    0.653 0.   ]
 [0.584 0.672 0.768 0.   ]
 [0.    0.771 0.887 1.   ]]
{'fraction_non_alphanumeric': 0.16213177422981787, 'fraction_numerical': 0.025185518326961996, 'mean_word_length': 2.9051799824407376, 'pattern_counts': {'":': 0, '<': 26, '<?xml version=': 0, '>': 23, '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': '310167', 'license': 'MIT', 'n_tokens_mistral': 1689, 'n_tokens_neox': 1591, 'n_words': 385, 'path': 'Tabular Model Based Algos.ipynb', 'repo_name': 'ishaan27chaturvedi/Frozen-Lake', 'size': '4447'}