[ 바닥부터 배우는 강화 학습 ] 04. MDP를 알 때의 플래닝

앞서 벨만 방정식을 배운 덕분에 이제는 실제로 간단한 MDP를 풀 수 있다. 이번 챕터에서 벨만 방정식을 반복적으로 적용하는 방법론을 통해 간단한 MDP를 직접 풀어보자.

 

이번 챕터에서 다룰 내용은 다음 두 조건을 만족하는 상황이다.

 

1. 작은 문제 (상태 집합 S나 액션의 집합 A의 크기가 작은 경우)

2. MDP를 알 때 (보상 함수\(r_s^a\)와 전이 확률 행렬\(P_{ss'}^a\)을 알고 있을 때)

 

MDP에 대한 모든 정보를 알 때 이를 이용해 정책을 개선해 나가는 과정을 넓게 가리켜 플래닝이라고 한다.

--> 미래가 어떤 과정을 거쳐 정해지는지 알고 있으니 시뮬레이션을 해보며 좋은 계획을 세우는 것이다.

 

이렇게 가장 쉬운 설정에서 정책 \(\pi\)가 주어졌을 때 각 상태의 밸류를 평가하는 prediction 문제와 최적 정책 함수를 찾는 control 문제를 푸는 방법에 대해 살펴보자.

 

테이블 기반 방법론을 활용하여 문제를 풀어나간다. (테이블 기반 방법론? - 모든 상태 s 혹은 상태와 액션의 페어(s, a)에 대한 테이블을 만들어서 값을 기록해 놓고 그 값을 조금씩 업데이트하는 방식

 

4.1 밸류 평가하기 - 반복적 정책평가

이 문제는 4방향 정책함수 \(\pi\)가 주어졌고 이때 각 상태 s에 대한 가치함수 \(v(s)\)를 구하는 전형적인 prediction 문제이다.

이제 반복적 정책 평가라는 방법론을 통해 문제를 해결할 수 있다.

(반복적 정책 평가? - 테이블의 값들을 초기화한 후, 벨만 기대 방정식을 반복적으로 사용하여 테이블에 적어 놓은 값을 조금씩 업데이트, 이는 MDP에 대한 모든 정보를 알 때 사용할 수 있음)

 

보상 \(r_{s}^a\)=-1로 모든 액션에 대해 고정

전이확률 \(P_{ss^{'}}^a\)은 100%이다( 예를 들면, \(a_{west}\) 액션을 선택하면 서쪽 칸으로 무조건 100%의 전이 확률을 통해 움직이기 때문)

\(\gamma\)는 편의상 1 로 정한다

 

1. 테이블 초기화

테이블 빈칸은 상태별 밸류 \(v(s)\)를 기록해야 하기 때문에 상태 개수만큼 필요하다.

임의의 값 0으로 초기화한다. 추후 반복적 정책평가를 진행하면서 각 상태의 밸류들은 특정값으로 수렴해 갈 것이다.

 

2. 한 상태의 값을 업데이트

 파란색으로 칠해진 상태 \(s_5\)를 생각해보자.

이 상태의 다음 상태 후보들은 동서남북으로 인접해있는 노란색 상태들이다.

다음 상태가 어디가 될지 알고 있으니 다음 상태의 값들을 이용해 현재 상태의 값을 정확하게 바꿔줄 수 있다.

현재 상태와 다음 상태의 밸류 사이 관계식이 벨만 기대 방정식이다.

 

\(r_{s}^a\) 와 \(P_{ss^{'}}^a\)를 알기에 바로 2단계 수식을 적용한다.

이 수식은 현재 상태 s의 가치를 다음에 도달하게 되는 상태 s'의 가치로 표현한 식이다.

이 식을 토대로 위 그림의 파란색 셀\(s_5\)의 밸류를 노란색 셀의 밸류를 이용해 업데이트해보자.

 

\(\pi\)(a|s)는 모든 액션에 대해 각각 0.25이다. 또 보상은 어느 액션을 하든 -1, \(\gamma\)는 1.

계산해보면 이렇다.

 

\begin{equation} \begin{split} v_{\pi}(s_5) = & 0.25 * (-1 + 0.0) + 0.25 * (-1 + 0.0) + \\                & 0.25 * (-1 + 0.0) + 0.25 * (-1 + 0.0) = -1.0 \end{split} \end{equation}

 

따라서 \(s_5\)자리 값을 -1.0으로 업데이트한다.

 

 

++ 이게 왜 더 정확한 값일까?

 

다음 상태의 값만 가지고 업데이트한다면 의미 없는 값을 이용해 의미 없는 값을 수정하는 것이니 제자리 걸음이다.

 

하지만 우리는 다음 상태의 값과 더불어 보상이라는 실제 환경이 주는 정확한 시그널을 섞어서 업데이트한다. 무의미한 값에 조금씩 정확한 값이 섞인다는 의미이다. 흙탕물에 깨끗한 물을 조금씩 계속 부어주면 점점 깨끗한 물이 되듯이 무의미하더라고 점차 실제 값에 가까워지게 되는 것이다.

 

게다가 다음 상태의 값이 항상 엉터리인것은 아니다.  "종료 상태"의 경우 가치가 0으로 초기화되어 있다. 이는 가치 \(v(s)\)의 정의가 미래에 받게 될 누적 보상의 기댓값으로 맨 마지막 상태에서는 그 뒤 미래가 존재하지 않기에 정확한 값이다. 덕분에 마지막 상태에 인접한 상태들의 경우 다음 상태의 가치 \(v(s')\)이 더 정확한 값을 가리키며, 이게 반복되어 인접한 상태의 밸류도 더 정확한 업데이트가 가능해진다.

이러한 이유들로 벨만 기대 방정식을 사용해 업데이트하면 조금씩 더 정확한 값에 다가갈 수 있다.

 

3. 모든 상태에 대해 2의 과정을 적용

앞에서 상태 \(s_5\)를 업데이트하고, 같은 방법으로 마지막 상태를 제외한 15개의 상태를 업데이트한다. (가장자리에서 바깥을 향하는 액션을 취하면 같은 자리에 그대로 남게 된다.)

종료 상태를 제외한 모든 상태의 값이 -1로 업데이트되었음을 알 수 있다.

 

4. 앞의 과정을 반복

이 과정을 계속하다 보면 각 상태의 값이 어떤 값에 수렴하게 된다. 그리고 그 값이 바로 해당 상태의 실제 밸류이다. 

\(s_0\)의 가치는 -59.4이다. 이 말은 4방향으로 무작위로 움직이다 보면 평균적으로 대략 60번 움직여야 종료 상태에 도달하게 된다는 뜻이다. 또 종료 상태 바로 위에 있는 상태 \(s_11\)의 경우 30번이나 움직여야 종료 상태에 도달하게 된다.

 

지금까지 정책 \(\pi\)가 주어졌을 때 각 상태의 밸류를 계산하는 법을 배웠다.

MDP에 대한 정보를 알고 그 크기가 충분히 작다면 해당 정책 함수를 따랐을 때 각 상태의 밸류를 구할 수 있게 된다.

이제 정책을 수정해가며 더 좋은 정책 함수를 찾는 법에 대해 소개한다.

 

4.2 최고의 정책 찾기 - 정책 이터레이션

본 챕터에서는 MDP를 알 때 최적 정책을 찾는 2가지 방법을 배워본다.

정책 이터레이션은 기본적으로 정책 평가와 정책 개선을 번갈아 수행하여 정책이 수렴할 때까지 반복하는 방법론이다. 

 

앞의 반복적 정책 평가의 결과를 잠시 생각해보자

 

\(s_5\)의 가치가 -54.6이고 좋은 액션이란 밸류가 더 큰 상태로 이동하는 것이다.

\(s_5\)에서 서쪽이나 북쪽으로 가면 가치가 -57.4로 더 작아진다. 반면 동쪽이나 남쪽으로 가면 가치가 더 커진다. 즉 상태 \(s_5\)에서는 동이나 남을 선택하는 것이 최선이다.

\(\pi'(a_{\text{동}} | s_5)\) = 1.0  or  \(\pi'(a_{\text{남}} | s_5)\) = 1.0

 

이렇게 만들어진 \(\pi\)'는 원래 정책보다 나은 정책이다.

이러한 정책을 그리디 정책이라고 한다. (그리디 = 탐욕스럽다, 눈 앞의 이익을 최대화하는 선택을 취하는 방식을 뜻함)

오른쪽과 아래쪽으로 가는 것이 그리디 정책인 이유는 당장 다음 칸의 가치가 높은 칸을 선택하기 때문이다.

 

\(s_5\)에서의 최적 정책과 그리디 정책이 일치하는 결과를 얻을 수 있다.

 

요약하면 이상한 정책(랜덤 정책)의 가치를 평가했을 뿐인데 \(s_5\)에서의 더 나은 정책을 알게된 것이다.

모든 상태에 대해 그리디 정책을 표시한 결과는 다음과 같다.

 

이는 간단한 MDP이기에 발생한 일이고 중요한 점은 \(\pi\)'이 \(\pi\)에 비해 개선되었다는 점이다. 이것이 정책 이터레이션의 핵심이다.

 

 

평가와 개선의 반복

정책 이터레이션은 정책 평가와 정책 개선으로 이루어져 있다.

1단계 ) 정책 평가 단계: 임의의 정책으로 \(\pi\) 를 고정해놓고 반복적 정책 평가 방법을 사용하여 각 상태의 밸류를 계산한다.

2단계 ) 정책 개선 단계: 1단계에서 계산해 놓은 상태별 밸류값 \(v(s)\)을 이용하여 그리디 정책을 생성한다. 

 

이렇게 \(\pi\)'이 생성되면 \(\pi\)'에 대해 다시 정책 평가를 진행한다. 즉 정책의 평가와 개선을 반복하는 것이다. 그러다보면 어느 순간 정책도 변하지 않고, 그에 따른 가치도 변하지 않는 단계에 도달하게 된다. 이렇게 수렴하는 곳이 바로 최적 정책과 최적 가치가 된다.

 

 

과연 정책은 개선되는가?

왜 그리디 정책 \(\pi\)'이 기존 정책 \(\pi\)에 비해 더 나은 정책으로 이어질까? 만일 그리디 정책이 더 나은 정책으로 이어지지 않는다면 이 모든 과정의 의미는 없다.

== 정책 개선 단계에서 새로운 정책이 반드시 더 높은 가치를 가져야 한다.

 

직접적으로 정책을 수정하는 부분은 정책 개선 단계밖에 없는데 이 단계에서 개선이 이루어지지 못하기 때문이다.

 

그래서 밸류에 대한 그리디 정책이 기존 정책보다 좋다는 것이 반드시 보장되어야하고 이것은 보장된다.

 

\(s_5\)라는 하나의 상태의 관점에서 생각해본다. 이 상태에서 원래 정책인 랜덤 정책 \(\pi\)를 따라 한 칸 움직였을 때 도달하는 다음 칸은 2가지중 하나이다.

1) \(s_5\)보다 밸류가 낮은 칸인 \(s_1\)과 \(s_4\)

2) \(s_5\)보다 밸류가 높은 칸인 \(s_6\)과 \(s_9\)

 

만일 1의 경우에 도달했다고 한다면 그때부터 종료까지 \(\pi\)로 움직이면 평균적으로 -57.4의 보상을 얻게된다. 대신 2의 경우부터 종료까지 \(\pi\)로 움직이면 -49.7의 보상을 얻게된다.

 

반대로 \(s_5\)에서 그리디 정책을 이용해 딱 한칸만 움직이고 그 이후로는 원래 정책을 이용해 움직인다고 해보자. 

\(s_5\)에서 그리디 정책을 이용하기에 다음 상태는 무조건 2의 경우에 속하고 보상은 평균 -49.7이다. 

 

\(\pi_{greedy}\) : \(s_5\)에서만 그리디 정책으로 움직이고 나머지 상태는 모두 랜덤 정책

\(\pi\) : 원래 정책 (모든 상태에서 랜덤 정책)

 

\(s_5\)에서는 \(\pi_{greedy}\)가 좋은 정책이다. \(\pi_{greedy}\)를 따르면 평균 -49.7의 리턴을 얻는 반면 \(\pi\)를 따르면 -49.7의 리턴을 얻거나 -57.4의 리턴을 얻는다.

 

즉 \(s_5\)부터 한 스텝을 그리디하게 움직이고 \(\pi\)를 따르는게 처음부터 \(\pi\)를 따르는 것보다 좋다는 의미이다.

 

 

정책 평가 부분을 간소화하기

정책 이터레이션은 루프 안에 루프가 있기 때문에 많은 연산을 필요로한다.

 

• 정책 이터레이션은 정책 평가와 정책 개선을 반복해서 수행한다.
• 정책 개선보다 정책 평가에서 많은 연산을 수행한다.

 

그런데 과연 테이블의 밸류가 수렴할 때까지 평가 스텝을 밟아야 할까?

--> 정책 평가를 6단계만 진행하고 일찍 멈춰(early stopping)도 최적의 정책에 도달 가능하다.

 

최적의 정책을 찾는 것이 목적이지 정확한 가치 평가를 하는 것이 목적이 아님.

 

이 예시에서는 k=6까지 진행하여도 이미 최적 정책에 도달했기에 6번만 업데이트해도 된다.

 

정책 평가 단계에서 반복적 정책 평가를 k=1까지 진행한 것이다.

--> 빠르게 정책 평가와 정책 개선이 가능하고, 빠르게 최적 정책을 찾을 수 있다.

 

작은 MDP에서 MDP에 대한 모든 정보를 알 때에 최적의 정책을 구하는 첫번째 방법을 배웠다.

 

 

 

4.3 최고의 정책 찾기 - 밸류 이터레이션

정책 이터레이션은 단계마다 서로 다른 정책의 가치를 평가했다.

개선 단계를 지날때마다 새로운 정책이 나오고, 평가 단계에는 새로운 정책의 밸류를 평가했기 때문

 

밸류 이터레이션은 오로지 최적 정책이 만들어내는 최적 밸류 하나만 바라본다.

최적 정책 = 가장 보상을 많이 받을 수 있는 정책

최적 밸류 = 최적 정책을 따랐을 때 얻는 밸류

벨만 최적 방정식 = 현재 상태 s와 다음 상태 s'의 최적 가치가 갖는 관계식

 

밸류 이터레이션 또한 테이블 기반 방법론이다.

테이블의 값들은 최적 정책 \(\pi\)*의 밸류인 \(v_{*}\)(s)를 뜻한다. 업데이트를 진행함에 따라 점차 실제 최적 밸류의 값으로 수렴해 간다.

 

 

앞의 반복적 정책 평가에서는 \(\pi\)가 주어져 있으니 벨만 기대 방정식을 사용했고 현재는 최적 밸류 사이의 관계를 알고 싶으므로 벨만 최적 방정식을 이용한다.

 

MDP의 모든 정보(보상 함수와 상태 전이 함수)의 값을 모두 알고있기에 2단계 식을 바로 적용한다.

 

\begin{equation} \begin{split} v_{*}(s) &= \underset{a}{\mathrm{max}} \left [ r_s^a + \gamma \sum_{s' \in S} P_{ss'}^a v_{*}(s') \right ] \\ &= \mathrm{max}(-1 + 1.0 * 0, -1 + 1.0 * 0,  -1 + 1.0 * 0, -1 + 1.0 * 0,) \\ &= -1.0 \end{split} \end{equation}

 

4방향 중 가장 큰 값은 -1이 된다. 그래서 테이블 \(s_5\)에 해당하는 값을 -1로 업데이트한다. 같은 방식을 모든 칸에 적용한 결과이다.

 

종료 상태는 더 이상 받을 보상이 없기에 가치가 0으로 고정이다. 같은 방식을 반복한다.

 

테이블의 값들이 수렴하였고 이 값은 각 상태의 최적 밸류를 의미한다.

왼쪽 상단의 상태 \(s_0\)에서 출발하여 최적 정책을 따라가면 종료 상태까지 6걸음이 필요한 것을 알 수 있다.

한 칸 걸을 때마다 -1의 보상을 얻으니 \(s_0\)의 가치는 -6인 것이다.

 

우리는 모든 상태에 대하여 최적 가치를 계산한 것이다. 이는 벨만 최적 방정식을 여러번 적용해 얻은 결과이다.

 

우리의 목적은 최적 밸류가 아닌 최적 정책을 찿는 것이다.

왜 최적 밸류를 구했을까? MDP를 모두 아는 상황에서는 일단 최적 밸류를 알면 최적 정책을 바로 얻을 수 있기 때문이다.

 

최적 밸류를 모두 계산해놓으면 임의의 상태에서 다음 상태 이동은 밸류가 가장 큰 셀로 이동하는 것이 최적 정책이다.

즉, 최적 밸류에 대한 그리디 정책이다.

 

이 정책은 최적 밸류를 높이는 방향으로 움직이기에 먼 미래까지 함께 보는 그야말로 최적 정책인 것이다.

 

 

 

 

 

이번 챕터에서는 우리는 크기가 작고 MDP에 대한 모든 정보를 알 때, 주어진 정책 \(\pi\)의 상태별 밸류 \(v_\pi\)(s)를 구하는 방법과 최적 정책 \(\pi\)*를 찾는 2가지 방법에 대해 배웠다.

 

정책 이터레이션은 평가 단계에서 사용하는 \(\pi\)의 밸류를 찾는다. --> 정책을 개선하는 데 초점 --> 최적 정책을 찾음

밸류 이터레이션에서는 최적 정책의 밸류를 찾는다. --> 상태 가치 함수를 개선 --> 최적 가치 함수를 찾음