본문 바로가기
Artificial Intelligence/ReinforcementLearning

강화학습(Reinforcement Learning) 정리노트-DQN

by raphael3 2019. 8. 28.
반응형

                                                                                                                                                         

                                                                                                                                                                                                                   

                                                                                                                                                         

                                                                                                                                                                                                              

                                                                                                                                                                                                              

  • 본 자료는 김성훈 교수님의 모두를 위한 강화학습을 기반으로 작성되었습니다.
  • 별도의 목차가 없습니다. 한 호흡에 읽어야 해서 부담스러울수도 있습니다.

그림 1

Agent는 자신이 할 수 있는 여러 Action들 중 하나의 Action을 선택하고, 그 선택을 Environment에게 넘긴다. Agent로부터 Action을 넘겨받은 Environment는 그 Action에 대하여 두 가지 결과물을 내는데, 일단, Action의 결과인, 어떤 상황으로 변했는지에 해당하는 state 정보를 넘긴다. 그리고, 넘겨받은 Action을 평가한 점수인 reward를 넘긴다.

Environment는 openAI gym에서 제공하는 Environment을 사용하게 되는데, environment는 우리가 직접 만들 수도 있다.

openAI는 gym이라는 파이썬 패키지를 제공하는데, 이 패키지를 이용하면 손쉽게 강화학습을 실험할 수 있는 환경을 구성할 수 있다.

코드 1

 

 

그림 1에서 본 바를 코드로 옮기면 코드 1과 같다. 먼저, 어떤 Environment 상에서 활동 할지를 정하고, 몇 번의 행동을 할지 epochs로 정한다. 그 다음, env라는 이름의 객체에 해당 Environment를 담도록 한다. 또한, 초기의 state를 reset()으로 초기화한다 (이는 gym 패키지만의 스타일이다). 그 다음, 반복문을 돌면서 action을 정하고, step()을 통해 반복적으로 action을 Environment에게 넘겨준다.(step()으로 Environment와 상호작용하는 방식도 역시 openAI gym만의 스타일이다.)

그 결과, Environment는 Action의 결과로 나온 state, Action에 대한 평가 결과인 reward, 게임이 종료되었는지(즉 Hole에 빠졌는지 아니면 Goal에 도착했는지) 알려주는 done, 마지막으로 추가 정보를 알려주는 additional_info를 받을 수 있다. render()메소드는 Environment의 상황을 그래픽으로 출력해주는 역할을 담당한다. 현재는, Action 부분은 random하게 설정되어 있다. 앞으로 진행되는 과정에서 Action은 특수한 알고리즘에 의해 선택된다.

그림 2

초기에 Agent는, 실은 Environment에 대한 어떠한 정보도 없이 무작정 Action을 취할 수 밖에 없게 된다. 따라서 여러 번의 시행착오를 통해 가장 적합한 Action이 무엇인지 스스로 학습해나가는 방식인 강화학습을 이용한다.

먼저, 사용자로부터 직접 키보드로 Action을 입력받아 게임을 진행해보자.

코드 2

State: 14 Action: 1 Reward: 0.0 Info: {'prob': 1.0}

키보드로 입력받는 방향키는 LEFT부터 반시계방향으로 0,1,2,3으로 정해진다. 이 코드에서 agent는 유저 자기 자신이기 때문에, readchar 패키지를 이용하여 유저로부터 직접 키보드 값을 입력받는다. 입력받은 키보드 값이 화살표키가 맞는지 아닌지를 검사하기 위하여 arrow_keys딕셔너리를 정의하고, 이를 이용하여 키를 검사한다. 나머지 부분은 코드 1과 동일하게 step()메소드를 이용하여 Environment와 상호작용하는 부분이다.

step()에 대한 더 자세한 설명은 다음과 같다.

The environment’s step function returns exactly what we need. In fact, step returns four values. These are:

  • observation (object): an environment-specific object representing your observation of the environment. For example, pixel data from a camera, joint angles and joint velocities of a robot, or the board state in a board game.
  • reward (float): amount of reward achieved by the previous action. The scale varies between environments, but the goal is always to increase your total reward.
  • done (boolean): whether it’s time to reset the environment again. Most (but not all) tasks are divided up into well-defined episodes, and done being True indicates the episode has terminated. (For example, perhaps the pole tipped too far, or you lost your last life.)
  • info (dict): diagnostic information useful for debugging. It can sometimes be useful for learning (for example, it might contain the raw probabilities behind the environment’s last state change). However, official evaluations of your agent are not allowed to use this for learning.

요약하자면, step 함수는 네 개의 value들을 return하는데, observation, reward, done, info다. observation은 Environment가 관찰한 바를 알려준다. 즉, Environment가 현재 상황이 어떤지에 대해 관찰한 모든 내용을 알려준다. (예를 들면, 현실 세계의 로봇에서는 여러 가지 observation이 발생할 수 있을 것이다.) observation은 여러 정보를 가질 수 있기 때문에 object 타입인 것으로 보인다. reward는 action의 결과로 얻은 모든 reward들의 합이다.

reward값은 Environment가 어떤 reward값을 어떤 타입의 숫자로 주느냐에 따라 다양할 수 있기 때문에 float타입으로 보인다. 확실한 것은, Goal에 도달할 시 높은 reward를 준다는 점이다. done은 Hole에 빠지거나, Goal에 도달할 경우에만 True가 된다.(아래 그림 3과 같다.) Environment를 reset할지 말지를 결정하는 flag변수로서 쓰인다. info는 확률값을 출력해준다. 참고용 정도로 활용할 수 있을 것 같다. openAI gym을 통해 살펴본 강화학습의 전체적인 상황은 그림 4와 같다고 할 수 있다.

그림 3

그림 3을 통해 관찰가능한 정보는, 일단 state는 왼쪽 위에서부터 0의 state(observation)을 가진다는 점이다. 즉, 책 읽는 방향과 똑같은 순서로 state가 숫자로 매핑된다.

action은 키보드로 입력받은 방향이 숫자로 매핑된 결과가 그대로 뜨며, reward는 현재까지 받은 reward의 합인데, reward를 update하지 않기 때문에, goal에 도달하기 전까지는 0의 reward가 유지된다.

우리는 그림3과 같이 전체적인 상황을 다 보면서 플레이하기 때문에 쉽게 goal에 도달할 수 있다. 그러나, 실제 agent가 바라보는 상황은 그림 5와 같다.

그림 5

어쨌든, 이렇게 매 timestep마다, agent는 Action을 선택하고, Environment는 observation과 reward를 되돌려주는 방식으로 돌아가게 되어있다 (그림 6). openAI gym 패키지에서 이 과정의 첫 시작은 reset()함수를 호출한 이후부터이다. 따라서 코드 1에서 reset()함수를 호출해준 것이다. 코드 2는 사용자로부터 직접 action을 받기 위해 reset()에 대한 별도의 호출이 필요하지 않지만, 넣어주어도 무방하다. reset()함수를 호출하게 되면, 초기의 observation을 받는다. (즉, 아마 agent의 현재 위치에 대한 정보를 받을 것이다.)

그림 6

이용가능한 모든 Environment에 대한 목록은 코드 3으로 알아낼 수 있다.

코드 3

 

주목할만한 점은, 내가 직접 Environment를 만들어 registry에 추가할 수 있다는 점이다. gym.make()와 register()함수를 이용해서, 내가 만든 Environment를 인자로 불러오기만 하면, 내가 만든 Environment를 쉽게 호출하여 사용할 수 있게 된다.

 

한편, 그림 5의 상황에서 agent는 일단 어떻게든 아무렇게나 움직이기라도 해야 상황이 어떤지 판단할 수 있는 상황이라고 할 수 있다. 즉, agent는 오로지 현재 state(파란색 박스)만을 알고 있는 상황이다. 특정 Action을 하기 전까진 아무것도 알 수 없다. 그러나 일단 Action을 하고 나면, 상황이 어떤지(->state), 그 행동에 대한 피드백은 어떤지(->reward)를 알아낼 수 있다. 현재 환경에서는, 맨 처음에 agent가 움직일 때 agent는 Hole에 빠지지 않거나, Goal에 도달하지 않는 한 지속적으로 0의 reward를 받게 된다 (reward가 0이라는 것은 agent의 Action에 대하여 잘했는지 못했는지 평가할 수 없다는 걸 의미한다).

그러므로 일단, agent가 Action을 취해야 한다.

 

그 방법, 첫번째: random한 Action을 취한다. —> 이 방법은 Goal에 도달할 확률이 낮다. 어쩌다 한 번 Goal에 도달할 수는 있지만, 매번 optimal하지 않은 선택을 한다는 문제가 있다.

 

두번째 방법: 어떤 길을 가기 전에, 미리 알아보고 간다. 예를 들면, 네이버 지도를 살펴보고 길을 나서는 것과 같은 방법을 쓰는 것이다. 이 지도를 강화학습에서는 Q라고 부른다. —> Q도 처음에는 Goal이 어딘지는 정확하게 알지 못하지만, 지속적으로 지도가 업데이트 되면서 궁극적으로 Goal에 도달하는 길을 알게 된다.

그림 7

Q에게 줄 정보는 현재 state와 어떤 action을 선택했는지에 대한 정보다. 그러면 Q는 그 길로 가는 행동(action)이 얼마나 좋은지를 알려준다(reward). 이를 Q-function, 혹은 state-action value function이라고 부른다. 즉 state와 action을 파라미터로 받는 함수다. 현재 상태에서 취할 수 있는 action은 네 가지로 정해져있다; LEFT, RIGHT, UP, DOWN. 이 각각에 대한 피드백(reward)은 예를 들면, 다음과 같이 받을 수 있다.

 

Q(current_state: S1, action: LEFT): 0 —> 좋은지 안좋은지 모르겠다.

Q(current_state: S1, action: RIGHT): 0.5 —> 좋을거라고 50% 확신한다.

Q(current_state: S1, action: DWON): 0.3 —> 30% 정도 확신한다.

Q(current_state: S1, action: UP): 0 —> 좋은지 안좋은지 모르겠다.

 

agent는 어떤 선택을 할 것인가? (즉, agent는 어떤 policy를 채택할 것인가?) 당연히, RIGHT를 선택할 것이다.

왜 그런가? Q가 maximum으로 확신하는 action이 RIGHT이기 때문이다.

 

우리는, 구현 측면에서 Q가 maximum으로 확신하는 action이 무엇인지를 알 필요가 있다. 이를 argument of the maximum value를 찾는 것, 줄여서 argmax를 찾는 것이라고 한다.

 

max값은 0.5이고, argmax는 RIGHT이니, agent는 RIGHT를 action으로 선택하여 길을 나서는 행동을 하면 된다.

이 과정을 수학적으로 표현하면 다음과 같다.

 

수식 1-1

각각의 action마다 Q의 평가 결과(피드백 결과)가 0과 1사이의 값으로 나오고,

수식 1-2

이 평가 결과들 중 가장 높은 값은 0.5이며,

수식 1-3

0.5를 내는 action은 RIGHT이다.

이를 일반화하여 표현하면 다음과 같다.

수식 1-4

즉, Q를 이용하여 optimal policy를 찾는 것이라고 보면 된다.

 

실은, Q는 처음에는 optimal하지는 않다. 하지만 처음부터 optimal하다고 가정하고 Q의 값을 그대로 참고하여, 길을 나서는 방식을 취한다.

궁극적으로, Q를 optimal한 Q가 되도록 학습시키는 것이 핵심이다. Q는 다음과 같이 update되어 optimal해진다.

수식 2

agent가 취한 특정 action1에 대하여 즉각적으로 그 action1에 대한 평가결과인 reward를 받고,

그다음 state의 가능한 action들 중, 가장 높은 Q값을 내는 특정 action2에 대한 평가 결과(reward)를 더하여, (즉 우항의 두 항은 모두 reward이다.)

현재 state에서 선택한, 특정 action1에 대한 Q값을 update한다. 이렇게 현재 state에서 모든 action에 대한 Q값을 update하여 지도를 고쳐나간다.

 

이 과정을 그림으로 나타낼 수 있다. 그림 8은 맨 처음의 Q의 상태를 나타낸다.

그림 8

Q는 이 상태에서 학습을 시작하는데, 상황이 이러하므로, agent는 무작위적으로 움직일 수 밖에 없게 된다. 그러다 agent가 우연히 goal 근처에 도착하면 (goal의 바로 왼쪽 박스에 도착하면), 해당 영역에서의 Q값이 RIGHT action에 대한 평가 결과(reward)인 1을 리턴받게 된다. 이 상황이 그림 9에 나타난다.

그림 9

같은 방식으로 계속 무작위적으로 행동하다가, 궁극적으로는 그림 10과 같은 상황이 된다.

그림 10

이젠 goal로 가는 길을 완벽히 알고있는 optimal한 Q가 되었다. 따라서 agent는 완성된 지도인 Q를 보면서, 항상 goal에 도달하게 된다.

이를 알고리즘으로 표현하면 알고리즘 1-1과 같다.

알고리즘 1-1

먼저, 모든 Q table의 값을 0으로 초기화 한다.

그 다음, 현재 상태가 무엇인지를 파악한 후, iterative한 learning과정을 거쳐 Q를 update한다.

learning 과정에서, agent는 모든 action에 대하여, 특정 action을 랜덤하게 선택하고, 이를 environment에게 넘긴다.

environment는 넘겨받은 action에 대한 reward를 내어주고,

agent는 새로운 상황에 직면하게 된다. 직면한 새로운 상황에서 지도(Q table)를 수정한다. 즉, goal로 가는 경로가 있다면 이를 체크한다 (어디까지나 비유적표현이다.). 그리고 현재 자신의 상황을 받아들인다 (s ← s').

—> 마치 사람이 일기쓰고, 현실을 직시하고 반성하는 과정같이 보인다.

여기서, 모든 Q table의 값을 0으로 초기화하게 되면, agent가 선택할 action의 우선순위가 없다는 문제가 있다. 이럴 경우엔 그냥 랜덤하게 아무 action이나 선택하도록 해야 한다. 코드 3을 보자.

 

코드 4

 

rargmax는 random argmax의 약자다. amax, nonzero같은 함수들에 대한 예시 코드는 코드 4와 코드 5에 있다.

코드 5

 

(16, 4)
100
(16, 4)
[ 13 14 15 100]

numpy.amax()는 array중 가장 큰(max) 값을 내는 numpy의 함수다. 어떤 array를 파라미터로 받으면, 해당 array의 element 하나하나를 검사(element-wise하게 검사)하여 그 중 최대값을 반환한다. 결과물의 첫 두줄은 16 by 4 array에서 가장 큰 값인 100을 출력하는 상황을 나타내고 있다.

numpy.amax()함수는 추가적으로 axis라는 파라미터를 받을 수 있다. axis는 말 그대로 축을 설정하는 것인데, 행축이나 열축을 기준으로 최대값이 담긴, 또 다른 numpy.ndarray 타입의 array를 반환한다. 주의할 점은 axis=0가 열이라는 점이다. 참고로, axis는 default값이 None이다.

코드 5

 

[1 0 2 3 0]
(array([0, 2, 3]),)
[[1 0 7]
[8 1 0]
[1 0 0]]
(array([0, 0, 1, 1, 2]), array([0, 2, 0, 1, 0]))
[[0 0]
[0 2]
[1 0]
[1 1]
[2 0]]
[1 7 8 1 1]
shape: (4,)
[False False True False]
(array([2]),)
b[0]: [2]
c: [[2]]
(array([2]),)
[[2]]

numpy.nonzero()함수는 0(zero)가 아닌 요소의 인덱스를 반환해주는 함수이다. 위의 코드 5에서 두번째 케이스인 2차원 행렬의 경우가 이해하기 어려울 수 있는데, 2차원 배열에서 0이 아닌 요소의 행 인덱스들이 하나의 array로, 그리고 열 인덱스들이 하나의 array가 되어 총 두 개의 array를 결과물로 받게 된다. 이를 transpose하는 것이 직관적으로 이해하기에 더 편하다.

코드 4와 코드 5를 기반으로 코드 3을 다시 보면,

코드 3

def rargmax(vector): # random argmax의 약자
    import random
    """
    Argmax that chooses randomly among eligible maximum indices.
    """
    m = np.amax(vector)
    condition = (vector == m)
    indices = np.nonzero(condition)[0]
    return random.choice(indices)

먼저, vector라는 파라미터를 받아들인다. 이 파라미터에는 16 by 4 형태의 Q table 중 1 by 4 하나만 들어올 예정이다.

받아들인 array 중 가장 큰 값을 저장하고,

vector변수에서 element-wise하게 m값을 제외한 모든 요소를 False로 만드는 condition을 만든다.

그 다음, 해당 조건을 nonzero()함수에 넣어, 해당 조건에 맞는 인덱스를 뽑아낸다. [0]가 붙은 이유는 결과값이 스칼라 값이 아닌, 1차원으로 array로 나오기 때문으로 보인다.

random.choice()의 예시 코드는 코드 6과 같다.

코드 6

 

따라서, 코드 3에서 최대값이 있다면 단 하나의 최대값에 해당하는 인덱스만이 반환될 것이고, 만일 최대값이 없어서(즉 변수 m이 0이 되어서) condition이 [True True True True]로 나오게 된다면, 네 개의 action([LEFT DOWN RIGHT UP])중 하나의 action을 랜덤하게 선택하게 될 것이다.

이제, 알고리즘 1을 코드로 그대로 구현해보자. 다음 코드 7과 같다.

코드 7

 

Q[state, action] = reward + np.max(Q[new_state,:])에서 np.max(Q[new_state,:])부분은 곧, Q table이 optimal하다는 가정을 깔고 있기 때문에 가능하다.

전체 구현 코드는 코드 8과 같다.

코드 8

 

Success rate: 0.862
Final Q-Table Values
LEFT DOWN RIGHT UP

[[0. 1. 0. 0.]

[0. 0. 0. 0.]

[0. 0. 0. 0.]

[0. 0. 0. 0.]

[0. 1. 0. 0.]

[0. 0. 0. 0.]

[0. 0. 0. 0.]

[0. 0. 0. 0.]

[0. 0. 1. 0.]

[0. 1. 0. 0.]

[0. 0. 0. 0.]

[0. 0. 0. 0.]

[0. 0. 0. 0.]

[0. 0. 1. 0.]

[0. 0. 1. 0.]

[0. 0. 0. 0.]]

그러나, 이러한 방식으로 완성된(학습된) 지도(Q table)가 과연 최선일까? 만약 최선이라면 항상 최선임이 보장되는가 (즉, always convergence to optimal solution)?

그림10

그림 10은 Q가 찾아낸 최적의 루트인데, 실은 우리는 이것이 최적의 루트가 아님을 이미 알고 있다. 우리의 Q function이 최적의 루트를 찾지 못한 이유는 무엇일까? 비유하자면, agent가 새로운 길을 찾아보지 않기 때문이다. 한 번 최적의 루트라고 확정된 경로를 그대로 고수하고, 다른 길은 쳐다보지 않는 것이라고 생각할 수 있다. 그렇다고 무조건 새로운 길을 탐험하는 것이 좋다고 할 수도 없다. 즉 내가 알고 있는 가장 좋은 길 뿐만 아니라, 또 다른 길을 탐험하기를 병행함으로써 가장 좋은 길을 찾을 필요가 있다. 이를 강화학습에서는 Exploit & Exploration 이라고 한다. (Exploit은 내가 이미 가진 것을 이용한다는 것이고, Exploration은 모르는 곳으로 한 번 가본다는 의미이다.)
Q function의 학습에 Exploit & Exploration 아이디어를 실현할 방법은 두 가지인데, 그 중 하나는 E-greedy라는 방법이다. 알고리즘 2-1을 보자.

알고리즘 2-1

 

E-greedy를 실제로 구현하기는 어렵지 않다. e(epsilon) 값을 이용하기만 하면 되기 때문이다. e값을 0.1로 고정시킨 다음, random값을 이용하여, random값이 e값을 넘지 못할 경우 Exploration 하도록 정하고, random값이 e값을 넘을 경우, 기존의 방식인 Q값 (optimal하다고 가정된 Q값)을 이용한다 (즉, Exploit 방식을 채택한다). e값이 0.1이므로, 10%의 확률로 새로운 길을 탐험하게 될 것이고, 90%의 확률로 기존의 방식을 고수하려고 할 것이다.
그러나 매번 10%의 확률로 Exploration 하도록 고정시키는 방법도 최선은 아니다. 지도(Q)가 업데이트 될 수록, 가장 좋은 루트가 어디인지 점차 알게 되는데, 이 상황에서도 Exploration 하도록 고정 시키는 것보다는, Exploration 할 확률을 점진적으로 줄여나가는 것이 더 좋다. 이를 decaying E-greedy라고 한다. 알고리즘 2-2가 이러한 상황을 구현한 코드이다.

알고리즘 2-2

 

agent가 Exploit & Exploration하게 만드는 또 다른 방법은, 알고리즘 3-1과 같이 random noise를 추가하는 것이다.

 

알고리즘 3-1

 

예를 들면, random_noise가 다음과 같이 기존의 Q값에 더해질 것이다.

 

 

즉 [0.6, 0.8, 1.0, 0.5, 0.6]중 가장 큰 값인 1.0의 argument인 인덱스 2를 action으로 선택할 것이다 (noise가 없는 상태에서는 인덱스 1을 선택할 것이다).
random_noise에도 역시 decaying 방법을 적용하는 것이 타당하다.

알고리즘 3-2

 

E-greedy 방법과 random noise 방법의 차이점은, E-greedy의 경우는 완전한 Exploration (다시 말해, 완전한 random selection)인 반면, random noise의 경우는 기존의 Q값에 더해진 값을 이용하기 때문에 완전한 Exploration은 아니라는 점이다. (즉, 기존의 Q값에 대하여 어느 정도의 dependency를 갖는다.)


알고리즘 1-2를 보자.

알고리즘 1-2

알고리즘 1-1에서 randomly하게 선택되던 action이 알고리즘 1-2에서는 좀 더 전략적으로 선택되고 있다.

알고리즘 1-2에 따라 업데이트된 Q table의 예는 그림 11과 같다.

그림11

알고리즘 1-2에 따라 Q는 두 가지 길이 있음을 알게 되었다. (그림 12)

그림12

그런데 길이 두 개라면 어느 길이 더 좋은지에 대해 판단해야 한다. 우리는 지금까지 Q function이 다양한 길을 탐색하도록 하기 위하여, Exploit & Exploration 전략을 사용했다. 그러나 강화학습의 진정한 목적은, 이렇게 하여 찾은 여러 갈래의 길들 중 어느 길이 가장 최선의 길인지를 알아내는 것 곧, 가장 optimal한 policy를 찾아내는 것이다. 따라서, 두 길 중 어느 길이 가장 최선의 길인지를 평가해야 한다. 이 문제를 해결하는 방법은, agent가 받는 피드백(reward)을 전략적으로 부여하는 것이다.

우리가 어떤 보상을 받는다고 할 때, 지금 당장 보상을 받는 것과, 1년 후에 보상받는 것과, 10년 후에 보상받는 것은 다르다. 지금의 물가와 미래의 물가가 다를 뿐만 아니라, 그 기간을 기다리는 시간이 길 수록 실제 보상으로 느껴지지 않을 것이다. 즉, 미래의 보상의 가치는 현재의 시점에서는 크지 않다. 마찬가지로, agent가 받는 보상의 가치 역시 시간에 따라 다르다. 따라서, 미래의 보상의 가치를 낮추어 Q table을 업데이트 하는 전략을 취하도록 한다. 이를 알고리즘 1-3에 나타내었다.

 

알고리즘 1-3

(알고리즘 1-3에서 discounted reward인 gamma는 보통 0.9값으로 주어진다.)


이를 좀더 풀어서 나타내면 다음 수식 3-1과 같다. (알고리즘 1-3의 Q와 수식 3-1의 R_t는 같다.)

수식3-1

수식 3-1은, 곧바로 받을 보상을 100%의 가치로 바라보고, 현재와 먼 보상일수록 0.9(90%)가 거듭 곱해 진 가치로 환산된 보상을 받게 되는 상황을 묘사하고 있다 (수식 3-2와 동일하다).

수식3-2

discounted reward를 적용한 상황을 그림으로 묘사해보면 다음과 같다. 먼저, 그림 13-1은 goal 근처에서 1의 reward를 받은 상황을 나타내며, 그림 13-2는 Q learning이 일어나는 과정을 GIF 이미지로 표현한 것이다.

그림13-1
그림13-2

더 좋은 시뮬레이션을 경험해보고 싶다면, 다음의 사이트를 추천한다.

J. H. Lee, "Q-learning Test," computingkoreanlab.com/app/jAI/jQLearning/

 

RL::Q-Learning

STATUS EPISODE: 0  |   MOVE: 0 times  |   TIME ELAPSED: 0.0 secs  |   Hole: 0 times  |   GOAL: 0 times OPTIONS SIZE: 4 6 8   |   VELOCITY: fast normal slow   |   REPEAT: 1 10 100 1000 * 1 2 3 4 5 6 7 8 9 (1000) times Hole: reward 0 -1 penalty game over go

computingkoreanlab.com

 

그림 14

 

이러한 Exploit & Exploration 방법, 그리고 decaying reward를 적용한 Q learning 방법이 항상 optimal policy로 수렴(convergence)한다는 것은 이미 증명되었다 (단, 환경이 deterministic하고, state의 개수가 한정적일 때).

E-greedy를 적용한 Q learning 코드는 코드 9와 같다 (discounted reward를 위해 gamma인 discounted factor가 함께 적용됨).

코드 9

또 다른 방법인 random noise를 추가하여 Exploit & Exploration 전략을 구현한 것은 코드 10에 나타나 있다 (코드 9와 마찬가지로 discounted factor가 적용됨).

코드 10

지금까지 진행해 온 environment는 deterministic한 환경이었다. 즉 기존의 환경은 어떤 action을 했을 때, 그 action에 대해 기대되는 state가 확정적인, 결정적인 환경이었다. 이러한 환경에서 Exploit & Exploration과 decaying future reward 방법을 적용했을 경우, (E-greedy 기준으로) 적어도 80% 이상의 정확도를 얻었다.

Q function이 항상 optimal policy로 수렴(convergence)된다는 것은 그림 14에서 볼 수 있듯이, 이미 증명되어 있다. 단, 조건은 환경이 deterministic하고, state의 개수가 한정적일 때만 그러하다. 그렇다면, 환경이 deterministic하지 않은 경우에도 convergence할 것인가? 즉, 만약 환경이 deterministic하지 않다면? 즉, 어떤 action을 했을 때, 예를 들면 DOWN으로 가겠다고 했을 때 DOWN으로 가지 않고 여기저기 미끄러지듯 다른 곳으로 가버리는 환경이라면? 이러한 환경을 stochastic한 환경 (또는 non-deterministic한 환경)이라고 부른다. 이러한 환경에서는 agent에게 ‘운’이 적용된다. 즉, 운이 좋으면 action의 의도대로 진행되고, 운이 좋지 않으면 그렇지 않은, 확률적인 환경인 것이다 (변동성이 무척 심한 시계열 데이터처럼 **태생적인 무작위성(inherent randomness)**을 갖는다).

우리는 코드 2에서 이미 deterministic한 환경을 경험했다. 우리가 누른 방향대로 action이 environment에 전달되고 environment는 우리가 원하는 state(와 reward)를 주었다.

이 때, 코드 2에서 눈여겨 볼 부분은 register()메소드를 호출하는 부분이다. 이 코드는 deterministic한 환경을 위해 특별히 들어간 코드이다. 즉, 'is_slippery’를 False로 만들어주기 위하여 들어갔다. 원래의 FrozenLake 환경은 'is_slippery’가 True이다.

stochastic한 FrozenLake 환경을 경험하기 위하여 코드 11을 실행해보자.

코드 11

코드 2와는 다르게 키를 제대로 눌러도 다른 곳으로 가는 것을 관찰할 수 있을 것이다.

그렇다면, 과연 stochastic한 환경에서도 Q learning이 잘 작동할까? 코드 12와 그 결과를 보자.

코드 12

정확도가 무척이나 낮다. stochastic한 세상(environment)에서는 아무리 지도(Q)가 정확하더라도 언제든지 도랑에 빠지거나 잘못된 길로 가버리기 쉽상이다.

 

따라서 지도(Q)를 더이상 100% 신뢰할 수는 없게 되었다. 우리는 이제 지도(Q)를 100%참고하지 않고 조금은 덜 참고할 것이다. 대신 우리는 우리가 생각하기에 좋은 길이라고 생각되는 길에도 어느 정도의 비중을 둘 것이다 (좀 더 비유하자면, 마치 부모님이나 선생님의 말씀을 어느 정도 참고정도만 하는 것과 동일하다).

 

즉, 멘토인 Q의 말을 100% 신뢰하는 것이 아닌 어느 정도만 신뢰하는 전략을 취한다. 따라서, 수식 3-2는 수식 3-3과 같이 바뀐다.

수식 3-2
수식 3-3

또는

수식 3-3을 보면 learning rate인 alpha가 적용된 것을 관찰할 수 있다. alpha값이 0.9라면, 지도(또는 멘토)인 Q를 deterministic한 환경에서 그랬던 것보다는 상대적으로 덜 참고하고, 기존의 Q값에도 어느 정도의 비중을 두는 방식이다.

알고리즘 1-3을 개선한 알고리즘 1-4는 이러한 상황을 반영한 알고리즘이다.

알고리즘 1-4

이러한 방식이 convergence를 보장함은 이미 증명되어 있으나(그림 15), 정말로 잘 작동할까? 우선, 이를 구현한 코드 13을 보자.

그림 15

코드 13

깃헙 소스코드를 기준으로, 기존의 Q learning 알고리즘을 사용할 때에 비하여 정확도가 올라갔지만, 그렇게 높다고는 할 수는 없는 결과를 얻었다. 실험 결과, DISCOUNT_RATE을 0.98로 할 때는 LEARNING_RATE으로 어떤 값을 주어도 0.5를 넘지 못하였다. 그러나 DISCOUNT_RATE를 0.99로 설정한 후, LEARNING_RATE을 0.85로 설정했을 때 정확도가 0.6895로 큰 차이를 보였다. DISCOUNT_RATE이 0.99일 경우에는 LEARNING_RATE에 따라 유의미한 차이가 보였다.

LEARNING_RATE에 따른 정확도 비교

LEARNING_RATE이 클수록 Q의 조언을 크게 받아들인다는 의미이며, LEARNING_RATE이 작으면 자신의 고집을 꺽지 않는다는 의미이다. 즉, 위와 같은 stochastic한 FrozenLake 환경에서 agent는 Q의 조언을 85% 정도 받아들일 때, 가장 높은 정확도를 낸다.

 

우리는 Q function이 항상 optimal policy로 수렴(convergence)한다는 것을 그림 14에서 보았고, 환경이 non-deterministic한 경우에도 convergence하다는 것을 그림 15에서 보았다. 그렇다면, state의 개수가 한정적이지 않은 경우에도 그러할 것인가?

 

그림 14
그림 15
그림 16

 

예를 들어, 그림 16과 같은 80 by 80 픽셀의 grayscale 게임 화면을 입력으로 받을 경우, 2^(8080)개의 state가 발생한다. Q function을 이용하여 FrozenLake에서와 같이 학습을 시킨다면, action이 4개 일 때, 42^(80*80)개의 경우의 수에 대하여 Q table을 작성해야 한다.

즉 실전 문제에 Q table을 사용하기에는 한계가 있다. 따라서, 우리는 이제부터 그림 17과 같이 Q를 Neural Network로 대체하여 이 문제를 해결하고자 한다.

그림 17-1
그림 17-2

 

그림 17-1은 Q function과 동일하게 state와 action을 입력으로 받고 reward(Q value)를 출력하는 Neural Network를 나타내며, 그림 17-2는 state만을 입력으로 받고 각각의 action에 대한 reward(Q value)를 출력으로 내는 Neural Network를 나타낸다. (이하는 그림 17-2를 대상으로 설명한다.)

우리의 목적은 Neural Network가 optimal policy가 되도록 학습(learning or approximation)시키는 것이므로, supervised learning 방식이 그러하듯, Hypothesis와 cost(loss) function을 정의해야 한다. 즉, 우리는 그림 18처럼, 우리 Network의 Hypothesis를 Weight*input과 같이 만들고, Hypothesis가 optimal policy가 되도록(Weight들의 값들이 optimal하게 변하도록) 학습시켜야 한다. 이 때 Hypothesis에 의해 나온 Network의 예측값(추측값)과 optimal policy 사이의 차이를 줄여야 학습이 이루어질 것이다. 즉, optimal policy가 라벨(label)이 되며, 이 policy는 optimal하다고 가정해야만 한다.

 

수식 18

optimal policy는 이미 우리가 공부했듯, 수식 3-2와 같이 주어진다.

수식 3-2

state만을 입력으로 받는 네트워크에서는, optimal Q function(s)을 이용해야 하는 것 아닐까? 모두의 강화학습 강의를 보면서, state만을 입력으로 받는 네트워크에 Q function(s,a)를 이용한다는 점에 의문이 들었다. Hypothesis도 W*s로서, a는 쓰이지 않는데 어떻게 이해해야 할까?

Neural Network를 거쳐서 나오는 우리의 Hypothesis는 그 결과로 네 개의 action에 대한 reward를 낸다. 이 네 개의 action들 중 reward가 가장 높은 argument를 선택할 것이므로, 기존의 수식 3-2를 target으로 사용할 때, action에 대한 reward(Neural Network에 의해 나온 action의 reward)VS action에 대한 reward(수식 3-2에 의해 나온 action의 reward)로, 상호 비교가 가능하다. 따라서, 수식 3-2가 optimal policy로 사용되어도 무방하다.

이 상황을 수학적으로 나타내면 다음 수식 4와 같다.

수식4

 

따라서 목표는 Deep Learning에서와 마찬가지로, Network의 가장 적절한 weight를 찾는 것, 곧 theta값을 찾아내는 것이 목표가 된다. 이를 위하여 (그림 18에서 정의된 loss function을 참고하여,) 다음 수식 5-1과 같은 loss function 최소화(minimization) 과정이 필요하다.

 

수식5-1

이를 알고리즘으로 나타내면 알고리즘 4-1과 같다. (알고리즘 4-1은 DeepMind의 Playing Atari with Deep Reinforcement Learning - University of Toronto by V Mnih et al.로부터 참고하였다.)

알고리즘 4-1

일단, 초기의 Q network의 weight을 random한 값들로 초기화한다. episode는 총 M번을 돈다. 그 다음, 초기 상태(본 논문에서는 게임 화면 이미지)를 Neural Network 학습에 적절하도록, 전처리(preprocess)한다.

한편, 한 번의 episode에 대하여 T번의 학습 과정을 거친다. 즉, action에 대한 평가 결과를 update하는 과정을 거치게 된다. 이 때, action 선택은 E-greedy 방식을 통해 random 값과 epsilon값의 대소 비교를 통하여 random한 action이 선택되거나, 또는 우리의 Q Network가 내는 argmax값(action)을 활용한다 (theta가 붙어있기 때문에 Network이다. 이 때 우리의 Q network는 optimal하다고 가정해야 한다.)

선택된 action을 수행하면 environment는 reward와 state(본 논문에서는 게임 화면 이미지)를 리턴한다. 그리고 리턴받은 새로운 new state(이미지)를 전처리하여 새로운 state로 업데이트한다.

이 논문에서는 optimal policy를 y로 나타내고 있다. y는 두 가지 경우에 따라 다른데, Goal에 도달하거나, Hole에 빠질 경우, 해당하는 reward만 반환하도록 하는 경우와, 그 이외의 Q network가 내는 discounted된 reward값(Q value)을 반환하는 경우이다.

이는 deterministic한 환경이든 non-deterministic한 환경에서든 동일하게 적용된다. 즉 수식 3-3을 non-terminal 케이스에서 사용하지 않는다. (why?)

수식3-3

이렇게 하여 반환된 label값(target값)과 Q network가 낸 값(Hypothesis)의 차이를 Gradient Descent하는 방식으로 Network의 Weight를 업데이트한다.

즉, 이전 timestep의 Q network와 그 다음 timestep의 Q network 사이의 차이를 줄이는 방식이며, 동일한 Network parameter(Weight)을 사용한다.

그림19

우리의 state는 총 16개(0~15)이다. 구현적인 측면에서, Neural Network에 입력으로 state만을 입력시킨다고 할 때, state정보를 그림 19와 같이 one-hot encoding 방식으로 인코딩하여 state전체(16개의 정보)를 Network의 input으로 준다.

Network의 출력에 해당하는 W*s의 결과는 4개의 값으로 나온다. 이로써, 각각의 action에 해당하는 Network의 평가값이 나오게 된다.

FrozenLake를 위한 one-hot encoding을 만드는 방법은 코드 13과 같이 numpy.identify() 를 이용한다.

 

코드 13

[[0. 1. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]]

 

Q network를 TensorFlow를 이용하여 구현한 코드는 코드 14와 같다. (그림 17-2의 상황이다.)

그림17-2

Percent of successful episodes: 0.3765%

 

먼저, environment를 만들어준다. environment는 stochastic한 환경이다.

input으로 줄 내용인 변수 X는 Placeholder를 이용하고, 지속적인 update가 필요한 Network의 Weight에 해당하는 변수 W는 Variabel로 만든다. Weight은 16 by 4 의 크기를 갖는다. Qpred = tf.matmul(X, W) 부분은 우리의 Hypothesis에 해당하며 1 by 4의 크기를 갖는다. 변수 Y는 target 값이며, target값은 4개의 action에 대한 reward값이므로, 1 by 4 의 크기를 갖는다.

우리의 loss function은 target인 Y와 Hypothesis가 낸 값인 Qpred의 차이이므로, loss = tf.reduce_sum(tf.square(Y - Qpred))이다. loss function에 대한 minimization은 AdamOptimizer를 이용한다.

Qs = sess.run(Qpred, feed_dict={X: one_hot(s)})는 TensorFlow에서 Hypothesis에 따라 실제 Neural Network를 실행시키는 부분이다. 여기서 Network의 추측값이 Qs에 저장된다.

action은 E-greedy에 따라 선택되며, 특히, Qs에 의해 선택되는 action은 Qpred의 weight에 따라 결정된 가장 큰 argument가 선택된다.

step()에 의하여 environment와 상호작용하여 s1, reward, done, _와 같은 변수들을 리턴는다. 이 때, Hole 또는 Goal에 도달했을 때에는 Qs가 reward만으로 업데이트된다. 반면, Hole이나 Goal에 도달하지 않은 상황이라면, 다음 상태인 s1에 대한 Qpred를 수행하여 target으로 사용할 Qs를 얻는다.

Qs[0, a] = reward와 Qs[0, a] = reward + dis * np.max(Qs1)에서, 2차원인 Qpred를 평가한 값이 1 by 4 array로 결과가 나온다. 즉, 결과가 2차원 array로 나온다. 따라서 Qs[0, a]와 같은 방식으로 접근하여, Qs를 업데이트한다.

X(이전 state;s)에 대한 Y(정답, 타겟, 라벨)를 Qs가 가지고 있으므로, 이를 이용하여 Network를 train시켜, 기존의 Qpred값과 비교하여, Qpred속에 있는 변수 중, 변경 가능한 변수인(Variable인) Weight을 업데이트시킨다.

마지막으로 현재 state인 s를 새로운 state인 s1으로 업데이트한다.

코드를 이해하기 쉽도록 그림으로 그려보면 다음과 같다.

그림20-1

X와 W의 모습의 예시를 그림 20-1에 보여주고 있다.

그림20-2

이에 따른 Qpred와 target인 Y의 예를 그림 20-2에 보여주고 있다.

그림20-3

위의 그림 20-3의 loss 값이 Adam Optimization에 적용되어, Variable인 W 값이 좀 더 optimal해지도록 업데이트된다.

 

코드가 수행된 결과를 보니, 생각보다 높지 않다. 그 이유는 무엇일까? 근본적인 이유는, optimal policy로 수렴하지 않기 때문이다. 즉 이러한 Q network을 사용하는 방법이 과연 convergence할 것인가?라고 질문한다면, 이 방식(Reinforcement Learning에 Neural Network를 사용하는 방식)은 convergence하지 않고, diverge한다고 할 수 있다. (다음의 사이트들을 참고한다.)

그림19

 

디테일 하게 그 이유를 들여다보자. optimal policy로 수렴하지 않는 데에는 세 가지 이유가 있다.

첫번째 이유로, Network가 너무 단순하고 얕다(Shallow Network).

두번째 이유로, input으로 들어가는 dataset들 간에 correlation이 크다는 점이다 (correlation between samples). 즉, 독립적인 사건이 아닌, 서로간의 dependency를 갖는 데이터들을 이용하여 Network를 학습시키기 때문에, 제대로 된 parameter update가 일어나지 않는다. 이를 해결하려면, 데이터들 간의 연관성이 떨어져야만 한다 (correlation이 낮아져야만 한다). 쉽게 얘기하자면, 유클리드 공간상에서, sample들 간의 거리가 서로 멀리 떨어져 있어야 한다. 아래의 그림 21-1을 보자.

그림21-1

전체 데이터셋이 이러한 모습이라고 할 때, 최적화된 모델은 다음 그림 21-2와 같을 것이다.

 

그림21-2

서로 correlation이 높은 데이터 셋만을 가지고 모델을 학습시키게 될 경우의 예는 그림 21-3과 같다. 극단적인 예로서, 서로 붙어있는 세 개의 샘플로 최적화된 모델을 만든다고 할 때의 상황이다.

 

그림21-3

초록색이 optimal한 모델이라고 할 때, 파란색 모델, 노란색 모델, 빨간색 모델 모두 최적화된 모델인 초록색 모델과는 상당한 차이를 보인다. 그렇다면, 데이터셋들끼리 correlation이 적은(데이터셋들끼리 서로 멀리 떨어진) 경우는 어떠할까? 그림 21-4를 보자.

 

그림21-4

correlation낮은 데이터셋끼리 학습한 모델의 경우, 최적 모델과 상당히 유사한 모습을 보인다.

세번째 이유는, non-staionary targets문제이다. target이 고정적이지 않고 계속 움직인다는 것이다. 우리 Q-network에서 target은 수식 6과 같다.

수식6

모델이 내는 예측값은 수식 7과 같다.

수식7

그리고 Network의 parameter는 수식 5-1로 표현된 loss function을 minimization하면서 update된다.

수식5-1

이 때, 예측값을 내는 데에 사용되는 네트워크(theta)와 target값을 내는 데에 사용되는 네트워크(theta)가 같은 네트워크인 것을 알 수 있다. 즉, 모델이 target과의 차이(error)를 줄이기 위해 네트워크를 업데이트 시키는 순간, target의 네트워크도 함께 업데이트된다. 이런식으로 계속해서 target 네트워크가 움직이기 때문에, 모델은 stationary하지 않은 target과의 error를 줄이는 과정을 반복한다고 할 수 있다. 따라서, 이 두 네트워크를 분리시킬 필요가 있다.

Q-network가 optimal policy로 수렴하지 않게하는 세 가지 문제를 DeepMind에서는 다음의 solution으로 해결하고 있다.

  1. Using Deep Network
  2. Capture and Replay
  3. Separate Networks; Create a target network

위 세 가지 아이디어가 녹아든 Q-network를 Deep Q Network, 줄여서 DQN이라고 부른다.

첫번째 아이디어는 weight과 hidden layer를 추가함으로써 해결가능하다. 두번째 아이디어를 구현하기 위해서, 모든 데이터는 즉각적으로 Network에 들어가는 대신, buffer에 저장되는 방식을 취한다.

 

그림22

loss function 최소화에 쓰이는 데이터인 state, action, reward, 그리고 그 다음 state를 계속 쌓아둔 후(→capture), 일정 시간 이후에 buffer에 쌓인 데이터 중 random하게 데이터를 뽑아서 학습에 사용한다. random하게 뽑는 것이 곧 데이터간의 correlation을 피하는 방법이다 (단, 정규분포를 따르도록 random selection이 일어나야 할 것이다). 알고리즘 4-1을 개선한 알고리즘인 4-2를 보자.

알고리즘 4-2

버퍼 D에 해당 정보들을 저장하고, 버퍼 D에서 해당 정보들을 랜덤하게 선택한다는 내용이 중간에 추가되었다. 이러한 방식을 사용하여, 모델이 조금씩 개선되어 최적화된 parameter를 얻을 수 있게 된다.

 

세번째 아이디어를 구현하기 위해서, 우리는 네트워크를 분리한다고 했다. 수식 5-2를 보자.

수식5-2

theta와 theta_bar로 표현된 서로 다른 두 네트워크를 이용함을 확인할 수 있다. 따라서 이 두 네트워크를 모두 update해야 할 필요가 있다. update할 때, target에 해당하는 네트워크는 한동안 update되지 않는다. 그러나 주기적으로 Q의 parameter값들이 target network로 한번에 copy&paste되는 방식으로 update된다. 이 상황이 알고리즘 4-3에 나타나있다.

알고리즘 4-3

전체적인 사항은 알고리즘 4-1과 같으나, 세부적인 차이점은, 두 개의 네트워크(theta, theta_bar)를 만들며 초기값은 두 네트워크가 동일하게 만든다는 점, 버퍼 D에 정보들을 저장한 다음, 랜덤하게 선택된 미니배치들을 이용하여 target을 설정한 다음, 이를 학습에 사용하여 paramter를 update시킨다는 점, 그리고 C step마다 target 네트워크를 업데이트한다는 점이다.

 

DQN이 리플레이 메모리를 사용하는 것은 장점이자 단점이 된다. 리플레이 메모리를 사용하기 때문에 데이터 간의 상관관계를 낮추고 고르게 분포된 데이터로 학습할 수 있게 하여, 결국엔 네트워크가 수렴되게 한다. 그러나 한편, 리플레이 메모리를 사용하기 위해서는 큰 메모리 공간이 요구된다. 또한 메모리에 저장된 오래된 데이터도 학습에 이용한다는 단점이 존재한다.

 

Reference

반응형
저작자표시 비영리 변경금지

티스토리툴바