<jupyter_start><jupyter_text>Policy Iteration Algorithm<jupyter_code>import numpy
import gym
import time
def execute(env, policy, gamma=1.0, render=False):
    start = env.reset() 
    totalReward = 0 
    stepIndex = 0 
    while True:
        if render: 
            env.render()
        start, reward, done, _ = env.step(int(policy[start])) 
        totalReward += (gamma ** stepIndex * reward) 
        stepIndex += 1
        if done:
            break
    return totalReward

def evaluatePolicy(env, policy, gamma=1.0, n=100):
    scores = [execute(env, policy, gamma=gamma, render=False) for _ in range(n)]
    return numpy.mean(scores)

def extractPolicy(v, gamma=1.0):
    policy = numpy.zeros(env.env.nS)
    for s in range(env.env.nS):
        q_sa = numpy.zeros(env.env.nA)
        for a in range(env.env.nA):
            q_sa[a] = sum([p * (r+gamma*v[s_]) for p,s_,r,_ in env.env.P[s][a]])
        policy[s] = numpy.argmax(q_sa)
    return policy

def CalcPolicyValue(env, policy, gamma=1.0):
    value = numpy.zeros(env.env.nS)
    eps = 1e-10
    while True:
        previousValue = numpy.copy(value)
        for states in range(env.env.nS):
            policy_a = policy[states]
            value[states] = sum([p * (r + gamma*previousValue[s_]) for p, s_, r, _ in env.env.P[states][policy_a]])
        if (numpy.sum((numpy.fabs(previousValue - value))) <= eps):
            break
                
    return value

def policyIteration(env, gamma=1.0):
    policy = numpy.random.choice(env.env.nA, size=(env.env.nS))
    print(policy)
    maxIterations = 1000
    gamma = 1.0
    for i in range(maxIterations):
        oldPolicyValue = CalcPolicyValue(env, policy, gamma)
        print('oldPolicyValue', oldPolicyValue)
        newPolicy = extractPolicy(oldPolicyValue, gamma)
        print('newPolicy', newPolicy)
        if (numpy.all(policy == newPolicy)):
            print('Policy iteration converged at %d.'%(i+1))
            break
        policy = newPolicy
    return policy

policy = numpy.array([1, 0, 2, 2, 2, 3, 1, 0, 3, 1, 2, 2, 3, 0, 1, 3])
newPolicy = numpy.array([0., 3., 3., 3., 0., 0., 0., 0., 3., 1., 0., 0., 0., 2., 1., 0.])
numpy.all(policy == newPolicy)
if __name__ == '__main__':
    env_name = 'FrozenLake-v0'
    env = gym.make(env_name)
    start = time.time()
    optimalPolicy = policyIteration(env, gamma=1.0)
    scores = evaluatePolicy(env, optimalPolicy, gamma=1.0)
    end = time.time()
    print("Best score = %0.2f. Time taken=%4.4f seconds" %(numpy.max(scores), end-start))<jupyter_output>[1 0 2 2 2 3 1 0 3 1 2 2 3 0 1 3]
oldPolicyValue [0.01926164 0.00963082 0.0329053  0.         0.02889246 0.
 0.06581059 0.         0.06741573 0.105939   0.19743178 0.
 0.         0.0529695  0.52648475 0.        ]
newPolicy [0. 3. 0. 0. 0. 0. 0. 0. 3. 1. 0. 0. 0. 2. 2. 0.]
oldPolicyValue [0.68085106 0.57446808 0.46808511 0.23404255 0.68085106 0.
 0.36170213 0.         0.68085106 0.68085106 0.61702128 0.
 0.         0.74468085 0.80851064 0.        ]
newPolicy [0. 3. 0. 3. 0. 0. 0. 0. 3. 1. 0. 0. 0. 2. 1. 0.]
oldPolicyValue [0.7804878  0.65853658 0.53658537 0.53658537 0.7804878  0.
 0.41463415 0.         0.7804878  0.7804878  0.70731707 0.
 0.         0.85365854 0.92682927 0.        ]
newPolicy [0. 3. 3. 3. 0. 0. 0. 0. 3. 1. 0. 0. 0. 2. 1. 0.]
oldPolicyValue [0.82352941 0.82352941 0.82352941 0.82352941 0.82352941 0.
 0.52941176 0.         0.82352941 0.82352941 0.76470588 0.
 0.         0.88235294 0.94117647 0.        ]
newPolicy [0. 3. 3. 3. 0. 0. 0. 0. 3. 1. 0. 0. 0. 2. 1. 0.]
Policy ite[...]
{'fraction_non_alphanumeric': 0.14861816130851663, 'fraction_numerical': 0.15425831923293853, 'mean_word_length': 2.209954751131222, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '87721', 'license': 'MIT', 'n_tokens_mistral': 1758, 'n_tokens_neox': 1389, 'n_words': 369, 'path': 'Reinforcement Learning/FrozenLake - Policy Iteration.ipynb', 'repo_name': 'deepaksood619/DS_ML', 'size': '3546'}