<jupyter_start><jupyter_text>Value Iteration: **Optimal Value function을 Bellman Optimality Equation으로 찾는다.**$$\\ V^*(s) =max_a \sum_{s'}[r(s,a,s') + \gamma V^*(s')]P(s'|s,a)$$step 1 : randomly initialize the value step 2 : Bellman Optimality Equation으로 value 업데이트 step 3 : (update value - current value)  stop, else repeat step2<jupyter_code>def value_iteration(env, gamma=0.99, epsilon=1e-6):
    obs_space = env.observation_space
    n_state = obs_space.n
    act_space = env.action_space
    n_act = act_space.n
    
    # Transition Probability
    P = env.unwrapped.P
    
    # Randomly initialize the value
    value = np.random.uniform(size=(n_state,1))
    
    while True:
        q = np.zeros((n_state,n_act)) # setting Q-value
        for s in P.keys():
            for a in P[s].keys():
                for prob, next_s, reward, done in P[s][a]:
                    q[s][a] += (reward + gamma*value[next_s])*prob
        v_prime = np.max(q,axis=1) # policy distribution이 어떤지가 중요하지 않고, 그냥 max로 때린다.
        dist = np.max(np.abs(v_prime - value))
        value = v_prime
        if dist < epsilon:
            break
    policy = np.zeros((n_state, n_act))
    policy[np.arange(n_state), np.argmax(q,axis=1)] = 1
    
    return policy, value

def plot_results(policy, value):
    plt.figure(num=0)
    plt.imshow(np.reshape(value,(8,8)))
    plt.title("Value Function")  
    arr_len = 0.2
    for i in range(8):
        for j in range(8):
            s = i*8+j
            if policy[s][0]> 0:
                plt.arrow(j,i,-arr_len,0,color="r",alpha=policy[s][0],width=0.01,head_width=0.5,head_length=0.1,overhang=1)
            if policy[s][1]> 0:
                plt.arrow(j,i,0,arr_len,color="r",alpha=policy[s][1],width=0.01,head_width=0.5,head_length=0.1,overhang=1)
            if policy[s][2]> 0:
                plt.arrow(j,i,arr_len,0,color="r",alpha=policy[s][2],width=0.01,head_width=0.5,head_length=0.1,overhang=1)
            if policy[s][3]> 0:
                plt.arrow(j,i,0,-arr_len,color="r",alpha=policy[s][3],width=0.01,head_width=0.5,head_length=0.1,overhang=1)
    plt.grid(False)
    plt.show()
    
if __name__=="__main__":
    print("Value Iteration Compact")
    import time
    start = time.time()
    policy, value = value_iteration(env)
    print("Computation Time : %.2f"%(time.time() - start))
    print('')
    
    plot_results(policy, value)
    np.set_printoptions(precision=3,suppress=True)
    print(policy)<jupyter_output>Value Iteration Compact
Computation Time : 0.60<jupyter_text>Run Optimal Policy<jupyter_code>obs = env.reset()
for t in range(10000):
    print('t = %d'%t)
    env.render()
    print('')
    action = np.random.choice(n_act, 1, p=policy[obs][:])[0]
    next_obs, reward, done, info = env.step(action)
    obs = next_obs
    if done:
        break
env.render()
env.close()<jupyter_output>t = 0

[41mS[0mFFFFFFF
FFFFFFFF
FFFHFFFF
FFFFFHFF
FFFHFFFF
FHHFFFHF
FHFFHFHF
FFFHFFFG

t = 1
  (Up)
[41mS[0mFFFFFFF
FFFFFFFF
FFFHFFFF
FFFFFHFF
FFFHFFFF
FHHFFFHF
FHFFHFHF
FFFHFFFG

t = 2
  (Up)
S[41mF[0mFFFFFF
FFFFFFFF
FFFHFFFF
FFFFFHFF
FFFHFFFF
FHHFFFHF
FHFFHFHF
FFFHFFFG

t = 3
  (Right)
SF[41mF[0mFFFFF
FFFFFFFF
FFFHFFFF
FFFFFHFF
FFFHFFFF
FHHFFFHF
FHFFHFHF
FFFHFFFG

t = 4
  (Right)
SFF[41mF[0mFFFF
FFFFFFFF
FFFHFFFF
FFFFFHFF
FFFHFFFF
FHHFFFHF
FHFFHFHF
FFFHFFFG

t = 5
  (Right)
SFFFFFFF
FFF[41mF[0mFFFF
FFFHFFFF
FFFFFHFF
FFFHFFFF
FHHFFFHF
FHFFHFHF
FFFHFFFG

t = 6
  (Up)
SFFFFFFF
FFFF[41mF[0mFFF
FFFHFFFF
FFFFFHFF
FFFHFFFF
FHHFFFHF
FHFFHFHF
FFFHFFFG

t = 7
  (Up)
SFFF[41mF[0mFFF
FFFFFFFF
FFFHFFFF
FFFFFHFF
FFFHFFFF
FHHFFFHF
FHFFHFHF
FFFHFFFG

t = 8
  (Right)
SFFFFFFF
FFFF[41mF[0mFFF
FFFHFFFF
FFFFFHFF
FFFHFFFF
FHHFFFHF
FHFFHFHF
FFFHFFFG

t = 9
  (Up)
SFFF[41mF[0mFFF
FFFFFFFF
FFFHFFFF
FFFFFHFF
FFFHFFFF
FHHFFFHF
FHFFHFHF
FFFHFFFG

t = 10
  (Right)
SFFFFFFF
FFFF[41mF[0mFFF
[...]
{'fraction_non_alphanumeric': 0.1361636034170334, 'fraction_numerical': 0.032617136940201914, 'mean_word_length': 3.37599093997735, 'pattern_counts': {'":': 1, '<': 8, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 13, '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': '148761', 'license': 'MIT', 'n_tokens_mistral': 1827, 'n_tokens_neox': 1626, 'n_words': 312, 'path': 'fastcampus/week2/2.Value_Iteration.ipynb', 'repo_name': 'Junhojuno/Deep-Reinforcement-Learning', 'size': '3863'}