💪🏻

MDP

생성일

2024/07/11 15:16

태그

강화학습

작성자

Markov Property

1. Grid world example

아래와 같은 상태를 가진 grid world를 고려한다.

•

State : S={(1,1),(1,2),...,(4,2),(4,3)}S = \{(1,1), (1,2), ... , (4,2), (4,3)\}S={(1,1),(1,2),...,(4,2),(4,3)} 

•

Action: A={north,south,east,west}A = \{north, south, east, west\}A={north,south,east,west}

•

Reward : (4,3) 도달 시 +1, (4,2) 도달 시 -1, 기타 case에 대해 negative reward c

→ negative reward의 적용 이유 : 의미없는 이동에 대한 패널티 부여

•

Agent : noisy movement, 강화학습을 통해 스스로 학습하는 주체

•

State trainsition probability 

벽(2,2)에 도달 시 현재 상태 유지

선택한 방향(80%) 기준 좌, 우 방향에 대해 10% 확률로 이동 → action에 무작위성 부여

•

Terminal state : (4,2), (4,3) 

•

Goal : total sum of rewards를 maximize하는 policy 찾기

이때, Episode가 아래와 같다면 total reward는 negative reward와 최종 reward의 합인 5c+1이 된다.

2. Actions in grid world

•

Deterministic

Agent의 다음 state가 현재 state와 action에 의해서 완벽히 정해지는 경우로, Policy가 정해지면 episode 1개만 가능하다.

•

Stochastic

Agent가 같은 state에서 같은 action을 하더라도 무작위성에 의해 다양한 결과가 가능하다. 따라서 Policy가 정해지더라도 여러 episode가 가능하다. 대부분 Stochastic grid world를 고려한다.

3. Markov property

•

Stochastic Process

확률적 과정은 시간에 따라 index가 부여된 확률 변수의 집합이다. 크게 이산 확률 과정과 연속 확률 과정으로 구분되며, 이때 t가 현재 state를 의미하고, t+1이 next state, 나머지가 post를 의미한다.

•

Markov Process

만약 확률 과정이 Markov property를 만족하면 Markov process라고 한다. Markov property를 만족한다는 것은 현재 state

S_t = s

가 주어졌을 때 다음 state

S_{t+1} = s'

이 될 확률이 과거의 상태들에 독립적이라는 것을 의미한다. 따라서 이를 Memoryless property라고도 한다.

P(S_{t+1} = s'|S_t = s) = P(S_{t+1}=s'| S_0 = s_0 , ..., S_t=s)

이처럼 Markov property를 만족하면 process에서 이전 상태가 기록될 필요성이 사라지므로, 계산 효율성이 증가한다.

•

State transition probability

현재 state s에서 다음 state s’이 될 확률을 의미하며 상태 전이 확률이라고 부른다. 이때 Markov property를 만족하는 경우라면 과거 state가 확률에 영향을 미치지 않으므로 행렬 형태의 표현이 가능하다.

P(S_{t+1} = s'|S_t = s)

•

State transition probability matrix

P_{ij} = P_{sisj} = p(s_j|s_i) = P(S_{t+1}=s_j | S_t =s_i)

와 같이 행렬 표현을 활용 가능하며 각각의 행의 합은 현재 상태에서 가능한 모든 미래 상태로의 진행 확률들의 합이므로 합은 1이 된다.

결과적으로 Markov process는 (S, P)의 tuple 형태로 나타낼 수 있다. 이때 S는 state의 집합이고 P는 상태 전이 확률 행렬이 된다.

Markov Decision Process

1. MDP

위에서 살펴본 MP는 State와 Transition Probability의 tuple로 표현 가능하였으나, MDP에서는 action, reward, discount factor가 포함되며, 모든 state는 Markov property를 만족하는 형태이다.

•

S : state space

•

A : action space

•

P : Transition Probability

P^a_{ss'} = p(s'|s,a)=P(s_{t+1}=s'|S_t=s, A_t=a)

→ 현재 state가 s이고 a action을 선택했을 때 다음 state가 s’이 될 확률을 의미한다.

•

R : reward function

Action 선택의 기준이 되며, reward가 주어지는 시점에 따라 다양한 표현이 가능하다.

R^a_{ss’}

: 현재 state에서 action을 해서 다음 state로 전이될 때 얻게 되는 reward에 대한 표현

R_s

: 현재 state에 존재하기만 하면 받게 되는 reward에 대한 표현

R^a_s

: 현재 state에서 action을 취했을 때 얻게되는 reward에 대한 표현

•

γ\gammaγ : 0~1 사이의 값으로 discount factor를 의미한다.

2. Environment model

MDP에서의 환경 모델은 전이 확률을 의미한다. 이때 전이 확률을 아는 경우 MDP를 안다라고 표현하며 이 경우를 Model-based라고 한다. Model-based의 경우 방대한 게산을 효율적으로 진행하기 위하여 Dynamic programming 방식을 사용하여 optimal policy를 찾는다. MDP를 모르는 경우 즉 전이 확률을 모르는 경우를 Model-free라고 하며 이 경우 Reinforce learning을 사용하여 optimal policy를찾게 된다. 단, MDP를 모델링하는 경우 state, action, reward space는 사전에 정의해준다.

3. optimal policy in Grid world example

아래와 같은 상태를 가진 grid world를 고려하여, optimal policy를 찾아보자

•

State : S={(1,1),(1,2),...,(4,2),(4,3)}S = \{(1,1), (1,2), ... , (4,2), (4,3)\}S={(1,1),(1,2),...,(4,2),(4,3)} 

•

Action: A={north,south,east,west}A = \{north, south, east, west\}A={north,south,east,west}

•

Reward : (4,3) 도달 시 +1, (4,2) 도달 시 -1, 기타 case에 대해 negative reward c

→ negative reward의 적용 이유 : 의미없는 이동에 대한 패널티 부여

•

Agent : noisy movement, 강화학습을 통해 스스로 학습하는 주체

•

State trainsition probability 

벽(2,2)에 도달 시 현재 상태 유지

선택한 방향(80%) 기준 좌, 우 방향에 대해 10% 확률로 이동 → action에 무작위성 부여

•

Terminal state : (4,2), (4,3) 

•

Goal : total sum of rewards를 maximize하는 policy 찾기

MDP에서 optimal policy는

\pi_*

로 표현하며, 각 state에서 어떤 action을 선택할 것인지에 대한 정보를 담고 있다. 즉, 위의 경우 9개의 state에서 취하는 action의 집합을 1개의 policy라고 할 수 있다. 이때 state transition probability에 의해서 같은 action을 선택하더라도 전이되는 state가 다를 수 있으므로 하나의 policy에 여러개의 episode가 있을 수 있고 따라서 reward의 단순 합이 아닌 합의 기댓값을 최대화 하는 것을 optimal policy

\pi_*

로 나타낸다.

위 그림은 각 모델마다 서로 다른 optimal policy를 표현한 것인데, small negative reward의 차이로 서로 다른 모델이 되며 optimal policy가 달라진다. small negative reward(c)의 값이 크면 각각의 이동에 대해 주어지는 penalty가 작으므로 1번 case의 (3,2)에서 optimal한 action이 west가 된다. 이는 -1에 도달할 가능성을 완전히 배제하기 위한 것으로, west action을 취하고 transition probability에 의해 north로 전이되기를 희망하는 것이다. 같은 이유로 (4,1)에서의 optimal action도 south가 된다. 반면 2번 case에서는 c의 값이 1번에 비해 작아졌으므로, step의 증가에 따른 penalty가 늘어난 것이고 따라서 (3,2)와 (4,1)에서 optimal action이 달라진다. 마지막으로 4번 case의 경우 각 step에 대한 penalty가 -2로 굉장히 크기 때문에 최대한 빠른 종료를 하도록 optimal policy가 주어진다. 특히 (3,2)에서 east action을 optimal로 취급하는데, 이는 +1 reward를 얻기 위해서 north action을 취할 시, +1에 도달하더라도 -2+1 = -1 의 reward를 얻게 되고 transition probability에 의해서 (3,3)에 도달하고 east action을 취했음에도 west로 전이된다면 훨씬 더 적은 보상을 얻기 때문에, 확률적으로 가장 안전한 east action을 optimal로 취급한다. 정리하자면 (3,2)에서 east action을 optimal로 지정하는 경우 0.8의 확률로 -1 보상을 얻게 되고 나머지 경우는 심지어 +1에 도달하는 경우이더라도 -1보다 작거나 같다. 만약 north action을 optimal로 취급하는 경우 가장 큰 reward는 -1인데, 이 경우는 -1을 얻기 위한 확률이 0.8*0.8=0.64가 되므로 (3,2)에서의 optimal action은 east이다.

Reward, Policy

1. Reward

reward는 scalar feedback으로 t step에서 agent의 action이 얼마나 적절한지를 나타내준다. 따라서 agent의 목표는 reward의 누적 합을 최대화 하는 것이다. 이때 강화학습은 Reward Hypothesis를 기반으로 진행된다.

•

Reward Hypothesis

→ 모든 목표는 reward의 누적 합의 기댓값을 최대화 하는 것으로 표현 가능하다.

이때, 기댓값이 나오는 이유는 하나의 Policy에서 transition probability에 의해서 나올 수 있는 episode가 여러개가 될 수 있기 때문에, 기댓값의 개념을 사용한다. 또한 reward를 받는 시점이 다양할 수 있는데, 예를 들어 바둑에서는 게임 종료 후에, 탁구에서는 각 점수마다 reward를 지급하는 방식을 사용할 수 있다.

2. Known dynamics

모든 transition에 대해서 dynamics(

p(s’,r|s,a)

)를 안다고 가정하면 transition probability, reward 등을 이를 사용해 계산 가능하다.

•

transition probability 

→ 현재 state s에서 action a를 선택하여 다음 state s’으로 전이하는 과정에서 얻을 수 있는 reward에 대한 확률의 합으로 transition probability를 표현할 수 있고 그 과정에서 dynamics에 대한 식이 존재한다.

•

expected reward (state-action pair)

→ 기댓값 부분을 기댓값의 정의에 의해 풀어준다.

p(r|s,a)

가 현재 state s에서 action a를 선택했을 때 얻을 수 있는 reward에 대한 확률이다. 따라서 이는 state s에서 action a를 선택했을 때 reward r을 받고 전이 가능한 모든 s’에 대한 합으로 표현 가능하다. 그리고 그 과정에서 dynamics에 대한 식이 존재한다.

•

expected reward (state-action-next_state)

→ 기댓값 부분을 기댓값 정의에 의해 풀어준다. 이때

p(r|s’)

을 조건부 확률의 정의에 맞게 풀어주고,

(s,a)

조건을 동시에 추가해주면 식의 전개가 가능하다. 그리고 그 과정에서 dynamics에 대한 식이 존재한다.

3. Return

→ t 시점부터 종료 시점까지 감가된 reward의 누적 합이다. 이때 감가율

\gamma

는 0~1 사이의 실수 값으로, 미래의 reward의 불확실성에 대한 표현이며 크기에 따라 근시안적이거나 원시안적인 모델임을 표현 가능하다. discount factor를 사용하는 이유는 return의 무한대 발산을 막고 미래의 불확실성에 대한 표현이 가능하며 실전적인 상황에서 당장의 보상에 조금 더 관심을 가지게 하기 위함이다. 그러나 모든 sequence가 반드시 종료되는 경우 사용하지 않는 경우도 있다.

4. Policy

•

stochastic policy

→ 주어진 state에서 취하는 action에 대한 확률 분포로 아래와 같다.

\pi(a|s) = P(A_t=a | S_t=s)

•

Deterministic policy

\pi(s)=a

policy는 각 state에서 어떤 action을 취하는 것이 optimal한지, 즉 total discounted reward를 최대화하기 위한 action 선택에 대한 guideline이다. 이때 MDP에서의 policy는 MDP 각 state가 Markov property를 만족하기 때문에 오직 현재 state에 대해서만 종속적이다.

•

case1) Known MDP

→ deterministic optimal policy

\pi_*(s)

가 존재한다.

•

case2) Unknown MDP

→ stochastic policy를 고려해야 하며,

\epsilon-greedy

방식을 사용한다.

\epsilon-greedy

방식은

\epsilon

만큼 random한 action을 선택하고

1-\epsilon

만큼 greedy한 action(optimal)을 선택하여 현재 sample에서 비록 최적은 아닐지라도, 경험하지 않은 action에 대해서도 고려할 수 있도록 해준다. 이때

\epsilon

의 확률은 선택 가능한 모든 action에 대해서 동등하게 나누게 된다.

5. Notation

v_\pi(s)

: state-value function → 현재 state에서 policy

\pi

를 따랐을 때 가능한 모든 return에 대한 기댓값

v_*(s)

: optimal state-value function → 현재 state에서 optimal policy

\pi

를 따랐을 때의 value

q_\pi(s,a)

: action value function → 현재 state에서 policy

\pi

에 따라 action a를 선택했을 때의 value

q_*(s,a)

: optimal action-value function → 현재 state에서 policy

\pi_*

에 따라 action a를 선택했을 때의 value

이때 value는 각각 return의 기댓값을 의미한다.

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로 부터도 정책이 개선될 수 있다.