2. 마르코프 결정 프로세스

2.1 마르코프 프로세스

강화학습은 "순차적 의사결정 문제"를 푸는 "방법론".
"순차적 의사결정^{Sequential decision making} 문제"는 결국 MDP^{Markov Decision Process} 라는 개념을 통해서 정확하게 표현할 수 있다.

Markov Process

$$MP \equiv (S, P)$$

• 상태의 집합 $S$

$$S= \{s_0, s_1, s_2, s_3, s_4 \}$$

• 전이 확률 행렬 $P$
전이 확률^{transition probability} 은 상태 $s$ 에서 다음 상태 $s'$ 에 도착할 확률을 가리킨다.

$$P_{ss'}$$

$P_{ss'}$ 의 조건부 확률 개념을 이용한 표현 방식

$$P_{ss'} = \mathbb{P}[S_{t+1} = s'|S_t = s]$$

전이 확률은 $s$ 와 $s'$ 에 대하여 행렬의 형태로 표현할 수 있다.

위 그림을 예로 상태 $s$ 5개를 행과 열로 하여 확률 값을 아래에 행렬^Matrix 표로 표현.
< 상태 $\rightarrow$ 상태 ( $s \rightarrow s'$ ) >

	누움($s_0$)	일어남($s_1$)	눈감음($s_2$)	잠이 옴($s_3$)	잠 듦($s_4$)
누움($s_0$)		0.4	0.6
일어남($s_1$)	0.1	0.9
눈감음($s_2$)				0.7	0.3
잠이 옴($s_3$)					1.0
잠 듦($s_4$)					1.0

| 전이 확률 행렬, 표 |

마르코프 성질

마르코프 프로세스의 모든 상태^state는 마르코프 성질^{Markov Property}를 따른다.

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

• 마르코프한 상태 ^{Markovian state}

  시스템의 다음 상태가 오직 현재 상태에 의해서만 결정될 때, 그 상태를 마르코프한 상태라고 한다. 즉, 과거의 상태는 미래의 상태에 아무런 영향을 미치지 않는다는 의미.

  ex)

  • 체스
  • 바둑
  • 날씨: 오늘 날씨가 맑으면 내일 비가 올 확률은 오늘 날씨에만 의존하며, 어제 날씨와는 무관합니다.
  • 주식 시장: 주식 시장의 내일 주가는 오늘의 주가와 시장 상황에 의해 결정되며, 과거의 주가 변동은 직접적인 영향을 미치지 않습니다.
  • 랜덤워크: 다음 위치는 현재 위치와 이동 방향에만 의존하며, 이전 위치는 고려하지 않습니다.

• 마르코프하지 않은 상태

  예측 시 과거의 이력이 영향을 미치면 마르코프하지 않은 상태라 할 수 있다.

  ex)

  • 카드 게임: 카드 게임에서 다음에 뽑을 카드는 현재 손에 들고 있는 카드와 이전에 버려진 카드들에 영향을 받습니다. (남은 덱에 어떤 카드가 남아있는지 추론 가능)
  • 고객 구매 패턴: 고객의 다음 구매는 현재 구매뿐만 아니라 과거 구매 이력에도 영향을 받을 수 있습니다. (특정 제품을 자주 구매하는 고객은 다음에 그 제품을 또 구매할 확률이 높음)
  • 언어 모델: 문장에서 다음에 나올 단어는 현재 단어뿐만 아니라 앞에 나온 단어들에도 영향을 받습니다. (문맥을 고려해야 자연스러운 문장이 생성됨)

---

2.2 마르코프 리워드 프로세스

마르코프 프로세스에 보상의 개념이 추가되면 마르코프 리워드 프로세스^{Markov Reward Process} 가 된다.

마르코프 프로세스는 $MP \equiv (S, P)$ 상태의 집합 $S$, 전이 확률 행렬 $P$ 로 정의 되는데, $MRP$를 정의하기 위해서는 보상함수 $R$ 과 감쇠 인자 $\gamma$ 가 "2가지 요소"로 추가로 필요.

$$MRP \equiv (S, P, R, \gamma )$$

• 상태$^{State}$ 의 집합 $S$

• 전이 확률 행렬 $P$

• 보상 함수 $R$ : 어떤 생태 $s$ 에 도착했을 때 받게 되는 보상을 의미

$$R = \mathbb{E}[R_t|S_t = s]$$

• 감쇠 인자 $\gamma$ ^감마

• $\gamma$ 는 0에서 1사이의 숫자.
• 강화 학습에서 미래에 얻을 보상에 비해 당장 얻는 보상을 얼마나 더 중요하게 여길지 나타내는 파라미터.
• 구체적으로 미래에 얻을 보상 값에 $\gamma$ 가 여러번 곱해지며 그 값을 작게 한다.

감쇠된 보상의 합, Return

$MRP$ 에서는 $MP$ 와 다르게 상태($s$)가 바뀔때마다 해당하는 보상($R$)을 얻는다. ($T$는 타임스텝)

$$s_0, R_0, s_1, R_1, s_2, R_2,..., s_T, R_T$$

이와 같은 하나의 여정을 강화 학습에서는 에피소드^episode 라 한다.

리턴^return $G_t$ 을 정의하면,

Return (보상의 합)

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

$\gamma$ 는 왜 필요한가?

$\gamma$는 리턴을 나타내는 식에서 $\gamma=0$ 이면 당장 얻는 보상만을 반영, 미래보상을 0으로 하여 근시안적인 에이전트가 된다. 반면 $\gamma = 1$ 이면 모든 타임 스텝의 보상을 평등하게 보며 매우 장기적인 시야를 가진 에이전트가 된다. 이는 $\gamma$에 대한 직관적인 이해이다.

$\gamma$ 가 꼭 필요한 이유 3가지가 있다.

• 수학적 편리성 : $\gamma$ 를 1보다 작게 함으로 리턴 $G_t$ 가 무한의 값을 가지는 것을 방지
• 사람의 선호 반영 : 예시로 당장 큰 금액의 복권과 장기적으로 지급 받는 연금복권이 있다.
• 미래에 대한 불확실성 반영

MRP에서 각 상태의 밸류 평가하기

상태 $s_2$ 에 이르기 까지 이전의 누적보상, $s_2$ 이후의 누적보상, 2가지의 경우가 있다. 해당 상태 $s_2$의 가치를 평가한다고 하면 해당 상태 이후의 누적보상을 고려하게 된다.

즉, $s_2$ 의 가치를 평가한다면, $s_2$ 이후 부터의 리턴을 측정한다. 하지만 리턴 값은 확률로 결정되며 매번 바뀌게 된다.

즉 $s_2$의 가치(밸류)를 평가해야 하는 방법은 리턴의 기댓값^Expectation을 사용하는 것이다.

에피소드 샘플링

$s_0$ 에서 $s_T$ 까지 가는 하나의 여정을 에피소드라 했다. 그런데 하나의 에피소드 안에서 무수히 많은 경우가 있다. 매번 에피소드가 어떻게 샘플링^Sampling(확률분포에서 표본추출) 되느냐에 따라 리턴이 달라진다.

표본추출을 통해서 어떤 값을 유추하는 방법론을 사용하게 되는데 이를 대표적인 방법론으로 Monte-Carlo 접근법 이라 한다.

상태 가치 함수

State Value Function

State Value Function

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

: 상태 s로부터 시작하여 얻는 리턴의 기댓값 "

---

2.3 마르코프 결정 프로세스

MP와 MRP에서는 상태 변화가 자동으로 이루어졌다. 다음 상태의 분포는 미리 정해진 확률에 이미 정해져 있다. 그러므로 MP, MRP 로는 순차적 의사 결정 문제를 모델링 할 수 가 없다.
순차적 의사 결정 문제는 의사 결정이 핵심이며, 이를 위해 에이전트가 등장한다.

MDP의 정의

Markov Decision Process

$$MDP \equiv (S,A,P,R,\gamma)$$

• 상태의 집합 $S$
마르코프 프로세스^MP, 마르코프 보상 프로세스^MRP 에서의 $S$ 와 같다.

• 액션의 집합 $A$
MDP에서 새로이 추가, 에이전트가 취할 수 있는 행동들을 모아 놓은 집합.

• 전이 확률 행렬 $P$
에이전트가 선택한 액션에 따라서 다음 상태가 달라짐, 하지만 결정적이지 않으며 확률이다.
MP, MRP 에서 전이확률행렬 은 $P_{ss'}$ 이었으나 MDP에서는 선택한 액션에 따라 다음 상태가 확률로 변한다.
조건부가 2가지로 붙게 된다. $s, a$ 상태와 행동

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

• 보상 함수 $R$
MRP는 상태에 의해 보상이 정해졌으나 MDP는 액션이 추가된다.

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

• 감쇠 인자 $\gamma$
MRP에서 $\gamma$ 와 동일하다.

아이 재우기 MDP

기존 아이가 잠드는 상황에서 어머니라는 에이전트가 개입하고 에이전트가 취할 수 있는 액션이 생겼다.

위 도표를 보면 상태 $s_2$ 에서 $a_1$행동을 취한다면 그 전이 확률을 아래 수식과 같이 표현할 수 있다.

전이 확률

$$P^{a_{1}}_{s_{2}, s_0} = 0.3 , \ \ \ P^{a_{1}}_{s_{2}, s_1} = 0.7$$

위 처럼 MDP가 간단하다면 최적 행동 하나만을 선택하면 되기에 최적 전략을 찾기 쉬우나
아래와 같이 복잡해진다면 최적 행동을 찾는 것이 쉽지만은 않다.

강화 학습에서 결국 찾고자 하는 것은
각 상태 $s$ 에서 어떤 액션 $a$ 를 선택해야 보상의 합을 최대로 할 수 있는가 이다.
이를 정책^Policy 이라고 한다.

정책 함수와 2가지 가치 함수

• 정책 함수^{policy function}
: 각 상태에서 어떤 액션을 선택할지 정해주는 함수.

policy function

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

: 상태 $s$ 에서 액션 $a$ 를 선택할 확률

바로 위에 그림에서 액션은 $a_0, a_1, a_2$ 3가지 이다.

각각에 대해 얼마큼의 확률을 부여할지를 정책 함수가 결정한다.

$$\pi(a_0|s_0)= 0.2$$ $$\pi(a_1|s_0)= 0.5$$ $$\pi(a_2|s_0)= 0.3$$

• 상태 가치 함수^{state value function} MRP에서 상태 가치 함수 와 비슷하나 에이전트^agent 및 액션^action이 포함되어 정책^policy을 반영해야 한다.

state value function

$$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$ 부터 끝까지 $π$ 를 따라서 움직일 때 얻는 리턴의 기댓값

• 액션 가치 함수^{state-action value function}

state-action value function

$$\mathrm{q}_{\pi}(s,a)=\mathbb{E}_\pi[G_t|S_t = s, A_t=a]$$

: $s$ 에서 $a$ 를 선택하고, 그 이후에는 $π$ 를 따라서 움직일 때 얻는 리턴의 기댓값

---

3.4 Prediction과 Control

MDP를 푼다는 것은 MDP가 주어 졌을때 즉, $(S,A, P, R, \gamma)$ 가 주어졌을때 주된 테스크는 2가지가 있다.

1. Prediction : 정책 $π$ 가 주어졌을 때 각 상태 $s$의 밸류 $v_\pi(s)$를 평가하는 문제
2. Control : 최적 정책 $π^*$ 를 찾는 문제

최적 정책^{optimal policy} $\pi^*$을 찾거나, 임의의 정책 $π$에 대해 각 상태의 밸류 $v_π(s)$ 구하고자 하는 것.

최적 정책^{optimal policy} $\pi^*$ 를 따를 때의 가치 함수를 최적 가치 함수^{optimal value function} $v^*$ 라고한다.

$\pi^*$, $v^*$ 를 찾았다면 "이 MDP는 풀렸다" 고 할 수 있다.