8.DP(2) Value Iteration 실습1

[ 8. Value Iteration 실습 1 ]

( https://sumniya.tistory.com/10?category=781573 의 도움을 받아 코드를 작성하였습니다 )

import numpy as np

1. get_state

( 이 부분은 이전의 “Policy Iteration with Python”과 동일하다 )

def get_state(s,a,grid_size):
    # agent가 취할 수 있는 4가지 행동(A) 
    A = [(-1,0),(1,0),(0,-1),(0,1)]
    s[0] += A[a][0]
    s[1] += A[a][1]
    
    # agent가 grid 밖으로 벗어날 수는 없다
    if s[0]<0:
        s[0]=0
    elif s[0]>grid_size-1:
        s[0]=grid_size-1
    
    if s[1]<0:
        s[1]=0
    elif s[1]>grid_size-1:
        s[1]=grid_size-1
    
    return s[0],s[1]

# ex) 4x4크기의 grid 세계
# 시작하는 state : (0,0)~(3,3)
# action 3 (즉 (0,-1))을 했을 때
# 위치하게 되는 놓이게 되는 state는?
for i in range(3):
    for j in range(3):
        x,y = get_state(s=[i,j],a=3,grid_size=4)
        print(x,y)

0 1
0 2
0 3
1 1
1 2
1 3
2 1
2 2
2 3

2. Policy Evaluation

getting the “value function”

\(v_{\pi}(s) = E[R_{t+1}+\gamma R_{t+2} + ... \mid S_t = s]\) 구하기

지난 포스트에서 얘기 했듯, Policy Iteration과는 다르게, Value Iteration에서는 Policy Evaluation의 과정만 있을 뿐, Improvement 과정이 없다. Value Iteration에서는 (value에 각 action을 취할 확률을 곱해서 summation을 하는 대신) max값을 바로 현재 state의 value로 취한다!

Policy Evaluation을 하는 코드는 다음과 같다.

def policy_eval(grid_size,action,policy,iter_num,reward=-1,dis=0.9):
    post_value_table = np.zeros([grid_size,grid_size])
    
    for i in range(iter_num):
        val_table = np.zeros([grid_size,grid_size])
        
        for m in range(grid_size):
            for n in range(grid_size):
                if (m==n==0) or (m==n==grid_size-1):
                    value_t = 0
                else :
                    value_t_list = []
                    for a in action:
                        m_, n_ = get_state([m,n],a,grid_size) # get s(t+1)
                        v = reward+dis*post_value_table[m_][n_] # no probability!
                        value_t_list.append(v)
                    val_table[m][n] = max(value_t_list) # just choose the MAX
        i += 1
        
        if i%1 ==0:
            print('Iteration : {} \n {} \n'.format(i,val_table))            
        post_value_table = val_table
        
    return val_table

다음의 상황을 가정해보자. ( grid의 크기 : 4x4 )

grid_size = 4
action = [0,1,2,3]
policy = np.empty([grid_size,grid_size,len(action)])

for i in range(grid_size):
    for j in range(grid_size):
        for k in range(len(action)):
            if i==j and ((i==0) or (i==grid_size)):
                policy[i][j]=0.00
            else :
                policy[i][j]=0.25

간단한 문제라서, 몇 번의 Iteration 없이도 거의 최적의 solution에 도달함을 알 수 있다.

final_value = policy_eval(grid_size,action,policy,6)

Iteration : 1 
 [[ 0. -1. -1. -1.]
 [-1. -1. -1. -1.]
 [-1. -1. -1. -1.]
 [-1. -1. -1.  0.]] 

Iteration : 2 
 [[ 0.  -1.  -1.9 -1.9]
 [-1.  -1.9 -1.9 -1.9]
 [-1.9 -1.9 -1.9 -1. ]
 [-1.9 -1.9 -1.   0. ]] 

Iteration : 3 
 [[ 0.   -1.   -1.9  -2.71]
 [-1.   -1.9  -2.71 -1.9 ]
 [-1.9  -2.71 -1.9  -1.  ]
 [-2.71 -1.9  -1.    0.  ]] 

Iteration : 4 
 [[ 0.   -1.   -1.9  -2.71]
 [-1.   -1.9  -2.71 -1.9 ]
 [-1.9  -2.71 -1.9  -1.  ]
 [-2.71 -1.9  -1.    0.  ]] 

Iteration : 5 
 [[ 0.   -1.   -1.9  -2.71]
 [-1.   -1.9  -2.71 -1.9 ]
 [-1.9  -2.71 -1.9  -1.  ]
 [-2.71 -1.9  -1.    0.  ]] 

Iteration : 6 
 [[ 0.   -1.   -1.9  -2.71]
 [-1.   -1.9  -2.71 -1.9 ]
 [-1.9  -2.71 -1.9  -1.  ]
 [-2.71 -1.9  -1.    0.  ]] 

6번의 iteration이후 얻게 된 value table은 다음과 같다.

final_value

array([[ 0.  , -1.  , -1.9 , -2.71],
       [-1.  , -1.9 , -2.71, -1.9 ],
       [-1.9 , -2.71, -1.9 , -1.  ],
       [-2.71, -1.9 , -1.  ,  0.  ]])