마르코프 결정 과정

상태는 마르코프 결정 과정이 존재하는 환경의 상황을 수학적으로 표현한 것이다. 이는 에이전트가 관찰 가능한 환경의 모든 정보를 포함하며, 일반적으로 실수 벡터, 이산적인 심볼, 또는 이미지 픽셀의 배열 등 다양한 형태로 나타낼 수 있다. 상태의 집합은 S로 표기하며, 각각의 특정 상태는 s ∈ S로 표현한다.

상태는 마르코프 성질을 만족해야 한다. 이는 미래 상태의 확률 분포가 오직 현재 상태와 선택된 행동에만 의존하며, 과거의 상태나 행동의 역사에는 독립적이어야 함을 의미한다. 수학적으로는 P(s_{t+1} | s_t, a_t, s_{t-1}, a_{t-1}, ...) = P(s_{t+1} | s_t, a_t)로 정의된다. 이 성질은 문제의 복잡성을 크게 줄여주는 핵심 가정이다.

상태 공간은 그 크기와 특성에 따라 다음과 같이 분류된다.

효율적인 상태 표현은 문제 해결의 핵심이다. 상태는 환경의 모든 관련 정보를 담아야 하지만, 불필요한 정보는 제거하여 차원을 줄이는 것이 중요하다. 이를 상태 표현 또는 특징 공학이라고 한다. 예를 들어, 자율 주행 문제에서 카메라 원본 이미지를 그대로 상태로 사용하기보다는, 차선 위치, 다른 차량의 상대적 거리와 속도 등 핵심 정보만 추출하여 상태 벡터를 구성한다.

행동은 에이전트가 특정 상태에서 선택할 수 있는 가능한 선택지의 집합을 가리킨다. 이 집합은 일반적으로 유한하지만, 연속적인 공간에서 정의될 수도 있다. 에이전트는 매 시간 단계마다 이 집합에서 하나의 행동을 선택하여 환경에 적용하며, 이는 다음 상태로의 전이와 즉각적인 보상에 영향을 미친다.

행동 공간의 설계는 문제의 복잡성과 해결 가능성에 직접적인 영향을 준다. 예를 들어, 격자 세계에서 로봇을 이동시키는 문제에서는 행동 집합을 {위, 아래, 왼쪽, 오른쪽}으로 정의할 수 있다. 반면, 주식 포트폴리오 관리 문제에서는 '매수', '매도', '보유'와 같은 행동이 포함될 수 있으며, 그 규모까지도 행동의 일부로 정의될 수 있다.

행동 선택은 정책에 의해 지배된다. 정책은 각 상태에서 각 행동을 선택할 확률을 매핑하는 함수이다. 따라서 행동은 에이전트가 환경과 상호작용하며 목표(누적 보상 극대화)를 달성하기 위한 핵심 수단이 된다.

전이 확률은 마르코프 결정 과정의 핵심 구성 요소 중 하나로, 에이전트가 특정 상태에서 특정 행동을 취했을 때, 다음 상태로 전이될 확률 분포를 나타낸다. 수학적으로는 조건부 확률 $P(s' | s, a)$로 표현되며, 이는 현재 상태가 $s$이고 행동 $a$를 선택했을 때, 다음 상태가 $s'$이 될 확률을 의미한다. 이 확률은 마르코프 성질을 만족시켜야 하며, 이는 미래 상태의 확률이 오직 현재 상태와 현재 선택된 행동에만 의존하고, 그 이전의 상태와 행동의 역사에는 독립적이어야 함을 뜻한다.

전이 확률은 일반적으로 확률 행렬이나 테이블 형태로 정의된다. 모든 상태 $s \in S$, 행동 $a \in A$, 그리고 다음 상태 $s' \in S$에 대해 확률값이 할당된다. 이 확률은 다음 조건을 만족해야 한다.

1. 비음수성: $P(s' | s, a) \geq 0$

2. 총합이 1: $\sum_{s' \in S} P(s' | s, a) = 1$

표는 전이 확률의 한 예를 보여준다. 예를 들어, 에이전트가 '상태_A'에서 '행동_1'을 취하면, 20% 확률로 제자리에 머물고('상태_A'), 80% 확률로 '상태_B'로 이동한다. '행동_2'를 취하면 100% 확률로 '상태_C'로 전이된다.

전이 확률은 환경의 역학을 결정하며, 에이전트가 최적의 의사결정을 학습하는 데 필수적인 정보이다. 이 확률 모델이 알려져 있으면 동적 프로그래밍과 같은 계획 방법을 사용할 수 있다. 반면, 환경 모델을 알 수 없는 경우에는 몬테카를로 방법이나 시간차 학습과 같은 모델 없는 강화 학습 알고리즘을 통해 경험으로부터 직접 학습한다.

보상 함수는 에이전트가 특정 상태에서 특정 행동을 취한 후, 그 결과로 다음 상태로 전이될 때 받는 즉각적인 숫자 신호를 정의한다. 이 함수는 일반적으로 $R(s, a, s')$ 또는 $R(s, a)$로 표기되며, 여기서 $s$는 현재 상태, $a$는 취한 행동, $s'$는 전이된 다음 상태를 나타낸다. 보상은 에이전트가 어떤 행동이 바람직한지를 학습하는 유일한 피드백이자, 궁극적 목표인 누적 보상을 최대화하기 위한 기준이 된다.

보상 함수의 설계는 마르코프 결정 과정 문제의 성패를 좌우하는 핵심 요소이다. 보상은 에이전트에게 원하는 행동을 유도하도록 명확하고 일관되게 주어져야 한다. 예를 들어, 게임에서 승리하면 큰 양의 보상을, 패배하면 음의 보상(페널티)을 주는 방식이다. 잘못 설계된 보상 함수는 에이전트가 의도하지 않은 부작용을 학습하거나, 지역 최적점에 빠지게 만드는 원인이 된다[2].

보상의 형태는 문제에 따라 다양하다. 가장 일반적인 형태는 다음과 같다.

보상 함수는 환경의 일부로 주어지거나, 학습자가 설계하여 에이전트에 제공한다. 강화 학습에서 에이전트의 목표는 이 보상의 할인된 누적 합, 즉 기대 수익을 최대화하는 정책을 찾는 것이다.

할인 인자는 미래 보상의 현재 가치를 결정하는 0과 1 사이의 값(γ)이다. 에이전트가 즉각적인 보상을 선호하는지, 아니면 장기적인 보상을 더 중요하게 여기는지를 조절하는 매개변수 역할을 한다. γ가 0에 가까우면 에이전트는 매우 근시안적으로, 즉 다음 상태에서 얻는 보상만을 고려한다. 반대로 γ가 1에 가까워질수록 에이전트는 더 먼 미래의 보상까지 현재 가치로 환산하여 고려하게 된다.

할인 인자는 수렴을 보장하는 데도 중요한 역할을 한다. 무한한 시간 동안 누적되는 보상의 합이 발산하지 않도록 하여, 가치 함수가 유한한 값을 가지게 만든다. 이는 벨만 방정식을 풀고 최적 정책을 찾는 수학적 기반을 제공한다.

적절한 할인 인자 값은 문제의 성격에 따라 결정된다. 예를 들어, 에피소드가 빠르게 종료되는 문제에서는 γ를 1에 가깝게 설정할 수 있다. 반면, 무한히 지속되는 과정이나 장기적인 계획이 중요한 문제에서는 γ를 1보다 작은 값(예: 0.9, 0.99)으로 설정하여 미래 보상을 할인한다. 이는 불확실한 미래 보상에 대한 합리적인 가정을 반영한다[3].

정책은 에이전트가 주어진 상태에서 어떤 행동을 선택할지를 결정하는 규칙이다. 이는 상태의 함수로 표현되며, 일반적으로 π(s) 또는 π(a|s)로 표기한다. 정책은 에이전트의 행동 방침을 정의하며, 마르코프 결정 과정에서 해결해야 할 핵심 대상이다.

정책은 결정론적 정책과 확률론적 정책으로 구분된다. 결정론적 정책은 특정 상태 s에서 항상 하나의 특정 행동 a를 선택한다(π(s) = a). 반면, 확률론적 정책은 상태 s가 주어졌을 때 가능한 모든 행동에 대한 확률 분포를 제공한다(π(a|s) = P(A_t = a | S_t = s). 확률론적 정책은 탐험과 활용의 균형을 맞출 때 유용하다.

정책의 질은 궁극적으로 에이전트가 누적하여 얻는 보상의 기댓값, 즉 가치 함수로 평가된다. 따라서 강화 학습의 목표는 보상을 최대화하는 최적 정책 π*을 찾는 것이다. 정책은 학습 과정에서 고정되어 있을 수도 있고, 가치 함수나 직접적인 경험을 바탕으로 지속적으로 개선될 수도 있다.

상태 가치 함수는 특정 정책을 따를 때, 에이전트가 어떤 상태에서 시작하여 미래에 받을 것으로 기대되는 누적 보상의 총량을 나타내는 함수이다. 이 함수는 주어진 상태가 얼마나 '좋은지'를 수치적으로 평가하는 척도를 제공한다. 일반적으로 V(s) 또는 V^π(s)로 표기하며, 여기서 π는 따르는 정책을 의미한다.

누적 보상은 일반적으로 미래 보상의 현재 가치를 반영하기 위해 할인 인자 γ를 사용하여 계산한다. 상태 s에서 정책 π를 따를 때의 상태 가치 V^π(s)는 다음과 같이 정의된다.

V^π(s) = E_π[ G_t | S_t = s ] = E_π[ R_{t+1} + γR_{t+2} + γ²R_{t+3} + ... | S_t = s ]

여기서 E_π는 정책 π 하에서의 기댓값을, G_t는 시간 t부터의 반환값을 의미한다. 할인 인자 γ는 0과 1 사이의 값을 가지며, 먼 미래의 보상일수록 현재 가치가 낮아지도록 조정한다.

상태 가치 함수는 벨만 방정식을 통해 재귀적으로 표현될 수 있다. 이는 현재 상태의 가치가 즉시 받는 보상과 다음 상태들의 가치의 기댓값으로 구성됨을 보여준다. 상태 가치 함수의 벨만 방정식은 다음과 같다.

V^π(s) = Σ_a π(a|s) Σ_{s'} P(s'|s, a) [ R(s, a, s') + γ V^π(s') ]

이 방정식은 동적 프로그래밍이나 시간차 학습과 같은 알고리즘을 통해 가치 함수를 추정하거나 계산하는 데 핵심적인 역할을 한다. 상태 가치 함수를 학습하는 것은 최적 정책을 찾는 과정의 중요한 단계이다.

행동 가치 함수는 정책 π를 따를 때, 특정 상태 s에서 특정 행동 a를 선택한 후, 이후 정책을 계속 따랐을 때 받을 것으로 기대되는 할인된 누적 보상의 기댓값을 나타낸다. 이 함수는 일반적으로 Q^π(s, a) 또는 q_π(s, a)로 표기하며, 큐 함수(Q-function)라고도 불린다. 수식으로는 다음과 같이 정의된다.

Q^π(s, a) = E_π[ G_t | S_t = s, A_t = a ] = E_π[ ∑_{k=0}^{∞} γ^k R_{t+k+1} | S_t = s, A_t = a ]

여기서 E_π는 정책 π 하에서의 기댓값을, γ는 할인 인자를, G_t는 시간 t부터의 반환값을 의미한다.

이 함수는 상태 가치 함수와 밀접한 관계를 가지며, 상태 가치 함수 V^π(s)는 주어진 상태 s에서 가능한 모든 행동 a에 대한 행동 가치의 평균으로 계산될 수 있다. 구체적으로, V^π(s) = ∑_{a ∈ A(s)} π(a|s) Q^π(s, a) 이다. 반대로, 행동 가치 함수는 현재 행동으로 인한 즉시 보상과, 그 행동이 유도할 다음 상태 s'의 상태 가치를 이용해 재귀적으로 표현된다. 이 관계는 벨만 방정식을 통해 다음과 같이 나타난다.

Q^π(s, a) = ∑_{s', r} p(s', r | s, a) [ r + γ V^π(s') ]

여기서 p(s', r | s, a)는 전이 확률을 나타낸다.

행동 가치 함수는 최적 정책을 찾는 데 직접적으로 활용된다. 만약 모든 상태 s와 가능한 행동 a에 대한 최적 행동 가치 함수 Q*(s, a)를 알게 되면, 최적 정책 π*는 각 상태에서 가장 높은 Q값을 주는 행동을 선택하는 탐욕적(greedy) 정책이 된다. 즉, π*(s) = argmax_{a} Q*(s, a) 이다. 이 특성 때문에, 시간차 학습의 한 방법인 Q-러닝과 같은 많은 강화 학습 알고리즘은 행동 가치 함수를 직접 학습하는 방식을 취한다.

최적 정책은 주어진 마르코프 결정 과정에서 에이전트가 얻을 수 있는 누적 기대 보상을 최대화하는 정책을 의미한다. 모든 가능한 정책의 집합을 Π라고 할 때, 최적 정책 π*는 모든 상태 s에 대해, 그리고 모든 정책 π ∈ Π에 대해 그 가치 함수가 V^π*(s) ≥ V^π(s)를 만족하는 정책이다. 즉, 어떤 상태에서 시작하더라도 최적 정책을 따르는 것이 다른 어떤 정책을 따르는 것보다 더 많은 보상을 기대할 수 있다.

최적 정책의 존재는 벨만 방정식을 통해 보장된다. 최적 상태 가치 함수 V*와 최적 행동 가치 함수 Q*는 각각 최적 벨만 방정식을 만족한다. 최적 정책 π*는 일반적으로 각 상태 s에서 최적 행동 가치 함수 Q*(s, a)를 최대화하는 행동 a를 선택하는 탐욕적 정책으로 구성된다. 이는 π*(s) = argmax_a Q*(s, a)로 표현된다.

최적 정책은 항상 결정론적 정책일 수 있다는 것이 알려져 있다. 즉, 각 상태에서 하나의 최적 행동을 확률 1로 선택하는 정책이 항상 존재한다. 또한, 최적 정책은 항상 고정적이며 정상 상태를 유지한다. 시간에 따라 변하지 않는 정책이 최적일 수 있다는 의미이다.

최적 정책을 찾는 것은 마르코프 결정 과정의 핵심 목표이며, 이를 위한 다양한 알고리즘이 개발되었다. 동적 프로그래밍 기반의 값 반복과 정책 반복, 강화 학습의 몬테카를로 방법 및 시간차 학습 등이 모두 궁극적으로 최적 정책 또는 그에 근사하는 정책을 찾아내는 것을 목표로 한다.

벨만 방정식은 마르코프 결정 과정에서 상태 가치 함수나 행동 가치 함수를 재귀적으로 정의하고 계산하는 데 사용되는 기본 방정식이다. 이 방정식은 리처드 벨만의 이름을 따서 명명되었으며, 최적화 문제를 더 작은 하위 문제로 분해하는 동적 프로그래밍 원칙에 기초한다. 벨만 방정식은 현재 상태의 가치가 즉각적인 보상과 미래 상태의 기대 가치의 합이라는 직관을 수학적으로 표현한다.

벨만 방정식은 크게 벨만 기대 방정식과 벨만 최적 방정식으로 구분된다. 벨만 기대 방정식은 주어진 정책 π에 대한 가치 함수를 정의한다. 상태 가치 함수 V^π(s)에 대한 벨만 기대 방정식은 다음과 같다.

V^π(s) = Σ_a π(a|s) Σ_s' P(s'|s,a) [ R(s,a,s') + γ V^π(s') ]

여기서, 기대값은 현재 상태 s에서 정책 π에 따라 행동 a를 선택할 확률과, 그 행동으로 인해 상태 s'로 전이될 확률을 모두 고려하여 계산된다. 행동 가치 함수 Q^π(s,a)에 대한 방정식도 유사하게 정의된다.

반면, 벨만 최적 방정식은 최적 정책 π*에 해당하는 최적 가치 함수를 정의한다. 최적 상태 가치 함수 V*(s)는 가능한 모든 행동 중에서 미래 기대 보상의 합을 최대화하는 행동을 선택함으로써 얻어진다.

V*(s) = max_a Σ_s' P(s'|s,a) [ R(s,a,s') + γ V*(s') ]

최적 행동 가치 함수 Q*(s,a)에 대한 방정식도 존재하며, 이 방정식들의 해가 바로 최적 가치 함수이다. 벨만 최적 방정식은 최적성 원리를 공식화한 것으로, 최적 정책은 현재의 선택이 남은 미래의 결정들도 최적으로 만드는 성질을 가진다.

이 방정식들은 이론적 토대일 뿐만 아니라 실제 알고리즘의 핵심이다. 동적 프로그래밍 기반의 값 반복과 정책 반복 알고리즘은 벨만 방정식을 반복적으로 적용하여 최적 가치 함수와 정책을 찾는다. 또한 시간차 학습과 같은 강화 학습 알고리즘들은 벨만 방정식을 샘플 기반의 추정 문제로 변형하여 온라인 학습을 가능하게 한다.

동적 프로그래밍은 완전한 환경 모델, 즉 상태 전이 확률과 보상 함수를 알고 있을 때 마르코프 결정 과정의 최적 정책을 계산하는 방법이다. 이 방법은 벨만 최적 방정식을 이용하여 체계적으로 문제를 해결한다. 주요 알고리즘으로는 정책 평가, 정책 개선, 그리고 이를 결합한 정책 반복과 가치 반복이 있다.

정책 평가는 주어진 고정된 정책 π에 대한 상태 가치 함수 V^π를 계산하는 과정이다. 벨만 기대 방정식을 업데이트 규칙으로 사용하여 모든 상태의 가치를 반복적으로 계산한다. 이 과정은 가치 함수의 변화가 임계값 이하로 떨어질 때까지 계속된다. 정책 개선은 평가된 가치 함수를 바탕으로 각 상태에서 더 나은 행동을 선택하여 정책을 개선하는 단계이다. 탐욕 정책 개선은 각 상태에서 가장 높은 행동 가치 함수 Q(s,a)를 제공하는 행동을 선택하는 방식으로 이루어진다.

이 두 단계를 번갈아 가며 수행하는 정책 반복 알고리즘은 정책 평가와 정책 개선을 반복하여 최적 정책에 수렴한다. 반면, 가치 반복은 정책 평가와 개선을 명시적으로 분리하지 않고, 벨만 최적 방정식을 직접 반복 적용하여 최적 가치 함수 V*를 먼저 구한다. 이후 최적 가치 함수로부터 탐욕 정책을 추출하여 최적 정책 π*를 얻는다. 두 알고리즘의 특징은 다음과 같다.

동적 프로그래밍 방법은 모델을 완전히 알고 있다는 전제 하에 정확한 해를 보장한다. 그러나 상태 공간이 매우 큰 경우에는 계산 비용이 지나치게 높아지는 차원의 저주 문제에 직면한다. 이 한계를 극복하기 위해 근사 동적 프로그래밍이나 샘플링 기반 방법들이 개발되었다.

몬테카를로 방법은 마르코프 결정 과정의 가치 함수를 추정하거나 최적 정책을 찾기 위해, 실제 또는 시뮬레이션된 경험(에피소드)을 통해 샘플 평균을 계산하는 알고리즘 패밀리를 가리킨다. 이 방법은 환경에 대한 완전한 모델(예: 전이 확률과 보상 함수의 명시적 지식)을 필요로 하지 않는다는 점에서 동적 프로그래밍과 구별된다. 대신, 에이전트가 환경과 상호작용하며 얻은 샘플 보상 시퀀스를 직접 활용한다.

몬테카를로 방법의 핵심은 에피소드 단위의 학습이다. 하나의 에피소드는 초기 상태에서 시작하여 종료 상태에 도달할 때까지의 상태, 행동, 보상의 순서열이다. 특정 정책 하에서 어떤 상태(또는 상태-행동 쌍)의 가치를 추정할 때, 해당 상태를 방문한 모든 에피소드에서 그 이후로 얻은 실제 보상의 할인 총합(또는 평균 보상)을 계산하여 평균낸다. 이는 가치 함수의 정의를 샘플 기반으로 직접 구현한 것이다.

몬테카를로 방법은 크게 예측 문제와 제어 문제로 나뉜다. 예측 문제는 주어진 정책의 상태 가치 함수를 추정하는 것이며, 모든 에피소드가 끝난 후에 가치 추정치를 한 번 업데이트하는 '에피소드 몬테카를로' 방식이 일반적이다. 제어 문제는 최적 정책을 찾는 것으로, 탐험과 활용의 균형을 위해 엡실론-그리디 정책과 같은 탐험적 정책을 사용하며, 추정된 행동 가치 함수를 기반으로 정책을 점진적으로 개선한다.

이 방법의 주요 특징과 고려사항은 다음과 같다.

몬테카를로 방법은 에피소드가 명확하게 종료되는 문제에 효과적으로 적용된다. 그러나 모든 상태를 충분히 방문하기 위해 많은 수의 에피소드가 필요할 수 있으며, 에피소드가 길어질수록 한 에피소드 내에서 학습 정보를 업데이트하는 데 지연이 발생한다는 한계가 있다. 이러한 특성은 단일 스텝 내에서 업데이트가 이루어지는 시간차 학습과 대비된다.

시간차 학습은 강화 학습에서 정책 평가와 최적 정책 탐색을 위해 사용되는 핵심 알고리즘 패밀리이다. 이 방법은 동적 프로그래밍과 몬테카를로 방법의 아이디어를 결합하여, 에피소드가 끝나기를 기다리지 않고 매 단계마다 예측값을 실시간으로 업데이트한다는 특징을 가진다. 이로 인해 온라인 학습과 연속적인 환경에서의 적용이 가능해진다.

시간차 학습의 기본 원리는 현재의 추정값과 그 다음 시점의 추정값(부트스트랩) 사이의 오차, 즉 시간차 오차를 이용하여 가치 함수를 업데이트하는 것이다. 대표적인 알고리즘인 TD(0)는 다음과 같은 업데이트 규칙을 따른다: V(s) ← V(s) + α [r + γV(s') - V(s)]. 여기서 α는 학습률, γ는 할인 인자, r은 즉시 보상, s와 s'은 현재 상태와 다음 상태를 나타낸다. 괄호 안의 항 [r + γV(s') - V(s)]이 시간차 오차이다.

시간차 학습의 주요 변형으로는 SARSA와 Q-러닝이 있다. SARSA는 온-폴리시 학습 알고리즘으로, 현재 정책을 따르는 행동의 가치를 학습한다. 반면 Q-러닝은 오프-폴리시 알고리즘으로, 현재 정책과 관계없이 최적의 행동 가치 함수를 직접 학습한다. 이는 최적 벨만 방정식을 근사적으로 푸는 것으로 이해할 수 있다.

이 방법들의 장점은 모델 없이도 환경과의 상호작용만으로 학습이 가능하며, 몬테카를로 방법에 비해 분산이 낮고 학습 속도가 일반적으로 더 빠르다는 점이다. 단점은 부트스트랩을 사용함으로써 편향이 발생할 수 있으며, 학습률과 탐험 전략 등의 하이퍼파라미터 설정에 민감할 수 있다는 것이다. 이러한 시간차 학습은 현대 강화 학습 알고리즘의 대부분, 특히 딥 Q 네트워크와 같은 방법들의 기초를 이룬다.

부분 관찰 마르코프 결정 과정(POMDP)은 에이전트가 환경의 완전한 상태 정보를 직접 관찰할 수 없는 상황을 모델링한다. 표준 MDP와의 핵심 차이점은 에이전트가 상태(State) 자체를 알지 못하며, 대신 상태에 의존적으로 생성되는 관찰(Observation)과 그 관찰의 확률적 신호만을 받는다는 점이다. 이는 센서 노이즈, 정보의 불완전성, 또는 직접 측정이 불가능한 숨겨진 변수가 존재하는 실제 문제를 반영한다.

POMDP는 7가지 요소 튜플 <S, A, T, R, Ω, O, γ>로 정의된다. 여기서 S, A, T, R, γ는 각각 상태, 행동, 전이 확률, 보상 함수, 할인 인자로 표준 MDP와 동일하다. 추가된 두 요소는 관찰 공간 Ω와 관찰 함수 O이다. 관찰 함수 O(o|s', a)는 행동 a를 취한 후 상태가 s'가 되었을 때, 관찰 o를 받을 조건부 확률을 나타낸다. 에이전트는 매 시간 단계마다 이 관찰과 이전 행동에 기반하여 환경의 실제 상태에 대한 확률적 신념(Belief)을 유지하고 업데이트한다.

에이전트의 핵심 임무는 이 신념 상태(Belief State)를 기반으로 최적의 행동을 결정하는 것이다. 신념 상태 b(s)는 현재 실제 상태가 s일 확률 분포를 나타내는 벡터이다. 새로운 관찰과 행동을 받으면, 베이즈 정리를 적용하여 신념 상태를 업데이트한다. 이로 인해 POMDP 문제는 연속적인 신념 공간 상의 MDP 문제로 변환될 수 있지만, 그 복잡도는 매우 높아진다.

POMDP의 해결은 계산적으로 매우 어려운 문제로 알려져 있다. 정확한 해법은 작은 문제에만 적용 가능하며, 일반적으로 근사적 해법을 사용한다. 대표적인 해법에는 신념 공간을 이산화하는 그리드 기반 방법, 신념 상태를 나타내는 키 샘플을 사용하는 포인트 기반 값 반복, 그리고 딥 러닝을 활용하여 신념을 표현하고 정책을 학습하는 방법 등이 있다.

계층적 마르코프 결정 과정은 복잡한 의사결정 문제를 여러 수준의 추상화된 하위 작업으로 분해하여 해결하는 MDP의 변형이다. 이 접근법은 인간이 복잡한 작업을 계층적으로 세분화하여 처리하는 방식에서 영감을 받았다. 계층 구조를 통해 전체 상태 공간과 행동 공간을 더 작고 관리 가능한 단위로 나누어, 계산 복잡성을 줄이고 학습 효율성을 높이는 것이 핵심 목표이다.

계층적 MDP의 일반적인 구조는 최상위 수준의 메인 태스크와 이를 구성하는 여러 하위 태스크로 이루어진다. 각 하위 태스크는 자체적인 상태, 행동, 보상을 가질 수 있으며, 상위 정책은 어떤 하위 태스크를 언제 실행할지 결정한다. 하위 태스크가 완료되면 상위 수준으로 제어권이 돌아오고, 상위 정책은 다음 하위 태스크를 선택한다. 이때 하위 태스크의 실행은 그 자체로 더 낮은 수준의 MDP 또는 원시 행동의 시퀀스가 될 수 있다.

주요 구현 프레임워크로는 옵션(Options) 이론이 널리 알려져 있다. 옵션은 초기 상태에서 종료 상태까지의 정책, 종료 조건, 시작 집합으로 정의되는 하위 정책의 단위이다. 최상위 정책은 원시 행동 대신 이러한 옵션을 선택하며, 옵션이 실행되는 동안은 내부 정책에 따라 행동이 결정된다. 이 외에도 MAXQ 값 함수 분해나 HAM(계층적 추상 기계) 같은 다른 형태의 계층적 분해 방법도 존재한다.

계층적 접근법의 장점은 다음과 같이 정리할 수 있다.

이러한 특성 덕분에 계층적 MDP는 로봇 작업 조립, 장기적인 전략 게임, 복잡한 내비게이션 과제 등에서 효과적으로 적용된다.

평균 보상 마르코프 결정 과정은 할인 인자를 사용하는 표준 MDP와 달리, 장기적인 시간 평균 보상을 최대화하는 것을 목표로 한다. 이 접근법은 시스템이 무한 시간 동안 운영될 때, 각 단계에서 얻는 보상의 평균율을 최적화하는 문제에 적합하다. 특히 통신 네트워크, 생산 라인 관리, 큐잉 시스템 등 안정적인 장기 성능이 중요한 분야에서 널리 적용된다.

평균 보상 MDP의 목표 함수는 일반적으로 다음과 같이 정의된다. 정책 π를 따를 때의 평균 보상 ρ(π)는 시간 단계 t가 무한대로 갈 때, 기대 누적 보합의 시간당 평균 극한값이다[4] 로 표현됨]. 이는 단위 시간당 얻는 보상의 장기 평균율을 의미하며, 할인되지 않은 보상의 극한 행동을 포착한다.

이 모델을 해결하기 위한 주요 알고리즘으로는 상대값 반복과 평균 보상 동적 프로그래밍이 있다. 이 방법들은 상태의 상대적 가치 차이를 추정하면서 평균 보상율을 동시에 계산한다. 또한, 강화 학습 분야에서는 평균 보상 시간차 학습 알고리즘도 연구되어 왔다. 이러한 알고리즘들은 할인 인자 γ를 1에 매우 가깝게 설정한 표준 MDP 해법과는 근본적으로 다른 접근법을 요구한다.

평균 보상 MDP의 주요 장점은 할인 인자 선택에 대한 민감도가 없으며, 무한 수평 문제에서 발생할 수 있는 보상의 발산 문제를 피할 수 있다는 점이다. 반면, 초기 일시적 현상의 효과가 장기 평균에 미치는 영향이 상대적으로 작아지므로, 초기 상태의 중요성이 감소한다는 특징도 있다.

마르코프 결정 과정은 강화 학습의 수학적 기초를 제공하는 핵심적인 프레임워크이다. 강화 학습은 에이전트가 환경과 상호작용하며 보상을 최대화하는 행동을 학습하는 머신 러닝 패러다임으로, MDP는 이러한 상호작용을 모델링하는 표준적인 형식을 정의한다. MDP의 구성 요소인 상태, 행동, 전이 확률, 보상 함수는 강화 학습 문제를 공식화하는 데 직접적으로 사용된다.

강화 학습 알고리즘의 주요 목표는 최적 정책을 찾는 것이다. 이를 위해 벨만 방정식을 기반으로 한 상태 가치 함수나 행동 가치 함수를 추정하고 개선하는 과정을 반복한다. 대표적인 해결 방법으로는 동적 프로그래밍, 몬테카를로 방법, 시간차 학습이 있으며, 이들은 모두 MDP의 가정 하에서 수렴성이 보장된다. 특히 시간차 학습은 Q-러닝과 같은 알고리즘의 기반이 되어, 모델(전이 확률)을 알지 못하는 경우에도 최적 정책을 학습할 수 있게 한다.

따라서, 강화 학습 이론의 대부분은 MDP 또는 그 변형(예: 부분 관찰 MDP)을 전제로 발전해왔다. 정책 경사 방법과 같은 최신 알고리즘들도 궁극적으로는 MDP 설정 하에서 누적 보상의 기댓값을 최대화하는 문제를 푸는 것으로 이해할 수 있다.

추천 시스템은 사용자에게 관심 있을 만한 아이템(영화, 음악, 상품, 뉴스 등)을 제안하는 시스템이다. 마르코프 결정 과정은 이러한 시스템을 모델링하고 최적화하는 데 효과적인 프레임워크를 제공한다. MDP를 적용할 때, 시스템의 상태(State)는 사용자의 현재 상황(예: 최근 본 아이템 목록, 프로필 정보, 세션 정보)으로 정의된다. 행동(Action)은 특정 아이템을 사용자에게 추천하는 것이며, 보상 함수(Reward Function)는 사용자의 피드백(클릭, 구매, 시청 시간, 평점)을 통해 얻어진다. 목표는 사용자의 장기적 만족도(예: 총 시청 시간 또는 재방문율)를 극대화하는 추천 정책(Policy)을 학습하는 것이다.

기존의 협업 필터링이나 콘텐츠 기반 필터링은 주로 즉각적인 반응(클릭률)을 예측하는 데 초점을 맞추지만, MDP 기반 접근법은 추천의 순차적 특성을 명시적으로 고려한다. 하나의 추천이 사용자의 다음 상태(관심사 변화)를 바꾸고, 이는 향후 추천의 효과에 영향을 미친다. 예를 들어, 사용자에게 한 장르의 영화만 반복적으로 추천하면 단기 클릭은 얻을 수 있지만, 사용자의 흥미가 빠르게 식어 장기적 참여도를 떨어뜨릴 수 있다. MDP는 이러한 시간적 의존성과 장기적 보상을 최적화 문제로 공식화한다.

MDP 기반 추천 시스템의 구현은 몇 가지 주요 과제를 안고 있다. 상태 공간과 행동 공간이 매우 크기 때문에 벨만 방정식(Bellman Equation)을 직접 풀기 어렵다. 따라서 함수 근사(Function Approximation)와 결합된 강화 학습 알고리즘, 특히 시간차 학습이나 딥 Q-네트워크 같은 방법이 자주 사용된다. 또한, 보상 신호가 희소하거나 지연될 수 있으며(예: 구매는 드물게 발생), 사용자의 선호도가 시간에 따라 변하는 문제도 해결해야 한다.

이러한 MDP 기반 프레임워크는 전통적 방법으로는 포착하기 어려운 사용자의 복잡한 의사 결정 과정과 진화하는 선호도를 모델링할 수 있어, 보다 개인화되고 적응적인 추천을 가능하게 한다.

로봇 제어와 자율 주행은 마르코프 결정 과정이 실제 세계 문제에 적용되는 대표적인 분야이다. 이 분야에서 로봇이나 자율 주행 차량은 에이전트가 되며, 센서를 통해 인지한 환경 정보(예: 위치, 장애물 거리, 차선)는 상태(State)를 구성한다. 에이전트는 주어진 상태에서 이동, 회전, 가속, 감속 등의 행동(Action)을 선택하고, 이를 통해 환경과 상호작용한다. 목표는 안전하게 목적지에 도달하거나, 에너지를 효율적으로 사용하거나, 주행 시간을 최소화하는 것과 같은 누적 보상 함수(Reward Function)을 최대화하는 정책(Policy)을 학습하는 것이다.

자율 주행의 경로 계획 및 제어 문제는 MDP로 모델링된다. 예를 들어, 상태는 차량의 위치, 속도, 주변 차량의 상대적 위치, 신호등 상태 등을 포함할 수 있다. 행동은 조향각과 가속/제동의 조합이다. 보상은 목표 지점에 도달하면 큰 양의 보상을, 충돌이나 차선 이탈에는 큰 음의 보상을, 효율적인 주행에는 작은 양의 보상을 부여하는 방식으로 설계된다. 환경의 불확실성(예: 다른 차량의 움직임, 감지 오차)은 전이 확률(Transition Probability)로 표현된다.

이러한 MDP 모델을 해결하기 위해 강화 학습 알고리즘이 널리 사용된다. 심층 강화 학습은 심층 신경망을 가치 함수나 정책의 근사자로 사용하여 고차원의 상태 공간(예: 카메라 이미지)을 직접 처리할 수 있게 한다. 이를 통해 로봇은 시뮬레이션 환경이나 실제 주행 데이터를 통해 복잡한 작업을 점진적으로 학습한다. 예를 들어, 로봇 팔이 물체를 잡는 동작을 학습하거나, 자율 주행 차량이 복잡한 교차로를 통과하는 정책을 학습하는 데 적용된다.

이러한 접근법의 핵심 과제는 시뮬레이션과 현실의 차이, 안전성 보장, 그리고 방대한 상태-행동 공간에서의 효율적인 탐색과 학습이다.

마르코프 결정 과정을 구현하고 실험하는 데 널리 사용되는 프로그래밍 라이브러리들이 존재한다. 이 라이브러리들은 강화 학습 알고리즘의 구현, 환경 모델링, 에이전트 훈련을 위한 표준화된 인터페이스와 도구를 제공한다.

가장 대표적인 라이브러리로는 OpenAI의 Gym(현재 Gymnasium)이 있다. 이는 다양한 에이전트와 환경 간의 상호작용을 위한 표준 API를 정의하며, 클래식 제어, 아타리 2600 게임, 로봇 시뮬레이션 등 수백 가지의 벤치마크 환경을 포함한다. 딥마인드의 DM Control은 물리 엔진 MuJoCo를 기반으로 한 정밀한 로봇 제어 환경을 제공한다. 파이썬 생태계에서는 Stable-Baselines3가 신경망 기반의 강화 학습 알고리즘(PPO, A2C, DQN 등)을 구현한 안정적인 라이브러리로 널리 사용된다.

다른 주요 라이브러리와 그 특징은 다음과 같다.

이러한 도구들은 이론적인 MDP 모델을 실제 코드로 구현하고, 다양한 정책을 평가하며, 복잡한 문제에 대한 최적 또는 근사 최적 정책을 학습하는 데 필수적이다.

시뮬레이션 환경은 마르코프 결정 과정 모델을 구현하고, 다양한 강화 학습 알고리즘을 개발, 테스트, 평가하기 위한 가상의 플랫폼이다. 이 환경은 에이전트가 상호작용할 수 있는 상태 공간, 행동 공간, 전이 역학, 보상 구조를 정의한다. 연구와 실무에서 표준화된 시뮬레이션 환경을 사용함으로써 알고리즘의 성능을 공정하게 비교하고 재현성을 확보할 수 있다.

고전적인 환경으로는 그리드 월드, 산악차 오르기, 카트폴, 얼음 호수 같은 단순한 제어 문제가 있다. 더 복잡한 도메인을 위한 환경으로는 Atari 2600 게임 에뮬레이터, MuJoCo 물리 엔진 기반의 로봇 모션 제어 태스크, OpenAI Gym의 "Classic Control" 및 "Box2D" 세트가 널리 사용된다. 최근에는 자율 주행 시뮬레이션([7]), 다중 에이전트 협력 및 경쟁 환경([8]), 그리고 실제 데이터를 기반으로 한 산업 문제(예: 추천 시스템, 자원 관리)를 위한 맞춤형 환경도 활발히 개발되고 있다.

이러한 환경들은 일반적으로 Python 인터페이스를 제공하며, 다음 표와 같은 핵심 기능을 표준화하여 제공한다.

주요 오픈소스 라이브러리로는 OpenAI Gym(및 후속 프로젝트인 Gymnasium)이 사실상의 표준으로 자리 잡았으며, 통합된 인터페이스를 통해 수백 가지 환경에 접근할 수 있게 한다. 그 외에도 DeepMind의 dm_control, Facebook의 TorchRL, 군사 훈련 시뮬레이션에 쓰이는 JAUS 표준 기반 환경 등이 특정 분야에서 활용된다.