[Reinforcement Learning] Markov Decision Process
From last posting ...
지난 포스팅 부터 다시 시작하자면, 결국 우리가 필요한 것은 다음과 같은 Plan이며,
해당 Plan은 Bellman Equation으로 부터 각 state의 value를 평가할 수 있게 되어 작성할 수 있게 되었다.
핵심적인 개념은, Agent의 출발 위치가 어디이든 상관이 없다 라는 것이다.
강화학습 모델의 경우에도 다음과 같은 Plan만 있다면, 그냥 뭐 다 한거라고 볼 수 있다.
하지만 실제 현실은 이렇게 간단하지 않은 경우가 많다. 따라서 마르코프 의사결정이 필요하다.
Markov Decision Process 의 원리
두 가지 개념으로 나누어 설명하겠다.
1. 결정론적 탐색(Deterministic Search)
2. 비결정론적 탐색(Non-deterministic Search)
결정론적 탐색에서는 agent가 해당 state에서
예를 들어 위로 가기로 했다면, 100%의 확률로 위로 가게 된다.
반면, 비결정론적 탐색에서는 agent가 해당 state에서 위로 가기로 했으면서,
위로 가지 않는 선택지가 생기기도 한다.
무슨 말이나면, 아까 본 Plan에서는 분명 위로 간다고 생각하고서는 실제 agent의 action은 위로 가지 않는 것이다.
여기서의 핵심은,
실제 세상에서 일어날 수 있는 현실적인 모델과 문제를 만들려고 하는 것이다.
왜냐면 우리가 실제로 뭔가 하려고할 때 결과가 의도한대로 나오기 힘들기 때문이다.
비결정론 탐색에서 모델링하고 있는 것은 Agent가 의도하지 못하거나, 제어할 수 없는 경우에 대해서 고려한다는 점이다.
여기서 두가지 개념이 나온다.
1. Markov Process
2. Markov Decision Process
Markov Process
A stochastic process has the Markov property if the conditional probability distribution of future states of the process(conditional on both past and present state) depends only upon the present state, not on the sequence of events that preceded it. A process with this property is a Markov Process
즉, 미래 상태가 그저 선택에 의한 것이 아니라, 전체적인 관점에서 볼 때
그 환경에서 우리가 수행한 행동의 결과가 현재 위치에 대해서만 의존하며, 현재로 어떻게 도달 했는지(과거)에 대해서는 무관하다.
이러한 속성을 마르코프 속성이라고 정의하고, 이러한 속성을 가진 과정을 마르코프 과정이라고 한다.
핵심은 Agent의 action이 현재 환경(통제할수 없는 변수 역시 포함)에만 의존하며,
현재 상태가 되기까지 무엇 일이 있었는지는 상관없다.
미래에 일어날 일은 1. 현재 상태 2. 수행하려는 행동 3. 무작위성 이 세가지로 만 결정된다.
Markov Decision Process
MDP(markov decision process) provide a mathematical framework for modeling decision making in situations where outcomes are partly random and partly under the control of a decision maker
예를 들어보자
Markov process는
Agent가 위로 가기로 결정한다면 "내가 위로 가려면 80%, 왼쪽 오른쪽으로는 각각 10%의 확률이다." 라는 것이다.
즉, 환경에 임의적인 요소가 있다는 점이고,
Markov Decision Processes는
Agent가 이 환경에서 뭘 해야하는지 이해하려고 사용하는 틀이다.
확률성과 임의성이 존재하는 환경에서 어디로 가야할지 를 알려주는 수학적인 framework 이다.
Markov Decision Processses 는 Bellman Equation을 수정한 형태라고 보면된다.
$$ V(s) = \underset{a}{max} (R(s,a)+\gamma V(s^{\prime})) $$
다시한번 설명하자면, 해당 상태 가치는 그 상태에서 수행할 수 있는 모든 행동의 최대값이고,
그 상태에서 행동을 수행해서 얻을 수 있는 보상에 다음 상태의 가치를 수정해서 더한 것이였다.
여기에서 임의성을 추가해보자.
임의성이 추가되었으므로, $ V(s^{\prime}) $을 계산할 수 가 없다.
따라서 이부분에 다음 상태의 기대 가치를 넣어주자
예를 들어 $ s^\prime $ 으로 갖을 수 있는 모든 경우의 수가
$ s^\prime_{1}, s^\prime_{2}, s^\prime_{3} $ 라고 할때
각 state로 갈 확률 혹은 임의성을 $P_1 $ 라고 한다면
$ V(s^{\prime}) $ 의 기댓값에 대해
$ <V(s^{\prime})> = P_1V(s^{\prime}_1)+ P_2V(s^{\prime}_2) + P_3V(s^{\prime}_3) $ 라고 할 수 있다.
따라서, 수정된 Bellman Equation은 다음과 같다.
$$ V(s) = \underset{a}{max} [R(s,a)+\gamma \sum_{s^\prime}P(s,a,s^\prime)V(s^\prime))] $$
짚고 넘어가야할점은 Probability는 현재 state 및 미래의 state에 모두 의존한다는 점이다.
즉, 통제 불가능한 state에 대해서도 다루고 있다.
다음 Markov Decision Process를 통해 Agent의 의사결정을 더 현실적으로 돕게 된다.