12-2. Markov Decision Process (MDP): 강화 학습 문제 정의

1. 강화 학습 문제 정의: Markov Decision Process (MDP)

강화 학습은 에이전트(Agent)가 환경(Environment)과 상호작용하며, 주어진 목표를 달성하도록 학습하는 패러다임입니다. 에이전트는 환경으로부터 관찰(Observation)을 받고, 행동(Action)을 취하며, 그 결과로 보상(Reward)을 받습니다. 이 일련의 상호작용 과정을 통해 에이전트는 최적의 행동 전략, 즉 정책(Policy)을 학습합니다. 이러한 강화 학습 문제를 수학적으로 엄밀하게 정의하기 위해, 우리는 Markov Decision Process (MDP)라는 강력한 프레임워크를 사용합니다. MDP는 강화 학습 문제를 형식화하고, 이론적 분석 및 알고리즘 개발을 위한 기반을 제공합니다.

1) MDP의 구성 요소

MDP는 다음과 같은 다섯 가지 핵심 요소로 구성됩니다.

• S (States): 상태 집합 - 환경이 가질 수 있는 모든 가능한 상태들의 집합입니다. 각 상태는 에이전트가 환경을 관찰하고 이해하는 방식을 나타냅니다. 예를 들어, 자율 주행 자동차의 경우, S는 자동차의 위치, 속도, 주변 환경(도로, 다른 차량 등)에 대한 정보를 포함할 수 있습니다.
• A (Actions): 행동 집합 - 에이전트가 각 상태에서 수행할 수 있는 모든 가능한 행동들의 집합입니다. 자율 주행 자동차의 경우, A는 가속, 감속, 좌회전, 우회전 등과 같은 동작들을 포함합니다.
• P (Transition probabilities): 상태 변환 확률 - 상태 $s$에서 행동 $a$를 취했을 때, 다음 상태 $s'$로 이동할 확률을 나타냅니다. 즉, $P(s' | s, a)$는 상태 $s$에서 행동 $a$를 취했을 때, 다음 상태가 $s'$가 될 확률입니다. 이 확률은 환경의 역학(Dynamics)을 모델링하며, 환경이 어떻게 변화하는지를 보여줍니다.
• R (Rewards): 보상 함수 - 상태 $s$에서 행동 $a$를 취하고 다음 상태 $s'$로 이동했을 때 에이전트가 받는 보상(Reward)의 기댓값을 나타냅니다. $R(s, a, s')$는 상태 $s$에서 행동 $a$를 취한 결과로 상태 $s'$로 이동했을 때 받는 즉시 보상(Immediate reward)을 의미합니다. 보상은 에이전트가 학습하는 목표를 정의하며, 에이전트가 바람직한 행동을 하도록 유도합니다.
• γ (Discount factor): 할인율 - 0과 1 사이의 값으로, 미래 보상의 가치를 현재 시점에서의 가치보다 얼마나 할인할 것인지를 결정합니다. 즉, 현재 받는 보상보다 미래에 받는 보상을 덜 중요하게 여기는 정도를 나타냅니다. 할인율은 에이전트가 단기적인 보상에 집중할지, 장기적인 보상에 집중할지를 조절하는 역할을 합니다.

MDP를 시각화하면 다음과 같습니다. 에이전트는 현재 상태 $s_t$에서 행동 $a_t$를 선택하고, 환경은 상태를 $s_{t+1}$로 변경하고 보상 $r_{t+1}$을 반환합니다. 이 과정을 반복하면서 에이전트는 환경과 상호 작용합니다.

2) Markov property (마르코프 성질)

MDP의 핵심 가정은 마르코프 성질(Markov Property)입니다. 마르코프 성질은 미래 상태가 과거의 모든 상태와 행동에 의존하는 것이 아니라, 현재 상태에만 의존한다는 것을 의미합니다. 즉, 다음 상태 $s_{t+1}$는 현재 상태 $s_t$와 현재 행동 $a_t$에만 의존하며, 이전 상태나 행동에는 영향을 받지 않습니다.

수학적으로는 다음과 같이 표현됩니다.

$$ P(s_{t+1} | s_t, a_t, s_{t-1}, a_{t-1}, ..., s_0, a_0) = P(s_{t+1} | s_t, a_t) $$

마르코프 성질은 강화 학습 문제를 단순화하고, 효율적인 학습 알고리즘을 설계하는 데 중요한 역할을 합니다. 이 성질 덕분에 우리는 현재 상태에 대한 정보만으로도 미래를 예측하고, 최적의 행동을 결정할 수 있습니다.

3) 정책 (Policy)

정책(Policy)은 에이전트가 특정 상태에서 어떤 행동을 할지를 결정하는 규칙입니다. 정책은 상태를 입력으로 받아, 각 상태에서 취할 행동에 대한 확률 분포를 출력합니다. 정책은 확률적(Stochastic)일 수도 있고, 결정적(Deterministic)일 수도 있습니다.

• 확률적 정책: 각 상태에서 모든 가능한 행동에 대한 확률을 부여합니다. $\pi(a|s)$는 상태 $s$에서 행동 $a$를 할 확률을 나타냅니다.

  예시: $\pi(가속|정지) = 0.1$, $\pi(가속|정지) = 0.9$ * 결정적 정책: 각 상태에서 하나의 행동만을 결정합니다. $\pi(s)$는 상태 $s$에서 에이전트가 취하는 행동을 나타냅니다.

  예시: $\pi(정지) = 가속$

강화 학습의 목표는 주어진 환경에서 보상을 최대화하는 최적의 정책 $\pi^*$를 찾는 것입니다. 즉, 최적의 정책은 에이전트가 가장 많은 보상을 얻을 수 있도록 환경과 상호 작용하는 방법을 정의합니다.

4) 가치 함수 (Value Function)

가치 함수(Value Function)는 특정 상태 또는 상태-행동 쌍에서 얻을 수 있는 기대되는 누적 보상(Expected cumulative reward)을 추정합니다. 가치 함수는 에이전트가 얼마나 '좋은' 상태에 있는지, 또는 얼마나 '좋은' 행동을 하고 있는지를 평가하는 데 사용됩니다. 가치 함수는 두 가지 주요 유형으로 나뉩니다.

• 상태 가치 함수 (State-value function), V-함수: 특정 정책 $\pi$를 따를 때, 상태 $s$에서 시작하여 얻을 수 있는 기대되는 누적 보상을 나타냅니다. $V_{\pi}(s)$로 표기하며, 다음과 같이 정의됩니다.

  $$ V_{\pi}(s) = \mathbb{E}_{\pi} \left[ \sum_{t=0}^{\infty} \gamma^t R(s_t, a_t, s_{t+1}) | s_0 = s \right] $$

  여기서 $\mathbb{E}_{\pi}$는 정책 $\pi$를 따를 때의 기댓값을 의미합니다.

• 상태-행동 가치 함수 (State-action value function), Q-함수: 특정 정책 $\pi$를 따를 때, 상태 $s$에서 행동 $a$를 취한 후 얻을 수 있는 기대되는 누적 보상을 나타냅니다. $Q_{\pi}(s, a)$로 표기하며, 다음과 같이 정의됩니다.

  $$ Q_{\pi}(s, a) = \mathbb{E}_{\pi} \left[ \sum_{t=0}^{\infty} \gamma^t R(s_t, a_t, s_{t+1}) | s_0 = s, a_0 = a \right] $$

  Q-함수는 특정 상태에서 특정 행동을 취하는 것이 얼마나 좋은지를 평가하기 때문에, 에이전트가 어떤 행동을 해야 할지 결정하는 데 직접적인 정보를 제공합니다.

5) 벨만 방정식 (Bellman Equation)

벨만 방정식은 가치 함수를 재귀적으로 정의하는 핵심 방정식입니다. 벨만 방정식은 현재 상태의 가치가 미래 상태의 가치와 현재 보상의 합으로 표현될 수 있다는 것을 보여줍니다. 이 방정식은 강화 학습 알고리즘의 핵심적인 기반이 됩니다.

• 상태 가치 함수에 대한 벨만 방정식:

  $$ V_{\pi}(s) = \sum_{a \in A} \pi(a|s) \sum_{s' \in S} P(s'|s,a) [R(s,a,s') + \gamma V_{\pi}(s')] $$

  이 방정식은 정책 $\pi$를 따를 때, 상태 $s$의 가치는, 상태 $s$에서 가능한 모든 행동 $a$를 취할 확률 $\pi(a|s)$과, 행동 $a$를 취한 후 다음 상태 $s'$로 이동할 확률 $P(s'|s,a)$을 고려하여 계산됨을 의미합니다. 그리고 그 다음 상태 $s'$에서 얻는 보상 $R(s, a, s')$와, 할인된 미래 가치 $\gamma V_{\pi}(s')$의 합으로 표현됩니다.

• Q-함수에 대한 벨만 방정식:

  $$ Q_{\pi}(s, a) = \sum_{s' \in S} P(s'|s,a) [R(s,a,s') + \gamma \sum_{a' \in A} \pi(a'|s') Q_{\pi}(s', a')] $$

  Q-함수의 벨만 방정식은 상태 $s$에서 행동 $a$를 취했을 때의 가치를 계산합니다. 이는 행동 $a$를 취한 후 다음 상태 $s'$로 이동할 확률 $P(s'|s,a)$과, 그 다음 상태 $s'$에서 정책 $\pi$에 따라 선택될 모든 행동 $a'$에 대한 Q-함수 값의 가중 합의 합으로 나타냅니다.

벨만 방정식은 가치 함수를 계산하고, 궁극적으로는 최적의 정책을 찾는 데 사용되는 다양한 강화 학습 알고리즘의 핵심을 이룹니다.

2. 강화 학습 문제의 수학적 정의

이제 MDP의 구성 요소를 바탕으로 강화 학습 문제를 수학적으로 정의할 수 있습니다. 강화 학습의 목표는 주어진 환경에서 최적의 정책 $\pi^*$를 찾는 것입니다. 최적의 정책은 에이전트가 환경과 상호 작용하면서 얻을 수 있는 누적 보상의 기댓값을 최대화합니다.

1) 반환 (Return)

반환(Return), $G_t$는 시간 단계 $t$에서 시작하여, 에피소드(Episode, 환경과의 한 번의 상호 작용 시퀀스)가 종료될 때까지 에이전트가 받는 모든 보상의 할인된 합을 의미합니다.

$$ G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1} $$

2) 가치 함수와 정책의 관계

최적의 정책 $\pi^*$를 찾기 위해, 우리는 가치 함수를 활용합니다. 최적의 정책은 최적의 가치 함수, 즉 최대의 보상을 얻을 수 있는 가치 함수에 대응합니다.

• 최적 상태 가치 함수: 모든 가능한 정책 중에서 가장 큰 상태 가치를 갖는 가치 함수입니다. $V_*(s) = \max_{\pi} V_{\pi}(s)$
• 최적 상태-행동 가치 함수: 모든 가능한 정책 중에서 가장 큰 상태-행동 가치를 갖는 가치 함수입니다. $Q_*(s, a) = \max_{\pi} Q_{\pi}(s, a)$

최적 상태 가치 함수와 최적 상태-행동 가치 함수는 다음과 같은 관계를 갖습니다.

$$ V_*(s) = \max_a Q_*(s, a) $$

즉, 최적의 상태 가치는 해당 상태에서 모든 가능한 행동 중 가장 좋은 행동의 Q-값과 같습니다.

3) 최적 정책 유도

최적의 정책 $\pi^*$는 다음과 같이 정의됩니다.

$$ \pi^*(a|s) = \arg\max_a Q_*(s, a) $$

즉, 최적의 정책은 각 상태에서 최적의 상태-행동 가치를 갖는 행동을 선택합니다. 이는 각 상태 $s$에서, Q-함수 $Q_*(s, a)$의 값을 최대화하는 행동 $a$를 선택하는 것을 의미합니다.

4) 최적 가치 함수의 벨만 최적 방정식 (Bellman Optimality Equation)

최적의 가치 함수는 벨만 최적 방정식을 만족합니다.

• 최적 상태 가치 함수에 대한 벨만 최적 방정식:

  $$ V_*(s) = \max_a \sum_{s' \in S} P(s'|s, a) [R(s, a, s') + \gamma V_*(s')] $$

• 최적 상태-행동 가치 함수에 대한 벨만 최적 방정식:

  $$ Q_*(s, a) = \sum_{s' \in S} P(s'|s, a) [R(s, a, s') + \gamma \max_{a'} Q_*(s', a')] $$

이 방정식들은 최적 가치 함수를 구하는 데 사용되는 다양한 강화 학습 알고리즘의 핵심적인 기반이 됩니다. 벨만 최적 방정식을 풀면, 우리는 최적의 정책을 유도할 수 있습니다.

3. MDP의 응용 및 활용 사례

MDP는 다양한 분야에서 실용적으로 활용되고 있습니다. MDP의 강력한 프레임워크는 실제 문제를 모델링하고, 에이전트가 목표를 달성하도록 학습하는 데 유용합니다.

1) 게임 AI

MDP는 게임 AI 개발에 널리 사용됩니다. 게임 환경을 MDP로 모델링하여, 에이전트가 게임을 플레이하도록 학습시킬 수 있습니다.

• 예시: 체스, 바둑, 스타크래프트 등 복잡한 전략 게임에서 최적의 플레이어를 학습시키는 데 사용됩니다.
• 에이전트는 게임의 상태, 가능한 행동, 보상 함수(승리/패배, 점수 획득 등)를 정의하여 학습합니다.

2) 로봇 공학

로봇 제어 문제 역시 MDP로 효과적으로 모델링할 수 있습니다.

• 예시: 로봇 팔 제어, 자율 주행, 드론 제어 등.
• 에이전트는 로봇의 센서 정보(상태), 로봇의 동작(행동), 목표 달성 정도(보상)를 통해 학습합니다.

3) 자율 주행

자율 주행 시스템은 MDP를 사용하여 주행 전략을 최적화할 수 있습니다.

• 예시: 차량의 상태(위치, 속도, 주변 환경), 행동(가속, 감속, 조향), 보상 함수(안전 운전, 목적지 도착 등)를 정의합니다.
• 에이전트는 MDP를 통해 안전하고 효율적인 주행 경로를 학습합니다.

4) 추천 시스템

MDP는 사용자에게 최적의 상품이나 콘텐츠를 추천하는 데에도 사용될 수 있습니다.

• 예시: 영화, 상품 추천, 뉴스 기사 추천 등.
• 에이전트는 사용자의 행동(클릭, 구매 등), 추천 상품(상태), 보상 함수(클릭률, 구매 성공률 등)를 기반으로 학습합니다.

4. 주의사항과 트러블 슈팅

MDP를 활용한 강화 학습을 수행할 때, 몇 가지 주의해야 할 사항과 발생할 수 있는 문제에 대한 해결책을 제시합니다.

1) 상태 공간의 차원의 저주 (Curse of Dimensionality)

상태 공간의 크기가 커질수록, 학습에 필요한 데이터 양이 기하급수적으로 증가합니다.

• 문제: 상태 공간이 너무 커서 모든 상태를 탐색하고, 각 상태에 대한 정확한 가치를 추정하기 어렵습니다.
• 해결책:
  • 상태 공간 축소: 상태 변수를 줄이거나, 특징 공학(Feature engineering)을 통해 상태 공간을 효과적으로 표현합니다.
  • 함수 근사 (Function approximation): 딥러닝 모델(예: 신경망)을 사용하여 가치 함수 또는 정책을 근사합니다.
  • 계층적 강화 학습 (Hierarchical Reinforcement Learning): 문제를 더 작은 하위 문제로 분할하여, 각 하위 문제에 대한 정책을 학습합니다.

2) 보상 설계 (Reward Design)

보상 함수는 에이전트의 학습 방향을 결정하는 중요한 요소입니다.

• 문제: 부적절한 보상 설계는 에이전트가 의도하지 않은 방식으로 행동하거나, 목표를 달성하지 못하게 할 수 있습니다.
• 해결책:
  • 세분화된 보상 (Sparse reward): 목표 달성에 필요한 각 단계에 대한 보상을 부여하여, 에이전트가 학습할 수 있는 신호를 제공합니다.
  • 보상 쉐이핑 (Reward shaping): 보상 함수를 조정하여, 에이전트가 바람직한 행동을 하도록 유도합니다.
  • 역강화 학습 (Inverse Reinforcement Learning): 전문가의 행동을 관찰하여, 보상 함수를 추론합니다.

3) 탐험-활용 딜레마 (Exploration-Exploitation Dilemma)

에이전트는 학습을 위해 새로운 행동을 탐험(Exploration)해야 할 뿐만 아니라, 지금까지 얻은 지식을 활용(Exploitation)하여 보상을 최대화해야 합니다.

• 문제: 탐험과 활용 간의 적절한 균형을 유지하기 어렵습니다. 탐험을 너무 많이 하면 학습 속도가 느려지고, 활용을 너무 많이 하면 최적의 정책을 찾지 못할 수 있습니다.
• 해결책:
  • ε-탐욕 정책 (ε-greedy policy): 일정 확률 ε로 임의의 행동을 선택하고, (1-ε)의 확률로 현재 가장 좋은 행동을 선택합니다.
  • 볼츠만 탐험 (Boltzmann exploration): 행동의 가치에 따라 확률적으로 행동을 선택합니다. 가치가 높은 행동을 선택할 확률이 더 높습니다.
  • 낙관적 초기화 (Optimistic initialization): 초기에 모든 상태의 가치를 높게 설정하여, 에이전트가 모든 상태를 탐험하도록 유도합니다.

4) 수렴 문제 (Convergence Issues)

강화 학습 알고리즘은 최적의 정책으로 수렴하지 못할 수 있습니다.

• 문제: 알고리즘의 하이퍼파라미터 설정, 환경의 복잡성, 보상 함수의 특성 등에 따라 학습이 불안정해지거나, 지역 최적해에 빠질 수 있습니다.
• 해결책:
  • 학습률 조정: 적절한 학습률을 선택하여, 학습의 안정성을 확보합니다.
  • 경사 하강법 최적화 (Gradient descent optimization): Adam, RMSprop과 같은 고급 최적화 알고리즘을 사용하여, 학습 속도를 높이고 안정성을 향상시킵니다.
  • 정책 평가 및 개선: 학습 과정에서 정책의 성능을 평가하고, 정책을 지속적으로 개선합니다.

5. 결론

Markov Decision Process는 강화 학습 문제를 수학적으로 정의하고, 다양한 알고리즘을 개발하기 위한 강력한 프레임워크입니다. MDP의 핵심 요소들을 이해하고, 이를 활용하여 실제 문제를 해결하는 것은 강화 학습 분야에서 매우 중요합니다. 본 포스트에서는 MDP의 개념, 구성 요소, 수학적 정의, 응용 사례, 주의사항 등을 자세히 살펴보았습니다. MDP를 기반으로 하는 다양한 강화 학습 알고리즘(예: Q-Learning, Deep Q-Network, Policy Gradient 등)을 학습하고, 실제 문제에 적용해 보면서, 강화 학습에 대한 깊이 있는 이해를 얻을 수 있을 것입니다.