機械学習プロフェッショナルシリーズ「強化学習」読書メモ

機械学習プロフェッショナルシリーズ「強化学習」読書メモ

強化学習は、機械学習の一分野であり、学習を行う主体であり、環境とやり取りをし、行動を選択するエージェント(Agent)と呼ばれる主体が、未知の環境や複雑な問題を持った環境(Enviroment)という状況の中で、選択することができる行動(Action)の中から、状態(State)と報酬(Reward)に基づいて最適なものを学習しながら最適な行動を選ぶ手法となる。それらを選択する代表的な手法としては、Q学習、SARSA、DDPG、DQN、PPOなどがあり、これらの手法を用いて、エージェントの行動価値や方策を評価し、最適な行動を選択するためのアルゴリズムを提供している。

強化学習は、ロボット制御、ゲームプレイ、自然言語処理、金融取引などの様々な分野で応用されており、人間の判断力を超える高度な判断を実現することができる。

ここでは機械学習プロフェッショナルシリーズ「強化学習」をベースに述べる。

今回は読書メモを記載する。

「強化学習で必要になる数理を、広くカバーした。一貫してていねいな解説なので、じっくり読める。ベルマン方程式の定式化、”マルコフ決定過程(MDP)の概要とアルゴリズム及び実装例について“で述べているマルコフ決定過程・方策勾配法をより深く！　最後に、分布強化学習、深層強化学習を紹介した。」

第1章　準備

はじめに
強化学習は逐次的意思決定ルールの学習を扱う
登場するモデル(構成要素)として、 大まかに「制御対象のシステム」と「学習対象の方策モデル」がある
本章では
はじめに強化学習の概要を紹介
強化学習の基本構成要素を解説する
1.2節では制御対象システムを記述する標準的な数理モデルであるマルコフ決定過程を導入
1.3節で方策モデルと呼ばれる意思決定ルールを規定する関数を説明する
1.4節では方策学習の目的関数を定義して、逐次意思決定問題の定式化を行う

1.1　強化学習とは

最適な意思決定のルールを定めることを目的とする学習分野
一般に、「教師あり学習」「教師なし学習」と並ぶ機械学習の一分野
従来の機械学習は、多くの場合尤度や事後確率の最大化として解釈される
強化学習でも問題を尤度最大化問題などに近似して、従来の機械学習法を利用して得アプローチはある
他の機械学習はない「報酬」という概念が登場する
その期待値などを最大にする逐次的意思決定ルールを学習することが強化学習の最大の特徴
基本的には報酬最大化として解く
意思決定は
状態と呼ばれる現在の状況を表すものに基づき行われる
その結果しては報酬や新しい状態を観測し
再び意思決定を行うことを繰り返す
逐次意思決定ルールは「方策(plicy)」と呼ばれる
方策の最適化問題を「逐次的意思決定問題(sequential decision-making problem)」と呼ぶ
例
ある小売店における、値下げセールなしはキャンペーン実施について簡単化した問題
各販売期でキャンペーンを実施するかどうすを決定し、売り上げの長期平均を最大にすることが目的
キャンペーン最適化問題
強化学習では、 各期の売り上げを「報酬」、 顧客の購買意欲を「状態」、 キャンペーン実施の状態の有無を「行動」として扱う
方策は状態に依存し、 決定論的(非確率的)とすると 以下のパターンが考えられる
方策A
キャンペーンを実施続ける。平均売上は1
方策B
キャンペーンを一切しない。平均売上は3
方策C
購買意欲midでキャンペーンを実施する。平均売上は約2
方策D
購買意欲highでキャンペーンを実施する。平均売上は4
平均売上(平均報酬)を最大にする方策はD
キャンペーンを乱発せず、購買欲がhighになるまで待ってキャンペーンをするのが良い
一般的な場合は、上記のようにシンプルではなく、 状態行動数が多く、状態遷移は確率的で複雑
そのような一般の逐次的意思決定問題に対して取り組む数理的枠組みが「強化学習」
任意の制御対象システムに対する学習法を考えることは現実的でない
システムに対して過程をおく
その典型的な仮定が「マルコフ性」
多くの場合、マルコフ性が成り立つ状態を観測できるとする「マルコフ決定過程」に対する学習法を考える
マルコフ決定過程の過程を緩めた「部分観測マルコフ過程」という数理モデルもある
学習対象の方策モデルに対して
例1.1では現在の状態のみに依存し、決定論的に行動を選択する簡単なものを扱った
過去の状態や行動などの履歴に依存して行動を選択する方策モデル
確率的に行動を選択するような複雑なモデル

1.2　マルコフ決定過程と逐次的意思決定問題

はじめに
強化学習の数りの基礎になる確率過程やマルコフ性、マルコフ決定過程などを説明して
逐次的意思決定の問題設定の典型例などを紹介する
1.2.1確率過程とマルコフ性
確率過程を導入する前に、 まず確率の基礎的な事項をサイコロの目を用いて確認する
サイコロを振ってみて 「サイコロの目が1になる」「偶数になる」等の ランダム性のある事象の生起しやすさを 定量的に示すものが「確率(probability)」
事象Aの確率をPr(A)と表記する
決定論的にある値をとるのではなく、とりうる値とその値になる確率が与えられている変数
実際に撮った値
確率変数と確率の対応関係のことを
確率過程(stochastic process)
サイコロを単発的に振るのではなく、繰り返して振っていく
変数の値が時間と共に確率的に変化するような確率変数の系列
時間ステップtをパラメータとして、{Xt, t∈T}と欠くことが多い
一般の確率過程では
時間ステップtの確率変数Xtがx∈Xをとりうる確率は
時間ステップt以前の全ての実現値に依存する
Pr(A|B)は事象Bが与えられた時の事象Aの条件付き確率を示す
強い制約を課された最も単純な確率過程として
各確率変数X1,X2,…が互いに独立で同一の確率分布に従う
任意のx1,..,xt-1∈Xに対して上記が成り立つ
手持ちのデータがi.i.d.に従うとみなせるのであれば
データの並びや時系列性の考慮が不要になり、 標準的なパターン認識や機械学習の手法を利用できる
多くの意思決定の問題ではi.i.d.の過程をおくことはできない
強化学習ではi.i.d.よりも弱い制約である マルコフ性(Markov property)を仮定する
マルコフ性は将来の確率変数の条件付き確率分布が 現時間ステップtの値xtにのみ依存する
Xtが与えられればt-1以前の値x1,..,xt-1には依存しない性質
マルコフ性という特性を持つ確立過程は
Pr(Xt+1=x’|Xt=x)は状態xから次ステップx’に遷移する確率を表す
マルコフ性を持つ確率過程
状態変数のとりうる値が離散値(有限または加算)の場合
確率過程の具体例
背後にあるプロセス(サイコロをふる)は同じでも、 確率変数の定義により、確率過程が異なる特性を持つ
(a)の確立過程はi.i.d.を満たす
(b)のYtはマルコフ性を満たす
(c)はI.i.d.もマルコフ性も満たさない
マルコフ性を満たさないと 状態遷移の確率分布の複雑性が時間ステップtに対して 組み合わせ的に増大して、一般に扱えなくなる
1.2.2マルコフ決定過程
強化学習は
行動選択ルールの最適化を行うため
従来の「状態(state)」のみの確率過程ではなく、 行動などを追加した確率制御過程(stochastic control process)と呼ばれる確率過程を考える
マルコフ連鎖に 「行動(action)」と 意思決定の良し悪しの基準になる「報酬(reward)」を 組み入れた確立制御過程
5つ組≙{S,A,Pso,Pt,g}で定義される
有限行動集合:A≙{a1,…,a|A|}∋a
初期状態確立関数:Ps0:S→[0,1]: ps0(s)≙Pr(S0=s)
状態遷移確立関数:Pr:SxSxA→[0,1] 報酬関数:g:SxA→ℝ
確率変数StとAtは時間ステップt∈ℕ0での状態と行動変数を表す
マルコフ決定過程の状態数は|S|、行動数は|A|
|X|は、Xが有限集合の場合、Xの要素数を表す
マルコフ連鎖に報酬のみを追加したマルコフ過程や|A|=1のマルコフ決定過程
報酬gは有界関数であり、上式を満たす定数Rmax∈ℝが存在することを仮定している
報酬の集合Rを上記のように定義する
表記が複雑にならないように、一部のルベグを除いて、 行動集合は状態に依存しない単一の集合Aとして扱う
状態sにより選択可能な行動集合Asが異なる場合に対しても上記と定義することで容易に適用できる
報酬関数についても
簡便さを優先して、どう時間ステップtの状態と行動のみに依存するg(St,At)を用いる
より一般的な報酬としては
次状態にも依存するような報酬g(St,At,St+1)や
報酬分布関数Pr(Rt≤r|St=s,At=a)などを用いることがある
報酬にマイナスをかけたものは損失(cost)と呼ばれる
マルコフ決定過程への入力となる行動の選択ルールを規定する関数を定義する
方策(policy)または製作と呼ばれる
様々な形の方策を考えることができる
本書では
時間ステップの状態sのみに依存して 確立的に行動を選択する確立的方策(stochastic policy) π:AxS→[0,1]: π(a|s)≙Pr(A=a|S=s)を用いる
ここで方策πを含めたマルコフ決定仮定Mを上記とする
任意の確立的方策πを含む方策集合を上式と定義する
マルコフ決定過程についての理解を確認するため、 その時間発展(s0,a0,r0,…,st,at,rt)の具体的な手順旬を以下に示す
1.2.3逐次的意思決定の典型的問題設定
方策の最適化問題である逐次的意思決定問題は
目的関数と呼ばれる方策を評価する関数を用いて
与えられた方策集合の中から
目的関数を最大にするような方策を探し求める問題
そのままでは問題の抽象度が高すぎて 効率の良い解放を与えることができないので
典型的にはシステムはマルコフ決定過程に従うと仮定して
目的関数に期待値報酬(expected reward)
もしくは期待リターン(expected return)と呼ばれる 期待値より引き報酬(expected discounted cumulative reward)
直面する実課題では前述の典型的な問題設定を適用できない
期待的な効用の最大化以外に、大損失を避けたい
逆に大儲けをする確率をとにかく高めた
現実の課題を数理的に意思決定として定式化するためには
問題設定の検討が大切
どの種類の豊作集合までを扱う必要があるのかの検証も必要
1.2.4強化学習とマルコフ決定過程
強化学習はマルコフ決定過程(のプランニング)の研究成果を基礎にしている
マルコフ決定過程も強化学習も主目的は同じ
マルコフ決定過程で記述されるような制御対象のシステムに対して
累積報酬の期待値などを最大化するような最適な方策を求めること
つまり逐次的意思決定問題を解くこと
マルコフ決定過程の研究ではシステムを既知と仮定することが多い
強化学習ではシステムが未知の問題を扱うことが多い
強化学習は上記のようにシステムとの相互作用から方策を学習することを考える
制御対象を環境(environment)
制御器や意思決定者をエージェント(agent)と呼ぶ

1.3　方策

はじめに
本節では、マルコフ決定過程に対する幾つかの方策の集合を定義し
それらの複雑性や関係性について、またどの方策集合までを考慮すれば十分であるかなどを議論する
1.3.1方策の分類
確率的方策πにたいして
πの集合Πの部分集合として 決定的方策(deterministic policy)πdの集合Πdを考えることができる
ΠdやΠdの上付き文字dはdeterministic policyの頭文字に由来する
πdを確率的方策πの形式に書き直すことができるので、 ΠdはΠに含まれることがわかる
これまでに導入した方策πやπdは状態sのみに依存し、過去の経験とは独立に行動を選択する
時間ステップtが進展しても意思決定ルール(方策関数)は変わらない
一般のマルコフ方策として、時間ステップtの進展に従い方策関数が変化するような非定常的な方策系列
時間不変の定常な式の方策を常識のように定義
簡単化のためにΠSをΠもしくはΠSDをΠdとして表記することもある
頭文字Sはstationary(定常)に由来する
現在の状態だけではなくそれ以前の経験にも依存して行動選択をする非マルコフ方策を考える
非マルコフ方策の中でも最も複雑で表現力の高い方策として
現在の時間ステップtまでの全ての経験の履歴に基づいて
行動選択率を求めるような「履歴依存の方策(history-dependent policy)がある
任意のπhtを含む方策集合を上記のように表記し
方策πdtの系列とその集合を上記のように定義する
方策系列の集合の関係性
1.3.2*方策の特徴
上記の包含関係から
履歴依存の方策集合ΠHから最良な方策系列πh*を同定すれば
それより良い方策は存在しない
方策系列を引数とする任意の目的関数に対して上式が成り立つ
よって最適な方策を見つけるために上式を最適化すれば良い
方策サイズが時間ステップに対して組み合わせ爆発を起こすため、一般にΠHに対する最適化問題を扱うことは困難
例1.2
各方策集合のサイズを確認する
各方策間のサイズの比較を簡単にするため、 確立的方策ではなく、有限集合である以下の決定的方の策集合を考える
定常な決定的マルコフ方策の集合
時間ステップ長がTの非定常な決定的マルコフ方策系列の集合
時間ステップ長がTの履歴依存の決定的方策系列の集合
Πh,dtは時間ステップtの履歴依存の決定的方策の集合
状態数|S|=2、行動数|A|=2の有限長Tのマルコフ決定過程における方策のサイズ
命題1.1 マルコフ方策の妥当性
どの履歴依存のマルコフ方策で行動選択したとしても
環境(確率制御過程)の大切な特徴である各時間ステップtでのStとAtの同時確率については
より簡単な方策であるマルコフ方策を用いても正確に再現できる
以下XXXX

1.4　逐次的意思決定問題の定式化

はじめに
本章では、はじめに逐次的意思決定の問題設定やマルコフ決定過程の分類を確認する
次に、標準的な目的関数を解説して、逐次意思決定問題を定式化する
その他の筑紫製糸決定問題の定式化についても簡単に紹介する
1.4.1問題設定
方策の最適化問題のことを逐次意思決定問題という
学習できるものは方策πのみであり
環境モデルであるマルコフ決定過程M≙{S,A,Ps0,PT,g}は 強化学習を適用する課題によって定まり、時間不変とする
もし環境モデルが既知なら、データがなくても、 環境モデルから方策を最適化することができる
データから方策を学習する場合と区別することが多く、
環境モデルから最適方策を求めることを、学習(learning)と言わず、 プランニング(planning)もしくはプランニング学習(planning learning)ということが多い
典型的なプランニングのアプローチ
状態遷移確率Ptや報酬関数gなどの知識を利用する動的計画法や線形計画法
環境モデルを入力(s,a)に対して出力(r,s’)を返すだけで 内部構造が道なモデル(ブラックボックスモデル)として扱い、 最適方策を探索するプランニング法もある
環境モデルが未知の場合
プランニングの場合とは異なり、
従来の最適化ソルバーをそのまま適用できるような最適化問題として定式化できず
データ(環境との相互作用の結果)からの学習が必要になる
本書では環境モデルが未知の場合の方策の学習問題を 「強化学習問題(reinforcement learning problem)」と呼ぶ
強化学習問題の設定として大きく2つある
一つは
従来の機械学習と似た設定
環境との相互作用などから得たデータが大量にあって
そのデータから方策を学習するバッチ学習 (batch learning)
オフライン学習とも呼ばれる
もう一つは
逐次的に環境と相互作用してデータを収集しながら学習する
2つの意思決定戦略があり、 それらのバランスを考慮する必要がある
データ収集・探索(exploration)
データが十分でないという立場から
環境についての不確実性を減らし、新たな発見をできるように行動を選択する戦略
データ活用(exploitation)
データはもう十分にあるという立場
データから最良と判断できる行動を選択する戦略
逐次意思決定問題の分類
1.4.2マルコフ決定過程の単一化
対象とする逐次意思決定問題の設定により、 次のように終了条件の異なるマルコフ決定過程が考えられる
(A)ゴール状態があり、ゴール状態に到達したら終了する
(B)あらかじめ決められた時間ステップになったら終了する
四半期など期限があらかじめ決められた元でのトータルの売り上げの最大化
軽か時間ステップの情報を状態に取り込み状態を拡張し、 規定の終了時間ステップになったら吸収状態に確率1で遷移する
(C)の無限時間長のマルコフ決定過程に変換したことになる
(C)終了しない(無限時間長のマルコフ決定過程)
(A)と(B)のマルコフ決定過程の持つ意味を変えずに、
表現型を少し変更するだけで(C)のマルコフ決定過程として再定式化できる
状態Dは吸収状態(absorbing state)
他の状態に遷移しない状態
元の状態がS≙{i,j,k}の3つの終了時間ステップTが2の場合
吸収状態をzとして、
拡張した状態集合はS={i0,j0,k0,i1,j1,k1,z}の　7つになる
拡張後の状態サイズは|S|xT+1のように終了時間ステップTに比例して大きくなる
1.4.3リターンと目的関数
1.4.4*その他の逐次的意思決定問題

第2章　プランニング

はじめに
環境が既知の場合の逐次的意思決定問題であるプランニング問題を扱う
プランニング問題の特徴や解法は、 環境が未知である強化学習問題を扱うための基礎になる
プランニング問題の特徴を調べることで
環境が未知の場合においても、どのクラスの豊作まで行えば良いかがわかる
プランニング方法の確率的近似としてTD法やQ学習法など強化学習の代表的な方法が導出される
本章では
はじめに機体リターンに基づく目的関数や最適価値関数、最適方策を導入し、最適方策を求める方法として動的計画法(具体的な方法ではなく方法の総称)を紹介する
次に、動的計画法に基づく方法として、価値反復法と方策反復法を示す
さらに、線形計画法による開放にも触れ、導入した目的関数の性質を議論する
5章では、環境をブラックボックスモデルとして扱うプランニングについて紹介する

2.1　準備
2.2　動的計画法
2.3　動的計画法による解法
2.4　線形計画法による解法

第3章　探索と活用のトレードオフ

はじめに
逐次的に学習際に問題となるデータの探索と活用のトレードオフについて説明
トレードオフを考慮する代表的な方策モデルを説明する

3.1　概要
3.2　探索と活用のトレードオフ
3.3　方策モデル

第4章　モデルフリー型の強化学習

はじめに
第2章では、環境(マルコフ決定過程)が既知として、完全な情報のもとでのほうさくの最適化(プランニング問題)を考えた
ここでは、環境は未知であり、環境とエージェントの相互作用などによって得られたデータから方策を学習することを考える
モデルフリー型の強化学習は
環境非同定型の強化学習とも呼ばれる
環境を陽に推定せずに、方策を学習するアプローチ
次章では、環境を明示的に推定するもたにい(環境同定)型の強化学習を紹介する
本章で紹介する方法の多くは、2章で示した動的計画法を基礎とし、確率的近似の考え方に従って、確率的に観測されるデータから学習する
価値反復法から派生される方法として
Q学習法
方策反復法に関連する方法として
SARSA法
アクター・クリティック法

4.1　データにもとづく意思決定
4.2　価値関数の推定
4.3　方策と行動価値関数の学習
4.4　収束性
4.5　アクター・クリティック法

第5章　モデルベース型の強化学習

はじめに
第4章では環境を推定しないモデルフリー形の強化学習を説明した
本章では、環境モデルを陽に推定し、 推定した環境モデルを用いて方策を求めるモデルベースの強化学習を扱う

5.1　問題設定の整理
5.2　環境推定
5.3　ブラックボックス生成モデルに対するプランニング
5.4　オンラインのモデルベース型強化学習

第6章　関数近似を用いた強化学習

はじめに
状態数が膨大であったり状態空間が連続の場合
これまでの状態ごとに値を持つようなテーブル形式の関数では テーブルの要素数が大きくなりすぎてしまい
学習が困難になる
本章では、価値関数や方策関数を関数近似器を用いて近似して、学習することを考える

6.1　概要
6.2　価値関数の関数近似
6.3　方策の関数近似

第7章　部分観測マルコフ決定過程

はじめに
これまで、エージェントはマルコフ性のある状態を観測できると仮定していた
実問題によってはマルコフ性の過程は現実的ではない
状態を部分的にしか観測できず
未来の出来事が現在の観測だけではなく、過去の履歴にも依存する
このような状況を数理モデル化したもの
部分観測マルコフ決定過程がある
本章では、部分観測マルコフ決定過程とその会報を紹介する

7.1　部分観測マルコフ決定過程（POMDP）の基礎
7.2　POMDP のプランニング
7.3　POMDP の学習

第8章　最近の話題

はじめに
最近の強化学習の新展開として以下を紹介
期待リターン(価値関数)ではなく、リターン分布に基づく分布強化学習
関数近似器に深層ニューラルネットワークモデルを用いる深層強化学習

8.1　分布強化学習
8.2　深層強化学習

付録A　補足
A.1　証明
A.2　ノルム
A.3　線形計画法
A.4　自然勾配法の補足