Partially Observable Markov Decision Process(POMDP)

Summary

$S$(State)가 partially observable하다.
즉, 현재 상태가 어떠한 건지 정확히 파악할 수 없다.

Chess vs Poker

MDP(Chess)

체스처럼 상대방과 나의 기물 위치를 파악할 수 있고, 그 정보만으로 state가 정의되니, fully-observable하다고 할 수 있다. 즉, MDP

Poker(POMDP)

포커처럼 상대방의 패를 알 수 없는 경우, 현재 상태($S$)를 정확히 정의할 수 없으므로 partially observable.

Definition

POMDP는 기존의 Markov Decision Process(MDP)에 2개의 component를 추가하여 정의한다.

$(S,A,P,R,\gamma ,\Omega ,O)$

• $S$(State): 에이전트가 존재할 수 있는 모든 상태의 집합

• $A$(Action): 에이전트가 특정 상태에서 취할 수 있는 모든 행동의 집합

• $P$(Transition Probability): 에이전트가 상태 $s$에서 행동 $a$를 했을 때, 다음 상태 $s^{\prime }$로 이동할 확률. 마르코프 체인과 마찬가지로 오직 현재 상태와 현재 행동에만 의존.
  $P(s^{\prime }\mid s,a)=\mathbb{P}(S_{t+1}=s^{\prime }\mid S_t=s,A_t=a)$

• $R$(Reward Function): 에이전트가 상태 $s$에서 행동 $a$를 하여 $s^{\prime }$로 갔을 때 받는 즉각적인 보상의 기댓값. 에이전트가 어떤 행동이 좋은 행동인지 판단하는 기준이 됨.
  $R(s,a,s^{\prime })=\mathbb{E}[R_{t+1}\mid S_t=s,A_t=a,S_{t+1}=s^{\prime }]$

• $\gamma$(Discount Factor): $0$과 $1$ 사이의 값($0\le \gamma \le 1$)으로, 미래에 받을 보상을 현재 가치로 환산할 때 사용. 1에 가까울수록 먼 미래의 보상을 중요하게 생각하고, 0에 가까울수록 당장 눈앞의 보상을 중요하게 생각

• $\Omega$(Observation Space) : 에이전트가 환경으로부터 받을 수 있는 모든 관측치($o$)의 집합입니다.

• $O$(Observation Function) : 에이전트가 어떤 행동($a$)을 해서 새로운 상태($s^{\prime }$)에 도달했을 때, 특정 관측치($o$)를 보게 될 확률입니다.
  $O(o\mid s^{\prime },a)=\mathbb{P}(O_{t+1}=o\mid S_{t+1}=s^{\prime },A_t=a)$

Solution : Belief State

MDP에서는 에이전트가 “현재 상태 $S_t$가 이거니까 행동 $A_t$를 해야지”라고 정책 $\pi (a\mid s)$를 세웠습니다. 하지만 POMDP에서는 진짜 상태를 모르니 이 방식이 불가능합니다.

대신 에이전트는 과거부터 지금까지 모은 관측치와 행동의 기록(History)을 바탕으로, **“현재 환경의 진짜 상태가 무엇일지에 대한 확률 분포”**를 만듭니다. 이를 **믿음 상태(Belief State, $b$)**라고 부릅니다.

$b_t(s)=\mathbb{P}(S_t=s\mid o_1,a_1,\dots ,a_{t-1},o_t)$

즉, 에이전트는 “지금 상태가 1번 상태일 확률 70%, 2번 상태일 확률 30%야”라는 스스로의 인지적 믿음을 바탕으로 다음 행동을 결정하게 됩니다. 결국 POMDP를 푼다는 것은, 새로운 관측치가 들어올 때마다 이 베이즈 정리(Bayes’ Rule)를 활용해 자신의 믿음 상태($b$)를 계속 업데이트해 나가는 과정이 추가되는 것입니다.