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

가장 간단한 상황인 *MDP를 알 때 *작은 문제를 푸는 방법에 대해 생각해보자.

*MDP를 안다 : 보상 함수와 전이 확률 행렬을 안다.

*작은 문제 : MDP에서 상태 집합 S나 액션의 집합 A의 크기가 작은 경우

---

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

위의 그림과 같이 4방향 랜덤이라는 정책 함수 π가 주어졌고 이때 각 상태 s에 대한 가치함수 v(s)를 구하는 전형적인 prediction 문제를 풀어보자.

이 문제는 반복적 정책 평가(iterative policy evaluation)이라는 방법론을 통해 해결할 수 있다. 반복적 정책 평가란? 테이블의 값들을 초기화한 후, 벨만 기대 방정식을 반복적으로 사용하여 테이블에 적어 놓은 값을 조금씩 업데이트 해나가는 방법론

위 그림에서 우리는 보상 함수와 전이 확률을 알고 있다. 보상은 어느 액션을 하든 -1이다. 또한 환경에 확률적인 요소가 없기 때문에 가장자리의 칸들을 제외하면 선택하는 액션의 방향으로 100%의 전이확률을 통해 움직인다. 이 문제에서는 편의상 γ=1로 가정하였다.

4.1.1. 테이블 초기화

먼저 테이블을 초기화하자. 테이블에 상태별 밸류 v(s)를 기록하기 때문에 테이블의 빈칸은 MDP 안의 상태 s의 개수만큼 필요하다. 주어진 문제에서는 MDP 상태가 16개이기 때문에 16개의 빈칸으로 이루어진 테이블을 만든다. 그리고 이 값들을 임의의 값 0으로 초기화한다.

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

16개의 값들 중 1개의 값 s5에 대해 업데이트를 해보자. 현재 상태와 다음 상태의 밸류 사이의 관계식인 벨만 기대 방정식을 통해 값을 바꿀 수 있다. 보상 함수와 전이확률을 알고 있으므로 2단계 수식을 이용하자.

정책함수는 4방향으로 균등하게 랜덤하므로 π(a|s)는 모든 액션에 대해 0.25이다. 따라서 원래 식에 값을 대입해 계산하면 아래와 같다.

현재 테이블에 담겨있는 값이 무의미한 값인데 왜 이게 더 정확한 값이지?
다음 상태의 값과 더불어 보상이라는 실제 환경이 주는 값을 섞어서 업데이트 하기 때문에 조금씩 정확한 값이 섞인다. 따라서 점차 실제 값에 가까워지게 된다.

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

가치 v(s)의 정의는 미래에 받게 될 누적 보상의 기댓값으로 맨 마지막 상태의 입장에서는 그 뒤의 미래라는 것이 존재하지 않기 때문에 0이 정확한 값이다.

모든 상태에 대해 2의 과정을 적용하면 위와 같은 값들로 업데이트된다.

4.1.4. 앞의 2~3 과정을 계속해서 반복

위와 같이 한 번 테이블의 모든 값을 업데이트하는 과정을 여러 번 반복하고, 몇 번 반복했는지를 k로 표기한다.

위와 같이 반복하다보면 각 상태의 값이 어떤 값에 수렴하게 된다. 그리고 그 값이 해당 상태의 실제 밸류이다.

이제 각 상태의 실제 가치를 알게 되었다. 예를 들어, $s_0$의 가치는 -59.4이다. 이 값은 4방향으로 무작위로 움직이다 보면 평균적으로 대략 60번은 움직여야 종료 상태에 도달하게 된다는 것이다. $s_{11}$은 30번은 움직여야 종료 상태에 도달하게 된다.

---

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

MDP를 알 때 최적 정책을 찾는 2가지 방법이 있다. 정책 이터레이션과 밸류 이터레이션 중 정책 이터레이션에 대해서 먼저 알아보자. 정책 이터레이션은 정책 평가와 정책 개선을 번갈아 수행하여 정책이 수렴할 때까지 반복하는 방법론이다. 그 전에 위에서 배운 반복적 정책 평가의 결과를 생각해보자.

벨만 기대 방정식을 통해 위와 같이 각 상태의 밸류를 구했다. 지금 $s_5$의 상태에 있을 때 밸류가 더 큰 상태인 $s_6$나 $s_9$로 이동하는 것이 좋은 액션일 것이다. 따라서 아래와 같은 정책 π’를 생각해볼 수 있다.

$π'(a_동|s_5)=1.0$ or $π'(a_남|s_5)=1.0 $

정책 π’은 원래의 정책 π보다는 나은 정책이며, 이러한 정책을 그리디 정책(greedy policy)이라고 한다. $s_5$의 상태에서 그리디 정책은 위와 같은 그림으로 나타낼 수 있다. 그러면 이 그리디 정책은 최적 정책과 일치함을 알 수 있다.

모든 상태에서 그리디 정책을 나타내면 위와 같다. 이 상태에서는 모든 상태에서 그리디 액션을 택했더니 더 나은 정책 π’를 얻었고 이와 최적 정책이 일치했다. 이 예시에서는 π’와 최적정책이 일치하는데 이런 경우는 많지 않다. 보통은 이전 정책에 비해 소폭 향상되는 정도이다. 여기서 중요한 점은 π’이 π에 비해 개선되었다는 것이다.

이것이 바로 정책 이터레이션(policy iteration)의 핵심이다.

4.2.1. 평가와 개선의 반복

정책 이터레이션은 위와 같이 총 2단계로 이루어져있다. 첫 번째 단계는 정책 평가(policy evaluation), 두 번째 단계는 정책 개선(policy improvement)이다.

1. 정책 평가 : 반복적 정책 평가 - 정책 π를 임의의 정책으로 초기화 → 고정된 π에 대해 각 상태의 밸류 계산

이렇게 하여 테이블에 각 상태의 밸류를 채워넣고 나면 정책 개선 단계로 넘어간다.

1. 정책 개선 : 그리디 정책 생성 - 새로운 정책 π’를 생성(정책 평가 단계에서 구한 $v(s)$를 이용해 $v(s)$에 대한 그리디 정책 생성) → π’>π가 성립하기 때문에 정책의 개선이 발생

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

4.2.2. 과연 정책은 개선되는가?

$s_5$라는 하나의 관점에서 생각해보자. 이 상태에서 원래 정책인 랜덤 정책 π를 따라 한 칸 움직였을 때 도달하는 다음 칸은 다음 두 가지 경우 중 하나이다.

1. $s_5$보다 밸류가 낮은 칸인 $s_1$과 $s_4$
2. $s_5$보다 밸류가 높은 칸인 $s_6$과 $s_9$

만일 1의 경우에 도달했다고 한다면 그때부터 종료까지 π로 움직이면 평균적으로 -57.4의 보상을 얻게 될 것이고, 2의 경우에 도달하여 그때부터 종료까지 π로 움직이면 평균적으로 -49.7의 보상을 받게 될 것이다.

만약 $s_5$에서 그리디 정책을 이용하여 한 칸만 움직이고 그 후로는 원래 정책을 이용한다고 하면 2의 경우와 같다. 따라서 우리는 아래의 2가지 경우를 비교해볼 수 있다.

• πgreedy : 딱 한 칸만 그리디 정책으로 움직이고 나머지 모든 칸은 원래 정책으로 움직이는 정책
• π : 원래 정책

위의 두 가지 정책 중 πgreedy가 π보다 좋은 정책이다. πgreedy를 따르면 무조건 평균 -49.7의 리턴을 얻는 반면 π를 따르면 -49.7의 리턴을 얻거나 -57.4의 리턴을 얻는다. 따라서 πgreedy의 평균 리턴이 π보다 크다. 이 논리를 귀납적으로 적용하면 결국 모든 상태에서 그리디한 정책 π’이 원래 정책 π보다 좋으므로 정책이 개선되었다는 것을 보장할 수 있다.

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

정책 이터레이션은 루프 안에 루프가 있기 때문에 많은 연산을 해야한다. 바깥쪽 루프는 평가와 개선의 반복 루프이고, 안쪽의 루프는 정책 평가 단계에서의 루프이다. 이 모든 과정을 풀어서 도식화하면 아래와 같다.

이렇게 세로로 이어지는 루프 안에 가로로 이어지는 루프가 포함되어 있다. 정책 평가 단계는 루프에서 연산을 가장 많이 필요로 하는데 평가를 끝까지 해야할까? 즉, 테이블의 밸류가 수렴할 때까지 평가 스텝을 밟아야하는지 생각해보자.

위와 같이 k=∞이 될 때까지 반복하면 각 테이블의 값이 실제 밸류에 수렴한다. 하지만 실제로 그렇게 반복하기는 어렵기 때문에 k=6까지만 실행을 해보면 위와 같이 나오게 되고, 이미 최적 정책에 도달했다는 것을 알 수 있다.

지금 최고의 정책을 찾는 것이 목적이지 정확한 가치를 평가하는 것이 목적인 상황이 아니다.

정책 이터레이션에서는 가치 함수가 오로지 그리디 정책을 찾는 데에만 쓰이고 테이블에 적혀있는 구체적인 값이 사용되지는 않는다. 따라서 극단적으로 k=1까지만 진행하고 도식화하면 아래와 같다.

간결해진 이터레이션을 통해 더욱 빠르게 평가와 개선을 진행할 수 있고, 그만큼 빠르게 최적 정책을 찾을 수 있다.

---

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

정책 이터레이션은 단계마다 서로 다른 정책의 가치를 평가했다. (개선 단계를 지날 때마다 새로운 정책이 튀어나오고, 평가 단계에선 방금 만들어진 새로운 정책의 밸류를 평가함) 하지만 밸류 이터레이션은 오로지 최적 정책이 만들어내는 최적 밸류 하나만 바라보고 달려간다. 이번에는 벨만 최적 방정식을 통해 최적 정책을 찾아보자.

4.3.1. 테이블 초기화

밸류 이터레이션 또한 테이블 기반 방법론을 사용한다. 따라서 위와 같이 테이블 초기화를 먼저 해준다. 정책 이터레이션에서는 테이블의 값들이 해당 평가 단계에서 사용하는 정책 π의 밸류였다. 이번에는 최적 정책 π의 밸류인 $v^(s)$를 뜻한다.

임의로 초기화된 값들이지만 업데이트를 진행함에 따라 점차 실제 최적 밸류의 값으로 수렴해 나간다. 처음에는 최적 밸류를 알 수 없으니 0으로 초기화하였다.

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

16개의 값들 중 1개의 값 $s_5$에 대해 업데이트를 해보자. 현재 상태와 다음 상태의 밸류 사이의 관계식인 벨만 기대 방정식을 통해 값을 바꿀 수 있다. 보상 함수와 전이확률을 알고 있으므로 2단계 수식을 이용하자.

$$ v_(s_5)=\max(-1+10,-1+10,-1+10,-1+1*0)=-1.0 $$

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

4방향의 다음 상태에 대해 $v^*(s')$의 값이 모두 같으므로 모든 상태에 대해 2의 과정을 적용하면 위와 같다. 오른쪽 하단의 종료 상태는 더 이상 받을 보상이 없기 때문에 가치가 0으로 고정이다.

4.3.4. 앞의 2~3 과정을 계속해서 반복

위와 같이 한 번 테이블의 모든 값을 업데이트하는 과정을 여러 번 반복하고, 몇 번 반복했는지를 k로 표기한다.

결국 테이블의 값들이 수렴하였고, 이 값은 각 상태의 최적 밸류를 의미한다. 예를 들어 $s_0$에서 출발하여 최적 정책을 따라가면 종료 상태까지 6걸음이 필요하다. 한 칸 걸을 때마다 -1의 보상을 얻게 되니 $s_0$의 가치는 -6인 것이고 테이블의 값도 -6에 수렴한다.

하지만 목적은 최적 밸류가 아닌 최적 정책을 찾는 것이었다.

왜 최적 밸류를 구했을까? MDP를 아는 상황에서는 최적 밸류를 알면 최적 정책을 곧바로 얻을 수 있기 때문이다. 에이전트 입장에서는 현재 상태에서 갈 수 있는 다음 상태가 무엇인지 모두 알고 있으며 이들 중에 최적 밸류가 가장 높은 칸으로 움직이면 된다. 그게 최적 정책이기 때문에 최적 밸류를 높히는 방향으로 움직이면 된다.

---

길찾기를 예로 보고 두 이터레이션을 비교하면?

밸류 이터레이션 : 갈 수 있는 블록의 개수가 정해져있다. (시간은 상관없는데 20번만 움직여서 목적지로 와라!)

정책 이터레이션 : 시간이 정해져있다. (많이 움직여도 되니까 2시까지 와라!)

---

• 정책 이터레이션 : 정책 ↔ 가치 함수 사이를 오가면서 점점 더 나은 정책을 직접 개선
• 밸류 이터레이션 : 정책을 두지 않고, 가치 함수만 최적화해서 마지막에 정책을 추출