Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning

概要

本稿では，確率的なユニットを含むコネクショニストネットワークに対する連想強化学習アルゴリズムの一般的なクラスを紹介する。 REINFORCEアルゴリズムと呼ばれるこれらのアルゴリズムは，即時強化課題とある限定された形式の遅延強化課題の両方において，期待される強化の勾配に沿った方向に重み調整を行うことが示されており，勾配の推定値を明示的に計算することなく，またそのような推定値を計算できるような情報を保存することさえもなく，これを行うことができる。このようなアルゴリズムの具体例は、既存のアルゴリズムと密接な関係にあるものもあれば、新規性はあるがそれ自体が興味深いものもあります。また、このようなアルゴリズムがバックプロパゲーションとどのように自然に統合できるかを示す結果も示されている。最後に、このようなアルゴリズムを使用する上での問題点を簡単に説明し、その限界的な動作についての知見や、同様の、しかしより強力な強化学習アルゴリズムを開発するために役立つ可能性のある更なる検討事項についても述べています。

1. はじめに

強化学習の一般的な枠組みには，様々な形の関数最適化から学習制御まで，幅広い問題が含まれています。これらの分野の研究は、それぞれの問題に重点を置く傾向がありますが、現実的な環境で活動する自律エージェントのための効果的な強化学習技術は、これらすべての問題に共同で取り組む必要があると考えられます。このように、強化学習問題を単純に扱いやすくするために、限られた形の強化学習問題に焦点を当てることは有効な研究戦略であるが、最も困難な問題に対する最終的な解決策は、おそらく広範囲の適用可能な技術の統合を必要とすることを念頭に置くことが重要である。

本論文では、学習者が入力と出力の対応付けを行うことを意味する連想課題と、1つの限定された例外を除き、学習者に提供される強化（すなわち、ペイオフ）が直近の入力と出力のペアによってのみ決定される即時強化を伴う課題のための、あるアルゴリズムに関する分析結果を示します。

遅延強化タスクは明らかに重要であり、最近注目を集めていますが、このようなタスクのアルゴリズムを開発するために広く用いられているアプローチは、即時強化学習者と、時間差法を用いた適応的な予測者または批評者を組み合わせることです（Sutton, 1988）。 Barto, Sutton and Anderson (1983)やSutton (1984)が研究したアクター批判アルゴリズムは、Watkins (1989; Barto, Sutton, & Watkins, 1990)のQ-learningアルゴリズムと同様に、明らかにこの形式のものです。ここでのさらなる仮定は、どのような強化学習アルゴリズムにおいても常に必要な要素である学習者の探索行動が、学習者の入出力行動におけるランダム性によって提供されるということです。これは、望ましい探索行動を実現するための一般的な方法ですが、特定のケースでは、系統的な探索や見かけ上の最適な選択肢の一貫した選択など、他の戦略が利用可能な場合があることに注意する必要があります。後者の戦略は、例えばA*探索で起こるように、代替行動の良し悪しが、常に過度に楽観的であり、経験を重ねることで現実的になるような推定値によって決定される状況で有効である（Nilsson, 1980）。さらに、ここではすべての結果をコネクショニスト・ネットワークの観点から捉え、関連する勾配を追跡または推定するアルゴリズムに主眼を置いています。このようなアルゴリズムには多くの限界があることが知られていますが、その研究が有用である理由はいくつかあります。

第一に、バックプロパゲーション（leCun, 1985; Parker, 1985; Rumelhart, Hinton & Williams, 1986; Werbos, 1974）の経験が示すように、勾配は、多くの場合、実装が簡単で驚くほど効果的なアルゴリズムを生成するための強力で一般的なヒューリスティックな基礎を提供していると思われる。次に、より洗練されたアルゴリズムが必要な場合には、勾配計算がそのようなアルゴリズムの中核となることが多い。また、ある種の既存のアルゴリズムが、このような勾配分析から生まれるアルゴリズムに似ている場合には、そのアルゴリズムに対する理解が深まる可能性がある。

ここで紹介するアルゴリズムのもう1つの特徴は、適切な勾配を統計的に登るということだけで説明できるにもかかわらず、この勾配の推定値を明示的に計算することなく、また、そのような推定値を直接計算できるような情報を保存することなく、これを実行していることである。これが、タイトルで「シンプル」と呼ばれている理由ですもっとわかりやすい形容詞はnon-model-basedでしょうか。この点については、本稿の後のセクションでさらに検討します。

ここではコネクショニストの視点を採用していますが、実行した分析のある側面は、適応的な入力・出力マッピングを実装する他の方法にもそのまま適用できることに留意する必要があります。ここで紹介する結果は、入出力マッピングがパラメータ化された入力制御分布関数で構成され、そこからランダムに出力が生成され、対応するアルゴリズムがパフォーマンスのフィードバックに基づいて学習者の分布関数を修正するような学習者に一般的に適用されます。ここでは勾配法を用いているため、これらの結果の潜在的な適用性に対する唯一の制限は、特定の明白な微分可能性の条件を満たさなければならないことです。ここで紹介した結果の多くは、様々な形で以前の技術報告書や会議論文に掲載されています（Williams, 1986; 1987a; 1987b; 1988a; 1988b）。

2. 強化学習コネクショニストネットワーク

特に指定のない限り，学習エージェントは複数の個別ユニットからなるフィードフォワードネットワークであり，各ユニットはそれ自体が学習エージェントであると仮定する．ここでは、すべてのユニットが確率的に動作するという追加の仮定をしていますが、後にネット内に決定論的なユニットがある場合も考慮すると便利です。ネットワークは、環境からの外部入力を受け取り、対応する活動をネットに伝播させ、出力ユニットで生成された活動を評価のために環境に送ることで動作します。評価は、スカラーの強化信号rで構成され、これはネット内のすべてのユニットにブロードキャストされると仮定しています。この時点で、各ユニットは、使用している特定の学習アルゴリズムに基づいて、その重みを適切に修正し、サイクルを再び開始します。

ここで使用する表記法は以下の通りです。ネットワーク内のi番目のユニットの出力をYiとし、そのユニットへの入力パターンをx^iとする。この入力パターンX^iはベクトルであり、その個々の要素（通常はx_jと表記）は、ネットワーク内の特定のユニットの出力（i番目のユニットに直接出力を送るもの）か、環境からの特定の入力（そのユニットがたまたま環境から直接入力を受けるように接続されている場合）である。そして、出力y^iは、x^iと、このユニットへの入力ラインの重みw_ijに依存する分布から引き出される。各iについて、w^iはすべての重みw_ijからなる重みベクトルを表すとする。また、ネットワーク内のすべての重みw_ijからなる重み行列をWとする。より一般的な設定では、w^iはi番目のユニット（またはエージェント）の動作が依存するすべてのパラメータの集合体、Wは全体（またはエージェントの集合体）の動作が依存するパラメータの集合体と見なすことができます。

さらに、各iについて、g_i (xi, w^i, x^i) = Pr {yi = xi | w^i, x^i }とすると、g_iはユニットのパラメータとその入力の関数としてのy_iの値を決定する確率質量関数であることになる。 (説明を簡単にするために、可能な出力値yiのセットが離散的である場合に適した用語と表記を一貫して使用していますが、g_iが対応する確率密度関数であるとみなされる場合、導き出される結果は連続値のユニットにも適用されます)。ベクトルw^iには、i番目のユニットの入出力動作が依存するすべてのネットワーク・パラメータが含まれているので、g_iをg_i(xi, w^i, x^i) = Pr{y_i = xi I W, x^i }と定義することも同様に可能である。ここで名前を挙げた r, yi, x^i などの量の多くは実際には時間に依存していることに注意してください。しかし、このような量が1つの方程式に複数現れる場合、それらは同じ時間ステップ t の値を表していることを理解した上で、この時間依存性への明示的な言及を控えることは、一般的に続編で便利です。即時強化タスクの文脈では、ネットワークと環境の相互作用の各時間ステップのサイクルを試行と呼んでいます。これらの定義を説明し、有用なサブクラスを紹介するために、確率的半線形ユニットを、出力yiが質量関数が単一のパラメータP_iを持つ所与の確率分布から引き出されるものと定義し、それは次のように計算される。

ここで、fは微分可能なスカッシング関数であり

これは、コネクショニストネットワークで広く使われている半線形ユニットに、単一パラメータ化された乱数生成器が続いていると見ることができます。確率的半線形ユニットの注目すべき特殊なケースとして、ベルヌーイ半線形ユニットがあります。このユニットでは、出力y_iはパラメータP_iを持つベルヌーイ確率変数であり、これは、可能な出力値が0と1のみであることを意味し、Pr {yi = 0 | w^i, x^i} = 1 - p_i、Pr {yi = 1 | w^i, x^i} = p_iとなります。このように、ベルヌーイの半線形ユニットについては次が成り立つ

ここでp_iは式(1)と(2)で計算されます。このタイプのユニットは、ボルツマンマシン(Hinton & Sejnowski, 1986)や、Bartoらが研究した強化学習ネットワーク(Barto & Anderson, 1985; Barto & Jordan, 1987; Barto, Sutton, & Brouwer, 1981)など、確率的なユニットを用いたネットワークによく見られます。 Bernoulli semilinear unitという名前は、よく知られているものに新しい名前を付けただけのように見えるかもしれませんが、この用語を使うことで、より一般的なクラスに属していることを強調することができます。一般的に使用されているスカッシング関数はロジスティック関数であり、次のように与えられる。

ベルヌーイ乱数生成器とロジスティック・スカッシング関数の両方を使用する確率的半線形ユニットは、ベルヌーイ-ロジスティック・ユニットと呼ばれる。ここで、ベルヌーイ半線形ユニットのクラスには、その計算が、加法的な入力ノイズまたはノイズのあるしきい値と一緒に線形しきい値計算の観点から代替的に記述される特定のタイプのユニットが含まれることを観察する。この観察は有用である。というのも、この後者の定式化は、Bartoたち(Barto, 1985; Barto & Anandan, 1985; Barto & Anderson, 1985; Barto, Sutton, & Anderson, 1983; Barto, Sutton, & Brouwer, 1981; Sutton, 1984)の調査で使用されたものだからである。具体的には、ユニットが出力y_iを次のように計算すると仮定している。

ここで、etaは与えられた分布PSIから無作為に引き出される。このようなユニットがベルヌーイ半線形ユニットと見なせることを確認するために、次のようにします。

次が得られる

したがって PSIが微分可能である限り、このようなユニットは、f_i(s_i)=1 - PSI(-s_i)で与えられるスカッシング関数f_iを持つベルヌーイ半線形ユニットとなります。

3. 期待強化性能基準

勾配学習アルゴリズムを検討するためには、最適化する性能指標が必要である。連想法であるかどうかに関わらず、即時強化学習の問題で非常に自然なものは、学習システムのパラメータの特定の選択を条件とする強化信号の期待値です。ここで、Eは期待演算子、rは強化信号、Wはネットワークの重み行列を表します。ここで期待値を用いる必要があるのは、以下のいずれかにランダム性があるためです。

(1)環境がネットワークへの入力を選択すること、 (2)ネットワークが特定の入力に対応する出力を選択すること、 (3)環境が特定の入力/出力ペアに対する強化値を選択すること。

E {r I W} を時間とは無関係に議論するのは、第一と第三のランダム性の源が定常分布によって決定され、環境がネットへの入力パターンを選択することも時間とは無関係に決定されると仮定した場合のみ意味があることに注意してください。このような仮定がない場合、任意の時間ステップにおけるrの期待値は、システムの歴史と同様に時間の関数となる可能性があります。したがって、これらの定常性と独立性の条件が成り立つことを暗黙のうちに仮定しています。これらの仮定により、E{r I W}はW の定義された決定論的な関数であることに注意してください。したがって、この形式では、強化学習システムの目的は、E{r I W}が最大となる点を求めて、すべての可能なウェイトマトリックスWの空間を探索することです。

4. REINFORCEアルゴリズム

連想即時強化学習課題に直面しているネットワークを考えてみましょう。このネットワークでは、各試行で強化値rを受け取った後に重みが調整されることを思い出してほしい。このネットワークの学習アルゴリズムが、各試行の終了時にネットワークの各パラメータw_ijを次の量だけ増加させるものであるとする。

ここで α_ijは学習率係数、b_ijは強化ベースライン、e_ij = partial In g_i/ partial w_ijは_wijの特性適格性と呼ばれる。さらに、強化ベースラインb_ijは、Wとx^iが与えられたとき、yiに条件付きで独立であり、レートファクターα_ijは非負であり、最大でもw_iとtに依存するとする（通常、α_ijは定数とする）。この名前は「REward Increment = Nonnegative Factor x Offset Reinforcement x Characteristic Eligibility」の頭文字をとったもので、アルゴリズムの形態を表しています。このクラスのアルゴリズムが興味深いのは、次のような数学的な結果です。

定理 1.

任意のREINFORCEアルゴリズムにおいて、E {ΔW | W} と ∇wE{r I W} の内積は非負である。さらに，すべての i と j に対して α_ij > 0 であれば，∇wE{r I W} = 0 のときだけ，この内積が 0 になります．また，αij = α がi と j に依存しないとき，E{ΔW | W} = α ∇wE{r I W} となります．

この結果は、性能尺度E {r |W}の重み空間での勾配である∇wE{r I W}をE {ΔW | W} に関連づける。具体的には，そのようなアルゴリズムでは，重み空間の平均更新ベクトルは，この性能指標が増加する方向にあるということです。この定理の最後の文は，各重み w_ij に対して，量 (r - b_ij) partial ln g_i/ partial w_ij が partial E {r I W}/ partial w_ij の不偏推定値を表すという主張と等価である．この定理の証明は付録Aに記載されている。

このようなアルゴリズムにはいくつかの興味深い特殊なケースがあり、そのうちのいくつかは既に文献で提案・検討されているアルゴリズムと一致しており、いくつかは新規のものである。まず、いくつかの既存のアルゴリズムがREINFORCEアルゴリズムであることを示し、そこから定理1がそれらに適用されることがすぐにわかる。また，このクラスに属するいくつかの新しいアルゴリズムについても検討する．

まず，（非強化）入力を持たないベルヌーイユニットを考え，適応すべきパラメータがpi = Pr {y_i = 1}であると仮定します．これは、行動に0と1のラベルを付けた2行動の確率的学習オートマトン(Narendra & Thathatchar, 1989)に相当します。確率質量関数g_iは以下のように与えられます。

ここから、パラメータPiの特性適格性は次のように与えられます。

Piが0または1にならないと仮定している．

このようなユニットに対する特定のREINFORCEアルゴリズムは、強化ベースラインにb_i = 0を選択し、レートファクターとしてα_i = rho_i p_i(1 - Pi)を使用することで得られる。ただし0 < rho_i < 1これにより、次のようなアルゴリズムが得られます。

これを、上記の結果(5)を用いて計算する。強化信号が0と1に限定されている場合のこのアルゴリズムの特殊なケースは、linear reward-inaction (L_R-I) stochastic learning automaton (Narendra & Thathatchar, 1989)の2アクションバージョンと一致します。このようなユニットで構成される「ネットワーク」は、このような学習オートマトンのチームを構成し、それぞれが個別の学習率を使用する。 LRオートマトンのチームの挙動については、NarendraとWheeler(1983; Wheeler & Narendra, 1986)が研究している。

ここで、ベルヌーイ線型ユニットを考える。この場合、g_i(y_i, w^i, x^i)は上記(4)の右辺で与えられ、p_iは(1)式と(2)式を用いてw^iとx^iで表される。特定のパラメータwijに対する特性適格性を計算するには、連鎖法則を用いる。式(1)と(2)を微分すると、d p_i/d s_i = f_i'(si)、partial s_i/ partial w_ij = x_jが得られる。 partial ln g_i/ partial p_i (y_i, w^i, x^i)が上記(5)の右辺で与えられることに注目して、この3つの量を掛け合わせると、重みwijに対する特性適格性は次のように与えられる。

piが0または1にならない限り．式(3)で与えられるfがロジスティック関数である特殊なケースでは、piが0や1になることはなく、f'(s_i)=p_i(1 - pi)となるので、w_ijの特性適格性は単純に次のようになる

ここで、このようなベルヌーイロジスティックユニットの任意のネットワークを考える。すべてのiとjに対して、α_ij = αとb_ij = 0を設定すると、次のような形式のREINFORCEアルゴリズムが生成されます。

これを上記の結果(7)を用いて計算します。これを連想報酬報酬（A_{R-P}）アルゴリズム（Barto, 1985; Barto & Anandan, 1985; Barto & Anderson, 1985; Barto & Jordan, 1987）と比較するのは興味深いことです。それはr in [0,1]について次の学習ルールを使用します

ここでαは正の学習率パラメータであり、0＜λ＜=1である。 λ＝0の場合、これは連想報酬作用（A{R-I}）アルゴリズムと呼ばれ、この場合、学習規則は式（8）に還元されることがわかる。ゆえに、A{R-I}をベルヌーイロジスティックユニットのネットワークに適用すると、REINFORCEアルゴリズムとなります。

これまでに検討したすべての例では、強化ベースラインは0です。しかし，強化比較(Sutton, 1984)を用いることも，REINFORCEの定式化と一致しています．この戦略では，過去の経験に基づいて，今後の強化の適応的な推定値を維持します．例えば，ベルヌーイロジスティックユニットのネットワークでは，次のような学習則を用いることができます。

r^の計算がyiの現在値（またはrの現在値）に基づくことがない限り、REINFORCEアルゴリズムとなります。 r^を計算するための一般的なアプローチの1つは，指数的平均化スキームを使用することです。

ここで，0＜ γ ＜=1である。また、r^をユニットへの現在の入力パターンx iの関数とするなど、より洗練された戦略もREINFORCEの枠組みに合致しています。今回の解析結果は，REINFORCEアルゴリズムにおける強化ベースラインの様々な選択を比較する根拠とはなりませんが，一般的には強化比較を用いることで，より優れた性能を持つアルゴリズムになると考えられています。 REINFORCEアルゴリズムの性能に関する質問については、以下で詳しく説明します。

5. エピソーディックREINFORCEアルゴリズム

ここでは，REINFORCEクラスのアルゴリズムを，ネットワークにループがある場合や，環境が未知の，場合によっては可変の遅延で強化値を提供する場合のような，時間的な信用割り当ての要素を持つ特定の学習問題に拡張する方法を考える．ここで、各エピソードはk個の時間ステップで構成されており、各時間ステップにおいて、ユニットはその出力を再計算し、環境はシステムへの非強化入力を変更することができる。各エピソードの終わりには、1つの強化値rがネットに与えられる。このアルゴリズムの導出は、"unfolding-in-time "マッピングの使用に基づいています。このマッピングは、一定期間にわたって動作する任意のネットワークNに対して、サイクルを持たないが対応する挙動を示す別のネットワークNを生成します。展開されたネットワークNは、各時間ステップごとにNを1回複製することで得られます。形式的には、これはNの各時間依存変数vに、値が時間に依存せず、すべての適切なtに対してv(t)=v^tという特性を持つ、Nの対応する時間インデックス付きの変数セット{v^t}を関連付けることになります。特に、Nの各重みw_ijは、Nのいくつかの重みw^t_ijを生み出し、その値はすべて、エピソードにわたってwijが一定であると仮定されているので、互いに、そしてNのwijの値に偶然にも等しくなります。この問題で検討されるアルゴリズムの形式は以下の通りである。各エピソードの終了時に、各パラメータwijを次のように増加させます。

ここで、すべての表記は先に定義したものと同じであり、eij（t ）は特定の時間tで評価されたw_ijの特性適格性を表している。定義上、eli（t）＝e^t_ijであり、後者は非循環ネットワークN*内で意味を持つ。例えば、同期的に更新されるベルヌーイロジスティックユニットの完全に相互接続されたリカレントネットワークでは、eij (t) = (yi (t) - pi (t))x_j(t - 1)となる。すべての量はREINFORCEアルゴリズムに必要な条件を満たしていると仮定し，特に，各iとjについて，強化ベースラインb_ijは出力値y_i(t)のいずれにも依存せず，レートファクターα_ijは最大でw^iとエピソード数に依存する．このような形式のアルゴリズムを(このような学習問題を対象とした)エピソーディックREINFORCEアルゴリズムと呼ぶ。例えば，ネットワークがベルヌーイロジスティックユニットで構成されている場合，エピソード型REINFORCEアルゴリズムは，次のようなルールで重みの変更を指示します。

以下の結果は、付録Aで証明されています。

定理2．

任意のエピソード型REINFORCEアルゴリズムにおいて、E {ΔWI W}と∇wE{r | W}の内積は非負である。さらに，すべての i と j に対してa_ij > 0 であれば，∇wE {r I W} = 0 のときのみ，この内積はゼロとなる．また，αij = α が i と j に依存しないとき，E{ΔW I W} = α∇E{r I W} となる．

このアルゴリズムで注目すべき点は、ネットワークの各パラメータwijに対して単一のアキュムレータを使用して、もっともらしいオンライン実装を行っていることです。このアキュムレータの目的は、適格和を形成することであり、その各項は、リアルタイムで実行されるネットワークの動作にのみ依存し、最終的に受け取る強化信号には依存しない。このようなエピソード学習タスクのより一般的な定式化も可能で、強化信号はエピソードの最後だけでなく、エピソード中の各時間ステップでネットワークに配信されます。この場合、適切なパフォーマンス指標は E {sum{t=1}^k r(t) |W] となります。この場合の統計的勾配追従アルゴリズムを作成する一つの方法は、(11)のrを単純にsum_{t=1}^k r(t)に置き換えることですが、rが因果関係にある場合、つまり以前の時間からのネットワークの入力と出力にのみ依存する場合、必要なクレジットの割り当てを行うためのより良い方法がある可能性があることに注意することは興味深いことです。大まかに言えば、kタイムステップ間隔でのこの学習問題を、k個の異なるが重複するエピソード学習問題として扱い、すべてのエピソードの最初から始めるというアイデアです。このアプローチの詳細については、これ以上の議論は省略します。

6. 多パラメータ分布を用いたREINFORCE

REINFORCEのフレームワークの興味深い応用例として，スカラ出力を確率的に多パラメータ分布から決定するユニットの学習アルゴリズムの開発がある。このようなユニットの計算方法としては、まず、重みと入力に基づいて決定論的な計算を行い、乱数生成プロセスを制御するすべてのパラメータの値を取得した後、適切な分布からランダムに出力を引き出すという方法があります。例えば、正規分布は、平均値muと標準偏差sigmaの2つのパラメータを持っています。このような分布に従って出力を決定するユニットは、まず、muとsigmaの値を決定的に計算し、次に、平均がこのmuの値に等しく、標準偏差がこのsigmaの値に等しい正規分布から出力を引き出します。

このようなガウスユニットの便利な点は、出力の平均値と分散値を個別に制御できることです。これが面白いのは、muを制御することは、ユニットの探索行動を制御することに等しいからです。一般的に、マルチパラメータ分布を用いたランダムユニットは、シングルパラメータ分布を用いたランダムユニットとは異なり、どこを探索するかに関わらず、探索行動の度合いをコントロールできる可能性があります。このようなユニットに対するREINFORCEのアルゴリズムは、ガウス型ユニットを例にすると、簡単に導出できることがわかります。このようなユニットの出力の平均値と標準偏差を入力と重みから決定する特定の手段にこだわるのではなく、単に平均値と標準偏差自体がユニットの適応可能なパラメータであるかのようにこのユニットを扱うことにします。これらのパラメータの実際の適応可能なパラメータとユニットへの入力に対するより一般的な機能依存性は、単に連鎖法則の適用を必要とする。 Gullapalli (1990)は、これらのパラメータを計算するための特別なアプローチとして、共通の入力ラインのセットで別々の加重和を使用しています。表記を簡単にするために、1つのユニットに焦点を当て、通常のユニットインデックスの添え字を省略します。このようなユニットでは、可能な出力のセットは実数のセットであり、1回の試行での出力yを決定する密度関数gは次のように与えられます。

このとき、xの特性適格性は

であり、aの特性適格性は

このユニットのREINFORCEアルゴリズムは次のような形になります。

また，

ここで、α_mu、b_mu、α_sigma、b_sigmaは適切に選択されます次を設定することで、合理的なアルゴリズムが得られます。

ここで、αは適当に小さい正の定数であり、b_mu＝b_sigmaを強化比較方式に従って決定させる。正規分布のパラメータmuの特性適格性を示す式(12)と、ベルヌーイ分布のパラメータpの特性適格性を示す式(5)が似ていることは興味深い。 pは対応するベルヌーイ確率変数の平均であり、p（1-p）は分散であるから、両式は同じ形をしている。実際、平均パラメータの特性適格性は、次の結果で述べられているように、さらに多様な分布に対してこの形を持っています。

命題1

確率質量または密度関数gが次のような形をしているとします。

ある関数Q，D，Sについて．ここで，mu，theta_2 ....theta_k は分布の平均値であるようなパラメータである。すると

ここでtheta_2は分布の分散です。この形式の質量関数や密度関数は、指数関数族の分布の特殊なケースを表しています(Rohatgi, 1976)。ポアソン分布、指数分布、ベルヌーイ分布、正規分布など、よく知られている多くの分布がすべてこの形であることは簡単に確認できます。この命題の証明は付録Bにあります。

7. バックプロパゲーションとの互換性

REINFORCEは，他の多くの確率的ユニットのネットワークに対する強化学習アルゴリズムと同様に，基本的に，局所的な行動の変化と，その結果として強化信号によって与えられる大域的なパフォーマンスの変化との間の相関を測定することによって動作することに留意するとよい。 このようなアルゴリズムでは、ユニット間の接続性の影響に関する情報はすべて無視されます。 ネットワーク内の各ユニットは、強化信号の変化に対する出力の変化の影響を、自分が直接接続されているユニットへの影響とは無関係に判断しようとします。これに対し、バックプロパゲーションアルゴリズムは、個々のユニットがお互いに及ぼす影響を知ることで、効果の連鎖全体が予測できることを利用しています。バックプロパゲーション・アルゴリズムは、決定論的ユニットのネットワークにおける教師付き学習にのみ適していますが、バックワードパスによって関連する偏微分を決定するこのアルゴリズムの単一のコンポーネントにバックプロパゲーションという用語を使用することも意味があります。(この意味では、チェーンナイルの計算上の実装に過ぎません）。) このような意味で、バックプロパゲーションを、今回検討した統計的勾配追従型強化学習アルゴリズムにどのように統合するかを検討することができます。ここでは、バックプロパゲーションの2つの利用方法を検討します。

7.1. 決定論的な隠れユニットを用いたネットワーク

確率的な出力ユニットと決定論的な隠れユニットを持つフィードフォワード・ネットワークを考えてみましょう。このようなネットワークを強化学習システムとして使用することは、ランダム性を出力ユニットに限定することで、必要な探索を行うことができるため、理にかなっています。ネットワークの入力ベクトルをx、ネットワークの出力ベクトルをyとします。ここで、g(XI, W, x) = Pr{y = XI I W, x}を、ネットワーク全体の入出力の振る舞いを記述する全体的な確率質量関数と定義することができます。ネットワークの出力が一般的にスカラー値ではなくベクトル値であることを除けば、REINFORCEのアルゴリズムを導出するために使用した形式や議論は、このようにローカルではなくグローバルな視点を持っている場合にはほとんど変化なく適用できます。特に、定理1の証明に用いた引数をベクトル値の出力の場合に簡単に拡張すると、ネットワークの任意の重みw_ijに対して、(r - b_ij) partial ln g/ partial w_ijがpartial E{r I W}/ parital w_ijの不偏推定値を表すことがわかります。ここで、Oを出力ユニットのインデックスセットとします。すべてのランダム性は出力ユニットにあり、そのランダム性はこれらのユニット間で独立しているため、次のようになります。

ここで、各kについて、x^kは、パターンxがネットワークに提示された結果、k番目のユニットの入力に現れるパターンである。なお、各x^kはxに決定論的に依存している。したがって

次を満たす

明らかに、この和はバックプロパゲーションによって計算することができる。例えば、出力ユニットがベルヌーイ半線形ユニットである場合、パラメータp_kを中間変数として用い、任意のウェイトw_ijの特性適格性を次のように書くことができます。

これは次を "注入 "することで効率的に計算することができます。

を，各kについて、k番目のユニットのスカッシュ関数の直後に計算し、その後、標準的なバックワードパスを実行することで．なお、w_ijが出力ユニットに付けられた重みである場合、このバックプロパゲーションの計算は、単に先に導かれた結果（6）を生じさせる。この結果は、ベルヌーイパラメータPiの特性適格性を、"squasher "と "summer "からなるサブユニットにバックプロパゲーションさせたものである。

ここでは、確率的な出力ユニットを持つネットワークのみに注目しましたが、このような結果は、確率的なユニットと決定論的なユニットが任意に混在するネットワークにもさらに一般化できることは容易に理解できるでしょう。この場合のアルゴリズムは，出力ユニットであるかどうかに関わらず，各確率ユニットで相関式のREINFORCE計算を行い，バックプロパゲーションを用いてその他の関連する偏微分を計算（正確には推定）するというものである．さらに，必ずしもREINFORCEに基づくものではない不偏推定値の計算と，決定論的関数によるバックプロパゲーションとの間に，より一般的な互換性を証明することも難しくありません。すなわち，ある変数群が第2の変数群に決定論的に依存する場合，第1の変数群に対する偏微分の不偏推定値をバックプロパゲーションすると，第2の変数群に対する偏微分の不偏推定値が得られるというものである．直感的にそうなることは合理的ですが、この結果を利用することはないので、ここでは厳密な数学的詳細は省略します。

7.2. 乱数発生器を経由したバックプロパゲーション

先ほど説明したアルゴリズムは、ネットワークの決定論的な部分でバックプロパゲーションを利用していますが、乱数発生器の入力側で偏微分情報を得る必要がある場合には、相関式の計算が必要になります。仮に、「乱数生成器をバックプロパゲーションする」ことができたとしましょう。どういうことかというと、確率的半線形ユニットを考えて、出力yiに何らかの決定論的な依存性を持つ関数Jがあるとします。この状況の例としては、ユニットが出力ユニットで、J = E {r I W}で、ネットワークの出力が正しいかどうかに応じて強化が行われる場合です。大まかには、partial J/ partial y_iの知識からpartial J/ partial piを計算できることが望ましい。しかし、ランダム性があるため、これらの量の間に決定論的な関係があるとは期待できない。より合理的な性質としては，partial E{J | p_i} / partial p_iがE {partial J/ partial y_i I p_i }によって決定されることが求められます．残念ながら、この性質も一般には成立しません。例えば、ベルヌーイ単位では、JがYiの非線形関数であるときは、この2つの量の間に特別な関係がなくてもよいことを確認するのは簡単です。しかし、乱数生成器の出力がそのパラメータの微分可能な関数として書ける場合、先ほど説明した決定論的計算によるバックプロパゲーションのアプローチを適用することができます。例として，ガウスユニットで使用されている通常の乱数生成器を考えてみましょう．その出力yは、パラメータmuとsigmaに応じてランダムに生成されます。次のように書くことができます。

ここで、zは標準正規偏差です。ここから次のことがわかります。

また

そのため、例えば、ガウス型隠れユニットによるバックプロパゲーションと、出力ユニットにおけるREINFORCEの使用を組み合わせることができる。この場合，そのようなユニットのmuに対する特性適格性は，出力値yに対して計算されたものと等しく設定され，一方，sigmaパラメータに対する特性適格性は，yに対するものに(y - mu)/sigmaを乗じて得られる。これらの結果は、muが平均値でsigmaが標準偏差であることに何ら依存していないことは注目に値します。また、muが変換パラメータでsigmaが分布のスケーリングパラメータである場合も同様の結果となります。より一般的には，パラメータへの依存性が微分可能である限り，出力がパラメータといくつかの補助的なランダム変数の関数として表現できるときは，当然ながら同じ手法を使用することができる。なお、ここでの議論は、上述のREINFORCEアルゴリズムの特性適格性を計算する際にバックプロパゲーションを使用した場合の結果に基づいており、結論は必然的にこのバックプロパゲーションの使用方法に限定されます。しかし，バックプロパゲーションは一般的に勾配推定値の不偏性を保持することも事実であるため，この形式の議論を適用することで，連続値の確率的ユニットのネットワークを使用する他の様々な状況でバックプロパゲーションを利用した統計的勾配追従アルゴリズムを得ることができます。このようなアプリケーションの1つは、そのようなネットワークの教師付きトレーニングです。

8. アルゴリズムの性能とその他の問題

8.1 収束特性

ここで行った分析の大きな限界は、REINFORCEアルゴリズムの漸近特性の予測にすぐにはつながらないことである。収束するとすれば、局所的な最大値に収束することが予想されるが、そのような収束はなくてもよい。 REINFORCEアルゴリズムの漸近挙動を解析的に明らかにする必要があるが，そのような結果はまだ得られていないため，シミュレーション研究がこれらのアルゴリズムの挙動を理解するための主要な情報源となっている．ここでは，文献で報告されているものと，現時点では予備的なものを含め，いくつかのシミュレーション結果を紹介する． Sutton（1984）は、単一ベルヌーイユニットの「ネットワーク」を用いて、非連想および連想の即時強化課題に直面する多くのアルゴリズムの性能を研究しました。調査されたアルゴリズムの中には，L_{R-I}と式(9)および式(10)に基づくものがあり，これは強化比較を用いたREINFORCEに過ぎません。これらの研究では，強化比較を用いたREINFORCEが他のすべてのアルゴリズムよりも優れていることがわかった。また，WilliamsとPeng(1991)は，ベルヌーイユニットのネットワークを用いた非結合関数最適化課題において，REINFORCEのいくつかのバリエーションを研究した。これらの研究では，勾配追従アルゴリズムに期待されるように，このようなアルゴリズムは局所最適に収束する傾向があることが示された．調査したいくつかの改良版には、この望ましくない傾向を打破するための修正が施されていました。特に興味深いのは、強化信号にエントロピー項を組み込んだもので、探索時にある程度の階層構造が望まれる課題において、特定のネットワークアーキテクチャが特に優れた性能を発揮することができる。

他にも、ベルヌーイユニットのネットワークや、単一のガウスユニットを使った予備的な研究が行われています。ガウスユニットの研究については後述する。ネットワークの研究では、監視下の学習タスクに直面している多層またはリカレントネットワークが、強化フィードバックのみを受けていました。リカレントネットワークの場合は，軌道を学習することが目的であり，エピソード的なREINFORCEを用いた．これらの研究で注目すべき点は，REINFORCEを用いて解を得るためには，強化関数を慎重に選択する必要があることです。このような問題では，明らかな強化関数を選択すると，深刻な偽最大値が発生する傾向があることがわかっているので，これは驚くべきことではない。一方，AR-pでは，このような単純な強化関数を用いても，一般に解を求めることに成功する。 AR-pと同様に，REINFORCEは成功しても一般に非常に遅い。特にエピソード型のREINFORCEは遅いと言われていますが、これも当然のことで、時間的な信用割り当てを行い、基本的に過去のすべての時間に一様に信用や非難を分散させています。 REINFORCEのアルゴリズムで漸近挙動が解析的によくわかっているものに2-action L{R-I}がありますが、他の多くのREINFORCEのアルゴリズムでこれまでに得られたシミュレーションの経験によると、これらのアルゴリズムの限界挙動の可能性の範囲は、実際には似ているかもしれません。 L{R-I}アルゴリズムは確率1で単一の決定論的行動選択に収束することが知られている。この収束で注目すべき点は、定理1から導かれるように、期待される運動が常に最良の行動の方向にあるにもかかわらず、劣った行動の選択に収束する確率が常に0ではないということである。同じような挙動を示すより単純な例として、吸収障壁を持つ整数上の偏ったランダムウォークがあります。運動が特定の方向に偏っていても、もう一方の障壁で吸収される確率は常にゼロではありません。一般に、L_{R-I}のような単純なREINFORCEアルゴリズムについて解析的に知られていることや、より洗練されたREINFORCEアルゴリズムのシミュレーションで得られた結果と一致する合理的な推測は以下の通りです。強化ベースラインの選択に応じて、このようなアルゴリズムは、多かれ少なかれ、期待される強化関数の局所的な最大値に収束する可能性が高く、ネットワークの動作のばらつきをゼロにするような他の点に収束する確率は、ゼロではない（しかし、通常は快適に小さい）。強化ベースラインの役割については、以下を参照してください。

8.2 . ガウス型ユニットの探索挙動

前述のガウス型ユニットの研究では，問題は単一の実変数yの関数を最適化する非結合型であり，適応可能なパラメータはmu とsigmaとした。式(13)，(14)から，このユニットの強化比較版REINFORCEは次のように挙動することがわかる。

過去に得られた関数値よりも高い関数値を与える値yがサンプリングされた場合，muはyに向かって移動し，同様にmuは低い関数値を与える点から離れていきます。さらに興味深いのは、sigmaがどのように適応されるかということです。サンプリングされた点yが、最近の過去に得られたものよりも高い関数値を与える場合、l y- muI < sigmaであればsigma は減少し、l y - mu I > sigmaであれば増加します。サンプリングされたポイントがより低い値になる場合は、逆の方向に対応する動作があります。探索の観点からすると、これは、より良い点が平均に適切に近いところで見つかるか、より悪い点が平均から適切に遠いところで見つかる場合には、muの周りの探索を狭くし、より悪い点が平均に適切に近いところで見つかるか、より良い点が平均から適切に遠いところで見つかる場合には、muの周りの探索を広くすることに相当します。サンプリングされた点yは、平均の1つの標準偏差内にある可能性がおよそ2倍であるため、muが（sigmaに対して十分な幅のある）局所的な丘の頂上に位置するときはいつでも、sigmaは局所的な最大値に収束できるように狭くなるということになります。しかし、局所的な最大値が非常に平坦である場合、sigmaはより悪い値のサンプリングが極端に少なくなるところまで減少し、その後変化しなくなることも事実です。この挙動は、決定論的強化とノイズ強化の両方を用いたシミュレーション研究で確認されています。また，rが常に非負であり，強化比較を用いない(b=0)場合，REINFORCEはmuがどの丘の頂上にも到達しないうちにsigmaを0に収束させてしまう可能性があることを示している．このようなユニットに対するREINFORCEを，Gullapalli (1990)が提案したmuとsigmaの適応に関する代替アルゴリズムと比較することは興味深い。この方法では，muはREINFORCEと基本的に同じ方法で適応されるが，sigmaは全く異なる方法で適応される。強化値rが0から1の間にあると仮定し，sigmaは1-rに比例すると考えます。この戦略は，sigmaが実行される探索の規模を制御するパラメータであり，関数の最適値は未知であるという観点からは理にかなっています。満足のいく性能が得られていないことがわかっている場合には、探索空間を粗視化して、最適値が見つかる可能性のある広い領域を特定するために、このスケールを広げることが合理的です。また、Schmidhuber and Huber (1990)は、ガウス型の出力ユニットを持つネットワークを用いて、モデルをバックプロパゲートする制御タスクで成功した結果を報告しています(Jordan & Rumelhart, 1990)。この研究では、モデルの学習と性能の学習を別々の段階ではなく、同時に進めるために、乱数発生器を介したバックプロパゲーションを用いた。

8.3. 強化ベースラインの選択

ここでの分析の重要な限界は、REINFORCEアルゴリズムにおける強化ベースラインの様々な選択の中から選択するための根拠を提供しないことである。定理1はどのような選択にも同じように適用されるが、このようなアルゴリズムの広範な経験的調査により、強化比較戦略のようなものを取り入れた適応的な強化ベースラインを使用すると、収束速度が大幅に向上し、場合によっては質的な動作にも大きな違いが生じるという避けられない結論が得られた。その一例として、前述のガウスユニットの研究があります。もっと単純な例としては、バイアスウェイトと入力のみを持つ単一のベルヌーイ半線形ユニットがあり、その出力yは強化度rに決定的な影響を与えます。 rが常に正であれば、b=0のときに一種の偏ったランダムウォークの挙動が得られ、劣った出力値に収束する確率がゼロではなくなることは容易に理解できる。対照的に、強化比較版では、bの値がrの2つの可能な値の間に横たわることになり、常により良い出力値に向かって運動することになります。しかし、この後者の動作は、rの2つの可能な値の間にあるbのどのような選択に対しても発生するので、適応強化ベースラインスキームの多種多様な可能性を区別するために、追加の考慮事項を適用する必要があります。

一つの可能性は、Williams (1986)によって簡単に検討され、最近ではDayan (1990)によってより詳細に検討されましたが、時間経過による個々の体重変化の分散を最小化する強化ベースラインを選ぶことです。これは、通常の強化比較法のような平均強化量ではなく、効果的に推定するのがより難しい別の量になることがわかりました。 Dayanのシミュレーション結果は、このような強化ベースラインを使用することで、平均強化を使用した場合よりも収束速度がわずかに向上することを示唆しているようですが、より説得力のある利点を示すことはまだできていません。適格性の代替形式 REINFORCEでは，強化比較の有無にかかわらず，現在と過去の強化値のみに依存する強化係数と，我々が特性適格性と呼ぶ別の係数の積に比例した重み変化を規定する。 REINFORCEのいくつかのバリエーションを得るための簡単な方法は，これらの要因のいずれかの形式を変化させることである。実際，Sutton (1984) が行ったシミュレーション研究では，これらの因子の両方を系統的に変化させることによって，さまざまなアルゴリズムが得られました。このような形をしているが、初期の研究には含まれていない、特に興味深い変形が、その後、複数の研究者によって検討され（Rich Sutton, personal communication, 1986; Phil Madsen, personal communication, 1987; Williams & Peng, 1991）、有望であることがわかった。これらの研究は、非連想的なタスクに対してのみ行われているので、ここで説明するアルゴリズムは、このような形になっています。 (さらに、このようなアルゴリズムを導き出すための原理的な根拠がまだ確立されていないため、連想の場合にどのように拡張すべきかはやや不明である）。)

ここでは特に、バイアスウェイトwのみを持つベルヌーイロジスティックユニットの場合を考えます。バイアス入力が1であることから，標準的な強化比較版REINFORCEでは，次のような形で重みの増分を規定します。

ここで、r^は指数関数的な平均化スキームに従って計算されます。

ここで、0＜gamma ＜1です。別のアルゴリズムは、次のルールで与えられます。

ここで、y^は次のように更新されます。

このアルゴリズムは，一般に，対応するREINFORCEアルゴリズムよりも高速かつ確実に収束することがわかっています．この2つのアルゴリズムには強い類似性があることは明らかです。さらに，対応する戦略は，他の多くの場合にREINFORCEの変種を生成するために使用することができます．例えば，ユニット内のランダム性が命題1が適用される任意の分布を用いている場合，その平均パラメータmuを調整するためのREINFORCEアルゴリズムにはy - muという係数が含まれており，これをy - y^に置き換えるだけでよい。このようなガウス単位の平均値を調整するアルゴリズムはテストされ，非常によく動作することがわかっています。このようなアルゴリズムでy - y^を使用することの潜在的な利点を示唆するいくつかの議論（Rich Sutton, personal communication, 1988）が与えられるが、より完全な分析はまだ行われていない。興味深いことに、このようなアルゴリズムの使用を正当化する分析的な理由の1つは、次に述べるような考察にあるかもしれません。

8.5. 他の局所勾配推定値の使用

REINFORCEのアルゴリズムをシンプルと呼ぶことには、本稿のタイトルにもあるように、いくつかの意味がある。まず，ここで挙げた例からも明らかなように，アルゴリズム自体が非常に単純な形をしていることが多い．また、基本的にどのような形式の乱数単位の計算に対しても簡単に導出することができます。しかし、おそらく最も重要なことは、定理1と2で与えられた意味において、このアルゴリズムが適切な勾配を登り、その勾配の推定値を明示的に計算することなく、また、そのような推定値を直接計算できるような情報を保存することもない、という事実です。明らかに、このような勾配を推定する別の方法があり、そのような様々な技術をどのように効果的に統合できるかを理解することは有益である。様々な代替アプローチを区別するために、まずいくつかの用語を定義します。 Barto, Sutton, Watkins (1990)は、適応制御分野における間接的なアルゴリズムを表現するために、モデルベースという用語を導入しました(Goodwin & Sin, 1984)。これらのアルゴリズムは、制御対象となるシステムの基礎となる関連パラメータを明示的に推定し、このシステムの学習されたモデルを用いて制御動作を計算します。即時強化学習システムに対応する概念は、学習システムの入力と出力の関数として強化の明示的なモデルを学習し、このモデルを使用してパラメータ調整を行おうとするものである。 REINFORCEのように、期待される強化の勾配に沿ってパラメータ調整を行う場合、このモデルは実際にこの勾配の推定値を得る必要があります。このようなアルゴリズムとして，モデルを介したバックプロパゲーションを用いる方法が，Munro (1987)によって提案され，研究されている。このようなモデルベースのアプローチは、強化関数とその導関数のグローバルモデルを用いるが、よりローカルなモデルベースのアプローチも可能である。これは、各ユニットにおいて、そのユニットの入力と出力の関数として強化の期待値を推定すること、または、REINFORCEのような勾配アルゴリズムが必要な場合は、この期待強化の導関数を推定することを含む。

Thathatchar and Sastry (1985) が研究している確率的学習オートマトンのアルゴリズムは，各アクションで受け取る平均強化量を記録しており，このような一般的な形式になっています．また，Q-learning (Watkins, 1989) は，累積強化の局所的な (この場合は状態ごとの) モデルの学習を含むものとみなすことができる． REINFORCEはこのような局所的な意味でのモデルベースではありませんが、より明示的な勾配推定値を生成しようとするアルゴリズムを検討することは、それを使用することで明確に識別できる強みを持つアルゴリズムにつながるのであれば、価値があるかもしれません。少なくとも非結合型の場合には、各ユニットで強化信号をユニットの出力に線形回帰するという興味深い可能性があります。上述のy - y^形式の適格性を用いたアルゴリズムは、このようなアプローチに関連しているのではないかと考えられますが、まだ十分に分析されていません。

9. 結論

ここで紹介した分析と，筆者らが行った様々なシミュレーション実験から，REINFORCE アルゴリズムはそれ自体が有用であり，さらに重要なことには，他のより効果的な強化学習アルゴリズムを開発するための健全な基盤となり得ることが示唆された。 REINFORCEアプローチの大きな利点は，ランダムな出力を任意の方法で計算するユニットの強化学習ネットワークに対して，統計的な勾配追従アルゴリズムを考案するための処方箋を示していることです。また、勾配ベースのアプローチであるため、バックプロパゲーションのような他の勾配計算技術との統合性にも優れています。主な欠点は、このクラスのアルゴリズムに適用できる一般的な収束理論がないことと、他の勾配アルゴリズムと同様に、偽最適値に収束しやすいことである。

e4exp / paper_manager_abstract