문제를 풀기 위해서는 먼저 문제가 잘 정의되어야 한다. 강화 학습에서 문제를 잘 정의하려면 주어진 문제를 MDP의 형태로 만들어야 한다.
이번 챕터의 목적은 MDP가 무엇인지 잘 이해하는 것이다.
2.1 마르코프 프로세스
그림은 아이가 잠이 들 때 벌어지는 상황을 마르코프 프로세스로 모델링 한 그림이다.
아이가 취할 수 있는 상태의 종류는 총 5가지이다.
아이가 상태에 진입하게 되면 해당 상태에서 1분씩 머물게 된다.
1분이 지나면 다음 상태로 상태 전이를 한다. (현재 상태에서 다음 상태로 넘어간다는 말)
아이는 1분 동안 누워있다가 40% 확률로 일어나서 노는 상태 \(s_1\)으로 전이하거나, 60%의 확률로 눈을 감은 상태로 넘어간다. 1분이 지나 상태 전이를 해야 할 때, 90%의 확률로 \(s_1\)에 그대로 머무르게 된다.
운 좋게 \(s_0\)으로 돌아온 후 \(s_2\)인 눈을 감은 상태로 상태가 바뀌었다면 확률에 따라 다음 상태가 결정된다.
종료 상태인 \(s_4\)에 도달하는 순간 마르코프 프로세스는 끝이 난다.
Markov Process를 앞으로 MP라고 부르자.
MP ≡ (S, P)
S : 상태의 집합
- 가능한 상태들을 모두 모아놓은 집합. 아이가 잠드는 마르코프 프로세스의 경우에는 집합의 원소가 5개로, } 였다.
P : 전이 확률 행렬
- \(P_{ss'}\)
- 전이 확률은 상태 s에서 다음 상태 s'에 도착할 확률을 가리킨다.
위의 마르코프 프로세스에서 \(s_0\)에서 \(s_2\)에 도달할 확률은 60%였다.
이를 수식으로 표현하면 \(P_{s0s2}\) = 0.6이 된다.
조건부 확률이라는 개념을 이용해서 표현해보자
\(P_{ss'}\) = P[ \(S_{t+1}\)=s' | \(S_t\) = s ]
마르코프 프로세스는 정해진 간격(위 예시에서는 1분 간격)으로 상태가 바뀐다.
시점 t에서 상태가 s였다는 것을 조건부 확률의 조건 부분에 집어넣는다.
시점 t에서 상태가 s였다면 t+1에서의 상태가 s'이 될 확률이라는 뜻이다.
*) 전이 확률이라고 하지않고 전이 확률 행렬이라고 하는 이유는 뭘까?
\(P_{ss'}\) 값을 각 상태 s와 s'에 대해 행렬 형태로 표현할 수 있기 때문이다.
마르코프 성질
이 과정의 이름이 왜 마르코프 프로세스일까?
-> 마르코프 프로세스의 모든 상태가 마르코프 성질을 따르기 때문이다.
마르코프 성질이란?
-> 미래는 오로지 현재에 의해 결정된다.
마르코프한 상태
예를 들면 체스 게임이 있다. -> 다음 둘 수를 판단할 때 현재 체스판의 상태를 분석해야 한다. 현재 상황에서 해야 하는 일과 과거 경기 양상이 어떠했는지 여부는 아무런 관련이 없다는 뜻이다.
마르코프 하지 않은 상태
반면 운전자의 상태를 생각해보자. -> 운전자의 주변 상황을 사진으로 찍어놓고 해당 상태에서 브레이크나 엑셀을 밟아야 할 지는? 결정할 수 없다.
(하지만 1초마다 주변 상황을 찍어 과거 사진 10장(즉 10초전 상황)을 하나의 상태로 묶어서 제공한다면 다음 상황을 고려할 수 있다.)
어떤 현상을 마르코프 프로세스로 모델링 하려면 상태가 마르코프 해야 하며, 단일 상태 정보만으로도 정보가 충분하도록 상태를 잘 구성해야 한다.
2.1 마르코프 리워드 프로세스(MRP)
아이가 잠이 드는 MRP
아까 보았던 아이가 잠이 드는 MP에 보상 값 R이 추가되었다.
아까의 마르코프 프로세스는 상태의 집합 S와 전이 확률 행렬 P로 정의 되었는데, MRP를 정의하기 위해서는 R과 γ라는 2가지 요소가 추가로 필요하다. R = 보상함수, γ = 감쇠 인자
MP ≡ (S, P, R, γ)
S : 상태의 집합
- 마르코프 프로세스의 S와 같고, 상태의 집합이다.
P : 전이 확률 행렬
- 마르코프 프로세스의 P와 같고, 상태 s에서 s'으로 갈 확률을 행렬의 형태로 표현한 것이다.
R : 보상 함수
- 어떤 상태 s에 도착했을 때 받게 되는 보상을 의미한다.
R을 수식으로 표현해보자.
R = E [ \(R_t\) | \(S_t\) = s ]
기댓값(E)이 등장한 이유는 특정 상태에 도달했을 때 받는 보상이 매번 조금씩 다를 수도 있기 때문이다.
(어떤 상태에 도달하면, 500원 짜리 동전을 던져서 앞면이 나오면 500원을 갖는다고하자. 이 경우 기댓값은 250원으로 정해진다.)
γ : 감쇠 인자
- γ는 0~1 사이의 숫자이다. 강화 학습에서 미래 얻을 보상에 비해 당장 얻는 보상을 얼마나 더 중요하게 여길 것인지를 나타내는 파라미터이다.
구체적으로는 미래에 얻을 보상의 값에 γ가 여러 번 곱해지며 그 값을 작게 만드는 역할을 하기에 감쇠라는 단어가 쓰였다. 리턴을 이해하면 γ의 의미를 진정으로 이해할 수 있다.
감쇠된 보상의 합, 리턴 \(G_t\)
MRP에서는 MP와 다르게 상태가 바뀔 때마다 해당하는 보상을 얻는다.
상태 \(s_0\)에서 보상 \(R_0\)을 받고 시작하여 종료 상태인 \(s_T\)에 도착할 때 보상 \(R_T\)를 받으며 끝이 난다.
이와 같은 하나의 여정을 강화 학습에서는 에피소드라고 한다.
이런 표기법을 이용해 리턴을 정의할 수 있다. 리턴이란 t시점부터 미래에 받을 감쇠된 보상의 합을 말한다.
\(G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3}\) + ...
현재에서 멀어질수록 γ가 여러 번 곱해진다. 여러 번 곱해질수록 그 값은 점점 0에 가까워진다. (0에서 1사이의 실수이기 때문에) 따라서 γ의 크기를 통해 미래에 얻게 될 보상보다 현재 얻는 보상에 가중치를 줄 수 있다.
강화 학습은 보상이 아니라 리턴을 최대화하도록 학습하는 것이다. 보상의 합인 리턴이 바로 우리가 최대화하고 싶은 궁극의 목표이다.
여기서 리턴이 과거의 보상을 고려하지 않고 미래의 보상을 통해 정의된다는 것을 유념해야 한다.
시점 t에 오기까지 그 이전에 100의 보상을 받았던 1000의 보상을 받았건 상관 없다. 에이전트의 목적은 지금부터 미래의 받을 보상의 합인 \(G_t\)를 최대화 하는 것이다.
γ는 왜 필요할까?
1. 수학적 편리성
감마 γ를 1보다 작게 해줌으로써 리턴\(G_t\)가 무한의 값을 가지는 것을 방지할 수 있기 때문이다.
리턴이 무한한 값을 가질 수 없게 된 덕분에 이와 관련된 여러 이론들을 수학적으로 증명하기가 한결 수월해진다.
MRP를 진행하는 도중 다양한 값의 보상을 받을 수 있는데(+1, -1, +10 등) 이 보상이 항상 어떤 상수 이하임을 보장할 수 있다면 MRP를 무한한 스텝동안 진행하더라도 리턴\(G_t\)의 값은 절대 무한한 값이 될 수 없다.
리턴이 무한하다면 어느 쪽이 더 좋을지 비교하기도 어렵고, 그 값을 정확하게 예측하기도 어려워진다. 감마 γ가 1보다 작은 덕분에 이 모든 것이 가능해진다.
2. 사람의 선호 반영
사람은 기본적으로 당장 벌어지는 눈앞의 보상을 더 선호한다. 따라서 에이전트를 학습하는데 있어서 감마의 개념을 도입한다.
3. 미래에 대한 불확실성 반영
미래는 불확실성 투성이다. 현재와 미래 사이에는 다양한 확률적 요소들이 있고 이로 인해 당장 느끼는 가치에 비해 미래에 느끼는 가치가 달라질 수 있다. 그렇기 때문에 미래의 가치에는 불확실성을 반영하고자 감쇠를 해준다.
MRP에서 각 상태의 밸류 평가하기
만일 어떤 상태의 가치를 평가하고 싶다면 어떤 값을 사용하면 좋을까요?
예를 들어 아이가 잠드는 MRP에서 눈을 감고 있는 상태 \(s_2\)의 밸류 혹은 가치를 숫자 하나로 평가하고 싶은 경우가 있다.
가장 먼저 떠오르는 생각은 보상이 높을수록 좋은 상태일 것이라는 점이다. 받은 보상을 모두 더해보자.
그런데 \(s_2\)에 도달하기까지 그 이전에 받은 보상이 중요할까, 아니면 이후에 받을 보상이 중요할까?
예를 들어 사람들이 선망하는 기업인 구글에 입사하는 것의 가치를 평가해보자. 구글에서 앞으로 받을 연봉이 매우 높기 때문일까, 구글에 입사하기까지 많은 돈을 받아서(?)일까.
어떤 상태를 평가할 때에는 당연히 그 시점으로부터 미래에 일어날 보상을 기준으로 평가해야 한다.
우리는 마침 그에 해당하는 값을 알고 있다. 그것은 바로 리턴이다.
리턴\(G_t\)은 그 시점부터 이후에 받을 보상들을 (감쇠하여) 더한 값이다.
한가지 문제가 있다면 그 리턴이라는 값이 매번 바뀐다는 점이다. MRP자체가 확률적인 요소에 의해 다음 상태가 정해지기 때문이다. 그렇다면 \(s_2\)의 밸류를 어떻게 평가해야 할까?
정답은 리턴\(G_t\)의 기댓값을 사용하는 것이다.
에피소드의 샘플링
시작 상태 \(s_0\)에서 출발하여 종료 상태 \(s_T\)까지 가는 하나의 여정을 에피소드라고 했다.
그런데 하나의 에피소드 안에서 방문하는 상태들은 매번 다르다. \(s_1\)은 방문할 수도 있고, 방문하지 않을 수도 있다. 그리고 그에 따라 리턴\(G_t\)도 달라진다.
즉 매번 에피소드가 어떻게 샘플링되느냐에 따라 리턴\(G_t\)이 달라진다는 말이다. 그렇다면 샘플링이란?
샘플을 뽑아본다는 뜻을 가진다. 어떤 확률 분포가 있을 때 해당 분포에서 샘플을 뽑아보는 것이 샘플링이다.
동전 X의 확률 분포는 다음과 같다.
P(X = 앞면) = 0.5
P(X = 뒷면) = 0.5
우리는 샘플링을 통해서 어떤 값을 유추하는 방법론을 사용하게 된다. 이를 몬테카를로 접근법이라고 하는데 앞으로 더 자세히 배울 예정이다.
정리하면 위와 같은 샘플링 기법을 통해 주어진 MRP에서 여러 에피소드를 샘플링해 볼 수 있다. 각 상태마다 다음 상태를 샘플링하며 진행하면 언젠가 종료 상태에 도달할 것이고 하나의 에피소드가 끝이 난다.
요점은 우리에게 P(전이 확률 행렬)가 주어져 있기 때문에 이런 샘플들은 원한다면 무한히 뽑아낼 수 있다는 것이다.
상태 가치 함수
상태 가치 함수는 상태를 인풋으로 넣으면 그 상태의 밸류를 아웃풋으로 출력하는 함수이다. 앞서 살펴본 것처럼 에피소드마다 리턴이 다르기 때문에 어떤 상태 s의 밸류 v(s)는 기댓값을 이용하여 정의한다.
v(s) = E [ \(G_t\) | \(S_t\) = s ]
상태 s로부터 시작하여 얻는 리턴의 기댓값
조건부로 붙은 \(s_T\) = s의 의미는 시점 t에서 상태 s부터 시작하여 에피소드가 끝날 때까지의 리턴을 계산하라는 뜻이 된다.
위 그림과 같이 \(s_0\)에서 출발하여 발생할 수 있는 에피소드는 무한히 많고, 그때마다 리턴도 항상 다르다.
기댓값을 구하려면 에피소드별로 해당 에피소드가 발생할 확률과 그때의 리턴 값을 곱해서 더해줘야 한다. 그러나 가능한 에피소드가 무한히 많기 때문에 이런 접근법은 현실적으로 불가능하다.
간단한 방법은 샘플로 얻은 리턴의 평균을 통해 밸류를 근사하게나마 계산해볼 수 있다.
위의 그림에서는 4.3, 4.6, 6.2, 5.4의 평균인 5.1이 v( \(s_0\) )가 된다.
<<정리>>
- MP = (S, P)
- MRP = (S, P, R, γ)
- 리턴 = 현재 시점부터 받을 보상의 합
- 같은 상태에서 출발하여도 에피소드마다 리턴이 달라지므로 주어진 상태의 가치를 리턴의 기댓값을 통해 정의할 수 있다.
2.3 마르코프 결정 프로세스(MDP)
MP와 MRP에서는 상태 변화가 자동으로 이루어졌다. MP나 MRP만 가지고는 순차적 의사결정 문제를 모델링 할 수 없다.
순차적 의사결정에서는 의사결정이 핵심이기에 의사결정에 관한 부분이 모델에 포함되어 있어야 한다.
MDP의 정의
MDP는 MRP에 에이전트가 더해진 것이다. 에이전트는 각 상황마다 액션(행동)을 취한다. 해당 액션에 의해 상태가 변하고 그에 따른 보상을 받는다.
MDP를 정의하기 위해서는 액션의 집합인 A가 포함된다.
MDP ≡ (S, A, P, R, γ)
S : 상태의 집합
- MP, MRP의 S와 같고, 가능한 상태의 집합이다.
A : 액션의 집합
- 에이전트가 취할 수 있는 액션들 (ex. 흙을 채집하는 로봇의 A는 앞으로 움직이기, 뒤로 움직이기, 흙을 채집하기 가 있다.)
P : 전이 확률 행렬
- MP, MRP에서는 현재 상태가 s일때 다음 상태가 s'이 될 확률을 \(P_{ss'}\)이라고 표기했다. 하지만 MDP에서는 현재 상태가 s이며 에이전트가 액션 a를 선택했을 때 다음 상태가 s'이 될 확률을 정의해야한다. ( \(P_{ss'}^a\) )
- 정의 : \(P_{ss'}^a = P[S_{t+1} = s' | S_t = s, A_t = a]\) (| 오른 편의 2가지 조건은 현재 상태 s에서 액션 a를 했을 때 이다.)
R : 보상 함수
- 상태 s에서 액션 a를 선택하면 받는 보상을 가리키며 이는 확률적으로 매번 바뀔 수 있기 때문에 마찬가지로 기댓값을 이용하여 표기한다.
- 정의 : \(R_s^a = E[R_{t+1} | S_t = s, A_t = a]\)
γ : 감쇠인자
- MRP에서의 γ와 같다.
아이 재우기 MDP
아이가 잠드는 상황에서 어머니라는 에이전트가 개입되기 시작했다.
어머니가 택할 수 있는 액션은 자장가를 불러주는 것, 같이 놀아주는 것이 있다.
아이가 활발한 상태인 \(s_0, s_1\)에서는 자장가를 불러주는 액션을 취하면 당장은 음의 보상을 받는다. 아이는 지금 일어나서 놀고 싶어하는 상태이기 때문이다.
이어서 잠이 오는 상태 \(s_3\)에 도달하면 같이 놀아주는 행위가 음의 보상을 받는다.
\(s_2\)에서 아이에게 놀아주는 액션을 선택하면 아이의 다음 상태는 그날 아이의 상태에 따라 \(s_0\)가 될 수도 있고, \(s_1\)이 될 수도 있다.
이때의 전이 확률을 수식으로 표현해보자.
실제 세계에서 마주하는 MDP는 상태의 개수가 무수히 많고, 액션의 개수도 훨씬 많다. 복잡한 MDP에서 결국 우리가 찾고자 하는 것은 각 상태 s에 따라 어떤 액션 a를 선택해야 보상의 합을 최대로 할 수 있는가이다. 이것을 전략이라고 표현하고 강화 학습의 언어를 빌리면 정책이라고 한다.
정책 함수와 2가지 가치 함수
정책 함수
아이를 재우려는 어머니의 입장에서 아이의 상태에 따라 \(a_0\), \(a_1\) 둘 중의 하나를 결정해야 한다. 그것을 어머니의 정책이라 부를 수 있다. 어머니의 목적은 보상의 합을 최대화하는 정책을 찾는 것이다.
정책 함수를 확률을 이용해 정의하면 다음과 같다.
π(a|s) = P[ \(A_t = a | S_t = s\) ] : 상태 s에서 액션 a를 선택할 확률
MDP 속 상태 \(s_0\)에서 선택할 수 있는 액션을 \(a_0, a_1, a_2\)라고 하면 이 각각에 대해 얼마큼의 확률을 부여할지는 정책 함수가 결정한다.
π( \(a_0\) | \(s_0\) ) = 0.2
π( \(a_1\) | \(s_1\) ) = 0.5
π( \(a_2\) | \(s_2\) ) = 0.3
각 상태에서 할 수 있는 모든 액션의 확률 값을 더하면 1이 되어야 한다.
여기서 정책은 에이전트 안에 있는 것이라는 점을 기억해야 한다.
상태 가치 함수
에이전트의 액션이 도입되었기 때문에 에이전트의 정책 함수에 따라서 얻는 리턴이 달라진다.
따라서 가치 함수는 정책 함수에 의존적이다. 가치 함수를 정의하기 위해서는 정책 함수 π가 정의되어야 한다. π가 주어졌다고 가정했을 때 가치 함수의 정의는 다음과 같다.
\(v_\pi(s) = E_\pi[r_{t+1} + \lambda r_{t+2} + \lambda^2 r_{t+3} + ... | S_t = s] = E_\pi[G_t | S_t = s]\)
s부터 끝까지 π를 따라서 움직일 때 얻는 리턴의 기댓값
이제부터 가치 함수는 π에 의존적이라는 것을 명심하자.
액션 가치 함수
위의 함수는 어떤 상태가 주어졌을 때 그 상태를 평가해주는 함수이다.
그렇다면 각 상태에서의 액션도 평가할 수는 없을까?
상태 가치 함수를 v(s)라고 표현하였다면 액션 가치 함수는 q(s,a)로 표현한다.
함수에 상태와 액션이 동시에 인풋으로 들어가야 한다. 액션만 따로 떼어내어 평가할 수 없는 이유는 상태에 따라 액션의 결과가 달라지기 때문이다.
여기까지가 차이이고 나머지는 상태 가치 함수 v(s)와 거의 똑같다. v(s)와 마찬가리조 미래에 얻을 리턴 \(G_t\)를 통해 밸류를 측정한다. 또한 정책 π에 따라 이후 상태가 달라지므로 π를 고정시켜 놓고 평가한다. 이를 수학적으로 표현해보자.
\(q_\pi(s, a) = E_\pi[G_t | S_t = s, A_t = a]\)
s에서 a를 선택하고, 그 이후에는 π를 따라서 움직일 때 얻는 리턴의 기댓값
a를 선택하고 나면 이후의 상태를 진행하기 위해 계속해서 누군가가 액션을 선택해야 하는데, 그 역할은 정책 함수 π에게 맡기는 것이다.
따라서 \(v_\pi\)(s)와 \(q_\pi\)(s,a)는 "s에서 어떤 액션을 선택하는가"하는 부분에만 차이가 있다.
\(v_\pi\)(s)를 계산할 때는 s에서 π가 액션을 선택하는 반면, \(q_\pi\)(s,a)를 계산할 때는 s에서 강제로 a를 선택한다.
일단 액션을 선택한 이후에는 2가지 가치 함수 모두 정책 함수 π를 따라서 에피소드가 끝날 때까지 진행한다.
2.4 Prediction과 Control
MDP 즉, (S, A, P, R, γ)가 주어졌을 때 우리가 관심 있어 하는 태스크는 Prediction과 Control이 있다.
Prediction : π가 주어졌을 때 각 상태의 밸류를 평가하는 문제
Control : 최적 정책 π*를 찾는 문제
알파고처럼 바둑이라는 상황을 MDP로 표현하여 해당 MDP에서 최적 정책 π*를 찾거나 임의의 정책 π에 대해 각 상태의 밸류 \(v_\pi\)(s)를 구하고자 하는 것이다.
그리드 월드와 같은 상황을 생각해보자
출발에서 시작하여 종료까지 도착하면 한 에피소드가 끝나며 스텝마다 -1의 보상을 받는 상황이다.
따라서 누적 보상을 최대화하고자 한다면 최단 경로를 지나 종료 상태에 도착해야 한다.
에이전트가 선택할 수 있는 액션은 총 4개로 동, 서, 남, 북 방향으로 한 칸씩 움직이는 것이다.
π(동|s) = 0.25
π(서|s) = 0.25
π(남|s) = 0.25
π(북|s) = 0.25
prediction의 예시를 들어보자. \(s_{11}\)의 밸류 \(v_\pi\)(\(s_{11}\))의 값은 몇이 될까?
다양한 경로에 대해 다양한 리턴을 받을 수 있다.
이 각각의 여정을 에피소드라고 부른다.
에피소드마다 미래에 얻을 보상이 다르며 에피소드가 발생할 확률도 다르다.
확률과 리턴의 곱을 모두 더해줘야 상태 \(s_{11}\)에서의 리턴의 기댓값을 구할 수 있게 된다.
이번에는 control 문제를 살펴보자.
control의 목적은 최적의 정책 π*를 찾는 것이다. 즉 세상에 존재하는 모든 π중에서 가장 기대 리턴이 큰 π를 뜻한다. 따라서 그리드 월드에서는 돌아가지 않고 종료를 향해 나아가면 된다.일반적인 MDP에서 π*를 찾기 위해 강화학습을 사용한다.
π*를 따를 때의 가치 함수를 최적 가치 함수라고 하며 v*라고 표기한다.
π*와 v*를 찾으면 이 MDP는 풀렸다고 말할 수 있다.
'바닥부터 배우는 강화 학습' 카테고리의 다른 글
| [ 바닥부터 배우는 강화 학습 ] 05. MDP를 모를 때 밸류 평가하기 (3) | 2024.01.02 |
|---|---|
| [ 바닥부터 배우는 강화 학습 ] 06. MDP를 모를 때 최고의 정책 찾기 (0) | 2023.11.23 |
| [ 바닥부터 배우는 강화 학습 ] 04. MDP를 알 때의 플래닝 (0) | 2023.11.10 |
| [ 바닥부터 배우는 강화 학습 ] 03. 벨만 방정식 (1) | 2023.10.04 |
| [ 바닥부터 배우는 강화 학습 ] 01. 강화 학습이란 (0) | 2023.09.18 |
