강화학습 공부 - (1) 마르코프 결정 프로세스

 

서론

MDP란 강화학습의 환경을 공식적으로 설명하는 것이다.

모든 환경이 관찰 가능하다고 가정한다.

거의 모든 강화학습의 문제들이 MDP로 표현될 수 있다.

 

마르코프 구성요소

• 현재를 기준으로 미래는 과거와 무관하다

상태 S_t는

$P[S_{t+1} | S_t] = P[S_{t+1} | S1, … S_t]$

 

상태 $S_{t+1}$은 오직 상태 S_t에 의해서만 결정된다.

이것이 상태 S_1에서 S_t까지 (히스토리)를 모두 반영한다고 가정한다.

따라서 현재의 상태가 다음(미래)상태를 결정하는데 충분하다고 본다.

 

상태 전환 확률은 마르코프 상태 s의 제일 높은 확률을 가진 다음 상태 s'를 결정하는 확률이다.

$P_{ss'} = P[S_t+1 = s' | S_t = s]$

 

상태 전환 행렬은 현재 상태에서 다음 상태로 갈 모든 확률을 표현하는 행렬이다.

만약 내가 다음 행렬에서 [0, 1]에 서있다면, [0,0], [0,2], [1,1]에 갈 확률은 각 0.05, 0.2, 0.4가 되는것이다. 모든 상태전환 행렬의 원소들의 합은 1이 되어야 한다.

0.05	0	0.2
0.03	0.4	0.1
0.07	0.05	0.1

 

마르코프 프로세스

마르코프 프로세스란 마르코프 속성들을 가진 상태들의 메모리가 없는 랜덤 프로세스(시퀀스)이다.

마르코프 프로세스는 (마르코프 체인이라고도 함) 다음 원소들을 가지는 튜플이다.

• S - 유한한 수의 상태들의 집합
• P - 상태 전환 확률 행렬

 

마르코프 보상 프로세스

마르코프 보상 프로세스는 마르코프 체인에 값(value)들이 있는 것이다.

마르코프 보상 프로세스는 다음의 원소들을 가진 튜플이다 (S, P, R, $\gamma$)

• S - 유한한 수의 상태들의 집합
• P - 상태 전환 확률 행렬
• R - 어떠한 상태에 도달했을 때 받는 보상 $R_s = E[R{_t+1} | S_t = s]$
• 위 수식은 리뭐드 $R_s$는 상태 t에서 시점 t+1에 받을 수 있다는 뜻이다.
• $\gamma$ - 감가율, 0에서 1사이의 값

 

리턴

리턴(목적) $G_t$는 시점 t에 받을 감가율이 반영된 보상을 의미한다.

$G_t = R_{t+1} + \gamma R_{t+2} + … = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$

 

감가율을 적용하면, 미래의 보상과 현재의 보상을 비교할 수 있게 된다.

 

 

가치함수

가치함수 v(s)는 상태 s의 장기적인 가치이다.

상태가치함수 v(s)는 상태 s에서 시작할때 예상되는 보상(리턴)을 의미한다.

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

 

 

벨만방정식

가치함수는 두 부분으로 나눠질 수 있다:

• 즉각적 보상 R_t+1
• 미래의 성공상태에서 받을 감가율이 적용된 보상

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

$\quad\quad= E[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + … | S_t = s]$

$\quad\quad= E[R_{t+1} + \gamma (R_{t+2} + \gamma R_{t+3} + … )| S_t = s]$

$\quad\quad= E[R_{t+1} + \gamma G_{t+1} | S_t = s]$

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

 

위의 수식은 보상을 두가지로 나누는 수식이다. 먼저 현재의 받을 보상을 분리시키고,

나머지 수식은 감가율을 적용한 목적 보상으로 통합될 수 있다.

 

 

벨만방정식 행렬 수식

$v = R + \gamma P v$

위는 아래와 같은 행렬 수식으로 표현될 수 있다.

$[v(1) … v(n)] = [R_1 … R_n] + \gamma [P_11 .. P_nn] [v(1) ... v(n)]$

 

 

벨만방정식 풀이

벨만 방정식은 선형 함수이다.

$v = R + \gamma P v$

$(1 - \gamma P) v = R$

$V = (1 - \gamma P)^-1 R$

 

위의 행렬 방정식을 푸는데는 $O(n^3)$의 시간이 걸린다.

따라서 큰 마르코프 프로세스에는 좋은 해답이 아니다.

 

 

마르코프 결정 프로세스

MDP는 마르코프 보상 프로세스에 결정을 더한것이다. 이는 마르코프 상태들의 집합인 환경을 표현하는 것이다.

마르코프 결정 프로세스는 다음의 원소들을 가진 튜플이다. <S, A, P, R, $\gamma$>

• S - 유한한 수의 상태들의 집합
• A - 유한한 수의 액션들의 집합
• $P^a_{ss'}$ - 상태 전환 확률 행렬  $P^a_{ss'} = E[S_{t+1} = s' | S_t = s, A_t = a]$
• 상태전환확률은 이제 현재 상태에서 에이전트가 취하는 행동도 고려가 된다.
• R - 어떠한 상태에 도달했을 때 받는 보상 $R^a_s = E[R_{t+1} | S_t = s, A_t = a]$
• $\gamma$ - 감가율, 0에서 1사이의 값

 

 

정책

정책 $\pi$ 는 상태가 주어졌을 때의 액션들의 분산이다.

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

정책은 에이전트가 취할 수 있는 가능한 모든 행위를 정의한다.

MDP의 정책은 현재 시점만을 고려한다. (시간과 무관하다.)

 

다음과 같은 MDP M과 policy $\pi$가 주어졌다:

M = <S, A, P, R, $\gamma$>, $\pi$

상태 시퀀스 S_1, S_2, …는 마르코프 프로세스 <S, $P^{\pi}$> 이다.

상태 보상 시퀀스 S_1, R_2, S_2, R_3 … 은 마르코프 보상 프로세스이다.

<S, $P^{\pi}$, $R^{\pi}$, $\gamma$>

 

위의 보상 프로세스에서 상태전환 수식과 보상수식은 다음과 같다:

$P^{\pi}_{s, s'} = \sum_{a \in A} \pi (a | s) P^a_{s, s'}$

$R^{\pi}_s = \sum_{a \in A} \pi (a | s) R^a_s$

 

 

상태가치함수

MDP의 상태가치함수 $v_{\pi}(s)$는 상태 s에서 시작해 정책 $\pi$를 따라갈 때 받을 수 있는 리턴을 정의 한다.

$v_{\pi}(s) = E_{\pi}[G_t | S_t = s]$

 

 

행동가치함수

행동가치함수 q_{\pi}는 상태 s에서 시작해, 정책 \pi를 따라 행동 a를 취하면 얻어지는 리턴을 정의한다.

$q_{\pi}(s, a) = E_{\pi} [G_t | S_t = s, A_t = a]$

 

 

벨만 기대 방정식

상태 가치 함수는 즉각적인 보상과 성공 상태의 감가율이 적용된 보상으로 나뉠 수 있다.

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

 

행동 가치 함수 역시 비슷하게 나뉠 수 있다.

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

 

벨만 기대 방정식의 상태 가치 함수는 현재 상태에서 얻을 수 있는 모든 보상의 평균값이고,

행동가치함수는 이 행동을 선택했을 때 얻을 수 있는 보상.

어떠한 행동을 선택했을 때 내가 어떤 상태로 놓일지는 환경이 결정한다.

따라서 그 확률까지 고려된 행동가치함수의 리턴을 고려한다.

 

위의 상태가치함수와 행동가치함수는 최적의 답을 찾기 전까지 항상 쌍으로 반복된다.

v → q → v → q ...

 

 

최적 가치 함수

최적상태가치함수 $v_{*}(s)$는 모든 정책들 사이의 최대 가치함수를 정의한다.

$v_{*}(s) = \max_{\pi} v_{\pi}(s)$

 

최적행동가치함수 $q_* (s, a)$는 모든 정책들 사이의 최대 행동-가치 함수를 정의한다.

$q_*(s, a) = \max_{\pi} q)_{\pi} (s, a)$

 

최적행동가치함수를 찾았다면, 그 강화학습은 끝난것이다.

 

 

최적 정책

최적 정책이란 MDP내에서 제일 잘 행동할 수 있는 정책을 고르는 것이다.

정책, 즉 상태와 행동의 관계에서 가장 좋은 것(보상을 많이 주는 것)을 고르는 것이 되겠다.

 

먼저 최적의 정책을 찾으려면, 정책을 비교하는 방법을 알아야 한다.

$\pi >= \pi' if v_{\pi}(s) >= v_{\pi'}(s), \forall s$

위의 수식을 설명하면 이렇다.

정책 $\pi$가 다른 정책 $\pi'$보다 낫다고 정의되려면,

$\pi$의 가치함수의 값이 $\pi'$의 가치함수의 값보다 커야한다.

 

 

최적 정책 법칙

• 모든 MDP에서는, 다른 모든 정책보다 나은 최적 정책 $\pi_*$가 존재한다.
• 또한 여러개의 최적 정책이 존재할 수 있다. (마지막에 같은 보상으로 같은 상태에 도달한다)
• 모든 최적 정책들은 같은 최적 가치 함수의 값을 이루게 된다. $v_{\pi_{*}}(s) = v_*(s)$
• 모든 최적 정책들은 같은 최적 행동-가치 함수를 이루게 된다. $q_{\pi_{*}}(s, a) = v_*(s, a)$

 

최적 정책을 찾는 법

최적 정책은 최대의 $q_*(s, a)$를 찾는것에 의해 찾아질 수 있다.

$\pi_*(a|s) = \begin{cases} 1,&\mbox{if}\quad a == argmax\quad q_*(s, a) \\ 0,&otherwise \end{cases}$

 

먼저 $q_*$를 찾기 위해 수식을 풀고, 가장 좋은 $q_*$를 주는 행동을 찾는 것이다.

따라서, 모든  MDP에는 결론이 되는 최적 정책이 존재하고, $q_*(s, a)$를 풀었다면, 우리는 그것을 찾은것이다.

 

 

벨만 최적 방정식 for v (상태 가치 함수)

우리가 $q_*$를 구한다면 끝이지만, 어떻게 $q_*$까지 도달할 수 있을까?

벨만 최적 방정식은 우리가 $q_*$의 해를 풀 수 있게 해준다.

이전에 언급했던 벨만 기대 방정식이 형재 상태에서 얻을 수 있는 모든 보상의 평균값이었다면, 벨만 최적 방정식은, 그 모든 보상들 중 최적의 보상을 고르는 수식이 된다.

$v_*(s) = \max_{a} q_*(s, a)$

 

 

벨만 최적 방정식 for q (행동 가치 함수)

어떤 행동이 최적의 보상을 주는지를 결정하는 방정식이다.

어떤 행동을 취한 뒤 (환경의 개입에 의해) 도달할 수 있는 상태는 각각 최적 가치 함수를 가지고 있다.

이 행동의 결과는 환경이 제어하기 때문에, 최적값을 바로 뽑아낼 수는 없다.

현재 행동의 보상과, 따라서 행동을 취한 뒤 도달할 수  있는 모든 상태의 가치함수들의 평균이 이 방정식이 된다.

$q_*(s, a) = R^{a}_{s} + \gamma \sum_{s' \in S} P^{a}_{ss'} v_*{s'}$

 

이 역시 벨만기대방정식때와 같이 최적의 해를 찾기 전까지 쌍으로 반복된다.

 

 

벨만 최적 방정식을 푸는 방법

• 벨만 최적 방정식은 비선형 함수이다.
• 보통은 닫힌 형태의 답이 존재하지 않는다.
• 반복이 답을 구하게 된다.
• 가치 반복
• 정책 반복
• 큐러닝
• Sarsa

참고자료

위 자료는 아래 유튜브의 강의 내용을 정리한 것입니다.

https://www.youtube.com/watch?v=2pWv7GOvuf0&list=PL7-jPKtc4r78-wCZcQn5IqyuWhBZ8fOxT&index=1