ETGL-DDPG: A Deep Deterministic Policy Gradient Algorithm for Sparse Reward Continuous Control

1. 문제 정의 (Problem)

이 논문은 강화학습 (RL) 에서 희소 보상 (Sparse Reward) 환경에 적용되는 심층 결정적 정책 경사 (DDPG) 알고리즘의 한계를 해결하는 것을 목표로 합니다.

• 배경: DDPG 는 밀집 보상 (Dense Reward) 이 주어지는 연속 제어 작업에서 우수한 성능을 보이지만, 목표 상태에 도달했을 때만 보상이 주어지는 희소 보상 환경에서는 성능이 급격히 저하됩니다.
• DDPG 의 주요 결함:
  1. 방향성 없는 탐색 (Lack of Directional Exploration): 기존 $\epsilon$-greedy 또는 노이즈 기반 탐색은 시간적 추상화 (temporal abstraction) 가 부족하여 넓은 상태 공간에서 목표에 도달하기 어렵습니다.
  2. 경험 재생 버퍼의 비효율적 처리: 희소 보상 환경에서는 성공적인 전이 (rewarded transitions) 가 매우 드뭅니다. DDPG 의 균일 샘플링 전략은 이러한 귀중한 성공 경험을 충분히 활용하지 못합니다.
  3. 느린 정보 전파 (Slow Information Propagation): 성공한 에피소드에서 마지막 단계 (목표 도달) 만 보상을 받기 때문에, 보상이 초기 상태로 역전파되기까지 많은 시도가 필요합니다.

2. 방법론 (Methodology)

저자들은 DDPG 를 개선하기 위해 세 가지 핵심 전략을 통합한 ETGL-DDPG 알고리즘을 제안합니다.

가. $\epsilon_t$-greedy: 탐색을 위한 트리 검색 (Search-based Exploration)

• 개념: 기존 $\epsilon$-greedy 를 확장하여, 탐색 확률 $\epsilon$이 발생할 때 무작위 행동을 하는 대신 **트리 검색 (Tree Search)**을 통해 생성된 '옵션 (Option)'을 따릅니다.
• 구현:
  • 에이전트는 경험 재생 버퍼 (Replay Buffer) 를 사용하여 환경의 전이 함수 (Transition Function) 를 근사합니다.
  • **LSH (Locality-Sensitive Hashing)**를 사용하여 연속 상태 공간을 이산화하고, 방문 횟수 (visit counts) 를 추정합니다.
  • 검색 트리는 방문 횟수가 적은 (방문되지 않은) 영역을 향해 확장되며, 가장 방문이 적은 노드까지의 경로가 탐색 옵션으로 반환됩니다.
  • 이는 RRT(Rapidly-exploring Random Tree) 와 유사한 구조로, 장애물을 피하고 미탐색 영역을 효율적으로 탐색하도록 유도합니다.

나. GDRB: 목표 조건부 이중 경험 재생 버퍼 (Goal-conditioned Dual Replay Buffer)

• 개념: 성공 (목표 도달) 과 실패 (시간 초과) 경험을 분리하여 저장하고 적응적으로 샘플링하는 두 개의 버퍼를 사용합니다.
  • $D_\beta$ (Exploration Buffer): 모든 전이 (성공/실패 포함) 를 저장하며, Reservoir Sampling을 사용하여 오래된 데이터도 유지합니다.
  • $D_e$ (Exploitation Buffer): 성공한 에피소드 (목표 도달) 의 전이만 저장하며, FIFO 정책을 따릅니다.
• 적응적 샘플링: 학습 단계에 따라 두 버퍼에서 샘플링하는 비율을 동적으로 조정합니다. 초기에는 $D_\beta$에서 더 많이 샘플링하여 탐색을 돕고, 학습이 진행됨에 따라 성공 경험이 풍부한 $D_e$의 비중을 높여 학습 효율을 극대화합니다.

다. Longest n-step Return: 보상 전파 가속화

• 개념: DDPG 의 기본인 1-step TD 업데이트를 대신하여, 에피소드 내 모든 전이에 대해 **가장 긴 n-step 반환 (Longest n-step Return)**을 사용합니다.
• 효과:
  • 성공한 에피소드의 경우, 마지막 단계의 보상을 에피소드 내 모든 상태 - 행동 쌍에 즉시 전파합니다 (Monte Carlo 업데이트와 유사).
  • 실패한 에피소드의 경우, 마지막 상태의 Q 값을 부트스트랩 (Bootstrap) 하여 Q-value 의 과대평가 (Overestimation) 편향을 줄입니다.

3. 주요 기여 (Key Contributions)

1. $\epsilon_t$-greedy 제안: 경험 기반 트리 검색을 활용한 방향성 탐색 전략을 도입하고, MDP 의 약한 가정 하에 **다항식 샘플 복잡도 (Polynomial Sample Complexity)**를 가짐을 수학적으로 증명했습니다.
2. GDRB 프레임워크: 성공과 실패 경험을 분리하고 적응적으로 샘플링하는 새로운 이중 버퍼 구조를 설계하여 희소 보상 환경에서의 데이터 효율성을 높였습니다.
3. 성능 입증: 제안된 세 가지 기법 ($\epsilon_t$-greedy, GDRB, Longest n-step) 을 통합한 ETGL-DDPG 가 기존 DDPG 및 최신 SOTA(State-of-the-Art) 방법들 (SAC, TD3, DOIE 등) 보다 다양한 희소 보상 연속 제어 환경에서 우수한 성능을 보임을 실험을 통해 입증했습니다.

4. 실험 결과 (Results)

• 환경: 2D/3D 내비게이션 (Wall-maze, U-maze, Point-push) 및 조작 작업 (Window-open, Soccer, Button-press) 등 6 가지 희소 보상 환경.
• 성능: ETGL-DDPG 는 모든 환경에서 다른 방법들보다 **높은 성공률 (Success Rate)**을 기록했습니다. 특히 난이도가 높은 Wall-maze 환경에서는 다른 방법들이 성공률을 0 에 수렴하는 반면, ETGL-DDPG 와 DOIE 만 성공적으로 목표를 달성했습니다.
• 탐색 효율성: $\epsilon_t$-greedy 는 $\epsilon_z$-greedy 나 다른 탐색 전략보다 환경 커버리지 (Environment Coverage) 가 훨씬 높았으며, 특히 복잡한 미로 환경에서 미탐색 영역을 효과적으로 발견했습니다.
• Ablation Study: 세 가지 기법 각각이 DDPG 성능을 개별적으로 향상시켰으며, 세 가지를 결합했을 때 시너지 효과가 발생함을 확인했습니다.
• 단점: DDPG 대비 학습 시간이 약 1.5 배 증가했습니다 (주로 $\epsilon_t$-greedy 의 국소 검색 비용 때문).

5. 의의 및 결론 (Significance)

이 논문은 희소 보상 연속 제어 문제에서 DDPG 의 근본적인 한계를 해결하기 위해 방향성 탐색, 데이터 샘플링 전략, 보상 전파 메커니즘을 통합적으로 개선한 새로운 패러다임을 제시합니다.

• 이론적 기여: 탐색 알고리즘의 샘플 효율성에 대한 이론적 증명을 제공했습니다.
• 실용적 기여: 복잡한 로봇 제어 및 내비게이션 작업에서 희소 보상을 효과적으로 처리할 수 있는 강력한 알고리즘을 제시하여, 실제 응용 분야에서의 RL 적용 가능성을 높였습니다.
• 향후 과제: 현재 정적 해싱 (Static Hashing) 에 의존하는 방문 횟수 추정을 동적 해싱 (Dynamic Hashing, 예: Normalizing Flows) 으로 대체하여 이미지 기반 고차원 상태 공간으로 확장하는 것이 향후 연구 방향입니다.