Part2 - 7. MC Control : MC기법을 활용한 최적 정책 찾기

지난 포스트까지 업로드했던 내용은 MC, TD 기법을 이용하여 가치를 추산(predict)하는 것에 대한 내용이었다.

한마디로 $V^{\pi}$를 계산하는 내용이었던 것이다. ($\pi$ 를 계산하는 내용 포함 X)

 

일반화 정책 반복에 대해 다시한번 보도록 하자.

그림1. 일반화 정책반복

정책 평가 : $\pi$에 대한 $V^{\pi}(s)$를 계산하는 것 (DP, MC-PE, TD-PE 활용)

정책 개선 : $\pi_{i+1} \geq \pi_i$를 만족시키는 $\pi_{i+1}$생성

 

지금까지 우리가 $\pi_{i+1}$을 계산하기 위해 사용하였던 방식은 탐욕적 정책 개선이다.

 

그러나 탐욕적 정책 개선에는 한계점이 명확하게 존재한다.

 

그림2. 탐욕적 정책개선

탐욕적 정책 개선은 s의 시점에서 Q값이 가장 큰 행동에 대해서만 확률 1을 주고, 나머지 행동에 대한 확률은 0으로 준다.

 

따라서, 특정 상태 s에 있을 때 무조건 Q에 의해 정해진 행동 a만을 수행한다는 말이다.

 

만약 다른 행동 b를 취했을 때 추후에 생길 수 있는 잠재적인 보상이 a를 통하여 얻는 보상보다 크다면

이것은 더 좋은 보상을 받을 기회를 묵살시켜 버리는 것이다.

 

탐욕적 정책 개선은 Exploitation(이용) ↑, Exploration(탐험) ↓ 인 정책 개선 방식이다.

Exploitation은 이미 알고 있는 가치함수를 활용하여 greedy하게 행동하는 경우를 의미하고,

Exploration은 새로운 가치함수를 더 잘 찾기 위해 가끔씩은 기존에 하지 않았던 행동을 하는 것으로 보면 된다.

 

보다 더 자세한 개념에 대해서는 링크를 확인하길 바란다.

RL (강화학습) 기초 - 2. Reinforcement Learning 소개

Exploitation과 Exploration이 적절하게 혼용이 되면 최적의 길을 찾을 수 있게 된다.

 

Exploitation-Exploration의 딜레마를 해결하기 위해 등장한 정책 개선 방법이 $\epsilon$ Greedy Policy이다.

 

1) $\epsilon$ - Greedy Policy

그림3. $\epsilon$ - Greedy Policy의 공식

엡실론($\epsilon$) 그리디 정책은 (1 - $\epsilon$)의 확률로 가장 좋은 행동을 선택한다.

그리고 $\epsilon$의 확률로 모든 가능한 행동 중 하나를 임의로 선택한다.

 

이는 exploration의 조정을 위한 것이다.

 

이 개념을 하나의 그림으로 설명하면 다음과 같다.

그림4. $\epsilon$ - Greedy Policy의 개념

그림4.와 같이 어떤 상태 $S_t$에서 Q값이 가장 높은 행동이 $a^3$이라고 가정했을 때,

결론적으로 각 행동이 가지는 정책함수 값은 ($a^1$ = $\epsilon/3$, $a^2$ = $\epsilon/3$, $a^3$ = (1 - $\epsilon$) + $\epsilon/3$)이 되어

상태 s에서 기존에 하지 않았던 행동을 할 수 있는 가능성 즉, Exploration이 증가하게 된다.

 

그렇다면 $\epsilon$ - Greedy 정책개선이 정말로 "정책개선" 일까?

(정책개선 : $\pi' \geq \pi$를 만족하는 $\pi'$을 생성하는 것)

 

$\epsilon$ - Greedy정책개선이 과연 정책개선이 맞는지 증명해보자.

 

그림5. $\epsilon$ - Greedy 정책의 정리

$Q^{\pi}(s, \pi'(s))$를 전개하면 다음과 같은 수식이 나오게 된다.

이 수식은 그림5.의 빨간색 박스와 같이 대소 관계 비교가 가능한데

 

그림6. $\epsilon$ - Greedy 정책의 정리

여기서 파란색 글자의 부분이 만족해야지만 정리가 만족하게 된다.

 

이는 다른 개념으로 설명이 가능하다.

만약 (1) $w_i \geq 0$이고, (2) $\sum_{w_{i}} = 1$인 임의의 가중치 ($w_i$)를 가진다 할 때

그림7. 가중치에 대한 증명

그림7.의 수식이 만족하게 된다.

 

그림8. $\epsilon$ - Greedy 정책의 정리

따라서 그림8.의 파란색 글자 부분을 임의의 가중치 $w(a)$이라 했을 때, (1)과 (2)의 성질을 모두 만족하므로 그림6.의 부등호는 만족함을 알 수 있다.

 

그러나 $\epsilon$ - 탐욕적 정책에도 단점이 존재한다.

 

$\epsilon$의 확률로 임의의 행동을 해야 한다는 것이다.

 

이게 왜 문제가 되느냐?? 하는 의문이 생길 수 있을 것 같다.

꾸준히 $\epsilon$의 확률로 임의의 행동을 해야 한다면 최적 정책으로의 수렴이 가능할까?

수렴한다 해도 매 학습 때마다 최적 정책의 값이 바뀔 수도 있을 것이라는 생각이 든다.

 

따라서 학습 초기에는 $\epsilon$을 상대적으로 높게, 학습이 진행될수록 $\epsilon$을 0에 가깝게 하는 GLIE조건을 생각해볼 수 있겠다.

 

2) GLIE조건

GLIE조건을 따르면 학습이 진행될수록 Greedy정책으로 수렴하게 된다.

 

GLIE조건이란 모든 $N(s,a) \rightarrow \infty$이 되도록 $\epsilon$을 학습 진행에 따라 스케쥴링하는 것이다.

 

그림9. GLIE $\epsilon$ - Greedy 정책개선

그림9.의 예에서는 $\epsilon$을 $\frac{1}{k}$로 두었다.

(k는 에피소드의 인덱스)

이를 이용하면 에피소드가 진행될수록 Greedy정책으로 수렴하게 될 것이다.

 

이상으로 $\epsilon$ - Greedy정책과 GLIE조건을 만족하는 $\epsilon$ - Greedy 정책을 사용하여

정책개선을 더 Expolration하게 만드는 방법을 알아보았다.

---

내 생각 :

$\epsilon$ - Greedy 정책의 정리에 대한 증명과정이 복잡하게 느껴질 수 있을 것 같다.

하지만 $\epsilon$ - Greedy정책은 Exploration의 조정에 큰 도움이 되는 것을 알게 되었으며,

GLIE조건을 추가하여 최적의 적절한 정책개선을 꾀할 수 있었던 것 같다.

참고자료 :

대소니님의 블로그 : daeson.tistory.com/312

stanford 강화학습강의 정리 : mynsng.github.io/reinforcement%20learning/2019/08/22/cs234-04/

강화학습 A-Z 강의자료