마르코프 결정 과정
‘한 걸음씩 결정하는 일’을 다섯 기호로 적는다. 강화학습의 모든 것이 여기서 시작된다
이 페이지의 본문은 영어로 제공됩니다. 제목과 요약은 한국어로 번역되었습니다.
정의
A Markov decision process (MDP) describes sequential decision-making with the five-tuple ⟨S, A, P, R, γ⟩: the agent sits in a state s ∈ S, chooses an action a ∈ A, the environment moves to a new state under the transition probability P(s′ | s, a) and emits a reward R, and future rewards are discounted by γ. It is the standard formalism of reinforcement learning: it fixes what the problem is, leaving only how to solve it.
직관적 이해
Picture playing a board game you have never seen. The board right now is the "state"; each move open to you is an "action"; how the board changes and how many points you gain are fixed by the "transition" and the "reward". The whole model rests on a single assumption: what happens next depends only on the present position, not on how you got there. That "only the present counts" property is the Markov property, and it is what allows the problem to be written down mathematically at all.
The agent–environment loop: observe a state → choose an action → receive a reward → reach a new state, again and again
The discount factor sets how far the agent looks: the weight on a reward k steps ahead is γ^k — at γ=0.99 it is still near 0.9 after ten steps, while at γ=0.5 it has decayed to one eighth in three
- γ = 0.99 (far-sighted)
- γ = 0.9
- γ = 0.5 (short-sighted)
작동 원리
- 01
Step 1 · Define states and actions
First decide what the world must be compressed into. A state should contain everything needed for an optimal decision — any more is wasteful, any less breaks the Markov property. The action space may be discrete (up/down/left/right, a move) or continuous (steering angle, joint torque).
- 02
Step 2 · Specify transitions and rewards
The transition probability P(s′ | s, a) says "given this state and action, how the world changes"; the reward R(s, a) scores that single step. Together they define the task itself — change the reward function and you have an entirely different problem, which is why reward design is often said to be harder than the algorithm.
- 03
Step 3 · Discount the future
Multiply each reward by γ^k and sum to get the discounted return. A γ near 1 makes the agent patient, willing to sacrifice now for later; a γ near 0 makes it short-sighted. For tasks that might never end, γ < 1 also guarantees the return stays finite.
- 04
Step 4 · Introduce policy and value functions
A policy π(a | s) is the rule for which action to take in each state — the object every algorithm ultimately learns. Value functions estimate how much return following a policy yields. Once the MDP is fixed, solving it reduces to one sentence: find the policy that maximises expected discounted return.
핵심 수식
G_t = r_{t+1} + γ r_{t+2} + γ² r_{t+3} + …응용 분야
- Robot control: arm positions and joint angles form the state, torques or target poses are the actions
- Game AI: Go and StarCraft are cast as MDPs, with the board as state and moves or commands as actions
- Recommendation and ads: user history is the state, the served item is the action, clicks or dwell time is the reward
- Resource scheduling: data-centre cooling and grid balancing write energy or cost as a negative reward
흔한 오해
- Real problems rarely satisfy the Markov property exactly. A single current frame is often not enough, so history must be stacked or memory introduced — that is a partially observable MDP (POMDP), which is substantially harder than an MDP.
- The reward function is not neutral. Write one term wrongly and the agent optimises something you never intended — reward hacking. The MDP framework guarantees correct solving, not that you asked the right question.
- The stationarity assumption is easy to overlook: P and R are assumed not to change over time, yet real systems drift (shifting tastes, ageing hardware), which calls for separate non-stationary methods.
핵심 용어
- State S
- The variables describing the present situation; must satisfy the Markov property
- Action A
- What the agent can do; either discrete or continuous
- Discount factor γ
- Between 0 and 1; how much future rewards are valued
- Policy π
- A mapping from states to actions, or to a distribution over actions