[강화학습 요약] SARSA / VFA / DQN

On policy : 현재 policy의 data만 사용

Off policy : 다른 policy의 data도 사용

 

Exploration : environment를 배우기 위해 다양한 action 취함

Exploitation : 이전의 policy로 best action취

 

$\epsilon$-greedy Policies

Policy가 deterministic 할 때는 무조건 특정 action만 진행 가능.

하지만 다른 action도 취해야 policy와 다른 Q function도 계산이 가능하므로

$\epsilon$ 의 확률은 랜덤한 action을 따르고

1-$\epsilon$의 확률로 policy를 따른다.

이러한 policy를 $\epsilon$-greedy Policy라고 한다

$\epsilon$을 N이 증가함에 따라 작아지게 만든다면 최종적으로 policy에 있는 action만 따르게 된다

(GLIE = Greedy in the Limit of Infinite Exploration)

 

MC for On Policy Q Evalutation

1. 모든 Q를 0으로 초기화

2. $\pi_i$로 episode 구하기

3. MC로 Q 구하기

4. $\pi_{i+1}=argmaxQ^{\pi_i}(s,a)$

5. $\pi_{i+1}$를  $\epsilon$-greedy Policy로 만들기

- 반복 -

 

SARSA

- (State-Action-Reward-State-Action)

-  $\epsilon$-greedy Policy + TD learning

- MC for On Policy Q Evalutation 에서 MC를 TD learning으로 바꾼 것과 동일

 

Bias

- 추가예정 : value가 overestimate 됨?

 

Double Q-learning

- bias 방지

- Q1, Q2 두 개의 Q사용

1. $\pi(s) = argmax(Q1+Q2)$ → $\epsilon$-greedy policy로 만들기

2. $\pi_i$로 episode 구하기

3. 50퍼센트의 확률로 Q1 또는 Q2 업데이트

  - Q1(s, a) ← Q1(s, a) + α * [r + γ * Q2(s', argmax(Q1(s', a')) - Q1(s, a)]

  - Q2(s, a) ← Q2(s, a) + α * [r + γ * Q1(s', argmax(Q1(s', a')) - Q2(s, a)]

4. 반복

 

- Q가 2배이므로 메모리가 더 많이 듬

- 학습 단계에서 overestimation이 줄어들어 exploration과 exploitation에서 더 안정적이다.

  → 더 optimal한 action을 찾게 해준다

 

Tabular representation

Tabular representation : State 가 제한적임, Q나 V matrix나 vector로 담을 수 있다

반대되는 개념

- Function Approximation

- Continuous State Representation

 

VFA (value function approximation)

- V와 Q는 방대한 양 모든 s와a의 경우의 수에 매핑되는 테이블로 표현되는것이 아니라 w파라미터를 통해 계산됨

$v(s;w) \approx v(s)$, $Q(s,a;w) \approx Q(s)$

대표적으로 linear value 및 nerual network로 approximation 한다

 

linear value function approximation

$\hat{V}(s;w) = \sum x_j(s)w_j = \textbf{x}(s)^T\textbf{w}$

예시

s = [s1, s2]

w = [w1, w2, w3]

x(s) = [s1, s2, s1^2]

V(s;w) = (w1*s1) + (w2*s2) + (w3*s2^2)

 

w는 Gradient descent를 통해 학습된다

V(s)를 구할 수 있는 방법이 있다고 해보자

 

Loss function을 다음과 같이 정의한다

$J(\textbf{w}) = E_\pi[(V(s)- \hat{V}(s;\textbf w))^2]$

 

stochastic한 환경에서는 V가확률로 주어지기 때문에 확률로 표현됨

 

$\Delta \textbf{w} = -\frac{1}{2}\alpha \nabla_wJ(\textbf{w})$

$\nabla_wJ(\textbf{w}) = E_\pi[2(V(s)-\hat V (s;\textbf w))]\nabla_w \hat V (s;\textbf w)$

$\Delta w = \alpha (V(s)-\hat V (s;\textbf w)) \nabla_w \hat V (s;\textbf w)$

매 descent 마다 $\Delta \textbf{w} $만큼 w가 업데이트 된다

 

하지만, V(s)를 제대로 구할 수 있는 방법은 거의 없다

model free VFA 필요

 

Monte Carlo VFA

$\Delta w = \alpha (V(s)-\hat V (s;\textbf w)) \nabla_w \hat V (s;\textbf w)$

에서 t time-step일 때 w 업데이트

$\hat{V}(s_t;w) = \textbf {x}(s_t)^T\textbf{w} $
$\Rightarrow  \nabla \hat{V}(s_t;\textbf w) = \textbf x(s_t)$

$V(s) \rightarrow G_t$ return으로 표현됨

 

$\Delta w = \alpha (V(s)-\hat V (s;\textbf w)) \nabla_w \hat V (s;\textbf w)$

 

TDVFA

$J(\textbf w) = E_\pi[(r+\gamma \hat{V}(s';\textbf w) - \hat{V}(s;\textbf w))^2]$

V(s) 대신 target이 $r+\gamma \hat{V}(s';\textbf w)$이다

 

Q function도 V 와 똑같이구할수있다

Loss function에서 V(s;w)에서 Q(s,a;w) 바꿔주기만 하면된다, 어차피 feature백터로 s,a 통해 w 계산하는 것 이외에 다 똑같다

 

DQN

V, Q에 deep neural network 적용, w가 DNN이다

 

Experience Replay

한 episode로 계속 V와 Q가 업데이트 되는 경우 현재 데이터와 직전 데이터간의 상호 연관성이 생길 수 있다.

(과거에 했던 action이 현재의 결과값에 영향을 미친다)

이전의 experience를 buffer에 넣은 후 특정 시점에 buffer에 있는 값으로 V,Q 업데이트

 

Prioritization

TD error ($ r + \gamma V(s') - V(s)$)가 높은 buffer를 선택.

TD error가 0 이라면 아무런 업데이트가 이루어지지 않는 

 

Fixed Q-Targets

estimating, updating하는 Q가 똑같은 Q라 실시간으로 변해 안정적이지 않음.

Q를 일정구간 일정하게 유지하고 한번에 업데이트

 

Dueling DQN

V(s) 와 A(s,a) advantage function을 각각 구해준 뒤,

Q(s, a) = V(s) + (A(s, a) - 1/|A| * ΣA(s, a'))

|A| : number of possible action

(장점은 잘 이해못함)

A와 S를 분리해서 다른 action에 비슷한 value 나올 때 분리해준다?