MDP를 그래프로 그리면 강화학습의 의사결정 구조가 보인다

노드는 상태, 에지는 행동인 그래프

MDP(Markov Decision Process) 그래프는 강화학습(Reinforcement Learning)의 수학적 프레임워크이자 의사결정 모델링의 핵심 구조다. 불확실성이 존재하는 환경에서 최적의 의사결정을 내리기 위한 이론적 기반을 제공한다.

MDP는 상태 집합(S), 행동 집합(A), 전이 확률(P), 보상 함수(R), 할인 인자(γ)로 구성된 튜플 <S, A, P, R, γ>로 정의된다.

• 상태 집합(S): 환경이 취할 수 있는 모든 가능한 상태들의 집합
• 행동 집합(A): 에이전트가 취할 수 있는 모든 가능한 행동들의 집합
• 전이 확률(P): 현재 상태와 행동이 주어졌을 때 다음 상태로 전이될 확률
• 보상 함수(R): 특정 상태에서 특정 행동을 취했을 때 얻게 되는 즉각적인 보상
• 할인 인자(γ): 미래 보상의 현재 가치 반영 비율 (0 ≤ γ ≤ 1)

MDP는 방향성 그래프(Directed Graph)로 표현할 수 있다. 노드는 상태를, 에지는 행동을 나타내며 각 에지에는 전이 확률과 보상이 레이블로 표시된다.

⤢✕

미래는 현재에만 의존한다는 마르코프 속성

MDP의 핵심 특성인 마르코프 속성은 "미래는 현재에 의해서만 결정되고, 과거는 영향을 미치지 않는다"는 것을 의미한다. 수학적으로 표현하면 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)다.

이 특성은 MDP 모델링의 단순화를 가능하게 하며, 현재 상태만 알면 최적의 결정을 내릴 수 있다는 것을 의미한다.

상태 가치와 행동 가치를 정의하는 함수

MDP에서 최적의 정책을 찾기 위해 두 가지 중요한 가치 함수를 정의한다.

상태 가치 함수(State Value Function) V(s)는 상태 s에서 시작하여 정책 π를 따를 때 얻을 수 있는 기대 누적 보상이다. V^π(s) = E_π[R_t+1 + γR_t+2 + γ^2R_t+3 + ... | S_t = s]

행동 가치 함수(Action Value Function) Q(s,a)는 상태 s에서 행동 a를 취하고 그 이후 정책 π를 따를 때 얻을 수 있는 기대 누적 보상이다. Q^π(s,a) = E_π[R_t+1 + γR_t+2 + γ^2R_t+3 + ... | S_t = s, A_t = a]

벨만 방정식이 가치 함수를 재귀적으로 묶는다

벨만 방정식은 가치 함수 간의 재귀적 관계를 수립하는 핵심 방정식이다.

상태 가치 함수의 벨만 방정식은 V^π(s) = ∑a π(a|s) ∑{s'} P(s'|s,a)[R(s,a,s') + γV^π(s')]다.

행동 가치 함수의 벨만 방정식은 Q^π(s,a) = ∑{s'} P(s'|s,a)[R(s,a,s') + γ ∑{a'} π(a'|s')Q^π(s',a')]다.

최적 가치 함수의 벨만 최적성 방정식은 V*(s) = maxa ∑{s'} P(s'|s,a)[R(s,a,s') + γV*(s')], Q*(s,a) = ∑{s'} P(s'|s,a)[R(s,a,s') + γ max{a'} Q*(s',a')]다.

다이나믹 프로그래밍으로 정책을 찾는 방법

가치 반복법(Value Iteration)은 모든 상태의 가치 함수를 반복적으로 업데이트하며, 수렴할 때까지 벨만 최적성 방정식을 적용한다.

⤢✕

정책 반복법(Policy Iteration)은 정책 평가와 정책 개선을 번갈아가며 수행한다. 현재 정책에 대한 가치 함수를 계산한 후, 더 나은 정책으로 업데이트한다.

⤢✕

환경 모델 없이 배우는 방법

Q-학습(Q-Learning)은 환경 모델 없이 경험을 통해 최적 행동 가치 함수를 학습한다. Q(s,a) ← Q(s,a) + α[r + γ max_a' Q(s',a') - Q(s,a)]

SARSA(State-Action-Reward-State-Action)는 현재 정책을 따르는 온-폴리시(on-policy) 학습 방법이다. Q(s,a) ← Q(s,a) + α[r + γQ(s',a') - Q(s,a)]

상태·행동 공간의 형태에 따라 갈리는 MDP 유형

유한 MDP(Finite MDP)는 상태와 행동의 집합이 유한한 경우로, 대부분의 기본 알고리즘은 유한 MDP를 가정한다.

연속 MDP(Continuous MDP)는 상태나 행동 공간이 연속적인 경우로, 함수 근사(Function Approximation)를 통해 접근한다. 딥 러닝 기반 강화학습에서 주로 다룬다.

부분 관측 가능 MDP(POMDP)는 에이전트가 환경의 상태를 완전히 관측할 수 없는 경우로, 복잡성이 크게 증가한다. 신념 상태(Belief State)라는 개념을 도입하여 문제를 해결한다.

로봇 제어부터 클라우드 자원 관리까지

로봇이 주어진 환경에서 최적의 경로를 찾아 목표에 도달하는 문제는 MDP로 모델링할 수 있다. 상태(S)는 로봇의 위치·방향·주변 환경 정보, 행동(A)은 전진·후진·좌회전·우회전 등의 동작, 전이 확률(P)은 로봇 동작의 불확실성(미끄러짐, 센서 오차 등), 보상(R)은 목표 도달 시 높은 보상과 장애물 충돌 시 패널티, 할인 인자(γ)는 미래 이동의 중요도를 나타낸다.

클라우드 컴퓨팅 환경에서 서버 자원을 효율적으로 할당하는 문제도 MDP로 모델링할 수 있다. 상태(S)는 현재 서버 부하와 사용자 요청 대기열 상태, 행동(A)은 서버 증설·축소·자원 재할당, 전이 확률(P)은 사용자 요청 패턴의 변화, 보상(R)은 서비스 성능과 운영 비용의 균형, 할인 인자(γ)는 단기적 vs 장기적 최적화 균형점이다.

⤢✕

체스, 바둑과 같은 게임에서 최적의 수를 찾는 문제도 MDP로 다룰 수 있다. 상태(S)는 게임판의 현재 상태, 행동(A)은 가능한 모든 합법적 수, 전이 확률(P)은 결정론적 게임에서는 1.0, 보상(R)은 승리 시 높은 보상과 패배 시 높은 패널티, 할인 인자(γ)는 게임의 장기적 전략 중요도다.

계층적·다중 에이전트·역방향으로 확장하는 MDP

계층적 강화학습(Hierarchical RL)은 복잡한 문제를 하위 작업들로 분해하여 계층적으로 해결하는 접근법이다. 옵션(Options) 프레임워크, MAXQ 분해 등의 방법이 있다.

멀티 에이전트 MDP(Multi-Agent MDP)는 여러 에이전트가 동시에 의사결정을 하는, 보다 복잡한 환경을 다룬다. 협력적, 경쟁적, 혼합 상황에 따라 접근법이 달라진다.

⤢✕

역강화학습(Inverse RL)은 전문가의 행동을 관찰하여 보상 함수를 추론하는 방법이다. 보상 함수가 명시적으로 정의되기 어려운 상황에서 유용하다.

MDP를 실제로 짤 때 고민해야 할 것들

상태 공간 설계에서는 문제의 본질을 반영하는 상태 표현 선택이 중요하다. 상태 공간이 너무 크면 차원의 저주(Curse of Dimensionality) 문제가 발생하므로 적절한 추상화(Abstraction)를 통해 상태 공간을 축소한다.

보상 설계는 에이전트의 행동에 직접적인 영향을 미친다. 희소 보상(Sparse Reward) 문제는 보상 형성(Reward Shaping)으로 해결하며, 단기적 목표와 장기적 목표 간의 균형을 유지해야 한다.

탐색과 활용의 균형(Exploration vs Exploitation)은 ε-greedy, 소프트맥스(Softmax), UCB(Upper Confidence Bound) 등의 전략을 활용한다. 학습 초기에는 탐색, 후기에는 활용에 중점을 두는 전략을 설계한다.

그래프 한 장으로 읽는 의사결정 문제

MDP 그래프는 불확실성이 있는 환경에서의 의사결정 문제를 모델링하는 강력한 수학적 프레임워크다. 마르코프 속성을 바탕으로 현재 상태만으로 최적의 의사결정이 가능하며, 다양한 알고리즘을 통해 최적 정책을 도출할 수 있다. 로봇 제어, 자원 관리, 게임 AI 등 다양한 분야에 적용 가능하며, 복잡한 현실 세계 문제를 해결하기 위한 확장 모델도 계속 연구되고 있다.