[강화학습 #07] SARSA and Q-Learning

이번 장에서는 TD를 사용하는 model-free control 중
on-policy에서의 SARSA와 off-policy에서의 Q-Learning을 알아본다.

SARSA

TD(0)에서 state value를 업데이트하는 식은 다음과 같았다.

이를 action value function을 적용하여 표현하면 다음과 같을 것이다.

기존 state value function을 사용했던 것과 다르게 action value function을 사용해서 state와 action의 pair을 통해 계산되는 것을 볼 수 있는데, 이를 SARSA라고 한다. SARSA는 현재 policy를 통해 얻어낸 A와 A'으로 바로 policy를 업데이트 하므로 on-policy 방식이라 할 수 있는 것이다.

 

SARSA는 이전 장에서 언급한 ϵ-greedy policy를 사용하며 이에 따라 GLIE와 Robbins-Monro sequence조건을 지켜야 하는데, 이는 다음과 같다.

 

또한 SARSA 역시 n-step TD와 TD(λ)처럼 n-step SARSA와 SARSA(λ)를 사용할 수 있다. 식 역시 state value function을 사용했던 것에서 action value function으로 바꿔주면 끝이다.

n-Step SARSA

Forward View SARSA(λ)

Backward View SARSA(λ)

---

Importance Sampling

이전 장에서 off-policy learning은 탐험을 하는 policy로 더 다양한 탐험을 하고, optimal한 target policy에 가까워지게 하는 방법이었다. 우리는 여기에 Importance Sampling을 적용하고자 한다. Importance Sampling은 원래 통계학에서 나온 개념으로, 중요한 부분을 알아내어 그 위주로 탐색을 해서 더 빠르고 효율적으로 값을 추정할 수 있다는 아이디어이다.

위 식에서 f(X)를 state value function이라 생각하고, P(X)를 현재 policy로 형성된 distribution이라 생각하자. 즉 현재 policy만으로 학습을 시켜 나간다고 볼 수 있는데, 이때 또 다른 distribution인 Q(X)를 P(X)f(X)에 곱해주고 나눠보자.

그럼 위와 같이 식 변형이 가능하다. 마지막 수식을 보면 P(X)로 형성된 distribution과 Q(X)로 형성된 distribution을 모두 따르면서 학습시킨다고 볼 수 있는 것이다. 이제 이를 MC와 TD에도 적용시켜 보자. 아래에서는 분자가 목표 policy고, 분모가 행동 policy라 보면 된다.

Importance Sampling for Off-Policy MC

Importance Sampling for Off-Policy TD

 

그러나 MC에서는 π와 μ값의 차이가 누적될수록 variance가 급격히 증가하고, TD에서도 감소했다 하지만 여전히 on-policy에 비해서는 높은 variance를 갖는다는 단점이 있다. 따라서 Importance Sampling은 한계가 있는 방법임을 알 수 있고, 따라서 아래의 Q-Learning이 등장하게 되었다.

---

Q-Learning

Q-Learning은 다음과 같은 특징을 갖고 있다.

• SARSA와 마찬가지로 action value function 사용
• 현재 state St에서의 action At는 행동 policy인 μ를 따라 선택
• 다음 state St+1에서의 action A'은 목표 policy인 π를 따라 선택

이를 다시 말하면, 에이전트의 action은 행동 policy를 기반으로 선택하고, action value function에 대한 예측을 수행할 때는 목표 policy를 사용하는 것이다. 이렇게 하면 off-policy의 단점이었던 높은 variance를 낮출 수 있다고 한다.

 

또한 Q-learning에서 μ는 ϵ-greedy 탐험을, π는 greedy 탐험을 실시한다. 앞선 SARSA에서는 모두 ϵ-greedy 탐험을 진행했다는 점과 차이가 있다. 이를 수식으로 표현하면 아래와 같다.

위의 내용들을 모두 종합하여 Q-Learning의 최종 식을 다음과 같이 나타낼 수 있다.

이 식을 보면 SARSA와 또 다른 차이를 볼 수 있는데, SARSA는 action value function을 Bellman Expectation Equation에 적용한 형태이고, Q-Learning은 action value function을 Bellman Optimal Equation에 적용한 형태임을 알 수 있다.