강화학습 기초. 1장 MDP와 벨만 방정식

괴도소녀·2021년 9월 28일

강화마을입주

목록 보기

2/2

사람들이 어떤 문제를 처음 접했을 때 어떤 문제인지 파악부터하는 습성이 있다.
하지만 강화학습에서의 에이전트는 그렇게 지능적이지 않으므로, 사용자가 문제를 정의해야 한다. 문제를 잘못 정의하면 에이전트가 학습을 못할 수도 있다.

MDP

강화학습은 순차적으로 행동을 계속 결정해야 하는 문제를 푸는 것이며,
MDP는 순차적으로 결정해야하는 문제를 수학적으로 표현한다.

MDP의 구성요소는 아래와 같다.

상태
행동
보상 함수
상태 변환 확률
할인율

MDP의 이해를 돕기 위해 그리드 월드라는 예제를 이용해 살펴보자.

상태 state

$S$ 는 에이전트가 관찰 가능한 상태의 집합이라고 하며, 더 정확히는 "자신의 상황에 대한 관찰"라는 말이 더 정확한 표현이다.

S = \{(x_1, y_1), (x_2, y_2),(x_3, y_3),(x_4, y_4),(x_5, y_5)\} \ \\ \\ \text{[수식 2.1 상태의 집합]}

그리드월드의 상태를 집합으로 나타낸다면 아래와 같다.

S = \{(1, 1), (1, 2),(1, 3),... ,(5, 5)\} \\ \text{[수식 2.2 그리드월드의 상태 집합]}

시간이 $t$ 일 때 상태를 $S_t$ 라고 표현하는데, 만약 시간이 $t$ 일 때 상태가 (1,3)이면 수식은 아래와 같이 표현된다.

S_t = (1,3)

어떤 $t$ 에서의 상태 $S_t$ 는 정해져 있지 않으며, 때에 따라 $t=1$ 일 때 $S_t=(1,3)$ 일 수도 있고 $S_t=(4,2)$ 일 수도 있다.

위의 식을 일반화 해보면,
"시간 $t$ 에서의 상태 $S_t$ 가 어떤 상태 $s$ 다"를 표현할 수식은 아래와 같다.

S_t = s \\ \text{[수식 2.4 시간 t에서의 상태]}

행동 Action

에이전트가 상태 $S_t$ 에서 할 수 있는 가능한 행동의 집합을 $A$ 라고 표현한다.
시간 $t$ 에 에이전트가 특정한 행동 $a$ 를 했다면 수식은 아래와 같이 표현할 수 있다.

A_t = a

그리드월드에서 에이전트가 할 수 있는 행동은 up, down, left, right로 4가지 이다.

A = \{\text{up}, \text{down}, \text{left}, \text{right}\}

만약 시간 $t$ 에서 상태가 (3, 1)이고 $A_t = \text{right}$ 라면 다음 시간의 상태는 (4,1)이 되지만, 바람과 같이 예상치 못한 요소가 있다면 도달하지 못할 수도 있으며, 이러한 요소를 포함해서 에이전트가 특정 행동을 했을 때 어디로 이동할지 결정하는 것이 상태 변환 확률 이라 한다.

보상함수

보상은 에이전트가 학습할 수 있는 유일한 정보이다.
아래는 보상함수의 정의이다.

r(s,a) = E(R_{t+1}|S_t = s, A_t = a)

보상함수는 시간 $t$ 일 때 상태가 $S_t=s$ 이고 그 상태에서 행동 $A_t=a$ 를 했을 경우에 받을 보상에 대한 기댓값 E(Expection)이다. 즉, 보상함수 $r(s,a)$ 가 보상의 기댓값이라고 한다.

여기서 기댓값은 어떤 정확한 값이 아니라 나오게 될 숫자에 대한 예상이다.
보상함수의 특이한 점은 에이전트가 어떤 상태에서 행동한 것은 시간 $t$ 이지만 보상을 받는 것은 $t+1$ 이라는 점이다. 보상을 에이전트가 알고 있는 것이 아니고 환경이 알려주는 것이기 때문이다.

이렇게 에이전트는 환경으로부터 하나의 시간 단위가 지난 다음에 보상을 받는데, 이 시간 단위를 타임스텝(time step)이라 한다.

상태 변환 확률

에이전트가 어떤 상태에서 어떤 행동을 취한다면 에이전트의 상태는 변할 것이며, 이를 수치적으로 표현한 것이 상태 변환 확률이다.

P_{ss}^{a} = P[S_{t+1} = s | S_t = s, A_t = a]

상태변환 확률은 환경의 모델(model)이라고도 부르며, 환경은 에이전트가 행동을 취하면 상태 변환 확률을 통해 다음에 에이전트가 갈 상태를 알려준다.

할인율 Discount Factor

미래의 가치를 현재의 가치로 환산하는 것을 할인한다 하고, 시간에 따라 할인하는 비율을 할인율이라고 한다. 할인율 $\gamma$ 는 0~1사이의 값이다. 보상에 곱해지면 보상이 감소한다.

\gamma \in [0,1]

만약 현재의 시간 $t$ 로부터 시간 $k$ 가 지난 후에 보상을 $R_{t+k}$ 를 받을 것이라고 하면 현재 그 보상의 가치의 수식은 아래와 같다.

\gamma^{k-1}R_{t+k} \\ \text{[할인율을 고려한 미래 보상의 현재 가치]}

더 먼 미래에 받은 보상일수록 현재의 에이전트는 더 작은 값으로 받아들인다.

마치... 은행 적금 같지 않은가?!!!

정책 policy

정책은 모든 상태에서 에이전트가 할 행동이다.
상태가 입력으로 들어올 시 행동을 출력을 내보내는 일종의 함수라고 생각해도 좋다.

정책을 수식으로 나타내면 아래와 같다.

\pi(a|s) = P[A_t=a|S_t=s]

시간 $t$ 에 $S_t = s$ 에 에이전트가 있을 때 가능한 행동 중 $A_t = a$ 를 할 확률을 나타낸다.

에이전트가 강화학습을 통해 학습해야할 것은 수많은 정책 중 최적 정책이다.
최적 정책은 각 상태에서 단 하나의 행동만을 선택한다.
하지만 에이전트가 학습하고 있을 때는 정책이 하나의 행동만을 선택하기 보다는 확률적으로 여러 개의 행동을 선택할 수 있어야지 다양한 상황에 대해 학습하고 최적 정책을 찾을 수 있을 것이다.

위처럼 상태, 행동, 보상함수, 할인율, 정책들의 요소의 과정들을 반복하면서 에이전트가 어떤 상태에서 앞으로 받을 것이라 예상했던 보상(가치함수 : Value Function)에 대해 틀리는 경우도 있을 것이다.

에이전트가 실제로 받은 보상을 토대로해서 가치함수와 정책을 바꿔나가면서 가장 많은 보상을 받게하는 정책을 꾸준히 학습할 수 있게 된다.

가치함수

앞으로 받을 보상에 대한 개념이 가치함수이다.
에이전트는 가치함수를 통해 행동을 선택할 수 있다.

MDP -> 가치함수 -> 행동선택

현재시간 $t$ 로부터 에이전트가 행동을 하면서 받을 보상들의 합을 수식으로 나타낸다면 아래와 같다.

R_{t+1} + R_{t+2} + R_{t+3} + R_{t+4} + R_{t+5} + ...

보상은 행동을 했을 때가 아닌 그 다음 타임스텝에 받는다는 것을 기억하자!

위 수식에서는 시간마다 받는 보상을 모두 포함했지만 에이전트가 시간마다 보상을 받을 수도 있고 게임이 끝날 때 한번에 받을 수도 있다. 하지만 바로 다음에 받는 보상과 시간이 지나서 받는 보상을 구별할 방법이 에이전트에게는 없다. 이러한 문제 때문에 상태의 가치를 판단하기위해서 할인율 이라는 개념을 도입한다.

시간 $t$ 이후의 '시간 $t$ 시점에서의 보상'을 모두 더하면 밑에 식이 완성되며 이 값을 반환값 $G_t$ 라고 한다.

G_t = R_{t+1}+\gamma R_{t+2} + \gamma^2 R_{t+3} + ...

하지만 각 상황에서의 얻은 반환값으로 각 상태의 가치를 알 수는 없으므로, 에이전트는 특정상태의 가치를 반환값에 대한 기댓값으로 판단한다.

v(s) = E[G_t | S_t = s]

이것까지가 가치함수의 개념이다. 각 타임스텝마다 받는 보상이 모두 확률적이고 반환값이 그 보상들의 합이므로 반환값은 확률변수이다.

하지만 가치함수를 정의할 때 정책을 고려하지 않는다. 에이전트가 앞으로 받은 보상에 대해 생각할 때 정책을 고려하지 않으면 안되므로 아래 첨자로 정책을 써준다.

v_{\pi}(s) = E_{\pi}[R_{t+1} + \gamma v_{\pi}(S_{t+1}) | S_t = s]

바로 위 수식이 강화학습에서 중요한 벨만 기대 방정식(Bellman Expection Equation) 이다.

벨만 기대 방정식은 현재 상태의 가치함수 $v_{\pi}(s)$ 와 다음 상태의 가치함수 $v_{\pi}(S_{t+1})$ 사이의 관계를 말해주는 방정식이다.

큐함수 Q Function

위에서 설명한 가치함수는 상태 가치함수(staate value-function)이다.
어떤 상태에서 어떤 행동이 얼마나 좋은지 알려주는 함수를 행동 가치함수라고하며 큐함수(Q Function) 이라고도 부른다. 큐함수는 상태, 행동이라는 두 가지 변수를 가지며 $q_{\pi}(s,a)$ 라고 나타낸다.

강화학습에서 에이전트가 행동을 선택하는 기준으로 가치함수보다는 큐함수를 보통 사용한다.

벨만 방정식

벨만 기대 방정식

어떤 상태의 가치함수는 에이전트가 그 상태로 갈 경우에 앞으로 받을 보상의 합에 대한 기댓값이다. 가치함수는 현재 에이전트 정책의 영향을 받으며, 식으로 나타내면 아래와 같다.
현재 상태의 가치함수와 다음 상태의 가치함수 사이의 관계를 식으로 나타낸 것이다.

수식 2.29를 살펴보면 정의상으로는 가능하지만 상태가 많아질수록 상당히 비효율적인 방법이며, 다른 조치가 필요해보인다.
그러므로 기댓값이 계산 가능한 상태로 만들려면 아래와 같이 식을 변형해야 한다.

기댓갑세는 어떠한 행동을 할 확률(정책 $\pi(a|s)$ )과 그 행동을 했을 때 어떤 상태로 가게 되는 확률(상태 변환 확률 $P_{s \acute s}^{a}$ )이 포함되어 있다.

벨만 최적 방정식

최적의 가치함수는 수많은 정책 중 가장 높은 보상을 얻게 되는 정책을 따랐을 때의 가치함수이다. 최적 정책을 따라갔을 때 받을 보상의 합이 최적 가치함수이다.

가장 높은 가치함수(큐함수)를 에이전트가 찾았다고 가정했을 때, 이 떄 최적 정책은 각 상태 $s$ 에서의 최적의 큐함수 중 가장 큰 큐함수를 가진 행동을 하는 것이다.
따라서 최적 정책은 최적 큐함수 q만 안다면 수식을 아래와 같이 나타낼 수 있다.

argmax는 q를 최대로 해주는 행동 a를 반환하는 함수이다.

큐함수 중에서 max를 취하는 것이 최적의 가치함수이며, 큐함수를 가치함수를 고쳐서 표현한 식을 벨만 최적 방정식(Bellman Optimality Equation)이라 한다.

벨만 기대 방정식과 벨만 최적 방정식을 이용해 MDP로 정의되는 문제를 "계산"으로 푸는 방법이 다음 포스팅의 다이내믹 프로그래밍(Dynamic programming)이다.

괴도소녀

이전 포스트