強化学習

方策

エージェントがどのように行動を決めるかを表したものを方策 (policy) という。現在の状態 $s$ のみによって行動 $a$ が決まるような、確率に依らない方策を決定論的 (deterministic) な方策といい、これを定式化すると以下のようになる。

s'=\mu(s)

一方、決定論的でない (確率に依る) 方策を確率的な方策といい、方策 $\pi$ が状態 $s$ から行動 $a$ を選ぶ確率を $\pi(a\mid s)$ で表す。

状態遷移確率 (state transition probability) は状態 $s$ から行動 $a$ を選択したとき、状態 $s'$ に遷移する確率であり、 $p(s'\mid s,a)$ で表す。

状態遷移確率は現実問題における不確実 (あるいは計算が難しい) な挙動を表すのに用いられる。例えば、ロボットを移動させる際の床の摩擦やモーターの故障などが挙げられる。

方策 $\pi$ によって状態 $s$ から次の状態 $s'$ に状態遷移する確率は以下のように表せる。

\sum_a\pi(a\mid s)p(s'\mid s,a)

状態遷移において、今の状態 $s$ と行動 $a$ のみによって次の状態が一意に決まる性質をマルコフ性という。また、マルコフ性をもつ過程をマルコフ決定過程 (Markov Decision Process, 以下MDP) という。

マルコフ性を定式化すると以下のようになる。

s'=f(s,a)

報酬関数 (reward function) は状態 $s$ から行動 $a$ を選択し状態 $s'$ に遷移したときに得られる報酬であり、 $r(s',a,s)$ で表す。

収益 (return) は時刻 $t$ から得る報酬の和であり、 $G_t$ で表す。

ただし、終わりがないタスク (連続タスク) において収益は無限大に発散しうるため、将来の報酬に割引率 $\gamma\;(\gamma<1)$ を乗算することで、収益が発散することを防ぐ。

\begin{aligned} G_t&=R_t+\gamma R_{t+1}+\gamma R_{t+2}+\cdots\\ &=R_t+\gamma G_{t+1} \end{aligned}

状態価値関数 (state value function) (あるいは単に価値関数とも) は、状態 $s$ から方策 $\pi$ に従って行動したときの収益の期待値であり、 $v_\pi(s)$ で表す。

v_\pi(s)=E_\pi[G_t\mid S_t=s]

ベルマン方程式 (Bellman Equation) は、MDPにおいて成立する、状態価値関数を求める上で重要な方程式である。

v_\pi(s)=\sum_{a,s'}\pi(a\mid s)p(s'\mid s,a)\{r(s,a,s')+\gamma v_\pi(s')\}

導出

\begin{aligned} v_\pi(s)&=E_\pi[G_t\mid S_t=s]\\ &=E_\pi[R_t+\gamma G_{t+1}\mid S_t=s]\\ &=E_\pi[R_t\mid S_t=s]+\gamma E_\pi[G_{t+1}\mid S_t=s] \end{aligned}

ここで

\begin{aligned} E_\pi[R_t\mid S_t=s]&=\sum_{a,s'}\pi(a\mid s)p(s'\mid s,a)r(s,a,s')\\ E_\pi[G_{t+1}\mid S_t=s]&=\sum_{a,s'}\pi(a\mid s)p(s'\mid s,a)E_\pi[G_{t+1}\mid S_{t+1}=s'] \end{aligned}

より

v_\pi(s)=\sum_{a,s'}\pi(a\mid s)p(s'\mid s,a)\{r(s,a,s')+\gamma v_\pi(s')\}

すべての状態において状態価値関数が最大となるような方策 $\pi_*$ を最大方策という。また、最適方策 $\pi_*$ に従って行動したときの状態価値関数を $v_*$ で表す。

このとき $v_*$ について成り立つベルマン方程式をベルマン最適方程式 (Bellman Optimality Equation) といい、次のように表せる。

v_*(s)=\sum_{a,s'}\pi_*(a\mid s)p(s'\mid s,a)\{r(s,a,s')+\gamma v_*(s')\}

行動価値関数 (action value function) は、状態 $s$ から行動 $a$ を選択し、その後は方策 $\pi$ に従って行動したときの収益の期待値であり、 $q_\pi(s)$ で表す。

\begin{aligned} q_\pi(s,a)&=E_\pi[G_t\mid S_t=s,A_t=a]\\ &=E_\pi[R_t+\gamma G_{t+1}\mid S_t=s,A_t=a] \end{aligned}

行動価値関数は慣習的にQ関数と呼ばれ、本記事でも以下Q関数と呼ぶ。

Q関数は状態価値関数に対して行動 $a$ を設定したものである。

状態価値関数 $v_\pi(s)$ はQ関数 $q_\pi(s,a)$ を用いて次のように表せる。

v_\pi(s)=\sum_a\pi(a\mid s)q_\pi(s,a)

q_\pi(s,a)=\sum_{s'}p(s'\mid s,a)\left\{r(s,a,s')+\gamma\sum_{a'}\pi(a'\mid s')q_{\pi}(s',a')\right\}

q_\pi(s,a)=\sum_{s'}p(s'\mid s,a)\left\{r(s,a,s')+\gamma\max_{a'}q_\pi(s',a')\right\}