기술적 요약: 결측-MDPs (miss-MDPs)

문제 정의

본 논문은 상태 특징이 동적으로 결측될 때의 불확실성 하에서 순차적 의사결정 문제를 다룹니다. 마르코프 의사결정 과정 (MDP) 은 완전 관측성을 가정하지만, 실제 세계 시나리오 (예: 불완전한 센서 데이터를 가진 의료 진단) 는 종종 결측된 특징을 포함합니다. 표준 부분 관측 마르코프 의사결정 과정 (POMDP) 은 관측 함수를 통해 이를 모델링할 수 있지만, 행동 - 관측 이력으로부터 이 함수를 학습하는 것은 일반적으로 식별 불가능하며 계산적으로 비실용적입니다.

저자들은 특정 문제 설정을 정의합니다: 알려진 기본 MDP(전이 함수 $T$) 와 알려지지 않은 결측 함수 $M$을 갖는 miss-MDP 가 주어지고, 행동 - 관측 궤적의 데이터셋이 있을 때, $\epsilon$-최적인 정책 $\pi^*$을 계산하는 것이 목표입니다. 핵심적인 어려움은 계획 수립을 가능하게 하기 위해 데이터로부터 $M$을 학습하는 데 있으며, 이는 일반적인 POMDP 에서는 불가능하지만 특정 하위 클래스에서는 잠재적으로 실현 가능한 작업입니다.

방법론

1. Miss-MDPs 의 정의

저자들은 **결측-MDPs(miss-MDPs)**를 POMDP 의 적절한 하위 클래스로 소개합니다.

• 구조: miss-MDP 는 튜플 $(S, A, T, b_0, \varrho, Z, M, \gamma)$입니다.
• 관측 공간: $Z = \times_{i \in I} (S_i \cup \{\perp\})$이며, 여기서 $\perp$는 결측된 특징을 나타냅니다.
• 결측 함수 ($M$): 특징이 관측되거나 결측될 확률을 결정하는 확률적 함수 $M: S \to \Delta(Z)$입니다.
• 결측 유형: 이 프레임워크는 고전적인 결측 데이터 분류 (Rubin, 1976) 를 채택합니다:
  • MCAR(완전 무작위 결측): 결측은 상태 값과 독립적입니다.
  • MAR(무작위 결측): 결측은 관측된 특징에만 의존합니다. 저자들은 단순 MAR(항상 관측되는 특징에만 의존) 과 일반적인 MAR 를 구분합니다.
  • MNAR(비무작위 결측): 결측은 관측되지 않은 (결측된) 특징 값에 의존합니다.

2. 학습 알고리즘 (PAC 보장)

본 논문은 데이터셋 $D$로부터 알려지지 않은 결측 함수 $\hat{M}$을 근사하기 위해 아마도 근사적으로 정확 (PAC) 한 학습 알고리즘을 제안합니다. 이 접근법은 특정 결측 유형의 식별 가능성에 의존합니다.

• 알고리즘 $A_{sMAR}$(단순 MAR 용):

  • 특징을 항상 관측되는 것 ($\hat{I}_{always}$) 과 잠재적으로 결측될 수 있는 것으로 분할합니다.
  • 항상 관측되는 특징의 값에 기반하여 결측 지표의 확률을 추정합니다.
  • 정리 1: 단순 MAR 의 경우, 데이터셋 크기가 증가함에 따라 $\hat{M}$이 높은 확률로 실제 $M$으로 수렴함을 증명합니다.

• 알고리즘 $A_{IMI}$(독립 결측 지표 용):

  • MCAR, 단순 MAR, 그리고 식별 가능한 MNAR 의 부분 집합에 적용 가능합니다.
  • 가정: (1) 특징 간 결측 지표의 독립성, (2) 자기 검열 없음 (특징의 값이 자신의 결측에 영향을 미치지 않음), (3) 양수성 (특징이 관측될 확률이 0 이 아님).
  • 다른 관측된 특징에 기반하여 각 특징에 대한 결측 확률을 독립적으로 추정합니다.
  • 정리 2: 이러한 가정 하에서 $\hat{M}$에 대한 PAC 보장을 증명합니다.

• 정책 계산:

  • $\hat{M}$이 근사되면, 저자들은 완전히 명시된 miss-MDP $\hat{P}$를 구성합니다.
  • 그들은 상용 POMDP 솔버 (예: SARSOP) 를 활용하여 $\hat{P}$에 대한 $\epsilon$-최적 정책을 계산합니다.
  • 정리 3: $\hat{M}$이 충분히 정확하다면, 결과적으로 도출된 정책이 실제 miss-MDP $P$에 대해 $\epsilon$-최적임을 증명합니다.

3. 이론적 통찰

• 무시 가능성: 저자들은 (주석 1) MAR( MCAR 포함) 의 경우, 결측 함수의 특정 확률이 베이지안 규칙에서 상쇄되므로 신뢰 업데이트(현재 상태 분포 유지) 에 대해 "무시 가능"함을 증명합니다. 그러나 함수는 여전히 정책 자체를 계산하는 데 필요하며, 이는 신뢰 간의 전이 확률이 $M$에 의존하기 때문입니다.

주요 기여

1. 형식화: 결측 데이터 이론 (MCAR, MAR, MNAR) 을 POMDP 프레임워크에 통합하여 관측 함수가 학습 가능한 실용적인 하위 클래스를 정의하는 miss-MDPs 도입.
2. 식별 가능성 분석: POMDP 관측 함수의 일반적인 비식별 가능성과 대조적으로, 결측 함수가 이력으로부터 학습 가능한 특정 조건 (단순 MAR, 자기 검열이 없는 독립적/MNAR) 식별.
3. PAC 알고리즘: 결측 함수를 학습하기 위한 공식적인 PAC 보장을 갖춘 알고리즘 ($A_{sMAR}$, $A_{IMI}$) 개발.
4. 최적성 보장: 충분한 정밀도로 $\hat{M}$을 학습하면 실제 시스템에 대한 $\epsilon$-최적 정책을 계산할 수 있음을 증명.

실험 결과

저자들은 두 가지 벤치마크에서 접근 방식을 평가했습니다:

1. ICU: 800 개의 상태를 가진 의료 의사결정 모델 (환자를 치료하는 의사).
2. Predator: 최대 1,765 개의 상태를 가진 추격 - 도주 게임 (Tag 변형).

결과:

• 근사 품질: 올바른 가정 하에서, 학습된 $\hat{M}$과 실제 $M$ 간의 총변동 (TV) 거리는 데이터셋 크기가 증가함에 따라 0 으로 수렴합니다.
• 정책 성능: 학습된 miss-MDP 에서 도출된 정책은 근사가 개선됨에 따라 최적 정책 값 ($\pi^*$) 으로 수렴합니다.
• 가정 민감성: 잘못된 가정 (예: 자기 검열이 있는 MNAR 데이터인 경우 MAR 을 가정) 은 나쁜 근사와 비최적 정책으로 이어집니다.
• 베이스라인 비교: 제안된 모델 기반 접근 방식은 두 벤치마크 모두에서 모델 없는 베이스라인 (메모리 유무의 PPO, POMCP) 보다 훨씬 뛰어났습니다. 저자들은 모델 없는 방법의 실패를 miss-MDP 의 특정 부분 관측성 구조를 효과적으로 처리하지 못했기 때문으로 돌리며, 결측이 제거되었을 때 이러한 방법들이 성공했음을 지적합니다.

중요성과 주장

본 논문은 결측 데이터 이론과 순차적 의사결정 간의 격차를 해소한다고 주장합니다. 주요 중요성은 POMDP 에서 결측 데이터를 처리하기 위한 원칙적인 모델 기반 접근법을 통계적 보장(PAC) 과 함께 제공한다는 점에 있습니다.

결측을 부수적인 것으로 간주하거나 보장이 없는 보간법에 의존하는 이전 연구와 달리, 이 작업은 다음을 수행합니다:

1. 결측 과정을 명시적으로 모델링합니다.
2. 이론적 오차 한계와 함께 데이터로부터 결측 함수를 학습합니다.
3. 학습된 모델을 활용하여 결과 정책의 근사 최적성을 보장합니다.

저자들은 겸손하게 현재 접근 방식이 기본 MDP 전이 함수가 알려져 있다고 가정한다고 지적합니다. 이 가정을 제거하고 프레임워크를 일반적인 miss-POMDP 로 확장하는 것을 향후 연구 방향으로 제시합니다. 실험 결과는 결측 메커니즘이 식별 가능한 패턴을 따르는 설정에서 제안된 접근 방식이 직접적인 POMDP 공식화 (POMCP 등) 와 딥 강화 학습 방법 (PPO 등) 보다 우수함을 확인시켜 줍니다.