[PER] Prioritized Experience Replay 논문 리뷰

본 글은 Google DeepMine 팀의 Tom Schaul, John Quan, Ioannis Antonoglou, David Silver가 ICLR(International Conference on Learning Representation) 2016년 학회지에 투고한 논문 "Prioritized Experience Replay" 라는 논문에 대해 정리 겸 리뷰하는 글이다.

---

논문 리뷰

초록의 연구 동기를 보면 다음과 같다.

기억의 되새김(Experience Replay)은 On-line 강화학습 에이전트가 기억하고 기억을 재사용할 수 있도록 해주었다. 그러나 과거의 기억들을 균일하게 뽑아 되새기며 학습하는데, 이러한 접근 방법은 경험이 주었던 충격을 망각한 채로 단지 일정 주기로 되새길 뿐이다.

 

라고 나는 의역했다. 정리하면 모든 경험은 같지 않다. 같지 않은 이유는 나에게 충격적이였던 것이나 스스로 반성하게 됐던 경험이 오래 남듯이, 경험은 제각기의 무게가 있기 때문이다.

 위 논문은 이를 Experience Replay에 녹여내어 PER를 만들었다.

 

 그렇다면 기억을 되새길 때 어떤 기억이 중요한지 가릴 기준이 필요하다. planning algorithm은 적절한 기준을 가지고 우선 순위를 매겨서 갱신하면 효과적일 수 있다고 알고 있는데, Prioritized sweeping은 갱신 할 때 변하는 값에 따라서 우선 순위를 가지는 상태를 선택한다. 그 중, TD error가 우선 순위를 결정하는 방법이 될 수 있다. (2절)

 그래서 이 논문은 우선 순위를 결정하는 메커니즘에 TD-error를 사용한다.

 

우선 순위를 결정할 기준은..? (3.2절)

 중요하게 되새길 기억의 중요한 요소는 기준으로, 각 전이(transition)의 중요성을 측정하는 기준이다. 이상적인 기준은 지금 상태에서 강화학습 에이전트가 학습할 수 있었던 양이 된다. 그런데 이 점수를 직접 계산할 순 없고, 합리적 매개체는 전이의 TD error의 크기이다. 이는 예상 외의 전이이거나 충격적인 정도를 나타낸다.

 DQN으로 TD error를 설명하면 다음과 같다.

 Experience Replay 과정 중에 target Q network로부터 target $y_j$를, Q-network로부터 $Q(s_j,a_j;\theta)$를 구하면

$$y_j = r_j + \gamma \text{max}_{a'} Q \left( s_{j+1},a';\theta^T \right)$$

$$e_{TD}=y_j - Q \left( s_j ,a_j ;\theta \right)$$

 그런데 TD error를 사용하는 방법은 TD-error를 이미 계산하는 강화학습 알고리즘(SARSA, Q-learning.. etc.)에 적합하다. 반면에 reward가 noisy한 경우에는 추정을 잘 못할 수 있다.

 

그러면 다른 경험은 되새길 필요도 없어? (3.3절)

 자극적인 것만 되새기면 괭장히 예민한 사람이 될 것이다. 강력 범죄 뉴스만 보면 세상은 험악한 곳이라고 인식하는 것 처럼..? 이렇듯 낮은 TD-error의 기억을 전혀 되새기지 않으면 기억의 다양성이 적어져서 시스템은 과적합되기 쉽다. 그렇다면 자극적인 것만 되새기는 방법을 Greedy prioritization이라 하면 균일하게 기억을 되새기는 Uniform random sampling 사이에 적당히 보간하여 사용해보자. 전이 $i$의 표본 순위(the probability of sampling transition) $P(i)$ 를 다음과 같이 정의하자.

$$P(i) = \frac{ p^\alpha_i}{\sum_k p^\alpha_k}$$

 $p_i>0$는 전이 $i$의 우선도(priority of transition)가 된다. 여기서 $\alpha$를 조절하여 얼마나 우선화를 할 것인가 결정할 수 있다. $\alpha=0$이면 Uniform random sampling이 된다.

 첫번째 변형은 직접적인 방법으로, 비례 우선화 (Proportional prioritization) 이며 $\varepsilon$은 정말 중요하지 않은 기억이라고 되새기지 않는 것을 방지하는 최저값이다. 

$$p_i =| \delta_i | +\varepsilon$$

 두번째 변형은 간접적인 방법으로 순위 우선화 (Rank-based prioritization) 이며 rank는 기억을 중요한 순서대로 줄 세운 순번이다. 가장 중요하면, $|\delta_i|$가 가장 크면 1이 되겠지?

$$p_i = \left(\text{rank(i)}\right)^{-1} $$

 여기서 두번째 변형은 $|\delta_i|$의 크기가 매우 크다고 해서 큰 영향을 받지 않으므로 강건한(robust) 특성을 가진다. 왜냐하면 그저 순번을 기반으로 되새김의 우선 순위를 결정하기 때문이다.

 

편향을 해소해주는 방법(Annealing the bias)

순위를 매겨서 되새기는 것은 의도치 않은 방향으로 분포를 변형시기기 때문에 편향을 야기한다. 

Importance-Sampling(IS) weight을 통해서 편향을 교정할 수 있다.

$$w_i = \left ( \frac{1}{N} \cdot \frac{1}{P(i)} \right)^\beta$$

$\beta=1$이라면 non-uniform probabilities $P(i)$를 완벽히 보상할 수 있다. 이런 가중치는 Q-learning의 갱신에 $\delta_i$ 대신 $w_i \delta_i$를 써서 넣어줄 수 있다. 그리고 안정성의 이유로 가중치를 $1/\text{max}_i w_i $ 으로 정규화해줌으로써 갱신 량을 작아지는 방향으로 조절해주기만 한다.

 

사족

이와 관련하여 PER를 구현한 코드를 찾아볼 수 있는데,

스텝을 진행하다가 divided by zero warnining을 내면서 멎거나 int is not subscription? 이라면서 터지는 경우가 있다.

이는 sumtree 에서 무작위적으로 표본을 뽑고 이에 대해 자료형을 확인하고 넣어주면 된다.

PER 의사 코드 해설

PER의 핵심은 아래 의사 코드의 9~13째 줄이 핵심이다.

Line 9 : 어떤 전이 $j$에 대해서 뽑을 확률을 계산해서 표본을 뽑는다.

Line 10 : IS 가중치를 계산해준다.

Line 12 : 지금 구한 TD-error로 방금 되새긴 경험의 순위 점수를 갱신해준다.

Line 13 : 네트워크 매개변수 $\theta$를 갱신한다.

Appendix

논문에서는 PER의 구현과 Hyper-parameter 선정 방법에 대해서만 정리했다.

효율적으로 PER을 구현하는 방법

Rank-based Prioritization : 저자는 우선순위 큐를 array-based binary heap으로 구현했다고 한다.

Proportional Prioritization : Sum tree 구조를 추천하는데, 이는 Sum tree의 구조에서 기인한다. Sum tree는 자식 노드 값의 합을 부모 노드가 가지고 있다. 자식 노드가 우선도 $p_i$ 값을 들고 있다고 하면 최상위 부모 노드의 값을 통해서 $\sum_k p_k$를 바로 얻을 수 있다. 따라서 mini-batch에서의 transition $i$의 표본 추출 확률 $P_i$를 구할 때 우선도 $p_i$의 합을 바로 구할 수 있다. 표본 추출 확률 $P_i$를 다시 보면 다음과 같다.

$$P_i=\frac{p_i ^\alpha}{\sum_k p_k^\alpha}$$

그리고 Importance Sampling 을 통해서 모든 가중치는 가중치의 최댓값이 1이 되도록 조정한다. 논문에서는 폭발적으로 큰 갱신 가능성을 피하고자, 합리적인 범위 내에서 모든 가중치를 유지시키는 것이 실질적으로 더 잘 작동한다고 했다. 이는 정규화(Normalization)가 편향 해소 매개변수인 $\beta$와 상호작용하기 때문에 $\beta$를 1으로 움직이는 (정규화 상수를 키우는) 방법은 스텝 크기 $\eta$로 annealing하는 것과 비슷하게 효율적인 평균 갱신을 줄여준다. <이 문단은 의역이 좀 필요한듯..>

Hyper-parameter 선정

논문에서는 아타리 게임을 이용하여 Hyper-parameter $\alpha$, $\beta$, $\eta$를 일정 범위를 정하여 튜닝했다고 한다. 그래서 선택된 값들은 다음 그림과 같다.

 

표를 참고하면

Proprotional Prioritization이라면 $\alpha$ 는 0.6, $\beta$는 0.4 -> 1.0으로 

Rank-based Prioritization이라면 $\alpha$는 0.7, $\beta$는 0.5 -> 1.0으로

조정하여 사용하는 것이 좋은 것 같다.

---

 

Reference

[1] "Prioritized Experience Replay (PER) implementation in PyTorch", https://github.com/rlcode/per