[RL] PER

키워드

1. 경험 재플레이 메모리에서 샘플링할 때, 중요한 경험을 우선적으로 샘플링하여 학습 효율성을 높임. TD 오류를 기반으로 경험의 중요도를 평가.

2. "Prioritized Experience Replay"

3. PER, Prioritized Experience Replay, Stochastic prioritizaion, bias annealing

Experience Replay

  Online Reinforcement learning 에이전트를 update하는 간단한 형태는 update 후 활용한 경험(experience)를 제거하는 것이다. 이 방식의 문제는 강한 상관관계와 나중에 유용할 수 있는 희귀한 경험을 빠르게 잊는 것이다. DQN에서는 이를 해결하기위해 experience replay를 활용했으며, 성능 개선으로 문제를 해결했음을 증명하였다. 하지만 이 방식은 완전히 uniform한 샘플링 방식을 활용하였고, 이는 중요성에 관계없이 동일한 빈도로 transition을 replay 하였다.

  Prioritized Experience Replay(PER)은 이와 달리 중요한 transition을 더 자주 replay하여, 더 효율적으로 학습할 수 있는 프레임워크다. 즉, 에이전트가 특정 transition에서 더 효과적으로 학습할 수 있다는 것을 의미한다. 성능 평가를 위해 기존 모델에서 PER을 적용하였으며, 여러 모델에 대해 확장성이 뛰어나다.

  PER은 기존 experience replay 처럼 순서대로 transition을 처리하지 않아도 된다. 여기에 처리되는 빈도만 추가된 방식으로, temporal-diffrence(TD) error의 크기로 기대되는 학습 진행률이 높은 transition을 더 자주 replay한다. 다만 이 방식은 다양성의 손실로 이어질 수 있기 때문에, stochastic prioritization으로 이를 완화하고 bias를 통한 PER을 구현하였다.

Prioritized Experience Replay (PER)

  기본적으로 experience replay는 “저장할 experience”와 “replay할 experience”로 구성되어있으며, PER은 둘 중 후자에 초점을 맞춘 알고리즘이다. 즉, 저장된 memory를 효과적으로 사용하는 방법이다.

  Prioritized의 이점을 직관적으로 이해하기 위한 'Blind Cliffwalk' 예다. 빨간색 화살표는 '잘못된' 행동을 취할 때마다 에피소드가 종료되는것을 의미한다. 검은색 화살표는 ’올바른' 행동을 취하는 것으로 일련의 상태를 통과하며 진행된다. 마지막으로 녹색 화살표는 목표에 도착하여 최종 보상 1을 얻는 것이다.

  이런 환경으로 보상이 드물 때 탐색의 어려움을 이해 할 수 있다. 0이 아닌 첫 번째 보상이 나올 때까지 exponential하게 증가하는 step 수가 필요하다. 마치 2족 보행 로봇이 걷는 방법을 발견하기 전에 반복적으로 넘어지는 것처럼, “드문 성공”은 매우 많고 중복된 실패 사이에 숨겨져 있다.

  이 환경에서 두 에이전트의 Q-learning을 통한 학습 시간 차이를 비교한 결과다. 첫 번째 에이전트는 균일하게 무작위로 transition을 replay하고, 두 번째 에이전트는 오라클을 호출하여 transition의 우선 순위를 지정한다. 오라클은 현재 state에서 global loss를 최대로 줄이는 transition을 선택하는 방식이다. 이를 통해 transition을 올바른 순서로 선택하면 균일한 선택보다 exponential하게 속도를 향상시킬 수 있다. 다만 오라클은 현실적이지 않기에, 실용적인 방식이 필요하다.

TD error

  PER의 핵심 구성 요소는 각 transition의 중요성을 측정하는 기준이다. 이상적인 기준 중 하나는 에이전트가 현재 state의 transition에서 학습할 수 있는 크기다. 이를 대변할 수 있는 값은 transition의 TD error 𝛿의 크기다. 

  이 방식의 효율성을 입증하기 위해 동일한 “Blind Cliffwalk”에서 'greedy TD error prioritization' 을 평가하였다. 즉, TD error가 가장 큰 transition을 replay하며, TD error에 비례하여 가중치를 update 하였다. 특히 최신 transition은 TD error가 없으며, 모든 경험이 최소한 한 번 replay되도록 보장하기 위해 이를 우선순위 최상단으로 두었다. 결과를 통해 이 알고리즘이 기존 방식보다 효율적이라는 것을 알 수 있다.

  또한 근본적으로 uniform 샘플링의 문제는 일부는 결코 replay되지 않으며, 일부 transition은 발생한 뒤 한참 후에 처음으로 replay된다는 것이다. 이로 인해 암묵적으로 bias가 발생하게 되는데, PER을 사용하게 되면 최신 transition에는 오류가 더 큰 경향이 있기 때문에 이러한 문제를 해결할 수 있다.

728x90

Stochastic prioritization

  다만 greedy TD error prioritization은 일부 문제가 존재한다. 먼저, replay되는 transition에 대해서만 update된다. 즉, TD error가 낮은 transition이 오랫동안 replay되지 않을 수 수도 있다. 그리고 reward가 stochastic할 경우 approximation errors로 인해 bootstrapping로 더욱 악화되는 noise spike에 민감하다. 또한 function approximator를 사용할 때 오류는 천천히 줄어드는데, 이로 인해 초기에 높은 오류를 보이는 transition이 자주 replay되고 다양성 부족으로 시스템이 overfitting된다.

  이러한 문제를 극복하기 위해 greedy 방식과 uniform 방식을 절충한 stochastic sampling 방법을 고안하였다. 이는 샘플링될 확률이 우선순위를 따르는 동시에 가장 낮은 순위의 transition에 대해서도 샘플링될 확률이 0이 아니도록 보장하는 것이다. 이에 대한 샘플링 transition 확률 𝑖는 아래와 같다.

  여기서 𝛼는 prioritization이 사용되는 비율을 결정하는 하이퍼파라미터다. 이 확률을 두 가지 버전으로 변형할 수 있다. 첫 번째 버전 은 𝑝𝑖=|𝛿𝑖|+𝜖로 직접적인 proportional prioritization이며, 두 번째 버전 은 𝑝𝑖=1/rank⁡(𝑖)로 간접적인 rank-based prioritization이다. 여기서 rank⁡(𝑖)는 replay 메모리가 |𝛿𝑖|에 따라 정렬될 때 transition 𝑖의 순위를 의미한다. 두 분포 모두 |𝛿|에서는 단조롭지만(monotonic), 후자가 outlier에 민감하지 않기 때문에 더 robust할 가능성이 있다. 아래 결과 처럼 두 변형 모두 uniform보다 속도가 향상되는 것을 알 수 있다.

Bias annealing

  Stochastic prioritization을 사용한 estimation은 expected value와 동일한 분포로 업데이트된다. 하지만 PER은 이 분포를 통제하지 않아 계속 변경되게되고, 그에 따라 추정치가 수렴할 솔루션이 변경되기 때문에 bias를 발생한다. Importance -Sampling(IS) weight는 이러한 편향을 수정한다.

  이는 𝛿𝑖 대신 𝑤𝑖​𝛿𝑖을 사용하여 Q-learning에 사용되며, 안정성을 위해 1/max𝑖⁡𝑤𝑖로 normalize하여 update 크기를 작아지는 방향으로만 조정한다. 지수 𝛽는 학습 종료 시에만 1에 도달하도록 schedule을 세워 시간에 따른 IS를 수정한다. 예시로 초기 값 𝛽0에서 1로 선형적으로 어닐링할 수 있다. 만약 𝛽=1인 경우 non-uniform한 확률 𝑃​(𝑖)는 완전히 보정된다.

  이 하이퍼파라미터를 이전 𝛼와 함께 고려하는 경우, 둘을 동시에 높이면 샘플링의 우선 순위가 더 적극적으로 지정되는 동시에 더 강력하게 수정된다. 즉, 𝛼는 오류가 높은 transition이 여러 번 표시되도록 하고 𝛽는 기울기 크기를 줄여, 최종적으로 알고리즘이 고도로 비선형적인 최적화 곡률을 따르도록 유도한다.

결과

  Baseline과 동일 모델에 PER을 적용했을때의 결과다. Baseline과 주요 차이점은 replay mechanism이며, baseline의 uniform과 PER의 rank-based, proportional 두 가지 버전을 비교했다. DQN에 PER을 추가하면 49개 게임 중 41개 게임에서 점수가 크게 향상되었으며, normalized된 평균 성능이 48%에서 106%로 증가하였다. Double DQN에서도 평균 성능은 111%에서 128%로 증가했다.

  Double DQN (tuned) 알고리즘에 PER을 적용한 모델의 개별  게임에 대한 성능 결과다. 일부 게임에서 처음으로 사람 수준으로 끌어올렸다. 또한 두 가지 버전 중 하나의 버전은 baseline과 동일하고 하나의 버전만 향상되는 게임도 있다.

  위 그래프는 100% 성능에 달성할때까지 소요된 학습 수를 비교한 자료다. PER을 적용하면 전체적으로 학습 속도가 두 배 수준으로 빨라진다는 것을 알 수 있다. 또한 특히 보상에 지연이 발생하는 게임에서 성능이 본격화될 때까지 시간 지연을 탁월하게 줄이는 점도 확인 할 수 있다.

Reference

논문 링크 : https://arxiv.org/abs/1511.05952