強化学習

強化学習は、ある環境内における知的エージェントが、現在の状態を観測し、得られる報酬ベース選択を最大化するために、どのようなアクション選択をとるべきかを決定する機械学習の一分野である。強化学習は、教師あり学習、教師なし学習と並んで、3つの基本的な機械学習パラダイムの一つである。

強化学習が教師あり学習と異なる点は、ラベル付きの入力／出力の組を提示する必要がなく、最適でない行動を明示的に修正する必要もない。その代わり、未知の領域の探索と、現在の知識の活用の間のバランスを見つけることに重点が置かれる。

この文脈の強化学習アルゴリズムの多くは動的計画法を使用するため、この環境は通常マルコフ決定過程として定式化される。古典的な動的計画法と強化学習アルゴリズムとの主な違いは、後者はMDPの正確な数学的モデルの知識を必要とせず、正確な方法では実行不可能な大規模MDPを対象にできることである。代表的なアルゴリズムとしてTD学習やQ学習が知られている。

1. 導入
-----

強化学習はその一般性から、ゲーム理論、制御理論、オペレーションズ・リサーチ、情報理論、シミュレーションに基づく最適化、マルチエージェントシステム、群知能、統計学など、多くの分野で研究されている。オペレーションズ・リサーチや制御の文献では、強化学習は近似動的計画法あるいはニューロダイナミック・プログラミングと呼ばれている。強化学習の問題は最適制御理論でも研究されており、主に最適解の存在と特徴づけや、その厳密な計算のためのアルゴリズムを対象するが、学習や近似への関心は高くない。また、経済学やゲーム理論では、限定合理性のもとで均衡がどのように生じるかを説明するために、強化学習が用いられることがある。

基本的な強化学習は、マルコフ決定過程としてモデル化される。

S}}：環境とエージェントの状態の集合
A}}：エージェントの行動の集合
：行動 の下で状態 から状態 に遷移する確率
：行動 で から に遷移した後の即時報酬強化学習の目標は、エージェントが、即時報酬から蓄積される報酬関数または他のユーザ提供の強化信号を最大化するような、最適または最適に近い方策を学習することである。これは、動物心理学で起こっていると思われるプロセスに似ている。たとえば、生物の脳は、痛みや空腹などの信号を負の強化、喜びや食物摂取を正の強化として解釈するように配線されている。いくつかの状況では、動物はこれらの報酬を最適化するような行動を学習することができる。このことは、動物は強化学習が可能であることを示唆している。

基本的な強化学習エージェント型人工知能は、離散的な時間ステップで環境と相互作用を行う。各時刻 t}} において、エージェントは現在の状態 と報酬 を受け取る。次に選択可能な行動の集合から、1つの行動 を選択し、それを環境に送信する。環境は新しい状態 に移動し、遷移 に関連付けられる報酬 が決定される。強化学習エージェントの目標は、期待累積報酬を最大化する方策 , を学習することである。

この問題をMDPとして定式化すると、エージェントが環境の現在の状態を直接観測することを仮定し、この場合、問題は完全観測可能であると言う。しかし、エージェントが一部の状態しか観測できない場合、あるいは観測された状態がノイズによって破損している場合、エージェントは部分観測可能であると呼ばれ、正式にはその問題を部分観測可能マルコフ決定過程として定式化しなければならない。どちらの場合も、エージェントが使用できる行動の集合は制限を受ける可能性がある。たとえば、口座残高の状態が正である制約を課すことができる。状態の現在値が3で、状態遷移が値を4だけ減らそうと試みた場合、その遷移は許可されない。

あるエージェントの性能を、最適に行動している別のエージェントの性能と比較すると、その差からリグレット という概念が生じる。最適な行動に近づくために、たとえ即時報酬は負であっても、エージェントはその行動の長期的な結果について考えなければならない。

したがって、強化学習は、長期的な報酬と短期的な報酬のトレードオフを伴う問題に特に適している。強化学習は、ロボット制御、エレベーターのスケジューリング、電気通信、バックギャモン、チェッカーSutton、囲碁など、さまざまな問題への応用に成功している。

強化学習を強力なものにしている2つの要素として、性能を最適化するためのサンプルの使用と、大規模な環境に対処するための関数近似の使用があげられる。この2つの重要な要素により、強化学習は次のような状況下で、大規模環境に適用することができる。

環境のモデルはわかっているが、閉形式表現が得られない。
環境のシミュレーションモデルだけが与えられている。
環境に関する情報を収集する唯一の方法は、環境と対話することである。これらの問題のうち、最初の2つは計画問題であり、最後の1つは真の学習問題であると考えることができる。ただし、強化学習はどちらの計画問題も機械学習問題に変換する。

2. 探索
-----

探索と活用のトレードオフは、多腕バンディット問題や、Burnetas and Katehakisの有限状態空間MDPの研究を通じて、最も詳細に研究されてきた。

強化学習には巧妙な探索機構が不可欠であり、推定された確率分布を参照せず、ランダムに行動を選択すればその性能は低下する。有限MDPについては、比較的よく理解されている。しかし、状態数に応じてうまくスケールするアルゴリズムがないため、単純な探索方法が最も実用的となる。

そのような方法の一つが -貪欲法で、 は探索と活用の量を制御するパラメータである。確率 で活用が選択され、エージェントは長期的に最も効果があると思われる行動を選択する。あるいは、確率 で探索が選択され、行動は無作為に選択される。通常、 は固定パラメータであるが、スケジュールに従ったり、またはヒューリスティックに基づいて適応的に調整することもできる。

3. 制御学習アルゴリズム
-------------

たとえ探索の問題を無視して、状態が観測可能であっても、過去の経験を使用して、どの行動がより高い累積報酬につながるかを見つけ出すという問題が残される。

3.1. 最適性の基準
-----------

3.1.1. 方策
---------

エージェントの行動の選択は、方策と呼ばれる写像としてモデル化することができる。

方策の写像は、状態 において行動 を選択する確率を与える61}}。決定論的な方策を考えても良い。

3.1.2. 状態価値関数
-------------

状態価値関数 は、状態 、すなわち から出発して、方策 に連続して従う場合の期待収益と定義される。したがって、大まかに言えば、価値関数は、ある状態にあることが「どれくらい良いか」を推定するものである60}}。

ここで、確率変数 は収益を表し、報酬に割引率 を乗じた将来の割引報酬の和として定義される。

ここで、 はステップ における報酬であり、 は割引率である。割引率 は1未満に設定され、遠い未来の事象ほど重み付けは小さくなる。

アルゴリズムは、期待収益が最大になるような方策を見つける必要がある。MDPの理論から、一般性を損なうことなく、探索をいわゆる「定常方策」の集合に限定できることが知られている。ある方策が返す行動分布が、最後に訪れた状態にのみ依存する場合、その方策は「定常的」である。探索はさらに決定論的な定常方策に限定されることがある。「決定論的定常方策」は、現在の状態に基づいて「決定論的」に行動を選択する。このような方策は、状態の集合から行動の集合へのマッピングとして識別できるので、一般性を損なうことなく、これらの方策はこのようなマッピングと識別することができる。

3.2. 総当たり法
----------

総当たり法は、次の2つの段階を伴う。

可能性のある各方策について、それに従った場合の収益をサンプリングする
期待収益が最大の方策を選択するこの場合の問題の一つは、方策数が増大する、あるいは無限大になる可能性である。また、収益の分散が大きい場合、各方策の収益を正確に推定するために多くのサンプルが必要になることもある。

これらの問題は、何らかの構造を仮定し、ある方策から生成されたサンプルが他の方策の推定に影響を与えるようにすることで改善することができる。これを実現するための2つな主要な手法は、価値関数推定と直接方策探索である。

3.3. Value function}}価値関数法
--------------------------

価値関数法は、ある方策に対する期待収益の推定値の集合を維持することにより、収益を最大化する方策を見つけ出そうとするものである。

これらの方法はマルコフ決定過程の理論に基づいており、最適性は前述したよりも強い意味で定義されている。方策は、どのような初期状態からでも最大の期待収益を達成する場合、最適であると呼ばれる。繰り返すが、最適方策は常に定常方策の中から見出すことができる。

最適性を正式に定義するために、方策 の価値を、

で定義する。ここで、 は初期状態 から に従うことに伴う収益を表す。また、 が変更しうる場合、 の最大可能値として を定義すると、

となる。

すべての状態において、これらの最適値を達成する方策を最適と呼ぶ。この強い意味で最適な方策は、期待収益 を最大化するという意味でも「最適」であることは明らかである。ここで、 は初期状態の分布 からランダムにサンプリングした状態である。最適性を定義するには状態価値で十分だが、行動価値を定義しておくと有用である。状態 、行動 、方策 が与えられたとき、 の下での状態-行動ペア の行動価値は、

で定義される。ここで は、状態 で最初に行動 を取り、その後 に従っているときのランダム収益を表している。

MDPの理論では、 が最適方策であれば、 から各状態 で最も価値の高い行動を選択することで最適に行動するとされている。このような最適方策の行動価値関数を最適行動価値関数といい、一般に と表わす。要約すると、最適行動価値関数を知っていれば、最適な行動方法を知ることができる。

MDPの完全な知識を前提とすると、最適な行動価値関数を計算するための2つの基本的な手法は、価値反復法と方策反復法である。どちらのアルゴリズムも、 に収束する一連の関数  を計算する。これらの関数を計算するには、状態空間全体に対する期待価値を計算する必要があるが、これは最小のMDPを除いては非現実的である。強化学習法では、大きな状態行動空間上の価値関数を表現する必要性に対処するために、サンプルの平均化や関数近似の手法を使用して期待値を近似する。

3.3.1. モンテカルロ法
--------------

モンテカルロ法は、方策反復法を模倣したアルゴリズムに使用することができる。方策反復法は、方策の評価と方策の改善という2つの段階から構成される。モンテカルロ法は、方策評価段階で使用される。この段階での目標は、定常的で決定論的な方策 が与えられたとき、すべての状態-行動ペア に対する関数値 を計算することである。ここでは簡単にするために、MDPは有限であり、行動価値を収容するのに十分なメモリがあり、問題は偶発的で、各出来事の後にランダムな初期状態から新しい出来事が始まると仮定する。そして、与えられた状態-行動ペア の価値の推定値は、 からサンプリングされた収益を時間経過とともに平均化することによって計算することができる。十分な時間があれば、この手順により、行動価値関数 の正確な推定値 を構築することができる。これで、方策評価段階の説明を終了する。

方策改善段階では、 に関する貪欲な方策を計算することにより次の方策を得る。状態 が与えられたとき、この新しい方策は を最大化する一つの行動を返す。実際には、遅延評価によって、最大化行動の計算を必要なときまで先送りすることができる。

この手法の問題を次にあげる。

最適でない方策を評価するのに時間がかかりすぎる場合がある。
サンプリングが非効率的に行われる
軌跡上の収益が高分散である場合、収束が遅くなる。
偶発的問題に対してのみ有効である。
小規模で有限なMDPでしか使えない。以降の小節では、それぞれの問題についてさらに議論する。

3.3.2. TD学習}}時間差分法
------------------

最初の問題は、価値が収まる前に手順が方策を変更できるようにすることによって対応できる。ただし収束を妨げて問題となる可能性もある。現在のほとんどのアルゴリズムではこれを行い、一般化方策反復という種類のアルゴリズムを作り出すことができる。多くのアクター・クリティック法はこの範疇に属する。

2番目の問題は、軌跡がその中の任意の状態-行動ペアに関与できるようにすることで修正できる。これは3番目の問題にもある程度有効であるが、収益が高い分散を持つ場合により優れた解決策は、再帰的ベルマン方程式に基づくサットンの時間差分学習であるSutton。TD法における計算法には、インクリメンタル法またはバッチ法がある。最小二乗時間差法のようなバッチ法は、サンプル内の情報をより有効に利用できる可能性があるが、インクリメンタル法は、バッチ法が計算量やメモリの複雑性の理由で実行不可能な場合に選択される唯一の方法となる。この2つの方法を組み合わせる手法もある。時間差分に基づく方法は、4番目の問題も克服している。

TDに特有のもう一つの問題は、再帰的なベルマン方程式への依存に起因している。ほとんどのTD法には、いわゆる パラメータ があり、ベルマン方程式に依存しないモンテカルロ法と、ベルマン方程式に完全に依存する基本的なTD法の間を、連続的に補間することができる。これにより、この問題を効果的に緩和することができる。

3.3.3. 関数近似法
------------

5番目の課題を解決するために、関数近似法が提案されている。線形関数近似は、各状態-行動ペアに有限次元ベクトルを割り当てるマッピング から始まる。そして、状態-行動ペア の行動価値は、 の成分を何らかの//重み// で線形結合することによって得られる。

その後、アルゴリズムは、各状態-行動ペアに関連する値ではなく、重みを調整する。ノンパラメトリック統計学の考え方に基づく方法が探究されている。

また、値の反復を出発点として、Q学習アルゴリズムとその多くのバリエーションを作成することができる。Qを表現するためにニューラルネットワークを使用するディープQ学習法を含め、確率的探索問題へのさまざまな応用ができる。

行動価値を用いる場合の問題は、競合する行動価値を高精度に推定する必要であることになる可能性があることで、収益にノイズが多い場合には取得するのが難しい場合があるが、この問題は時間差法によってある程度軽減される。いわゆる互換関数近似法を使用すると、一般性と効率性が損なわれる。

3.4. #Direct policy search}}直接方策探索
----------------------------------

別の方法として、方策空間を直接探索する方法があり、この場合、問題は確率的最適化の一つとなる。利用可能な2つの方法は、勾配に基づく方法と、勾配を用いない方法である。勾配に基づく手法は、有限次元空間から方策空間へのマッピングから始まる。パラメータベクトル が与えられたとき、 に関連する方策を とする。評価関数を、

と定義すると、この関数は穏やかな条件下ではパラメータベクトル の関数として微分可能になる。もし の勾配がわかっていれば、勾配上昇を使うことができる。勾配の解析式が存在しないため、ノイズを含んだ推定値しか利用できない。このような推定値はさまざまな方法で構築することができ、ウィリアムズのREINFORCE法のようなアルゴリズムで作成することができる。方策探索法は、ロボット工学の文脈でも使用されている。多くの方策探索法は、局所最適に陥ることがある。

勾配情報への依存を避けるために、多くの種類の方法がある。たとえば、シミュレーティドアニーリング、クロスエントロピー法、または進化的計算の手法などがある。多くの勾配を用いない手法は、大域的な最適解に到達することができる。

ノイズの多いデータでは、方策の収束が遅くなることがある。こうしたことは、たとえば、軌跡が長くリターンの分散が大きい偶発的問題で起こる。このような場合、時間差分法に依存する価値関数に基づく手法が役立つ可能性がある。近年では、アクター・クリティック法が提案され、さまざまな問題で良い結果を出している。

3.5. モデルベース・アルゴリズム
------------------

最後に、上記の方法はみな、初めにモデルを訓練するアルゴリズムと組み合わせることができる。たとえば、Dynaアルゴリズムは経験からモデルを訓練し、実際の遷移に加えて、よりモデル化された遷移を価値関数に与えることができる。このような方法はノンパラメトリックモデルに拡張できる場合があり、たとえば、遷移を単純に保存して学習アルゴリズムに「再生」させるなどの方法がある。

モデルの使用には価値関数を更新する以外の方法もある。たとえば、モデル予測制御Model predictive controlでは、モデルを用いて挙動を直接更新する。

4. 理論
-----

ほとんどのアルゴリズムの漸近的挙動と有限標本挙動の両方がよく理解されている。優れたオンライン性能が証明されたアルゴリズムも知られている。

MDPの効率的な探索については、Burnetas and Katehakisで述べられている。また、多くのアルゴリズムで有限時間性能の限界が見られるが、これらの限界はかなり緩いと予想されるため、相対的な価値と限界をより深く理解するために、さらなる研究が必要である。

インクリメンタルアルゴリズムについては、漸近的収束の問題が解決されたreason=What are the issues that have been settled?。時間差分に基づくアルゴリズムでは、従来よりも広い条件の下で収束するようになった。

5. 研究
-----

研究テーマを次に列挙する。

アクター・クリティック法
少ないパラメータでも多数の条件下で動作する適応的手法
ソフトウェアプロジェクトにおけるバグ検出
継続的な学習
ロジックベースフレームワークとの組み合わせ
大規模MDPでの探索
人間のフィードバックからの強化学習
スキル獲得における暗黙知と明示知の相互作用
情報探索-好奇心型行動と、タスク依存型-目的指向型行動とを区別する内発的動機付け の大規模な経験的評価
大きな行動空間
モジュール型および階層型な強化学習
マルチエージェント・分散型強化学習は、関心を集めて話題で、応用が拡大している
乗員主体の制御
コンピューティング資源の最適化
部分情報。たとえば予測的状態表現を使用する。
新規情報の最大化することに基づく報酬関数
サンプルベースの計画
証券取引
転位学習
脳内のドーパミンを利用した学習をモデル化したTD学習。黒質緻密部から大脳基底核へのドーパミン作動性投射は予測誤差である。
価値関数と方策の探索方法

6. 強化学習アルゴリズムの比較
----------------



6.1. 連想強化学習
-----------

連想強化学習タスクは、確率的学習オートマトンタスクと教師あり学習パターン分類タスクの側面をあわせ持っている。連想強化学習タスクでは、学習システムは閉ループで環境と相互作用する。

6.2. 深層強化学習
-----------

深層強化学習Deep reinforcement learningは、ディープニューラルネットワークを使用し、状態空間を明示的に設計することなく、強化学習を拡張するものである。Google DeepMindによってATARIゲームの強化学習が研究されたことで、深層強化学習やエンドツーエンド強化学習が注目されるようになった。

6.3. 敵対的深層強化学習
--------------

敵対的深層強化学習は、学習された方策の脆弱性に焦点を当てた強化学習の活発な研究分野である。この研究領域では、当初、強化学習方策がわずかな敵対的操作の影響を受けやすいことがいくつかの研究で示されていた。これらの脆弱性を克服するためにいくつか方法が提案されているが、最新の研究では、これらの提案された解決策は、深層強化学習方策の現在の脆弱性を正確に表すには程遠いことが示された。

6.4. ファジィ強化学習
-------------

強化学習にファジィ推論を導入することで、連続空間におけるファジィルールで状態-行動価値関数を近似することが可能になる。ファジィルールの IF - THEN 形式は、自然言語に近い形式で結果を表現するのに適している。ファジィルール補間によるファジィ強化学習への拡張により、サイズが縮小されたスパース・ファジィ・ルールベースを使用して、基本ルールに重点を置くことができるようになった。

6.5. 逆強化学習
----------

逆強化学習では報酬関数が与えられない。その代わり、専門家が観察した行動から報酬関数を推測する。このアイディアは観察された行動を模倣することであり、多くの場合、最適または最適に近い行動となる。

6.6. 安全な強化学習
------------

安全な強化学習とは、システムの訓練や配置の過程で、その合理的な性能を確保し安全制約を尊重することが重要な問題において、期待収益を最大化する方策を学習する過程と定義することができる。

7. 参考項目
-------

Q学習
State–action–reward–state–action
最適制御
マルチエージェントシステム
遺伝的アルゴリズム

8. 脚注
-----

9. 推薦文献
-------

10. 外部リンク
---------

[1]
[2] 
[3] 
[4] url=https://web.archive.org/web/20181008104644/http://www.dcsc.tudelft.nl/~robotics/media.html at Delft University of Technology
[5]
[6] Series of blog post on RL with Python code
[7]

[8] 木村 元ら
[9] Suttonの[10]の日本語訳