マルコフ決定過程
「一歩ずつ決める」ことを五つの記号で書き表す。強化学習はここから始まる
本ページの本文は英語で提供されています。タイトルと導入は日本語化されています。
定義
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