相互依存関係による学習ヒューリスティクスの自動修正 東京工業大学 情報理工学研究科 計算工学専攻 沼尾 正行 森山 甲一 [email protected] [email protected] MACC’99 1999 年 11 月 30 日∼12 月 1 日 Abstract We consider a method that dynamically adapts the heuristics employed in a learning process according to the changes in the environment. In our method, the evaluation of the heuristics, necessary for adaptation, is done by the low-level part that is influenced by the heuristics. We apply the method to a problem of obtaining cooperation of multi-agents in a reinforcement learning context. 1 はじめに エージェント 学習ヒューリ スティクス 自律的な学習システムを構築するためには、その学 学習部 * 駆動部 知覚部 行動 評価 習行動におけるヒューリスティクスを環境の変化に応 じて動的に適応させなくてはならない。そのためには 図 1 そのヒューリスティクスを評価しなくてはならないが、 その方法が問題となる。通常の行動やその指針である エージェント クスと学習部が相互に依存し影響し合う関係でなくて ヒューリスティクスの評価はいわゆる報酬の形で与え はならない (図 1 ∗ 印)。 られる。しかし学習行動の場合は、そのヒューリスティ 本研究では、学習部が学習ヒューリスティクスの評 クスの評価を行なう上位のメカニズムの存在を仮定し 価を与えることでこの関係を実現することにする。以 てしまうと評価の無限後退に陥る危険が生じ、また評 下ではその具体的問題として、強化学習によるマルチ 価を人間が与えてしまうと本当の意味での自律性が失 エージェントの協調獲得を扱う。 われる。 そこで本研究では学習行動のヒューリスティクスを、 3 その影響を受ける学習メカニズムが評価することによっ 強化学習による協調獲得 3.1 て動的に適応させることを目的とする。そして具体的 報酬のフィルタリング に強化学習によるマルチエージェントの協調獲得問題 マルチエージェントの協調獲得問題は、協力的問 について実験を行ない、結果を示す。 題 (Co-operative Problem) とデッドロック回避問題 2 (Deadlock Avoidance Problem) の 2 つに分けられ 相互依存関係 る [3, 4]。協力的問題は全エージェント共通の評価関 数を最大化するもので、これが最大になる時に各エー 外部環境に対して行動し、その結果として評価を受 けるエージェントを仮定する。このエージェントの内 ジェントの獲得報酬も最大になるというものである。 部を 図 1 のように各部分に分けて考える。この図で 一方デッドロック回避問題は、複数のエージェントの 実線矢印は制御、点線矢印はデータの流れを表してい 獲得報酬が同時に最大になることはない状況の時、各 る。この時学習ヒューリスティクスと学習部が支配従 エージェントが一斉に報酬を追求するとデッドロック 属の関係にあるならば、このヒューリスティクスを評 に陥ってしまうため、それを回避する問題である。 価するために更に上位のメカニズムが必要となる。こ これらを強化学習の手法で解決するために、予めフィ のことから、無限後退を防ぐには学習ヒューリスティ ルタリングした報酬を用いて強化学習を行なおうとす 1 相互依存関係による学習ヒューリスティクスの自動修正 MACC’99 1999 年 11 月 30 日∼12 月 1 日 2 る手法が提案された [4, 5]。これは近隣エージェントの これは前節のフィルタを動的にしたものであり、α, β 平均報酬を用いて以下の式で表されるフィルタ [4] を を変化させることで平均フィルタ・強調フィルタを含 構成し、獲得報酬をフィルタリングするものである。 む様々なフィルタとして働くことができる (表 1)。本 これらの式で r はエージェントの獲得報酬、r は強化 研究ではこの α, β の変化を強化学習を用いて学習する 学習に用いられる報酬、E は近隣エージェントの平均 ことでフィルタの動的適応を実現することとし、この 1 報酬、p (> 0) はパラメータを表す 。 • 平均フィルタ 1 (平均以下を底上げ) r = r E if r > E otherwise 学習に必要な報酬を相互依存の観点から学習部が与え ることにする (図 1 ∗ 印に相当)。なお、以下では α, β のことをまとめて汎用フィルタパラメータまたは単に パラメータ、それらの学習を行なう部分をパラメータ 学習部と称する。 • 平均フィルタ 2 (平均以上をカット) r = 表 1 r if r < E α β 対応フィルタ E otherwise 0 1 1 0 平均フィルタ 1 1 p+1 1 1 フィルタなし 強調フィルタ 1 1 p+1 強調フィルタ 2 • 強調フィルタ 1 (平均以下を強調) r = α, β と各フィルタの関係 r − p(E − r) if r < E r otherwise 平均フィルタ 2 • 強調フィルタ 2 (平均以上を強調) r − p(E − r) r r = if r > E otherwise 4 実験 ここでは協力的問題の例として文献 [4] と同様にゲー 平均フィルタ (Average Filter) が協力的問題に、強 ム理論の分野で有名な「共有地の悲劇」[2, 6] タイプの 調フィルタ (Enhancement Filter) がデッドロック回避 ゲームと、デッドロック回避問題の例としてオリジナ 問題に有効であることが文献 [4] に示されている。従っ ルの「狭路問題」により実験を行なった。強化学習手 て、これらのフィルタは協調獲得学習における一種の 法としては Q-learning [8] を用い、学習率・割引率は ヒューリスティクスであると考えることができる。 共に 0.5 とした。 3.2 以下の実験においてループ 1 回とは、表 2 の動作を 汎用フィルタ 全エージェントが 1 回ずつ行なうことを表している。 前節のフィルタはそれぞれ固定的であるため、動的 な環境においては逆効果をもたらす可能性がある。更 に問題のタイプによって異なるフィルタを用いる必要 があるため、人が予め問題を見極めなくてはならない。 なお必要に応じて、動作間でエージェント間の同期を 取ることにする。 表 2 各エージェントの動作 これらの問題を解決するためにはフィルタの動的適応 1. 行動提示 性が要求される。そこで本研究では、まず以下の式で 2. 報酬 r 獲得 3. パラメータ (α, β) 調整 ∗ 表される汎用フィルタ (General Filter) を提案する。こ の式で α, β はパラメータを表し、その他の記号は上と 同じものである。 r = 1 強調フィルタ な拡張である。 E + α(r − E) if r < E E + β(r − E) otherwise 2 は文献 [4] にはないが、強調フィルタ 1 の自然 4. 報酬のフィルタリング (r 計算) 5. 学習部による学習 6. パラメータ学習部による学習 ∗ (∗ : 汎用フィルタの場合のみ) 相互依存関係による学習ヒューリスティクスの自動修正 4.1 1999 年 11 月 30 日∼12 月 1 日 MACC’99 「共有地の悲劇」タイプゲーム 表 5 「共有地の悲劇」実験設定 「共有地の悲劇」タイプゲームは、全てのエージェ ントが一斉に行動を提示し、その行動により共通コス ト rc を算出、各エージェントは自分の行動に対する報 酬から共通コストを差し引いた報酬 r を獲得するとい エージェント数 10 近隣エージェント 図 2 のように定義・固定 局所平均 E フィルタ後報酬 r の平均 う流れで行なわれた2 。まとめると以下のようになる。 1. 全エージェントが行動を (同時に) 提示 2. 共通コスト rc を計算 (初期値 0) 3. 各エージェントの報酬 r 計算・獲得 表 6 「共有地の悲劇」学習部設定 行動 利他的・協力的・利己的 状態 近隣エージェントの行動組合せ 報酬 表 3 で定義 行動選択 4. 1. へ 確率的 各エージェントの行動による共通コスト rc の増減 と獲得報酬 r は 表 3 で与えられた [4]。例えば 3 台の 表 7 エージェント環境において行動がそれぞれ利己的・利 パラメータ学習部設定 他的・利己的である場合には、この表から共通コスト 初期値 rc が (+1) + (−1) + (+1) = 1 と求められるため、各 行動 (α, β) = (1, 1) パラメータ値の増加・維持・減少 エージェントの獲得報酬は 表 4 のようになる。 状態 パラメータ値の変化行動 報酬 フィルタ後報酬の符号反転 −r 表 3 行動による rc の変化と獲得報酬 r r) (10 回の獲得報酬の和 確率的 行動 rc の変化 獲得報酬 r 行動選択 利己的 +1 3 − rc 行動頻度 協力的 ±0 −1 1 − rc −3 − rc 1 回/ループ 1 回 ( 1 回/ループ 10 回) 行動範囲 0 ≤ α, β ≤ 2 0 ∼ 0.1 のランダム幅 利他的 行動幅 ( 0 ∼ 1 のランダム幅 ) 表 4 (カッコ内は従属的評価の場合) 行動と獲得報酬の例 ID 0 1 2 行動 利己的 利他的 利己的 獲得報酬 2 −4 2 4 5 3 実験の細かな設定は 表 5 ∼ 7 の通りである。ここ 6 2 7 で 表 7 の「行動」「状態」「行動幅」は α, β それぞれ について決定される。また同表の「報酬」に現れる符 1 号反転操作は、学習部がフィルタ後報酬 r (学習部に 8 0 与えられた報酬) を符号反転することでそれに制御的 9 意味合いを持たせ、パラメータ学習部に与えていると 考えることができる。従って、これらのフィルタパラ メータは相互依存的に評価されていると解釈できる。 図 2 エージェント 0, 1 の近隣エージェント [4] 3 相互依存関係による学習ヒューリスティクスの自動修正 MACC’99 1999 年 11 月 30 日∼12 月 1 日 4 20 10 Sum of Rewards 0 -10 No Filter -20 Average 1 -30 Average 2 -40 Enhancement 1 (p=1) Enhancement 2 (p=1) -50 General (Interdependent) -60 General (Subordinate) -70 0 500 1000 1500 Loop Times 図 3 2000 2500 3000 「共有地の悲劇」ゲームの結果 なお、比較のため汎用フィルタパラメータの変化を 表 8 行動提示回数と獲得報酬の関係 単に長期的に得られる報酬によって学習する、従属的 評価3 を用いた実験も行なった。表 7 のカッコ内はこ の場合の設定である。 実験結果を 図 3 に示す。このグラフは 15 回の実 験結果の平均をベジエ曲線で近似したもので、横軸が 進む : r =1− 1 (c − 1) 2 待つ : r =1− 1 c 2 ループ回数、縦軸が全エージェントの報酬合計を表し ている。相互依存的 (interdependent) 評価の場合、始 めはフィルタなしと同様に報酬合計が減少して行くが、 途中で下げ止まって増加に転じているのが分かる。一 方、従属的 (subordinate) 評価の場合はフィルタなし と同様に報酬合計が減少し続けることが分かる。 4.2 の狭い道を 2 台の車がいかに早く通過できるかとい う問題である (図 4)。すなわち一種の哲学者の食事問 題 [7, 2.3.1 節] であるが、この問題には時間的な条件 が付いていることに注意を要する。 2 台の車は同時に「進む」と「待つ」のどちらかを 提示する。両者の行動が異なれば 表 8 にある報酬を 「狭路問題」 これは、車のすれ違うことが不可能な狭い道があり、 その両側に 2 台の車が同時に現れたと仮定する時、こ 獲得する。この表で c は行動提示回数、r は獲得報酬 を表している。「待つ」を提示した車は相手の車の通 過を待ってから通過するので、「進む」を提示した車 に比べて行動提示 1 回分だけ獲得報酬が少なくなって いる。両者の行動が同じならば両者とも再び行動を提 示する。これは両者が同時に「進む」を選択すると、 すれ違うことが不可能なので結局通過できず、同時に 図 4 2 文献 「狭路問題」 [4] はゲームの流れについてあまり詳しく書かれていない ために、これとは異なっているかもしれない。 3 報酬を計算する期間に支配されているため。 「待つ」を提示しても状況は進展しないからである。 実験の細かな設定は 表 9, 10 の通りである。なお パラメータ学習部については「共有地の悲劇」ゲーム と同じである (表 7)。また、同様に比較のために従属 相互依存関係による学習ヒューリスティクスの自動修正 表 9 「狭路問題」実験設定 MACC’99 1999 年 11 月 30 日∼12 月 1 日 5 結果である。そのためフィルタ後報酬 r はパラメータ 変化後のフィルタによるものながら、以前のパラメー エージェント数 ペア生成 10 ( 2 台 × 5 ペア) タの影響を強く受けていると思われる。 この時にフィルタ後報酬 r が負であったとすると、 ループごとにランダム生成 近隣エージェント 図 2 のように定義・固定 それは以前のパラメータが良くないということを表し 局所平均 E フィルタ後報酬 r の平均 ていると考えられる。従ってこの場合はパラメータを 10 変化させるべきであるため、パラメータ学習部へ正の 最大行動提示回数 報酬を与えるのが好ましいと思われる。同様にフィル タ後報酬 r が正であるならば、パラメータの変化はあ 的評価を用いた実験も行なった。 表 10 「狭路問題」学習部設定 まり好ましくないとも考えられる。そのためパラメー タ学習部へ負の報酬を与えることにより、パラメータ の変化を抑制しているのではないだろうか。 行動 進む・待つ 状態 相手 ID と両者の行動組合せ べた考察ではパラメータを変化させるか否か、フィル 報酬 表 8 で定義 タ後報酬 r が正か負かについてしか考えていない。ま 行動選択 確率的 しかしこの考察にもまだ問題点がある。今までに述 た 表 7 によるとパラメータの変化行動には増加・維 持・減少の 3 つがあるが、変化行動が「維持」の場合 実験結果を 図 5 に示す。これは「共有地の悲劇」 は上と逆の現象が起こるであろう。この場合の説明は 今後の課題でもある。 ゲームと同様に 15 回の実験の平均値をベジエ曲線で 近似したものであり、横軸がループ回数、縦軸が全エー ジェントの獲得報酬合計を表している。この問題の場 合はどちらの評価法も結果に大差はなく、フィルタな しと同等の結果となっていることが分かる。 6 まとめと課題 本研究では学習部に作用するヒューリスティクスに ついて、学習部が評価することにより無限後退を避け て動的適応を実現することを目的とした。そして具体 5 考察 的な問題として強化学習によるマルチエージェントの 協調獲得を扱った。協調獲得の一手法として報酬をフィ 本研究では 2 つの実験の結果、それぞれで汎用フィ ルタリングする手法を紹介し、そこで用いられるフィ ルタが類似するフィルタが異なるという意味で、ある ルタをまとめた汎用フィルタを提案した。このフィル 程度のフィルタ (学習ヒューリスティクス) の汎用化が タを一種の学習ヒューリスティクスと考え、そのパラ 実現されたものと考えられる。 メータ変化に要する評価を学習部が与えるという解釈 更に「共有地の悲劇」タイプゲームでは、学習部が フィルタ後報酬 r を符号反転してパラメータ学習部に によって相互依存関係による学習ヒューリスティクス の自動修正の実験を行ない、「共有地の悲劇」タイプ 与えるという方法による相互依存的評価が、予め決め ゲームでは一定の成果を獲得した。結果として、この られた期間に得られた報酬合計をパラメータ学習部に 手法による学習ヒューリスティクス評価の実現例を示 与えるという従属的評価に比べて良好な結果を得た。 すことができたのではないかと思う。 以下では、なぜ符号反転すると良い結果を得られるこ 今後の課題をいくつか挙げる。 とがあるのかについて考察する。 まず、汎用フィルタパラメータの変化とエージェン トの行動の間に時間差があることを考慮しなくてはな らない。汎用フィルタパラメータは学習部に作用する ものであるため、その行動への影響は時間がしばらく 経った後に出て来るものと思われる。また、報酬を獲得 する元となる行動は変化前のパラメータによる学習の • 本研究のパラメータ評価法が有効な問題範囲の限 定とその数学的解析 前節の考察をより深め、更にパラメータの収束条 件や行動範囲による影響などを数学的に解析する。 • 人手によるパラメータ評価法の改良 相互依存関係による学習ヒューリスティクスの自動修正 MACC’99 1999 年 11 月 30 日∼12 月 1 日 6 8 7 Sum of Rewards 6 No Filter 5 Average 1 4 Average 2 3 Enhancement 1 (p=1) Enhancement 2 (p=1) 2 General (Interdependent) 1 General (Subordinate) 0 0 500 1000 1500 Loop Times 図 5 2000 2500 3000 「狭路問題」実験結果 例えば「狭路問題」においても、少なくとも4 強調 フィルタと同等の働きを持つように、パラメータ を導く評価式を発見する。 • 解釈によらない相互依存関係の実現 学習部にパラメータ評価法自体を獲得させること により、パラメータ評価として符号反転した報酬 を与えるという一種のヒューリスティクスを排除 し、解釈によらない相互依存関係を実現する。 • 社会的視点からのフィルタの妥当性の検証 [3] 三上 貞芳. 強化学習のマルチエージェント系への応用. 人 工知能学会誌, Vol. 12, No. 6, pp. 845–849, November 1997. [4] Sadayoshi Mikami and Yukinori Kakazu. Cooperation of Multiple Agents Through Filtering Payoff. In 1st European Workshop for Reinforcement Learning, 1994. [5] Sadayoshi Mikami, Yukinori Kakazu, and Terence C. Fogarty. Co-operative Reinforcement Learning By Payoff Filters. In Proc. 8th European Conference on Machine Learning, ECML-95, (Lecture Notes in Artificial Intelligence 912), pp. 319–322, Heraclion, Crete, Greece, 1995. 本研究で用いたフィルタに類似したものの存在を [6] 岡田 章. ゲーム理論. 東京: 有斐閣, 1996. 現実社会に認めることが可能ならば、マルチエー [7] Andrew S. Tanenbaum. Operating Systems: Design and Implementation. Englewood Cliffs, NJ: PrenticeHall, 1987. （坂本 文 監修, 大西 照代 訳. MINIX オペ レーティング・システム. 東京: アスキー, 1989）. ジェントによる社会システムモデルの研究 [1] に 応用できる。 その他にも課題はあるだろうが、解釈によらない相 互依存関係の実現を主目的として研究を進めて行きた いと考えている。 References [1] 出口 弘. 規範と制度化の階層的意志決定モデル. 第 8 回マルチ・エージェントと協調計算ワークショップ (MACC’99), 1999. [2] Garrett Hardin. The Tragedy of the Commons. Science, Vol. 162, pp. 1243–1248, 1968. 4 強調フィルタが正解とは限らないため。 [8] Christopher J. C. H. Watkins and Peter Dayan. Technical Note: Q-learning. Machine Learning, Vol. 8, pp. 279–292, 1992.
© Copyright 2024 ExpyDoc
![防災士パンフレット[PDF 188KB]](http://s1.expydoc.com/store/data/005926544_1-bd0b3429d73dc654f8f86c9a70b1cf51-250x500.png)
