強化学習
連想強化学習タスク(associative reinforcement learning)は、確率的学習オートマトンタスクと教師あり学習パターン分類タスクの側面をあわせ持っている。連想強化学習タスクでは、学習システムは閉ループで環境と相互作用する。
状態価値関数(state-value function) V π ( s ) {\displaystyle V_{\pi }(s)} は、状態 s {\displaystyle s} 、すなわち s 0 = s {\displaystyle s_{0}=s} から出発して、方策 π {\displaystyle \pi } に連続して従う場合の期待収益(expected return)と定義される。したがって、大まかに言えば、価値関数は、ある状態にあることが「どれくらい良いか」を推定するものである。
V π ( s ) = E  [ R ∣ s 0 = s ] = E  [ ∑ t = 0 ∞ γ t r t ∣ s 0 = s ] , {\displaystyle V_{\pi }(s)=\operatorname {E} [R\mid s_{0}=s]=\operatorname {E} \left[\sum _{t=0}^{\infty }\gamma ^{t}r_{t}\mid s_{0}=s\right],}
ここで、確率変数 R {\displaystyle R} は収益(return)を表し、報酬(reward)に割引率(discount-rate) γ {\displaystyle \gamma } を乗じた将来の割引報酬の和として定義される。
別の方法として、方策空間(その何らかの部分集合)を直接探索する方法があり、この場合、問題は確率的最適化(英語版)の一つとなる。利用可能な2つの方法は、勾配に基づく方法と、勾配を用いない方法である。勾配に基づく手法(policy gradient methods、方策勾配法)は、有限次元(パラメータ)空間から方策空間へのマッピングから始まる。パラメータベクトル θ {\displaystyle \theta } が与えられたとき、 θ {\displaystyle \theta } に関連する方策を π θ {\displaystyle \pi _{\theta }} とする。評価関数を、
ρ ( θ ) = ρ π θ {\displaystyle \rho (\theta )=\rho ^{\pi _{\theta }}}
と定義すると、この関数は穏やかな条件下ではパラメータベクトル θ {\displaystyle \theta } の関数として微分可能になる。もし ρ {\displaystyle \rho } の勾配がわかっていれば、勾配上昇(gradient ascent)を使うことができる。
MDPの理論では、 π ∗ {\displaystyle \pi ^{*}} が最適方策であれば、 Q π ∗ ( s , ⋅ ) {\displaystyle Q^{\pi ^{*}}(s,\cdot )} から各状態 s {\displaystyle s} で最も価値の高い行動を選択することで最適に行動する(最適行動を取る)とされている。このような最適方策( Q π ∗ {\displaystyle Q^{\pi ^{*}}} )の行動価値関数(action-value function)を最適行動価値関数(optimal action-value function)といい、一般に Q ∗ {\displaystyle Q^{*}} と表わす。要約すると、最適行動価値関数を知っていれば、最適な行動方法を知ることができる。
MDPの完全な知識を前提とすると、最適な行動価値関数を計算するための2つの基本的な手法は、価値反復法と方策反復法である。どちらのアルゴリズムも、 Q ∗ {\displaystyle Q^{*}} に収束する一連の関数 Q k {\displaystyle Q_{k}} ( k = 0 , 1 , 2 , ... {\displaystyle k=0,1,2,\ldots } ) を計算する。これらの関数を計算するには、状態空間全体に対する期待価値を計算する必要があるが、これは最小の(有限の)MDPを除いては非現実的である。強化学習法では、大きな状態行動空間上の価値関数を表現する必要性に対処するために、サンプルの平均化や関数近似の手法を使用して期待値を近似する。
十分な時間があれば、この手順により、行動価値関数 Q π {\displaystyle Q^{\pi }} の正確な推定値 Q {\displaystyle Q} を構築することができる。これで、方策評価段階の説明を終了する。
方策改善段階では、 Q {\displaystyle Q} に関する貪欲な方策(greedy policy)を計算することにより次の方策を得る。状態 s {\displaystyle s} が与えられたとき、この新しい方策は Q ( s , ⋅ ) {\displaystyle Q(s,\cdot )} を最大化する一つの行動を返す。実際には、遅延評価によって、最大化行動の計算を必要なときまで先送りすることができる。
この手法の問題を次にあげる。
最適でない方策を評価するのに時間がかかりすぎる場合がある。
サンプリングが非効率的に行われる(長い軌跡が、軌跡を開始した単一の状態-行動ペアの推定値を改善するだけである)
軌跡上の収益が高分散(high variance)である場合、収束が遅くなる。
偶発的問題(episodic problems)に対してのみ有効である。
小規模で有限なMDPでしか使えない。
以降の小節では、それぞれの問題についてさらに議論する。