Skip to main content

MDP and Bellman Equations

Markov Decision Process (MDP) は、RL のほぼすべての algorithm の基礎です。MDP と Bellman equation を理解しておくと、Q-learning、policy gradient、PPO、DPO まで自然に繋がります。

MDP の定義​

M=(S,A,P,R,γ)M = (\mathcal{S}, \mathcal{A}, P, R, \gamma)
  • S\mathcal{S}: state space
  • A\mathcal{A}: action space
  • P(s′∣s,a)P(s' \mid s, a): 遷移確率
  • R(s,a)R(s, a): reward function
  • γ∈[0,1)\gamma \in [0, 1): discount factor

Markov 性: 次状態は 直前の状態と行動のみ に依存。

Policy と return​

Policy は state から action への写像 (確率的または決定的) です。

π(a∣s)=Pr⁡(At=a∣St=s)\pi(a \mid s) = \Pr(A_t = a \mid S_t = s)

時刻 tt から先の discounted return:

Gt=∑k=0∞γkRt+k+1G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}

Value function​

State-value function:

Vπ(s)=Eπ[Gt∣St=s]V^{\pi}(s) = \mathbb{E}_{\pi}[G_t \mid S_t = s]

Action-value function:

Qπ(s,a)=Eπ[Gt∣St=s,At=a]Q^{\pi}(s, a) = \mathbb{E}_{\pi}[G_t \mid S_t = s, A_t = a]

Bellman expectation equation​

VπV^\pi は再帰的に書けます。

Vπ(s)=∑aπ(a∣s)∑s′,rP(s′,r∣s,a)[r+γVπ(s′)]V^{\pi}(s) = \sum_{a} \pi(a \mid s) \sum_{s', r} P(s', r \mid s, a)\bigl[r + \gamma V^{\pi}(s')\bigr]

同様に Q について:

Qπ(s,a)=∑s′,rP(s′,r∣s,a)[r+γ∑a′π(a′∣s′) Qπ(s′,a′)]Q^{\pi}(s, a) = \sum_{s', r} P(s', r \mid s, a)\bigl[r + \gamma \sum_{a'} \pi(a' \mid s')\, Q^{\pi}(s', a')\bigr]

これが Bellman expectation equation です。Iterative policy evaluation の根拠になります。

Bellman optimality equation​

最適 policy π∗\pi^* に対しては:

V∗(s)=max⁡a∑s′,rP(s′,r∣s,a)[r+γV∗(s′)]V^{*}(s) = \max_a \sum_{s', r} P(s', r \mid s, a)\bigl[r + \gamma V^{*}(s')\bigr] Q∗(s,a)=∑s′,rP(s′,r∣s,a)[r+γmax⁡a′Q∗(s′,a′)]Q^{*}(s, a) = \sum_{s', r} P(s', r \mid s, a)\bigl[r + \gamma \max_{a'} Q^{*}(s', a')\bigr]

これが Q-learning の基礎です。

Policy iteration と Value iteration​

  • Policy iteration: 評価と greedy 改善を交互に繰り返す
  • Value iteration: Bellman optimality を直接 fixed-point 反復

理論的には収束しますが、現実の MDP は state が巨大なので、function approximator (NN) を使って Q や V を近似します。

関連ページ​

主なソース​