강화학습 Q-learning on non-deterministic worlds



출처



Frozen Lake 게임이 non-deterministic인 경우 Q를 어떻게 학습하는지 알아보겠습니다. 이 포스팅은 Frozen Lake 게임과 강화학습의 기본 개념을 안다는 전제로 김성훈 교수님의 강화학습 강의를 제 나름대로 정리한 포스팅입니다. 우선 non-deterministic이 무슨 의미인지부터 살펴보면 non-deterministic 이라는 것은 원하는대로 되지 않는다는 의미입니다. (stochastic이라고도 합니다.) 이런 경우에는 무조건 Q가 가라는 대로 가는 것보다는 "기존의 믿음" 을 차근 차근 업데이트 해나가는 것이 Q 학습이 더 잘 된다고 합니다. 이는 현실 세계와도 많이 닮아있습니다. 이를 멘토에 비교해볼 수 있는데, 무조건 멘토가 하라는 대로 하기보다는 결국 무언가를 하기 위해서는 타인의 조언 보다는 자기 자신의 신념이 더 중요하다고 할 수 있습니다.


이를 식으로 표현하면 기존 알고리즘은  


Q(state, action) = R + λmax(Q(new state)) (λ < 1)


이었는데


Q(state, action) = (1-a)Q(state, action) + a(R+λmax(Q(new state)) (a = learning rate)

Q(state, action) = R + max(Q(new state))

출처: http://3months.tistory.com/173 [Deep Play]


사용하게 됩니다. learning rate 개념을 통해 Q를 한 번에 업데이트 하지 않고, 기존에 믿음을 토대로 조금씩 업데이트 해나가는 것입니다. 이를 구현하는 코드를 보겠습니다. 기존 코드에서 Q 업데이트 하는 부분만 달라지기 때문에 크게 다르지는 않습니다.



라이브러리 로드

import gym
import numpy as np
import matplotlib.pyplot as plt 
from gym.envs.registration import register
import random as pr


environment 생성 및 하이퍼 파라미터 초기화

env = gym.make('FrozenLake-v0')
# Q-table 초기화
Q = np.zeros([env.observation_space.n, env.action_space.n])

# Learning Rate
learning_rate = 0.85

# discount factor
dis = .99
    
# learning 횟수
num_episodes = 2000

# 학습 시 reward 저장
rList = []


Q-learning 알고리즘

for i in range(num_episodes):
    
    # env 리셋
    state = env.reset()
    rAll = 0
    done = False
    
    #decaying E-greedy
    e = 1./((i//100)+1)
    
    # Q-table Learning algorithm
    while not done:
        
        # Choose an action by e greedy
        '''
        if np.random.rand(1) < e:
            action = env.action_space.sample()
        else:
            action = np.argmax(Q[state, :])
        '''
        
        # add Random noise
        action = np.argmax(Q[state, :]+ np.random.randn(1, env.action_space.n)/(i + 1))
        
        # new_state, reward 업데이트 
        new_state, reward, done, _ = env.step(action)
        
        # update Q-table
        Q[state, action] = (1-learning_rate) * Q[state, action] + learning_rate*(reward + dis*np.max(Q[new_state, :]))
        
        rAll += reward
        state = new_state

    rList.append(rAll)

action을 선택하는 부분에서 e-greedy 방법을 사용하는 방법과 random noise를 사용하는 방법이 있는데 둘 다 exploit & exploration을 구현한 것으로 둘 중 하나를 사용하면 됩니다. 밑에 #update Q-table 부분에 Q를 업데이트하는 코드를 볼 수 있습니다. learning rate를 통해 기존의 믿음을 얼마나 받아들일지, Q의 판단을 얼마나 받아들일지를 조정합니다.

print('success rate: ', str(sum(rList)/num_episodes))
print('Final Q-table values')
print(Q)
plt.bar(range(len(rList)), rList, color = 'blue')
plt.show()

('success rate: ', '0.4135')
Final Q-table values
[[  6.05216575e-01   4.77802714e-03   7.66890982e-03   1.14402756e-02]
 [  1.89070559e-04   2.71412272e-05   2.94641678e-03   6.06539650e-01]
 [  6.20782244e-03   3.96037865e-03   2.02160738e-03   5.88158391e-01]
 [  1.38851811e-04   1.81853506e-04   1.08700028e-03   3.36662917e-01]
 [  5.63057417e-01   1.35053120e-03   4.64530097e-04   1.81633578e-03]
 [  0.00000000e+00   0.00000000e+00   0.00000000e+00   0.00000000e+00]
 [  8.64124213e-05   2.51760080e-04   7.21585211e-02   3.41902605e-05]
 [  0.00000000e+00   0.00000000e+00   0.00000000e+00   0.00000000e+00]
 [  3.70706358e-05   1.37044981e-03   2.40643636e-04   7.95889822e-01]
 [  1.09162680e-04   5.60870413e-01   9.16914837e-04   2.64997619e-04]
 [  9.20012820e-01   5.54630225e-05   7.32392792e-05   0.00000000e+00]
 [  0.00000000e+00   0.00000000e+00   0.00000000e+00   0.00000000e+00]
 [  0.00000000e+00   0.00000000e+00   0.00000000e+00   0.00000000e+00]
 [  4.37606936e-04   4.03103644e-04   9.16837079e-01   3.65822303e-04]
 [  0.00000000e+00   0.00000000e+00   2.34205607e-03   9.98477546e-01]
 [  0.00000000e+00   0.00000000e+00   0.00000000e+00   0.00000000e+00]]

success rate는 0.4135인데, 이는 0.4135의 확률로 Goal에 도착한다는 것입니다. non-deterministic world 에서는 상당히 높은 성공률입니다. 또 이 부분에서 중요한 점은 이 non-deterministic world에서의 강화학습 알고리즘의 성공률은 사람의 성공률 보다 높을 수 있다는 것입니다. 왜냐하면 deterministic world에서는 사람이 한 눈에 게임의 rule을 알 수 있고, 매우 쉽게 Goal을 찾을 수 있는 반면, non-deterministic world에서는 사람에게는 Goal을 찾아가는 것이 쉽지 않습니다. 하지만 non-deterministic world에서도 확률적으로 패턴이 존재하고, 이 사람이 이해하기 힘든 패턴속에서 강화학습 알고리즘은 에러를 최소화할 최적의 경로를 찾는다는 것입니다. 이 부분이 진정한 강화학습의 강점이 아닐까 생각해보았습니다.



  • 안녕하세요 2018.01.13 15:24

    질문하나만 해도될까요?