強化学習輪読#1

概要

今回の発表は、本の導入部を(一部順番を変更して)紹介する。
本の概要としては「環境との相互作用によって学習するという自然な発想を計算機的アプローチで再現/評価する」ということであり、導入となる１章は簡単な例を用いて大枠を紹介する内容となっていた。

本の概要

乳児が 遊んだり、腕を打ったり、周りを見渡したりするとき、明確な教師は存在しないが、環境と直接感覚的なつながりを持っている。(転べば痛いし、歩ければ褒められる)
人間を含む多くの動物は、このような相互作用による経験を主な情報源として、結果を予想することで、最善な行動を決定している。相互作用からの学習は、学習と知能のほぼ全ての理論の基礎となる考え方となる。この本では、科学的・経済的に関心のある、相互作用との学習を実現するのに有効な設計を探り、数学的解析や計算実験で評価する。

目次

1. 強化学習とは
2. 他分野との関係性
3. 簡単な例
4. まとめ

1. 強化学習とは

順番を前後して、自然界および人間社会における実例からエージェントの設定を考え、強化学習全体の設定を考える。

1-1. 相互作用と学習

まずは強化学習を理解するにあたっていくつか自然/社会における学習の例から考える。
例えば以下のような例は強化学習として捉えられる。

• チェスの名人が、ある盤面について、可能な手とそれに対する相手の手を予測して計画を立てることで、どの一手が望ましいかを即座に直感的に判断する。
• ガゼルの子牛は、生まれて数分後は足元でもがいているが、30分後には時速20マイルで走っている。
• 掃除ロボットは現在のバッテリーの充電レベルと、過去にどれだけ早く簡単に充電器を見つけることができたかに基づいて、ゴミを集めようとするか、充電ステーションに戻る道を探し始めるかを判断する。
• 目や耳の感覚器で情報を得て、状況に応じた迅速な判断を行うことで、ボウル、スプーン、牛乳などを手に取ったり運んだりという行動をし、最終的には朝食として栄養を摂る。また、ここでは本人が意識しているかどうかに関わらず、自身の体の状態を感知して、栄養の必要性や空腹の度合い、食べ物の好みなどを決定するという判断も行われている。

これらの全ての例では、以下のように、__目標を達成しようとしているアクティブな意思決定エージェントとその環境との間の相互作用__を伴う。

• エージェントの行動は、環境の将来の状態(例えば、次のチェスの位置、ロボットの次の場所、およびそのバッテリーの将来の充電レベル)に影響を与える行動をとることができ、それによって、次の時刻でエージェントが利用可能な選択肢を変化させる。
• エージェントは頻繁にその環境を監視しなければならない。例えば朝食を準備する人は牛乳が溢れないようにボウルを注意してみていないといけない。
• エージェントは目標に対する進捗状況を判断する。例えばチェスプレーヤーは、その一手で試合に勝ったか否かがわかり、移動ロボットはそのバッテリーがいつ切れるかわかり、フィルは自分が朝食に満足しているかを把握している。
• エージェントは、その経験を使用して、時間をかけてパフォーマンスを向上させることができる。
  チェスプレイヤーは、ポジションを評価するために使用する直観力を磨いてプレイを改善し、ガゼルの子牛は走る効率を向上させ、フィルは朝食を作ることを合理化することを学ぶ。

1-2. エージェントの設定

以上のように考えると、エージェントは環境の状態を常に知覚して、行動を決定し、目標に対しての進捗を最大化するために何をすべきかを学習すると言える。これが強化学習である。つまり、エージェントは以下の要素を持つ。

• その環境の状態をある程度感知できる、(感覚)
• その状態に影響を与える行動をとることができる。(行動)
• 環境の状態に関連する目標を持つ。(目標)

この本では、このようなエージェントに対して動的システムの考え方を用いて定式化し、マルコフ決定過程の最適制御の問題としている。具体的な定式化は後述となるが、基本的な考え方は、目標を達成するために時間をかけて環境と相互作用する学習エージェントを以上のような3つの側面から単純に捉えたものである。またこの際、以下の２点を考慮することが重要となる。

• ある状況においてどの行動をとるべきかを事前に教えられているのではなく、どの行動が最も報酬をもたらすかを試してみて発見しなければならない。(試行錯誤探索)
• 即時的な報酬だけでなく、次の状況やそれに続くすべての報酬を考えて行動をとる必要がある(遅延報酬)

1-3. 強化学習全体の設定

上のような性質を持つエージェントを考えたとき、環境との相互作用は以下の４つの要素に分解できる。

• ポリシー(感覚を入力として行動を出力)
• 報酬信号 (目標達成をエージェントに伝える)
• 価値関数 (将来累積報酬の現在価値=遅延報酬)
• 環境モデル (環境の状態とエージェントの行動を入力として次の時刻の環境の状態とエージェントへの報酬を出力)

以下から順を追って説明していく。

○ ポリシー

一言で言うと、ポリシーとは、「知覚された環境の状態から、その状態にあるときに取られるべき行動へのマッピング」である。問題によってはポリシーは単純な関数やルックアップテーブルであるかもしれないし、大規模な計算を必要とする関数かもしれないし、確率的であるかもしれない。ポリシーは、それのみで行動を決定するという意味で、強化学習エージェントの中核となる。

○ 報酬信号

報酬信号は強化学習問題のゴール・目標を定義する。各タイムステップで環境はエージェントに報酬と呼ばれる単一の数字を送る。この数字は報酬信号は環境の状態と取られた行動の確率的な関数であることもある。そして、エージェントの目的は、長期的に受け取る報酬の合計を最大化することとなる。生物学的システムでは、我々は喜びや痛みの経験に類似したものを報酬として考えるかもしれない。
この報酬信号が、ポリシーを変更するための基本的な情報となる。あるポリシーによって選択された行動で低い報酬に続いている場合、その状況で他の行動を選択するようにポリシーを変更する。

○ 価値関数

報酬信号が近視眼的な行動の良さを示すのに対し、価値関数は長期的に何が良いかを示す。一言で言えば、価値とは「エージェントがその状態を起点として、将来にわたって蓄積すると期待できる報酬の総量」である。
例えば、ある状態は基本的に直接的な報酬が低くとも、高い報酬を得る状態に近い状態であれば、高い価値を持っている。また、その逆もあり得る。
人間に例えるなら、報酬は喜び（高ければ喜び）と痛み（低ければ痛み）のようなものですが、価値は、環境が特定の状態の快不快など、より洗練された先見の明のある判断に対応している。
報酬がなければ価値は存在せず、価値を推定する理由は、より多くの報酬を達成することであるが、意思決定や評価を行う基準はあくまでも価値である。
報酬は基本的には環境によって直接与えられるが、価値は、エージェントが生涯にわたって行う観察の連続から推定し、再推定しなければならないため、報酬を決定することであるよりも価値を決定することははるかに困難である。実際、強化学習について考える場合の最も重要な構成要素は、効率的に値を推定する方法である。この価値の推定こそ、過去数十年の間に強化学習について学んだ中で最も重要なことである。

○ 環境モデル

環境のモデルは、環境がどのように振る舞うかについて推論を可能にするものである。ある状態と行動が与えられると、モデルは結果として次の状態と次の報酬を予測する。
全体をまとめた図は以下の通り

2.関連する分野との関係性

2-1. 教師あり学習と教師なし学習との比較 (機械学習手法としての比較)

強化学習は機械学習の一種だが、教師あり学習、教師なし学習とは、概念的に分離しておくことが不可欠である。特に強化学習では、問題とその解決方法の区別が非常に重要であり、この区別しなくては混乱を招く。

○ 教師あり学習との違い

教師あり学習とは、知識をもつ外部の教師から提供されたラベル付きの訓練データセットを用いて学習を行う。

• 各サンプルは、状況(変数)とその時とるべき行動の答え(ラベル)が組みとなる。
• 状況と行動を一般化し、未観測な状況でも正しい行動をとることが目的となる。

この手法も重要な学習方法ではあるが、環境との相互作用からの学習を行うことはできない。
なぜなら、エージェントがおかれる任意の状況とその状況における全ての行動について、正しさを測ることが非現実的であるからである。一方、強化学習では、経験のみからその報酬量を知ることで、次に取るべき行動を学習する。

○ 教師なし学習との違い

強化学習はまた、機械学習の研究者が教師なし学習と呼ぶものとは異なる。教師あり学習と教師なし学習という用語は、機械学習のパラダイムを網羅的に分類しているように見えるが、そうではない。
教師なし学習は隠れた構造を見つけようとするものであって、強化学習は報酬信号を最大化するという点で異なる。著者らは強化学習を第三の機械学習パラダイムであると考えている。

○ 探索と活用

また、上記二つの学習手法にはなく、強化学習にある問題として「探索(exploration)と活用(exploitation)のジレンマ」の問題が挙げられる。強化学習においては、

• 強化学習エージェントが多くの報酬を得るためには、過去に試したことがあり、報酬を生み出すのに効果的であると分かった行動をとるべきである。(活用)
• しかし、そのような行動を発見するためには、過去に選択したことのない行動を試さなければならない。(探索)

というジレンマが発生する。つまり、エージェントは様々な行動を試してみて、最も良いと思われる行動を徐々に選択していかなければならない。また、そのためには期待される報酬の信頼できる推定値を得るために、各行動を何度も試行しなければならない。
探索-活用のジレンマは、何十年にもわたって数学者によって集中的に研究されてきましたが、いまだに解決されていない。

○ 目標指向型エージェント

強化学習のもう一つの重要な特徴は、不確実な環境と相互作用する問題の全体を解決することである。
これは、機械学習の研究の多くが、最終的にどのように有用になるかを明示的に指定していなこと対照的である。

e.g.)

• 数学の問題が解けても研究ができるとは限らない。
• 競技プログラミングができてもプロダクト開発ができるかはわからない。
• ユーザーをクラスタリングすることが収益の改善に繋がるかはわからない

たしかに、これらのアプローチは多くの有用な結果をもたらしてきたが、孤立した副問題に焦点を当てるまででが限界である。
強化学習は逆のアプローチで、明確に定められた目標に対する行動を対話的に学ぶエージェントを設定することから始める。1-2にもあるように、すべての強化学習エージェントは、

• 明示的な目標を持ち、
• 環境の側面を感知することができ、
• 環境に影響を与える行動を選択することができる。

ため、目標を達成するに必要な行動のみをとるようになる。また、強化学習に教師あり学習が応用される場合、副次的に解くべき問題の重要度がわかる(ようにするべきである)。

2-2. ミニマックス・動的計画法・進化計算との比較 (解法としての比較)

○ミニマックス・動的計画法

あとで紹介する○×ゲームなどの、シンプルな対戦ゲームの場合、古典的な手法では

• ミニマックス戦略
• 動的計画法

などを用いてアプローチしてきた。しかし、これらの方法はあくまでも、相手が特定の戦略をとるということを前提とした考え方である。これでは、想定しなかった戦略をとる相手、すなわち報酬や状態を返す環境モデルが確定的でない状況に対して脆弱である。
多くの場合、環境の確定的な情報は手に入らないため、価値の推定と環境モデルという考え方が必要となる。

○メタヒューリスティクスとの違い

強化学習手法のほとんどは、価値関数の推定を中心に考えるが、問題を解決するためには必要でないこともある。以下のようなアルゴリズムは価値関数を介さずに問題を解こうとする。

e.g.)

• 遺伝的アルゴリズム
• 遺伝的プログラミング
• シミュレーテッドアニーリング

例えば遺伝的アルゴリズムで言えば、異なるポリシーを持つエージェントの「生涯」の行動を評価し、最も多くの報酬を得ることができるエージェントを生存させることで優れたエージェントを抽出するという方法である。
このような方法は、

• ポリシー取りうる空間が十分に小さい場合
• 良いポリシーが見つけやすい構造化である場合
• 環境の状態を完全には認識できない場合

などに効果的である。
しかし、この本では、環境と対話しながら学習する手法に注目している。個々の行動の詳細な相互作用を利用できる手法は、進化的手法よりもはるかに効率的になる場合が多い。
また、価値関数を推定しない手法もいくつか紹介するが、これらの手法は、ポリシー関数のパラメータの「調整すべき方向」を推定する。あくまでもこの推定値は、エージェントが環境の相互作用をから導くため、進化計算とは異なり、強化学習の性質を持つ。この手法も多くの問題で有用であることが証明されている(第13章を参照)。

2-3. 他分野との関わり (応用・工学的な関連)

現代の強化学習は他の工学や科学の分野において成果を残している。
例えば、

• オペレーションズリサーチや制御理論における古典的な「次元の呪い」に対処する。
• 心理学や神経科学と強く結びついており、双方に大きな利益をもたらしている。

本書の本文では、第14章と第15章で心理学と神経科学との関連をまとめながら、工学と人工知能に関連する強化学習のアイデアを展開している。

3. 簡単な例

○×ゲーム(9マス３目並べ)を想定する。

• エージェント：プレイヤー1
• 環境：盤面&プレイヤー

と定義でき、当然エージェントは、

• 環境を知覚し、
• 毎ターン一手を指すという行動をとり、
• 縦横斜めのどれか3つ連続で揃えるという目標とする。

また、強化学習の枠組みを考えると、

• ポリシー：盤面を見て、次の一手を決める関数
• 報酬：勝敗(バイナリー)
• 価値：勝利への近さ
• 環境モデル：t期の盤面の状態とエージェントの行動を入力として、t+1期の状態および勝敗判定を返す関数

と言える。そして残るのは、

• 試行錯誤探索(活用と探索)
• 遅延報酬

を考慮して価値をどのように推定するのかである。
まず価値関数は、9マス×3(○×空)の盤面の全状態に対応して1つの数字が価値として得られる表であるとする。その初期値は、

• 勝利状態：1(=遅延報酬)
• 敗北状態と引き分け確定状態：0
• その他：0.5

とし、この表を何度も更新していくことで、各状態の勝利確率の推定値とする。
更新は例えば、

 V(s_t) := V(s_t) + \alpha \left(V(s_{t+1}) - V(s_{t})\right)

という式を用いる。また、$s_{t+1}$は可能な手のうち、

• 最大の価値の状態になるよう打つ(活用)
• ランダムな手を打つ(探索)

という選択方法が考えられる。ここにおいて「活用と探索のどちらをとるのか」「ランダムの分布」についての選択は、様々な工夫ができる。
この活用・探索・更新は以下のような図で説明するとわかりやすい。

毎ターン点線の選択肢があり、そのうち実戦の手を実際にとったものを表す。アスタリスクがついている手は活用をした手で、そうでない手が探索のてである。そして、矢印のように探索した結果を前の状態にフィードバックし、改善or悪化分の$\alpha$倍だけ加えるように前の状態の価値を更新する。
$\alpha$の値はタイムステップの進行によって収束させれば対戦相手を問わないエージェントができ、タイムステップを収束させなければ、相手の行動の変容にも対応できるエージェントとなる。
また、○×ゲームはタイムステップも環境の状態も離散でとてもシンプルな構造であるが、どちらも連続値をとるような問題設定もとることができる。

4. まとめ

• エージェント
• 環境

が相互作用をもつ強化学習である。また、エージェントは、

• 知覚
• 行動
• 目標

という性質を持つ。このようなエージェントと環境の相互作用は、

• ポリシー
• 報酬
• 価値
• 環境モデル

という４つの要素に分けられ、この価値を推定することが強化学習の主なタスクである。価値の推定には、

• 活用
• 探索

のバランスを持って試行錯誤し、結果による報酬をフィードバックして推定値を更新する。

Appendix

演習 1.1. 【セルフ学習】

ランダムな相手と対戦するのではなく、双方が学習しながら自分自身と対戦したとすると何が起こると考えられるか？

演習 1.2.【対称性】

○×ゲームの位置は対称性がある。これを利用するためには上で説明した学習プロセスをどのように修正すればよいと考えられるか？また、この変更は、どのようにで学習プロセスを改善するか？さらに、相手が対称性を利用しなかったとの場合はどうすべきか？

演習 1.3.【貪欲法】

探索はせず、Greedyな手を打つとした場合、どのような学習をするか？

演習1.4. 【探索からの学習】

探索的な手を含むすべての手の後に学習の更新し、$\alpha$はステップが進むにつれ収束していくとする。このとき探索的な手については更新しないということもできる。この探索的な手からの更新の有無ではどのような違いがあると考えられるか? また、どちらの場合がよい学習をするか?

演習1.5.【その他の改善点】

上で説明した○×ゲームの問題を改善するのに、他に何か良い方法が考えられるか？