기술 요약: 자연 정책 경향을 이중 평활화 정책 반복으로 간주

문제 제기

강화 학습 (RL) 문제는 일반적으로 마르코프 결정 과정 (MDP) 으로 모델링됩니다. 정책 반복 (PI) 과 가치 반복 (VI) 과 같은 고전적인 동적 프로그래밍 방법은 벨만 연산자의 수축 (contraction) 과 단조성 (monotonicity) 속성에 의존하는 반면, 자연 정책 경향 (NPG) 과 정책 이중 평균 (PDA) 과 같은 현대적인 경향 기반 방법들은 주로 정책 공간에 대한 연속 최적화의 관점에서 분석됩니다.

문헌에는 개념적 격차가 존재합니다: NPG 에 대한 분석들은 종종 고전적 방법들의 강력한 수렴 보장을 뒷받침하는 근본적인 $\ell_\infty$-노름 수축을 활용하지 못합니다. 그 결과, NPG 에 대한 기존 이론적 결과들은 하나 이상의 한계를 겪는 경우가 많습니다:

1. 전역 기하학적 수렴의 부재.
2. 초기 상태 분포나 집중도 계수 (concentrability coefficients) 에 대한 의존성.
3. MDP 나 알고리즘에 추가적인 정규화를 요구하여 곡률을 유도해야 함.
4. 적응형이며 궤적에 의존하는 스텝 사이즈에 대한 의존성.

본 논문은 MDP 를 수정하거나 적응형 스텝을 요구하지 않고 분포 무관한 기하학적 수렴 분석을 가능하게 하는 고전적 PI 와 현대적 경향 기반 방법을 연결하는 통합 프레임워크를 제공함으로써 이 격차를 해소하는 것을 목표로 합니다.

방법론: 이중 평활화 정책 반복 (DSPI)

저자들은 벨만 연산자 프레임워크로 공식화된 통합 알고리즘 프레임워크인 **이중 평활화 정책 반복 (DSPI)**을 소개합니다. DSPI 는 과거 Q-함수들의 가중 평균에 적용된 정규화된 탐욕적 (greedy) 단계를 통해 정책을 업데이트합니다.

DSPI 의 핵심은 두 가지 수준의 평활화를 포함합니다:

1. 평균 평활화: 가장 최근의 Q-함수만 사용하는 대신, 알고리즘은 모든 과거 Q-함수들의 이동 평균 ($\bar{Q}_k$) 을 유지합니다.
2. 정규화 평활화: 탐욕적 정책 업데이트는 엔트로피와 같은 오목 함수 $\nu(\cdot)$를 포함하는 정규화된 단계 (예: 소프트맥스) 로 대체됩니다.

업데이트 규칙은 다음과 같이 정의됩니다:
$$\pi_{k+1}(s) \in \arg\max_{\mu \in \Delta(A)} \left\{ \mu^\top \bar{Q}_{k+1}(s) + \eta_k \nu(\mu) \right\}$$
여기서 $\bar{Q}_{k+1} = (1-\beta_k)\bar{Q}_k + \beta_k Q_{\pi_k}$이며, 평활화 파라미터 $\eta_k$는 스텝 사이즈 $\beta_k$에 기반하여 기하학적으로 감소합니다.

중요하게도, 저자들은 DSPI 가 평활화된 벨만 연산자 ($H_\eta$ 및 $H^\pi_\eta$) 를 사용하여 간결한 공식화를 허용함을 보여줍니다. 이를 통해 알고리즘은 최적화 이론적 도구에만 의존하는 것이 아니라, 이러한 연산자들의 단조성과 수축 속성을 사용하여 분석될 수 있습니다.

주요 기여

1. 알고리즘의 통합

본 논문은 DSPI 가 여러 주요 알고리즘을 특수한 경우로 포함하는 일반적 프레임워크임을 입증합니다:

• 정책 반복 (PI): 스텝 사이즈 $\beta_k \equiv 1$ (평균화 없음) 일 때 정규화가 사라지면 회복됩니다.
• 자연 정책 경향 (NPG): $\nu(\cdot)$를 Shannon 엔트로피로 설정하고 특정 스텝 사이즈 스케줄을 선택함으로써 회복됩니다.
• 정책 이중 평균 (PDA): $\nu(\cdot)$를 이동된 음의 발산 생성 함수로 선택함으로써 회복됩니다.
• 이중 평균화 정책 반복: 정책이 평균화된 Q-함수 ($\nu(\cdot) \equiv 0$) 를 기반으로 탐욕적으로 업데이트되는 새로운 변형입니다.

2. 통합 수렴 분석

평활화된 벨만 연산자의 속성을 활용함으로써, 저자들은 DSPI 에 대한 통합 수렴 분석을 제공합니다:

• 점근적 수렴: 총합이 발산하는 임의의 스텝 사이즈 시퀀스에 대해 증명되었습니다.
• 전역 기하학적 수렴: 상수 스텝 사이즈에 대해 증명되었습니다. 오차 한계는 다음과 같습니다:
  $$\|V^* - V^{\pi_k}\|_\infty \leq (1 - (1-\gamma)\beta)^{k-1} (\gamma \|V^* - V^{\pi_0}\|_\infty + \tau \nu_{\max})$$
  여기서 $\gamma$는 할인 인자이고 $\beta$는 상수 스텝 사이즈입니다.

3. NPG 및 PDA 에 대한 개선된 이론적 보장

DSPI 프레임워크를 NPG 와 PDA 에 적용하면 다음과 같은 결과가 도출되며, 이는 제한적인 가정 없이 최첨단 수준을 개선하거나 일치시킵니다:

• 분포 무관성: 수렴 한계는 초기 상태 분포나 집중도 계수가 아닌 가치 함수 간격의 $\ell_\infty$-노름에만 의존합니다.
• 추가 정규화 불필요: 분석은 표준 NPG 에 내재된 엔트로피 항을 제외하고 MDP 를 수정하거나 추가 정규화 항을 추가하지 않고도 성립합니다.
• 간단한 스텝 사이즈: 결과는 정책 궤적이나 벨만 오차에 의존하는 적응형 스텝 사이즈가 아닌, 사전 지정된 기하학적으로 증가하는 스텝 사이즈 스케줄 ($\alpha_k = \beta \alpha_0 / (1-\beta)^k$) 에 대해 성립합니다.
• 반복 복잡도: NPG 와 PDA 는 $O((1-\gamma)^{-1} \log((1-\gamma)^{-1}\epsilon^{-1}))$번의 반복 내에서 $\epsilon$-최적 정책을 달성합니다.

4. 이중 평균화 PI 의 유한 종료

정규화되지 않은 경우 (이중 평균화 PI) 에 대해, 저자들은 유한 종료를 증명합니다. 알고리즘은 상태 공간과 행동 공간의 크기가 각각 $n$과 $m$일 때, 최대 $O(mn(1-\gamma)^{-1} \log((1-\gamma)^{-1}))$번의 반복 내에서 최적 정책을 찾습니다. 이는 알고리즘이 $k^*$번의 반복마다 적어도 하나의 비최적 행동을 제거함을 보여줌으로써 달성됩니다.

5. 확장

프레임워크는 자연스럽게 다음으로 확장됨이 입증되었습니다:

• 선형 함수 근사: 선형 함수 근사를 적용한 DSPI 는 함수 근사 오차 항까지 기하학적 수렴을 달성합니다.
• 확률적 최단 경로 (SSP) 문제: 분석은 할인되지 않은 SSP 문제로 확장되어, 모든 정상 정책이 적절하다는 가정 하에 분포 무관한 전역 기하학적 수렴을 확립합니다.

결과 및 의의

본 논문은 고전적 동적 프로그래밍과 현대적 경향 기반 RL 을 연결하는 통합적 관점을 제공한다는 점에서 주요 의의가 있다고 주장합니다. NPG 와 PDA 를 정책 반복의 평활화 및 평균화 변형으로 해석함으로써, 저자들은 다음과 같은 성과를 거둘 수 있었습니다:

1. 강력한 보장 회복: 벨만 연산자의 고유한 속성 (단조성과 수축) 만을 사용하여 NPG 와 PDA 에 대한 전역 기하학적 수렴을 확립합니다.
2. 인공물 제거: 이전의 최적화 기반 분석에서 종종 요구되었던 "곡률 유도" 정규화나 적응형 스텝 사이즈의 필요성을 제거합니다.
3. 분석 단순화: 분포 불일치 계수의 복잡성을 피하는 더 간결하고 원칙적인 분석을 제공합니다.

저자들은 현재 분석이 정확한 Q-함수에 대한 접근을 가정하여 (정책 개선 역학을 격리함) 수행되었으나, 이 프레임워크는 Q-함수를 추정해야 하는 모델 없는 설정에서의 향후 연구를 위한 토대를 마련했다고 지적합니다. 그들은 유한 시간 정책 평가 보장과 DSPI 의 결합을 모델 없는 RL 에 대한 날카로운 샘플 복잡도 결과를 달성하기 위한 중요한 다음 단계로 식별합니다.