마르코프 의사결정 과정(MDP)

마르코프 의사결정 과정(Markov Dicision Process, MDP)은 순차적인 의사결정 문제를 수학적으로 모델링하는 방법이다.

이는 강화학습에서 핵심 개념으로 사용되며, 에이전트가 환경과 상호 작용하면서 최적의 행동을 학습하는 데 활용된다.

결정적 탐색(Deterministic Exploration)과 비결정적 탐색(Non-Deterministic Exploration)

결정적 탐색(Deterministic Exploration)

걸졍적 탐색이란 주어진 상태에서 특정 행동을 취했을 때 정확히 어떤 상태로 전이될지 알 수 있는 환경에서 목표 상태를 찾는 과정이다. 즉, 모든 것이 예측 가능하고 불확실성이 전혀 없는 상황에서 최적의 경로를 찾는 문제이다.

예를 들면, 만약 에이전트가 위로 가기로 결정하면 100% 확률로 위로 가게 된다. 다른 옵션은 없이 정확히 그대로 되는 것이다.

비결정적 탐색(Non-Deterministic Exploration)

비결정적 탐색은 주어진 상태에서 특정 행동을 취했을 때 어떤 상태로 전이될지 확률적으로만 알 수 있는 환경에서 목표 상태를 찾는 과정이다. 즉, 불확실성이 존재하며, 최적의 경로를 찾는 것이 더욱 복잡한 문제이다.

결정적 탐색과는 반대로 에이전트가 위로 가기로 결정하면 여러 옵션이 생긴다. 예를 들면, 3개가 생길 수 있다. 그러면 80% 확률로 위로 가고, 10% 확률로 위로 가고 싶어도 왼쪽으로 가게 되거나 10% 확률로 위로 가고 싶어도 오른쪽으로 가게 된다.

마르코프 과정(Markov Process)

MDP, 마르코프 의사결정 과정을 이해하려면 먼저 마르코프 과정에 대해서 알아야 한다.

마르코프 속성(Markov Property)

마르코프 속성은 현재 상태는 과거의 모든 정보를 포함하ㅗ 있으며, 다음 상태는 현재 상태와 행동에만 의존한다는 개념이다. 즉, 과거의 상태는 다음 상태에 직접적인 영향을 미치지 않는다.

예시로 동전을 전지는 상황을 생각해 보면, 동전을 전지기 전의 모든 과거 정보(날씨, 습도, 던지는 사람의 힘 등)는 현재 동전의 상태(앞면 또는 뒷면)에 이미 반영되어 있다. 따라서 다음에 동전을 던졌을 때 앞면이 나올지 뒷면이 나올지는 현재 동전의 상태와 던지는 행위에만 영향을 받는다.

마르코프 과정(Markov Process)

마르코프 과정은 마르코프 속성을 만족하는 확률 과정이다. 즉, 현재 상태에서 다음 상태로 전이할 활률이 과거의 모든 상태에 의존하지 않고 현재 상태에만 의존하는 과정이다.

마르코프 의사결정 과정(Markov Decision Process)

마르코프 의사결정 과정 MDP는 마르코프 과정에 의사결정 요소를 추가한 모델이다. 즉, 에이전트가 틀정 상태에서 행동을선택하고, 그 행동에 따라 다음 상태로 전이하며 보상을 받는 과정이다.

MDP는 불확실한 환경에서 의사결정을 최적화하기 위한 Action, Reward 및 Policy의 개념을 추가한다.

MDP는 다음과 같이 정의할 수 있다.

• s : state, 상태
• a : action, 에이전트가 수행할 작성
• P : 주어진 동작에서 상태 간의 전이 확률
• R : 에이전트가 각 생태-행동에 대해 얻는 보상

MDP의 목적은 최적의 Policy를 찾는 것이다. 최적의 Policy는 상태에서 행동으로 매핑하여 시간이 지남에 따라 예상되는 누적 보상을 최대화하는 것이다.

여기서 Bellman 방정식을 사용할 수 있다.

이 방정식에서 R(s, a)는 상태 s에서 행동 a를 취함으로써 얻는 보상을 나타낸다.

P(s, a, s')는 현재 상태 s일 때, 주어진 행동 a을 수행하면 다음 상태 s'의 확률을 나타낸다.

쉽게 얘기하자면, 위의 80% 확률로 위로 가고, 10% 확률로 왼쪽, 10% 확률로 오른쪽이라고 했었다.

그렇다면 \( 0.8 * V(s'_1) + 0.1 * V(s'_2) + 0.1 * V(s'_3) \) 과 같다는 말이다.

벨만 방정식은 MDP에서 각 상태의 가치를 추정하는 식으로 수렴할 때까지 가치 함수를 반복적으로 개선하여 최적의 Policy를 결정할 수 있게 한다.

 

정리해보자면, 마르코프 과정에서 상태, 행동, 보상 및 확률의 개념을 추가한 MDP는 시간이 지남에 따라 누적 보상을 극대화하는 최적의 정책을 찾을 수 있도록 한다. 벨만 방정식은 MDP를 풀고, 의사결정을 도출하는 데 기본적인 도구 역할을 한다.