마르코프 결정 과정 MDPs 이해하기

마르코프 결정 과정 (MDPs) 이해하기

Overview

마르코프 결정 과정(Markov Decision Process, MDP)은 강화 학습(reinforcement learning)에서 매우 중요한 개념입니다. MDP는 환경과 에이전트 간의 상호작용을 모델링하는 수학적 프레임워크로, 에이전트가 최적의 정책을 찾기 위해 환경과 상호작용하는 방법을 정의합니다. 이 개념을 이해하면 강화 학습을 설계하고 분석하는 데 큰 도움이 됩니다.

MDP의 구성 요소

MDP는 다음과 같은 네 가지 기본 구성 요소로 이루어져 있습니다:

1. 상태(State, S)
2. 행동(Action, A)
3. 보상(Reward, R)
4. 전이 확률(Transition Probability, P)

1. 상태 (State, S)

상태는 에이전트가 환경 내에서 현재 위치하고 있는 상황을 나타냅니다. 각 상태는 환경의 특정 시점에서 에이전트의 위치, 상황 또는 컨디션을 의미합니다.

• 예시: 자율주행 자동차의 경우, 상태는 자동차의 위치, 속도, 주변 장애물의 위치 등을 포함할 수 있습니다. 예를 들어, "자동차가 교차로에 접근 중"이라는 상태는 특정 속도와 위치 정보를 포함합니다.

2. 행동 (Action, A)

행동은 에이전트가 상태에서 선택할 수 있는 동작을 나타냅니다. 각 행동은 상태를 변화시킬 수 있으며, 에이전트가 환경에 영향을 미치는 방법을 정의합니다.

• 예시: 자율주행 자동차가 "좌회전" 또는 "우회전" 같은 행동을 선택할 수 있습니다. 이러한 행동은 자동차의 경로와 최종 목적지에 영향을 미칩니다.

3. 보상 (Reward, R)

보상은 에이전트가 특정 상태에서 특정 행동을 취했을 때 받는 즉각적인 피드백입니다. 보상은 에이전트가 목표를 달성하는 데 얼마나 잘하고 있는지를 측정하는 지표입니다.

• 예시: 자율주행 자동차가 교차로를 안전하게 통과하면 양의 보상을 받을 수 있습니다. 반대로, 신호를 무시하거나 사고를 일으키면 음의 보상을 받을 수 있습니다.

4. 전이 확률 (Transition Probability, P)

전이 확률은 현재 상태와 행동에 따라 다음 상태로 전이될 확률을 나타냅니다. 이는 환경의 동적 특성을 모델링하는 데 사용됩니다.

• 예시: 자율주행 자동차가 특정 도로에서 회전하는 경우, 도로의 상태에 따라 실제로 원하는 방향으로 회전할 확률이 달라질 수 있습니다. 예를 들어, 미끄러운 도로에서는 회전 실패 확률이 높아질 수 있습니다.

MDP의 수학적 정의

MDP는 수학적으로 5개의 요소로 정의됩니다: 상태 집합(S), 행동 집합(A), 보상 함수(R), 전이 확률 함수(P), 그리고 정책(π)입니다.

• 상태 집합(S): S는 가능한 모든 상태의 집합입니다.
• 행동 집합(A): A는 가능한 모든 행동의 집합입니다.
• 보상 함수(R): R: S × A → ℝ는 상태와 행동의 쌍에 대해 보상을 반환합니다.
• 전이 확률 함수(P): P: S × A × S → [0, 1]은 주어진 상태와 행동 쌍에 대해 다음 상태로 전이될 확률을 반환합니다.
• 정책(π): π: S → A는 각 상태에서 에이전트가 취할 행동을 결정합니다.

MDP의 해결 방법

MDP를 해결하는 목표는 최적의 정책을 찾는 것입니다. 이는 에이전트가 환경에서 최대의 장기적 보상을 얻기 위해 취할 최적의 행동 시퀀스를 결정하는 것입니다. 일반적으로 다음과 같은 방법으로 MDP를 해결합니다:

1. 벨만 방정식 (Bellman Equation)

벨만 방정식은 MDP의 최적 정책을 찾기 위한 핵심 방정식입니다. 이 방정식은 특정 상태에서의 최적 가치 함수(V)를 다음과 같이 정의합니다:

[
V(s) = \max_{a \in A} \left[ R(s, a) + \gamma \sum_{s' \in S} P(s' | s, a) V(s') \right]
]

여기서 ( \gamma )는 할인율(discount factor)로, 미래 보상에 대한 현재의 중요도를 나타냅니다.

2. 정책 반복 (Policy Iteration)

정책 반복은 주어진 정책을 평가하고, 이를 개선하는 과정입니다. 정책 평가 단계에서는 현재 정책을 기준으로 가치 함수를 계산하고, 정책 개선 단계에서는 가치 함수에 따라 최적의 정책을 도출합니다.

• 정책 평가: 현재 정책에 따라 상태의 가치를 계산합니다.
• 정책 개선: 가치 함수에 따라 각 상태에서 가장 좋은 행동을 선택합니다.

3. 가치 반복 (Value Iteration)

가치 반복은 정책 반복의 변형으로, 가치 함수를 반복적으로 업데이트하여 최적의 정책을 찾습니다. 각 상태의 가치는 다음과 같이 업데이트됩니다:

[
V(s) \leftarrow \max_{a \in A} \left[ R(s, a) + \gamma \sum_{s' \in S} P(s' | s, a) V(s') \right]
]

가치 반복은 각 상태에서 최대 가치를 계산하고 이를 반복하여 수렴할 때까지 업데이트합니다.

예시: 그리드 월드 (Grid World)

그리드 월드는 간단한 MDP 예제입니다. 이 예제에서 에이전트는 격자(grid) 위를 이동하며, 목표는 최대 보상을 얻는 것입니다. 예를 들어, 4x4 격자에서 에이전트는 상하좌우로 이동할 수 있으며, 목표는 특정 위치에 도달하거나 장애물을 피하는 것입니다.

• 상태: 격자의 각 셀.
• 행동: 상하좌우 이동.
• 보상: 특정 위치에 도달하면 양의 보상, 장애물에 부딪히면 음의 보상.
• 전이 확률: 이동 시 벽에 부딪힐 확률, 목표 위치에 도달할 확률.

이 예제는 MDP의 기본 개념을 이해하는 데 유용하며, 실제 문제를 모델링할 때의 기초를 제공합니다.

참고문서

• Reinforcement Learning: An Introduction (Sutton & Barto) - 강화 학습의 기초와 MDP에 대한 자세한 설명을 제공합니다.
• Markov Decision Processes (Wikipedia) - MDP의 정의와 관련된 기본 개념을 설명합니다.
• Bellman Equation (Wikipedia) - 벨만 방정식에 대한 자세한 정보를 제공합니다.

이 문서들은 MDP를 이해하고 적용하는 데 도움을 줄 것입니다.