On the Complexity of Robust Markov Decision Processes and Bisimulation Metrics

마르닉스 수이렌과 기예르모 A. 페레스가 집필한 논문 "On the Complexity of Robust Markov Decision Processes and Bisimulation Metrics"에 대한 상세한 기술적 요약은 다음과 같습니다.

1. 문제 정의

이 논문은 **강건한 마르코프 결정 과정 (Robust Markov Decision Processes, RMDPs)**의 계산 복잡성을 다룹니다.

• 맥락: 표준 MDP 는 전이 확률이 정확하게 알려져 있다고 가정합니다. 반면, RMDP 는 가능한 전이 함수들의 집합을 포함하는 불확실성 집합 (uncertainty set) $U$를 정의함으로써 불확실성을 모델링합니다. 목표는 $U$ 내의 최악의 경우 (worst-case) 전이 함수 하에서 기대 할인 누적 보상을 최대화하는 정책을 찾는 것입니다.
• 구체적 초점: 저자들은 불확실성 집합 $U$가 반공간 표현 (halfspace representation) (즉, $Dx \leq b$) 으로 정의된 **볼록 다면체 (convex polytope)**인 RMDP 에 집중합니다. 이는 정점 표현과 구별되며, 실제 응용에서 사용되는 표준 입력 형식입니다.
• 결정 문제: 연구된 핵심 문제는 **임계값 문제 (threshold problem)**입니다: 주어진 RMDP 와 임계값 $\kappa$에 대해, 강건 가치 $V^\pi_M(s_\iota) \geq \kappa$를 만족하는 정책 $\pi$가 존재하는가?
• 직사각형성 (Rectangularity): 논문은 불확실성 집합에 대한 두 가지 구조적 가정을 구분합니다:
  • $(s, a)$-직사각형: 불확실성은 각 상태 - 행동 쌍마다 독립적입니다. 자연 (Nature) 은 각 $(s, a)$에 대해 분포를 독립적으로 선택합니다.
  • $s$-직사각형: 불확실성은 상태별로 독립적이지만, 해당 상태 내의 행동 간에는 의존적입니다.
  • 비직사각형: 전체 시스템에 걸친 일반적인 의존성입니다.

2. 방법론

저자들은 문제 분석을 위해 강건 최적화 이론, 복잡도 이론, 그리고 논리 부호화를 혼합하여 사용합니다.

• 강건 선형 계획법 (Robust Linear Programming, RLP): $(s, a)$-직사각형 RMDP 의 경우, 저자들은 강건 선형 계획법 기법을 활용합니다. 그들은 고정된 정책을 평가하는 것이 불확실성 집합에 의해 부과된 무한한 제약 조건을 이중화 (dualizing) 함으로써 표준 선형 계획법 (LP) 문제로 변환될 수 있음을 보입니다.
• 실수 1 차 이론 (First-Order Theory of the Reals): 더 복잡한 $s$-직사각형 경우 (최적 정책이 무작위화를 필요로 할 수 있음) 에는 문제를 실수의 1 차 이론으로 부호화합니다. 이를 통해 양자 제거 기법을 사용하여 복잡도 상한을 확립할 수 있습니다.
• 환원 (Reductions): 저자들은 알려진 어려운 문제를 RMDP 임계값 문제로 환원시켜 하한을 확립합니다:
  • 패리티 게임 (Parity Games): RMDP 임계값 문제로 환원됩니다.
  • 동시성 거리 (Bisimulation Metrics): RMDP 임계값 문제로 환원되어, MDP 상태 간의 거리 계산과 RMDP 해결 사이의 이론적 연결고리를 확립합니다.
• 알고리즘적 구성: 그들은 강건 정책 반복 (Robust Policy Iteration, RPI) 알고리즘을 제안합니다. 이는 정책 평가 단계 (선형 방정식 풀이) 를 불확실성 집합에서 유도된 강건 LP 를 푸는 것으로 대체함으로써 표준 정책 반복을 확장한 것입니다.

3. 주요 기여

A. $(s, a)$-직사각형 RMDP 에 대한 복잡도 결과

• 정책 평가: 메모리 없는 결정론적 정책을 평가하는 것이 강건 선형 계획법을 통해 P(다항 시간) 에 속함을 증명했습니다.
• 임계값 문제: 결정 문제 (가치 $\geq \kappa$인 정책이 존재하는가?) 가 NP에 속함을 증명했습니다. 이는 최적성을 위해 메모리 없는 결정론적 정책을 추측하고 (이 클래스에서는 최적성을 위해 충분함) 다항 시간 내에 이를 검증함으로써 달성됩니다.
• 알고리즘적 함의: 결과적으로, 할인 인자 $\gamma$가 고정된 경우 강건 정책 반복은 $(s, a)$-직사각형 RMDP 에 대한 다항 시간 알고리즘입니다.

B. $s$-직사각형 RMDP 에 대한 복잡도 결과

• 임계값 문제: 무작위 정책이 최적일 수 있는 $s$-직사각형 RMDP 의 경우, 임계값 문제가 PSPACE에 속함을 증명했습니다. 이는 최적 무작위 정책의 존재와 최악의 경우 전이를 실수의 1 차 이론으로 부호화함으로써 유도됩니다.

C. 하한 및 난이도

• P-난이도 (P-Hardness): 문제는 표준 MDP 를 일반화하므로, 직사각형성과 볼록 불확실성 가정 하에서도 P-hard 입니다.
• 패리티 게임 연결: 저자들은 패리티 게임의 승자를 결정하는 문제가 RMDP 임계값 문제로 환원됨을 보여줍니다. 따라서 일반적인 RMDP 임계값 문제에 대한 다항 시간 알고리즘을 찾는 것은 패리티 게임을 다항 시간에 해결할 수 있는지 여부에 대한 오랜 미해결 문제를 해결하는 것과 동일합니다.
• 동시성 거리 (Bisimulation Metrics): 두 MDP 상태 간의 **동시성 거리 (bisimulation metric)**를 계산하는 것이 특별히 구성된 $(s, a)$-직사각형 RMDP 의 강건 가치 문제를 푸는 것과 동등함을 확립했습니다.

D. 실제 적용: 동시성 거리

• 논문은 강건 정책 반복이 MDP 상태 간의 동시성 거리를 계산하는 데 사용할 수 있는 실용적이고 효율적인 알고리즘임을 보여줍니다.
• 이 접근 방식은 종종 느린 표준 고정점 반복을 강건 정책 반복으로 대체하며, 거리 고정점 방정식과 RMDP 의 강건 벨만 방정식 간의 동등성을 활용합니다.

4. 결과

이론적 결과

• 복잡도 지형:
  • $(s, a)$-직사각형 RMDP: 임계값 문제 $\in$ NP.
  • $s$-직사각형 RMDP: 임계값 문제 $\in$ PSPACE.
  • 일반 RMDP: P-hard (패리티 게임을 통해).
• 동등성: 구성된 RMDP 의 최적 강건 가치는 원래 MDP 의 동시성 거리와 정확히 일치합니다.

실험적 결과

저자들은 Frozen Lake 환경 (5x5, 10x10, 20x20) 에서 강건 정책 반복 (RPI) 을 구현하고 강건 경계 값 반복 (RBVI) 과 비교했습니다.

• 성능: RPI 는 RBVI 보다 현저히 빨랐습니다.
  • 5x5 맵에서: RPI 는 22 배 더 빨랐습니다.
  • 10x10 맵에서: RPI 는 13 배 더 빨랐습니다.
• 최적성 테스트: 최적성 테스트 (RPIOT) 를 추가하면 반복 횟수와 계산 시간이 추가로 감소했습니다.
• 확장성: 20x20 맵에서 RBVI 는 시간 초과가 발생했고, RPI 는 메모리 부족으로 중단되었습니다 (RBVI 의 많은 작은 LP 와 대조적으로 매 반복마다 하나의 거대한 LP 를 풀기 때문). 이는 시간 효율성과 메모리 소비 간의 트레이드오프를 강조합니다.

5. 의의

• 이론적 발전: 이 논문은 반공간 표현의 다면체 불확실성을 가진 RMDP 의 복잡성에 관한 문헌의 공백을 메웁니다. 이는 $(s, a)$-직사각형 경우가 NP 에 속하는 반면, 일반 경우는 (패리티 게임과 연결되어) 더 어려울 가능성이 있음을 명확히 합니다.
• 알고리즘적 효율성: 특정 클래스의 RMDP 에 대해 가치 반복 대신 강건 정책 반복을 사용하는 것에 대한 엄밀한 근거를 제공하며, 고정 할인 인자에 대한 다항 시간 솔루션을 제시합니다.
• 교차 영역 영향: 동시성 거리를 RMDP와 연결함으로써, 논문은 강건 최적화 도구를 사용하여 MDP 에서 상태 거리를 계산하는 새로운 경로를 열었습니다. 이는 연구자들이 형식적 검증 및 모델 추상화 문제에 RMDP 의 풍부한 알고리즘 도구상자 (정책 반복 등) 를 적용할 수 있게 합니다.
• 미해결 문제: 이 작업은 $(s, a)$-직사각형 RMDP 의 정확한 복잡성 (P 에 속하는지 여부) 이 패리티 게임의 복잡성과 직접적으로 연결된 채로 미해결 문제임을 강조합니다.

요약하자면, 이 논문은 RMDP 에 대한 포괄적인 복잡도 분석을 제공하며, 강건 제어와 동시성 거리 간의 새로운 이론적 연결을 확립하고, 강건 정책 반복이 이러한 문제에 대해 매우 효과적인 실용적 도구임을 입증합니다.