💪🏻

POMDP

생성일

2025/04/02 13:10

태그

강화학습

작성자

Partially Observable Markov Decision Process (POMDP)

1. POMDP’s State transition = (S, A, O, T, Z, R)

•

State & Action & Reward

→ MDP와 동일하다.

•

State Transition Probability

→ MDP와 동일하며,

T(s,a,s’) = P(s’|s,a)

로 상태 전이 확률을 표현한다.

•

Observation

→ Agent가 action을 선택하여 다음 state로 전이한 후에 Observation을 통해 현재 state에 대한 단서를 얻는다.

Z(s’, a, o) = P(o|s,a)

로 표현된다.

•

Observation Probability

→ Observation set의 각 원소를 관찰하게 될 확률을 의미한다.

•

요약 : MDP에서는 상태가 완전히 관찰 가능한 반면, POMDP에서는 상태가 부분적으로만 관찰 가능하다. 즉, 에이전트는 완전한 상태 정보를 갖지 않고, 관찰을 통해 간접적으로 상태를 추론해야 한다. 

2. Planning

state가 부분적으로만 관측 가능하므로, Agent는 상태에 대한 확률 분포인 Belief b를 사용한다. 이때 Belief b의 의미는 ”에이전트가 각 상태에 대해 가지고 있는 확률 분포”이다. 즉 각 상태가 현재 상태일 가능성을 나타내는 것이다. 이때 Belief b′(s′)는 이전의 Belief 과 새로운 observation을 바탕으로 update된다.

1) Initial state

→ Agent가 초기화된 belief 상태를 가지고 있다.

2) action 선택

→ Agent는 현재 belief를 기반으로 Action 선택

→ 현재 state에 대한 확률적 추정을 바탕으로 Action 선택

3) State transition

→ Agent가 다음 state

s_{t+1}

로 전이

4) get obsevation

→ 새로운 state

s_{t+1}

에서 는 observation

o_{t+1}

를 획득

5) belief state update

b'(s') = \frac{P(o|s',a)\sum_{s\in S} P(s'|s,a)b(s)}{P(o|a,b)}

→ 베이지안 법칙을 통해 전개되는 수식으로 위의 식이 유도되는 과정은 아래와 같다.

6) get reward

→ Agent는 State transition과 observation 을 통해 reward 획득

3. 한계점

MDP에서 현실적으로 모든 state spcae를 알 수 없기 때문에, POMDP를 도입한 것인데 그럼에도 불구하고 POMDP 실제 사용에 어려움이 있다. 예를 들면 Large State Space, Long Planning Horizon, Large Observation Space, Large Action Space가 있다.

•

 Long Planning Horizon: agent가 목표를 달성하기 위해 여러 단계의 계획을 세워야 할 때, 각 단계의 잠재적 결과 수가 기하급수적으로 증가하는 현상.

→ 위 수식에서 알 수 있지만, observation space랑 belief probability를 계속 계산해야 하여 매 state space가 바뀔 때마다 무수한 연산이 생긴다.

4. 해결방법

샘플링 기반 근사

•

PBVI (Point-Based Value Iteration):  대표적인 belief 집합을 샘플링하고, 그 샘플된 belief에서만 가치 함수를 계산하여 문제의 복잡성을 줄인다.

•

HSVI (Heuristic Search Value Iteration): Heuristic 기법을 사용하여 검색 공간을 줄이고 빠르게 좋은 정책을 찾는다.

Intrinsic Motivation and Intrinsic Rewards

강화학습에서는 reward가 매우 sparse하다는 사실을 알 수 있다.

“reward가 sparse하다” 라는 건 에이전트가 학습 과정에서 보상을 받는 빈도가 매우 낮다는 것을 말한다.

예를 들면, 여기서 마리오가 어떤 보상을 받기 위해 다양한 action을 한다고 했을 때 만약 주어진 177초동안 아무런 reward를 받지 못했다면 학습 시간이 너무 오래걸린다. 때문에 sparse reward 인 경우, 적당한 reward 를 받을 수가 없어 학습이 전혀 되지 않는다. 이러한 sparse reward 문제를 해결하기 위해 ε-greedy, UCB, HER 등이 있다.

1. UCB

•

존재하는 행동의 선택지 중에서, 가장 높은 upper bound를 가진 행동을 선택

점선에 가까울 수록 높은 reward를 받을 확률이 높다고 했을 때, 무난한 선택은 2번인 것을 확인 할 수 있다. 높은 reward를 지속적으로 받을 수 있기 때문이다.

먼저 가장 높은 action value인 𝑄𝑡(𝑎)를 선택하고, 여기에 오른쪽 항인 upper bound를 더하는 형태로 구성되어있다.

𝑄_𝑡(𝑎)

: time step t에서 행동 a의 평균 보상

𝑁_𝑡(𝑎)

: time step t까지 행동 a가 선택된 횟수

해당 action이 선택된 횟수가 적다면 그 action을 하도록 유도한다. 그래서 처음에는 많은 action이 있더라도 아예 선택되는 action이 없도록 하는 방식으로 나중에는 효율적인 탐색을 해서 agent가 유용한 보상을 더 자주 발견하도록 해서 sparse reward 문제를 간접적으로 해결할 수 있다.

정리하자면, 평균 reward도 높고 선택된 횟수도 적은 action을 선택하도록 구성된 알고리즘이다.

2. HER (Hindsight Experience Replay)

1) episode에서 각 transition을 저장할 때, 원래 목표뿐만 아니라 다른 목표와 함께 저장

2) 각 episode에서 최종 state를 목표로 하는 transition을 추가로 저장

3) Reward 변화로 인한 학습 효율성 증대

알고리즘 단계:

초기화 

•

목표 ggg 와 초기 state s0s_0s0​ sampling

상태 전이 반복 

•

Action policy πb(st∥g)\pi_b(s_t∥g)πb​(st​∥g)를 사용하여 현재 state sts_tst​와 목표 ggg에서 action ata_tat​를 sampling

•

Action ata_tat​를 실행하고 새로운 상태 st+1s_t+1st​+1 관찰

episode 종료 후 state transition 저장

•

기본 transition 저장

•

추가 목표를 위한 transition 저장

◦

현재 episode의 state를 기반으로 추가 목표 집합 G:=S(currentepisode)G:=S(currentepisode)G:=S(currentepisode) sampling

최적화 반복 

•

Replay buffer R에서 Mini bath B sampling

•

알고리즘 A를 사용하여 Mini batch B로 한 단계 최적화 수행

→ 정리하자면 Agent가 환경과 상호작용 하여 얻은 모든 transition과 원래 목표를 replay buffer에 저장함과 동시에 현재 episode에서 도달한 최종 state를 새로운 목표로 설정하여 transition을 추가로 저장하고, 이후에 replay buffer에서 sample을 뽑아서 그것으로 optimization을 진행한다.

replay buffer에서 transition을 sampling 하는 것과 함께, strategy S에 따라 additional goal g'을 sampling 하는 모습을 볼 수 있다.

original goal g가 있긴 하지만, g에 도달하지 못한 trajectory의 경우 r_g는 항상 near-zero reward일 것이기 때문에, additinal goal g'에 대해 새로 non-zero reward signal을 계산하기 위함이다.

그리하여, additional goal g'에 대해 발생한 non-zero reward signal rg'과 s||g'으로 치환된 sample을 통해 agent는 학습을 수행한다. 이러한 과정을 통해 original goal g에 도달하는 것을 실패한 trajectory로 부터도 정책이 개선될 수 있다.