Strongly Polynomial Time Complexity of Policy Iteration for $L_\infty$ Robust MDPs

기술 요약: $L_\infty$ 강건 MDP에 대한 정책 반복의 강한 다항 시간 복잡도

문제 정의
본 논문은 불확실성 하의 순차적 의사결정 분야의 근본적인 미해결 과제인, 고정된 할인 인자(discount factor)를 가진 $L_\infty$ 불확실성 집합을 갖는 강건 마르코프 결정 과정(Robust Markov Decision Processes, RMDPs)에 대한 강한 다항 시간 알고리즘의 존재 여부를 다룬다. 고전적인 MDP는 정확한 가치 계산을 위해 강한 다항 시간 알고리즘을 허용하며(Ye, 2011), RMDP의 경우 선형 계획법(LP)을 통해 다항 시간 알고리즘이 존재하지만, RMDP가 강한 다항 시간 알고리즘(입력 계수의 비트 길이에 독립적인 산술 연산 횟수를 갖는 알고리즘)을 허용하는지에 대한 문제는 해결되지 않은 채 남아 있었다. 구체적으로, $(s, a)$-직사각형 RMDP를 턴 기반 확률 게임(turn-based stochastic games)으로 환원하려는 이전의 시도들은 $L_\infty$ 불확실성 다포체(polytope)를 표현하기 위해 필요한 행동의 수가 기하급수적으로 증가하여 다항 시간 환원에 실패하였다.

모델 및 정의
저자들은 $(s, a)$-직사각형 RMDP와 $L_\infty$ 불확실성 집합에 초점을 맞춘다.

• $(s, a)$-직사각형성: 환경은 각 상태-행동 쌍에 대해 독립적으로 전이 확률을 선택하며, 이는 동적 계획법 구조를 보존한다.
• $L_\infty$ 불확실성: 각 상태-행동 쌍 $(s, a)$에 대해, 실제 전이 벡터는 명목 추정치 $\hat{P}_{s,a}$ 주변의 $L_\infty$ 구(ball) 내에 존재한다.
• 목표: 에이전트는 적대적인 환경 정책 $\tau$에 맞서 최악의 기대 할인 비용을 최소화하는 정책 $\sigma$를 찾는다.
• 강한 다항 시간(Strongly Polynomial Time): 알고리즘이 강한 다항 시간이라는 것은, 산술 연산의 횟수가 변수와 제약 조건의 다항식으로 제한되며, 계산 중 숫자의 크기가 입력 계수의 비트 길이에 관계없이 입력 크기에 대한 다항식인 경우를 의미한다.

방법론
본 논문은 정책 평가(Policy Evaluation)와 정책 개선(Policy Improvement)을 교대로 수행하는 강건 정책 반복(Robust Policy Iteration, PI) 알고리즘을 분석한다.

1. 강건 마르코프 체인(Robust Markov Chains, RMCs): 저자들은 먼저 더 단순한 경우인 (단일 행동을 갖는) RMC-PI를 분석한다.

   • 정책 개선: 비트 정밀도에 의존하는 선형 계획법(LP)을 푸는 대신, 저자들은 최적의 환경 응답을 계산하기 위해 호모토피 알고리즘(Homotopy Algorithm, Behzadian et al., 2021)을 활용한다. 이 알고리즘은 $O(n \log n)$에 실행되며, 특정 구조적 특성을 가진 정책을 생성한다: 즉, 경계(0, 1, 또는 불확실성 반경)에 도달할 때까지 "기여자(donor)" 상태에서 "수혜자(receiver)" 상태로 질량(mass)을 이동시켜 전이 확률을 조정한다.
   • 잠재 함수(Potential Function): 호모토피 알고리즘에 의해 허용되는 확률 질량 이동을 추적하기 위해 새로운 잠재 함수 $f_\tau(s, s', s'')$가 도입된다. 이 함수는 낮은 최적 가치를 가진 상태에서 높은 최적 가치를 가진 상태로 질량을 이동시킴으로써 얻을 수 있는 가치의 잠재적 개선량을 측정한다.
   • 조합적 경계: 저자들은 현재 정책의 전이 확률과 최적 전이 확률 사이의 "편차(discrepancy)"가 기하급수적으로 감소함을 증명한다. 결정적으로, 저자들은 실수들의 부호 있는 부분 집합 합(signed subset sums)에서 가장 중요한 비트(Most Significant Bits, MSBs)의 개수에 관한 조합적 보조정리(Lemma 8)를 확립한다. 더 일반적인 정리(Theorem 20/21)로부터 유도된 이 보lemma는 MSB의 개수를 $O(|X| \log |X|)$로 제한한다.
   • 수렴 논증: 가치 오차의 기하급수적 수축(Lemma 2)과 편차의 가능한 MSB의 유한한 개수(Lemma 8)를 결합함으로써, 저자들은 알고리즘이 임의로 작은 업데이트를 무한히 반복할 수 없음을 보여준다. 즉, 편차의 MSB는 다항식 횟수만큼만 변할 수 있다.

2. 강건 MDP (RMDPs): 분석은 일반적인 RMDP 케이스인 RMDP-PI로 확장된다.

   • 알고리즘은 현재 에이전트 정책에 대한 RMC 하위 문제를 반복적으로 해결하여 최악의 환경 응답을 찾은 다음, 결과적으로 발생하는 비용을 최소화하도록 에이전트 정책을 업데이트한다.
   • 행동에 대한 유사한 잠재 함수가 정의되어, 최적의 에이전트 행동으로부터 벗어나는 데 드는 비용을 추적한다.
   • 동일한 논리가 적용된다: 최대 잠재력을 가진 행동은 가치 오차의 수축이 변화를 강제하기 전까지 로그 횟수 이상의 반복 동안 지속될 수 없다.

주요 기여 및 결과

• 강한 다항 시간 RMC-PI: 저자들은 $n$개의 상태와 상수 할인 인자 $\gamma$를 갖는 RMC에 대한 강건 정책 반복이 $O(n^4 \log n \cdot \frac{\log((1-\gamma)/n^2)}{\log \gamma})$ 회의 반복 내에 종료됨을 증명한다. 각 반복은 다항 시간 연산(행렬 역행렬 및 호모토피 단계)을 포함하므로, 총 실행 시간은 강한 다항 시간이다.
• 강한 다항 시간 RMDP-PI: 이 결과는 $n$개의 상태와 $m$개의 행동을 갖는 일반적인 RMDP로 일반화된다. 알고리즘은 $O(n \cdot m \cdot \frac{\log(1-\gamma)}{\log \gamma})$ 회의 반복 내에 종료되며, 이는 RMDP-PI 역시 강한 다항 시간임을 입증한다.
• 조합적 보조정리: 본 논문은 부호 있는 부분 집합 합에서의 서로 다른 MSB의 개수를 제한하는 새로운 조합적 결과인 Lemma 8을 도입한다. 저자들은 이 정리의 더 강력한 버전이 AI 연구 에이전트(Aletheia)에 의해 독립적으로 도출되었음을 언급하며, 수학에 대한 AI의 기여를 강조한다.

의의 및 주장
본 논문은 강건 최적화 이론의 주요 미해결 과제를 해결했다고 주장한다. $(s, a)$-직사각형 $L_\infty$ RMDP에 대해 강건 정책 반복 알고리즘이 강한 다항 시간에 실행됨을 보여줌으로써, 저자들은 Ye(2011)의 고전적 MDP에 대한 기념비적인 결과를 강건한 설정으로 일반화한다. 이 결과는 다음과 같은 이유로 중요하다:

1. 입력 파라미터의 비트 길이에 의존하지 않고 정확한 값(근사치가 아닌)을 계산하기 위한 이론적 보장을 제공한다.
2. 행동의 수가 기하급수적으로 증가하여 실패했던 이전의 환원 기법들의 한계를 극복한다.
3. 무한한 불확실성 집합에도 불구하고, 호모토피 알고리즘의 조합적 특성을 사용하여 강건 벨만 연산자(robust Bellman operator)를 효율적으로 탐색할 수 있음을 입증한다.

저자들은 이론적 토대가 이제 확립되었으나, 향후 연구에서 데이터 기반 불확실성 집합에 대한 경험적 연구와 이러한 잠재력 기반 논증이 개선된 실용적 변형이나 정지 기준(stopping criteria)으로 이어질 수 있는지 탐구할 수 있다고 결론짓는다. 또한, 표준 MDP 정책 반복 변형들에 대한 다항 시간 경계 문제도 여전히 열려 있음을 언급한다.