[강화학습: RL] 2-1. 마르코프, Markov(MP, MRP)

단단한 강화 학습 3장 '유한 마르코프 결정 과정'과 인터넷 강의를 참고해서 만든 게시글입니다.

---

이번 게시글에서는 MP, MRP를, 다음 게시글에서는 MDP(Markov Decision Process, 마르코프 결정 과정)을 다루도록 하겠다.

MP(Markov Processes): 마르코프 과정

마르코프 특성

$P(S_{t+1}|S_t)= P(S_{t+1}|S_t, S_{t-1},...S_0)$  
현재 상태 $S_t$를 알면 역사를 아는 것과 동일한 수준으로 미래 상태를 추론할 수 있다. 즉, 미래 상태는 과거와 무관하게 현재의 상태만으로 결정될 수 있다. 따라서 마르코프에서는 과거의 state는 필요 없고, 현재의 state만 있으면 학습이 가능하다.

 

정의

MP는 <S, P>인 튜플로 정의된다.  
- S: (유한한) 상태의 집합  
- P: State transition matrix, 상태 천이 행렬로 현재 state에서 다음 state로 이동할 확률을 정의한다. 만약, n개의 state가 존재한다면, P는 n, n의 matrix형태로 정의된다.  
  
길 찾기를 예시로 들어보자.  
- S={서울, 부산, 대전, 원주, 광주, 대구, 울산}으로 정의할 수 있다.  
- $P_{서울, 부산}$은 서울에서 부산으로 갈 확률이다. 따라서 state의 크기만큼 (7,7) 행렬로 정의된다.  

 State transition matrix(상태 천이 행렬)
상태 천이 행렬을 구해보자. 아래와 같은 예시가 있고, 열의 순서를 E, A라고 한다면
matrix는 $\begin{bmatrix} 0.3& 0.7\\ 0.4& 0.6\end{bmatrix}$ 로 생성된다.

https://en.wikipedia.org/wiki/Markov_chain

---

MRP(Markov Reward Processes): 마르코프 보상 과정

MRP는 MP에 보상을 추가한 과정이다.

 

정의

MRP는 $<S,P,R, \gamma>$ 로 이뤄져 있고, MP에서 $R, \gamma$가 추가되었다.
- R: 보상 함수
- $\gamma$: 할인율(discounted return)을 뜻하며, 0~1 사이의 실수이다. 이를 사용하는 이유는 미래보다 현재의 보상을 더 크게 하기 위함이다.

$G_t$ (gain, 이득)

강화 학습은 기대되는 이득 (expected return)을 최대화해야 한다. 따라서, 이득이 최대화되도록 행동을 선택한다.
$G_t= R_{t+1}+R_{t+2}+...+R_T$로 정의할 수 있다. 
할인율을 고려하면 $G_t= R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+...$로 표현된다.

할인율을 고려하는 이유는 아래와 같다.
- 감가 하면 값이 무한히 커지는 것을 방지한다. 
만약, 최종 T(시간 단계)가 유한하지 않고, 무한이라고 생각해보면 최대화하려고 하는 gain 자체가 쉽게 무한이 될 수 있기 때문에 제대로 학습이 되지 않는다.
- 수학적 계산이 쉬워진다.
- 먼 미래는 불확실한 것을 반영한다.

따라서 대부분 할인율을 고려하지만, 항상 에피소드가 끝나는 경우에는 할인율을 고려하지 않기도 한다(할인율=1).

value function(가치 함수)

가치 함수는 agent가 주어진 state에 있는 것이 얼마나 좋은지를 추정하는 함수이다. 얼마나 좋은지는 미래의 보상을 기준으로 즉, 이득의 기댓값을 기준으로 정의된다. 
$V(s)= E[G_t|S_t=s]$ 로 주어진 state에서의 가치를 표현한다.

가치 함수를 bellman equation(벨만 방정식)으로 풀어쓸 수 있다.
$V(s)= E[G_t|S_t=s]$ 위에서 정의했던 $G_t= R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+...$를 대입한다.
$=E[R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+...|S_t=s]$
$=E[R_{t+1}+\gamma(R_{t+2}+\gamma2 R_{t+3}+...)|S_t=s]$
* $G_t= R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3}+...$를 또다시 이용해 G로 묶어준다.
 
 $=E[R_{t+1} +\gamma G_{t+1}|S_t=s]$....(1)
$=E[R_{t+1} +\gamma V(S_{t+1})|S_t=s]$...(2)
$=R(S) + \gamma \Sigma_{S' \in S_{t+1}}P_{ss'}V(S')= R+\gamma Pv$
즉, 현재 reward와 상태 천이 행렬(State transition matrix)*상태들의 가치로 표현할 수 있다.

* 추가 증명 (1) -> (2)
 $=E[R_{t+1} +\gamma G_{t+1}|S_t=s]=E[R_{t+1} |S_t=s]  +E[\gamma G_{t+1}|S_t=s]$
 $=E[R_{t+1} |S_t=s]  +\gamma E[G_{t+1}|S_t=s]$
 $=E[R_{t+1} |S_t=s]  +\gamma V(S_{t+1})$
 $=E[R_{t+1} |S_t=s]  +\gamma E[V(S_{t+1})|S_t=s]$
 $=E[R_{t+1}+ \gamma V(S_{t+1})|S_t= s]$
 t+1 상태의 가치는 t+1상태의 가치들의 평균값과 같다를 이용한 증명이다.
 
벨만 방정식을 행렬로 표현하면 다음과 같다.

즉, 벨만 방정식으로 모든 state의 가치를 파악할 수 있다.

벨만 방정식 풀이법

$v= R+\gamma Pv$
$(I-\gamma P)v=R$
$v=(I-\gamma P)^{-1}R$
위의 식으로 직접적으로 해를 구할 수 있다. 하지만, n이 커질수록 직접적으로 문제를 푸는 것이 어려워진다. 이런 경우 DP, MC, TD 등을 활용해 문제를 풀 수 있다.