기술적 요약: 제한된 정책 클래스를 위한 정책 경향 재검토

문제 제기

표준 정책 경향 (PG) 방법은 마르코프 결정 과정 (MDP) 을 해결하는 데 널리 사용됩니다. 이론적으로 제한되지 않은 정책 클래스에서 충분한 탐색이 이루어진다면 최적 정책으로 수렴할 것이 보장되지만, 제한된 정책 클래스에서는 자주 실패합니다. 상태 집계, 분산형 다중 에이전트 시스템, 부분 관측 가능 환경 등을 포함하는 이러한 설정에서 PG 방법은 종종 비최적 임계점에 갇히게 됩니다.

저자들은 이러한 실패의 근본 원인을 표준 정책 경향 정리의 **단시성 (myopic nature)**으로 규명했습니다. 이 정리는 단일 행동 단계 이후 현재 정책으로 복귀하는 것을 기반으로 정책의 개선을 평가하는 1-단계 Q-함수에 의존합니다. 제한된 클래스에서는 이러한 "단시성"으로 인해, 클래스 내에 더 나은 정책이 존재하더라도 현재 정책에서 벗어나는 즉시의 1-단계 비용이 높아 보이는 반면, 새로운 정책의 여러 단계가 필요한 장기적 이득은 경향 계산에 반영되지 않기 때문에 경향이 개선 방향을 나타내지 않을 수 있습니다. 초기 상태 분포가 최적 정책의 지지 영역을 충분히 커버할 만큼의 탐색을 제공하지 않는다면, 완전히 관측 가능한 설정에서도 이러한 문제가 지속됩니다.

방법론

1. 상관 정책 공식화

단시성을 해결하기 위해 저자들은 정책의 재공식을 제안합니다. 확률적 정책을 직접적인 매핑 $\pi: S \to \Delta(A)$로 보는 대신, 상관 정책 $\tilde{\pi}$를 결정론적 정책 집합 $\Pi_{det}$ 위의 분포로 정의합니다.

• 제한된 클래스: 학습 과정은 사전 정의된 결정론적 정책 집합 위의 모든 분포인 $\tilde{\Pi}_{res} = \Delta(\Pi_{det})$에서 수행됩니다.
• 실행: 표준 롤아웃에서는 각 단계마다 $\tilde{\pi}$에서 결정론적 정책이 독립적으로 샘플링됩니다. 그러나 저자들은 k-단계 평가 메커니즘을 도입합니다.

2. k-단계 정책 경향

핵심 혁신은 국소 최적점을 탈출하기 위해 평가 지평을 수정하는 k-단계 정책 경향입니다.

• k-단계 가치 함수 ($J_{\tilde{\pi}, k}$): 각 단계마다 새로운 결정론적 정책을 샘플링하는 대신, 알고리즘은 결정론적 정책 $\pi_{det} \sim \tilde{\pi}$를 샘플링하고 연속적으로 k 단계를 실행한 후 재샘플링합니다.
• k-단계 Q-함수 ($Q_{\tilde{\pi}, k}$): 이 함수는 첫 k 단계 동안 특정 결정론적 정책 $\pi'_{det}$를 취한 후 $\tilde{\pi}$의 표준 k-단계 롤아웃을 수행했을 때의 회수를 평가합니다.
• 정리 5.5 (k-단계 PG 정리): $\tilde{\pi}$의 매개변수에 대한 k-단계 가치 함수의 경향은 k-단계 Q-함수를 사용하여 다음과 같이 표현됩니다:
  $$\nabla_\alpha J_{\tilde{\pi}_\alpha, k}(\mu) = \frac{1}{1-\gamma^k} \mathbb{E}_{s \sim d_{\tilde{\pi}_\alpha, k}^\mu} \left[ \mathbb{E}_{\pi_{det} \sim \tilde{\pi}_\alpha} [Q_{\tilde{\pi}_\alpha, k}(s, \pi_{det}) \nabla_\alpha \log \tilde{\pi}_\alpha(\pi_{det})] \right]$$
  k-단계 창을 통해 행동을 평가함으로써, 경향은 단기 비용이 발생할 수 있는 결정론적 정책의 장기적 이득을 "볼" 수 있게 되어 단시적 편향을 교정합니다.

3. 최적화 알고리즘

이 논문은 이 k-단계 목적 함수에 적용될 때 **투사된 경향 하강 (PGD)**과 미러 하강의 수렴성을 분석합니다. 이 분석은 벨만 완전성이나 기존 문헌에서 흔히 사용되는 경향 우세와 같은 강한 가정 없이 가치 함수의 매끄러움과 미분 가능성만 가정합니다.

주요 기여 및 결과

1. 근사 최적성의 이론적 보장

주요 이론적 기여는 k-단계 목적 함수의 모든 영 (zero) 경향 임계점과 경계 국소 최소값이 성능 측면에서 최적 결정론적 정책과 지수적으로 근접함을 증명하는 것입니다.

• 정리 6.1: 임의의 임계점 $\tilde{\pi}_{crit}$에 대해, 성능 격차는 다음을 만족합니다:
  $$\mathbb{E}_{\pi_{det} \sim \tilde{\pi}_{crit}}[J_{\pi_{det}}(\mu)] - J_{\pi^*_{det}}(\mu) \leq \frac{8\gamma^k}{1-\gamma} g_{max}$$
  k 가 증가함에 따라 이 상한은 지수적으로 좁아져 1-단계 방법을 괴롭히는 비최적 국소 최소값을 효과적으로 제거합니다.

2. 수렴 속도

저자들은 하강 알고리즘 (PGD 및 미러 하강) 이 이러한 근사 최적 해에 $O(1/T)$ 속도로 수렴함을 보여줍니다.

• 정리 6.2 및 6.3: 표준 경향 우세 조건 (제한된 클래스에서 자주 실패함) 이 부재함에도 불구하고, k-단계 평가는 근사적 경향 우세 조건을 유도합니다. 이로 인해 알고리즘은 일반적으로 매끄러운 비볼록 함수에 전형적인 느린 $O(1/\sqrt{T})$ 속도 대신, 볼록 또는 경향 우세 문제와 관련된 더 빠른 $O(1/T)$ 속도를 달성할 수 있습니다.

3. 분포 불일치 회피

중요한 발견은 이러한 상한이 분포 불일치 인자 $\|d_{\pi^*}^\mu / d_{\pi}^\mu\|_\infty$ 또는 $\|d_{\pi^*}^\mu / \mu\|_\infty$에 의존하지 않는다는 점입니다.

• 표준 PG 이론에서는 초기 분포 $\mu$가 최적 정책의 상태 점유 영역을 커버하지 않을 경우 이러한 인자가 무한대가 되어 완전히 관측 가능한 설정에서도 비최적 임계점으로 이어질 수 있습니다.
• k-단계 방법은 초기 분포의 커버리지와 관계없이 k 가 충분히 크다면 이러한 점들을 탈출할 수 있음이 입증되었습니다.

중요성 및 응용

이 논문은 이전 방법들이 실패했거나 비현실적인 가정에 의존했던 제한된 정책 클래스를 가진 복잡한 MDP 를 해결하기 위한 이론적 기초를 제공한다고 주장합니다.

• 상태 집계: 대규모 시스템에서 흔히 필요한 집계된 상태를 행동으로 매핑하는 정책에 대해 근사 최적 보장을 제공합니다.
• 다중 에이전트 시스템: 독립 에이전트, 분산 에이전트, 그룹 분산 에이전트를 가진 협력 환경에 적용됩니다. 이러한 환경은 종종 Dec-POMDP 로 모델링되며, 이는 비실용적 (NEXP-완전) 으로 알려져 있습니다. 이 논문은 이러한 설정에서 경향 기반 방법에 대한 긍정적인 이론적 결과를 제공합니다.
• 완전 관측 가능 설정: 이 작업은 완전히 관측 가능한 MDP 에서조차 열악한 탐색 (초기 상태 분포) 이 비최적 임계점을 생성할 수 있음을 강조합니다. k-단계 방법은 완벽한 초기 탐색을 요구하지 않고 이러한 점들을 탈출할 수 있는 메커니즘을 제공합니다.

결론

단시적인 1-단계 평가에서 상관된 k-단계 평가로 전환함으로써, 제안된 방법은 제한된 정책 클래스의 최적화 지형을 근본적으로 변화시킵니다. 이는 임계점이 최적 해와 지수적으로 근접함을 보장하고, 강한 실현 가능성 가정이나 완벽한 초기 탐색 없이도 표준 하강 알고리즘에 대한 빠른 수렴을 보장합니다. 이는 상태 집계 및 다중 에이전트 강화 학습의 이론적 보장과 실제 응용 사이의 간극을 메워줍니다.