![[논문 리뷰] Prioritized Experience Replay (PER)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FC2zbS%2FbtshyPgDs9a%2F1TRaVkT984biVlIkyK7xK1%2Fimg.png)
[1511.05952] Prioritized Experience Replay (arxiv.org)
Prioritized Experience Replay
Experience replay lets online reinforcement learning agents remember and reuse experiences from the past. In prior work, experience transitions were uniformly sampled from a replay memory. However, this approach simply replays transitions at the same frequ
arxiv.org
이 논문은 DQN의 uniformly sampled experience replay를 중요도에 따라 prioritized experience replay로 바꾸어서 성능 향상을 이루어 냈다. DQN논문의 마지막에 prioritized sweeping에 대해 이야기를 하면서 성능 향상의 가능성의 제기하는데 이 논문이 그것을 이루어낸 논문이다.
[논문 리뷰] Human-level Control through Deep Reinforcement Learning (DQN)
Human-level control through deep reinforcement learning | Nature 이번에는 Nature지에 발표된 DQN관련된 논문을 리뷰해보고자 한다. Playing Atari with Deep Reinforcement Learning과 거의 같은 저자들이 작성을 했는데 이는
limepencil.tistory.com
Introduction
Online RL은 바로 들어온 데이터를 이용해 파라미터를 업데이트하는데 이는 두 가지의 문제가 있다.
- RL에서는 연속되는 데이터 간의 상관관계가 아주 크기 때문에 기존의 stochastic gradient algorithm에 부적합하다.
- rare 한 경험을 나중에 사용하지 못하고 잊어버리게 된다
이를 해결하기 위해 experience replay가 나왔고 덕분에 예전의 데이터와 최신의 데이터를 같이 학습하여 위에 제기된 문제들을 모두 해결하였다. DQN에서는 이것을 사용하여 가치함수의 학습을 안정화시켰다. DQN에서는 large sliding widnow replay memory를 사용하였는데 이는 필요한 데이터를 줄이고 이를 더 많은 계산과 메모리로 대체하였다.
하지만 위의 방법에서는 같은 확률로 모든 데이터를 사용하기 때문에 더 좋은 데이터와 덜 좋은 데이터의 차이를 구분하지 못한다는 단점이 있다 이를 염두의 두고 만든 게 prioritized experience replay (PER)이다. 이 논문에서는 temporal-difference(TD) error의 크기를 기준으로 삼아 priority를 정의하였다.
TD error은 value function의 예측값과 실제 $V$의 차이의 크기이다.
Background
많은 뇌과학적인 studies를 통해 쥐의 hippocampus에서 experience replay가 되고 있다는 사실이 밝혀졌다. 또한, 보상과 관련된 sequence는 더 자주 replay 되었다. 또한, TD error이 높은 sequence도 자주 replay 되었다. 이를 강화학습의 알고리즘에 적용을 하려고 prioritized sweeping이라는 기법이 소개되었고(1999), TD error을 이 priority의 기준으로 적용한 연구가 있었다(2013). 이 논문에서는 이 아이디어를 사용하여 model-free RL에 맞추어 변형을 시켰고 stochastic sampling을 사용하여 function approximator에 더 잘 맞도록 하였다.
Prioritized Replay
Using a replay memory leads to design choices at two levels: which experiences to store, and which experiences to replay (and how to do so). This paper addresses only the latter: making the most effective use of the replay memory for learning, assuming that its contents are outside of our control.
Replay memory를 사용하기 위해서 고려해야 할게 두 가지가 있는데:
- 어떤 experience를 저장할지
- 어떤 experince를 학습할지
이 논문에서는 1번은 컨트롤 밖이라고 생각하여 2번에 집중한다.
이 논문에서는 Blind Cliffwalk라는 환경을 예를 들어 왜 중요한지 설명한다. 이 환경에서는 reward를 random 한 방식으로 얻는데 $2^{-n}$만큼의 step이 필요한데 이를 기존의 experience replay를 사용한다면 너무 많은 실패에 성공한 experience가 묻힐 것이다. 위의 그래프를 보면 어떠한 strategy를 가지고 replay를 선택한 방법이 랜덤 하게 고르는 것보다 훨씬 더 빠른 학습 속도를 보여준다.
priority의 기준을 TD error으로 잡으면 agent가 이 experience가 얼마나 unexpected 했는지, 즉 배울 점이 많은지를 어느 정도 측정할 수 있다. 이것은 특히 online RL에 적합하지만 reward가 noisy 한 경우에는 잘 작동을 하지 않을 수 있다. TD error 순서대로 나열하고 이대로 학습을 하는 greedy TD-error prioritization은 위에 얘기했었던 환경에서 상당한 속도 향상을 보여줬다.
하지만 이 방식에는 여러 가지의 문제가 있는데:
- TD error 순서대로 replay가 되기 때문에 TD-error이 낮은 sequence는 한 번도 replay가 안될 수도 있다.
- stochastic reward 같은 noise에 취약하다
- 너무 한정된 experience만 반복해서 학습한다.
이것을 해결하기 위해 이 논문에서는 stochastic sampling을 제안한다. Stochastic prioritization을 사용하면 priority의 순서는 maintain 되나 모든 experience에 대해 0이 아닌 sampling 확률을 보장한다. 확률은 다음과 같은 식으로 정의된다. $$P(i) = \frac {p_i^\alpha}{\sum_k p_k^\alpha}$$
여기에서 $p_i$는 priority이고 $\alpha$는 얼마만큼의 prioritization을 사용하는지에 대한 hyperparameter이다 ($\alpha$ = 0일 때 uniform).
이 논문에서는 $p_i$에 대해서 두 가지를 제시하는데:
- Proportional prioritization: $p_i = |\delta_i| + \epsilon$ ($\epsilon$ is to have non-zero priority)
- Rank-based prioritization: $p_i = \frac {1}{\text {rank}(i)}$
이 논문에서는 rank-based가 outlier에 영향을 받지 않기 때문에 더 robust 하다고 설명하고 있다. 실제로 위의 그래프를 보면 Blind Cliffwalk 환경에서 더 빠른 속도로 학습하고 있는 것을 알 수 있다.
하지만 prioritization을 사용하면 expected distribution에서 멀어지기 때문에 bias가 생긴다. 이는 수렴해야 하는 정해진 정답에서 멀어지도록 된다. 이를 해결하기 위해 importance-sampling(IS)을 도입하여 해결하고자 했다.
$$w_i = \left(\frac {1}{N} \cdot \frac {1}{P(i)}\right)^{\beta}$$
이 weight을 Q-learning update때에$\delta_i$대신 $w_i \delta_i$로 사용하면 된다 ($\frac {1}{\max_i w_i}$를 사용하여 normalize 해준다). $\beta$를 어떤 값에서 시작하여 1로 anneal 하게 만들면 처음에는 크게 update가 반영이 되다가 점점 안정적으로 변한다. 이 방식의 장점은 high-error인 transition을 자주 보게 만들면서 그의 따른 gradient magnitude를 줄일 수 있는 방법이다.
Atari Experiments
DRL에서는 빼놓을 수 없는 Atari benchmark에서 DQN과 DDQN에 PER을 결합하여 state-of-the-art를 달성하였다. 이번 논문에서 나온 hyperparameter인 $\alpha$와 $\beta_0$는 coarse grid search를 사용하여 적절한 값을 찾았다. 이 방법은 성능을 올릴뿐더러 더 빠르게 학습을 진행시킬 수 있다. 또한 DDQN의 예시를 통해 DQN의 improvements들과 complementary 하다는 것이 증명되었다.
Discussion & Conclusion
Rank-based가 예상과는 다르게 그렇게 robust 한 성능을 보여주지 않았는데 이는 relative error scale을 없애면서 performance drop이 생기기 때문이다. 또한 과도한 clipping이 두 가지의 방법이 비슷한 결과를 가지고 오게 하는 이유일 수도 있다. PER을 supervised learning에도 적용시키는 방법을 말하고 있고, 또한 prioritized memory 같은 맨 처음에 말했었던 방법을 제시하고 있다. 결론적으로, PER은 학습 속도를 2배를 향상하면서 성능을 높였고 이는 RL 학습을 효율적으로 하는데에 기여했다.