[논문] PRIORITIZED EXPERIENCE REPLAY
카테고리: Papers
0. Abstract
Experience replay는 online RL agent가 과거의 experience를 기억하고 재사용할 수 있게 했다.
이때 Experience transition은 Experience memory로부터 중요도에 상관없이 같은 확률로 sampling 된다.
이 논문에서는 prioritizing experience를 위한 프레임워크를 만들어 중요한 transition은 더 자주 replay 되도록 해 학습을 효율적으로 하게한다.
1. Introduction
기존의 방식은 single update 후에 사용한 데이터를 즉시 버렸다.
하지만 이러한 방식에는 두가지 문제점이 있었다.
- i.i.d assumption을 깨는 상관관계가 강한 update를 한다.
- 나중에 사용될 수도 있는 rare한 experience를 빨리 잊어버린다.
Experience replay는 experience를 replay memory에 저장해 위 문제를 해결했다.
- 저장된 experience를 섞어 사용해 상관관계를 없앤다.
- rare한 experience도 single update보다는 많이 사용한다.
experience replay를 사용한 DQN에서의 value function의 학습 안정화를 통해 이에 대한 해결을 입증했다.
이 논문에서는 transition을 prioritizing하는 것이 어떻게 더 효과적이고 효율적인지를 설명한다.
key idea : RL agent는 어떤 transition으로 다른 transition보다 더 효과적으로 학습할 수 있다.
즉, 모든 transition이 동일하게 중요한게 아니라 transition마다 중요도가 다르다는 것이다.
Experience replay는 transition을 경험한 순서대로 사용하는 것으로부터 자유롭게했다.
PER은 경험한 transition을 같은 확률로 사용하는 것으로부터 자유롭게 한다.
TD error를 통해 그들의 중요도를 측정해 높은 transition은 학습하는데 더 자주 사용한다.
하지만 이러한 방식에도 문제점이 있는데 각각의 방법을 통해 보완한다.
- loss of diversity → stochastic prioritization을 통해 완화한다.
- introduce bias → important sampling을 통해 보완한다.
2. Background
Priortized sweeping 방식을 통해 value iteration 같은 planning algorithm에서 적절한 순서로 prioritizing update를 하면 더 효율적이게 할 수 있다.
이 방식은 다음에 업데이트할 state를 선택하는데, 만약 그 State가 업데이트될 경우 value 변화가 클 것으로 예상되는 State를 우선적으로 선택한다.
TD error가 이러한 우선순위를 측정하는 방법이다.
PER은 value iteration의 경우와 비슷한 prioritization 방법을 사용하지만 두가지 차이점이 있다.
- model-based planning이 아닌 model-free RL이다.
- stochastic prioritization을 사용한다.
- function approximator를 사용해 학습할 때 더 robust하다.
3. PRIORITIZED REPLAY
replay memory를 사용하는 것은 크게 두 단계를 고려해 설계해야한다.
- 어떤 경험을 저장할지
- 어떤 경험을 replay할지
이 논문은 학습을 위해 replay memory의 가장 효과적으로 사용하는 방법을 연구한다.
(어떤 경험을 저장하는 지에 대해서는 통제할 수 없다고 가정한다.)
prioritization의 잠재적인 이득을 이해하기 위해서 위의 예시를 볼 수 있다. 이 예시는 reward가 rare할 때 exploration의 어려움을 보여준다.
state를 이동하는 action은 두가지로 right, wrong이 있다. right을 선택하면 이동하고 wrong을 선택하면 1로 돌아온다. state 1에서 시작해 state n까지 간다면 reward 1을 얻고 wrong을 선택하면 0을 얻는다.
n개의 state로 시작해서 처음으로 0이 아닌 reward를 받는 경우의 수는 \(2^n\)이다.
두 agent가 있다고 가정하고 첫번째 agent는 일정하게 transition을 replay 하고 두번째 oracle agent는 transition을 prioritize하고 replay한다.
이 oracle은 현재 state에서 최대한 loss를 줄이는 방향으로 greedy하게 transition을 선택한다.
이러한 oracle은 현실적으로 불가능하지만, 오른쪽 그래프는 좋은 순서로 transition을 고르는 것이 얼마나 극적으로 성능을 향상시킬수 있는지 알 수 있다.
3.2 PRIORITIZING WITH TD-ERROR
앞서 priortize의 효과를 그래프로 확인했다. 그렇다면 이제 어떻게 priortize를 할지알아야한다.
prioritized replay의 핵심 요소는 transition의 중요도를 측정하는 기준이다.
이상적인 기준은 “agent가 그 transition을 통해 얼마나 학습할 수 있는지”인데 이것을 직접적으로 구할수는 없어서 그 대안으로 TD error \(\delta\)를 사용한다.
TD error는 해당 transition이 얼마나 놀라운지, 얼마나 예상밖의 transition인지 나타낸다. 즉, 다음 단계의 bootstrap estimate과 실제값의 차이를 나타낸다.
SARSA나 Q-learning같은 online RL 알고리즘에 적합하다. 이미 TD error가 계산이 되어있고, 이를 기반으로 파라미터를 업데이트하기 때문이다.
( 그렇다고 TD error가 항상 좋은 기준인것은 아니다. reward가 noisy하다면 부정확할 수 있다.)
TD error의 효과를 확인하기 위해 앞서 살펴본 방식과 greedy TD-error prioritization를 비교할 수 있다.
greedy TD-error prioritization은 그 transition의 가장 마지막 TD error를 transition과 함께 memory에 저장한다. 그리고 TD error가 가장 큰 transition을 replay한다.
처음 들어온 transition은 알고있던 TD error가 없기 때문에 무조건 maximal priority로 간다. 그러므로 모든 경험이 한번은 사용된다.
위 그래프를 통해 TD-error 사용의 효과에 대해서 볼 수 있다.
3.3 STOCHASTIC PRIORITIZATION
하지만 greedy TD-error prioritization에도 몇가지 문제가 있다.
- replay memory 전체를 sweep하는 비용을 피하기 위해 TD error는 replay하는 transition만 업데이트를 한다. → 한번 방문했을 때 TD error가 낮으면 오래동안 다시 replay되지 않는다.
- noise에 민감하다. bootstrapping에 의해 더욱 심해질 수 있다.
- greedy prioritization은 경험의 작은 부분만 집중을한다.
- function approximator를 사용할 때, error가 천천히 감소하기 때문에 transition의 초기 error값이 높게 잡히면 자주 replay된다.
이러한 loss of diversity은 시스템을 overfitting하게 한다.
이러한 문제점을 해결하기 위해 pure greedy prioritization과 uniform random sampling 방법을 섞어 서로의 장단점을 보완한 stochastic sampling을 제안한다.
즉, replay memory 내의 prioritization은 유지하되 모든 transition에 대해 non-zero의 확률을 보장하게 한다.
Sampled될 확률 \(P(i)\)는 다음과 같이 정의한다.
\(p_i\) : transition i의 priority (\(p_i > 0\))
\(\alpha\) : prioritization이 얼마나 강하게 작용할지를 나타낸다
(\(\alpha\) = 0이면 uniform case, \(\alpha\) =1이면 greedy prioritization)
\(p_i\)를 구하는 2가지 variants가 있다.
-
proportional prioritization \(p_i = |\delta_i| + \epsilon\), epslion은 양의 상수로 확률이 0이 되는것을 막는다.
-
rank-based prioritization \(p_i = \frac{1}{rank(i)}\), rank는 경험 i가 replay memory에서 \(|\delta|\) 값에 따라 정렬되었을 때의 순위이다. 이때 P는 \(\alpha\)를 갖는 power-law distribution를 따르게 된다.
두 분포 모두 \(∣\delta∣\) monotonic하지만, 후자가 더 robust할 확률이 높고, outliers에 민감하지 않다.
두 분포 모두 uniform baseline보다 빠른 속도를 갖는다.
3.4 ANNEALING THE BIAS
앞서 말한 TD error의 두번째 문제점은 bias을 만든다는 것이다.
stochasitc update의 estimation은 그 update가 그들의 expectation의 estimation과 같은 분포를 따른다고 가정한 것이다. 하지만 Prioritized replay는 이 분포를 제어할 수 없는 방식으로 변경해 최종 수렴할 solution도 바뀌면서 bias가 생긴다.
이 문제를 해결하기 위해 importance-sampling weights를 사용한다.
이러한 weights는 Q-learning update에 \(\delta_i\) 대신 \(w_i\delta_i\)로 변경되어 사용될 수 있다.
그리고 안정성을 이유로 항상 weights를 \(\frac{1}{max_iw_i}\)로 normalize해 update를 downward로 확장한다.
일반적인 RL에서는 훈련 후반부(수렴 단계)에서 업데이트의 bias를 없애는 것이 중요하다. 왜냐하면 이 시점에서는 policy, state distribution, bootstrap target들이 계속 변경되기 때문에 학습 과정이 non-stationary하기 때문이다. 우리는 이 경우 작은 bias는 무시할 수 있다고 가정한다.
시간이 지남에 따라 IS 보정량을 annealing하는 유연성을 이용한다. 즉, β에 대한 스케줄을 정의하여 학습의 끝에만 β가 1이 되도록 한다. (실제로는 \(\beta_0\)에서 1까지 \(\beta\)를 linearg하게 anneal한다.)
하이퍼파라미터 \(\alpha\)와 \(\beta\)는 상호작용하며, 두 값을 동시에 증가시키면 prioritized sampling을 더욱 공격적으로 적용하면서 보정도 강하게 수행할 수 있다.
IS는 prioritized replay과 결합할 때 또 다른 이점을 제공한다. non-linear function approximation에서는, 큰 업데이트가 학습을 불안정하게 만들 수 있다.
gradient의 first-order approximation는 local에서만 신뢰할 수 있기 때문에, larget step으로의 학습은 성능이 좋지 않다.
prioritized sampling이 high TD error를 가진 경험을 더 자주 학습하도록 유도하여 IS annealing이 gradient 크기를 줄여 업데이트의 안정성을 확보한다.
그 결과, 알고리즘은 non-linear optimization landscapes를 따라가며 Taylor expansion을 지속적으로 re-approximated하여, optimization가 더 안정적이고 효과적으로 이루어진다.
PER을 RL 에이전트에 통합하여 Double DQN을 개선하였다.
주요 수정 사항은 Double DQN에서 사용되는 uniform random sampling을 논문에서 제시한 stochastic prioritization과 importance sampling 방법으로 교체한 것이다.
4. ATARI EXPERIMENTS
prioritized replay는 일반적으로 유용해서 experience replay를 활용해 문제에 특화된 하이퍼파라미터 튜닝없이도 학습을 더 효율적으로 할 수 있다고 가설을 세웠다.
이를 확인하기 위해 두가지 알고리즘을 비교한다 DQN, DDQN (tuned)
둘의 유일한 차이는 replay memory로 부터의 sampling mechanism이다.
또한 앞서 살펴본 rank-based 와 proportional priorized replay도 비교를 한다.
Nomalized score
Learning speed
왼쪽 : using maximum
오른쪽 : using mean
5. Discussion
rank-based prioritization는 outliers나 TD error의 크기에 영향을 받지 않기 때문에 더 안정적일 것이라 예상되었다. 또한, heavy-tail 특성 덕분에 sample이 다양하게 유지되며, 다양한 error 값의 그룹에서 stratified sampling을 수행하므로 학습 과정 전반에서 minibatch의 기울기 크기가 일정하게 유지될 수 있다.
반면, proportional prioritization은 TD error의 크기에 따라 sampling되므로, error 분포에 구조적 특징이 있는 경우 더 효과적일 수 있다.
그러나 실제 실험에서는 두 방식의 성능이 유사하게 나타났다. 그 이유는 DQN 알고리즘이 rewards와 TD-error를 clipping하여 이상치를 제거하기 때문으로 추측된다. 또한, 많은 transition들이 처음 replay될 때 이미 상당한 시간이 지난 후 인 경우가 많았다.
uniform sampling은 기본적으로 오래된 transition을 더 자주 선택하는 bias를 가지고 있다.
이는 오래된 transition이 이미 수십만 번의 업데이트가 적용된 정책에 의해 생성된 데이터 이기 때문이다.
그러나 prioritized replay 는 처음 본 transition에 가중치를 부여하는 방식으로 첫 번째 문제를 직접적으로 해결한다. 최근 transition은 대체로 더 큰 TD-error를 가지므로 더 자주 replay되는 경향이 있어 두 번째 문제도 자연스럽게 완화된다.
즉, 오래된 transition는 시간이 지나며 여러 번 update될 기회를 얻었고, 새로운 transition은 value function으로부터 덜 예측되기 때문에 더 큰 error를 가지는 경향이 있다.
deep NN이 prioritized replay와 다른 흥미로운 방식으로 상호작용할 것이라 가정한다.
NN의 top layers에서는 representation기반으로 value를 학습하는 과정이 진행되고, bottom layers에서는 향상된 representation을 학습하는 과정이 이루어진다고 가정했을 때,
- 이미 좋은 representation을 가진 transition은 빠르게 error가 줄어들어 replay 빈도가 감소하고,
- 안좋은 representation을 가진 transition은 더 자주 replay 되며 학습이 집중됨
결과적으로, resources가 representation이 안좋은 부분에 더 많이 투자되어, 안좋은 상태를 더 잘 구별할 수 있도록 학습이 이루어짐을 의미한다.
단, 이는 observations와 network capacity이 충분한 경우에 가능할 것이다.
6. CONCLUSION
이 논문에서는 prioritized replay라는 방법을 소개하여 experience replay을 통한 학습 효율을 향상시켰다.
여러가지 variants을 연구하고, large replay memory으로도 확장 가능한 구현 방안을 고안했으며,
그 결과 prioritized replay가 학습 속도를 2배 향상시키고, Atari 벤치마크에서 새로운 최고 성능을 달성했음을 확인했다.
댓글남기기