2章　マルコフ決定過程

• バンディット問題ではエージェントの行動に関わらず、問題は毎回同じ
• 現実の問題は、エージェントの行動によって状況が変わる→マルコフ決定過程として定式化
• マルコフ決定過程（MDP：Markov Decision Process）

2.1.1　MDPの具体例

図2-1, 2-2

• エージェント：ロボット
• 環境：その周り
• 報酬：りんご+1, 爆弾-2, その他0
  エージェントの行動によっておかれる状況が変わっている
  行動によって変わる状況 ⇒ **状態（state）**と呼ばれる

この問題の最適な行動は左へ2回進むこと

図2-3
爆弾で-2になるが直後に+6を得られる
⇒目先の報酬ではなく将来の報酬の総和を最大化する必要があるとわかる

2.1.2　エージェントと環境のやりとり（MDPの概要）

• エージェントが行動を起こすことによって状態が遷移する
• 状態の遷移に伴い、得られる報酬も変わる（図2-4）

遷移の時系列データ：S0, A0, R0, S1, A1, R1, S2, A2, R2, ......
※Rtの時間のタイミングについて2つの慣例がある

2.2　環境とエージェントの定式化

MDPは、以下の要素を数式にして、環境とエージェントの定式化をする

• 状態遷移：どのように遷移するか
• 報酬：どのように与えられるか
• 行動：どのように行動を決めるか

2.2.1　状態遷移

状態遷移には2種類の性質がある

図2-5左

• 今の状態sと行動aで次の状態s'が一意に決まるもの ⇒ 決定論的
• s' = f(s, a) ← 状態遷移関数と呼ばれる

図2-5右

• 上記に対して次の状態が確率的に決まるもの ⇒ 確率的
• ロボットの例：床が滑る、モータの不備など
• p(s'| s, a) ← 状態遷移確率と呼ばれる
• 具体例：図2-6　p (s'| s=L3, a=Left)

p(s'| s, a)は現在の状態と行動だけに依存して次の状態が決まる
⇒ 状態遷移では過去の情報は必要ない
⇒ この性質をマルコフ性という

MDPはマルコフ性を仮定することで問題を解きやすくする
マルコフ性を仮定しないと、過去のすべての状態や行動を考慮する必要があり大変

2.2.2　報酬関数

本書では報酬は「決定論的」に与えられる想定

• 状態s, 行動a, 次の状態s' の報酬 ⇒ r(s, a, s')：報酬関数
• 例：図2-7　r(s=L2, a=Left, s'=L1) = 1
• ちなみにこの例だと、次の状態s'さえ分かれば報酬が決まるので、報酬関数はr(s')としても実装できる

2.2.3　エージェントの方策

次の状態、報酬ともに、現在の状態だけに基づいて決まる。
⇒環境について必要な情報はすべて現在の状態にある
⇒行動も現在の状態だけに基づいて決められる

行動の決め方にも決定論的か確率的がある

• 図2-8左　決定論的：a=μ(s)　ある状態sの時の行動a
• 図2-8右　確率的：π(a|s)　ある状態sの時に行動aをとる確率
  
  
  
  

これで3つの要素を数式で表せた！

• 状態遷移確率：p(s'| s, a)
• 報酬関数：r(s, a, s')
• 方策：π(a|s)

2.3　MDPの目標

ここまでで定式化した数式を使った、エージェントと環境のやり取りの流れ

• エージェントは方策 π(a|s) によって行動を決定
• 行動と状態遷移確率 p(s'| s, a) によって次の状態に遷移
• 報酬関数 r(s, a, s') に従って報酬が与えられる

上記の流れの中で、最適方策を見つけるのがMDPの目標
※最適方策とは収益（後述）が最大となる方策

最適方策について、厳密に定式化できるように準備を進める

2.3.1　エピソードと連続タスク

MDPは問題によってエピソードタスクと連続タスクに分けられる。

エピソードタスク

• 「終わり」のある問題
• 例：囲碁 → 最終的に勝ち、負け、引き分けのどれかになる
  次の試合では、何も石が置かれてない状態（初期状態）から始まる
• 初めから終わりまでの一連の試行をエピソードと呼ぶ
• 例：図2-9のようなグリッドワールド

連続タスク

• 「終わり」のない問題
• 例：在庫管理 → 売れ行きや在庫の量に応じてベストな仕入れ量を判断
  このような問題は、「終わり」は設けずに永遠に続くような問題設定として定義できる

2.3.2　収益

新たに収益という用語を定義する
G_t=R_t+γR_{t+1}+γ^2R_{t+2}+...

• 収益：各時刻の報酬の和
• それぞれに係数γがついている
• γは0~1.0の間をとり、時間が進むほど報酬を指数関数的に減衰させる（割引率）
• 割引率は、連続タスクの時（終わりがない）に収益の発散を防ぐ目的
• また、割引率によって近い将来の報酬を重要視させている⇒人の行動原理に沿っている？
  例：今日1万円もらうのと1年後に2万円もらうのでは今日の方が魅力的？（議論）

収益を最大化することをエージェントの目標とする