いものやま。

雑多な知識の寄せ集め

強化学習について学んでみた。(その9)

久々に。

前回までは、非連想的な問題である、n本腕バンディット問題を扱っていた。

今回からは、元々考えていた、強化学習について学んでみた。(その3) - いものやま。で述べたような状況ーーすなわち、行動の選択によって、状態がどんどん変化していってしまうような状況ーーを考えていく。

状態遷移のモデル

ところで、行動の選択によって状態がどんどん変化していってしまう場合、何が難しいのかというと、それはそれぞれの行動がどれくらい後にもらえる報酬に寄与したのかがパッとは分からないということだ。

例えば、最初の猿の例であれば、大きい箱を選ぶという行動と小さい箱を選ぶという行動はそれ自体では報酬がもらえず、後にもらえる報酬もそのあとに選ぶ行動によって変わってきてしまう。
なので、それぞれの行動の価値をどう考えればいいのかが難しい。

これを論理的に考えていくことが出来るようにするために、状態遷移のモデルというものを考えていく。

まず、報酬とは別に、収益 R_t \: (t=0, 1, \cdots)というものを考える。
これは、報酬 r_{t+1}が行動 a_tを選択した直後にもらえるものであるのに対し、行動 a_tを選択したことで、最終的に合計でどれくらいの報酬を得られたのかを示すものとなっている。
すなわち、

 {
\begin{align}
R_t &= r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \cdots \\
&= \sum_{k=0}^{\infty} \gamma^k r_{t+k+1}
\end{align}
}

と定義される。
なお、 \gamma \: (0 \le \gamma \le 1)割引率と呼ばれるもので、将来もらえる報酬をどれくらい現在の価値として考慮に入れるかを表すパラメータになる。
例えば、 \gamma = 0なら、直後の報酬のみを考えることになるし、 \gamma = 1なら、将来もらえる報酬をすべてそのまま現在の価値として考慮に入れることになる。

このように収益を定義すると、それは、その状態や行動の最終的な価値を意味するものとなってくる。

ただ、収益 R_tを上のように定義したけれど、当然、収益は行動 a_tのあとの状態 s_{t+1}や報酬 r_{t+1}、さらに、その状態で選択される行動 a_{t+1}によって変わってくることになる。
なので、実際には収益の期待値というものを考えていかないといけない。
そして、最終的にはこの収益の期待値が最大になるようにすることを考えることになる。

収益の期待値を考えることが出来るようにするために、状態遷移の確率 \mathcal{P}^a_{ss'}、報酬の期待値 \mathcal{R}^a_{ss'}を、次のように定義する。

 {
\begin{align}
\mathcal{P}_{ss'}^{a} &= Pr\left\{ \left. s_{t+1} = s' \right| s_t = s, a_t = a \right\} \\
\mathcal{R}^{a}_{ss'} &= E\left\{r_{t+1} \left| s_t = s, a_t = a, s_{t+1} = s' \right. \right\}
\end{align}
}

すなわち、それぞれ、状態 sのときに行動 aを選択して状態が s'になる確率と、そのときに得られる報酬の期待値を表す。

図に表すと、次のような感じ。

f:id:yamaimo0625:20150901155412p:plain

これらの確率、期待値は、エージェントがその値を知ることが出来るかは別として、環境によって決まってくる。
すなわち、これらの値が状態遷移のモデルを表現することになる。
とくに、各状態と行動の繋がり、および、状態遷移の確率と報酬の期待値を表したグラフを、状態遷移グラフと呼んだりする。

状態価値ベクトル、行動価値ベクトル

ただし、これだけだとまだ収益の期待値は計算できない。
というのも、収益の期待値は、エージェントがどのように行動を選択するのかという確率ーーすなわち、方策(ポリシー)ーーに影響を受けるからだ。

逆に言えば、状態遷移のモデルがあるときに、ある方策 \pi: \mathcal{S} \times \mathcal{A}(s) \rightarrow [0, 1]が与えられれば、それに対応した収益の期待値というのは計算可能になってくる。

そこで、ある方策 \piが与えられたとして、状態の価値を表すベクトル \boldsymbol{V}^{\pi} \in \mathbb{R}^{\mathcal{S}}(これを状態価値ベクトルと呼ぶことにする)、および行動の価値を表すベクトル \boldsymbol{Q}^{\pi} \in \mathbb{R}^{\mathcal{S} \times \mathcal{A}(s)} (これを行動価値ベクトルと呼ぶことにする)を、収益の期待値を使って次のように定義する。

 {
\begin{align}
V^{\pi}_s &= E \left\{ \left. R_t \right| s_t = s \right\} \\
Q^{\pi}_{s, a} &= E \left\{ \left. R_t \right| s_t = s, a_t = a \right\}
\end{align}
}

なお、本ではこれらをそれぞれ状態価値関数 V^{\pi}: \mathcal{S} \rightarrow \mathbb{R}行動価値関数 Q^{\pi}: \mathcal{S} \times \mathcal{A}(s) \rightarrow \mathbb{R}としているけれど、これらは方程式内で変数になるので、ベクトルと解釈しておいた方が分かりやすいと思う。
(関数が方程式の変数になっているという考え方がすんなり受け入れられるのであれば、本の記述でも問題ないのだけど)

ところで、この定義について計算をしていくと、

 {
\begin{align}
V^{\pi}_s &= E \left\{ \left. R_t \right| s_t = s \right\} \\
&= E \left\{ \left. r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \cdots \right| s_t = s \right\} \\
&= E \left\{ \left. r_{t+1} + \gamma \left( r_{t+2} + \gamma r_{t+3} + \cdots \right) \right| s_t = s \right\} \\
&= E \left\{ \left. r_{t+1} + \gamma R_{t+1} \right| s_t = s \right\} \\
&= \sum_{a \in \mathcal{A}(s)} \pi(s, a) \left( \sum_{s' \in \mathcal{S}} \mathcal{P}^a_{ss'} \left( \mathcal{R}^a_{ss'} + \gamma E \left\{ \left. R_{t+1} \right| s_{t+1} = s' \right\} \right) \right) \\
&= \sum_{a \in \mathcal{A}(s)} \pi(s, a) \left( \sum_{s' \in \mathcal{S}} \mathcal{P}^a_{ss'} \left( \mathcal{R}^a_{ss'} + \gamma V^{\pi}_{s'} \right) \right)
\end{align}
}

となることから、状態価値ベクトル \boldsymbol{V}^{\pi}の各要素 V^{\pi}_{s}の間には、次の関係が成り立つ。

 { \displaystyle
V^{\pi}_s = \sum_{a \in \mathcal{A}(s)} \pi(s, a) \left( \sum_{s' \in \mathcal{S}} \mathcal{P}^a_{ss'} \left( \mathcal{R}^a_{ss'} + \gamma V^{\pi}_{s'} \right) \right) \: \: \: \: \left( \forall s \in \mathcal{S} \right)
}

したがって、これは \boldsymbol{V}^{\pi}に関する連立一次方程式になっていて、Bellman方程式と呼ばれている。

なお、行動価値ベクトル \boldsymbol{Q}^{\pi}についても同様の展開が出来て、次のような連立一次方程式が得られる。
(これもBellman方程式と呼ばれる)

 {\displaystyle
Q^{\pi}_{s, a} = \sum_{s' \in \mathcal{S}} \mathcal{P}^a_{ss'} \left( \mathcal{R}^a_{ss'} + \gamma \sum_{a' \in \mathcal{A}(s')} \pi(s', a') Q^{\pi}_{s', a'} \right) \: \: \: \: \left(\forall (s, a) \in \mathcal{S} \times \mathcal{A}(s) \right)
}

Bellman方程式があることから、これを解くことが出来れば、ある方策でのそれぞれの状態、行動の価値を計算できることが分かる。
さらに、方策を変更することで状態、行動の価値を向上させることが出来れば、それぞれの状態でより価値の高い行動を選択できるようになっていることになる。

そこで、問題となってくるのは、次の3つ。

  • 方策が与えられたときに、Bellman方程式をどうやって解けばいいのか。(方策評価
  • Bellman方程式の解を改善する(=収益の期待値を大きくする)ような方策をどうやって得ればいいのか。(方策改善
  • そもそも、状態遷移のモデル(状態遷移の確率、および、報酬の期待値)が分からない場合、どうすればいいのか。

明日以降は、これらを順番に片付けていくことになる。

今日はここまで!

強化学習

強化学習

  • 作者: Richard S.Sutton,Andrew G.Barto,三上貞芳,皆川雅章
  • 出版社/メーカー: 森北出版
  • 発売日: 2000/12/01
  • メディア: 単行本(ソフトカバー)
  • 購入: 5人 クリック: 76回
  • この商品を含むブログ (29件) を見る