Chapter 2. 마르코프 결정 과정

밴디트 문제에서는 에이전트가 어떤 행동을 취하든 다음에 도전할 문제의 설정은 변하지 않는다. 하지만 현실은 그렇지 않다. 2장에서는 에이전트의 행동에 따라 상태가 변하는 문제를 다룬다. 이러한 문제의 대표적인 예로 마르코프 결정 과정(Markov Decision Process(MDP))가 있다.

마르코프 결정 과정(MDP)란?

마르코프 결정 과정에서 '결정 과정'이란 '에이전트가 환경과 상호작용하면서 행동을 결정하는 과정'을 의미한다.

구체적인 예

위와 같이 격자로 구분되어 있고 그 안에 로봇(에이전트)가 있는 '그리드 월드'를 생각해보자. 에이전트는 오른쪽으로 이동하거나 왼쪽으로 이동할 수 있다. 폭탄과 사과는 에이전트가 얻을 수 있는 보상이다. 

그림과 같이 에이전트의 행동에 따라 에이전트가 처하는 상황이 달라지며, 강화 학습에서는 상태(state)라고 한다. MDP에서는 에이전트의 행동에 따라 상태가 바뀌고, 상태가 바뀐 곳에서 새로운 행동을 하게 된다. MDP에서는 시간 개념이 필요하다. 특정 시간에 에이전트가 행동을 취하고, 그 결과 새로운 상태로 전이한다. 이때의 시간 단위를 타임 스텝이라고한다.

에이전트와 환경의 상호작용

MDP에서는 에이전트와 환경 사이에 상호작용이 이루어진다. 명심해야 할 것은 에이전트가 행동을 취함으로써 상태가 변한다는 점이다. 

위 그림에서는 시간 t에서의 상태가 \(S_t\)이다. 이 상태에서 에이전트가 행동 \(A_t\)를 수행하여 보상 \(R_t\)를 얻고, 다음 상태인 \(S_{t+1}\)로 전환된다. 이러한 에이전트와 환경의 상호작용은 실제로 다음과 같은 전이를 만들어 낸다.

$$S_0, A_0, R_0, A_1, R_1, S_2, A_2, R_2, \cdots $$

강화학습에서는 보상 시점을 t와  t+1 둘 다 잡을 수 있으나, 이 책에서는 t 시점에 보상을 받는 것으로 처리함

환경과 에이전트를 수식으로

MDP는 에이전트와 환경의 상호작용을 수식으로 표현한다. 그렇게 하려면 다음의 세 요소를 수식으로 표현해야 한다

• 상태 전이: 상태는 어떻게 전이되는가?
• 보상: 보상은 어떻게 주어지는가?
• 정책: 에이전트는 행동을 어떻게 결정하는가?

상태 전이

왼쪽 그림은 에이전트가 왼쪽으로 이동을 했고 그 결과로 '반드시' 왼쪽으로 이동 된 모습이다 이러한 성질을 결정적(deterministic) 이라고 한다. 따라서 다음 상태 s'는 현재 상태 s와 행동 a에 의해 '단 하나로' 결정 된다.

$$s' = f(s,a)$$

\(f(s,a)\)는 상태 s와 행동 a를 입력하면 다음 상태 s'을 출력하는 함수이며, 상태 전이 함수(state transition function)라고 한다.반면 오른쪽은 이동을 왼쪽으로 했어도 0.9의 확률로 왼쪽, 0.1의 확률로 그 자리에 머무를 수 있다. 이러한 성질을 확률적(stochastic)하다고 한다.이제 확률적 상태 전이를 표기하는 방법을 알아보자. 에이전트가 상태 s에서 행동 a를 선택한다고 할 때, 이 경우 상태 s'로 이동할 확률인 상태 전이 확률(state transition probability)은 다음처럼 나타낸다$$p(s'|s,a)$$

\(p(s'|s,a)\)가 다음 상태 s'를 결정하는 데는 '현재' 상태 s와 행동 a만이 영향을 준다. 다시 말해 상태 전이에서는 과거의 정보는 전혀 신경 쓰지 않는다. 이처럼 현재의 정보만 고려하는 성질을 마르코프 성질(markov property)라고 한다.

MDP는 마르코프 성질을 만족한다고 가정하고 상태 전이(와 보상)을 모델링한다. 마르코프 성질을 도입하는 가장 큰 이유는 문제를 더 쉽게 풀기 위함이다. 만약 마르코프 성질을 따르지 않는다고 가정한다면 과거의 모든 상태와 행동까지 고려해야 해서, 그 조합이 기하급수적으로 늘어난다.

보상 함수

보상 함수(reward function)은 다음과 같이 간단히 표시. 보상도 확률적으로 주어질 수 있다.

에이전트의 정책

정책(policy)는 에이전트가 행동을 결정하는 방식이다. 정책에서 중요한 점은 마르코프 성질에 의해서 '현재 상태'만으로 행동을 결정할 수 있다는 것이다.

MDP의 마르코프 성질이라는 특성은 에이전에 대한 제약이 아니라 '환경에 대한 제약'으로 볼 수 있다. 즉, 마르코프 성질을 만족하도록 '상태'를 관리하는 책임이 환경 쪽에 있다는 뜻이다. 에이전트 관점에서 보면 최선의 선택에 필요한 정보가 모두 현재 상태에 담겨 있기 때문에 현재만을 바라보고 행동할 수 있다.

에이전트는 현재 상태를 보고 행동을 결정한다. 이때 행동을 결정하는 방식인 정책은 '결정적' 또는 '확률적'인 경우로 나눌 수 있다.

왼쪽 그림처럼 L3 상태에서 반드시 Left 행동을 하는 결정적 정책은 다음과 같이 정의한다.

$$\alpha = \mu(s)$$

오른족 그림처럼 확률적으로 결정되는 정책은 다음과 같이 정의한다.

$$\pi(a|s)$$

 위 그림의 예시를 수식으로 표현하면,

$$\pi(a=\text{Left} | s = \text{L3}) = 0.4$$

$$\pi(a=\text{Right} | s = \text{L3}) = 0.6$$

MDP의 목표

MDP의 목표는 정해진 틀 안에서 수익이 최대가 되는 최적 정책(Optimal Policy)를 찾는 것이다. 이 최적 정책을 수식으로 정확히 표현하려면 MDP의 문제가 크게 두 가지로 나뉜다는 사실을 알아야한다. 바로 '일회성 과제'와 '지속적 과제'이다.

일회성 과제와 지속적 과제

MDP는 문제에 따라 일회성 과제와 지속적 과제로 나뉜다. 일회성 과제(episodic task)는 끝이 있는 문제이다. 예를 들어 바둑은 일회성 과제로 분류된다. 바둑은 결국 승리/패배/무승부 중 하나로 귀결된다. 일회성 과제에서는 시작부터 끝까지의 일련의 시도를 에피소드라고한다. 

반면 지속적 과제(continuous task)는 끝이 없는 문제이다. 예를 들어 재고 관리가 있다. 재고 관리에서는 에이전트는 얼마나 많은 상품을 구매할지를 결정한다. 판매량과 재고량을 보고 최적의 구매량을 결정한다. 이런 유형의 문제는 끝을 정하지 않고 영원히 지속될 수 있다.

수익(Return)

수익이란 시간 t에서부터 미래에 얻는 모든 보상을 합한 합이며 다음과 같이 정의된다.

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

시간이 지날수록 보상은 감마값에 의해 기하급수적으로 줄어든다. 이 감마를 할인율(discount rate)라고 한다. 할인율을 도입하는 주된 이유는 지속적 과제에서 수익이 무한대가 되지 않도록 방지하기 위함이다. 또한 할인율은 가까운 미래의 보상을 더 중요하게 보이도록 한다

상태 가치 함수

방금 정의한 '수익'을 극대화하는 것이 에이전트의 목표이다. 여기서 주의할 점은 에이전트와 환경이 '확률적'으로 동작한다는 점이다. 따라서 확률적 동작에 대응하기 위해서는 기대값, 즉 '수익의 기대값'을 지표로 삼아야 한다.

상태 \(S_t=s\)이고 에이전트의 정책을 \(\pi\)라 할 때, 에이전트가 얻을 수 있는 기대 수익은 다음처럼 표현한다.

$$v_\pi(s) = \mathbb{E}[G_t| S_t=s, \pi]$$

이처럼 수익의 기대값을 \(v_\pi(s)\)로 표기하며 \(v_\pi(s)\)를 상태 가치 함수(state-value function)이라고 한다. 

우변에서 에이전트의 정책 \(\pi\)는 조건으로 주어진다. 정책이 바뀌면 당연히 수익도 바뀌기 때문이다. 이런 특성을 명시하기 위해 상태 가치 함수는 \(v_\pi(s)\) 처럼  \(\pi\)를 밑으로 쓰는 방식을 많이 따른다. 또한 다음처럼 쓰기도 한다.

$$v_\pi(s) = \mathbb{E}_\pi[G_t| S_t=s]$$

소문자 \(v_\pi(s)\)는 실제 상태 가치 함수이고 대문자 \(V_\pi(s)\)는 추정치로서의 상태 가치 함수를 의미한다.

최적 정책과 최적 가치 함수

최적 정책이란 무엇이며 애초에 '최적'을 어떻게 표현할 수 있을까?

두 가지 정책 \(\pi\)와 \(\pi'\)이 있다고 가정하자.

왼쪽 그림과 같은 상황이라면 어떤 정책이 더 좋은지 우열을 가릴 수 없다. 반면, 오른쪽 그림과 같은 상황이라면 분명히 \(\pi'\)이 더 나은 정책이라고 할 수 있다.

이렇게 두 정책의 우열을 가리려면 하나의 정책이 다른 정책보다 '모든 상태'에서 더 좋거나 최소한 똑같아야 한다.

최적 정책을 \(\pi_*\)로 표현한다면 정책 \(\pi_*\)는 다른 정책과 비교하여 모든 상태에서 상태 가치 함수 \(v_{\pi_*}(s)\)의 값이 더 큰 정책이라는 뜻이다.

중요한 사실은 MDP에서는 최적 정책이 적어도 하나는 존재한다는 사실이다(수학적 증명 가능). 그리고 그 최적 정책은 '결정적 정책'이다. 결정적 정책에서는 각 상태에서의 행동이 유일하게 결정된다. \(\alpha = \mu_*(s)\)와 같이 상태 s를 입력하면 행동 \(\alpha\)를 출력하는 \( \mu_*(s) \)로 나타낼 수 있다. 

최적 정책의 상태 가치 함수를 최적 상태 가치 함수(optimal state-value function, \(v_*\))이라고 한다.

MDP 예제

다음과 같은 두 칸짜리 그리드 월드 문제를 생각해보자.

백업 다이어그램

백업 다이어그램이란 방향 있는 그래프를 활용하여 상태, 행동, 보상의 전이를 표현한 그래프이다.

왼쪽 그림의 경우, 에이전트의 정책이 결정적이고 상태 전이도 결정적이기 때문에 백업 다이어그램의 전이는 일직선으로 뻗어나간다.

하지만 오른쪽 그림처럼 에이전트가 확률적으로 행동한다면 두 가지로 행동할 가능성이 있기 때문에 백업 다이어그램이 넓게 퍼져나간다.

최적 정책 찾기

최적 정책은 결정적 정책으로 존재한다고 알려져있다. 따라서 모든 결정적 정책을 알아낸다면 그 중에서 최적 정책을 고를 수 있을 것이다. 

위 표에는 모든 결정적 정책이 적혀있다. 이제 각각의 정책의 상태 가치 함수를 계산하여 가장 높은 값을 가지는 정책을 고르면 된다. 예를 들어 \(\mu_1\)의 상태 가치 함수는 다음처럼 계산 된다.

무한등비급수 합 공식을 이용하여 상태 L1, L2에서의 상태 가치 함수를 계산할 수 있다. 이런 식으로 모든 정책에 대해서 값을 구한 뒤 그래프로 표현해보면 다음과 같다.

그래프에서 보듯 \(\mu_2\)가 모든 상태에서 다른 정책들보다 상태 가치 함수의 값이 더 크므로 최적 정책임을 알 수 있다.

정리

• MDP는 에이전트와 환경의 상호작용을 수식으로 표현한 것
• 환경에는 상태 전이 확률(함수)와 보상 함수가 있다.
• 에이전트에는 정책이 있다.
• 환경과 에이전트가 영향을 주고 받는 틀 안에서 최적 정책을 찾는 것이 MDP의 목표이다.
• 최적 정책이란 모든 상태에서 다른 어떤 정책보다 상태 가치 함수의 값이 더 크거나 같은 정책을 말한다.