先端論文紹介ゼミ Role-based Context-specific Multiagent Q-learning

目次 Abstract Introduction Collaborative multiagent MDPs and　einforcement learning Role-based context-specific Q-learning Experiments Conclusion 2011/1/21 先端論文紹介ゼミ

Abstract マルチエージェント強化学習における主な問題はエージェント数に従い行動状態空間サイズが指数関数的に増大すること。 本稿では行動空間の増加を軽減するために「roles and context - specific coordination graphs」を利用する。 全体結合Q関数を部分的Q関数に分解する。 部分的Q関数は小グループのエージェントで構成され価値ルールの組で構成される。 自動的に各価値ルールの重みを学習するマルチエージェントQ学習アルゴリズムを提案する。 2011/1/21 先端論文紹介ゼミ

Role-based Context-specific Multiagent Q-learning Introduction マルチエージェントシステムとは複数のエージェントとの相互作用で共存するエージェント群。 マルチエージェントシステムの研究ではエージェントの行動管理の問題に焦点を当てている。 本稿では全てのエージェントが共通の目標をもつ完全集中型マルチエージェントシステムに焦点を当てる。 エージェントの個々の行動を確認するプロセスはグループ全体の最適政策を学習する。 2011/1/21 先端論文紹介ゼミ

Introduction マルチエージェントシステムを単一の「大きな」エージェントとして扱い、最適政策を学習させる方法。 　マルチエージェントシステムを単一の「大きな」エージェントとして扱い、最適政策を学習させる方法。 　行動空間が指数関数的に増加するため詳細な設計が難しい 各エージェントが独立した自身の政策を学習する方法。 各エージェントが他のエージェントの情報なしに学習を行う。 　収束が学習エージェントの政策に依存するため、安定しない。 2011/1/21 先端論文紹介ゼミ

Introduction 行動空間のサイズを軽減するために最近の研究は“context-specific coordination graph (CG)”を使用する。 CGの考え方： 　エージェントが個々に行動できる中で少数のエージェントの行動の調整を行う。 例）ロボットサッカーにおいて他のロボットが自己の独立した行動をするなかで、ボールの保持者やその周りのプレイヤーの行動を調整する必要がある。 2011/1/21 先端論文紹介ゼミ

Introduction 本論文ではCGに基づいたマルチエージェントQ学習を提案する。 オフライン設計段階では役割に対する価値ルールを定義する。 オンライン割り当て段階では、役割割当アルゴリズムを用いて、エージェントに役割を割当て、エージェントが役割に対応した価値ルールを得る。 提案手法ではCGの重みを学習する。 CGの重みはQ学習から派生した更新式を利用する。 2011/1/21 先端論文紹介ゼミ

Collaborative multiagent MDPs (CMMDP)and reinforcement learning CMMDPは5つの要素＜n,S,A,R,T>より成り立つ。 （n:エージェント数、 　S:有限状態空間、 　A：行動空間、 　R：報酬、 　T：状態sのエージェントが行動aを選択し状態s’に遷移した場合に取る行動の確率） Q学習は以下の式を用いて更新される。 γは報酬割引率、αは学習率とする。 2011/1/21 先端論文紹介ゼミ

Collaborative multiagent MDPs (CMMDP)and reinforcement learning Joint action learners　（JAL) 　　この手法はマルチエージェントシステム（MASの）を単一の「大きな」エージェントとして扱う。 　エージェントの状態-行動の組は結合状態空間と元のMASの結合行動空間である。 　　「大きな」エージェントの学習にはQ学習を用いる。 　　 欠点： 　　学習エージェントの状態と行動の組がエージェント数に従い指数関数的に増加する。 2011/1/21 先端論文紹介ゼミ

Collaborative multiagent MDPs (CMMDP)and reinforcement learning Independent learners　（IL) 　　この手法はエージェントが他のエージェントの情報なしに独立した学習を行う。 　　 指数関数的な結合行動空間を考慮する必要はない。 　　 欠点： 　　他のエージェントの政策に依存するため、学習の収束が安定しない。 2011/1/21 先端論文紹介ゼミ

Role-based context-specific Q-learning Context-specific coordination graphs and roles 　協調の依存関係はCGを用いて表すことができる。 　価値ルールはエージェントが協調行動を実行する文脈を定義する。 　協調の依存関係をG=(V,E)で定義する。 　全体結合Q関数を部分的Q関数の和で近似される。 2011/1/21 先端論文紹介ゼミ

Role-based context-specific Q-learning Context-specific coordination graphs and roles 　定義2： 　　価値ルール 　　　　　　　　　　　は現在の状態がsであり、統一行動aを行った時、　　　　　　　となる。それ以外は０とする。 　定義3： ここで 2011/1/21 先端論文紹介ゼミ

Role-based context-specific Q-learning Context-specific coordination graphs and roles 　定義4： 　「役割」の要素は　　　　　　　　　　とする。 （m：役割の数、 　　 ：役割mに関連付けられておる価値ルールの組、 　 ：はエージェントiが現在の状態で役割mが適当であるかのポテンシャル関数） 　「役割」を2つの段階を用いてCGに内蔵する。 ・オフライン設計段階 ・オンライン割当段階 2011/1/21 先端論文紹介ゼミ

Role-based context-specific Q-learning Context-specific coordination graphs and roles 　オフライン設計段階 　　エージェントに対する価値ルールの定義の代わりに役割に対する価値ルールを定義する。 　　エージェントに役割を割り当てる役割割当アルゴリズムを使用する。 　　 エージェントは割り当てられた役割から価値ルールを得る。 2011/1/21 先端論文紹介ゼミ

Role-based context-specific Q-learning Context-specific coordination graphs and roles 役割割当アルゴリズム 　|M|>nのとき配列Mを定義する。（M：役割の数、n：エージェント数） 　役割の重要度により順序付けされる。 　同じ役割は複数のエージェントに割り当てることができる。 　エージェントが複数の役割をもつことはできない。 　エージェントiと役割mからポテンシャル を算出する。 2011/1/21 先端論文紹介ゼミ

Role-based context-specific Q-learning Q-learning in context-specific coordination graphs 定義5： はエージェントiに対する部分的Q値 　　　　　　　はエージェントiを含む価値ルール。 njはエージェントiを含むそのルールに関係するエージェントの数。 2011/1/21 先端論文紹介ゼミ

Role-based context-specific Q-learning Q-learning in context-specific coordination graphs 定理１：価値ルール　　　　　 は以下の式で更新する。 　 　njはρjに関するエージェントの数。 　　niは状態ｓで統一行動aが一致しているインスタンスの価値ルールのエージェントiの出現回数。 2011/1/21 先端論文紹介ゼミ

Role-based context-specific Q-learning Q-learning in context-specific coordination graphs 学習アルゴリズム 2011/1/21 先端論文紹介ゼミ

Experiments 提案手法RQをJAL、ILと比較する。 問題設定は追跡問題を適用する。 10*10のグリッド平面に２体のハンターと１体の獲物を配置 ハンターと獲物の行動は上下左右静止の５行動。 獲物はランダム行動を行う。 捕獲条件は獲物と同セルおよび 隣接セルに両ハンターが移動。 2011/1/21 先端論文紹介ゼミ

Experiments RQアルゴリズムにおいて役割を二つ用意する。 　　capture：獲物を捕獲するように行動する。 Supporter:捕獲者のサポートをする行動を取る。 役割割当の配列 は となる。 captureの役割のポテンシャルはハンターと獲物のマンハッタン距離に基づく。 Where is the distance between predator i and the prey　　　　　 2011/1/21 先端論文紹介ゼミ

Experiments 各ハンターが得る報酬は以下に示す。　　　 2011/1/21 先端論文紹介ゼミ

Experiments 実行結果 手法 平均捕獲ステップ RQ 12.92 JAL 12.78 IL 17.02 2011/1/21 実行結果　 手法 平均捕獲ステップ RQ 12.92 JAL 12.78 IL 17.02 2011/1/21 先端論文紹介ゼミ

Conclusion role-based context-specific multiagent Q-learning手法を提案。 Role and context-specific coordinarion graphsを使用。 自動的に各価値ルールの重みを学習するQ学習アルゴリズムを提案。 実験は従来のマルチエージェント強化学習より大幅に速い学習速度で同じ政策に収束することを示した。 2011/1/21 先端論文紹介ゼミ

ご清聴ありがとうございました。 2011/1/21 先端論文紹介ゼミ

Role-based context-specific Q-learning 補足1 例）状態ｓと状態s0が以下の規則をもつ。 　　エージェントは状態ｓに協調行動a＝{a1,a2,a3}を行い、状態はs’に遷移する。状態s’での最適行動は　　　　　　　　　　　　である。 　　従って状態sにおいてルールρ1、ρ2、ρ4が表れ、状態s’においてルールρ5とρ7が表れる。 2011/1/21 先端論文紹介ゼミ

Role-based context-specific Q-learning 補足1 次のようにρ1、ρ2、ρ4を更新する。 2011/1/21 先端論文紹介ゼミ

Experiments 補足2:生成される価値ルールの一例 価値ルールρ1は捕獲者の役割が他の支援者となるハンターの支援がなくても獲物をほかうしようとするべきと示す。 　　ルールρ2は捕獲者が獲物の位置に動き、支援者が現在の位置で静止する連携文脈である。 2011/1/21 先端論文紹介ゼミ