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

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

이전의 내용은 아래의 링크를 참고해주세요.

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

---

 

MDP(Markov decision processes: 마르코프 결정 과정)

MDP는 MRP에 행동을 추가한 과정이다.

 

정의

MDP는 $<S, A, P, R,\gamma>$인 튜플이다.
- S: 상태의 집합
- A: 행동들의 집합
- p(상태 천이 행렬): $P_{SS'}^a= P[S_{t+1}=s' |S_t=s, A_t=a]$
- R(보상 함수): S X A
- $\gamma$: 할인율, 감소율 

적절한 action을 가함으로써 미래의 상태와 보상을 바꿀 수 있다.

정책 함수(policy function, $\pi$)

정책 함수는 현재 상태에서 수행할 행동의 확률 분포이다.
$\pi(a|s)= P(A_t=a|S_t=s)$
마르코프 특성을 가정했으므로 현재 상태만 가지고 행동을 결정해도 충분하다.

즉, 정책에 따라 P, R의 값이 달라진다. 그만큼 좋은 정책을 가지고 있다면 최대한 많은 이득을 얻을 수 있다.

state value function(상태 가치 함수)

현재 상태에서 정책을 따른다면 얻을 미래의 가치
$V_{\pi}(s)= E_{\pi}[G_t|S_t=s]$
$= \Sigma_{a \in A}\pi(a|s)Q_{\pi}(s,a)$
즉, 상태 s에서 행동 a를 할 확률 ($\pi(a|s)$)과 가치($Q_{\pi}(s,a)$)를 곱하면 현재 상태의 가치가 된다.
아래의 $Q_{\pi}(s,a)$를 대입하면
$=R_s^\pi + \gamma \Sigma_{S' \in S}P_{ss'}^aV_{\pi}(S')= R^{\pi}+ \gamma P^{\pi}v$ 로 표현할 수 있다.

* $R_s^\pi=\Sigma_{a\in A} \pi(a|s) R_s^a$
 * $R_{ss'}^\pi=\Sigma_{a\in A} \pi(a|s) R_{ss'}^a$

state-action value function(행동 가치 함수)

현재 상태 s에서 a라는 행동을 취한 후, 정책을 따른다면 얻을 미래의 가치
$Q_{\pi}(s)= E_{\pi}[G_t|S_t=s, A_t=a]$
$Q_{\pi}(s,a)=R_s^a+ \gamma \Sigma_{S' \in S}P_{ss'}V_{\pi}(S')$
식을 보면 알 수 있듯이, 정책이 정해지면 MDP는 MRP로 변한다. 즉, 어떤 정책이 결정되느냐에 따라 가치 함수의 값들이 달라진다.

bellman equation의 행렬 표현

$v= R^{\pi}+ \gamma P^{\pi}$
$=(I-\gamma P^{\pi})^{-1}R^{\pi}$
행렬로 표현할 수 있고, 다음의 식을 이용해 직접해를 구할 수 있다.

이렇게 좋은 정책만 있으면 최대한 많은 이득을 얻을 수 있다.
그렇다면 정책은 어떻게 구해야 할까?

최적 가치 함수(optimal value function)

$V^*(s)= max_{\pi}V_{\pi}(s)$
state s에서 가장 높은 가치를 만드는 $\pi$를 적용하며, 최적 행동 가치 함수 또한 마찬가지다.
즉, 가장 높은 가치를 만드는 정책을 골라야 한다.

optimal policy(최적 정책)

최적  행동 가치 함수 $Q^*(s,a)= max_{\pi}Q_{\pi}(s,a)$를 안다면 정책에 대해 (0,1)의 확률을 주면서 최종 정책을 만들 수 있다.
즉, $\pi^*(a|s)=$argmax인 state에 대해서는 1의 확률(무조건 해당 state를 거침), 나머지 state에 대해서는 0의 확률을 준다.
 

벨만 최적 방정식

$Q^*(s,a)= R_s^a+ \gamma \Sigma_{S' \in S}P_{ss'}^aV_{\pi}^*(S')$ 
기존의 행동 가치 함수에서 $V^*$를 대입해서 얻을 수 있다.

Bellman Optimality Equation(BOE)

위의 벨만 최적 방정식에서 Q*공식에 V*의 argmax..를 대입하면 BOE가 나온다.
하지만, 이전의 방정식과는 다르게 BOE는 직접해가 존재하지 않는다. 대신 반복적 알고리즘을 통해 해를 계산할 수 있는데, 여기서 policy evaluation, value iteration, Q-Learning, SARSA 등을 이용한다.