マルコフ決定過程

バンディット問題では、エージェントの行動によって次に取り組む問題は変わらない。

マルコフ決定過程（MDP）は、エージェントの行動によって状況（状態（state））が変わる問題を扱う。

MDPでは、以下の３つを数式によって定式化する

• 状態遷移：状態はどのように遷移するか
• 報酬：報酬はどのように与えられるか
• 方策：エージェントはどのように行動を決定するか

次の状態s’は状態sと行動aによって一意に決まることを、決定論的な状態遷移という

関数としては以下のようになる（状態遷移関数）

$s' = f(s, a)$

今エージェントが状態Sにいて、行動aを行い、状態S’に移動する確率は以下になる（状態遷移確率）

$p(s'|s, a)$

上記は現在の状況sと行動aに依存してs’が決まるので、現在よりも過去の情報は必要ない

この性質をマルコフ性という

エージェントが状態sにいて、行動aを行い、次の状態がs’になったときの報酬を以下とする

$r(s, a, s')$

方策はエージェントがどのように行動を決めるかを表す

エージェントがある場所にいるときには、必ず特定の行動を行う

$a = μ(s)$

ある状態sにいるときの行動aをとる確率

$π(a|s)$

上記の枠組みの中で最適方策（Optimal Policy）を見つけること。最適方策とは収益を最大化する方策。

「終わりのある問題」。例えば囲碁（最終的に勝ち負け引き分けになる）。

「終わりのない問題」。例えば在庫管理。

時刻はtで状態がStであると仮定する。エージェントが方策πによって行動Atを行い報酬Rtを得て、新しい状態$S_{t+1}$に遷移する流れが続く場合、収益Gtは以下のように定義される

$G_t = R_t + γR_{t+1} + γR_{t+2} + ...$

$γ$は割引率（0から1の間）と呼ばれる。割引率を導入する理由は連続タスクの場合に報酬が無限大に発散することを防ぎ、近い将来の報酬ほど重要に見せかける。

エージェントは行動を確率的に消えるかもしれないし、状態が確率的に遷移するかもしれずその場合、得られる収益も確率的となる

確率的な挙動に対応するには期待値を使う。収益の期待値は以下のようになる

$ν_π(s) = E[G_t|S_t = s, π]$

または

$ν_π(s) = E_π[G_t|S_t = s]$

上記の$ν_π(s)$を状態価値関数と呼ぶ

すべての状態において、他のどの方策よりも状態価値関数の値が大きいとき、その方策は最適方策となる。最適方策は決定論的である。数式にすると以下のようになる。

$a = μ(s)$

最適方策における状態価値関数は最適状態価値関数と呼ぶ