The Value Function Semi-Algebraic Set in Partially Observable Markov Decision Processes

기술 요약: POMDP에서의 가치 함수 반대수 집합 (The Value Function Semi-Algebraic Set in POMDPs)

문제 정의
본 연구는 메모리리스(memoryless) 확률적 정책 하의 무한 시간 지평(infinite-horizon) 부분 관측 마르코프 결정 과정(POMDP)에서 가능한 가치 함수들의 집합이 갖는 기하학적 구조를 조사한다. 완전 관측 마르코프 결정 과정(MDP)에서의 가치 함수 기하학은 볼록 다면체(convex polytopes)의 합집합으로 특징지어지며 잘 알려져 있으나(Dadashi et al., 2019), 이에 대응하는 POMDP의 구조는 그동안 거의 탐구되지 않았다. 저자들은 부분 관측성이 어떻게 에이전트의 관점에서 비마르코프적 역학을 도입하고 결정 변수들을 결합하여, 정책 최적화의 지형을 근본적으로 변화시키는지에 대한 간극을 메우고자 한다.

방법론
저자들은 가능한 가치 함수의 집합을 정책 변수를 파라미터로 하는 벨만 방정식으로부터 유도된 파라미터 선형 시스템의 해집합으로 해석함으로써 문제에 접근한다.

1. 파라미터 선형 시스템: 벨만 방정식 $(I - \gamma P^\pi)V^\pi = r^\pi$를 정책 파라미터 $p$에 따라 계수가 선형적으로 의존하는 파라미터 시스템 $A(p)x - b(p) = 0$으로 재구성한다.
2. 구간 및 파라미터 특성 규명: 저자들은 구간 선형 시스템(Oettli & Prager, 1964)과 파라미터 시스템(Hladík, 2012)의 결과들을 활용한다. 이들은 먼저 정책 다면체를 직사각형 파라미터화로 분해함으로써 무수히 많은 피스와이즈 리니어(piecewise linear) 부등식을 이용한 특성을 확립한다(정리 3.9).
3. 반대수 축소 (Semi-Algebraic Reduction): 유한한 기술(description)을 얻기 위해, 저자들은 존토프(zonotope) 기반 조건을 적용한다. 저자들은 벡터 $x$가 가능한 가치 함수일 필요충분조건이 미드포인트 잔차 벡터(midpoint residual vector)가 파라미터화의 편차 벡터들에 의해 생성된 존토프 내에 존재하는 것임을 입증한다. 이 조건은 다항식 방정식 및 부등식 시스템으로 변환된다.
4. 명시적 구축: 저자들은 정책 파라미터와 가치 함수 제약 조건으로 구성된 행렬 $C(x)$의 랭크(rank)를 분석하여 명시적인 반대수 기술을 구축한다. 이를 통해 기초 선형 시스템의 랭크에 따라 솔루션 공간을 층화(stratification)할 수 있다.

주요 기여
본 논문은 네 가지 주요 이론적 기여를 제공한다:

• 파라미터적 해석: (PO)MDP의 가능한 가치 함수를 정책에 의해 파라미터화된 벨만 방정식의 해집합으로 프레임화하여 명시적인 기술을 가능하게 한다(섹션 3).
• 무한 피스와이즈 리니어 특성 규명: 무수히 많은 피스와이즈 리니어 부등식의 관점에서 가치 함수가 실현 가능하기 위한 필요충분조건을 제공한다(정리 3.9).
• 유한 반대수 기술: 유한한 다항식 방정식과 부등식만을 사용하여 가능한 집합의 기술을 도출하며, 해당 집합이 반대수 집합(semi-algebraic set)임을 확립한다(정리 4.2 및 코롤러리 4.3).
• 명시적 경계 구축: 제약 행렬의 랭크에 따라 층화된 POMDP 파라미터의 결정 조건(determinantal conditions)을 통해 가능한 집합의 경계를 명시적으로 구축한다(정리 4.4).

결과 및 발견

• 기하학적 복잡성: 가능한 집합이 다면체의 합집합(선형 제약)인 MDP와 달리, POMDP에서의 가능한 집합은 비선형 제약에 의해 정의되는 반대수 집합이다. 이는 곡선 형태의 경계와 더 복잡한 기하학적 구조를 초래한다.
• 초기 상태에 대한 의존성: 최적 정책이 초기 상태 분포와 무관한 MDP와 대조적으로, POMDP에서의 최적 정책은 유일하지 않을 수 있으며 초기 상태 분포에 민감하게 의존할 수 있음을 저자들은 보여준다. 이는 가능한 집합의 비볼록(non-convex)하고 곡선적인 기하학적 구조의 직접적인 결과이다.
• 지역 최적해 (Local Optima): 기하학적 특성 규명은 장기 보상의 고립된 지역 극대값(isolated local maximizers)의 출현을 드러낸다. 무작위로 생성된 POMDP에 대한 실험적 시뮬레이션은 부분 관측성이 가치 및 정책 공간 모두에서 상당한 확산을 유도하며, 여러 개의 뚜렷한 지역 최적해가 예외가 아닌 일반적인 현상임을 보여준다.
• 메모리리스 vs. 유한 메모리: 관측 강화(observation enhancement)를 통해 유한 메모리 정책으로 확장하면 가치의 확산이 감소하지만, 부분 관측성에 의해 유도되는 근본적인 기하학적 복잡성은 유지되며 이는 완전 관측 사례와 구별된다.

의의 및 주장
본 논문은 이러한 기하학적 특성 규명이 MDP와 POMDP 모두에서 정책 최적화의 지형에 대한 새로운 통찰을 제공한다고 주장한다. 구체적으로, 본 연구는:

• MDP의 알려진 다면체 결과를 훨씬 더 복잡한 부분 관측 설정으로 확장한다.
• 초기 상태 분포에 대한 최적 정책의 의존성 및 고립된 지역 극대값의 존재와 같이 부분 관측성에 고유한 질적 현상을 밝혀낸다.
• 반대수 구조가 부분 관측 환경에서의 최적화 및 학습을 이해하는 데 핵심적인 역할을 한다는 점을 시사한다.

저자들은 자신들의 결과가 주로 구조적이며 즉각적으로 효율적인 정책 최적화 알고리즘을 제공하지는 않지만, 알고리즘 설계, 수렴 보장 및 강건성 분석을 위한 향후 연구의 수학적 토대를 마련한다고 언급한다. 본 연구는 메모리리스 확률적 정책 및 할인된 무한 시간 지평으로 제한되며, 메모리 또는 벨리프 스테이트(belief-states)를 가진 정책으로의 확장이 중요한 향후 과제로 식별되었다.