[강화학습] SARSA와 DQN 개념 정리

 

 

심층 강화학습의 주요 포인트를 확실하게 파악하고 넘어간다.

그 후, SARSA와 DQN의 개념을 정리하고 둘의 차이점을 비교한다.

 

 

* 본 포스팅은 책 'Foundations of Deep Reinforcement Learning: Theory and Practice in Python'을 참고하고 정리한 것임을 밝힙니다. 포스팅 내에 쓰인 수식과 알고리즘 그림은 책에서 가져온 것입니다.

 

 

1. Value-based Algorithm

 

$V^{\pi}(s)$ or $Q^{\pi}(s, a)$

 

이전 포스팅에서 다룬 Model-based 기반 REINFORCE 알고리즘은 agent가 직접 policy를 학습해 가는 방식이었다. 하지만 이번 Value-based 알고리즘은 state-action 쌍을 직접 평가하면서 actions을 결정한다.

 

 

Q(s, a)는 state와 action을 모두 고려하고, V(s)는 state만을 고려한다. V는 사실상 Q로 도출할 수 있는데, 이는 state에서 취할 수 있는 모든 action의 기댓값이 곧 V(s)이기 때문이다.

 

 

$V^{\pi}(s)$는 State에서 특정 action에 대한 정보를 가지고 있지 않기에, 어떤 state에서든 restart의 비용이 커질 수밖에 없다. state에서 가능한 모든 action들을 해봐야 하기 때문이다. 반면에 $Q^{\pi}(s, a)$는 이 문제를 피할 수 있어, $Q^{\pi}(s, a)$를 활용하는 경우가 더 많다. 

 

 

 

2. Temporal Difference Learning (TD)

: model-free 강화학습 방식의 한 종류. value function의 current estimate로부터 bootstrapping 하는 방식으로 학습한다. 

 

TD의 Q 수식

 

SARSA 문제에선 trajectories를 생성하고, Q-value for each (s, a) pair를 예측한다. trajectories는 $Q_{tar}$를 생성할 때 활용한다. 결국 Q-value와 $Q_{tar}$ 사이의 간격을 줄여가는 문제다. TD learning은 $Q_{tar}$를 얼마나 잘 생성할 것인가에 대한 이야기다.

 

왜 TD를 활용하는 것일까?

 

2-1. $Q_{tar:MC}^{\pi}$는 몬테카를로(MC)를 통해 추측하는 value function을 가리키는데, 수식을 보면 알 수 있듯이 모든 trajectories의 returns를 평균 낸 것이다.

MC 방식의 Q 수식

 

MC 방식을 통할 경우, agent는 Q를 예측하기 위해 episode들이 끝날 때까지 기다려야 한다. 위의 수식을 보아도, Q는 trajectories들의 returns 합이 나올 때 구할 수 있다. 반면에, TD는 time-step 별로 이전의 value function 값들을 토대로 현재 value function을 추정할 수 있다. 이에 따라, trajectories가 끝날 때까지 기다릴 필요가 없게 된다.

 

2-2. DP(dynamic Programming)도 time-step 방식으로, 매 step마다 업데이트하거나, 그 전의 결과들을 토대로 현재 값을 추측할 수 있다. 다만, DP는 모든 경우의 수를 다 찾는다는 점에서 강화학습 문제를 풀기에 적합하지 않다. 최적의 경로로 가장 빠르게 가야 하기 때문이다. 즉, TD는 MC의 random sample 방식과 DP의 time-step 방식을 각각 가져온 것이라 볼 수 있다. 

 

 

	Model-free	Bootstrapping	Update
DP	X (full-width)	O	Time-step
MC	O (Sample)	X	End of episode
TD	O (Sample)	O	Time-step

(정리표)

 

 

 

3. SARSA 개념과 Training process

: Value-based algorithm의 강화학습 방법 중 하나

 

주요 특징
1) TD learning(Q-function) 방식을 활용
2) ε-greedy policy (a method for generating actions): 다음 action을 결정짓는 방법 중 하나로, random 하게 액션을 선택할 수 있는 여지를 남겨둠으로써 bias 문제를 해결하고자 했다.
3) on-policy: policy를 직접 학습시키는 것(REINFORCE) 외에도, Target value가 action 생성하는 policy에 의존할 경우도 on-policy로 본다. line 8을 보면, Target value인 $y_{i}$가 a'에 의존하는 것을 볼 수 있다. a'는 experience-generating policy(ε-greedy)에 의존하고 있으므로 SARSA를 on-policy라고 볼 수 있다.

 

 

SARSA algorithm을 간략하게 살펴보자. (1) 처음에 입실론과 세타를 초기화하고, Max step을 지정하고 (2) for문을 돌린다. (3) ε-greedy를 통해 trajectories를 생성, (4) 그 안에서 다시 Q 값을 구하며 target value를 업데이트한다. (5) target value와 $Q^{\pi}$의 차이를 구하고, (6) 세타를 업데이트한다.  

 

SARSA와 비슷하게 언급되는 알고리즘이 Q-learning(심층 신경망을 활용한 버전이 DQN)이다. 방식은 똑같은데, $Q^{\pi}$를 업데이트하는 방식이 조금 다르다. SARSA는 실제 action과 state 그 자체를 선택하는 반면, Q-learning은 그중에서 제일 큰 $Q^{\pi}(s, a)$를 선택하여 업데이트한다.

 

 

 

 

 

3. DQN 개념과 Training process

: 딥러닝과 강화학습을 결합하여 인간 수준의 높은 성능을 달성한 첫 번째 알고리즘(from DeepMind)

 

먼저 Q-learning이란?

SARSA와 거의 비슷한 알고리즘이다. 현재 행동을 생성할 때는 ε-greedy를 활용하지만, 후에 다음 행동을 예측하거나 생성할 때는 ε-greedy가 아니라 최고의 return을 주는 action을 선택하는 방식이 활용되었다. 행동하는 정책과 학습할 때 사용하는 정책이 다르기에, Q-learning은 off-policy 알고리즘이다. 

 

Q-learning의 단점: state-action(s, a)에 해당하는 Q-value를 테이블 형식으로 저장하고 학습한다. 이 경우, state/action space가 커지면 memory/exploration time 문제가 발생

 

해결점: 딥러닝을 활용하여 Q-table에 해당하는 Q-function을 비선형 함수로 근사 시킨다면 어떨까? 굳이 저장할 필요가 없어진다.

 

 

출처: 이것저것 테크블로그

 

 

DQN의 3대 요소

 

3-1) CNN Architecture

: Q-function 근사를 linear function이 아니라 CNN Architecture를 통해 진행

 

 

3-2) Experience Replay

: 매 스텝마다 추출된 샘플 $e_{t} = (s_{t}, a_{t}, r_{t}, s_{t+1})$을 replay memory D에 저장. Replay memory D에 저장된 샘플들을 uniform 하게 랜덤 추출하여 Q-update 학습에 이용

장점 1: 본래 다음 샘플을 학습하지만, 이럴 경우 Correlation이 강한 연속된 샘플들로 모델을 학습하게 된다. 제대로 된 학습을 할 수 없기에, random 추출하여 샘플 사이의 dependency를 최대한 무시할 수 있도록 한다. 

장점 2: Q-update로 인해 behavior policy 변경 발생 시, policy로 생성되는 training data의 분포도 갑작스럽게 변화할 수 있다. 학습 데이터의 distribution 갑작스러운 변화는 학습 안정성을 해친다. 하지만 랜덤 추출을 통해 각각 다른 시간에서 수행된 샘플들로 update를 하기에 data가 편향 분포하지 않는다.

 

 

3-3) Target Network

: main Q-network와 target network의 이중화된 구조. 프로세스는 다음과 같다. (1) Target network를 활용하여 y를 계산. (2) Main Q-network를 이용하여 Q(s, a) 계산. (3) Loss function을 이용하여 Main Q-network 업데이트. (4) 매 C 스텝마다 Target network를 Main Q-network로 업데이트. 

 

Main Q-network: State, Action을 이용해 결괏값이 되는 Q(s, a)를 얻는데 이용. 매 스텝마다 파라미터가 업데이트
Target network: 기존 Q-network를 동일하게 복제한 상태에서, y(target value)를 업데이트하기 위한 maxQ(s, a) 과정에 활용. 매 C 스탭마다 Main Q-network로 업데이트. 

 

장점 1: 기존 Q-network는 $\theta$가 업데이트되면, 결괏값인 action-value와 target value(y)가 동시에 움직이게 된다. 하지만 C 스텝동안 Target value를 고정해 두면, 원하는 방향으로 업데이트시킬 수 있다. 

 

 

 

(1) line 9에서 Boltzmann policy를 활용하여 generating.
(2) line 10-11에서 생성된 데이터들을 batch로 sampling.
(3) line 12에서 U번의 epoch.
(4) line 13은 각 action들을 말하고, 이 안에서 y 업데이트가 이뤄진다.
(5) line 18-20에서 $\theta$ 업데이트.

 

 

Boltzmann policy란?
: ε-greedy의 alternative method가 될 수 있다. 완전히 랜덤 하게 맡기는 것에서 성능 향상을 한 버전. 특정 행동이 높은 Q-values와 연관되어 있다면 can be selected often. 

 

파라미터(temperature)가 크면, distribution이 uniform 해진다. 반대로 작으면, concentrated 될 수 있다. 더 나은 학습을 위해 인간이 직접 파라미터를 조정하는 것이기에, epilon-greedy에 비해 local minima에 빠지기 쉽다.