Prioritized Experience Replay

Prioritized Experience Relpay

0. Abstract

▶ experience replay를 통해 online RL는 과거의 experiences를 기억하고 재사용 가능했으며, 이전 작업에서 replay transition은 replay memory에서 uniformly sampling

→ 그러나 이런 접근 방식은 중요성에 관계없이 원래 경험했던 것과 동일한 빈도로 transition을 단순히 replay

▶ 해당 논문에서는 중요한 transition을 더 자주 replay하여 더 효과적으로 학습할 수 있도록 prioritizing experience framework를 개발

→ prioritized experience replay DQN은 Atari game에서 uniform replay DQN에서의 성능을 능가

 

---

1. Introduction

(1) Experience replay in DQN

▶ online RL agent는 experience stream을 관찰하는 동안 parameters(ex. policy, value function or model)를 점진적 update

→ 가장 단순한 형태로 single update 후 들어오는 data를 즉시 삭제

▶ 첫번째, stochastic gradient-based algorithms의 i.i.d assumption을 깨는 strongly correlated updates 문제

▶ 두번째, 나중에 유용할 가능성이 있는 experience를 빠르게 잊어버리는 문제

 

▶ experience replay는 replay memory에 저장된 exeperiece로 update에 대해 더 적은 recent experience를 혼합하여 temporal corrlation를 깨는 것이 가능하게 하며, rare experience는 single update보다 많이 사용하여 위 문제를 해결

→ DQN에서 입증되었으며, experience replay를 사용하여 DNN으로 대표되는 value function의 훈련을 안정화

→ 특히 DQN는 large sliding window replay memory를 사용하여 random uniformly sampling한 결과 각 transition을 평균 8번 재방문

 

▶ 일반적으로 experience replay는 학습에 필요한 경험의 양을 줄이고 더 많은 계산과 더 많은 메모리를 대체 가능하며 이는 종종 RL agent가 환경과 interaction하는 것보다 더 저렴한 리소스임

 

(2) Prioritized experience replay 

▶ 해당 논문에서는 repaly되는 transition의 prioritization를 지정하면 uniformly random sampling되어 replay 되는 경우보다 더 효과적인지 조사

▶ 핵심 아이디어는 RL agent가 일부 transition에서 더 효과적으로 학습 가능하다는 것 

→ transition은 more or less surprising, redundant, task-relevant할 수 있음

→ transition은 agent에게 즉시 유용하지 않을 수 있지만, agent의 역량이 증가하면 그렇게 될 수 있음 

→ prioritized replay는 agent가 실제 경험한 것과 동일한 빈도로 transition을 고려하지 않도록 함 

 

▶ 특히 TD-error의 크기로 측정할 때 예상되는 학습 진행이 높은 transition을 더 자주 replay할 것을 제안

▶ 이 prioritization이 야기하는 diversity loss는 stochastic prioritization으로 완화하고 importance-sampling으로 수정하는 bias를 도입

 

---

2. Background 

▶ value interation과 같은 planning algorithm은 update의 prioritization를 적절한 순서로 지정하여 성능 향상

▶ Prioritized sweeping: update가 실행된 경우 value 변경에 따라 prioritization가 지정된 다음 update state 선택

→ TD-error는 explore할 위치 또는 선택할 feature를 선택할 때 리소스를 집중할 위치를 결정하기 위한 prioritization mechanism으로 사용

▶ 해당 논문의 접근 방식은 유사한 prioritization method를 사용하지만 model-based보다는 model-free RL 사용

▶ 또한 sample에서 function approximator를 학습할 때 더 강력한 stochastic prioritization을 사용

 

(1) Supervised learning

▶ supervised learning에는 re-sampling, under-sampling, over-sampling 기술을 포함하여 class id가 알려진 경우 non-uniform data set를 처리하는 수많은 기술들이 있으며 여기에는 ensemble method가 결합 가능

→ 최근 논문에는 experience replay가 있는 deep RL의 맥락에서 re-sampling 형식을 도입

▶ 이 method는 experience를 positive & negative reward를 위한 두 개의 버킷으로 나눈다음 각각에서 fixed 부분을 선택하여 replay

→ 이것은 positive & negative experience에 대한 자연스러운 개념이 있는 영역에만 적용 

 

---

3. Prioritized replay 

▶ replay memory를 사용하면 store할 experience와 replay할 experience의 두 가지 수준의 디자인 선택 가능

→ 해당 논문에서는 후자에 대해서만 설명 

 

3.1 Motivating example

▶ prioritization의 잠재적인 이점을 이해하기 위해 reward가 드물 때 exploration challenge를 예시하는 'Blind Cliffwalk' 환경을 사용

→ n states만 있는 환경에서는 0이 아닌 첫 번째 reward가 있을 때까지 기하급수적인 random steps가 필요

→ random action sequence가 reward로 이어질 확률은 2^(-n)

▶ most relevant(rare success) transition은 고도로 중복된 실패 사례에 숨겨져 있음 

 

Blind Cliff env

 

▶ 위 환경을 사용하여 두 agent의 학습 시간 차이를 강조

→ 두 agent 모두 동일한 replay memory에서 가져온 transition에 대해 Q-learning update를 수행

▶ 첫번째 agent는 uniformly random하게 replay

▶ 두번째 agent는 oracle를 호출하여 transition의 우선순위를 지정하여 replay 

→ oracle은 current state에서 global loss를 최대한 줄이는 transition을 greedy하게 선택 

▶ 결과적으로 transition을 좋은 순서로 선택하면 uniformly random 선택보다 기하급수적으로 속도가 빨라짐을 확인 

→ oracle은 현실적이지는 않지만, 그래프의 큰 격차는 uniformly random replay를 개선하는 실용적인 접근 방식을 찾는 동기를 부여 

 

3.2 Prioritizing with TD-error

▶ prioritized replay의 중심 구성 요소는 각 transition의 중요성을 측정하는 기준

▶ 이상적인 기준 중 하나는 RL agent가 현재 state의 transition에서 학습 할 수 있는 양(expected learning progress)

→ 해당 측정 값에 직접 접근할 수는 없지만 합리적인 proxy는 transition의 TD-error δ의 크기 

// δ: transition이 얼마나 놀랍거나 예상치 못한지를 의미 (ex.구체적으로 value가 next step bootstrap estimate에서 얼마나 멀리 떨어져 있는지)

▶ 이는 이미 TD-error를 계산하고 δ에 비례하여 parameter를 update하는 SARSA 또는 Q-learning과 같은 incremental, online RL algorithm에 특히 적합

→ TD-error는 reward가 noisy한 경우 일부 상황에서 좋지 않은 estimate일 수 있음 

 

▶ TD-error를 prioritizing replay를 지정하는 잠재적인 효율성을 입증하기 위해 Blind Cliffwalk env에서 uniform과 oracle baselines을 greedy TD-error prioritization algorithm과 비교 

▶ replay memory의 각 transition과 함께 마지막으로 발생한 TD-error를 저장

▶ absolute TD error가 가장 큰 transition이 memory에서 replay

▶ TD-error에 비례하여 weight를 update하는 Q-learning update가 이 transition에 적용

▶ 새로운 transition은 known TD-error 없이 도착하므로 모든 experience가 한 번 이상 표시되도록 보장하기 위해 이를 최대 prioritization에 적용

 

 

3.3 Stochasitc prioritization

▶ greedy TD-error prioritization에는 문제가 존재

▶ 첫번째, 전체 replay memory에 대한 비용이 많이 드는 sweep을 방지하기 위해 replay되는 transition에 대해서만 TD-error가 update

→ 첫 번째 visit 할 때 낮은 TD error가 있는 transition이 오랫동안 replay되지 않을 수 있음(즉, sliding window replay memory를 사용하지 않는다는 의미)

▶ 두번째, noise spikes(ex. reward가 stochastic할 때)에 민감하고 bootstrapping에 의해 악화되며 여기서 approximation error가 또 다른 noise source로 나타남 

▶ 세번째, greedy prioritization은 experience의 작은 subset에만 중점을 둠

→ 특히 function approximation을 사용할 때 error가 천천히 축소되며 이는 초기에 높은 error transition이 자주 replay된다는 것을 의미

 

▶ 이러한 diversity 부족으로 인해 시스템이 overfitting되기 쉬움

▶ 문제 극복을 위해 pure greedy prioritization과 uniform random sampling 사이를 보간하는 stochastic sampling method를 도입

→ sampling되는 확률은 transition의 prioritization에서 monotonic한 반면 가장 낮은 prioritization의 transition에 대해서도 0이 아닌 확률을 보장 

→ replay memory 내 prioritization는 유지하되 모든 transition에 대해 non-zero의 확률을 가지게함

▶ sampling transition probability P(i)를 다음과 같이 정의 

// p_i^a: transition i의 prioritization. a는 prioritization가 얼마나 사용되는지를 결정 ex. if a=0: uniform case

 

transition probability

 

(1) Calculating P(i)

▶ 첫번째 variant, direct proportional prioritization p_i = |δ_i| + e

// e: error가 0이면 해당 transition을 다시 visit하지 않는 것을 방지하는 작은 양의 positive constant

 

▶ 두번째 variant, indirect rank-based prioritization p_i = 1 / rank(i)

// rank(i): replay memory가 |δ_i|에 따라 정렬될 때 transition i의 rank 

→이 경우에 P(i)는 exponent a를 갖는 power-low distribution이 됨 

 

▶ 두 distribution 모두 |δ|에서 monotonic하지만 후자는 특이치에 둔감하기 때문에 더 강력할 가능성이 높음

▶ stochastic prioritization의 두가지 variant는 Cliffwalk task의 uniform baseline보다 큰 속도 향상으로 이어짐

 

 

3.4 Annealing the bias

▶ stochastic update를 통한 expectation estimate는 expectation과 동일한 distribution에 해당하는 update에 의존

▶ prioritized replay는 이 distribution을 제어할 수 없는 방식으로 변경하므로 estimate가 수렴되는 solution을 변경하기 때문에 bias를 도입(policy 및 distribution이 고정된 경우에도)

▶ B=1인 경우의 non-uniform probabilities P(i)를 완전히 보상하는 아래의 improtance-sampling(IS) weight를 사용하여 이 bias를 수정 

→ 이러한 weight는 δ_i대신 w_i δ_i를 사용하여 Q-learning update로 fold 가능(따라 일반 IS가 아닌 weighted IS임)

 

Importance Sampling weights

 

▶ 안정성을 위해 weight를 항상 1/max_i w_i로 정규화하여 update를 downward로만 확장 

 

▶ 일반적인 RL 시나리오에서 update의 unbiased 특성은 학습이 끝날 때, 수렴 근처에서 가장 중요

→ 프로세스가 policy, state distribution, bootstrap target의 변경으로 인해 매우 non-stationary하기 때문

▶ 이 맥락에서 small bias는 무시할 수 있다고 가정

→ 따라 exponent B에 schedule를 정의하여 시간이 지남에 따라 importance-sampling 수정량을 annealing하는 유연성을 이용

→ 실제로 value B는 0에서 1까지 linearly anneal하며 exponent a의 선택과 상호작용

▶ 만약 둘다 동시에 늘리면 sampling을 더 강력하게 수정하는 동시에 더 적극적으로 sampling prioritization를 지정 

 

▶ importance-sampling은 non-linear function approximation의 맥락에서 prioritized replay와 결합할 때 이점 존재

→ large learning step이 방해 요소가 되는 이유는 gradient의 first-order approximation는 local에서만 신뢰할 수 있고, 더 작은 global step-size로 방지해야하기 때문

▶ 대신 해당 논문의 접근 방식에서 prioritization은 high-error transition이 여러번 표시되도록 하는 반면, IS correction은 gradient 크기를 줄이고 algorithm이 highly non-linear optimization 곡률을 따르도록 함

→ prioritization 과정에서 transition의 high-error가 learning step을 크게 만들기도 하는데 이를 IS correction이 gradient 크기를 줄여줘 효과적으로 step의 크기를 줄여줌 

→ Taylor expansion이 지속적으로 re-approximated되기 때문 

 

---

4. Atari experiments

 

 

---

5. Discussion

▶ rank-based prioritization & proportinal prioritization 간의 일대일 비교에서 rank-based variant는 이상치나 오류 크기의 영향을 받지 않기 때문에 더 강력할 것으로 예상

▶ 또한 heavy-tail property는 sample이 다양하다는 것을 보장하고 서로 다른 오류의 파티션에서 계층화된 sampling을 통해 전체 mini batch gradient를 훈련 전반에 걸쳐 안정적인 크기로 유지