MDP 개념 정리: Markov Decision Process, Policy, Reward

MDP는 상태가 있고, 그 상태에서 행동을 선택하면 확률적으로 다음 상태와 보상이 정해지는 의사결정 모델입니다.

강화학습에서 policy, reward, discount factor, value iteration, Q-Learning 같은 용어가 한꺼번에 나올 때는 먼저 MDP의 구성요소를 잡아야 전체 흐름이 보입니다.

 

핵심 정리

Markov Decision Process는 보통 상태 집합, 행동 집합, 전이 확률, 보상, 할인율로 설명합니다. 상태는 현재 상황, 행동은 선택 가능한 움직임, 전이 확률은 행동 뒤 어느 상태로 갈 가능성, 보상은 그 선택의 즉시 결과, 할인율은 미래 보상을 현재 판단에 얼마나 반영할지를 뜻합니다. policy는 어떤 상태에서 어떤 행동을 고를지 정하는 규칙입니다. MDP를 알고 있으면 value iteration은 모델을 알고 있을 때 값을 갱신하는 방식으로, Q-Learning은 환경을 직접 경험하면서 행동 가치 함수를 배워가는 방식으로 이해하기 쉬워집니다.

• State는 에이전트가 놓인 현재 상황입니다.
• Action은 그 상태에서 선택할 수 있는 행동입니다.
• Transition probability는 행동 뒤 다음 상태로 이동할 확률입니다.
• Reward는 상태와 행동 결과로 받는 보상입니다.
• Discount factor는 먼 미래 보상을 얼마나 작게 볼지 정합니다.
• Policy는 각 상태에서 어떤 행동을 고를지 정하는 규칙입니다.

원문은 Q-Learning과 value iteration에 대한 메모가 섞여 있어 처음 보는 사람이 출발점을 잡기 어려웠습니다. 이번 보강은 MDP 구성요소를 먼저 세우고, 뒤쪽 메모를 읽을 때 policy와 reward가 어디에 연결되는지 보이게 정리했습니다.

이어서 볼 글

• Exploration vs Exploitation: 강화학습 탐색과 활용 딜레마 - MDP의 policy가 행동을 고를 때 마주하는 탐색과 활용 균형이다.
• OpenAI Gym 사용법: reset, step, reward 기본 흐름 - MDP의 상태, 행동, 보상 흐름을 코드 환경에서 확인하는 글이다.
• Q-Learning 실험: 횡행 행동이 이득으로 학습되는 상황 - MDP 위에서 Q-value를 학습할 때 보상 설계가 결과를 바꾸는 사례이다.
• Q-Learning Learning Rate 문제: 작은 학습률과 느린 수렴 - MDP 환경에서 Q-Learning 업데이트와 learning rate 영향을 보는 실험이다.

 

Markov decision processes ( MDPs )

아래 설명 good(http://sanghyukchun.github.io/76/)

A policy is a rule that the agent follows in selecting actions, given the state it is in.

> The core problem of MDPs is to find a "policy" for the decision maker

그래서 optimal policy니 하면서 policy라는 말이 나왔구만..

목표는 아래처럼 시간에 따른 reward의 합을 최대할수 있도록 의사결정자의 action 선택인 $\pi$ 선정에 도움을 주는것 (골라주는 것)

$\sum^{\infty}_{t=0} {\gamma^t R_{a_t} (s_t, s_{t+1})} ($where we choose $a_t = \pi(s_t))$

내 Q-Learning에서는 비용으로 잡았으므로 거꾸로 최소화..

MDP는 5개의 구성요소로 구성된다.

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

S는 아래 그림같이 state들 전체 집합, 

A는 아래 a0, a1등으로 보이는 action (이게 랜덤하게 선택된다는 듯 하다. 내 Q-Learning 알고리즘에서 random()이 쓰였듯이)

P는 음.. 이게 아래 0.1, 0.7 이런 숫자같은데 내 Q-Learning 알고리즘에서 보자면 좀 애매하다. 왜냐면 여기서는 a를 랜덤하게 픽하고 나서 그다음에 어디로 갈지 전이 확률이 나오는데, 내 Q-Learning 알고리즘에서는 다음 state를 랜덤하게 pick하고 그 사이 weight를 R과 $\gamma$를 통해 계산한다. \\

음 다시보니까 내 Q-Learning 에서는 ax다음에 하나의 정해진 Sy로 무조건 가는 구조네.. (그림처럼 ax에서 여러 S로 가는 구조가 아니라)

아래 variant가 내가 구현한 Q-Learning하고 비슷한듯..\\

P의 경우 1이거나 0인거고...\\

오호.. 아래 끝판왕이 나왔네.. value iteration하고 Q-Learning은 비슷하지만, \\

P나 R을 불완전하게 알때도 쓸 수 있는게 Q-Learning이고.. \\

P를 정확히 모르는 대신, initial state를 랜덤하게 바꿔가면서 갈수 있는데로 다니다보면 비슷해진다. 이런 취지의 설명인듯?\\

내가 궁금했던.. 왜 매번 initial state를 바꾸는가에 대한 어떻게 보면 답이네...\\

매번 바꾸는게 아니라 순서를 고정할 순 없는건가?\\

> The core of the algorithm is a simple value iteration update. 

아예 대놓고 Q-Learning의 core 알고리즘은 value iteration이라고 나와있네 ㅎㅎ

R은 reward.. 

$\gamma$는 0과 1사이 discount factor.. future reward의 비율을 결정.. 익히 알고 있는 내용이다.

이거 보다보니까 Q-Learning 그 자체네?.. 신기...

Q-Learning과의 차이점은 optimal policy를 찾는 방법에 있는듯..

Q-Learning에서는 쉬운 모델링을 제시한거고 일반적으로는 DP같은걸 쓰면 풀리는 듯

> the state transitions of an MDP process satisfies the Markov property. 그렇겠지 markov란 이름이 붙었으니까..

>modeling decision making in situations where outcomes are partly random and partly under the control of a decision maker. > 뭔솔

>At each time step, the process is in some state s, and the decision maker may choose any action a that is available in state s. The process responds at the next time step by randomly moving into a new state s', and giving the decision maker a corresponding reward $R_a(s,s')$.

음.. 좋은말 많이 나오네.. state, action, random move, reward.

>Markov decision processes are an extension of Markov chains; the difference is the addition of actions (allowing choice) and rewards (giving motivation). Conversely, if only one action exists for each state and all rewards are the same (e.g., zero), a Markov decision process reduces to a Markov chain.

오.. 이게 중요한 말이네.. 두번 읽자.\\

원래 상태전이 그래프(Markov chain)에서는 하나의 노드에서 다른 노드로 가는 방법이 정해져있다. (예를 들면 가장 높은 확률로 전이)

근데 MDP에서는 action이라는 명목하에 이리도 갔다가 저리도 갔다가 하고 그에 따라서 시스템이 reward를 준다 말이네..

내 프로그램을 MDP형태로 그려보면 다음처럼 되어 있는거네..

action 다음에 갈래길은 하나인거고 (확률 1.0),

action 을 선택하기 위한 Q-matrix 값들이 저렇게 분포하는거고..

나는 Q를 Q(s, a)로 정의하는 대신 Q(s0, s1)로 정의한거고..

(a라는 값은 필요없고.. 1.0은 항상 똑같으니 생략 가능)

Reward또한 R(s, a)로 기술되는데.. 내꺼는 s만 정해지면 a가 정해지니까 a를 생략해서 R(s)로 표현 가능한 상황인듯