[강화학습 이론] 2장_강화학습 기초1 : MDP와 벨만 방정식

슥슥·2022년 11월 23일

강화학습 기초 스터디

목록 보기

1/7

2장. MDP와 벨만방정식

강화학습 이전에 "순차적 행동 결정 문제"에 대한 이해가 필요하다. 이 문제는 MDP로 정의할 수 있고, MDP 문제에서 에이전트가 학습하기 위해서는 가치함수 개념이 사용된다. 이 개념은 벨만 방정식과도 연관된다.

MDP

강화학습은 순차적으로 어떤 행동을 취해야할지에 대한 문제를 푸는 것이다. MDP는 순차적으로 결정해야하는 문제를 수학적으로 표현하는 방식이다.
MDP는 다음과 같은 구성요소로 이루어져있다.

1. 상태 ( $S$ )

$S$ 는 에이전트가 관찰 가능한 상태의 집합이다.
실제 세상에서는 센서로 입력되는 값으로 볼 수 있지만, 학습을 위해서는 사용자가 상태를 정의해줘야한다.

만약 2차원 평면에서 5가지의 상태가 존재한다면 다음과 같이 표현할 수 있다.

S= \left\{(x_1, y_1),(x_2, y_2),(x_3,y_3),(x_4,y_4),(x_5,y_5)\right\}

5X5 2차원 좌표평면에서는 총 25개의 상태가 존재하고, 각 상태는 $(x,y)$ 로 이루어진 좌표일 것이다.

S= \left\{(1,1),(1,2),(1,3),...,(5,4),(5,5)\right\}

에이전트는 시간에 따라서 25개의 상태를 탐험하게 되고, 시간이 t일의 상태를 $S_{t}$ 로 표현한다. 시간 t에서 $S_{t}$ 는 정해져있지 않고, 시간에 따라서 확률적으로 변하는 확률변수이다.

따라서, "시간 t에서 상태 $S_{t}$ 는 어떤 상태 $s$ 이다"는 다음과 같이 표현한다.

S_{t} = s

2. 행동 ( $A$ )

$A$ 는 에이전트가 상태 $S_{t}$ 에서 할 수 있는 "행동"의 집합이다. 상태와 마찬가지로, $A_{t}$ 는 확률적으로 변하기 때문에 확률변수이다. 시간 t에 에이전트가 특정한 행동 $a$ 를 했다면, 다음과 같이 표현한다.

A_{t} = a

2차원 평면에서 에이전트가 할 수 있는 행동은 상,하,좌,우로 움직이는 것으로, 다음과 같이 표현할 수 있다.

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

즉, 시간 $t$ 에서 상태가 (3,1)이고, $A_{t}=right$ 이면 $t+1$ 에서의 상태는 (4,1)이 될 것이다.

3. 보상함수 ( $r(s,a)$ )

"보상함수" $r(s,a)$ 는 에이전트가 학습할 수 있는 유일한 정보로, 외부 환경이 에이전트에게 주는 정보이다. 시간이 $t$ , 상태가 $S_{t}=s$ , 행동이 $A_{t}=a$ 일 때 에이전트가 받을 보상은 다음과 같다.

r(s,a) = E\left[R_{t+1} | S_{t}=s,A_{t}=a\right]

즉, 보상함수는 시간 $t$ 에서의 상태와 행동을 통해 $t+1$ 에서 받을 수 있는 보상에 대한 기댓값이다.

4. 상태 변환 확률 ( $P_{ss}^{a}$ )

어떤 행동을 하더라도 상태의 변화에는 확률적인 요인이 들어간다. 이 확률을 수치적으로 표현한 것이 "상태 변환 확률" $P_{ss'}^{a}$ 이다.

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

이는 상태 $s$ 에서 행동 $a$ 를 취했을 때, 상태 $s'$ 으로 도달할 확률이다. 보상함수와 마찬가지로 상태 변환 확률은 에이전트 외부 환경에서 전달되는 값이다. 상태 변환 함수는 환경의 모델이라고도 불리는데, 에이전트의 행동에 따라 상태 변환 확률을 통해 다음 상태를 알려준다.

5. 할인률 ( $\gamma$ )

같은 양의 보상이더라도, 현재 받는 것이 가치가 높고 나중에 받을수록 가치가 떨어진다. 이를 표현하기 위해 "할인율"을 사용한다.
할인율은 미래의 가치를 현재의 가치로 환산함에 따라 할인되는 비율을 뜻하고, 0과 1 사이의 값으로 나타낸다. 더 먼 미래의 보상일수록 현재에는 더 작은 값으로 받아들인다.

\gamma \in [0,1]

따라서, 할인률을 고려한 $t+k$ 시점에서 발생하는 가치의 $t$ 시점에서 현재 가치는 다음과 같다.

\gamma^{k-1}R_{t+k}

6. 정책( $\pi(a|s)$ )

"정책"은 모든 상태에서 에이전트가 할 행동이다. 상태가 입력으로 주어졌을 때 행동을 출력으로 내보내는 함수의 형태이다.

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

정책은 한 상태에 대해 한 가지 행동을 출력할 수도 있지만, 확률적으로 나타낼 수도 있다. 특히 학습 과정에서는 다양한 행동을 선택하여 최적의 정책을 찾아야한다.

이렇게 정의된 MDP를 통해 에이전트는 형태 상태에서 앞으로 받을 수 있는 보상을 고려해서 행동을 선택한다. 환경은 에이전트에게 실제 보상과 다음 상태를 알려주고, 이를 토대로 에이전트는 가치함수와 정책을 수정해나간다. 최종적으로는 가장 많은 보상을 받도록 하는 최적의 정책을 찾을 수 있을 것이다.

가치함수

1. 가치함수

그렇다면 에이전트는 어떻게 MDP를 통해서 최적 정책을 찾을 수 있을까? 에이전트는 현재 상태에서 앞으로 받을 수 있는 보상을 고려하게 되고, 이 개념이 가치함수이다.
현재 시점 $t$ 로부터 에이전트가 행동을 하여 얻을 수 있는 보상은 다음과 같다.

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

여기에 할인율 $\gamma$ 를 고려한 전체 보상인 반환값 $G_t$ 는 다음과 같다.

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

에이전트와 환경이 유한한 시간동안 상호작용하는 것을 에피소드 라고 말한다. 유한한 시간동안 진행되기 때문에 마지막 상태에 도달하면 최종 반환값을 계산할 수 있다.

총 5번의 에피소드가 발생하면 총 반환값은 다음과 같다.

G_1 = R_2 + \gamma R_3 + \gamma^2 R_4 + \gamma^3 R_5 +\gamma^4 R_6\\ G_2 = R_3 + \gamma R_4 + \gamma^3 R_5 +\gamma^3 R_6\\ G_3 = R_4 + \gamma^1 R_5 +\gamma^2 R_6\\ G_4 = R_5 +\gamma^1 R_6\\ G_5 = R_6

MDP의 구성요소들은 확률변수, 즉 확률적으로 변화하기 대문에 반환값에 대한 기댓값으로 특정 상태 $t$ 에서 얻을 수 있는 가치를 표현할 수 있다. 이를 가치함수 $v(s)$ 라고 한다.

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

각 시점마다 얻는 보상은 확률적이기 때문에 반환값 자체는 확률변수지만, 가치함수는 기댓값이기 때문에 특정 값이다.
가치함수의 $G_t$ 에 위에서 구한 반환값의 식을 대입한 후 정리하면 다음과 같이 표현할 수 있다.

v(s)=E[R_{t+1}+\gamma v(S_{t+1})|S_t=s]

해석하자면 현재 상태 $s$ 에서의 가치함수는 다음 단계에서 받는 보상과 다음 단계에서의 가치함수(반환값의 기댓값)의 합과 동일하다.

한편, 에이전트는 현재 상태에서 정책을 고려하여 행동을 선택하고, 그 행동에 따라서 보상이 주어지기 때문에 가치함수에서는 정책을 고려해야한다. 정책 $\pi$ 을 고려한 가치함수는 다음과 같다.

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

이렇게 구한 최종 가치함수 식 $v_\pi(s)$ 가 바로 벨만 기대 방정식이다. 벨만 기대 방정식은 현재 상태의 가치함수 $v_\pi(s)$ 와 다음 상태에서의 가치함수 $v_\pi(S_{t+1})$ 사이의 관계를 표현하는 방정식이다.

2. 큐함수

위에서 정의한 가치함수는 상태 가치함수이다. 즉, 어떤 상태가 입력으로 들어왔을 때, 앞으로 받을 수 있는 보상의 합을 출력하는 함수이다. 이를 통해서 어떤 상태에 있는게 얼마나 좋은지 알 수 있고, 다음에 어떤 상태로 가야하는지 판단할 수 있다.

그런데, 다음 상태로 가기 전에 실제로는 에이전트가 선택한 행동에 따라 보상이 달라지고, 상태 변환 확률에 따라 달라질 수도 있다. 이러한 요소를 다 고려하기 위해 각 행동에 대해 가치를 알려주는 함수를 사용한다. 이를 행동 가치 함수라고 하고 간단하게 큐함수라고 한다.

큐함수는 상태와 행동을 동시에 변수로 가지고, $q_\pi(s,a)$ 로 표현한다. 따라서 큐함수를 통해 가치함수를 다음과 같이 표현할 수 있다.

v_\pi(s) = \sum_{a \in A}\pi(a | s)q_\pi(s,a)

큐함수는 가치함수처럼 벨만 기대 방정식 형태로 나타낼 수 있는데, 조건문에 행동에 대한 변수가 추가된 형태이다.

q_\pi(s) = E_\pi[R_{t+1}+\gamma q_\pi(S_{t+1},A_{t+1}) |S_t=s,A_t=a]

벨만 방정식

1. 벨만 기대 방정식

위에서 정의했던 것 처럼 벨만 기대 방정식은 다음과 같다.

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

벨만 방정식의 형태로 보상의 합에 대한 기댓값을 표현하면 변수를 저장하고 재귀함수를 도는 형태이기 때문에 연산에서 이점을 얻을 수 있다.
기댓값을 계산하기 위해서는 벨만 기대 방정식의 형태를 한번 더 바꿔줘야 한다. 기댓값에 사용되는 확률에는 어떤 행동을 할 확률(정책 $\pi(a|s)$ )과 행동을 통해 어떤 상태로 갈 확률 (상태 변환 확률 $P_{ss'}^{a}$ )이 있다.

v_\pi(s) = \sum_{a \in A}\pi(a|s)(r(s,a)+\gamma \sum_{s' \in S}P_{ss'}^{a}v(s'))

이는
상태 $s$ 에서 모든 행동 $A$ 에 대해 행동 $a$ 를 선택할 확률 X ( $a$ 를 선택했을 때 얻는 가치 + 할인율 X 모든 상태 $S$ 에 대해 $s'$ 으로 도달할 확률 X $s'$ 에서의 가치 함수)
라고 해석할 수 있다.

2. 벨만 최적 방정식

벨만 기대 방정식을 반복하다보면 현재의 정책을 통해 에이전트가 얻을 수 있는 보상에 대한 기댓값을 계산할 수 있다.
즉, 벨만 기대 방정식이 더이상 업데이트되지 않고, 좌변과 우변이 동일해진다.

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

강화학습의 최종 목표는 최적 정책을 찾는 것이다. 최적의 정책( $v^*(s)$ )은 모든 정책에 대해서 가장 큰 가치함수를 주는 정책이다. 최적 가치함수와 큐함수는 다음과 같다.

v^*(s) = max_a[v_\pi(s)] \\ q^*(s,a) = max_a[q_\pi(s,a)]

가장 큰 가치함수/큐함수를 찾았다면, 최적 정책은 각 상태 $s$ 에서 최적의 큐함수 중에서 가장 큰 큐함수를 가진 행동 $a$ 를 하는 것이다. 최적 정책은 가장 큰 값만을 선택하고 나머지는 선택하지 않는다.

\pi^* = \begin{cases} 1, \;if\; a=argmax_{a \in A}q^*(s,a)\\ 0, \;otherwise\; \end{cases}

최적의 가치함수는 최적의 큐함수에서 max인 행동을 취하는 것이기 때문에 다음과 같이 표현할 수 있다.

v^*(s) = max_a[q^*(s,a) | S_t=s,A_t=a]

큐함수를 가치함수로 표현한 식을 벨만 최적 방정식이라고 한다.

v^*(s) = max_aE[R_{t+1}+\gamma v^*(S_{t+1})| S_t=s,A_t=a]

가치함수에 대한 벨만 최적 방정식을 큐함수에 대한 벨만 최적 방정식으로 표현하면 다음과 같다.

q^*(s,a) = E[R_{t+1}+\gamma max_{a'}q^*(S_{t+1},a')|S_t=s,A_t=a]

최적의 큐함수는 다음 상태에 선택 가능한 행동 중 가장 높은 큐함수 $q^*(S_{t+1},a')$ 에 할인율을 한번 적용하고 보상 $R_{t+1}$ 을 더한 값과 같다.

이렇게 정의한 벨만 기대 방정식과 벨만 최적 방정식을 통해 정의된 문제를 계산하는 것이 다이내믹 프로그래밍 (Dynamic Programming)이다.

정리

MDP

순차적 행동 결정 문제의 수학적 정의

상태 : $s$
행동 : $a$
보상함수 : $r(s,a)$
상태 변환 확률 : $P_{pp'}^a$
할인율 : $\gamma$

가치함수

어떤 정책이 더 좋은 정책인지 판단하는 기준
현재 상태 $S$ 로부터 정책을 통해 받을 것으로 기대되는 보상의 합

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

보통 선택하는 행동 $a$ 를 선택했을 때의 가치를 나타내는 큐함수 사용

q_\pi(s) = E_\pi[R_{t+1}+\gamma q_\pi(S_{t+1},A_{t+1}) |S_t=s,A_t=a]

벨만 방정식

벨만 방정식 : 현재 상태 $S_t$ 의 가치함수와 다음 상태의 가치함수 $S_{t+1}$ 사이의 관계식
벨만 기대 방정식 : 특정 정책을 따를 때 가치함수 사이의 관계식

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

최적의 정책은 최적의 가치함수를 선택하도록 하는 정책
벨만 최적 방정식 : 최적의 정책에서 가치함수 사이의 관계식

v^*(s) = max_aE[R_{t+1}+\gamma v^*(S_{t+1})| S_t=s,A_t=a]

슥슥

다음 포스트

[강화학습 이론] 2장_강화학습 기초1 : MDP와 벨만 방정식

강화학습 기초 스터디

2장. MDP와 벨만방정식