들어가며...

앞 글의 TD(0)는 정해진 Policy $\pi$의 State value를 학습했다.

$$V(S_t) \leftarrow V(S_t) + \alpha \left[ R_{t+1} + \gamma V(S_{t+1}) - V(S_t) \right]$$

이것은 Prediction 문제다. 현재 Policy를 계속 따르면 각 State가 얼마나 좋은지 평가한다.

이제는 Policy 자체를 개선하는 Control 문제로 넘어가야 한다. 어느 Action을 골라야 하는지 알려면 State value보다 Action value가 편하다.

$$Q(s,a)$$

State $s$에서 Action $a$를 했을 때 장기적으로 얼마나 좋은지를 직접 저장하기 때문이다. Transition model을 몰라도 각 Action의 Q값을 비교해 가장 큰 것을 고를 수 있다.

TD Control의 기본 Update 모양은 다음과 같다.

$$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha \left[ \text{TD target} - Q(S_t,A_t) \right]$$

SARSA와 Q-Learning의 차이는 거의 전부 TD target 안에 있다.

• SARSA는 실제로 선택한 다음 Action의 Q값을 빌린다.
• Q-Learning은 다음 State에서 가장 큰 Q값을 빌린다.

겉으로 비슷한 수식이 On-policy와 Off-policy로 갈라지는 이유를 천천히 살펴보자.

SARSA는 실제로 이어진 다섯 항목에서 이름이 왔다

SARSA는 한 번의 Update에 사용하는 경험 순서의 앞글자를 이어 붙인 이름이다.

$$S_t, A_t, R_{t+1}, S_{t+1}, A_{t+1}$$

State에서 Action을 하고 Reward와 Next State를 받은 뒤, 현재 Policy가 실제로 다음 Action까지 선택한다.

SARSA의 Target은 다음과 같다.

$$R_{t+1} + \gamma Q(S_{t+1},A_{t+1})$$

전체 Update 식은,

$$\begin{aligned} Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha \big[ R_{t+1} + \gamma Q(S_{t+1},A_{t+1}) - Q(S_t,A_t) \big] \end{aligned}$$

이다.

여기서 $A_{t+1}$은 단순히 Q값이 가장 큰 Action이라고 가정하지 않는다. Agent가 현재 사용 중인 Policy, 예를 들어 $\epsilon$-greedy Policy로 실제 선택한 Action이다.

탐색 때문에 두 번째로 좋아 보이는 Action을 골랐다면 SARSA Target도 그 Action의 Q값을 사용한다.

Q-Learning은 실제 다음 Action 대신 최대값을 본다

Q-Learning의 Target은 다음 State에서 가능한 Action 중 가장 큰 Q값을 사용한다.

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

전체 Update는 다음과 같다.

$$\begin{aligned} Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha \big[ R_{t+1} + \gamma \max_{a'} Q(S_{t+1},a') - Q(S_t,A_t) \big] \end{aligned}$$

Agent가 다음에 어떤 Action을 실제로 선택했는지는 Target 계산에 들어가지 않는다. 다음 State에서 Greedy하게 행동했다면 얻을 수 있는 가장 큰 Q값을 바라본다.

그림의 Next State에서 Q값이 $5$, $2$, $1$인 세 Action이 있다고 하자. 탐색 때문에 Agent가 Q값 $2$인 Action을 실제 선택했다.

• SARSA가 빌리는 값: $2$
• Q-Learning이 빌리는 값: $5$

이 한 칸의 차이가 두 Algorithm의 학습 대상 Policy를 바꾼다.

같은 숫자로 두 Update를 계산해보기

현재 경험과 추정이 다음과 같다고 하자.

• $Q(S_t,A_t)=4$
• $R_{t+1}=1$
• 실제로 고른 $A_{t+1}$의 Q값은 $2$
• Next State의 최대 Q값은 $5$
• $\gamma=0.9$
• $\alpha=0.1$

SARSA

Target은,

$$1+0.9\times2=2.8$$

이다. 현재 Q값 $4$보다 낮으므로 Update하면,

$$\begin{aligned} Q(S_t,A_t) &\leftarrow 4+0.1(2.8-4) \\ &= 3.88 \end{aligned}$$

가 된다.

Q-Learning

Target은,

$$1+0.9\times5=5.5$$

이다. Update하면,

$$\begin{aligned} Q(S_t,A_t) &\leftarrow 4+0.1(5.5-4) \\ &= 4.15 \end{aligned}$$

가 된다.

같은 $(S_t,A_t,R_{t+1},S_{t+1})$를 봤는데 SARSA는 값을 내리고 Q-Learning은 값을 올렸다. SARSA는 실제 Policy가 탐색 Action까지 포함해 만들어낼 미래를 평가했고, Q-Learning은 Greedy하게 행동할 Target policy의 미래를 평가했기 때문이다.

On-policy와 Off-policy

On-policy는 Data를 만드는 Policy와 학습하려는 Policy가 같은 경우다.

SARSA에서는 현재 $\epsilon$-greedy Policy가 다음 Action을 고르고, 그 Action의 Q값으로 같은 Policy를 평가한다.

$$\text{behaviour policy} = \text{target policy}$$

Off-policy는 Data를 만드는 Policy와 학습하려는 Policy가 다를 수 있다.

Q-Learning에서는 실제 행동을 만드는 Behaviour policy가 $\epsilon$-greedy일 수 있지만, Target은 Greedy policy를 가정한다.

$$\text{behaviour: }\epsilon\text{-greedy}$$ $$\text{target: greedy}$$

Off-policy라고 해서 아무 Data로나 무조건 잘 배운다는 뜻은 아니다. Behaviour policy가 필요한 State-Action을 충분히 방문해야 하고, Function approximation과 결합하면 학습이 불안정해질 수도 있다. 지금은 Tabular 환경에서 두 Policy의 역할이 분리된다는 뜻으로 이해하면 충분하다.

Cliff Walking에서 보이는 직관

SARSA와 Q-Learning의 차이를 설명할 때 Cliff Walking 예시가 자주 등장한다.

출발점과 도착점 사이의 가장 짧은 길이 절벽 바로 옆에 있다고 하자. 절벽에 빠지면 큰 음의 Reward를 받고 출발점으로 돌아간다.

Agent는 학습 중에 $\epsilon$-greedy로 탐색한다. 따라서 Greedy path를 따라가다가도 작은 확률로 엉뚱한 방향을 선택할 수 있다.

SARSA의 관점

SARSA는 다음에도 $\epsilon$-greedy로 행동할 실제 Policy를 평가한다. 절벽 가까이에서는 탐색 Action 하나로 추락할 위험까지 Value에 반영된다. 그래서 학습 중 사용 중인 Policy에 더 안전한 우회 경로가 좋아 보일 수 있다.

Q-Learning의 관점

Q-Learning Target은 Next State부터 Greedy하게 행동한다고 본다. 탐색 때문에 실수할 가능성을 Target policy에 포함하지 않는다. 따라서 Greedy policy 기준으로 가장 짧은 절벽 가장자리 경로를 높게 평가할 수 있다.

이 예시는 SARSA가 항상 안전하고 Q-Learning이 항상 위험하다는 일반 법칙은 아니다. Behaviour와 Target이 같은지 다른지가 학습 결과에 어떤 차이를 만들 수 있는지 보여주는 직관적인 환경이다.

왜 두 방법 모두 Exploration이 필요할까?

Q-Learning은 Target에서 $\max$를 사용하니 Greedy하게 행동만 해도 될 것 같지만, Data를 모으는 Behaviour policy에는 여전히 Exploration이 필요하다.

초기 Q값은 정확하지 않다. Greedy action만 반복하면 우연히 처음 높게 평가된 Action에 갇힐 수 있다. 선택하지 않은 Action의 Q값은 고칠 경험도 생기지 않는다.

그래서 보통 다음처럼 행동한다.

• 높은 확률로 현재 가장 큰 Q값의 Action을 선택한다.
• 작은 확률 $\epsilon$으로 다른 Action도 시도한다.

SARSA는 이 $\epsilon$-greedy 행동 자체의 Q값을 학습한다. Q-Learning은 $\epsilon$-greedy로 경험을 모으면서 Greedy target을 학습한다.

Exploration을 언제 얼마나 줄일지는 다음 글의 주제다.

Terminal state에서의 Target

Next State가 Terminal이면 그 이후 미래 Value는 $0$으로 둔다.

$$Q(S_{t+1},a)=0 \qquad \text{if } S_{t+1}\text{ is terminal}$$

두 Algorithm 모두 마지막 Transition에서는 Target에 즉시 Reward만 남는다.

$$\text{Target}=R_{t+1}$$

Terminal 이후에는 다음 Action이 없으므로 SARSA의 $A_{t+1}$도 선택하지 않는다.

SARSA와 Q-Learning의 흐름

SARSA

1. $S_t$에서 Policy로 $A_t$를 고른다.
2. Action을 실행해 $R_{t+1},S_{t+1}$을 관찰한다.
3. 같은 Policy로 $A_{t+1}$을 실제 선택한다.
4. $R_{t+1}+\gamma Q(S_{t+1},A_{t+1})$로 Update한다.
5. $(S_t,A_t)\leftarrow(S_{t+1},A_{t+1})$로 이동한다.

Q-Learning

1. $S_t$에서 Behaviour policy로 $A_t$를 고른다.
2. Action을 실행해 $R_{t+1},S_{t+1}$을 관찰한다.
3. $R_{t+1}+\gamma\max_{a'}Q(S_{t+1},a')$로 Update한다.
4. Next State에서 Behaviour policy로 다음 Action을 고른다.

SARSA는 다음 Action을 먼저 골라야 현재 Update를 할 수 있고, Q-Learning은 Next State의 Q값들만 있으면 Update할 수 있다.

자주 헷갈리는 부분

SARSA도 Greedy action을 고를 수 있다

On-policy라는 말이 항상 무작위 Action만 쓴다는 뜻은 아니다. 현재 Policy가 $\epsilon$-greedy라면 대부분의 경우 Greedy action을 고른다. 다만 탐색으로 다른 Action을 골랐을 때도 그 실제 Action을 Target에 반영한다.

Q-Learning의 Behaviour가 Greedy일 필요는 없다

Target은 Greedy하지만 경험은 $\epsilon$-greedy 등 다른 Policy로 모을 수 있다.

$\max$는 Action을 실행하는 연산이 아니다

Q-Learning Update에서 $\max$는 Target을 계산하기 위해 가장 큰 숫자를 읽는 것이다. Agent가 실제로 그 Action을 실행했다는 뜻은 아니다.

둘 다 Value estimate를 Bootstrap한다

두 Algorithm 모두 실제 Return을 끝까지 기다리지 않고 Next State의 Q 추정을 빌린다. 차이는 어느 Next Action의 Q값을 빌리는가다.

이번 글에서 기억할 것

이번 글의 핵심은 다음과 같다.

SARSA는 실제로 행동하는 Policy의 미래를 배우고, Q-Learning은 경험을 만든 Policy와 별개로 Greedy policy의 미래를 배운다.

조금 더 나누면 다음과 같다.

1. SARSA Target은 $R_{t+1}+\gamma Q(S_{t+1},A_{t+1})$다.
2. Q-Learning Target은 $R_{t+1}+\gamma\max_{a'}Q(S_{t+1},a')$다.
3. SARSA는 On-policy, Q-Learning은 Off-policy다.
4. Q-Learning의 $\max$ Action이 실제 실행된 Action일 필요는 없다.
5. 두 방법 모두 충분한 경험을 모으려면 Exploration이 필요하다.

다음 글에서는 이 Exploration을 별도 문제로 꺼내 살펴본다. Multi-Armed Bandit을 이용해 Greedy policy가 왜 나쁜 선택에 갇힐 수 있는지, $\epsilon$-greedy와 UCB가 새로운 Action을 어떤 기준으로 시도하는지 정리할 예정이다.

참고 자료

• David Silver, Lecture 5: Model-Free Control
• 서울대학교 DSBA 연구실, Introduction of Reinforcement Learning
• Sutton & Barto, Reinforcement Learning: An Introduction, 2nd Edition