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

이번 포스팅에서는 지난 글에 이어 TD Control 방식 중 하나인 Q-Learning에 대해 다루겠습니다.

Q-Learning

On-Policy & Off-Policy Learning

앞선 포스팅에서 SARSA를 설명할 때, SARSA와 Q-Learning의 차이는 학습 방식이 On-Policy인지 Off-Policy인지의 차이라고 설명했었습니다. 그래서 기본적인 TD를 $Q$에 관한 식으로 변환한 Policy Iteration 알고리즘을 SARSA라고 했구요. 그렇다면 대체 On-Policy와 Off-Policy는 대체 무엇이길래 On-Policy 방식의 SARSA는 버림받고, Off-Policy 방식의 Q-Learning이 각광 받는 걸까요?

단순히 단어 자체의 의미만 가지고 생각해본다면 On-Policy Learning은 학습 과정에서 policy를 사용하는 학습 방식이고, Off-Policy Learning은 그렇지 않은 방식이라고 생각할 수 있습니다. 저도 처음에는 그랬구요. 정말 착각하기 쉬운 네이밍이지만, 실제로 이 두 용어는 전혀 다른 의미를 가지고 있습니다. 설명의 편의를 위해 이전 포스팅에서 사용했던, TD를 $Q(s, a)$에 대해 변환했던 식을 가져와 보겠습니다.

$Q(S_t,A_t) \leftarrow Q(S_t, A_t) + \alpha (R_{t+1} + \gamma Q(S_{t+1}, A_{t+1})- Q(S_t, A_t))$

지금까지의 내용들을 잘 이해했다면, 위 식에서 $R_{t+1}+\gamma Q(S_{t+1}, A_{t+1})$는 TD target이고, 여기서 $Q(S_t, A_t)$를 빼준 값이 TD error라는 사실은 간단히 이해할 것입니다. 이 식을 통해 우리가 목표로 하는 TD target과 현재의 $Q$값의 차이만큼 $Q$를 업데이트해주는 것이 지금까지 우리가 공부했던 TD의 prediction 방식인 것이지요. 그렇다면 여기서 편의를 위해 TD target의 $Q(S_{t+1}, A_{t+1})$를 target(목표), TD error을 계산하기 위한 뺄셈 연산에 사용한 $Q(S_t, A_t)$를 behavior(행동)이라고 지칭하겠습니다. 지금까지 우리는 $Q$를 업데이트하기 위해 target과 behavior을 구하는 과정에서 항상 같은 정책을 사용했습니다. 이것을 On-Policy Learning이라고 합니다. 하지만 잘 생각해봅시다. 굳이 target과 behavior이 같은 정책을 사용해야 할 필요가 있을까요?

지금까지 설명했던 MC와 TD는 local optima 같은 문제를 해결하기 위해 $\epsilon$-greedy 방식으로 정책을 업데이트했습니다. 이 때 주의해야 할 것은 local optima가 문제가 되어 exploration이 요구되는 것은 다음 학습에서 할 행동(behavior)을 선택하는 시점이라는 사실입니다. 오히려 우리의 목표(target)은 $\epsilon$-greedy보다 greedy한 방식으로 업데이트하는 것이 더 정확할지도 모릅니다. 그렇다면 우리는 대체 무엇을 위해 target과 behavior을 선택할 때 같은 정책을 고집하는 걸까요? 이러한 질문에서 시작된 개념이 바로 Off-Policy Learning입니다. Target과 behavior을 선택하는 과정에서 서로 다른 정책을 사용함으로써 학습 효율을 높일 수 있다는 것이 Off-Policy Learning의 존재를 뒷받침하는 논리인거죠. (이 경우 policy improvement에 사용하는 정책을 target policy, 동작할 액션을 선택할 때 사용하는 정책을 behavior policy라고 합니다.) 그렇다면 실제로 Off-Policy Learning이 On-Policy 방식보다 효율적인가에 대해 생각해봅시다.

우선 On-Policy 방식인 기존의 TD에 대해 생각해봅시다. Policy Iteration 방식으로 정책을 업데이트한다고 했을 때, 첫 번째 prediction에서 사용했던 sample들은 업데이트된 정책에서는 사용하지 못하는 sample이 될 가능성이 많습니다. 이는 behavior policy와 target policy로 같은 정책을 사용하기 때문에 발생하는 문제일 것입니다. 그렇다면 거꾸로 말해 behavior과 target policy가 다른 Off-Policy 방식은 과거에 사용한 sample을 policy improvement 후에 다시 사용한다 하더라도 문제가 없을 것이라고 생각할 수도 있을 것입니다. 이는 즉 On-Policy보다 Off-Policy 모델에서 사용하는 sample의 효율이 더 높다는 것을 의미합니다. 그럼 더 적은 sample을 가지고도 유의미한 결과를 낼 수 있겠죠. 이것이 Off-Policy Learning이 더 많이 사용되는 이유 중 하나입니다.

또 그 외에도 앞서 말했던 것처럼 behavior을 계산할 때 exploration을 고려하는 동시에 greedy improvement 방식으로 최적 정책을 계산한다던가, 다수의 정책을 학습에 사용할 수 있다는 등 실제로 강화학습을 진행할 때에는 Off-Policy 모델을 사용하면서 얻을 수 있는 이점이 훨씬 많이 있습니다. 그렇다보니 Off-Policy 기반의 Q-Learning이 SARSA나 기타 다른 On-Policy 방식의 알고리즘보다 각광받을 수밖에 없는겁니다. 그렇다면 이제, Off-Policy Learning을 어떻게 사용하는지에 대해 알아봅시다.

Importance Sampling

Q-Learning의 구체적인 동작에 대해 설명하기에 앞서, Importance Sampling(이하 IS)이라는 개념에 대해 잠깐만 짚고 넘어가겠습니다. 이해를 돕기 위해 이번에도 식부터 가져오겠습니다.

$E_{X \sim P}[f(X)]=\sum P(X)f(X)\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =\sum Q(X) {{P(X)}\over{Q(X)}}f(X)\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =E_{X \sim Q} \left[{P(X) \over Q(X)}f(X)\right ]$

언뜻봐도 되게 간단한 식이지 않나요? 이게 Importance Sampling의 전부입니다. 원래는 $P$라는 확률 분포를 사용해 $f(X)$의 기댓값을 계산해야 하지만, $\sum$의 내부에 새로운 확률 분포 $Q$를 한 번씩 곱하고 나눔으로써 $P$를 이용한 $f(X)$의 기댓값을 $Q$를 이용한 ${P(X) \over Q(X)}f(X)$의 기댓값으로 표현할 수 있게 되는 것이죠. 정말 번거롭지 않나요? 그냥 $P$를 쓰면 바로 구할 수 있는 값을 굳이 곱하고 나누는 과정을 추가하면서까지 $Q$를 사용해서 계산하려고 하는 이유가 뭘까요? 확실히 일반적인 상황에서 IS는 연산이 늘어나는 번거로운 과정입니다. 하지만 만약 우리가 알고 있는 확률 분포가 $P$가 아니라 $Q$ 뿐이라면 어떨까요? 그럼 $Q$에 대한 기댓값을 구하는 것이 훨씬 효율적으로 변할 것입니다. $P$에 대한 분포는 알지 못하기 때문에 $P$의 분포를 따르는 샘플을 추출하는 것은 불가능하지만, $Q$의 분포와, 특정 위치에서의 $P$의 값은 알 수 있기 때문에 해당 값들을 통해 획득한 샘플을 $P$의 샘플로써 사용하는 것이지요. 이것이 바로 IS를 사용하는 목적입니다. 그렇다면 강화학습 이야기를 하다가 갑자기 느닷없이 왜 IS에 대해 설명을 한 것일까요?

$G_t^{\pi/\mu} = {\pi(A_t|S_t)\pi(A_{t+1}|S_{t+1})...\pi(A_T|S_T) \over \mu(A_t|S_t)\mu(A_{t+1}|S_{t+1})...\mu(A_T|S_T)}G_t\\ \ \\ V(S_t) \leftarrow V(S_t) + \alpha(G_t^{\pi/\mu}-V(S_t))$

위 식은 MC에서 $V$를 업데이트할 때 사용한 식에서 target에 해당하는 리턴을 IS를 통해 수정한 것입니다. 원래의 식에서는 리턴 $G_t$를 포함한 모든 가치 함수가 정책 $\mu$를 기반으로 업데이트된 값을 가지고 있었습니다. 하지만 $G_t$와 새로운 정책 $\pi$를 이용한 IS로 $\pi$ 기반의 새로운 리턴 $G_t^{\pi / \mu}$를 획득할 수 있습니다. 즉, 변형된 식에서의 target $G_t^{\pi / \mu}$는 behavior인 $V$의 정책인 $\mu$가 아닌, 정책 $\pi$를 통해 업데이트되는 항으로 바뀌는 것입니다. 따라서 IS를 사용함으로써 기존의 On-Policy Learning 모델들을 Off-Policy 모델로 사용할 수 있는 것입니다. 물론 이것은 MC에만 국한된 내용이 아닙니다. On-Policy TD인 SARSA의 업데이트 식 역시 동일한 형태로 수정할 수 있습니다.

$V(S_t) \leftarrow V(S_t) + \alpha \left({\pi(A_t|S_t) \over \mu(A_t|S_t)}(R_{t+1} + \gamma V(S_{t+1})) - V(S_t) \right)$

하지만 IS를 이용해 Off-Policy Learning 모델을 구현하는 방식은 실제로 거의 사용하지 않는 방법입니다. 이제부터 배울 Q-Learning과 같이 처음부터 다른 정책을 이용해 behavior과 target을 업데이트하는 방식이 훨씬 효율적이기 때문에, 현재로써는 이러한 방식으로도 Off-Policy 모델을 구현할 수 있다는 사실만 이해하셨다면 충분합니다.

Q-Learning

그렇다면 이제부터 본격적으로 Q-Learning에 대해 다뤄보겠습니다. Off-Policy 모델인 Q-Learning도 기본적인 형태는 지금까지의 Control 모델과 동일합니다. Q-Learning에서 action-value $Q(s, a)$를 업데이트할 때 사용하는 식은 다음과 같습니다.

$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha(R_{t+1}+ \gamma Q(S_{t+1}, A') - Q(S_t, A_t))$

Q-Learning에서 이 식이 SARSA와 다른 점은 단 한 가지, target에 해당하는 $Q$의 액션 $A$입니다. SARSA는 On-Policy 모델이기 때문에 behavior와 target의 액션 $A$가 같은 정책에 의해 정해지는 반면, Q-Learning은 지금까지 설명했던 것처럼 behavior과 target에 따라 '다른 정책'를 사용하기 때문에 이를 구분하기 위해 새로운 정책을 통해 획득한 액션 $A'$를 사용한 것입니다. 따라서 모델이 어떻게 동작하는지 이해하려면 '다른 정책'이 구체적으로 어떤 정책인지 알아야 할 필요가 있습니다.

우선, Q-Learning에서 behavior policy는 명확하게 정해져있지 않습니다. 따라서 지금까지처럼 exploration을 고려해 $\epsilon$-greedy 모델을 사용할 수도 있고, 아니면 주어진 환경에 맞춰 원하는 다른 모델을 선택해서 사용할 수도 있어 improvement 모델 선택이 자유로운 편입니다. 반면, target policy의 경우 반드시 greedy 모델을 사용해 policy improvement 과정을 진행해야 합니다. 애초에 Off-Policy 모델을 고안한 이유가 target policy를 업데이트할 때 exploration을 고려하지 않기 위함이다보니 Q-Learning 알고리즘을 만들 때부터 target policy는 greedy하게 업데이트하는 것이 가장 효율적일 것이라는 가정을 전제로 했습니다. 따라서 target policy $\pi$는 다음과 같이 나타낼 수 있습니다.

$\pi(S_{t+1}) = \argmax_{a'}Q(S_{t+1}, a')\\ \ \\ R_{t+1}+\gamma Q(S_{t+1}, A')=R_{t+1} + \max_{a'}\gamma Q(S_{t+1}, a')$

따라서, Q-Learning에서는 target policy를 업데이트할 때 $Q(S_{t+1}, a')$이 최대가 되도록 하는 $a'$를 사용해 업데이트를 진행하는 것입니다.

Double Q-Learning

기본적인 Q-Learning에 대해 배웠으니 이젠 Q-Learning을 활용한 double Q-Learning에 대해 설명하겠습니다. Double Q-Learning은 2개의 액션 가치 함수 $q$, $q'$을 이용해 업데이트를 진행하는 방식입니다. 기존의 Q-Larning은 target policy와 behavior policy가 완전히 분리되어 있었지만, Double Q-Learning에서는 target에 사용했던 $q$, $q'$를 behavior에도 사용하는 방식을 사용합니다.

$R_{t+1} + \gamma q_t'(S_{t+1}, \argmax q_t(S_{t+1}, a)) \ \ .\ .\ .\ (1)\\ R_{t+1} + \gamma q_t(S_{t+1}, \argmax q_t'(S_{t+1}, a)) \ \ .\ .\ .\ (2)$

Double Q-Learning의 TD target은 다음과 같이 나타낼 수 있습니다. 식이 2개인 이유는 업데이트할 액션 가치 함수를 $q$로 선택하느냐, $q'$으로 선택하느냐에 따라 식이 조금 달라지기 때문입니다. 만약 $q$를 업데이트하기로 선택했다면, (1)식을 이용하여 greedy한 액션을 찾을 때에는 $q$를 사용하고, 업데이트에 사용할 target은 $q'$에서 그 값을 받아오는 방식으로 동작하는 겁니다. 물론 선택한게 $q'$이라면 (2)식을 사용하여 반대로 동작을 하겠지요. $q$와 $q'$ 중 하나를 선택하는 방법은 랜덤이든 확률을 부여하든 그 방식은 상관없기 때문에 모델을 구현하는 과정에서 설정하면 되고, behavior의 경우도 $(q+q')/2$ 등의 방식으로 $q$와 $q'$을 사용하여 나타내어 사용할 수 있습니다.