해당 글은 강화 학습의 개념 전반에 대해 순차적으로 다룰 예정입니다.

이번 포스팅에서는 Monte Carlo Algorithm 기반의 prediction한 정보를 통해 Policy Iteration을 하기 위한 Monte Carlo Control에 대해 설명하겠습니다.

Monte Carlo Control

Greedy Policy Improvement

Greedy Policy Improvement는 특정 상태에서 가장 높은 보상을 받을 수 있는 상태로의 액션만 남도록 정책을 수정하는 과정이다.

MDP에서의 Greedy policy Improvement 모델을 식으로 표현하면 아래와 같다.

$\pi'(s)=\argmax_{a \in A}(R_s^a+P_{ss'}^aV(s'))$

이 식은 greedy하게 업데이트된 정책을 상태 가치 함수 $V(s)$를 사용해 나타낸 식이다. 하지만 MDP 모델을 배운 우리는 상태 가치 함수를 액션 가치 함수로 나타낼 수 있다는 사실을 알 수 있다. 해당 내용을 다시 상기시켜보자. 액션 가치 함수 $Q(s)$를 $V(s)$를 사용해 나타내면 아래와 같이 나타낼 수 있다.

$Q(s, a)=R_s^a + P_{ss'}^aV(s')$

따라서 우리는 앞의 두 식을 토대로 $\pi'(s)$를 $Q(s)$로 표현할 수 있다.

$\pi'(s)=\argmax_{a \in A}Q(s, a)$

결국, 우리는 액션 가치 함수 $Q(s, a)$만 알고 있으면 greedy policy improvement를 할 수 있는 것이다. 상태 가치 함수 $V(s)$를 사용하면 상태 천이 함수 $P_{ss'}^a$를 알아야 하지만, 액션 가치 함수의 경우 단순히 해당 상태에서의 $Q(s, a)$값을 비교해서 그 값이 가장 큰 $Q(s, a)$의 액션 $a$를 선택하도록 정책을 업데이트하면 되기 때문이다. 또한 Policy Iteration 과정을 통해 우리가 원하는 것은 최적 정책 $\pi^*$를 획득하는 것인만큼 정책을 업데이트하는 과정에 액션에 대한 정보를 알고 있는 것이 더 효율적이기 때문에 Iteration의 과정에는 상태 가치 함수 $V(s)$ 대신 액션 가치 함수 $Q(s, a)$를 사용하는 것이다. 그렇다면 $Q(s, a)$는 어떻게 계산할 수 있을까? MC를 예를 들어 확인해보자.

• Increment counter : $N(s, a) \leftarrow N(s, a) + 1$
• Increment total return : $S(s, a) \leftarrow S(s, a) + G_t$
• Action Value : $Q(s, a) = {{S(s, a)} \over {N(s, a)}}$
• $if\ N(s) \rightarrow \infin ,\ Q(s) \rightarrow q_\pi(s)$

따라서, 액션 가치 함수 $Q(s, a)$를 계산하려면 MC의 기존의 계산 과정에서 $V(s) \rightarrow Q(s, a)$, $N(s) \rightarrow N(s, a)$, $S(s) \rightarrow S(s, a)$로 변환해서 $Q(s, a)$를 계산하면 되는 것이다.

Issue of Generalized Policy Iteration

일반적인 Policy Iteration, 즉 Greedy Policy Improvement 방식에는 문제가 하나 존재한다. Greedy한 방식으로 정책을 업데이트하고 나면, 이렇게 업데이트된 정책을 사용해서 다시 에피소드 샘플을 만들어서 완료된 에피소드를 사용해 학습을 진행해야 한다. 하지만 만약 처음 업데이트한 정책이 잘못된다면 그 이후로 진행되는 iteration의 결과물도 전부 잘못된 결과를 업데이트하게 된다.

예를 들어 상태 $S_0$에서 선택할 수 있는 액션이 $a_1, a_2, a_3, a_4$인데(각 액션을 선택했을 때의 보상과 각 액션을 선택할 확률은 동일하다고 하자), policy improvement를 할 때 각각의 액션을 통해 도달하는 상태의 리턴이 전부 0이라고 하자. 그렇다면 4가지 액션 모두 획득 가능한 보상이 동일하기 때문에 원래라면 해당 상태에서의 정책은 random access의 형태가 되야 한다. 하지만 일반적인 greedy policy improvement 모델은 각 액션의 가치를 순차적으로 비교해 가치가 최대가 되는 액션을 선택하는 구조로 동작을 수행하기 때문에 모든 액션의 가치가 동일하다면 맨 처음에 max 변수에 할당된 액션을 greedy한 액션으로 인식할 수 있다.(이 경우엔 greedy하다고 인식된 액션이 $a_1$이 되었다고 하자.) 이 경우, 모든 액션의 가치는 동일하지만 policy improvement 결과 $S_0$의 정책은 무조건 $a_1$을 선택하도록 업데이트가 될 것이기 때문에 이후의 모든 학습은 잘못된 정책을 기반으로 동작하게 되는 것이다.

이러한 문제를 해결하기 위해 greedy한 정보를 사용하되 기존의 정책 정보도 일부 반영하여 정책이 완전히 잘못된 방향으로 업데이트되는 것을 방지하도록 구상된 것이 바로 $\epsilon$-greedy policy improvement이다.

ϵ-greedy Policy Improvement

지금까지 설명했던 일반적인 greedy policy improvement 방식은 현재 상태에서 가진 정보를 기반으로 최적의 결과를 도출해내기 위한 방식으로, 이를 exploitation이라고 한다. 하지만 앞에서도 설명했듯 exploitation 방식만 가지고는 최적 정책에 도달하는데 어려움이 있다. 따라서 이 문제를 보완하기 위해 새로운 정보를 탐색해 결과 도출에 반영하는 exploration 방식을 policy improvement 과정에 추가한 것이 바로 $\epsilon$-greedy policy improvement이다.

$\epsilon$-greedy 방식은 간단히 말하면 $\epsilon$ 만큼 exploration을 정책에 반영하자는 것이다. $\epsilon$-greedy policy improvement의 함수를 나타내면 아래와 같다.

$\pi(a|s)= \Bigg\{{{{\epsilon \over m} + 1 - \epsilon}\ \ \ \ if\ \ a^* = \argmax_{a \in A}Q(s, a) \atop {\epsilon \over m}\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ otherwise\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }$

이 함수는 만약 액션 $a^*$가 greedy한 액션이라면 우선 $1-\epsilon$ 만큼을 해당 액션의 정책으로 할당해주고, 남은 $\epsilon$ 만큼의 확률은 선택 가능한 모든 액션에 동일하게 배분한다. 따라서 $\epsilon$ 만큼의 확률을 선택 가능한 액션의 수 $m$으로 나눠 각각의 액션에 할당해준 것이다. 이처럼 greedy policy improvement의 결과를 정책에 반영하되, 기존 정책을 $\epsilon$만큼 남겨둬 exploration을 수행할 수 있도록 구성한 것이 바로 $\epsilon$-greedy policy improvement이다.

GLIE

강화 학습을 갓 시작하는 시점에는 단순한 exploitation이 학습에 나쁜 영향을 미치는 것을 방지하기 위해 exploration이 필요하지만, iteration이 반복되고 학습이 점점 진행될수록 사용되는 sample의 수가 늘어나면서 exploration의 필요성이 떨어지게 된다. 그렇게 되면 일반적인 greedy 모델을 통해 정책을 업데이트해도 된다. 따라서 $\epsilon$을 상수로 설정하는 것보단 policy improvement가 진행될수록 감소되는 변수로 설정하면 더욱 효율적으로 학습을 진행할 수 있다. 이러한 개념을 GLIE(Greedy in the limit with Infinite Exploration)이라고 한다. GLIE를 사용할 때의 $\epsilon$은 일반적으로 $\epsilon_k = {1 \over k}$로 선언하여 policy improvement 횟수 $k$가 늘어날수록 $\epsilon_k$가 작아지도록 모델을 구성하게 된다.