深層強化学習のベイズ主義的な情報探索に駆動された自然言語処理の意味論

スポンサーリンク

派生問題:確率的バンディット問題

以上の推測統計学の状況を前提とすれば、推測統計学的な情報の発見探索はベイズ的に実践可能な状態になっているようだ。理由不十分の原則を前提とした情報的事前確率非情報的事前確率区別によるデータドリブンな意思決定は、ベイズ更新を背景としたベイズ推定逐次合理性によって、仮に少ないデータ収集状況から分析を開始していたとしても、最終的には旧い統計学の分析に基づく意思決定とは遜色の無い精度を誇る。

しかし、単純に情報を探索し続けていくだけでは、いずれリソースの限界に直面するであろう。限られたリソースの中で最善を尽くすためには、既知の情報を活用しながら未知の情報を探索していく必要がある。まさに「バンディット問題(Bandit Problem)」との関連から、「探索(explore)」と「活用(exploit)」の区別を導入しなければならない。

問題解決策:バンディットアルゴリズムの設計

N組の腕(arm)を持つ複雑なスロットマシンを想定する。これを「バンディット(Bandit)」と呼ぶ。ゲームのプレイヤーは、このスロットマシンのどの腕を引いても、それに応じた報酬(reward)を得られる。しかし、報酬は常に得られる訳ではない。ある腕の報酬よりも別の腕の報酬の方が高いかもしれない。腕を引くには、スロットマシンにコインを投入するという意味で、コストを支払う必要がある。

そのため、プレイヤーはスロットマシンでギャンブルを敢行していると言える。腕を引くことにリスクがあるだけでない。プレイヤーにとって、最初はそれぞれの腕の報酬確率も不確実だ。正体不明な腕を引き続けることで、経験的にデータを収集するしかない。

ここまでの説明を前提とする限りでは、この問題統計学上の問題に過ぎない。どの腕の平均報酬が最大になるかは、リスクを冒して調べるしかない。それぞれの腕を何度も引き、受け取る報酬の中項を出すことで、平均的な報酬計算できる。しかし、本物の「バンディット問題」は現実的により複雑となる。

限られた情報とリソースにおける選択

バンディット問題は、それぞれの腕を引くことで得られる報酬についての情報が少ないからこそ、特殊な問題とされる。プレイヤーは、実際に引いた腕の報酬についてしか、情報を得られない。どの腕を引いても、引かなかった他の全ての腕の情報を損失することになる。全ての情報同時に得ることは不可能だ。

実際、状況は過酷だと言える。プレイヤーは、過去の自身の決定に関して、部分的なフィードバックしか得られない。それだけではなく、決定に失敗した場合には文字通り損失を被ることになる。常に最適な腕を引ける訳ではない。

バンディットアルゴリズム

バンディットアルゴリズム(Bandit Algorithm)」は、元々は理想的なギャンブラーが架空のカジノで最大限に儲けることを考えて設計された。この架空のカジノにはスロットマシンしか存在しない。スロットマシンは、お金を強奪する強盗(bandit)とも呼ばれている。このカジノにはスロットマシンしかないが、それぞれのスロットマシンの当たりの確率設定には差異がある。例えばスロットマシンの中には、100回に1回、5ドル当たるマシンもあれば、1000回に1回、25ドル当たるマシンもある。

バンディットアルゴリズムとA/Bテストの差異

バンディットアルゴリズムインターネット広告配信においても応用されている。どのエンドユーザーやセグメントにどの広告を配信するのかを選択することは、一種のギャンブルなのだ。実際にそのエンドユーザーやセグメントがその広告を経由して成果を発生させれば、「報酬」を得ることになる。閲覧者の「状態」に対して広告を配信することを「行動」と見做せば、インターネット広告配信システムは一種の強化学習問題に直面していることになる。故に強化学習アルゴリズムバンディットアルゴリズムは「アドテクノロジー(Ad technology」にもなり得るということになる。

こうしたことから、バンディットアルゴリズムA/Bテストと何が違うのかが問われることがある。とはいえ、双方はそもそも参照する問題設定が異なっている。だから、双方のアルゴリズム機能的に等価問題解決策として観察されることは、本来ならばあり得ない。つまりこの意味では、A/Bテストバンディットアルゴリズムは同一視できないのである。

A/Bテストはテスト期間中常にアトランダムに配信すべき広告やユーザー・インターフェイスを決定する。テスト期間が終わるまでは、このアトランダム性が持続する。仮にテスト期間の途中で最適な広告やUIが判明したとしても、それを積極的に出し分ける訳ではなく、尚もアトランダムに出し分け続ける。

これに対してバンディットアルゴリズムは、テスト期間の途中で最適な広告やUIが判明した場合には、むしろそれらを積極的に配信すべき対象として学習して、以後実際にそれらを配信する。つまりバンディットアルゴリズムは、初期はアトランダムに広告やUIを出し分けていくが、次第に出し分けるべき対象を収束させていく。

探索(explore)と活用(exploit)の差異

このバンディットアルゴリズムA/Bテスト差異特徴付ける概念として、「探索(explore)」と「活用(exploit)」の区別を導入できる。探索は、上述した言葉で言うところのテストを意味する。アトランダムに広告やUIを配信することによって、最適な配信対象を調査する処理を、ここでは探索と呼んでいる。一方、活用は現時点で最適であるとされる配信対象を配信することを指す。

A/Bテストは探索しか実行しない。活用という概念は、このテストには無い。これに対して、バンディットアルゴリズムは探索と活用の双方を実行する。

こうした差異が伴うのは、双方の問題設定差異があるためでもある。何故なら、A/Bテストはその名の通り広告やUIを検証することこそが問題としているのに対して、バンディットアルゴリズムギャンブラー報酬を最大化することを問題として設計されているからだ。

A/Bテストバンディットアルゴリズムは異なる問題設定に対する問題解決策となる。故に双方は「機能的に等価」ではない。問題設定に応じて、双方を利用し分ければ良いだけの話だ。

不確実性に直面した時の楽観主義

バンディットアルゴリズムは「不確実性に直面した時の楽観主義(Optimism in face of uncertainty)」に依拠する。ギャンブラーのように、情報が不足している際にも決断する場合には、これらのアルゴリズムが有用に機能するだろう。これらのアルゴリズムは、「証明」や「根拠付け」とは程遠い。これらのアルゴリズムは、演繹的でもなければ、帰納的でもないだろう。これらのアルゴリズムは発見探索的で、ヒューリスティック(Heuristik)なデータ分析となる。

機能的拡張案:バンディットアルゴリズムとしてのepsilon-Greedy Algorithm

概念的には、探索と活用を確率的に振り分けるアルゴリズムをepsilon-Greedyと呼ぶ。バンディットアルゴリズムの一種として有名だ。貪欲(Greedy)なアルゴリズムとは、長期的な観点では良い結果にならなくても、現時点で最適だと考えられる行動を採るアルゴリズム意味する。

活用と探索の振り分けは、確率εで活用を、1-εで探索を行なう。εはパラメタとして設定できる。活用では、期待値の最も高い腕を引くこととなる。100回中99回当たった腕より、1回中1回当たった腕の方が、確率は高い。故にこちらの腕を引くことになる。一方探索では、全ての腕からアトランダムに選択した腕を引く。

広告やUIの配信におけるユースケース

長期間、このアルゴリズム広告やUIを配信させようとすると、次の二つの現象を反復することになる。

  1. 既知の最適な選択肢を活用する。
  2. 所与の選択肢全てをアトランダムに探究する。

アルゴリズムにおける2つの選択肢

上述した探索と活用の区別を導入するのならば、このアルゴリズムは、究極的には次の3つしか実行しない。

  1. 1 – epsilonの確率で、Epsilion-Greedyアルゴリズムは最適だと思われる選択肢を活用する。
  2. epsilon / 2の確率で、Epsilion-Greedyアルゴリズムは最適だと思われる選択肢を探求する。

  3. epsilon / 2の確率で、Epsilion-Greedyアルゴリズムは最だと思われる選択肢を探求する。

これが、Epsilion-Greedyアルゴリズムの全てとなる。

εと(1 – ε)の差異

探索と活用の区別を導入するなら、上記の三つの選択肢は単純に探索と活用を確率論的に割り振っていることを意味している。εを探索の選択確率として設定するか、活用の選択確率として設定するかは、それぞれの関連する書籍や論文においては統一されていないように見受けられる。

epsilon-Greedyのメリットは、仕組みが非常にシンプルで済むことだ。だがデメリットが多い。第一に、単なる確率で、割合で腕の報酬を考慮するため、母数の少ないうでを適切に評価できないことが挙げられる。第二に、探索では完全にアトランダムに腕を選択することになるため、明らかに良くないと判明している腕でも、未知の腕と等価な選択肢として扱ってしまう。第三に、最も良いと判断された腕を繰り返し引き続けるため、最初に間違った腕を良い腕と判断した場合に修正が利きにくい。

機能的拡張案:バンディットアルゴリズムとしてのsoftmax Algorithm

バンディットアルゴリズムの一種であるsoftmax Algorithmは、概念的には、当たる確率の高い腕を高い確率、当たる確率の低い腕を低い確率で引くことによって、活用と探索を実行する。

基本的には当たった確率の加重平均でその腕を引く。だがそのまま加重平均を用いると、ほぼ等確率で全ての腕を引いてしまう。故にこのアルゴリズムではexp関数を利用して個々の確率差異を大きくする必要がある。

腕Aと腕Bを持つスロットマシンを仮定する。ここで、腕Aの期待値をrA、腕Bの期待値をrBとした場合、腕Aを引く確率を次のように計算する。

$$\frac{exp(\frac{rA}{tau})}{exp(\frac{rA}{tau})+exp(\frac{rB}{tau})}$$

熱力学的な温度概念

ここでいうtauとは、差異の大きさを調節するパラメタだ。tauが0に近ければ、確率の高い腕を100%採用する。逆に無限(∞)に近ければ、完全にアトランダムに腕を引くことになる。tauのパラメタ概念は熱力学の温度概念からヒントを得ている。このアルゴリズムでは、tauに対応付けられる温度を少しずつ増減させられる。

この温度調節を特に「アニール(Annealing)」という。アニールとは、Softmaxのアルゴリズムにおいて、時間の経過とともに温度を下げる工程を意味する。アニールという用語は、鍛冶屋の喩えから来ている。鍛冶屋が鋳鉄の温度を少しずつ下げることで、柔軟性を減らし、硬度を増していく工程をアニールするという。こうすると、金属が最終的に作りたい形に近付くに連れ、少しずつ材料が強力になる。

このアルゴリズムのメリットは、良い腕とい腕を区別できた時に、その情報を探索に応用することが可能になる点だ。良い腕を多く引き、い腕を少なく引くことができる。一方デメリットは、引いた回数を考慮しないことだろう。つまり100回中50回当たった腕も、2回中1回当たった腕も、等価になる。

このアルゴリズムを選択するリスクとして指摘できるのは、パラメタであるtauの設定によって結果が大幅に異なってしまうことだ。パラメタ設定を誤れば、完全にアトランダムな場合と同じ結果になる。これではアルゴリズム意味が無い。

機能的拡張案:バンディットアルゴリズムとしてのUpper Confidence Bounds(UCB) Algorithm

バンディットアルゴリズムの一種であるUpper Confidence Bounds(UCB) Algorithmは、概念的には、各腕についての情報に対してどの程度「確信」を持つことができているのかをアルゴリズム自身が考慮して腕を選択する。このアルゴリズムは、知らない腕については、積極的に探索を実行する。そうすることで、それぞれの腕について、より確信を持とうとする。

アルゴリズム的には、評価式から評価値を求め、評価式が最も高いアームを引く。評価式は次の通りだ。

$$\frac{rA\sqrt{2log(totalCount)}}{count}$$

ここで、rAが腕Aの期待値となる。totalCountは全ての腕を引いた総計回数となる。countは、腕Aを引いた回数を意味する。

このアルゴリズムのメリットは、パラメタを設定する必要が無いということだ。故に実運用時のチューニングの負担が軽減される。何も情報がない場合に実行した場合、これは大きな利点になる。どのような反応が起こるかがよくわからなくても、UCBを実行できるからだ。

最終的に最も良い腕のみを選ぶように収束することも、メリットとして挙げられる。しかし選択可能な腕の個数が無限に近付く場合は、UCBのような、未知の腕を積極的に探索するアプローチは通用しない。こうした状況では、ベイズ統計学的に拡張されたBayes-UCBのように、事前分布を頼りに事後分布を更新するアプローチによる手助けが必要になる。

機能的拡張案:バンディット問題の問題解決策としてのThompson Sampling

Thompson Samplingはベルヌーイ分布とベータ分布の前提から出発したアルゴリズムで、バンディット問題の解決策としても機能する。このアルゴリズムは次の前提から記述されている。

  1. ギャンブルの勝敗はベルヌーイ分布に従うと仮定する。
  2. 事前分布として、勝率 pを想定する。この事前分布はベータ分布に従うものとする。

漸近最適なアルゴリズム

Thompson Samplingはベイズ推定と事後確率のサンプリングによってデータを処理する。このアルゴリズムは漸近最適なアルゴリズムで、処理の流れは次のようになる。

  1. 各アームiの報酬確率分布を初期化する。

$$α_i = 1, β_i = 1$$

  1. 各ラウンドで確率分布の事後確率を抽出し、その標本の最大なものを選択する。

$$\DeclareMathOperator*{\argmax}{argmax}θ_i ~ Beta(α_i, β_i), I(t) = \argmax_{θ_i}$$

  1. 報酬を確認して、確率分布をベイズ更新する。

$$if(X_{I(t)}(t) = 1) then$$ $$\\α_i = α_i +1$$ $$else$$ $$\\β_i = β_i + 1$$

専らここでのベイズ更新は二項尤度関数におけるベイズ更新となる。故にそのベータ分布は共役事前確率(conjugate prior)となる。つまり、事前確率がベータ分布であるのなら、事後確率もベータ分布になる。

Thompson SamplingとUCBの比較

どのバンディットパターンであっても、途中まではUCBと同様の損失傾向ではあるものの、試行回数が増大していくに連れてUCBの損失がThompson Samplingの損失よりも高まる傾向があることが、実験によって判明している。

腕の数が多ければ、それだけ報酬の差分が小さい。UCBのパフォーマンスが低下するのは、ここに起因している。Thompson Samplingは報酬期待値が収束した後は良い腕しか引かなくなる。一方UCBは良い腕が判明した後も一定の確率比較い腕も引いてしまう。

バッチプログラムとしての配信アルゴリズムへの展望

上記の実験報告によれば、腕を引いてから報酬を得るまでに遅延(delay)が生じる場合であっても、Thompson SamplingはUCBに比して損失が低い。1000ステップ遅延している場合、UCBの損失は10倍に膨れ上がるのに対し、Thompson Samplingは6倍に留まる。故にバッチプログラム化された配信アルゴリズムのように、リアルタイムで報酬を得られるオンライン配信システムとしては実装できない場合であっても、Thompson Samplingのアルゴリズムを採用すべきであるということになる。

ただし注意しなければならないのは、上記の実験では、報酬が可変的である場合のシミュレーションが実施されていないということである。例えば報酬広告の成果報酬金額のみとした場合、報酬が変動し易くなるため、報酬の定義を改めた方が良い場合もある。

問題再設定:強化学習問題の枠組み

より情報探索による問題解決目的達成を促進させるには、「探索」と「活用」の区別を導入し続けるだけではなく、その情報探索の舞台となる環境から受容した刺激から学習するようなフィードバック・ループ設計しておかなければならない。この学習するシステム外部環境区別を導入する上で、強化学習問題の枠組みが有用となるであろう。

問題解決策:強化学習アルゴリズムの設計

強化学習(Reinforcement Learning)」は、一般に「強化学習問題(Reinforcement Learning Problem)」と呼ばれている問題設定において、目的を達成するための相互作用(interaction)から学習していく問題の枠組み(framing of the problem)を意味する。強化学習問題の枠組みでは、エージェント環境、状態、行動、報酬など、様々な概念が記述される。この諸概念の記述形式アルゴリズム次第で微妙に変わる。

環境、報酬、行動、状態の概念

学習者や意思決定者は、ここではエージェント(agent)と呼ばれている。このエージェントの外部のあらゆる諸要素から構成されて、エージェントとの相互作用対象となり得る概念の全ては、「環境(environment)」と呼ばれる。

環境はまた、報酬(reward)の発生源でもある。エージェントは、この報酬獲得を最大化することを目指して行動(action)を選択していく。エージェントの行動選択可能性は、環境の状態(state)に左右される。状態は、エージェントが利用可能な情報意味する抽象的な概念だ。それは環境の一部の情報が前処理されることによって得られる。

強化学習アルゴリズムのマルコフ性

強化学習問題の枠組みでは、エージェントが状態から選択可能な行動を決定する確率写像(map)の計算処理が実装される。この写像を特にエージェント方策(policy)と呼ぶ。強化学習問題ではこの方策最適化が目指される。

その際、その数学的計算を単純化する技術として、マルコフ性(Markov property)が仮定される。これにより、強化学習アルゴリズムは意思決定や価値が現在の状態にのみ依存している関数であるという前提を構築している。ただしこの技術を導入したことによる制約条件として、強化学習問題では状態と報酬の個数が有限であるという前提も引き受けることになっている。

強化学習アルゴリズムの価値関数とベルマン方程式

ほぼ全ての強化学習アルゴリズムは、価値関数(value function)に基づく報酬評価を実行している。この関数は状態の関数意味する状態価値関数(state-value function)や状態と行動の対応関係の関数意味する行動価値関数(action-value function)として記述される。これら諸関数は総じてエージェントが「ある状態sであること」がどの程度の良いのかを評価する際に言及される。この「どの程度良いのか」は、その状態sであることによって将来的に期待される報酬として把握される。

この強化学習アルゴリズムにおける価値関数は、再帰的であることが指摘されている。任意の方策πと状態sに対して、sの価値とsから可能な後続の諸状態の価値との間には、以下のような価値Vに対するベルマン方程式(Bellman equation)が成り立っている。

$$V^{\pi}(s)=\sum_a\pi(s,a)\sum_{s’}\Pr[s_{t + 1}=s’|s_t=s,a_t=a]\Bigl[\mathrm{E}[r_{t + 1}|s_t=s,a_t=a,s_{t + 1}=s’] \gamma V^{\pi}(s’)\Bigr]$$

この方程式は、ある時点における状態と後続の状態との関連を物語っている。前提にあるのは、エージェントがある状態から後続の状態を予測することだ。ベルマン方程式は全ての状態の可能性をその生起確率の重み付けによって取り扱う。それによれば、開始時の初期状態の価値は、「期待される後続の諸状態の価値」と、「それに達するまでの間に得られる報酬」との和と等価になる。

状態価値関数と行動価値関数の差異

ほぼ全ての強化学習アルゴリズムは「価値関数(value function)」に基づく評価を反復している。価値関数は状態の関数か、状態と行動の組み合わせの関数となる。この関数は、エージェントがある状態にいることや、ある状態で行動を選択することがどの程度良いのかを評価する。この「どの程度良いのか」は、将来的に期待される収益に関連して設定される。エージェントが将来受け取ると期待できる報酬は、エージェントの行動選択に依存する。したがって、価値関数は特定の方策との関連から設定される。

強化学習問題の枠組みにおいて、価値関数状態価値関数(state-value function)と行動価値価値関数(action-value function)に区別される。これらの価値関数エージェント経験に基づいて見積もることが可能だ。例えば、方策πに従うエージェントが遭遇した各状態に引き続いて発生する収益の平均値を維持するなら、その状態に遭遇した回数が無限回数に近付くに連れて、平均値は状態の価値$$V^π(s)$$に収束する。もしある状態において選択された各行動それぞれに対してその平均値が保持されるのならば、それらの平均値も同様に行動価値$$Q^π(s, a)$$に収束する。

モンテカルロ法

こうして無限回数の経験反復によって価値関数を見積もる方法を「モンテカルロ法(Monte Carlo method)」と呼ぶ。様々な領域で利用されているモンテカルロ法は、強化学習問題の枠組み価値関数の推定と最適方策の発見を可能にする学習方法としても活用できる。モンテカルロ法は概ね強化学習問題の脈絡では動的計画法との差異によって特徴付けられている。

動的計画法のような古典的な強化学習アルゴリズムを採用した場合、環境モデルが必要になる。しかし、未知なる環境を探索する上では、いつでも十分なモデルが得られる保証は無い。とりわけ環境から得られる報酬のモデルに関しては、予めその情報を手にするのが難しい。

問題解決策:経験のみに準拠したモンテカルロ法

強化学習アルゴリズムとしてのモンテカルロ法は、環境の完全なモデルを仮定しない。それよりも、モンテカルロ法は「経験(experience)」のみで探索を可能にする。ここでいう経験というのは、強化学習問題の枠組みとの兼ね合いで言えば、状態、行動、報酬に関する経験意味する。これらの経験は、実際に環境を探索することで得られる経験だけではなく、「シミュレーション上の経験(simulated experience)」でも構わない。

概念的には、こうした経験は「出来事(episode)」を一つの単位として区別される。ここでいう出来事は、生成消滅する事象を意味する。つまりいずれの経験も、やがては終息を迎えると仮定される。逆に言えば、半永久的に持続する経験は仮定しない。そして強化学習問題におけるモンテカルロ法価値関数推定と方策が変更されるのは、こうした出来事としての経験が完了した時に限定される。

モンテカルロ法と動的計画法の差異

等価機能分析として、モンテカルロ法と動的計画法を機能的に比較しておこう。モンテカルロ法は動的計画法に対して少なからず次の3つの利点を有している。

1. 環境モデルは要求されない

第一に、モンテカルロ法の場合、動的計画法とは異なり、環境モデルが無くても学習を可能にする。環境との相互作用から直接的に最適方策学習する際には、モンテカルロ法の方が機能する。

2. シミュレーションだけでも学習が可能になる

第二に、モンテカルロ法の場合はシミュレーションだけで学習が可能になる。動的計画法とは異なり、実際にエージェント環境を探索させる必要は無い場合もある。

3. 状態群を部分集合に細分化した場合に計算が効率化する

第三に、状態群を部分集合へと細分化した上で、その一部をモンテカルロ法学習した場合には、とりわけ効率的な学習が可能になる。この部分集合計算によって、他の部分集合計算の精度が犠牲になる訳ではない。

モンテカルロ法と動的計画法の共通点

一方、モンテカルロ法と動的計画法には共通するアルゴリズム部分もある。双方とも価値関数を単に計算するだけではないという点では共通している。この二つのアルゴリズムは、いずれも、本質的に同様の方法最適化を目指した相互作用を実行する。つまり動的計画法と同様に、方策評価、方策改善、そして方策一般化反復を実行する。

問題解決策:状態価値推定と行動価値推定の区別

所与の方策状態価値関数学習する上でも、モンテカルロ法は有用となる。しかし、環境モデルの利用可能性に限度がある場合や、あるいは全くモデルが得られない場合ならば、状態の価値よりも行動の価値の方が推定するメリットは大きい。ここでは、モンテカルロ法を利用した場合の状態価値推定行動価値推定機能的な比較を試みる。

モンテカルロ法による状態価値推定の機能

状態価値推定問題視する前に、まずは状態価値という概念を確認しておく。ここでいう状態価値とは、累積的な報酬期待値を意味する。つまりある状態sの価値Vは、その状態から開始した際の期待収益に他ならない。言い換えれば、価値Vは割引された累積報酬期待値を意味する。

モンテカルロ法のように、経験のみから収益を計算するには、その状態になったことで取得した収益の平均を求めれば良い。多くの収益が観測されるにしたがって、この平均値は期待値へと収束する。この収束の理論強化学習問題における全てのモンテカルロ法において共通して想定されている。

訪問概念から価値推定へ

方策πに従って状態sになるという出来事集合が与えられた場合、πにおけるsの価値は次のように表せる。

$$V^π(s)$$

出来事で状態sになることを特に「状態sへの訪問(visit)」と呼ぶ。強化学習の領域では、この「訪問」という概念から、Vを求める幾つかの方法が提案されている。「全訪問MC法(The every-visit MC method)」は、sへの訪問を全て集計して、その収益の平均値としてVを求める方法だ。これに対して、「初回訪問MC法(The first-visit MC method)」では、初回の訪問のみを集計して、その収益の平均値からVを求める。全訪問MC法にせよ、初回訪問MC法にせよ、sへの訪問回数や初回訪問回数が無限回に近付くにつれて、価値Vに収束する。例えば初回訪問MC法では、各収益は独立で等しく分布したVの推定となる。大数の法則により、これらの推定の平均はその期待値に収束する。全訪問MC法は、初回訪問MC法に比して直接的ではないが、その推定もVに漸近的に収束する。

モンテカルロ法とブートストラップ法の差異

生成消滅する事象としての出来事で各状態が区別されていることからもわかるように、モンテカルロ法では、各状態に対する推定が独立であるという仮定が受け入れられている。つまり、ある状態の推定は、他の状態には依存しないと仮定する。

一方、動的計画法では、この仮定は受け入れられていない。そのため、他の推定結果を利用してある推定を実施する「ブートストラップ法(bootstrap method)」が、モンテカルロ法で採用されることは無い。

これは一見して大胆な仮定かもしれないが、機能する仮定ではある。何故なら、各状態推定を独立と見做せば、ある状態群の部分集合に対する推定が別の部分集合に影響を与えることを防げるからだ。これは、モンテカルロ法を動的計画法から区別するメリットに対応している。繰り返すように、状態群を部分集合へと細分化した上で、その一部をモンテカルロ法学習した場合には、とりわけ効率的な学習が可能になるのである。

行動価値推定

モデルが得られない場合、状態価値推定よりも行動価値推定の利点の方が大きくなる。と言うよりも厳密に比較するなら、モデルが最初から手に入っているなら、状態価値の推定だけで、次の行動の意思決定には十分通用するということだ。となれば、行動価値推定機能はモデルが無い場合の「埋め合わせ」であるということになる。

モデルが無い場合に状態価値推定だけでは不十分であるのは、動的計画法を再び引き合いに出すだけで理解できるかもしれない。動的計画法のブートストラップ法などのように、数ステップ分「先読み」することで、報酬と次の状態の最良の組み合わせに準じて行動を選択することは可能であろう。しかしそれは、モデルがあればの話だ。実際、動的計画法はモデルが無ければ機能しない。

これを前提とすれば、モンテカルロ法が真の意味でその存在意義を発揮するのは、まさにモデル無き行動価値推定が必要とされる局面においてのことだ。言い換えれば、モンテカルロ法という問題解決策が参照している問題設定は、行動価値に対する方策評価問題に他ならない。その機能は端的にQ(s, a)を見積もることに直結する。

Q(s, a)の見積り

尤も、以上のような機能的な非等価性があるにも拘わらず、モンテカルロ法における行動価値推定状態価値推定アルゴリズム的には等価だ。厳密さを省いて単純化するなら、全訪問MC法にせよ、初回訪問MC法にせよ、これまで単に状態sとして観測されていた変数に状態sと行動aの組み合わせを代入するようなものになる。

実際、行動価値推定における全訪問MC法は、状態と行動の組み合わせの価値をその行動が選択された場合の状態への訪問結果として得られる収益を平均する。一方、初回訪問MC法も、ある行動aが選択された場合の初回の状態sのみを平均化するだけだ。そしていずれに方法も、それぞれの状態と行動の組み合わせの選択回数が無限回に近付くにつれて期待値へと収束する。

モンテカルロ法による行動選択の偏り

ただし、モンテカルロ法行動価値推定を実施した場合の派生問題となるのは、全ての状態と行動の組み合わせが選択される保証が無いということだ。もしπが決定論的な方策であるのならば、そのπ次第では状態と行動の組み合わせに偏りが生じる。特定の状態には一切訪問しない可能性もある。特定の状態sから選択可能な行動は一つではない。だからこそ行動価値推定によって、複数の行動からの選択の負担軽減が求められる。だがある状態sで可能になる行動選択肢が網羅的に調査されないのならば、その行動価値推定の返り値(returns)の精度は疑わしいものとなる。

全ての状態と行動の組み合わせが無限回訪問される猶予

勘の良い読者は、この派生問題から確率論的バンディット問題想起したかもしれない。既知の行動選択肢を活用するか、それとも新たな行動選択肢を探索するのかは、トレードオフの問題だ。

バンディット問題に対する解決策としては、epsilon-greedy法やソフトマックス戦略などのような様々なバンディットアルゴリズムが記述されている。一方、モンテカルロ法では、全ての状態と行動の組み合わせが探索の開始点として選択される可能性があるということ、その確率が0よりも大きいことを推定の制約条件として加えることで、操作的にこの問題を解消しようとする。こうすることで、全ての状態と行動の組み合わせが無限回訪問される猶予を遺しておくのだ。

実世界における探索の不自然さ

しかしこの問題解消策では、実際にエージェント環境と相互作用する場合に、不自然さを生み出すことになる。環境もまた訪問可能な状態や選択可能な行動を制約する可能性があるからだ。そのため、全ての状態と行動の組み合わせが無限回訪問されることを保証するというのは、純粋に現実的な環境を前提とした推定から乖離することを意味する。

この派生問題への代替案となるのは、方策のみに照準を定めるということだ。つまり、各方策において、全ての行動が0よりも大きな確率で選択される可能性があることを保証しておくのである。

しかしこの代替案で解決しようとした場合、また派生問題が伴う。それは、この方策確率操作が純粋なアトランダム性を否定してしまうということだ。それは言わば、モンテカルロ法という概念そのものの否定になってしまう。つまりここが強化学習問題におけるモンテカルロ法機能的な限界と考えて良いだろう。

問題解決策:「方策オン型」と「方策オフ型」の区別

強化学習で想定される行動主体としてのエージェントは、環境についての十分な知識や情報を有していない。エージェントは、諸状態で諸行動を選択するが、その際には不確実性と偶発性に曝される。そこで強化学習エージェントは、環境のモデルを必要としない価値関数や最適方策の探索発見を目指した学習を敢行することになる。その際強化学習では、ただエージェントの試行錯誤によってのみ得られる経験学習していくことになる。

ただし、エージェントが十分に試行錯誤するには、各状態で十分な数の行動の選択可能性が保証されていなければならない。まずは初期状態の行動選択に慎重にならざるを得ない。それ次第では後続の方策において選択不可能な行動が派生してしまう。後続の行動選択においても、「この行動を選択したが故にあの行動が選択できなくなる」といった偏りが生じれば、十分な数の試行錯誤ができなくなる。

そこで強化学習では「方策オン型(on-policy)」と「方策オフ型(off-policy)」の区別が導入されている。「方策オン型」が比較確率論的な方策から比較的決定論的な方策への移行を意味する一方で、「方策オフ型」が比較確率論的な方策比較的決定論的な方策の併存を意味する。ここで導入することになる区別は、サイバネティクス的な制御問題との関連から記述することで、より特徴付けることができるだろう。

モンテカルロ法による制御

モンテカルロ法による制御問題は、最適方策群の近似問題に他ならない。この解決策となるアルゴリズムは、動的計画法同様、一般化方策反復(generalized policy iteration: GPI)に準拠する。GPIは近似方策と近似価値関数を保持する。一方では近似方策価値関数に対応して繰り返し改善され、他方では価値関数方策に対応する価値関数として改善されていく。この反復により、双方は最適なものに近付く。

Richard Sutton and Andrew Barto (1998). Reinforcement Learning. MIT Press. 5.3 Monte Carlo Controlより[引用](https://accel-brain.com/erinnerung-von-anthropologischen-materialismus-in-medienasthetik/3/#link2keyword=引用)。

方策改善は、現在価値関数において、方策をGreedyに探索することで実行される。行動価値関数を有しているのならば、Greedyであるための環境モデルは必要無い。いずれの行動価値関数Qにおいても、対応するGreedyな方策は、各状態sに対して最大のQ値を持つ行動を決定論的に選択するだけになる。

$$\DeclareMathOperator*{\argmax}{argmax}π(s) = \argmax_{a} Q(s, a)$$

故に方策改善はQに関する各πをGreedyな方策として再記述することによって実行される。

$$\DeclareMathOperator*{\argmax}{argmax}Q^{π_k} (s, π_{k+1}(s)) = Q^{π_k}(s, \argmax_{a} Q^{n_k}(s, a))$$

$$\DeclareMathOperator*{\max}{max}= \max_{a} Q^{n_k}(s, a)$$

$$ \geq Q^{π_k} (s, π_k(s))$$

$$= V^{π_k} (s)$$

方策改善の定理

ここで重要となるのは、kの時の方策πとk 1の時の方策πの比較だ。 現在方策πで行動を選択するのが最適なのか、それともその方策πを改善するべきなのかは、考慮に値する。これは確率論的バンディット問題の探索と活用のトレードオフにも関わる問題だ。この問題に買いを見出す一つの方法は、次のアルゴリズムを前提に、状態sで行動aを選択すると共に、その後は既存の方策πに従うことである。

$$Q^π (s, a) = E_π {r_{t+1}+γV^π (s_{t+1}) |s_t = s, a_t = a}$$

この値を

$$V^π (s)$$

と比べた場合の大小が判断基準となる。

もし上記のQ値がV値よりも大きければ、状態sで行動aを選択することが最適であるということになる。つまり、まず状態sで一度行動aを選択し、その後は方策πに従うことが常に方策πに従うことよりも良いのならば、状態sで行動aを選択することが最適であることを意味する。したがって、方策πは状態sで行動aを選択することを考慮して改善されるべきであるという推定が成り立つ。強化学習問題では、この関連を特に「方策改善の定理(policy improvement theorem)」と呼ぶ。

この方策改善の定理モンテカルロ法においても適用される。つまりkの時の方策πとk 1の時の方策πにも該当する。モンテカルロ法方策評価は、出来事を一単位として、評価と改善を交互に実行していくのが自然とされる。各出来事が発生した後に、観測された収益が方策評価に利用される一方で、出来事の中で訪問した状態の全てに対して方策が更新される。

「方策オン型」と「方策オン型」のモンテカルロ法による制御

全ての状態と行動の組み合わせが選択されることを保証する一般的な方法は、エージェントにそれを選択させ続けることしかない。これを可能にする方法として、「方策オン型」と「方策オフ型」の区別が導入される。

方策オン型」の学習では、エージェントにepsilon-greedyなど、ソフト(soft)な方策が適用される。この方策では、学習が進むにつれてεを減算していく。これにより、相対的に確率論的であった最適方策の探索を徐々に決定論的な探索へと移行させていく。

一方「方策オフ型」のモンテカルロ法も、GPIを継承している。この「方策オフ型」のモンテカルロ法では、方策を決定論的に徐々に移行していく。そのための方法として採用されているのは、epsilon-greedy法だ。

方策オフ型」のモンテカルロ法では、最適価値関数を獲得する「挙動方策(behavior plolicy)」と、実際の評価と学習対象の「推定方策(estimation policy)」の区別を導入する。この区別を導入することのメリットの一つは、挙動方策が全ての選択可能な行動をサンプリングし続ける場合であっても、推定方策としてはGreedyのような決定論的な方策を利用し続けることができるという点にある。

$$Q^π(s, \overline{π}(s)) = \sum_{a}^{} \overline{π} (s, a) Q^π (s, a)$$

$$\DeclareMathOperator*{\max}{max}= ε \sum_{a}^{} Q^π (s, a) + (1 – ε) \max_a Q^π(s, a)$$

$$ \geq ε \sum_{a}^{} Q^π(s, a) + (1 – ε) \sum_{a}^{} \frac{π(s, a) – ε}{1 – ε} Q^π(s, a)$$

機能的拡張案:時間差分学習

強化学習問題の枠組みでは、モンテカルロ法と動的計画法を組み合わせた理論として、「時間差分学習(Temporal Difference learning; TD Learning)」が提唱されている。TD学習法は、モンテカルロ法と同様に環境のモデルを利用せずに経験から直接学習する。そして動的計画法と同様に、最終的な終息結果を待たずに、他の推定値による学習結果を部分的に参照することで推定値を更新するブートストラップ法を実行する。

TD学習法は経験によって予測問題を解決していく点でモンテカルロ法機能的に等価である。そしてこれらのアルゴリズムは、方策πに従って幾つかの経験を得ることで価値推定値を更新していく。この意味でもTD学習法はモンテカルロ法機能拡張版であると言える。

モンテカルロ法同様、TD学習法もまた「方策オン型」と「方策オフ型」の区別に対応している。とりわけ「方策オフ型」のTD学習法としてはSarsaアルゴリズムを、「方策オフ型」のTD学習法としてはQ学習アルゴリズムを、それぞれ挙げられる。これらのアルゴリズムは「TD制御アルゴリズム(TD control algorithm)」とも呼ばれる。

Sarsaのアルゴリズム

Richard Sutton and Andrew Barto (1998). Reinforcement Learning. MIT Press. 6.4 [Sarsa](https://accel-brain.com/semantics-of-natural-language-processing-driven-by-bayesian-information-search-by-deep-reinforcement-learning/2/#link2keyword=Sarsa): On-Policy TD Controlより[引用](https://accel-brain.com/erinnerung-von-anthropologischen-materialismus-in-medienasthetik/3/#link2keyword=引用)。

Q学習のアルゴリズム

Richard Sutton and Andrew Barto (1998). Reinforcement Learning. MIT Press. 6.5 Q-Learning: Off-Policy TD Controlより[引用](https://accel-brain.com/erinnerung-von-anthropologischen-materialismus-in-medienasthetik/3/#link2keyword=引用)。

SarsaとQ学習のアルゴリズム的差異

Q学習が「方策オフ型」として比較確率論的な方策比較的決定論的な方策の併存によって学習していくのに対して、Sarsaは「方策オン型」として比較確率論的な方策から決定論的な方策への移行によって学習していく。

アルゴリズムの収束性はQと方策に依存する。ε-greedyに無限回数状態-行動の写像を更新した結果、極限方策がgreedyな方策に収束する場合、Sarsaアルゴリズム確率1で最適方策と最適行動価値関数に収束することになる。

機能的拡張案:モンテカルロ法と時間差分学習法の統合

強化学習アルゴリズムは、モンテカルロ法にせよTD学習法にせよ、動的計画法やバンディット問題の背景に対する扱い方には多少の差異はあれど、方法論以上の大きな差異は無い。これらのうちのいずれかを選択しなければならないという道理も無い。むしろ、各方法を組み合わせて同時に適用することで独自のアルゴリズム設計することの方が意味を持つ。複合性を兼ね備えたアルゴリズムはそれだけ複合的な問題の解決に役立てるからだ。

しかし、理論的な概念の抽象化とその関連付けを施さなければ、方法として区別された各アルゴリズム結合させるのは難しい。そこで、モンテカルロ法TD学習法を統一する概念の導入が求められる。

適格性追跡

適格性追跡(eligibility trace)は、強化学習問題の枠組みにおいて、モンテカルロ法TD学習法の中間に位置付けられる問題解決策だ。例えばTD(λ)の学習では、λによって適格性追跡の参照方法が規定できる。SarsaであれQ学習であれ、大半のTD学習法は適格性追跡と統合することでより効率的に学習することが可能になる。

適格性追跡TD学習法をモンテカルロ法の側へと拡張させた問題解決策だ。これまで言及してきたSarsaQ学習が1ステップのTD学習であるのならば、モンテカルロ法はnステップのTD学習のうち、nを最大化したTD学習であると言える。だが環境モデルや報酬次第では、1ステップのTD学習モンテカルロ法が最適となる訳ではない。その中間にこそ最適解があり得る場合もあるだろう。適格性追跡は、この中間の解を探索する。

nステップTD予測は、nに1を代入すれば通常のTD学習となり、nに最大値を代入すれば通常のモンテカルロ法になる。一方、nの値が2や3などといった半端な値の場合は、これら双方のアルゴリズムでは対応できない。例えばnが3の場合は、最初の3回の報酬と3ステップ後の状態の推定価値に基づいて、エージェント方策を判断していくことになる。この方策の判断自体はTD学習法の範疇から逸脱していない。故にこうしてnを拡張したTD学習法を特に「nステップTD学習法(n-step TD method)」と呼ぶ。

ここでいうステップ(step)は、無論時系列的に増大していく数値を意味する。故にこのnステップTD学習法において肝となるのは、状態と報酬のシーケンスに他ならない。簡略化のために行動概念を省略するなら、このシーケンスは単純に次の数式で表せる。

$$s_t, r_{t + 1}, s_{t + 1}, r_{t 2}, r_T, s_T$$

ここでいう大文字のTは、シーケンス中の出来事における最後のステップを意味する。

Richard Sutton and Andrew Barto (1998). Reinforcement Learning. MIT Press. 7.1 n-Step TD Predictionより[引用](https://accel-brain.com/erinnerung-von-anthropologischen-materialismus-in-medienasthetik/3/#link2keyword=引用)。

このシーケンスの結果として状態sの時に得られる収益を予測するなら、通常のモンテカルロ法ならば$$V^π (s_t)$$の推定である$$V_t(s_t)$$は収益を完全な状態で更新される。

$$R_t = r_{t+1} + γ r_{t+2} + γ^2 r_{t+3} + … + γ^{T-t-1} r_T$$

一方1ステップの場合は、収益が完全な状態で更新されることは無い。この場合、収益は最初の報酬に割引率を掛け合わせた推定価値を加えた値となる。

$${R_t}^1 = r_{t+1} + γ V_t(s_t+1)$$

この数式の関連は、実際は2ステップ以後も変わりない。

$${R_t}^2 = r_{t+1} + γ r_{t+2} + γ^2 V_t(s_t+2)$$

この時、$$γ^2 V_t(s_t+2)$$は、$$γ^2 r_{t+3} + γ^3 r_{t+4} + … + γ^{T-t-1} r_T$$を意味する。故にこれに従ってステップ数を増やしていけば、いずれはnを無限回数反復した場合のモンテカルロ法へと近似されていくことになる。この近似化は、nステップ後を打ち切りにして、n 1番目の状態価値を加算することで処理される。これは無論実際に得られた収益ではなく価値推定であるため、近似すべきと考えるほどの差分があるのは確かだ。

これらのことから、nステップの報酬期待値は、実際の価値関数に対する近似によって、現在価値関数内在的に改善することが可能であると保証される。価値関数Vを用いたnステップの報酬期待値は、原理上如何なるVにおいても、Vそれ自体より$$Vπ$$をより良く推定する。これは、言い換えるなら、新しい推定に伴う誤差の最大値は、Vの内在した推定誤差の最大値に比例する。

Richard Sutton and Andrew Barto (1998). Reinforcement Learning. MIT Press. 7.1 n-Step TD Predictionより[引用](https://accel-brain.com/erinnerung-von-anthropologischen-materialismus-in-medienasthetik/3/#link2keyword=引用)。

これはnステップの収益における「誤差縮減特性(error reduction property)」と呼ばれる。この性質によって、予測の誤差は減少していくことで正確な予測へと収束していくことを形式的に表現することができる。

価値の更新は、任意のnステップにおける収益に対してのみならず、nステップの収益の平均値に対しても実行できる。例えば、2ステップの収益の半分と4ステップの収益の半分に対しても、価値を更新することができる。

$$R_t^{ave} = \frac{1}{2}R_t^{(2)} + \frac{1}{2}R_t^{(4)}$$

収益の重み付けが正の値を成しており、尚且つその合計が1になっているという条件の下であれば、この価値の更新は如何なる収益集合においても適用できる。それがたとえ無限集合であっても、例外ではない。この収益の集合は上述した「誤差縮減特性」を持つため、収束性を保証するために利用することができる。

これを前提とすれば、TD(λ)アルゴリズムは、nステップの価値の更新を平均化する方法の一種として位置付けることができる。この場合、価値更新の平均値はnステップの全ての価値更新結果から算出されている。それらの価値は次のように比例して重み付けされる。

$$λ^{n-1} (0 \leq λ \leq 1)$$

ここで、1 – λは正規化係数として参照される。重みの合計は1になることが保証されている。これらの要素から得られる価値更新は、λ収益(λ-return)と呼ばれる収益に対する価値更新となる。

$$R_t^λ = (1 – λ) \sum_{n=1}^{∞} λ^{n-1} R_t^{(n)}$$

下図のように、1ステップの収益の場合は単純に重みの最大値となる1 – λが計算される。2ステップであればその次に大きな重み付けとなる$$(1 – λ)λ$$が、3ステップの場合は$$(1 – λ)λ^2$$が、それぞれ算出される。

Richard Sutton and Andrew Barto (1998). Reinforcement Learning. MIT Press. 7.2 The Forward View of TD(λ)より[引用](https://accel-brain.com/erinnerung-von-anthropologischen-materialismus-in-medienasthetik/3/#link2keyword=引用)。

ステップが1回分追加される度に、重み付けの値はλの値の分だけ低下していく。そして終端状態に到達した時、その後のnステップの収益値は全て$$R_t$$と等価になる。この関連をもう少し簡明に表現するなら、次のように記述できる。

$$R_t^λ = (1 – λ) \sum_{n=1}^{T-t-1} λ^{n-1} R_t^{(n)} + λ^{T-t-1} R_t$$

こうしたλ収益を利用して価値の更新を繰り返すアルゴリズムを特に「λ収益アルゴリズム(λ-return algorithm)」と呼ぶ。あるステップの時間tで発生する状態価値に対する増減$$ΔV_t(s_t)$$は次のようになる。

$$ΔV_t(s_t) = α [R_t^λ – V_t(s_t)]$$

以上の適格性追跡の記述では、モンテカルロ法TD学習の特殊事例として参照可能にすることができている。モンテカルロ法に基づいた無限回数のステップ数を踏まずに、その中間に留まる姿勢を適格性追跡と呼ぶ。ただしこれまでの記述形式は専ら理論的であった。言い換えれば、この適格性追跡は「順方向のビュー(Forward View)」から記述されている。と言うのも、上記の価値更新の平均化に至っては顕著に表れている特徴だが、この観点から適格性追跡を記述すると、その計算は訪問した全ての状態に対して将来起こり得る全ての報酬を観測して、最良の組み合わせを決定する処理になる。それは下図のように、ある状態から前方を観察することで価値更新内容を決定して次の状態へと進んでいくイメージとなる。

Richard Sutton and Andrew Barto (1998). Reinforcement Learning. MIT Press. 7.2 The Forward View of TD(λ)より[引用](https://accel-brain.com/erinnerung-von-anthropologischen-materialismus-in-medienasthetik/3/#link2keyword=引用)。

この順方向のビューでは、後ろ向きの観察は実行されない。次の状態に進んだなら、次の報酬期待値を計算する上で、過去の状態を振り返る必要は無いのである。

各状態のメモリ変数としての適格性追跡

適格性追跡には、もう一つ別の見方がある。それは、適格性追跡が状態への訪問や行動の実行などのような出来事の一時的な記録であるという見方だ。この適格性追跡は、出来事(events)に関するメモリ(memory)のパラメタが学習上の変異に対して適格であることを記録する。TD誤差が発生した際には、適格性を有した状態群や行動群だけが、その誤差によって信用(credit)されるか、あるいは非難(blame)される。このことから、適格性追跡出来事と訓練情報との間の架け橋となる。

このメモリ変数としての適格性追跡は、記録した過去出来事を参照するという点で、「逆方向のビュー(backward view)」に準拠している。これは先に示した「順方向のビュー」と対になっている。そればかりか、逆方向のビューは順方向のビューの埋め合わせとして有用となる。と言うのは、順方向のビューによって未来のステップに関する知識を利用する場合には、とりわけ出来事学習結果の因果関係が不透明になる。一方、逆方向のビューは順方向のビューを近似した計算を提供する。そのため逆方向のビューにおける適格性追跡は、過去出来事を一時的なメモリとして保持しておくことによって、因果関係を明確化することができる。このビューは、原因と結果の形式で纏め上げられた出来事に対する漸進的学習アルゴリズム設計を可能にする。

逆方向のビューでは、上述したように、適格性追跡は各状態の付加的なメモリ変数のような概念として把握される。時刻tにおける状態sの適格性追跡は$$e_t(s) \in R^+ $$と表現できる。この適格性追跡は各ステップにおける全ての状態に対してγλ分だけ低下していく。各ステップで訪問された1個の状態の適格性追跡は、全ての$$s \in S$$に対して以下のように1だけ増加する。

このパラメタが言い表しているのは、ある状態を訪問した場合にはその状態に紐付く適格性追跡の値が累積していくと共に、その状態が訪問されない状況が続けば減衰していくということだ。如何なる状態においても、適格性追跡では、最近訪問された状態だけがメモリとして記録される。ここでいう「最近」とは、γλに依存する。

この場合の適格性追跡は、TD誤差発生時に各状態で学習上の変異の影響を受けることが「適格」である度合いを指し示している。例えば状態価値の予測におけるTD誤差は、次のようになる。

$$σ_t = r_{t+1} + λV_t(s_{t+1}) – V_t(s_t)$$

TD(λ)における逆方向のビューでは、TD誤差の信号全般により、「最近」訪問した全ての状態に対して均整の取れた更新(proportional update)を実行させる。言い換えれば、全ての$$s \in S$$に対して、$$ΔV_t(s) = ασ_te_t(s)$$となる。

こうしてTD(λ)に対する逆方向のビューでは、時間過去に遡る向きで学習が実行される。各時点で現在のTD誤差を観察して、その時点における適格性追跡に従う形で、先行状態に対する誤差を均整の取れた形で割り当てる。下図のように、エージェントは現時点から過去の状態に向けて誤差の値を提示しているイメージとなる。各時点でTD誤差と適格性追跡が算出できれば、各時点で価値更新を実行し続けることが可能になる。

Richard Sutton and Andrew Barto (1998). Reinforcement Learning. MIT Press. 7.3 The Backward View of TD(λ)より[引用](https://accel-brain.com/erinnerung-von-anthropologischen-materialismus-in-medienasthetik/3/#link2keyword=引用)。

ΔVの値からも明らかなように、より過去の状態ほど適格性追跡の値も小さくなる。故に現在の更新による影響度も少ない。より過去の状態ほど、TD誤差を説明する上で得られる信用(credit)は低いとも言えるだろう。逆に言えば、より「最近」の状態ほど適格性追跡の値も大きくなるために、より「最近」の状態はTD誤差を説明する上での信用が高いと言える。

適格性追跡型のSarsaアルゴリズム

これまでのTD(λ)アルゴリズムは単に状態価値に対して適格性追跡を適用させる計算形式であった。これに対して、行動価値Q(s, a)に対して適格性追跡を適用させるのならば、SarsaQ学習アルゴリズムとの関連付けを試みなければならない。以下では、方策オン型TD制御方法としてSarsa(λ)を、方策オフ型TD制御方法としてQ(λ)を、それぞれ取り上げる。

Sarsa(λ)は状態のみならず状態と行動の組み合わせに対して適格性の追跡を実行する。この場合の適格性追跡を次のように表現する。

$$e_t(s, a)$$

これは状態変数を状態行動変数に置換しているだけである。これを前提とすれば、全ての状態と行動の組み合わせに対して、以下の計算が成り立つ。

$$Q_{t+1}(s, a) = Q_t(s, a) + ασ_te_t(s, a)$$

ここでσに着目するなら、

$$σ_t = r_{t+1} + γQ_t(s_{t+1}, a_{t+1}) – Q_t(s_t, a_t)$$

となる。故に全てのsとaの組み合わせに対して、次の適格性追跡が成り立つ。

適格性追跡型のQ学習アルゴリズム

クリス・ワトキンスの適格性追跡型のQ学習アルゴリズムは、適格性追跡型のSarsaとは明確に異なるアルゴリズムとなる。その差異はやはり「方策オフ型」と「方策オン型」の区別に対応する。Q学習が「方策オン型」であるなら、学習亜された方策と行動選択で参照される方策が同一である必要は無い。Q学習ではとりわけ探索型の行動を含めた方策群に従いながら、一方ではGreedyな方策学習することで、その行動選択は準最適になる時もある。それ故に、Sarsaの場合のように単純に適格性追跡概念を導入する訳にはいかない。

適格性追跡型のQ学習の順方向のビューは限定的な観点となる。例えば時刻tにおける状態と行動の組み合わせとなるs, aの価値更新を実行していると仮定しよう。後続の2回のステップではGreedyな行動を選択して、3回目のステップでは非Greedyな探索的な行動を選択するとしよう。価値の学習において、Q学習アルゴリズムエージェントはGreedyな方策に従っている限り、その後の経験しか利用することができない。したがって、1ステップの収益と2ステップの収益は参照可能だが、3ステップの収益を参照することはできない。Greedyな方策では、nが3以上の場合に、nステップの収益を必要としないのである。

故にQ(λ)はSarsa(λ)とは異なって出来事の最後まで先読みし続ける訳ではない。Q(λ)のエージェントが先読みをするとすれば、それは探索行動時のみに限定される。Q(λ)では、行動価値の知識に基づいて実行された探索の後の1回分の行動のみが観察される。例えば最初の1回目が探索的な行動であったのならば、Q学習は1ステップの価値更新を実行する。これを一般化して、t + n回目に最初の探索行動が実行されたのならば、価値更新は最長で$$\DeclareMathOperator*{\max}{max}r_{t+1} + γr_{t+2} + … + γ^{n-1}r_{t+n} + γ^n \max_aQ_t(s_{t+n}, a)$$に対する更新となる。

Q(λ)の逆方向のビューにおいては、適格性追跡は探索行動時には常に0にある。このことを除けば、後はSarsa(λ)とアルゴリズム的に等価となる。

Q値の更新式は次のようになる。

$$Q_{t+1}(s, a) = Q_t(s, a) + ασ_te_t(s, a)$$

σは以下のようになる。

$$\DeclareMathOperator*{\max}{max}σ_t = r_{t+1} + γ \max_{a´}Q_t(s_{t+1}, a´) – Q_t(s_t, a_t)$$

しかし、速度の都合上、Q学習において適格性追跡を利用する利点は低く見積もられている。とりわけ学習の初期に探索的な行動が頻繁に繰り返されると、2ステップを超える価値更新が実行されるの稀となる。そのため、その学習速度が通常のQ学習よりも速くなることはほとんど無いとされる。後の研究者たちによってこの速度の改善が図られているが、その分実装が複雑化することが指摘されている。

問題解決策:計画と学習の区別

以上の強化学習問題の枠組みにおいて、強化学習エージェントは周辺環境観察することでその情報を分析することを可能にする。そうした環境とは、エージェントにとっての「環境のモデル(a model of the environment)」に他ならない。環境のモデルというのは、エージェントが自身の行動に対してどのように応答するのかを予測可能にするあらゆる対象を意味する。そしてこの環境のモデルは、エージェントが獲得し得る報酬の資源でもある。

ユーザーという名の人間を含意した環境のモデルは、状態と行動の組み合わせが与えられた時に結果として生じる後続の状態と報酬の予測に関する可能性の諸条件として構成される。モデルが確率的な出来事集合であるのならば、生起可能な状態や選択可能な行動は複数存在する。そしてそれらの組み合わせは一定の生起確率を持つ。そうしたモデルは確率構成する分布(distribution)として記述できる。例えば状態遷移確率報酬期待値はベイズ推定の射程範囲でもある。

モンテカルロ法指し示している通り、エージェント経験はシミュレーションであっても良い。この経験のシミュレーションに環境のモデルを利用することもできる。初期の状態と行動の組み合わせが付与されれば、モデルは可能な状態遷移や選択可能な行動群を指し示すと共に、その確率分布が生起確率で重み付けされたあらゆる可能な遷移対象を構成する。開始状態と方策さえ設定されれば、モデルは関連するあらゆる出来事を記述できる。

こうしたシミュレーション上の経験(simulated experience)の特徴を明確にする上で、計画(planning)の方法学習(learning)の方法区別を導入することは有用となる。ここでいう計画の方法は、動的計画法やヒューリスティック探索などのように、環境のモデルを必要とする学習アルゴリズムを指す。一方、モデルが無くとも機能するモンテカルロ法やTD法は学習方法に位置付けられる。双方は、将来の出来事を先読みしながら近似価値関数の更新と共に価値関数計算を可能にする点では機能的に等価だ。しかしながら、強化学習問題を追究するのであれば、これら二つの方法は一つのアーキテクチャで統合してしまうのが望ましい。

そのアーキテクチャの一例として、Dyna-Qという単純明快な機能を挙げることができる。Dyna-Qは実際の環境にモデルをより正確に適合させるように学習すると共に、これまで記述してきたような価値関数方策の改善を両立する。強化学習問題では、とりわけ前者を「モデル学習(model-learning)」と呼び、後者を「直接的強化学習(direct reinforcement learning)」と呼ぶ。ここでいう「直接的」というのは、「計画(planning)」という、環境のモデル越しに実行する強化学習意味する「間接的強化学習(indirect reinforcement learning)」と対を成している。そしてDyna-Qはこれらの諸概念をサイクルの如く反復する仕様になっている。

Richard Sutton and Andrew Barto (1998). Reinforcement Learning. MIT Press. 9.2 Integrating Planning, Acting, and Learningより[引用](https://accel-brain.com/erinnerung-von-anthropologischen-materialismus-in-medienasthetik/3/#link2keyword=引用)。

直接的強化学習と間接的強化学習はそれぞれ対成す機能を持つ。間接的強化学習では限られた量の経験をより多く活用する。そのため、環境との相互作用が少なくとも、より良い方策を設定できる。ただし当のモデル設計が誤っていれば、その影響を被る。これに対して、直接的強化学習は素朴なアルゴリズムではあるものの、モデル設計による影響をほとんど受けずに済む。専らこの双方は対立する問題解決策として観察されている。一方Dyna-Qはこれら双方の問題解決策を両立する折衷案となる。

Richard Sutton and Andrew Barto (1998). Reinforcement Learning. MIT Press. 9.2 Integrating Planning, Acting, and Learningより[引用](https://accel-brain.com/erinnerung-von-anthropologischen-materialismus-in-medienasthetik/3/#link2keyword=引用)。

上図のように、Dyna-QをはじめとしたDynaエージェントアーキテクチャでは、エージェント環境の相互作用を基盤として、これによって実際上の経験構成される。特に図中の左側の処理が直接的強化学習で、右側の処理はモデルによる間接的強化学習指し示している。モデルは実際の経験から学習される。そしてそれがシミュレーション上の経験の前提条件となっている。したがってDynaエージェント強化学習アルゴリズムは「計画」と「学習」の最終的な共通点となる。経験の発生源が可変性を持ち、その他の処理は共通性を持つ。

スポンサーリンク