들어가며...

두 번째 글에서는 State가 단순히 지금 보이는 화면이 아니라, 미래를 판단하는 데 필요한 History를 담은 요약본이라고 정리했다. 그리고 현재 State를 알고 나면 더 오래된 과거가 다음 State 예측에 추가 정보를 주지 않는 성질을 Markov property라고 불렀다.

$$P(S_{t+1} \mid S_t) = P(S_{t+1} \mid S_1, \ldots, S_t)$$

그런데 State 하나를 잘 정의했다고 강화학습 문제가 완성되는 것은 아니다. Agent가 이동할 수 있는 다음 State는 무엇인지, 각 이동은 얼마나 자주 일어나는지, 그 과정에서 어떤 Reward를 받는지, Agent가 고를 수 있는 Action은 무엇인지도 적어야 한다.

이 정보를 차례대로 붙여 만든 것이 Markov Decision Process, 줄여서 MDP다.

처음 MDP라는 이름을 보면 새로운 Algorithm처럼 느껴질 수 있다. 본인도 처음에는 Q-Learning 옆에 MDP라는 학습 방법이 하나 더 있는 줄 알았다. 하지만 MDP는 문제를 푸는 Algorithm이 아니라 강화학습 환경을 수학으로 적는 형식에 가깝다.

Sudoku에 비유하면 MDP는 숫자가 채워진 문제지와 규칙이고, Q-Learning이나 Policy Gradient는 그 문제를 풀기 위한 방법이다. 문제지와 풀이법을 먼저 분리해두면 뒤에서 새로운 Algorithm이 등장해도 훨씬 덜 헷갈린다.

이번 글에서는 MDP를 한 번에 정의하지 않고 다음 세 단계로 조립해보려고 한다.

1. State와 Transition만 있는 Markov Process
2. Reward와 Discount factor를 붙인 Markov Reward Process
3. Agent의 Action을 붙인 Markov Decision Process

Markov Process: State가 확률에 따라 이동한다

Markov Process는 Markov Chain이라고도 부른다. Markov property를 만족하는 State들이 시간에 따라 이어지는 확률 과정이다.

$$S_1, S_2, S_3, \ldots$$

이 과정을 정의하려면 두 가지가 필요하다.

$$\text{Markov Process} = \langle \mathcal{S}, \mathcal{P} \rangle$$

• $\mathcal{S}$: 가능한 State의 집합
• $\mathcal{P}$: State 사이의 Transition probability

예를 들어 퇴근 직전의 본인이 있을 수 있는 장소를 다음과 같이 정했다고 하자.

$$\mathcal{S} = \{\text{DESK}, \text{CAFE}, \text{HOME}, \text{GYM}, \text{SLEEP}\}$$

현재 State가 DESK일 때 다음 State가 CAFE일 확률은 다음처럼 적는다.

$$\mathcal{P}_{ss'} = P(S_{t+1}=s' \mid S_t=s)$$

$s$는 현재 State, $s'$는 다음 State다. Prime 기호가 붙었다고 전혀 다른 종류의 변수가 된 것은 아니고, 같은 State 집합 안에서 다음 칸을 가리킬 뿐이다.

구체적인 값을 넣으면 다음과 같다.

$$P(S_{t+1}=\text{CAFE} \mid S_t=\text{DESK})=0.6$$

문장으로 읽으면 “지금 DESK에 있을 때 다음 State가 CAFE일 확률은 $0.6$”이다.

그림에서 DESK를 출발하는 확률은 CAFE $0.6$, HOME $0.3$, GYM $0.1$이다. 다음 State는 이 셋 중 하나여야 하므로 확률을 모두 더하면 $1$이 된다.

$$0.6 + 0.3 + 0.1 = 1$$

일반적으로도 현재 State $s$에서 가능한 모든 다음 State의 확률을 더하면 $1$이다.

$$\sum_{s' \in \mathcal{S}} \mathcal{P}_{ss'} = 1$$

현재 State마다 이런 확률을 한 줄씩 적어 모은 것을 State transition matrix라고 한다.

$$\mathcal{P} = \begin{bmatrix} \mathcal{P}_{11} & \cdots & \mathcal{P}_{1n} \\ \vdots & \ddots & \vdots \\ \mathcal{P}_{n1} & \cdots & \mathcal{P}_{nn} \end{bmatrix}$$

Matrix의 각 Row는 현재 State 하나, 각 Column은 다음 State 하나에 해당한다. 따라서 한 Row의 합은 항상 $1$이다.

여기까지는 Agent도 Action도 없다. DESK에서 CAFE로 갈지 HOME으로 갈지 본인이 선택하는 것이 아니라, 정해진 확률에 따라 다음 State가 나타난다. 이름은 Process지만 무언가를 학습하는 과정도 아니다. State가 어떤 확률 규칙으로 이어지는지를 적어둔 것이다.

Transition probability가 1이 아니면 틀린 걸까?

처음 강화학습 예시를 보면 화살표 위에 $0.6$, $0.3$ 같은 숫자가 적혀 있어서 괜히 현실을 부정확하게 표현한 것처럼 느껴질 수 있다. 내가 HOME Button을 눌렀으면 HOME으로 가는 것이지, 왜 확률이 필요한가 싶은 것이다.

하지만 같은 현재 상황에서도 결과가 달라질 수 있는 환경은 많다.

• Robot이 앞으로 걸었지만 바닥이 미끄러워 옆으로 밀릴 수 있다.
• 게임 Character가 공격했지만 일정 확률로 빗나갈 수 있다.
• 추천 System이 같은 Item을 보여줘도 사용자가 클릭할 수도 있고 지나칠 수도 있다.
• 같은 길로 출근해도 교통 상황에 따라 도착 시간이 달라질 수 있다.

Transition probability는 Agent가 우유부단하다는 뜻이 아니다. 같은 조건에서도 Environment의 결과가 달라질 수 있다는 불확실성을 표현한다.

물론 모든 Transition이 반드시 확률적일 필요는 없다. HOME에서 SLEEP으로 항상 이동하는 단순한 환경이라면 그 확률은 $1.0$이다. 이런 Transition을 Deterministic하다고 한다. Deterministic transition도 확률이 $1$인 특별한 경우로 Transition probability 안에 포함할 수 있다.

Markov Reward Process: 이동에 점수를 붙인다

Markov Process는 State가 어떻게 이동하는지는 알려주지만, 어떤 State가 좋은지는 말해주지 않는다. CAFE에 가는 것이 좋은지, GYM에 가는 것이 좋은지 숫자로 판단할 기준이 아직 없다.

여기에 Reward function $\mathcal{R}$과 Discount factor $\gamma$를 추가하면 Markov Reward Process, 줄여서 MRP가 된다.

$$\text{MRP} = \langle \mathcal{S}, \mathcal{P}, \mathcal{R}, \gamma \rangle$$

두 가지가 새로 들어왔다.

• $\mathcal{R}$: 각 State에서 기대하는 즉시 Reward
• $\gamma$: 미래 Reward를 현재 기준으로 얼마나 반영할지 정하는 Discount factor

David Silver 강의의 표기를 따르면 State $s$의 Reward function은 다음과 같다.

$$\mathcal{R}_s = \mathbb{E}[R_{t+1} \mid S_t=s]$$

이 수식은 “현재 State가 $s$일 때 다음에 받을 Reward의 평균적인 값”이라고 읽으면 된다.

Reward가 항상 같은 숫자로 나오는 환경이라면 Expectation이 조금 거창해 보일 수 있다. 하지만 같은 CAFE State에서도 대기 시간이 짧을 수도 있고, 주문이 잘못 나올 수도 있다. 실제 Reward가 매번 달라질 수 있으므로 여러 번 경험했을 때 평균적으로 얼마나 받을지를 Reward function으로 적는다.

첫 글에서 살펴본 Return도 여기서 다시 등장한다.

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

MRP에서는 State sequence가 확률에 따라 정해지고, 그 경로를 따라 Reward가 쌓인다. 같은 DESK에서 시작해도 어떤 날은 CAFE를 거쳐 HOME으로 갈 수 있고, 어떤 날은 바로 GYM으로 갈 수 있다. 따라서 실제 Return도 Episode마다 달라질 수 있다.

아직은 어떤 State의 Return이 평균적으로 얼마나 될지를 계산하지 않는다. 그 평균이 바로 다음 글에서 다룰 Value다. 이번 글에서는 MRP가 “어디로 이동하는가”뿐 아니라 “그 이동을 따라 어떤 Reward를 받는가”까지 표현한다는 점만 잡고 넘어가면 된다.

Reward 표기가 자료마다 다른 이유

강화학습 자료를 보다 보면 Reward function의 모양이 조금씩 다르다.

$$\mathcal{R}(s), \qquad \mathcal{R}(s,a), \qquad \mathcal{R}(s,a,s')$$

어떤 자료는 현재 State만으로 Reward를 정의하고, 어떤 자료는 State와 Action을 함께 사용한다. 다음 State까지 포함하는 경우도 있다.

예를 들어 벽에 부딪혔을 때 $-1$을 주는 미로에서는 현재 State보다 “어떤 Action을 했고 어디에 도착했는가”로 Reward를 적는 편이 자연스럽다. 반면 특정 State에 머무는 것 자체가 점수를 결정한다면 $\mathcal{R}(s)$만으로도 충분하다.

표기가 다르다고 서로 다른 강화학습을 이야기하는 것은 아니다. Reward가 어떤 조건에서 결정되는지를 어디까지 명시했는지의 차이다. 이번 시리즈에서는 David Silver 강의의 흐름에 맞춰 MRP에서는 $\mathcal{R}_s$, MDP에서는 $\mathcal{R}_s^a$ 표기를 사용한다.

Markov Decision Process: Agent의 선택을 넣는다

이제 마지막 조각인 Action을 추가해보자. MRP에 Agent가 선택할 수 있는 Action 집합 $\mathcal{A}$를 넣으면 Markov Decision Process가 된다.

$$\text{MDP} = \langle \mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma \rangle$$

각 기호를 문장으로 바꾸면 다음과 같다.

Action이 생겼으므로 Transition probability에도 조건이 하나 추가된다.

$$\mathcal{P}_{ss'}^a = P(S_{t+1}=s' \mid S_t=s, A_t=a)$$

MRP에서는 현재 State $s$만 알면 다음 State의 분포가 정해졌다. MDP에서는 현재 State에서 어떤 Action $a$를 선택했는지까지 알아야 다음 State의 분포가 정해진다.

Reward function도 같은 방식으로 Action을 조건에 넣는다.

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

문장으로 읽으면 “State $s$에서 Action $a$를 했을 때 다음에 받을 Reward의 평균”이다.

DESK라는 같은 State에서도 공부하러 가거나, 집으로 가거나, 운동하러 갈 수 있다. 바로 이 선택 때문에 이름에 Decision이 붙는다.

다만 Action과 Next State를 같은 것으로 생각하면 안 된다. “GYM으로 이동”이라는 Action을 골랐더라도 길이 막히거나 갑자기 문을 닫았다면 HOME State에 도착할 수 있다. Action은 Agent가 선택한 것이고, Next State는 그 Action을 받은 Environment가 Transition probability에 따라 만들어낸 결과다.

MP, MRP, MDP를 한 줄씩 비교하기

지금까지 하나씩 붙인 구성 요소를 표로 모으면 구조가 훨씬 잘 보인다.

외울 때는 긴 이름을 통째로 붙잡기보다 다음처럼 생각하는 편이 편하다.

$$\text{MP} \xrightarrow{+\mathcal{R},\,\gamma} \text{MRP} \xrightarrow{+\mathcal{A}} \text{MDP}$$

State 이동에 점수를 붙이면 MRP, 거기에 선택권까지 붙이면 MDP다.

Policy를 정하면 MDP가 다시 MRP가 된다

첫 번째 글에서 Policy $\pi(a \mid s)$는 State $s$에서 Action $a$를 고를 확률이라고 설명했다.

$$\pi(a \mid s) = P(A_t=a \mid S_t=s)$$

MDP에는 여러 Action이 열려 있지만 Policy를 하나 정하면 Agent가 어떤 비율로 Action을 고를지가 결정된다. 예를 들어 DESK에서 STUDY를 $0.6$, LEAVE를 $0.3$, WORK OUT을 $0.1$의 확률로 고르는 식이다.

그러면 Action을 하나씩 따로 적는 대신 Policy가 섞어 만든 하나의 Transition probability를 계산할 수 있다.

$$\mathcal{P}_{ss'}^{\pi} = \sum_{a \in \mathcal{A}} \pi(a \mid s) \mathcal{P}_{ss'}^a$$

수식의 오른쪽은 다음 순서로 읽으면 된다.

1. Policy가 Action $a$를 고를 확률 $\pi(a \mid s)$를 본다.
2. 그 Action을 했을 때 $s'$로 갈 확률 $\mathcal{P}_{ss'}^a$를 곱한다.
3. 가능한 모든 Action에 대해 더한다.

Reward도 같은 방식으로 Policy가 선택할 Action 비율을 반영해 평균낼 수 있다.

$$\mathcal{R}_s^{\pi} = \sum_{a \in \mathcal{A}} \pi(a \mid s) \mathcal{R}_s^a$$

MDP에서 Policy를 하나 고정하면 Agent의 선택 규칙이 정해지고, 그 Policy를 따라 나타나는 State와 Reward의 sequence는 하나의 MRP처럼 볼 수 있다.

이 관계가 중요한 이유는 Policy를 평가하는 문제를 MRP의 Value 계산으로 바꿀 수 있기 때문이다. “이 Policy를 계속 따르면 얼마나 좋은가?”라는 질문은, Policy가 만든 MRP에서 Expected return을 구하는 질문이 된다. 정확한 계산은 다음 글에서 이어서 살펴볼 예정이다.

MDP를 안다고 Transition matrix까지 아는 것은 아니다

MDP를 $\langle \mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma \rangle$로 쓴다고 해서 Agent가 처음부터 $\mathcal{P}$와 $\mathcal{R}$의 숫자를 모두 알고 있어야 하는 것은 아니다.

Board game처럼 규칙이 완전히 주어진 환경에서는 Transition과 Reward를 미리 알 수 있다. 이런 경우에는 Environment model을 알고 있다고 말한다. Dynamic Programming은 이런 Model을 알고 있다는 가정에서 출발한다.

반면 현실의 Robot이나 처음 실행한 Game에서는 어떤 Action이 어떤 결과를 만드는지 직접 경험하기 전까지 모를 수 있다. 그래도 환경 자체는 MDP로 표현할 수 있다. 단지 Agent가 그 MDP의 Transition과 Reward를 모르는 것이다.

이 차이를 다음처럼 구분하면 된다.

• MDP: 환경이 어떤 State, Action, Transition, Reward 구조를 가지는가?
• Model-based 여부: Agent가 Transition과 Reward의 규칙을 알고 있거나 학습하는가?
• RL Algorithm: 모르는 정보와 경험을 이용해 어떤 Policy를 찾는가?

문제의 구조가 존재하는 것과 풀이자가 그 구조의 숫자를 알고 있는 것은 별개의 이야기다.

Terminal state와 끝나지 않는 과정

강화학습 환경은 끝이 있는 Episodic task와 계속 이어지는 Continuing task로 나눌 수 있다.

Game 한 판, 미로 탈출, 주문 완료처럼 명확한 끝이 있는 문제에서는 Terminal state를 둔다. 위 예시에서는 SLEEP을 하루의 끝으로 정할 수 있다. Terminal state에 도착하면 Episode가 끝나고 새로운 시작 State에서 다음 Episode가 시작된다.

반면 온도 조절 System이나 계속 움직이는 Robot처럼 과정이 끝없이 이어질 수도 있다. 이런 경우에는 Reward의 합이 무한히 커지는 문제를 줄이기 위해 $\gamma<1$인 Discounted return을 자주 사용한다.

Terminal state를 자기 자신으로 확률 $1$만큼 이동하는 Absorbing state로 표현하기도 한다.

$$P(S_{t+1}=s_{\text{terminal}} \mid S_t=s_{\text{terminal}})=1$$

실제로는 Episode가 이미 끝났지만, 수학적으로 Transition probability의 Row가 계속 합계 $1$을 유지하도록 자기 자신으로 돌아오는 화살표를 그려두는 방식이다.

자주 헷갈리는 부분

MDP는 강화학습 Algorithm이 아니다

MDP는 문제를 표현하는 형식이다. Q-Learning, SARSA, Policy Gradient처럼 좋은 Policy를 찾는 방법과 구분해야 한다.

Action이 Next State를 확정하지는 않는다

Agent는 Action을 선택하지만 Environment의 결과는 확률적일 수 있다. 같은 $(s,a)$에서도 서로 다른 $s'$와 Reward가 나올 수 있다.

Reward와 Value는 다르다

Reward는 한 Step 뒤에 받는 숫자다. Value는 어떤 State에서 시작했을 때 미래의 Return을 평균적으로 얼마나 기대하는지 나타낸다. 이번 글의 State 옆에 적힌 $R=+2$가 그 State의 Value라는 뜻은 아니다.

Markov라는 말은 과거가 필요 없었다는 뜻이 아니다

State를 만들 때는 History가 사용될 수 있다. 다만 충분한 State가 만들어진 뒤에는 그 State를 조건으로 다음 Transition과 Reward를 표현할 수 있다는 뜻이다.

이번 글에서 기억할 것

이번 글의 내용을 한 문장으로 줄이면 다음과 같다.

MDP는 Agent가 어떤 State에서 어떤 Action을 선택할 수 있고, 그 결과 다음 State와 Reward가 어떤 확률로 나타나는지를 적은 강화학습의 문제지다.

조금 더 나누면 다음 여섯 가지다.

1. Markov Process는 $\langle \mathcal{S}, \mathcal{P} \rangle$로 State의 확률적 이동을 표현한다.
2. MRP는 Reward와 Discount factor를 추가한 $\langle \mathcal{S}, \mathcal{P}, \mathcal{R}, \gamma \rangle$다.
3. MDP는 Action을 추가한 $\langle \mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma \rangle$다.
4. Action을 골라도 Next State와 Reward는 확률적으로 달라질 수 있다.
5. Policy를 고정하면 MDP에서 나타나는 State와 Reward sequence를 MRP로 볼 수 있다.
6. MDP를 정의하는 것과 Agent가 Transition과 Reward의 숫자를 알고 있는 것은 다르다.

이제 강화학습 문제의 재료는 모두 모였다. 하지만 아직 DESK, CAFE, HOME 중 어느 State가 장기적으로 더 좋은지는 알 수 없다. 당장 받는 Reward만 비교해서는 먼 미래의 결과를 놓칠 수 있기 때문이다.

다음 글에서는 Reward, Return, Value를 다시 구분하고, State value $v(s)$와 Action value $q(s,a)$가 각각 어떤 질문에 답하는지 살펴보려고 한다. 여기서부터 강화학습이 미래를 예측하는 방식이 본격적으로 시작된다.

참고 자료

• David Silver, UCL Reinforcement Learning Course
• David Silver, Lecture 2: Markov Decision Processes
• Google DeepMind, RL Course by David Silver - Lecture 2
• 서울대학교 DSBA 연구실, Introduction of Reinforcement Learning
• Sutton & Barto, Reinforcement Learning: An Introduction, 2nd Edition