🎓 RL2 - MDP

🎓 개요

강화학습은 에이전트가 환경과 상호작용하며 시행착오를 통해 최적의 행동을 학습하는 순차적 의사결정 문제이다. 이러한 문제를 효과적으로 해결하기 위해서는 환경의 변화를 수학적으로 모델링해야 하며, 이를 설명하는 핵심 개념이 마르코프 과정(Markov Process)이다.

마르코프 과정은 현재 상태만으로 미래 상태를 결정할 수 있는 성질(마르코프 성질, Markov Property)을 가진다. 이를 통해 에이전트는 과거의 모든 정보를 기억하지 않고도 학습할 수 있는 효율성을 제공한다. 마르코프 과정을 확장한 마르코프 보상 과정(MRP)은 상태별로 장기적인 보상을 평가하는 데 활용되며, 마르코프 결정 과정(MDP)은 에이전트가 최적의 행동을 선택하여 순차적 의사결정을 해결하는 강화학습의 핵심 프레임워크이다.

결론적으로, MDP는 강화학습에서 순차적 의사결정을 모델링하는 기초를 제공하며, 이를 깊이 이해하는 것이 강화학습을 설계하고 구현하는 데 필수적이다. 다음으로, 이러한 각 개념을 구체적으로 살펴본다.

🎓 순차적 의사결정이란?

시간에 따라 변화하는 환경 속에서 에이전트가 일련의 행동을 선택하여 최적의 목표를 달성하는 문제를 말한다.

자율주행 차량의 순차적 의사결정을 예시로 들어보자.

1. 신호등 관찰: 차량이 교차로에 접근하며 신호등의 상태를 확인한다. 빨간불일 경우 정지하고, 초록불일 경우 다음 행동을 준비한다.
2. 장애물 감지 및 회피: 교차로를 지나며 앞 도로에서 자전거 또는 장애물을 감지한다. 차선을 변경하거나 속도를 조정하여 장애물을 회피한다.
3. 교차로 통과: 초록불일 때 가속하거나 속도를 유지하며 교차로를 안전하게 통과한다.
4. 목적지 접근 및 주차: 목적지 근처에 도달하면 주차 공간을 찾아 안전하게 차량을 주차한다.

이 4단계는 반드시 순서에 맞게 이루어져야 한다. 만약 순서가 뒤바뀌면 다음과 같은 상황이 발생한다.

• ④ → ③ → ② → ①: 차량이 주차를 먼저 시도한 뒤 교차로를 통과하고 장애물을 회피한 다음 마지막으로 신호를 관찰한다.
  문제점: 주차 완료 후 교차로를 다시 통과하려는 비논리적 행동과 신호를 무시하는 상황이 발생한다.
• ② → ④ → ③ → ①: 장애물을 회피한 뒤 주차를 시도하고 교차로를 통과하며 마지막에 신호를 확인한다.
  문제점: 신호 확인 없이 교차로를 통과하려는 위험한 행동과 주행 흐름의 혼란이 발생한다

MDP가 강화학습에 꼭 필요한 이유

순차적 의사결정은 시간이 지남에 따라 변화하는 환경 속에서 최적의 행동을 선택해야 하지만, 다음과 같은 오류를 내포할 수 있다:

• 단기적인 보상 최적화: 즉각적인 보상만을 고려하여 장기적인 결과를 간과하는 문제.
• 불확실성 간과: 행동 결과가 확률적으로 나타날 수 있음에도 이를 무시하고 결정하는 문제.
• 복잡성 증가: 시간의 흐름에 따라 상태와 행동의 조합이 폭발적으로 증가해 효율적인 계산이 어려워지는 문제.
• 환경 변화 미반영: 환경이 동적으로 변화함에도 고정된 정책을 사용해 최적화에 실패하는 문제.

이러한 오류를 해결하기 위해 MDP가 필요하다.

결론적으로, MDP는 환경의 동적 특성을 수학적으로 모델링하고, 미래 결과를 고려한 최적 정책 설계를 가능하게 하며, 불확실성 처리를 통해 행동 결과를 확률적으로 예측할 수 있다. 또한, Bellman 방정식을 이용한 효율적인 계산 구조를 제공하며, 자율주행, 로봇 제어, 게임 AI 등 다양한 문제에 일반화 가능한 프레임워크이다.

🎓 Markov Process(MP, 마르코프 과정)

마르코프 과정은 확률론적인 상태 전이 과정을 모델링한 수학적 프레임워크이다. 이는 현재 상태만으로 다음 상태가 결정되는 특성(마르코프 성질, Markov Property)을 가지며, 시간에 따라 변화하는 동적인 시스템을 표현한다. 더 간단히 말해서, 이는 현재 상태만을 기반으로 미래 결과에 대한 예측을 할 수 있는 과정이며, 가장 중요한 점은 이러한 예측이 과정의 전체 이력을 알고 있을 때 할 수 있는 예측과 똑같이 좋다는 것 또한 시스템의 현재 상태를 조건으로 미래 및 과거 상태는 독립적이다.

구성요소

상태 집합 (S)

• 시스템이 가질 수 있는 모든 상태의 집합.
• 예: 자율주행 차량의 위치(교차로, 직선 도로, 목적지 등), 날씨 상태(맑음, 흐림, 비 등).

상태 전이 확률 (P(𝑠,𝑠'))

• 현재 상태 𝑠에서 다음상태 𝑠'로 전이될 확률.
• 전이는 확률적으로 결정되며, 상태 전이 확률은 다음 조건을 만족한다:

  $P(s, s') = P[s_{t+1} = s' \mid s_t = s]$
  예: 현재 날씨가 맑음일 때, 흐림으로 변할 확률이 0.3, 비로 변할 확률이 0.2

Markov Property(마르코프 성질)

마르코프 특성은 현재 상태가 주어졌을 때, 미래 상태는 과거 상태와 독립적으로 현재 상태에 의해서만 결정된다는 성질

$P(s_{t+1}\mid s) = P[s_{t+1} \mid s_t]$
현재 상태 $s_t$가 주어졌을 때, 다음 상태가 발생할 확률은 $P(s_{t+1} \mid s_t)$로 나타낼 수 있다.

마르코프 과정은 복잡한 동적 시스템의 기초적인 모델로, 이를 확장하면 보상을 포함한 마르코프 보상 과정(MRP), 행동을 포함한 마르코프 결정 과정(MDP)로 발전한다. 이를 통해 더 복잡한 순차적 의사결정 문제를 해결할 수 있다.

🎓 마르코프 보상 과정(Markov Reward Process, MRP)

마르코프 보상 과정(MRP)은 마르코프 과정(MP)에 보상 함수(Reward Function)를 추가하여 상태에서 얻는 보상을 평가할 수 있도록 확장한 모델이다. 이를 통해 상태의 가치를 계산하고, 장기적인 보상을 평가할 수 있는 수단을 제공한다. 쉽게 말하면 Return과 가치 함수(Value Function)를 이용하여 장기적인 보상을 예측할 수 있다.

구성요소

상태 집합 (S)

• 시스템이 가질 수 있는 모든 상태의 집합.

상태 전이 확률 (P(𝑠,𝑠'))

• 현재 상태 𝑠에서 다음상태 𝑠'로 전이될 확률.

보상 함수

• 보상 함수는 특정 상태에서 에이전트가 받는 보상을 정의
• 이는 상태 𝑠에서의 기대 보상을 의미하며, 특정 상태에서 평균적으로 받게 될 보상을 수학적으로 나타낸 것

할인율 (𝛾)

• 미래 보상을 현재 가치로 평가하는 계수. → 미래 보상의 현재 가치를 조정하는 역할

상태 가치 함수(State Value Function)

특정 상태 𝑠에서 시작했을 때, 얻을 수 있는 기대 보상을 정의하는 함수로 $v(s) = \mathbb{E}[G_t | S_t = s]$($\mathbb{E}$는 기댓값을 의미) 이다. 즉, 우선 상태 가치 함수를 알기 전에 Return($G_t$)과 Episode의 개념을 알아야한다.

• Return($G_t$)
  Return($G_t$)은 특정 시점 𝑡에서 시작하여 미래에 받을 누적 보상을 의미

  $G_t = \sum_{k=0}^{T-1} \gamma^k R_{t+k+1} = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots + \gamma^{T-1} R_T$

• Episode(t)
  강화학습에서 하나의 과정이 시작되고 종료되는 일련의 상태(State) 및 행동(Action) 시퀀스를 의미 → 시작 상태에서 시작하여 종료 상태(Terminal State)에 도달할 때까지의 과정

상태 가치 함수의 Bellman 방정식 표현

위 식은 현재 상태에서 얻는 보상 $R_{t+1}$과 할인된 다음 상태의 기대 가치 $\gamma v(S_{t+1})$의 합으로 나타낼 수 있음을 의미한다. Bellman 방정식을 활용하면 상태 가치 함수를 재귀적으로 계산할 수 있으며 Bellman 방정식의 일반적인 형태는 다음과 같다.

여기서,

R(s) : 현재 상태에서 기대되는 즉각적인 보상
P(s'|s) : 현재 상태에서 다음 상태로 전이될 확률
$\gamma v(s')$ : 다음 상태의 기대 가치에 할인율을 적용한 값

이 방정식을 이용하면 각 상태의 가치를 재귀적으로 계산할 수 있다. 강화학습에서는 MRP를 기반으로 마르코프 결정 과정(MDP)을 정의하며, 이는 최적의 행동을 찾는 데 활용된다.

🎓 마르코프 결정 과정(Markov Decision Process, MDP)

마르코프 결정 과정(MDP)은 마르코프 보상 과정(MRP)에 행동(Action)과 정책(Policy)을 추가한 모델이다. 이는 순차적 의사결정 문제를 해결하기 위해 설계된 프레임워크로, 에이전트가 상태에서 행동을 선택하고 정책을 최적화하여 최적의 보상을 얻는 문제를 다룬다.

구성요소
상태 집합 (S)

• 시스템이 가질 수 있는 모든 상태의 집합.

행동 집합 (𝐴)

• 에이전트가 상태에서 취할 수 있는 모든 행동의 집합.

상태 전이 확률 (P(𝑠,𝑠'))

• 현재 상태 𝑠에서 다음상태 𝑠'로 전이될 확률.

보상 함수

• 보상 함수는 특정 상태에서 에이전트가 받는 보상을 정의

할인율 (𝛾)

• 미래 보상을 현재 가치로 평가하는 계수. → 미래 보상의 현재 가치를 조정하는 역할

정책(𝜋)

정책은 에이전트가 특정 상태에서 어떤 행동을 선택할지를 결정하는 전략이다.

• 결정론적 정책(Deterministic Policy)
  같은 입력 상태에 대해 항상 동일한 행동을 출력한다.
  수식 : $\pi(s) = a$
• 확률적 정책(Stochastic Policy)
  특정 상태에서 행동을 확률적으로 선택한다.
  수식 : $\pi(a | s) = P(A_t = a | S_t = s)$

MDP의 목표는 총 보상의 기대값을 최대화하는 최적 정책 𝜋을 찾는 것

가치 함수(Value Function)

MDP에서는 각 상태와 행동의 장기적인 기대 가치를 계산하여 최적의 의사결정을 수행하며 2가지로 나눌 수 있다.
1. 상태 가치 함수 $V^\pi(s)$

• 특정 상태 𝑠에서 시작하여 정책 𝜋를 따를 때 얻을 수 있는 총 기대 보상
  $V^\pi(s) = \mathbb{E}_\pi \left[ G_t \mid S_t = s \right]$

2. 행동 가치 함수 $Q^\pi(s, a)$

• 특정 상태 𝑠에서 행동 𝑎를 선택한 후 정책 𝜋를 따를 때 얻을 수 있는 총 기대 보상.
  $Q^\pi(s, a) = \mathbb{E}_\pi \left[ G_t \mid S_t = s, A_t = a \right]$

Bellman 방정식 표현

1. 상태 가치 함수 $V^\pi(s)$ Bellman 방정식 개념적 설명

• 상태 𝑠에서 정책 𝜋를 따를 때, 얻을 수 있는 총 기대 보상 $V^\pi(s)$는 아래와 같이 정의된다.
• 즉, 현재 상태에서 기대되는 보상과, 다음 상태에서의 가치($V^\pi(s')$)의 기댓값을 할인한 값의 합이다.
  $V^\pi(s) = \sum_{a \in A} \pi(a | s) \sum_{s' \in S} P(s' | s, a) \left[ R(s, a) + \gamma V^\pi(s') \right]$

2. 최적 상태 가치 함수 $V^\pi(s)$ Bellman 방정식 개념적 설명

• 최적 정책 𝜋를 따른다면, 각 상태 𝑠에서 최고의 행동을 선택해야 한다.
• 즉, 가능한 모든 행동 중에서 기대 보상이 가장 큰 행동을 선택해야 한다.
  $V^*(s) = \max_{a \in A} \sum_{s' \in S} P(s' | s, a) \left[ R(s, a) + \gamma V^*(s') \right]$

수식적으로 이해하는 Bellman 방정식 표현

Bellman 방정식은 MDP의 상태 가치 함수 𝑉(𝑠)를 재귀적으로 표현한 식이다.
이를 단계별로 분석하면:

1. 현재 상태 𝑠에서 행동 𝑎를 선택하고, 즉각적인 보상 𝑅(𝑠,𝑎)를 받는다.
2. 확률적으로 다음 상태 𝑠′로 전이되며, 이 상태에서 장기적인 기대 가치
   𝑉(𝑠′)를 얻을 수 있다.
3. 하지만 미래 보상의 가치는 현재보다 낮게 평가되므로, 할인율 𝛾를 적용하여 현재 가치에 반영한다.

이를 수식으로 나타내면:

하지만, 모든 상태 전이는 확률적이므로 이를 확률적으로 고려하여 다음과 같이 표현할 수 있다.

또한, 에이전트는 정책 𝜋에 따라 행동 𝑎를 선택하므로, 이 확률까지 반영하면:

마지막으로, 최적 정책을 따른다면 최적 행동을 선택하므로, 최적 상태 가치 함수는 다음과 같이 표현된다

🎓 용어 정리

• 상태 전이 확률 (P(𝑠,𝑠'))
  현재 상태 𝑠에서 다음상태 𝑠'로 전이될 확률.

• 할인율 (𝛾)
  미래 보상을 현재 가치로 평가하는 계수. → 미래 보상의 현재 가치를 조정하는 역할

• 정책(𝜋)
  정책은 에이전트가 특정 상태에서 어떤 행동을 선택할지를 결정하는 전략

• Return($G_t$)
  특정 시점 𝑡에서 시작하여 미래에 받을 누적 보상을 의미

• Episode(t)
  강화학습에서 하나의 과정이 시작되고 종료되는 일련의 상태(State) 및 행동(Action) 시퀀스를 의미 → 시작 상태에서 시작하여 종료 상태(Terminal State)에 도달할 때까지의 과정

🎓 향후 연구 계획

1. Q-learning과 Deep Q-Network(DQN)
   Q-learning 알고리즘의 원리 이해 DQN의 구조와 주요 구성 요소 (Replay Buffer, Target Network 등)에 대한 탐구

참고 : https://canvas4sh.tistory.com/296