기술 요약: 정책 경사(Policy Gradient)에서 궤적 재사용을 통한 빠른 수렴

문제 정의

정책 경사(Policy Gradient, PG) 방법론은 연속 제어 문제에 효과적이지만 샘플 효율성이 낮다는 단점이 있다. 표준적인 "바닐라" PG 알고리즘(예: REINFORCE, GPOMDP)은 오직 새로운 온-폴리시(on-policy) 데이터에만 의존하며, 이는 $\epsilon$-근사 정지점(stationary point)에 도달하기 위해 $O(\epsilon^{-2})$개의 궤적이 필요함을 의미한다. 이러한 비효율성은 그래디언트 추정치의 높은 분산에서 기인하는데, 그래디언트가 항상 새로운 샘플로부터 추정되기 때문에 이 분산이 사라지지 않기 때문이다.

과거의 데이터(오프-폴리시 궤적 또는 그래디언트)를 재사용하는 것은 효율성을 높이기 위한 일반적인 전략이지만, 기존의 이론적 연구들은 주로 그래디언트 재사용(예: SVRPG, SRVRPG, STORM-PG)에 집중해 왔으며, 최대 $O(\epsilon^{-3/2})$의 속도를 달성했다. 과거 궤적의 재사용은 직관적임에도 불구하고 엄격한 이론적 관점에서는 그동안 거의 탐구되지 않았다. 궤적을 재사용하려는 기존의 시도들은 수렴 보증이 부족하거나, 강력한 가정 및 복잡한 추정기(예: 모든 과거 정책을 저장해야 하거나 단순한 중요도 가중치 적용 시 높은 분산이 발생하는 문제)에 의존했다.

본 논문이 다루는 핵심 질문은 다음과 같다: 과거의 오프-폴리시 궤적을 재사용하는 것이 PG 방법론의 샘플 복잡도(sample complexity)를 증명 가능한 수준으로 개선할 수 있는가?

방법론

RT-PG 알고리즘

저자들은 가장 최근 $\omega$번의 반복(iteration)에서 수집된 궤적을 활용하여 정책 경사를 추정하는 새로운 알고나리즘인 **RT-PG (Reusing Trajectories – Policy Gradient)**를 제안한다. 핵심 혁신은 수정된 다중 중요도 가중치(Multiple Importance Weighting, MIW) 기법을 사용하여 온-폴리시 데이터와 오프-폴리시 데이터를 결합하는 다중 멱 평균(Multiple Power Mean, MPM) 추정기이다.

MPM 추정기

데이터 재사용 시 발생하는 통계적 문제(특히 현재의 정책 파라미터와 과거 궤적 사이의 의존성으로 인한 편향)를 해결하기 위해, MPM 추정기는 두 가지 핵심 메커니즘을 사용한다:

1. 결정론적 계수(Deterministic Coefficients): 모든 과거 정책에 의존하여 "교차 시간 편향(cross-time bias)"을 유발하는 밸런스 휴리스틱(Balance Heuristic, BH)과 달리, RT-PG는 반복 횟수와 윈도우 인덱스에만 의존하는 결정론적 계수 $\alpha_{i,k}$를 사용한다. 이를 통해 교차 시간 편향을 제거한다.
2. 멱 평균(Power Mean, PM) 보정: 중요도 가중치가 유계(bounded)가 되도록 하는 "방어적(defensive)" 특성을 확보하고, 결정론적 계수로 인해 발생하는 편향을 제어하기 위해, MPM 추정기는 바닐라 중요도 가중치에 PM 보정을 적용한다. 정책 $\pi_{\theta_i}$ 하에서 수집되어 $\pi_{\theta_k}$에서 평가된 궤적 $\tau$에 대한 수정된 가중치는 다음과 같다:
   $$\left( (1 - \lambda_{i,k}) \frac{p_{\theta_i}(\tau)}{p_{\theta_k}(\tau)} + \lambda_{i,k} \right)^{-1}$$
   여기서 $\lambda_{i,k} \in [0, 1]$는 보정 파라미터이다. 이 항은 바닐라 가중치와 1 사이의 조화 평균을 나타내며, 가중치가 $1/\lambda_{i,k}$에 의해 제한되도록 보장한다.

이론적 분석

저자들은 MPM 추정기에 대한 엄격한 유한 시간 분석(finite-time analysis)을 제공한다:

• 집중 구간(Concentration Bounds): 마팅게일(martingale)을 위한 프리드먼 부등식(Freedman's inequality)과 벡터 값 형태의 그래디언트를 처리하기 위한 커버링 아규먼트(covering argument)를 사용하여 고확률 집중 구간을 도출한다.
• 편향 제어(Bias Control): 분석에서는 두 가지 소스의 편향을 명시적으로 분리하고 제어한다:
  • 타겟 편향(Target Bias): 타겟 파라미터 $\theta_k$가 궤적의 이력(history)에 의존하기 때문에 발생한다. 이는 이력을 포함하는 파라미터 공간의 부분 집합에 대한 커버링 아규먼트를 통해 제어된다.
  • PM 편향(PM Bias): PM 보정 항에서 발생한다. 이는 배치 크기와 궤적 분포 간의 $\chi^2$-발산(divergence) 상한을 기반으로 $\lambda_{i,k}$를 신중하게 선택함으로써 관리된다.

주요 기여

1. 최초의 엄격한 증거: 본 논문은 과거의 오프-폴리시 궤적을 재사용하는 것이 PG 수렴을 유의미하게 가속화할 수 있다는 최초의 이론적 증명을 제공한다.
2. 새로운 추정기 (MPM): 유계된 중요도 가중치를 유지하면서 마지막 $\omega$번의 반복에서 얻은 오프-폴리시 궤적을 신선한 온-폴리시 데이터와 효과적으로 혼합하는 MPM 추정기를 도입하였다.
3. 개선된 샘플 복잡도:
   • 부분 재사용(Partial Reuse): 가장 최근 $\omega$번의 반복($\omega < K$)에서 궤적을 재사용할 때, RT-PG는 $\tilde{O}(\epsilon^{-2}\omega^{-1})$의 샘플 복잡도를 달성한다.
   • 전체 재사용(Full Reuse): 모든 가용 가능한 과거 궤적을 재사용할 때($\omega \ge K$), 알고리즘은 $\tilde{O}(\epsilon^{-1})$의 샘플 복잡도를 달성한다. 이는 PG 방법론에 대해 알려진 최상의 속도와 일치하며, 표준 $O(\epsilon^{-2})$ 속도보다 상당한 개선을 나타낸다.
4. 실제 구현: 정책의 비유사성(divergence)에 대한 경험적 추정치를 기반으로 오프-폴리시 데이터에 적응적으로 가중치를 부여하는 RT-PG의 실용적인 변형을 제안하여, 실제 적용 시 이론적인 전역 상한 $D$를 구할 필요가 없도록 하였다.

결과

이론적 결과

표준적인 가정(궤적 분포 간의 유계된 $\chi^2$-발산 및 정책 클래스의 정규성) 하에서, 저자들은 RT-PG가 다음을 만족하는 $\epsilon$-근사 정지점을 찾는다는 것을 증명한다:

• 전체 재사용 환경에서 $\tilde{O}(\epsilon^{-1})$ 샘플 복잡도.
• 부분 재사용 환경에서 $\tilde{O}(\epsilon^{-2}\omega^{-1})$ 샘플 복잡도.

이러 결과들은 BH 기반 방식과 달리 과거 정책을 저장할 필요 없이 과거 궤적만을 저장하면 된다는 점에서도 유효하다.

실험적 결과

Cart Pole, Half Cheetah, Swimmer와 같은 연속 제어 태스크에 대해 선형 가우시안(linear Gaussian) 및 딥 가우시안(deep Gaussian) 정책을 사용하여 실험을 수행하였다.

• 샘플 효율성: RT-PG는 샘플 효율성 측면에서 표준 온-폴리시 베이스라인(GPOMDP) 및 최신 분산 감소 방법론(SVRPG, SRVRPG, STORM-PG, DEF-PG)을 일관되게 능가하였다. Half Cheetah 환경에서 RT-PG는 대부분의 베이스라인보다 거의 두 배 높은 최종 성능을 달み하였다.
• 궤적 재사용의 영향: 윈도우 크기 $\omega$를 변화시키는 실험을 통해 궤적 재사용 윈도우를 늘릴수록 수렴이 가속화됨을 입증하였다. RT-PG는 매우 큰 윈도우에서는 수렴 효과가 점차 감소하였으나, 적절한 윈도우에서도 베이스라인들을 크게 앞질렀다.
• 단순 재사용과의 비교: RT-PG는 균등 가중치를 사용하는 MIW-PG보다 성능이 현저히 높았으며, 이는 분산을 제어하는 데 있어 PM 보정 및 적응형 가중치 방식의 유효성을 입증한다.
• 메모리 효율성: 가중치 계산을 위해 모든 과거 정책 파라미터를 저장해야 하는 BH 기반 방식과 달리, RT-PG는 과거 궤적만을 저장하면 되므로 고차원 정책 공간에서도 확장성이 높다.

의의 및 주장

본 논문은 궤적 재사용이 PG 수렴을 가속화하는 실행 가능하고 강력한 메커니즘이라는 최초의 엄격한 이론적 근거를 제공한다고 주장한다. RT-PG 알고리즘과 MPM 추정기를 도입함으로써, 저자들은 과거 데이터를 재사용하고자 하는 직관적인 아이디어와 증명 가능한 수렴 보증 사이의 간극을 메웠다.

그 의의는 다음과 같다:

1. 이론적 발전: 궤적 재사용이 $\tilde{O}(\epsilon^{-1})$ 속도를 달 Can 수 있음을 입증하였으며, 이는 강력한 가정이나 그래디언트 재사용 없이는 PG 방법론에서 달성하기 어렵다고 여겨졌던 영역이다.
2. 실용적 유용성: 궤적 재사용이 학습 안정성을 해치지 않으면서 샘플링 비용을 줄일 수 있음을 보여주어, 더 큰 배치 크기나 복잡한 분산 감소 기법이 필요한 그래디언트 재사용 방식의 실용적인 대안을 제시하였다.
3. 메모리 효율성: BH 기반 방식의 한계인 과거 정책 파라미터 저장에 따른 메모리 오버헤드 없이 개선된 속도를 달성하였다.

저자들은 결과가 궤적 분포 간의 유계된 $\chi^2$-발산 가정에 의존하며, 샘플 복잡도가 파라미터 차원 $d_\Theta$에 따라 달라진다는 점을 언급하며 겸허하게 한계를 밝혔다. 이 가정을 제거하고 차원 의존성을 없애는 것을 향후 과제로 남겼다.