[강화학습] TD: SARSA vs Q-learning

TD learning은 다음 스텝의 정보를 바탕으로 value function을 업데이트하는 방식이다. TD learning 중 on-policy는 SARSA, off-policy는 Q-learning이 대표적이다. 
SARSA는 policy를 따르며 학습하는 on-policy 알고리즘으로, 학습에 사용하는 행동도 현재 사용하는 policy에서 선택된 행동이다.
$$Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \alpha \left[ r_t + \gamma Q(s_{t+1},a_{t+1}) - Q(s_t,a_t)\right]$$
$$Q(s_t,a_t) \leftarrow (1-\alpha)Q(s_t,a_t) + \alpha \left( r_t + \gamma Q(s_{t+1},a_{t+1})\right)$$
일반적으로는 exploration 정책과 학습 정책이 동일하므로 수렴이 안정적이다. 하지만 policy가 최적이 아닐 때도 그 policy를 따르는 보수적인 업데이트로 인해 최적 정책에 도달하는 속도가 느릴 수 있다.

반면, Q-learning은 exploration하는 behavior policy와 학습하고자 하는 target policy를 분리한 off-policy 알고리즘이다. exploration을 하더라도 학습은 항상 그 상황에서의 최선의 행동을 기준으로 이루어지며, exploration을 하면서도 학습은 greedy policy 기준으로 진행되므로 더 빠르게 optimal policy를 추정할 수 있다. 하지만 실제 action과 학습 기준이 다르기 때문에 수렴이 불안정할 수 있다.
$$Q(s_t,a_t) \leftarrow Q(s_t,a_t) + \alpha \left[ r_t + \gamma max_a \,Q(s_{t+1},a) - Q(s_t,a_t)\right]$$

value function 업데이트 식에서 SARSA와의 차이는 Q-learning은 max를 통해 시행한 target policy 중 Q value function을 최대로 하는 action을 고른다는 것이다. 
앞서 이론적으로 설명한 SARSA와 Q-learning 알고리즘을 실제로 구현해보았다. 이론적으로 설명한 SARSA와 Q-Learning 알고리즘을 바탕으로, FrozenLake-v1 환경에서 직접 구현을 진행하였다.
https://www.gymlibrary.dev/environments/toy_text/frozen_lake/#frozen-lake

Frozen Lake - Gym Documentation

아래는 실제 코드 구현에서 주목할 만한 몇 가지 포인트이다.

Q table

Q = np.zeros((state_size, action_size))

초반에 Q table을 만들고 각 (state,action) 쌍에 대해 Q 값을 0으로 초기화한다. FrozenLake-v1 환경은 discrete 상태공간이므로 2차원 배열로 표현할 수 있다.

ε -Greedy Policy

def epsilon_greedy(self, Q, epsilon):
    policy = np.ones((state_dim, action_dim)) * epsilon / action_dim
    policy[np.arange(state_dim), np.argmax(Q, axis=1)] += 1 - epsilon
    return policy

ε 확률로 random action을 선택하고, (1−ε)의 확률로 최댓값을 선택하는 policy이다. 두 알고리즘 모두 동일한 방식으로 action을 선택합니다.

SARSA 업데이트

Q[state, action] += alpha * (reward + gamma * Q[next_state, next_action] - Q[state, action])

실제로 선택한 다음 action을 기반으로 업데이트하는 on-policy 방식이다. 

Q-Learning 업데이트

Q[state, action] += alpha * (reward + gamma * np.max(Q[next_state]) - Q[state, action])

다음 상태에서 가능한 행동 중 가장 Q값이 높은 행동을 기준으로 업데이트하는 off-policy 방식이다. Q-learning은 greedy policy를 기준으로 업데이트하지만, 실제 action 선택은 ε -greedy policy를 사용하여 exploration하며, 이를 통해 상태 공간의 더 넓은 영역을 학습할 수 있게 된다.
자세한 내용은 아래 깃허브 링크에서 확인할 수 있다.
Github : https://github.com/seonvin0319/25RL_Study/tree/main/TD

25RL_Study/DP at main · seonvin0319/25RL_Study

이 글은 Sutton & Barto의 Reinforcement Learning 6장을 바탕으로 작성되었다.