[로봇인공지능]Markov Decision Process

차근차근 인공지능, 인프준

 

 

 

Markov Decision Process(MDP)

MDP는 RL, 강화 학습에서 중요한 핵심 이론이다. 이론을 알아보기 전에 Markov property에 대한 정의를 먼저 알아보면 agent가 환경에서 어떤 행동을 취하기 위해서는 의사결정이 필요하다. 그럴 때 의사결정을 위해서 주변 환경으로부터 정보를 받게 되는데 이런 정보들의 특성을 Markov property라 한다.

 

현재 state에서 다음 state로 변화하는 transition은 오로지 현재 state만 의존한다. 왜냐하면 현재 state에는 과거의 여러 과정을 거쳐서 행동한 것이므로 앞으로의 행동을 위한 정보를 충분히 포함하고 있다고 보는 것이다.

 

 

 

Markov_마르코프 연쇄

 

Markov Chain

Markov property를 가지고 있는 체인을 Markov Chain이라고 한다.  Transition probability graph 또는 Transition probability matrix로로 표현할 수 있다.

 

state에 대한 콘셉트들?

The state j is accesible(or reachable) from i, i에서 j로 갈 확률이 0이 아니다.

i에서 갈 수 있는 모든 set, i에서 j로 변할 수 있고 j에서 i로도 변할 수 있으면 i와 j state가 communicate 할 수 있다고 얘기한다, 한 번에 도달하지 않아도 도달할 수 있으면 된다. 

 

Irreducible 하다: 모든 state가 서로 communicate 할 수 있다.

 

 

State Classification, state 종류

1. Absorbing State: 모든 트랜지션이 자신에게 돌아오는 상태를 의미한다.
2. Transient and Recurrent states: 도달 가능(reachable)하다. S가 S'로 돌아오지 못할 때 S를 transient state라 한다. transient state가 아닌 state 모두를 recurrent states라 한다. recurrent states는 S가 S'로 갔다가 다시 S로 돌아올 수 있음을 의미한다. 즉 모든 state들은 이 두 가지로 분류가 가능하다.

 

 

 

 

state가 변화를 하다가 어느 순간 recurrent class에 들어가 버린다면, 앞으로의 state는 영원히 recurrent class안에 머무를 수밖에 없다. 왜냐하면 나갈 수 있는 엣지가 존재하지 않기 때문이다. 그리고 만약 현재 state가 transient state라면 transient state의 변화는 일정구간 transient state고 일정구간은 recurrent state로 구성되어 있는 시퀀스로 바뀔 수 있다.

 

 

 

 

steady state probability distribution?

markov chain이 있고 거기서 시간이 충분히 흘렀을 때 그때의 마지막에 state가 어떻게 될 것인가에 대한 확률이다.

 

 

 

 

Markov Reward Process

Rt는 time에서 reward, RT는 Terminal Time Step에서의 reward로 표현한다. 당장 좋은 리워드를 선택하는 게 아니라 미래까지 고려했을 때의 좋은 action을 취하기 위해서 미래의 reward를 고려해야 한다.

 

Return은 로봇 action의 Rt가 쌓이고 있는데 영원히 terminal에 도달하지 못하게 되면 무한루프에 빠지게 될 수 있는데 이때 수렴하기 위해서 필요한 개념이다. 너무 먼 미래는 현재를 계획하는데 크게 도움이 되지 않을 수 있기 때문에 discounted return을 써서 불확실성을 줄이고 수렴성을 보장한다.

 

어떤 state S에서 시작해서 expected discount return을 구하면 그것을 state의 Value라고 표현한다.

 

RL에서 agent goal: Find a policy that maximize the expected discounted return
강화 학습에서의 목표는 보상을 극대화하는 것

 

 

Markov Decision Process

MDP는 보통 튜플로 표현한다. <S, A, P, R, r> 

• S_State(space)
• A_Action space
• P_Transition Probability
• R_Reward
• r_discounted factor

Goal in MDP: Find a policy that maximize the expected cumulative reward
MDP의 목표는 agent가 얻을 수 있는 리워드들의 합을 극대화하는 policy를 찾는 것

 

policy: state가 주어졌을 때 어떤 행동(action)을 취할 것인가

 

 

 

 

value function을 estimate 해야 한다.

• state-value function:  the expected discounted return when starting in state S
• action-value function: 현재 state에서 어떤 action을 취하느냐에 따라서 나오는 reward

 

 

state-value function과 action-value function을 정리해보자면 먼저 state-value function는 현재 상태에서 이 policy를 따랐을 때 얼마나 좋고 가치 있는지 표현하는 값이다. 그리고 action-value function은 policy에 따라서 이 행동(action)을 했을 때 얼마나 좋고 가치 있는지 표현하는 값이다.

 

 

 

 

state가 변화함에 따라서 얻는 reward, 이 reward들의 합을 value function이라고 한다. state의 변화는 항상 policy에 의존한다. 강화 학습의 목표는 가장 좋은 policy를 찾는 것이다. 이것은 policy가 optimal value 또는 optimal action-value를 찾기를 기대하는 것이다. 이렇게 최적화된 value function을 찾는 것이 목표이며 이 과정을 MDP를 푼다고 표현하기도 한다.

 

 

 

 

---

 

 

내용 참고

한양대학교 인공지능융합대학원 로봇인공지능 2주차 강의자료