강화학습을 위한 마르코프 결정 과정(MDP)과 벨만 기대 방정식

이번 글은 ‘파이썬과 케라스로 배우는 강화학습’ 책과 여러 포스트를 참고하여 강화학습의 기초가 되는 Markov Decision Process(MDP, 마르코프 결정 과정)와 Bellman 기대 방정식에 대해 정리한 내용을 담고 있다.



강화학습은 좋은 행동을 점점 더 많이 하게 하는 것 즉, 강화의 개념을 컴퓨터 학습에 적용시킨 것이다. 어떠한 환경 내에 주어진 에이전트(컴퓨터)는 현재 자신의 상태를 인식하여 선택 가능한 행동들 중에서 보상을 최대화하는 행동 혹은 적절한 행동 순서를 스스로 선택한다. 이를 통해 최적의 행동 방식 또는 정책을 찾아가는 것이 강화학습의 목적이라고 할 수 있다.

컴퓨터에게 어떤 문제를 풀게 하기 위해서는 해당 문제를 수학적으로 정의해야 하는데 일반적으로 강화학습이 풀고자 하는 순차적 행동 결정 문제는 MDP로 정의할 수 있다.



Markov Decision Process (MDP, 마르코프 결정 과정)

MDP는 순차적으로 행동을 결정해야 하는 문제를 풀기 위해 수학적으로 표현한 것으로, [그림 1]과 같이 상태, 행동, 상태 변환 확률, 보상 함수 그리고 감가율까지 총 5개의 요소들로 이루어져 있다.



[그림 1] 마르코프 결정 과정(MDP)의 구성 요소



각각의 요소들을 자세히 한 번 살펴보자.


아래의 내용들은 [그림 2]를 참고하면 더 쉽게 이해할 수 있을 것이다. 참고로 [그림 2]는 MDP를 이해하기 위한 대표적인 예시로 5 X 5 크기의 그리드 환경을 조성한 것이다.



첫 번째 S에이전트가 관찰 가능한 상태의 집합을 뜻한다. [그림 2]의 그리드 월드와 같이 5 x 5 크기로 정해진 환경에서 각 좌표는 하나의 상태가 될 수 있으며, 이 모든 (x, y) 좌표들을 나열한 것이 상태의 집합이 된다. 사용자는 이러한 상태를 정의하여 에이전트가 학습할 수 있는 환경을 조성해주어야 한다.



[그림 2] MDP의 대표적인 예시 - 그리드 월드 (5x5)



[그림 2]를 통해 간단히 살펴보면, 에이전트의 현재 위치는 (1, 1)에 있기 때문에 상태는 (1, 1)이라고 할 수 있다. 이후 에이전트는 시간의 흐름에 따라 S의 상태들을 돌아다니게 되는데, 시간이 t일 때 상태 S_t는 (1, 2)일 수도 있고, (3, 3)일 수도 있다. 이처럼 시간 t에 에이전트가 있을 수 있는 상태는 얼마든지 달라질 수 있기 때문에 이를 확률변수라고 표현한다.

두 번째 A는 상태 S_t에서 할 수 있는 가능한 행동들의 집합을 뜻한다. [그림 2]와 같은 그리드 월드에서는 왼쪽, 오른쪽, 위, 아래로만 이동할 수 있고 이 네 가지가 행동의 집합이 된다. 에이전트가 다음 시간에 할 행동이 딱 정해져 있는 것이 아니기 때문에 이 또한 A_t로 표현해준다.



[그림 3-1] 시간 t에서의 상태




[그림 3-2] 시간 t에서의 행동 수식



에이전트가 만약 어떤 상태에 있다가 행동을 취하게 되면 s에서 s’의 상태로 변화하게 될 것이다. 하지만 어떤 행동 a를 취했다 하더라도 s’에 도달하지 못할 가능성이 존재하는데 이러한 확률적인 요인들을 수치로 표현한 것이 세 번째인 상태 변환 확률 P다.



[그림 4] 상태 s에서 행동 a를 했을 때 또 다른 상태인 s’에 도달할 확률 (상태 변환 확률) 수식



이 값 자체는 조성된 환경의 일부일 뿐 에이전트가 알 수 있는 값은 아니다. 그렇기 때문에 환경은 에이전트가 어떠한 행동을 취했을 때 상태 변환 확률을 통해 에이전트가 가야 할 상태를 알려주게 된다.

다음은 보상 함수 R이다. 보상은 에이전트가 학습할 수 있는 유일한 정보로써 환경이 에이전트에게 제공하는 정보라고 할 수 있다. 만약 시간 t에서 상태 S_t=s이고, 행동 A_t=a라고 할 때 에이전트가 받을 보상은 [그림 5]와 같다.



[그림 5] 시간 t에서 상태가 S_t=s이고 행동이 A_t=a일 때 에이전트가 받을 보상 (보상함수) 수식



보상함수가 받을 보상에 대해 기댓값(E)으로 표현하는 이유는 어떠한 정확한 값을 추출해 내는 것이 아니라 나오게 될 숫자에 대한 예상을 하는 것이기 때문이다. 에이전트에게 보상을 주는 것은 주어진 환경이고 상황에 따라 같은 행동을 하더라도 다른 보상을 줄 수도 있기 때문에 여러 가지 상황을 고려하여 기댓값으로 표현한다.

여기서 중요한 점은 에이전트가 현재 행동을 한 것에 대한 보상을 t 시간에 받는 것이 아니라 t+1 시간에 받게 된다는 것이다. 그 이유는 위에서 봤던 것처럼 상태가 변화할 때 환경이 에이전트에게 정보를 알려주는 것이기 때문에 상태가 변한 시점인 t+1 시간에 보상 R_(t+1)을 받게 된다.

추가로, [그림 2]를 보면 에이전트가 깃발이 있는 (4, 4)의 상태로 가는 행동을 했을 때는 +1의 보상을 받게 되고, 폭탄이 있는 (2, 4)나 (3, 2)의 상태로 가는 행동을 했을 때는 -1의 보상을 받게 된다. 목적지인 깃발에 도달했다고 하더라도 도착의 의미로 보상을 주는 것이 아니라 목적지로 가는 동안 좋은 행동을 했기 때문에 보상을 준 것이라고 할 수 있다.

마지막 요소는 감가율이다. 참고한 책에는 감가율이라고 나와있지만 할인 요인(Discount Factor)이라고 부르는 곳도 상당히 많이 있다. 어찌 됐든 에이전트는 현재 상태를 기준으로 판단을 하기 때문에 당장 가까이 보이는 보상일수록 더 큰 가치로 여긴다. 하지만 미래에 받을 수 있는 보상도 고려를 해야 되기 때문에 현재 시간 t로부터 시간 k가 지난 후 받을 수 있는 보상을 [그림 6]과 같이 계산한다. 이를 토대로 보면 시간이 지나면 지날수록 에이전트가 받을 수 있는 보상의 크기는 점점 줄어들 것이다. (감가율은 0에서 1 사이의 값을 가진다.)



[그림 6] 감가율을 고려한 미래 보상의 현재 가치 수식



MDP에 포함되는 요소에 대해서는 어느 정도 설명을 마쳤다. 쉽게 이해하기는 어려운 내용이지만 반복적으로 보다 보면 익숙해질 수 있을 것이라 생각한다.

다음으로 중요한 내용은 바로 정책 (Policy)이다. 정책은 모든 상태에서 에이전트가 할 행동을 보여주는데, 에이전트는 강화학습을 통해 수많은 정책들 중에서 최적 정책을 찾아야 한다.



[그림 7] S_t=s에 에이전트가 있을 때 가능한 행동 중 A_t=a를 할 확률 (정책) 수식



수식에서 정책에 대한 기호는 π로 표현한다. [그림 2]를 예로 들어 정책을 설명해보면, 에이전트가 예상하는 행동 경로가 모든 상태에 나타나 있음을 말한다. 즉, 각 좌표마다 이동할 수 있는 경로를 예상할 수 있어 에이전트가 자신이 해야 할 행동을 알 수 있다는 것이다.


사실 이 부분에 대한 내용은 직접 예시를 넣어서 수치적으로 계산을 해보면 좋겠지만 이론 설명만으로 넘어가도록 하겠다.



가치함수

에이전트는 행동을 통해 환경으로부터 다음 상태와 보상에 대한 정보를 알게 되었고, 이러한 과정을 반복하면서 최종적인 보상이 가장 많은 경우가 될 때까지 정책을 바꿔나가며 학습하게 된다.


그렇다면 에이전트는 매번 어떻게 행동을 선택할 수 있을까?


그 방법에는 두 가지 관점이 있다. 한 가지는 단기적 관점 그리고 또 다른 한 가지는 장기적 관점이다.

단기적 관점으로 보면 에이전트가 상태를 관찰하면서 가치함수에 따라 행동을 선택하게 되고 환경으로부터 보상을 받게 되는데 에이전트는 시간이 증가할 때마다 큰 보상을 위주로 받으려고 하게 된다. 이러한 경우 최적의 정책에 도달할 수 있을 지에 대한 가능성에 의문이 생길 수 있다.

장기적 관점에는 일련의 보상들의 단순합, 반환값, 그리고 가치함수가 있다.

단순합의 경우 앞으로 받을 수 있는 보상의 모든 합을 더하게 되는데 에이전트 입장에서는 지금 받은 보상이나 미래에 받는 보상 모두 똑같이 취급하기 때문에 시간에 따른 보상 혹은 한 번에 받는 보상과 여러 번 나눠서 받는 보상 등을 구분할 수 없게 된다. 결국 단순한 보상의 합으로는 판단을 내리기 쉽지 않다.

반환값의 경우 앞서 말했던 감가율을 고려하여 보상을 얻게 된다. 이 경우 목적지에 도달했을 때 그동안 받았던 보상을 정산하게 되는 구조로 되어 있는데 [그림 8]과 같은 수식으로 확인할 수 있다.



[그림 8] 에이전트가 환경을 탐험하며 받은 보상의 합 (반환값) 수식



다음은 가치함수이다. 기존 반환값 같은 경우 목적지에 도달해야만 보상을 확인할 수 있었는데, 때로는 정확한 값을 얻기 위해 끝까지 기다리는 것보다 완전하지는 않더라도 현재 정보를 토대로 행동하는 것이 나을 때가 있다고 판단하여 직접 경험해보지 않고도 기댓값에 의해 보상을 예측하는 방식을 도입하였다.



[그림 9] 가치함수 수식



기존의 가치함수와 기댓값의 기호 밑에 정책에 대한 내용을 써주게 되면 정책을 고려한 가치함수가 되며, 강화학습에서 상당히 중요한 벨만 기대 방정식이 된다. 벨만 기대 방정식은 현재 상태의 가치함수와 다음 상태의 가치함수 사이의 관계를 말해주는 방정식으로, 이러한 벨만 방정식을 어떻게 풀어가느냐가 강화학습의 관건이다.



[그림 10] 벨만 기대 방정식



마지막으로 큐함수에 대해 설명하고 글을 마치려고 한다.

위에 설명한 가치함수는 상태 가치함수로, 상태가 입력으로 들어오면 그 상태에서 앞으로 받을 보상의 합을 출력하는 함수가 가치함수였다. 그래서 에이전트는 가치함수를 통해 자신이 어떤 상태에 있는 것이 어느 정도로 좋은지 알 수 있었다.

만약 어떤 상태에서 각 행동별로 따로 가치함수를 만들어서 그 정보를 얻어올 수 있다면 다음 상태의 가치함수를 따져보지 않아도 어떤 행동을 선택해야 좋을지 선택할 수 있다. 이와 같이 어떤 상태에서 어떤 행동이 어느 정도로 좋은지 알려주는 것을 행동 가치함수라고 하며 동시에 큐함수라고 부른다.



[그림 11] 큐함수 수식



강화학습에 대한 내용을 이번에 처음 다루게 되면서 벨만 기대 방정식까지 공부하게 되었는데 관련 내용에 대한 수식이 상당히 많고 아직은 조금 더 이해가 필요할 듯하다. 벨만 최적 방정식에 대해서는 추후 기회가 되면 다루어보도록 하겠다.



Reference



CURG 원본 링크: https://medium.com/curg/%EA%B0%95%ED%99%94%ED%95%99%EC%8A%B5%EC%9D%84-%EC%9C%84%ED%95%9C-%EB%A7%88%EB%A5%B4%EC%BD%94%ED%94%84-%EA%B2%B0%EC%A0%95-%EA%B3%BC%EC%A0%95-mdp-%EA%B3%BC-%EB%B2%A8%EB%A7%8C-%EA%B8%B0%EB%8C%80-%EB%B0%A9%EC%A0%95%EC%8B%9D-d205388f3015

강화학습을 위한 마르코프 결정 과정(MDP)과 벨만 기대 방정식

https://y8ncastle.world/2020/08/07/curg/ai/mdp/

Author

Alec J

Posted on

2020-08-07

Updated on

2021-02-09

Licensed under