CH2. 마르코프 결정 프로세스
[바닥부터 배우는 강화학습] CH2. 마르코프 결정 프로세스을 읽고 정리한 내용입니다.
강화 학습에서 문제를 잘 정의하려면 주어진 문제를 MDP(Markov Decision Process)의 형태로 만들어야 한다.
마르코프 프로세스(Markov Process)
- 미리 정의된 어떤 확률 분포를 따라서 상태와 상태 사이를 이동하는 프로세스
- 어떤 state에 도착했을 때, 다음 state가 어디가 될지 각각에 해당되는 확률이 있고 그 확률에 따라 다음 state가 결정됨
- 하나의 상태에서 뻗어 나가는 화살표의 합은 항상 100%다
- 상태의 집합 $S$
- 가능한 상태들을 모두 모아 놓은 집합
- $S = {s_0, s_1, … }$
- 전이 확률 행렬 $P$
- transition probability $P_{SS’}$는 상태 $S$에서 다음 상태 $S’$에 도착할 확률을 나타낸다.
- 조건부 확률 개념을 이용해서 표현해보면, $P_{SS’} = \mathbb{P}[S_{t+1}=s’|S_t=s]$
- 즉, 시점 t에서 상태가 s였다면 t+1에서의 상태가 s’이 될 확률을 구한 것.
마르코프 성질
- 미래는 오로지 현재에 의해 결정된다.
- 마르코프 프로세스에서 다음 상태 $s_{t+1}$이 될 확률을 계산하려면 현재의 상태 $s_t$가 무엇인지만 주어지면 충분하다.
- 이전에 방문했던 state들은 t+1 시점에 아무런 영향을 주지 못한다.
마르코프 리워드 프로세스 (Markov Reward Process)
MRP를 정의하기 위해서는 reward function $R$과 damping factor $\gamma$ 가 필요하다. \(MRP \equiv (S,P,R,\gamma)\)
- S, P는 이전과 동일
- 보상 함수 $R$
- 어떤 state s에 도착했을 때 받게 되는 보상
- \[R = \mathbb{E}[R_t|S_t=s]\]
- 특정 상태에 도달했을 때 받는 보상이 매번 조금씩 다를 수 있기 때문에 기댓값으로 표현한다
- damping factor $\gamma$
- 0과 1 사이의 숫자
- 미래 얻을 보상에 비해 당장 얻는 보상을 얼마나 더 중요하게 여길 것인지를 나타내는 파라미터
- 미래에 얻을 보상의 값에 $\gamma$가 여러번 곱해지는 형식
감쇠된 보상의 합, Return
- MRP에서는 MP와 다르게 상태가 바뀔 때마다 해당하는 보상을 얻음
episode: $s_0$에서 종료 상태 $s_r$까지 가는 여정- Return은 아래와 같이 정의됨. \(G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ...\)
- 위 식에 따라 리턴은 t시점부터 미래에 받을 감쇠된 보상의 합이 된다.
- 현재에서 멀어질수록 $\gamma$가 여러번 곱해지기 때문에
- 따라서 $\gamma$의 크기를 통해 미래 얻게 될 보상에 비해 현재 얻는 보상에 가중치를 줄 수 있다
$\gamma$의 필요성
- 만일 감마가 0이라면 미래의 보상은 모두 0이 되고, 감마가 1이라면 현재의 보상과 미래의 보상이 완전히 대등해진다.
- 수학적 편리성, 사람의 선호 반영, 미래에 대한 불확실성 반영
에피소드의 샘플링
- 에피소드가 어떻게 sampling되냐에 따라 리턴은 달라진다
- Monte-Carlo 접근법
State Value Function (상태 가치 함수)
에피소드마다 리턴이 다르기 때문에 특정 state s의 v는 기댓값을 이용하여 정의함.
\[v(s) = \mathbb{E}[G_t|S_t = s]\]마르코프 결정 프로세스
MDP의 정의
MDP는 MRP에 에이전트가 정해진 것이다. \(MDP \equiv (S,A,P,R,\gamma)\)
전이 확률 행렬 P는 에이전트가 바꿔줄 수 있는 부분이 아니며, 같은 상태에서 같은 액션을 해도 확률적으로 다음 상태가 달라질 수 있다.
이를 수식으로 표현하면 $ P^a_{ss’} = \mathbb{P}[S_{t+1}=s’|S_t=s, A_t=a] $보상 함수 R : \(R^a_s = \mathbb{E}[R_{t+1}|S_t=s, A_t=a]\)
정책함수와 2가지 가치함수
정책 함수 : 각 상태에서 어떤 액션을 선택할지 정해주는 함수
$ \pi(a|s) = \mathbb{P}[A_t=a|S_t=s] $상태 가치 함수(state value function) : 어떤 상태가 주어졌을 때 그 상태를 평가해주는 함수
$ v_\pi (s) = \mathbb{E}\pi [r{t+1} + \gamma r_{t+2} + … | S_t =s] $액션 가치 함수(state-action value function) : s에서 a를 선택하고, 그 이후에는 $\pi$를 따라서 움직일 때 얻는 리턴의 기댓값
$ q_\pi (s,a) = \mathbb{E}_\pi [G_t|S_t=s, A_t=a] $
Prediction과 Control
- prediction : $\pi$가 주어졌을 때 각 상태의 벨류를 평가하는 문제
- control : 최적 policy를 찾는 문제. 즉, 이 세상에 모든 $\pi$ 중에서 가장 기대 리턴이 큰 $\pi$를 찾는다.