Markov Decision Process (MDP)

• 다른 이름: MDP
• 카테고리: Learning & autonomy › RL & simulation
• 태그: reinforcement-learning, decision-making, dynamic-programming, probability, robot-learning

순차적 의사결정의 표준 수학 모델로, 상태, 행동, 전이 확률, 보상, 할인율로 이루어지며 다음 상태는 현재 상태와 행동에만 의존한다.

정의

마르코프 결정 과정(Markov decision process, MDP)은 상태를 반복해서 관측하고, 행동을 선택하고, 보상을 받고, 새로운 상태로 이동하는 에이전트를 기술한다. 보통 튜플 (S, A, P, R, γ)로 쓰며, 초기 상태 분포 ρ₀가 함께 붙는 경우가 많다. 각각 상태 공간, 행동 공간, 전이 확률 P(s′ | s, a), 보상 함수 R(s, a), 그리고 미래 보상과 즉각적인 보상 사이의 가중치를 정하는 0과 1 사이의 할인율 γ이다. 핵심 가정은 마르코프 성질(Markov property)이다. 다음 상태의 분포는 현재 상태와 행동에만 의존하며, 그 상태에 이르기까지의 이력에는 의존하지 않는다. 1950년대 Richard Bellman의 동적 계획법 연구가 이 틀을 확립했다.

MDP에서의 목표는 기대 할인 보상 합을 최대화하는 정책(policy), 즉 상태에서 행동으로(또는 행동에 대한 분포로) 가는 사상이다. 가치 함수 V(s)와 행동 가치 함수 Q(s, a)는 어떤 정책 아래에서 한 상태로부터, 또는 한 상태와 행동으로부터 얻는 기대 리턴을 나타낸다. 이 함수들은 벨만 방정식(Bellman equations)을 만족하며, 벨만 방정식은 한 상태의 가치를 즉각적인 보상에 뒤따르는 상태들의 할인된 가치를 더한 것으로 표현한다. P와 R이 알려져 있고 상태 공간이 작으면 가치 반복과 정책 반복으로 MDP를 정확히 풀 수 있다. 이들이 알려져 있지 않거나 공간이 크고 연속적이면, 강화 학습이 샘플링된 경험으로부터 가치와 정책을 추정한다.

MDP는 거의 모든 강화 학습, 그리고 불확실성 아래에서의 계획 중 상당 부분의 형식적 기반이다. 많은 변형이 가정 중 하나를 완화한다. 부분 관측 MDP(POMDP)는 에이전트가 실제 상태를 본다는 가정을 없애고, 제약 MDP는 비용 한도를 추가하며, 세미 MDP(semi-MDP)는 걸리는 시간이 가변적인 행동을 허용하고, 마르코프 게임 같은 다중 에이전트 확장은 여러 의사결정자를 모델링한다. 상태에 무엇을 넣을지는 공학적 결정이다. 속도, 접촉 상태, 다른 에이전트의 의도 같은 중요한 정보가 빠지면, 에이전트의 관점에서 그 과정은 더 이상 마르코프 과정이 아니다.

중요한 이유

모든 강화 학습 논문과 로봇공학의 대부분의 의사결정 방법은 문제를 MDP나 그 변형으로 정식화한다. 튜플의 구성 요소와 각 방법이 어떤 가정에 의존하는지를 알면, 그런 논문을 읽고, 실제 로봇을 위한 상태와 보상을 설계하고, 문제가 실제로는 부분 관측 문제인 경우를 알아볼 수 있다.

주요 응용

• 조작과 이동을 위한 강화 학습 문제의 정식화
• 가치 반복과 정책 반복을 이용한 불확실성 아래에서의 계획
• R을 추론하거나 형성하는 보상 설계와 역강화 학습
• 전이 함수 P를 학습하는 모델 기반 강화 학습
• 마르코프 게임과 잠재 의도 변수를 통한 다른 에이전트와의 상호작용 모델링

실제 사례

로봇 암이 블록을 목표 지점까지 밀도록 학습시키는 팀은 이 작업을 MDP로 정식화한다. 상태에는 관절 각도와 속도, 블록 자세, 목표 위치가 들어 있고, 행동은 제어 단계마다의 엔드 이펙터 위치 변화이며, 보상은 블록과 목표 사이 거리의 음수에 성공 시 보너스를 더한 것이고, 작업이 많은 단계에 걸치므로 γ는 1에 가깝게 설정한다. 초기 시험에서 정책은 블록이 움직이고 있을 때 불규칙하게 동작한다. 상태에 블록 자세는 들어 있지만 블록 속도는 들어 있지 않기 때문이다. 블록 속도를 추가하거나 최근 몇 개의 관측을 쌓으면 마르코프 성질이 충분히 회복되어, SAC나 PPO 같은 표준 알고리즘이 안정적으로 학습한다.

흔한 오해

• MDP에는 이산적인 상태와 행동이 필요하다 — 로봇공학에서는 연속 상태 공간과 연속 행동 공간이 흔하며, 이때 합은 적분으로, 표 형식 방법은 함수 근사로 대체된다
• 마르코프 성질은 세계에 관한 사실이다 — 이는 선택한 상태의 성질이다. 속도나 숨은 변수를 빠뜨리면 물리 시스템이 에이전트의 관점에서 비마르코프적이 될 수 있다
• 할인율은 조급함만을 반영한다 — 할인율은 무한 구간 문제에서 리턴을 유계로 만들고 학습의 분산과 안정성에도 영향을 주므로, 흔히 하이퍼파라미터처럼 조정된다
• MDP를 풀려면 P의 모델이 필요하다 — 강화 학습 방법은 P를 한 번도 적어 내리지 않고도 샘플링된 전이로부터 좋은 정책을 찾는다

알아야 할 사람

• 강화 학습 실무자와 연구자
• 상태, 행동, 보상을 설계하는 로봇 학습 엔지니어
• 계획 및 의사결정 연구자
• 로봇 학습을 시작하는 로봇공학 학생

관련 기술

• 벨만 방정식(Bellman Equation)
• 가치 반복(Value Iteration)
• 정책 반복(Policy Iteration)
• Q-Learning
• Gymnasium
• 동적 계획법(Dynamic Programming)

관련 용어

• Reinforcement Learning
• Partially Observable Markov Decision Process (POMDP)
• Hamilton-Jacobi-Bellman Equation (HJB)
• Inverse Reinforcement Learning
• Offline Reinforcement Learning
• Proximal Policy Optimization

관련 프로젝트

• LeRobot: HuggingFace ML library for real-world robotics in PyTorch
• MuJoCo: DeepMind physics engine for robotics and ML research
• PyBullet: Python physics simulator for robotics and RL research with fast CPU-based simulation
• OpenPI: Physical Intelligence VLA foundation models for general robot control
• Microduck: Pollen Robotics' $399 walking duck robot: open-source software, closed hardware
• Isaac Lab: NVIDIA robot learning framework: one task API across Newton, PhysX and Isaac Sim

동영상

• Markov Decision Processes - Computerphile: Computerphile