[강화학습] Markorv Decision Process

이 글은 강화학습 스터디를 진행하면서 공부한 내용을 정리한 글이다.

마르코프 결정 프로세스(MDP)

강화학습에서 문제를 잘 정의하려면 주어진 문제를 MDP형태로 만들어야 한다.

“순차적 의사 결정 문제”는 MDP 개념을 통해 더 정확하게 표현할 수 있다.

마르코프 결정 프로세스 개념은 마르코프 프로세스와 마르코프 리워드 프로세스를 거친다. 이들은 모두 마르코프 성질을 만족한다.

마르코프 성질(Markov Property)

다음을 만족하면 마르코프 성질을 따른다고 한다.

$$
\mathbb{P}[\mathbf{s_{t+1}}|\mathbf{s_t}] = \mathbb{P}[\mathbf{s_{t+1}}|\mathbf{s_1, s_2, ...,s_t}]
$$

이는 미래는 오로지 현재에 의해 결정된다는 것을 의미한다.

바둑 경기와 같이 오로지 찰나의 순간을 확인했을 때 어떤 상황인지 알 수 있는 경우는 마르코프한 상태이다. 과거가 어떤 상황이었는지의 정보를 알지 않아도 충분히 특정 시점의 바둑 경기를 봐도 어떤 상황이고 어떤 수를 두어야 하는지 생각해낼 수 있다.

그러나 축구 경기 중 한 순간을 캡처했을 때는 선수가 공을 패스할 것인지, 드리블을 할 것인지, 슈팅을 할 것인지 알기 힘들 가능성이 높다. 이런 경우는 마르코프하지 않은 상태이다. 이 경우 연속적인 시점의 정보를 엮음으로써 더 마르코프한 상태로 만들 수 있다.

마르코프 프로세스(Markov Process)

미리 정의된 확률 분포를 따라 상태와 상태 사이를 이동하는 프로세스

각각의 상태를 $s_0, s_1, …$ 라고 하고 상태의 집합을 $S$라고 한다.

특정 상태에서 다음 상태로 도착할 확률을 전이 확률이라고 한다. $P_{ss’}$는 상태 $s$에서 상태 $s’$가 될 확률을 의미한다. $P_{ss’} = P[S_{t+1}=s’|S_t=s]$

마르코프 리워드 프로세스(Markov Reward Process)

마르코프 프로세스에서 보상이라는 개념이 추가된 것이다.

각 상태가 얼마나 좋은지를 알기 위해 상태 별로 가치를 매긴다.

어떤 상태의 가치는 특정 시점에서부터 미래에 일어날 보상을 기준으로 평가된다. 따라서 특정 상태의 가치는 특정 상태에서부터 에피소드가 끝날 때까지의 보상의 합이 된다. 그러나 미래의 불확실성과 미래보단 현재가 더 중요하기 때문에 종료시점까지의 보상을 모두 동일하게 더해버리면 비효율적이다. 이를 보완하기 위해서 감쇠 인자 $\gamma$가 사용된다. 미래에 발생할 보상에 0과 1사이의 값을 곱해 더 적게 반영하게 한다. 이렇게 해서 계산된 특정 시점에서부터 미래에 받을 보상의 합을 리턴(return)이라고 한다.

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

강화학습은 보상이 아니라 리턴을 최대화하도록 학습하는 것임을 강조한다.

특정 상태에서 보상을 받고 시작하여 종료 상태까지 도달하여 보상을 받는 것까지를 에피소드라고 한다. 에피소드 별로 리턴 값이 다르게 계산된다. 가능한 모든 에피소드를 반영해서 리턴을 계산하는 것이 이상적이지만, 그것은 불가능하기 때문에 샘플링을 해서 그의 기댓값을 사용한다. (Monte-Carlo 접근법을 사용한다.)

리턴의 기댓값을 통해 상태의 가치를 계산할 수 있다. 이러한 관계를 수식으로 표현하면 다음과 같고, 이를 상태 가치 함수(state value function)라고 한다.

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

마르코프 결정 프로세스(Markov Decision Process)

MP와 MRP는 상태 변화가 자동적으로 이루어졌다. 그러나 이들은 순차적 의사결정 문제를 모델링 할 수 없다. 의사결정을 할 수 없기 때문이다. 따라서 자신의 의사를 가지고 행동하는 에이전트의 개념을 추가한다.

에이전트는 각 상황마다 행동을 취한다. 해당 행동에 의해 상태가 변하고 그에 따른 보상을 받는다. MRP에서 행동에 대한 변수가 추가되는 것 외에도 전이 확률 행렬 정의에 변화가 생긴다. MP와 MRP에서는 상태에 따라 다음 상태가 결정되지만, MDP에서는 에이전트가 선택한 액션에 따라 다음 상태가 달라지기 때문이다. 전이 확률 행렬의 표기는 $P^{a}_{ss’}$로 바뀐다.

$$
P^a_{ss'} = \mathbb P[S_{t+1}=s'|S_t=s, A_t=a]
$$

이때 주의해야할 점은 같은 상태 s에서 같은 액션 a를 선택해도 매번 다른 상태에 도착할 수 있다는 것이다. 이것은 에이전트가 통제할 수 없는 환경적인 요인으로 인해 발생한다.

뿐만 아니라 액션은 보상에도 영향을 준다. 현재 상태 s에서 어떤 액션을 선택하느냐에 따라 받는 보상이 달라진다.

$$
R^a_s=\mathbb E[R_{t+1}|S_t=s, A_t=a]
$$

각 상태 s에 따라 어떤 액션 a를 선택해야 보상의 합을 최대로 할 수 있는가를 찾아야 한다. 보통은 전략이라고 표현할 수 있지만, 강화학습에서는 이를 정책(policy)이라고 한다. 이러한 관계를 나타낸 함수를 정책 함수라고 한다.

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

• 각 상태에서 할 수 있는 모든 액션의 확률 값을 더하면 1이 된다.
• 정책 함수는 에이전트 안에 존재한다.

상태 가치 함수

MRP에서와 조금 다르게, MDP에서는 에이전트의 정책 함수에 따라 얻는 리턴이 달라진다. 따라서 MDP의 경우 정책 함수가 정의되어야 가치 함수를 정의할 수 있다.

$$
v_{\pi}(s)=\mathbb E_\pi [r_{t+1}+\gamma r_{t+2}+\gamma^2 r_{t+3} + ...|S_t=s] = \mathbb E_\pi[G_t|S_t=s]
$$

액션 가치 함수

각 상태에서의 액션의 가치를 평가하는 함수다.

상태에 따라 액션도 달라지기 때문에 액션 가치 함수는 상태 s와 액션 a를 변수로 가진다. 이를 수학적으로 표현하면 다음과 같다.

$$
q_\pi(s,a) = \mathbb E_\pi[G_t|S_t=s , A=a]
$$

상태 가치 함수와 액션 가치 함수의 차이는 $v_\pi(s)$를 계산할 때는 s에서 $\pi$가 액션을 선택하는 반면, $q_\pi(s,a)$를 계산할 때는 s에서 강제로 a를 따로 선택한다. 둘다 모두 액션을 선택한 이후에는 정책함수를 따라서 에피소드가 끝날 때까지 진행한다.

MDP가 주어졌을 때 주로 하게되는 테스크는 prediction과 control이다.

prediction은 $\pi$가 주어졌을 때 각 상태의 가치를 평가하는 문제이고 (value를 예측),

control은 최적 정책 $\pi^*$를 찾는 문제다.