본문 :
Preview
Markov Decision Process (MDP)
우리는 이전 포스트에서 RL 문제를 Markov 결정 프로세스(MDP)로 정의했습니다.
또한 MDP의 transition 모델은 Markov 속성 $P(st+1|s0,a0,...,st,at) = P(st+1|st , at )$ , 즉 다음 상태 는 +1, 다시말해 현재 상태 와 그 다음 상태 에 의한 action에 의존합니다. 이는 현재 상태에 도달한 과정(이전 작업 또는 상태)는 transition 확률에 영향을 미치지 않습니다.
또 할인 계수 γ ∈ [0, 1]은 에이전트가 미래의 보상을 즉각적인 보상에 비해 얼마나 중요하게 여기는지를 담당합니다.
episode length H는 에이전트가 작업을 수행해야 하는 최대 시간 단계 수를 나타냅니다.
시간 단계 H에 도달하면 환경은 현재 상태를 다시 초기 상태로 재설정하고 전체 상호 작용 체인이 종료됩니다. 이 전체 상호 작용 체인은 일반적으로 에피소드라고 합니다. H = ∞를 선택할 수 있습니다. 이 경우 MDP를 non-episodic 이라고 합니다.
Policy
에이전트의 행동을 결정하기 위한 정책 π는 일반적으로 상태 $s$에 대한 에이전트의 행동을 정의하는 데 사용됩니다. 정책은 결정론적인 action 즉 행동을 $a = π(s)$를 주어진 상태 s에 매핑하는 결정론적 함수 π(s)이거나 조건부 π(a|s)로 정의된 확률적 함수입니다. 다시말해 내부 프로세스에 따라 확실하게 결정되는 임의의 프로세스 혹은 랜덤한 확률 분포를 따라 결정되는 어떠한 확률 변수일 수 있다는 말 입니다.
이와 같은 “함수”는 주어진 상태에서 행동이 취해질 가능성을 정의합니다.
최적의 행동을 위해서는 결정론적 정책(함수)를 할당하는 것으로 충분합니다. 하지만 알 수 없는 환경과의 상호 작용에서 최적의 행동을 학습할 때 다른 결정을 인코딩하기 위해서는 확률적 정책이 필요합니다.
예를 들어 주어진 상태에 대한 최선의 행동이 불확실한 경우 임의의 확률로 s에서 행동 1 또는 행동 2를 취할 가능성이 있는 policy를 가정 할 수 있습니다. 그리고 확률적이 결정되는 행동의 일련의 과정을 탐색이라고 합니다.
이러한 이유로 확률적 정책은 일반적으로 무작위 정책으로 시작하여 학습 과정에서 천천히 확률을 줄이는 방식으로 탐색에 사용됩니다
Partially Observable Markov Decision Process (POMDP)
이제 POMDP에 대해서 이야기 할 수 있습니다.
MDP에서는 항상 환경의 현재 상태를 온전하게 관찰할 수 있고 환경의 다음 상태는 현재 상태와 선택한 action에만 의존한다고 가정했습니다.
이 가정은 다음 작업을 계산하기 위해 현재 상태에 의해 잠재적으로 최적일 수 있는 다음 action을 위한 확률적 동작의 집합입니다.
그러나 이러한 가정은 실제 응용 프로그램에는 적용되지 않는 경우가 많습니다. 예를 들어 서버는 다수의 client의 현재 상태를 알지 못합니다. 또 edge 단말은 사용자의 현재 상태에 대한 일부 파편적 정보만을 입력받을 수 있습니다. 이러한 경우 MDP에서 발견한 reactive policy에서 observation은 Markov 속성을 갖지 않기 때문에 최적의 정책을 나타내지 못 할 수 있습니다. 때문에 POMDP는 이와 같은 파편적 정보에 대한 MDP의 확장으로 간주 할 수 있습니다.
여기서 차이라고 하면 에이전트가 관찰 가능한 공간이 축소 되었고 상태 공간 또한 축소 되었습니다.
또한 히스토리 $h_t = (o_0,a_1,...,a_t−1,o_t)$를 모든 과거의 action과 그에 따른 변화를 포함하는 벡터라고 해봅시다.
history는 각 타임스텝의 단일 관찰이 Markov 속성을 보유하지 않기 때문에 POMDP의 최적 정책을 결정하기 위해서는 과거의 동작 정보가 필요할 수 있기 때문 입니다. 예를 들어 동일한 관찰 o를 갖지만 동일한 작업 a에 대해 다른 다음 observation을 갖는 서로 다른 next state 인 두 개의 서로 다른 state s_1 및 s_2가 있을 수 있기 때문입니다.
따라서 다음 상태와 다음 관찰을 예측하려면 o와 a만 사용하는 것으로는 충분하지 않다는것을 직감적으로 알 수 있습니다.
따라서 POMDP를 해결하기 위해 POMDP를 같은 형태의 MDP(보다 계산적으로 복잡한)로 변환하는 두가지 function을 이야기 하고자 합니다. 이는 MDP 및 POMDP에 대한 최적의 정책을 얻기 위한 복잡성을 살펴보면 알 수 있습니다. 유한한 또는 무한한 horizon MDP를 푸는 것은 P-완전인 반면, 유한한 수평선 POMDP를 푸는 것은 PSPACE-hard인 것으로 증명되었습니다.
참조 :
https://www.jstor.org/stable/3689975#metadata_info_tab_contents
- Information state : 이 접근 방식에서는 전체 기록 h_t가 정보 상태라고 하는 MDP의 일종의 state로 사용됩니다. 전체 record가 Markov 속성을 충족한다는 것은 위에서 이미 언급했습니다. $P(ht+1 = (o0, a1, . )$ 즉, 모든 과거 행동과 상태의 전환이 현재 이력에 이미 있습니다. 따라서 우리는 이를 바탕으로 정보 상태 MDP를 얻을 수 있습니다. 하지만 information state space는 원래 상태 공간보다 훨씬 큽니다. 각 시간 단계(episode에서) 마다 실제와 정보의 간극이 기하급수적으로 증가하기 때문입니다.
- Belief state : 이 접근 방식에서는 실제 agent가 겪어온 환경과의 상호작용과 그 보상을 history로 사용하는 대신 충분한 통계적 history를 사용합니다. 이 history는 Belief state으로, 에이전트에게 과거 관찰 및 행동이 주어진 현재 기본 상태에 대한 에이전트의 현재 믿음을 나타냅니다: $b_t (s_t ) = p(s_t |o_1:t , a_1:t )$. 예를 들어 두 개의 개별 상태 s_0과 s_1이 있는 POMDP가 있다고 가정해봅니다. 이 때 신뢰 상태는 0과 1 사이의 1차원 벡터로 지정됩니다. 일종의 확률이라고 생각해도 무방합니다. 여기서 0은 환경이 s_0에 있고 1은 s_1에 해당한다는 믿음(확률)입니다. 0과 1 사이의 어떠한 값(확률)에 의해 0 < p < 1은 환경이 s_0에서 확률 1 - p이고 s1에서 확률 p라는 믿음을 바탕으로 action을 수행합니다. 이에 이 Belief state를 사용하여 Belief state에 기반한 보상 함수 및 전환 함수를 도출할 수 있습니다. 그러나 이 경우 추가적으로 연속 상태와 D-차원 신뢰 벡터 $(D = |S|)$가 있는 MDP가 추가적으로 정의되어야 합니다. 또한 새로운 관찰과 행동이 주어지면 현재 Belief state을 업데이트하는 방법 또한 필요합니다.
Uploaded by N2T
