Comments
Description
Transcript
修士論文 他エージェントの行動予測を利用したマルチエージェ ント強化
NAIST-IS-MT0151011
修士論文
他エージェント の行動予測を利用したマルチエージェ
ント 強化学習のゴール毎の状態空間分割による高速化
稲垣 浩司
2002 年 2 月 8 日
奈良先端科学技術大学院大学
情報科学研究科 情報処理学専攻
本論文は奈良先端科学技術大学院大学情報科学研究科に
修士 (工学) 授与の要件として提出した修士論文である。
稲垣 浩司
審査委員：
伊藤 実 教授
石井 信 教授
杉本 謙二 教授
他エージェント の行動予測を利用したマルチエージェ
ント 強化学習のゴール毎の状態空間分割による高速化3
稲垣 浩司
内容梗概
マルチエージェント系における適応行動の実現は，工学及び認知科学の観点か
ら興味深い課題である．その中でも，学習による適応行動の自律的獲得に関する
研究が，強化学習の発展を契機として近年注目を集めている．
マルチエージェント系において，個々のエージェントが実行する行動の善し悪
しは，他エージェントが実行する行動に依存する．この点に注目した先行研究と
して，他エージェントの行動を推定しながら学習を進行するマルチエージェント
強化学習法が提案されている．しかしながら，この学習法は，状態空間が広いな
ど 学習に時間を費やす問題に対して，他エージェントの行動推定の誤差が大きく
なるという問題点が生じる．本論文では，他エージェントの実行する行動を予測
しながら学習を進行するマルチエージェント強化学習法に，状態空間を複数に分
割して学習を高速化する手法を導入した．
本手法を追跡問題に適用し，評価実験を行った結果，本手法により他エージェ
ントの行動の推定がより正確に行えることを確認した．
キーワード
マルチエージェント系, 強化学習, Q 学習, 状態空間, 追跡問題
3 奈良先端科学技術大学院大学 情報科学研究科 情報処理学専攻 修士論文,
MT0151011, 2002
年
2
月
8
日.
i
NAIST-IS-
An acceleration method for multi-agent
reinforcement learning with the estimation of
the other agent's action by decomposing the
3
state space
Koji Inagaki
Abstract
The realization of cooperative behaviors in multi-agent systems is an interesting
topic from the viewpoint of engineering and cognitive science. In particular,
studies on autonomic acquisition of cooperative behaviors from learning attract
recent attention since the development of reinforcement learning.
In multi-agent systems, whether one agent's action is good or not depends
on the other agent's action. A multi-agent reinfocement learning method with
the estimation of the other agent's action was proposed. In this paper, the idea
of decomposing the state space is introduced to the multi-agent reinforcement
learning method in order to accelerate the learning.
I applied the introduced method to pursuit problem and evaluated the method.
From the experiments, I conrmed that the method improves estimation of the
other agent's action.
Keywords:
multi-agent system, reinforcement learning, Q-learning, state space, pursuit problem
3 Master's
Thesis, Department of Information Processing, Graduate School of Information
Science, Nara Institute of Science and Technology, NAIST-IS-MT0151011,
ii
February 8, 2002.
目次
1.
はじめに
1
2.
強化学習（シングルエージェント ）
3
2.1 強化学習の概要 : : : : : : : : : : : : : : : : : : : : : : : : : : : :
3
2.2 マルコフ決定過程 : : : : : : : : : : : : : : : : : : : : : : : : : : :
3
2.3 Q 学習 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
4
2.4 状態空間分割を用いた Q 学習 : : : : : : : : : : : : : : : : : : : :
5
マルチエージェント 強化学習
7
3.1 マルチエージェント強化学習の概要 : : : : : : : : : : : : : : : : :
7
3.2 他エージェントの行動予測を利用した強化学習 : : : : : : : : : : :
7
3.3 他エージェントの行動予測を利用した強化学習の高速化 : : : : : :
9
3.
4.
5.
実験
12
4.1 追跡問題 : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :
12
4.2 実験結果及び考察 : : : : : : : : : : : : : : : : : : : : : : : : : : :
15
結論
20
謝辞
21
参考文献
22
iii
図目次
7
:: : : : :: : : : :: : : :
状態空間分割を用いた Q 学習 : : : : : : :
状態と部分状態 : : : : : : : : : : : : : : :
追跡問題のグリッド 空間（ 獲物が 2 体） :
捕獲状態の例（ 獲物が 2 体） : : : : : : :
追跡問題のグリッド 空間（ 獲物が 3 体） :
捕獲状態の例（ 獲物が 3 体） : : : : : : :
8
獲物捕獲までに費やした平均時間ステップ数（ 獲物が 2 体の追跡
1
2
3
4
5
6
強化学習の枠組
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
3
6
10
12
13
14
14
9
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 15
行動確率予測の二乗平均誤差（ 獲物が 2 体の追跡問題） : : : : : : 16
10
獲物捕獲までに費やした平均時間ステップ数（ 獲物が 3 体の追跡
問題）
: : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 17
行動確率予測の二乗平均誤差（ 獲物が 3 体の追跡問題） : : : : : : 18
問題）
11
iv
1.
はじめに
マルチエージェント系における適応行動の実現は，工学及び認知科学の観点か
ら興味深い課題である．その中でも，学習による適応行動の自律的獲得に関する
研究が，強化学習 [1] の発展を契機として近年注目を集めている．
マルチエージェント系において，個々のエージェントが実行する行動の善し悪
しは，他エージェントが実行する行動に依存する．この点に注目した先行研究と
して，他エージェントの実行する行動を予測しながら学習を進行する強化学習法
が提案されている [2]．この強化学習法では，他エージェントが実際に実行した
行動を観測し，その観測情報を基に他エージェントの政策（行動決定関数）を推
定する．そして，推定した他エージェントの政策を基に他エージェントの未来行
動を予測し，その予測行動を考慮に入れながら学習を進行する．ここで，他エー
ジェントの政策推定は，他エージェントが実際に実行した行動は将来にも実行す
る可能性が高いであろうという仮定に基づいて行われている．ところで，この強
化学習法は，エージェントが適当な政策を獲得するまでに多くの時間を費やす課
題（タスク）にはあまり適していないと考えられる．他エージェントが実行する
行動には，その他エージェントにとって有効な行動と，そうでない行動（学習の
進行により，将来実行しなくなる行動）があるが，他エージェントが適当な政策
を獲得していない段階では，後者の行動，すなわち，有効でない行動を実行する
確率が比較的高くなる．しかし，この強化学習法における他エージェントの政策
推定は，他エージェントが実行した有効でない行動に対しても，その行動を将来
に実行する可能性が高いと解釈しながら行われる．したがって，推定した他エー
ジェントの政策と他エージェントが実際に獲得している政策との間の誤差は大き
くなる．この誤差は自分（エージェント ）の学習（適当な政策の獲得）を遅らせ
る原因となる．更に，自分の学習の遅れは，他エージェントの学習（適当な政策
の獲得）を遅らせる．このように，他エージェントの政策の推定誤差は，マルチ
エージェント系全体の学習を遅らせる方に働く．適当な政策の獲得までに多くの
時間を費やす課題では，この他エージェントの政策の推定誤差が原因で生じる学
習の遅延が大きくなると考えられる．
ところで，Whitehead らは，適当な政策の獲得までに多くの時間を費やす課題
1
に対して，状態空間を学習が比較的容易な部分状態空間に分割し，分割したそれ
ぞれの部分状態空間で強化学習を行い，学習したそれらの部分状態空間を統合す
る枠組みを提案した [3]．この枠組みにより，強化学習する状態空間を削減するこ
とができる [3, 4]．本研究では，他エージェントの行動予測を利用した強化学習
法 [2] にこの枠組みを組み込み，状態空間を削減することにより，他エージェン
トの政策の推定誤差の影響が学習関数に乗ることによる学習の遅れを軽減させ，
学習を高速化することを目的とする．
以下，2章では，シングルエージェント環境（ 単一のエージェントが存在する
環境）における強化学習について紹介する．3章では，マルチエージェント強化
学習において，これまでの研究と本論文で導入した高速化手法について述べる．
4章では，実験に用いる設定問題である追跡問題について説明し，実験結果及び
考察について述べる．5章は結論で，本研究の成果をとりまとめ，今後の課題に
ついて述べる．
2
2.
2.1
強化学習（シングルエージェント ）
強化学習の概要
強化学習 [1] とは，試行錯誤を通じて環境に適応した行動を自律的に獲得する
ための手法である．強化学習では，教師付き学習のようにどの行動をとるべきか
を教えるのではなく，行動（ action ）に対して与えられる報酬（ reward ）を手が
かりにして適応行動を獲得する．学習主体であるエージェント（ agent ）は，制御
対象である環境（ environment ）から観測される状態（ state ）に応じて行動を選
択し，環境はエージェントの選択した行動によって報酬を与える．
強化学習の枠組を図 1に示す．
Environment
state
reward
action
Agent
図 1 強化学習の枠組
報酬にはノイズや遅れがあるため，行動直後の報酬のみではエージェントの行
動が望ましいのかは判断できないが，試行錯誤を繰り返すことによってエージェ
ントはより多くの報酬を得る行動を学習する．
2.2
マルコフ決定過程
シングルエージェント環境における強化学習で扱う環境のダ イナミクスは，マ
ルコフ決定過程 [1] によってモデル化できることを仮定するのが一般的である．
マルコフ決定過程は以下のように表される．環境のとり得る状態の有限集合を
3
S ，エージェントがとり得る行動の有限集合を A と表す．各離散時間ステップに
おいて，エージェントは環境から状態 s 2 S を観測し，行動 a 2 A を実行する．
そして，環境は確率的に状態 s +1 2 S へ遷移する．その遷移確率は式 (1) で表さ
t
t
t
れる．
P (s; a; s ) = P (s +1 = s js = s; a = a)
0
(1)
0
r
t
t
t
このとき環境からエージェントへ報酬 rt+1 が確率的に与えられるが，その期待
値は式 (2) で表される．
R(s; a) = E fr +1 = rjs = s; a = ag
t
t
(2)
t
将来の報酬獲得にどれほど貢献するかを評価するため，その後得られる報酬の
時系列を考える．時系列中の報酬を割引いて足し合わされた総計を割引報酬の和
V
t
とすると，マルコフ決定過程において，エージェントの学習目標は，Vt の期待
値を最大にすること，あるいは最大にするような政策（行動決定関数）を求める
ことである．割引報酬の和は式 (3) で表される．
V = r +1 + r +2 + 2r +3 + 1 1 1 =
t
t
t
X
1
t
k
r
k
ただし， (0
r+
=0
k
+1
(3)
1) は，割引率と呼ばれ，エージェントが将来受け取る報酬を
どれくらい考慮にいれるかを決定するパラメータである．
2.3
Q
学習
強化学習の代表的な手法の一つに Q 学習 [1] がある．Q 学習では，環境から得
られる状態と，エージェントがとり得る行動の組に対して割引報酬の和の期待値
を学習する Q テーブルを保持する．Q テーブルに記憶される割引報酬の和の学
習値（ Q 値）の数は，エージェントの状態数を S ，可能な行動数を A とすると，
S 2 A となる．
エージェントは，Q 値をもとに政策にしたがって行動を選択する．異なる政策
の下では，同じ状態においても選択する行動が異なる可能性がある．行動選択法
の代表的なものとして，greedy policy（貪欲な政策）と呼ばれる常に最大の Q 値
4
を持つ行動を選択するものや，一定の確率（ " ）でランダムに行動を選択し，そ
れ以外は常に最大の Q 値を持つ行動を選択する "-greedy policy などがある．本
論文では，環境の探査（ exploration ）と知識利用（ exploitation ）の両方の性能を
兼ね備えたボルツマン選択法を用いる．状態 s において，行動 a を選択するボル
j
ツマン選択法の選択確率 (a s) は，式 (4) で与えられる．
(ajs) = P
ここで
e
(
)
Q s;a =T
b2A
e
(
(4)
)
Q s;b =T
Q(s; a) は，状態 s，行動 a に対する Q 値，A はとり得る行動の集合，T
は温度係数である．温度係数が大きい場合はエージェントがよりランダムに行動
を選択し，温度係数が小さいとより貪欲的に行動を選択することになる．Q 値の
更新は，エージェントが行動して状態が遷移する毎に行う．状態 s において行動
a を選択し，その結果状態 s
0
に遷移し，環境から報酬 r を受けとった時の Q 値の
更新式を式 (5) に示す．
Q(s; a)
ここで，(0
(1 0 )Q(s; a) + fr + max Q(s ; a )g
0
a0 2A
0
(5)
< 1); (0 1) は，それぞれ学習率，割引率と呼ばれるパ
ラメータである．
Q 学習は，マルコフ決定過程の下である条件を満たすように調整すれば，最適
解に収束することが証明されている [5, 6]．
2.4
状態空間分割を用いた Q 学習
強化学習の応用問題では，主に設計者が達成すべき状態（ゴール）で報酬を与
えるという形で，させたいタスクをエージェントに指示している．このような問
題に対して，エージェントの状態の観測がゴールの情報を基に行われると，ゴー
ルの数の増大によって状態数の組み合わせ爆発を引き起こす．状態空間分割を用
いた Q 学習 [3] では，状態を決定しているゴール毎の部分状態に分割して，それ
ぞれに Q テーブルを保持することにより状態数の爆発を防ぐ．例えば，ゴールが
一つの問題の場合の状態数を M とすると，ゴールの数が N 個になると，一般的
5
な Q 学習では状態数は M N となるが，状態空間分割を用いた Q 学習では状態数
はM
2 N に抑えることができる．
状態空間分割を用いた Q 学習におけるエージェントの状態 s を，式 (6) に示さ
れるように各部分状態の集合により定義する．
s = fc1; c2; 1 1 1 ; c
N
g
(6)
ここで，N は分割した状態空間の総数を表す．本論文では予めゴール毎に状態空
間分割を行っており，N はゴールの数に相当するが，学習途中で部分状態の内容
を変更したり N を変化させる状態空間分割法も提案されている [7, 8]．
state
Environment
reward
action
Agent
Control Module
Learning Learning
Module
Module
Learning
Module
図 2 状態空間分割を用いた Q 学習
図 2に示すように，状態空間分割を用いた Q 学習システムは，複数の学習モ
ジュール（ learning module ）と単一のコントロールモジュール（ control module ）
からなる．学習モジュールは，式 (6) で分割された部分状態毎に Q テーブルが割
り当てられ，その分割された状態空間に対する学習結果を保持する．コントロー
ルモジュールは各学習モジュールの学習結果をもとにエージェントの行動を決定
する．
6
3.
3.1
マルチエージェント 強化学習
マルチエージェント 強化学習の概要
大規模なシステムでは，それを構成する要素毎に自律的な判断させ，それらを
協調行動させる自律分散システムの構築が求められている．そのための解決策と
して，マルチエージェント環境（複数のエージェントが存在する環境）での強化
学習（マルチエージェント強化学習）が注目されている [9]．マルチエージェント
環境は，一般的にマルコフ決定過程でないので，Q 学習の収束性は保証されない
が，状態遷移の不確実性の影響が大きくなければ局所的政策への収束は期待でき
る [10]．
3.2
他エージェント の行動予測を利用した強化学習
本論文で提案する強化学習法は，前述した他エージェントの行動予測を利用し
た強化学習法 [2]（以下，RLwAE と書く）に，状態空間を複数に分割して強化学
習を行う枠組み [3] を組み込んだものである．本節では，RLwAE について説明
する．他エージェントの行動予測としては，自分 (エージェント ）の政策を基に
予測するもの [11] があるが，RLwAE では他エージェントの過去の行動の観測を
基に予測するもの（ 後述の式 (10) 参照）を採用する．
RLwAE は，２体エージェント環境における強化学習法で，学習関数として Q
Q (s; a ; a ) を用いている．ここで，Q (s; a ; a ) は，環境の状態 s 2 S で
自分（エージェント k ）が行動 a 2 A ，他エージェントが行動 a 2 A を実行
することがエージェント k とってどれだけ効果的かを表す関数（価値関数）であ
る．ここで，S は環境状態の集合，A はエージェント k の行動の集合，A は他
エージェントの行動の集合を表す．RLwAE では，学習関数中の変数 a の値（他
関数
k
k
k
o
k
k
k
o
o
o
k
o
o
エージェントの行動）を予測しながら学習を進行する．以下に，RLwAE の学習
の流れを示す．
1. 現在の状態 s
2 S において，エージェント k は式 (7) の soft-max 関数で
7
(a js) に従って行動を確率的に選択する．
k
与えられる政策
k
e k ( k )
(a js) = P
e k (
k
Q
s;a
=T
(7)
k
k
Q
b2A
)
s;b =T
(a js) は，エージェント k が状態 s で行動 a 2 A を選択
(s; a ) は
する確率を表す．T は式 (4) と同様，温度係数である．また，Q
k
ここで，政策
k
k
k
k
k
式 (8) で与えられる関数である．
X
Q (s; a ) k
I (a js)Q (s; a ; a )
k
k
o
a 2A
o
(8)
k
o
k
o
I (a js) は，エージェント k が推定した他エージェントの政
策で，他エージェントが状態 s で行動 a 2 A を選択すると（エージェン
ト k が ）予想している確率を表す．
k
ここで，関数
o
o
o
2. エージェント k は，手続き１で選択した行動 a
他エージェントも同期して行動
動により，状態は
r
k
s から s
0
a
2A
o
k
o
2A
k
を実行する．ここで，
を実行する．両エージェントの行
2 S へ遷移し，エージェント k は環境から報酬
を受け取る．
3. エージェント k は，状態 s，行動 a ; a に対する Q 関数値を式 (9) に従っ
k
o
s で他エージェントが実行可能な全ての行動 a
js) を更新する．
対して，式 (10) に従って関数 I (a
て更新し，状態
other
2A
o
に
k
other
(s ; a ) g
(1 0 )Q (s; a ; a ) + fr + max Q
Q (s; a ; a )
k
k
k
o
I (a
k
other
js)
ここで，式 (9) 中の
式 (10) 中の (0
k
k
o
(1 0 )I (a
k
other
k
0
k
a 2A
0
0
k
k
8
<
js) + : (a = a )
0 (otherwise)
other
o
(9)
(10)
; は，式 (5) と同様，学習率，割引率である．また，
1) は，観測した行動を将来の行動予測時にどれくら
い考慮するかを決定するパラメータである．
4. 学習の終了条件を満たしていれば終了．そうでなければ，手続き１に戻る．
RLwAE では，以上の学習法を２体のエージェントの両方が自律的に行う．
8
3.3
他エージェント の行動予測を利用した強化学習の高速化
RLwAE は，獲物が１体の追跡問題 [12]（ 4.1節で後述する追跡問題の問題設定
において獲物を１体にしたもの）に適用され，その有効性が示されている [2]．こ
の獲物が１体の追跡問題は，目標の達成に２体のハンター（エージェント ）の協調
が必要であるが，目標は一つしか存在しないため学習は比較的容易で，ハンター
が適当な政策を獲得するまでにあまり多くの時間を費やさない課題である．ここ
で，RLwAE を獲物が複数の追跡問題（ 4.1節で後述する追跡問題）に適用するこ
とを考える．この獲物が複数の追跡問題では，ゴールが複数存在し，それぞれの
ゴールの達成に２体のハンターの協調が必要である．この課題において，他ハン
ターがどのゴールを達成しようとしているのか（どの獲物を捕獲しようとしてい
るか）わからないため，捕獲行動の学習は獲物が１体の場合より難しくなる．ま
た，獲物を１体から複数に増やすことにより，状態集合 S の要素数は増加し，状
態空間が増大する．したがって，獲物を１体から複数に増やした場合，ハンター
（エージェント ）が適当な政策を獲得するまでにより多くの時間を費やすと考え
られる．ところで，RLwAE は，エージェントが適当な政策を獲得するまでに多
くの時間を費やす課題に対しては，あまり有効でないことが予想される．他エー
ジェントが適当な政策を獲得していない段階では，他エージェントは適当でない
行動（学習の進行により，将来実行しなくなる行動）を実行する確率が比較的高
いが，RLwAE では，他エージェントが実行した適当でない行動に対しても，将
来にその行動を実行する可能性が高いと解釈しながら他エージェントの政策を推
定する（ 式 (10) による関数
獲得している政策
o
I
k
の更新）．したがって，他エージェントが実際に
と推定した他エージェントの政策
くなる．RLwAE において，自分（エージェント
エージェントの政策
I
k
k
との間の誤差は大き
k ）の政策 k
は，推定した他
に依存しているため，この誤差は，エージェント
当な政策の獲得を遅れさせる．同様に，エージェント
れは，他エージェント
I
k の適
k の適切な政策の獲得の遅
o の適当な政策の獲得を遅れさせる．RLwAE では，２体
のエージェントの両方が 3.2節で示した強化学習法を利用していることに注意す
る．このように，RLwAE において，適当な政策の獲得の遅れは，学習（適当な
政策の獲得）の遅れを加速させる方に働く．適当な政策の獲得までに多くの時間
9
hunter_2
prey_2
hunter_1
prey_1
s=([-3,2],[-1,-2],[1,2])
c1=([-3,2],[-1,-2])
c2=([-3,2],[1,2])
図 3 状態と部分状態
を費やす課題に対しては，この他エージェントの政策の推定誤差が原因で生じる
学習の遅延が大きくなると考えられる．
ところで，Whitehead らは，適当な政策の獲得までに多くの時間を費やす課題
に対して，状態空間を学習が比較的容易な状態空間に分割し，分割したそれぞれ
の状態空間で強化学習を行い，学習したそれらの状態空間を統合する枠組みを提
案した [3]．この枠組みにより，強化学習する状態空間を削減することができる．
この枠組みを RLwAE に組み込んだ場合，状態空間サイズは小さくなるため，他
エージェントの政策の推定誤差の影響が学習関数（ Q 関数）に乗ることによる学
習の遅れが軽減し，学習が高速になることが期待できる．本論文では，この枠組
みを RLwAE に組み込み，学習が高速になるかど うか調査する．
本論文では，実験に使用するタスクとして，4.1節で後述する獲物が複数の追
s の表現には s = (p ; p1; p2; 1 1 1 ; p )
を用いる．ただし，p は自分（ hunter k ）と他ハンター（ hunter o ）の相対位置，
p (i = 1; 2; 1 1 1 ; N ) は自分と prey i の相対位置である 1 ．N は分割した状態空間の
跡問題を取り上げる．ここで，環境の状態
o
N
o
i
1 上下，左右の境界が繋がっているグリッド 空間の状態表現は相対位置の組合せで表すのが一
般的で，この表現により，非冗長な状態の記述ができる．
10
s = (p ; p1; p2; 1 1 1 ; p )
を，式 (6) に示す部分状態 c1 = (p ; p1 ); c2 = (p ; p2 ); 1 1 1 ; c = (p ; p ) に分割す
る．例えば，図 3 の hunter 1 から見た状態は s = ([03; 2]; [01; 02]; [1; 2])，部分
状態は c1 = ([03; 2]; [01; 02]); c2 = ([03; 2]; [1; 2]) である．そして，それぞれの
部分状態における Q 関数 Q1 (c1 ; a ; a ); Q2 (c2 ; a ; a ); 1 1 1 ; Q (c ; a ; a ) を用意
する．状態 s で，エージェント k が行動 a ，他エージェントが行動 a を実行
し，状態が s 2 S へ遷移し，エージェント k が環境から報酬 r を受け取ったと
する．そのとき，エージェント k は，部分状態 c (i = 1; 2; 1 1 1 ; N )，行動 a ; a
に対する Q 関数値 Q (c ; a ; a ) を式 (11) で更新する．
総数（本論文ではゴールの数）を表す．本研究では，状態
o
o
o
k
N
k
k
N
o
N
k
o
k
o
N
N
k
o
k
o
0
k
i
k
o
k
i
i
Q (c ; a ; a )
k
i
状態
i
k
o
k
o
(s ; a )g
(1 0 )Q (c ; a ; a ) + fr + max Q
k
i
k
i
k
o
k
k
0
(11)
0
k
k
a 2A
s における Q 関数値 Q (s; a ; a ) は式 (12) により求める．
k
k
o
Q (s; a ; a ) =
k
k
学習の流れは，式 (8) 中の
o
1
N
X
N
=1
Q (c ; a ; a )
(12)
k
i
i
k
o
i
Q (s; a ; a ) に式 (12) で求めた Q (s; a ; a ) を用い，
k
k
k
o
k
o
式 (9) の代わりに式 (11) を用いることを除くと，3.2節で示した RLwAE の学習
の流れと同じである．
11
: hunter
: prey
図 4 追跡問題のグリッド 空間（獲物が 2 体）
4.
4.1
実験
追跡問題
本研究では，実験に使用するタスクとして，マルチエージェント系の研究で広
く利用されている追跡問題 [12] を取り上げる．追跡問題は問題設定の変更が容易
で，研究の焦点に合わせた設定が可能である．本研究では，獲物が複数の追跡問
題として，獲物が 2 体の場合 [13] と獲物が 3 体の場合の２つの実験を行う．以下
に，本研究における問題設定を示す．
1. 獲物が 2 体の追跡問題
２次元（ 7
2 7 ）のグリッド 空間中に，２体のハンターと２体の獲物が
存在する（図 4 ）．ここで，グリッド 空間の上と下，右と左の境界は繋
がっているものとする．
各離散時間ステップ毎に，ハンターと獲物は，それぞれ１つの行動を
同期して実行する．ここで，ハンターが実行可能な行動は，隣接する
上，下，左，右のグリッド へ移動する（ 図 4の矢印），現在位置に留
まる，の５通りとする．また，獲物の実行可能な行動は，隣接する上，
12
図 5 捕獲状態の例（獲物が 2 体）
右のグリッドへ移動する（図 4の矢印），現在位置に留まる，の３通り
とする．
ハンターの目標は，２体の獲物のうちいずれか１体を捕獲することで
ある．ここで，
『 捕獲』の定義は『２体のハンターが獲物を上下，ある
いは左右から挟んだ状態』とする（図 5 ）．
本研究では，ハンターを『エージェント 』と定義する．そして，２体
のハンターのそれぞれが，獲物を捕獲する協調行動を強化学習により
自律的に獲得することを目的とする．
初期配置から獲物が１体捕獲されるまでを『１エピソード 』とする．い
ずれか１体の獲物が捕獲されると，全てのハンターと獲物はグリッド
空間中にランダムに初期配置され，新たなエピソードを開始する．
ハンターはグリッド 空間全体を観測できるとし，グリッド 内に存在す
る全ての獲物とハンターの正確な位置情報を知ることができるとする．
ハンター間のコミュニケーションは存在しないものとする．
獲物は学習を行わず，３通りの行動の中から１つの行動を確率的に選
択する．獲物の行動選択確率は，右へ移動する確率と現在位置に留ま
る確率をそれぞれ 25 ，上へ移動する確率を
率は時不変とする．
13
1
5
とする．この行動選択確
: hunter
: prey
図 6 追跡問題のグリッド 空間（獲物が 3 体）
図 7 捕獲状態の例（獲物が 3 体）
2. 獲物が 3 体の追跡問題
２次元（ 5
2 5 ）のグリッド 空間中に２体のハンターと３体の獲物が存在す
ること（図 6 ）と，ハンターの目標が３体の獲物のうちいずれか１体を捕獲
すること（ 図 7 ）以外は，獲物が 2 体の追跡問題と同様である．
14
Average time steps needed in an episode
400
RLwAE
350
RLwAE_SD
300
250
200
150
100
50
0
0
6
2 10
6
4 10
6
6 10
6
8 10
7
1 10
Number of learning time steps
図 8 獲物捕獲までに費やした平均時間ステップ数（獲物が 2 体の追跡問題）
4.2
実験結果及び考察
3.2節で示した手法（ RLwAE ）と，3.3節で示した手法（ RLwAE に状態空間
を分割する枠組を組み込んだ手法．以下，RLwAE SD と書く）を，4.1節で示し
た獲物が２体の追跡問題と獲物が 3 体の追跡問題に適用した．獲物が 2 体の追跡
問題に適用した実験結果を 図 8 と 図 9 に，獲物が 3 体の追跡問題に適用した実
験結果を図 10 と 図 11に示す．図 8，図 10 の結果は，10000 学習タイムステッ
プ毎に，その時までの学習性能を評価するため，初期配置を変えた 100 評価エピ
ソード の実験を行い（このエピソードでは学習を行わない），その平均タイムス
テップ数（１評価エピソード 中に費やしたタイムステップ数）を示したものであ
る．ここで，学習タイムステップとは，学習開始時から費やしたトータルのタイ
ムステップである（ 評価エピソードでのタイムステップは含まない）．図 9，図
15
0.05
RLwAE
Mean square error
RLwAE_SD
0.04
0.03
0.02
0.01
0
6
0
6
6
4 10
2 10
6
8 10
6 10
7
1 10
Number of learning time steps
図 9 行動確率予測の二乗平均誤差（ 獲物が 2 体の追跡問題）
11 の結果は，10000 学習タイムステップ毎に，式 (13) で与えられる平均二乗誤
差（ MSE ）を示したものである．
MSE =
1
jS j 2 jA j
o
j j
ここで， Ao は集合
A
o
X
fI (a js) 0 (a js)g2
k
o
s2S;a 2A
o
(13)
o
o
o
の要素数である．MSE は，他エージェントの政策推定
がどれくらいうまくいっているかを示すための尺度で，値が小さいほど 推定誤差
（関数 I k と他エージェントの政策 o の誤差）が小さいことを表す．実験で使用し
た学習パラメータの値は， = 0:3， = 0:9，T = 0:1， = 0:5
2 0:999977
num ep
ep はエピソード 数（ 評価実験のエピソード は含まない）
を表す．減衰係数 0:999977 は 0:999977100000 0:1 となるように選ばれた値であ
る．ここで，エピソード 数 100; 000 は，獲物が 2 体の追跡問題を適用した実験で，
である．ここで，num
16
Average time steps needed in an episod
80
RLwAE
RLwAE_SD
60
40
20
0
6
0
2 10
6
4 10
6
6 10
6
7
8 10
1 10
Number of learning time steps
図 10 獲物捕獲までに費やした平均時間ステップ数（獲物が 3 体の追跡問題）
両学習法における平均タイムステップ数（図 8 ）が収束するあたりのエピソード
数である（ 100; 000 エピソード までに，RLwAE DS においては約 5,600,000 学習
タイムステップ， RLwAE においては約 7,300,000 学習タイムステップに対応す
る）．それぞれのハンターが環境から受け取る報酬 rk は，獲物捕獲時に
r = 1: 0 ，
それ以外の時に r = 00:05 としている．すべての s 2 S ，c 2 C ，a 2 A ，
a 2 A に対して，Q 関数，関数 I の初期値は，それぞれ Q (s; a ; a ) = 0:0，
Q (c ; a ; a ) = 0:0，I (a js) = 0:2 としている．ここで，C は部分状態の集合と
k
i
k
o
i
k
k
k
o
k
k
k
o
k
i
k
o
o
する．
図 8 の結果は，RLwAE SD と RLwAE の両学習法の獲物捕獲までに費やした
平均タイムステップ数の収束値はほぼ同等であるが，収束までに費やす学習タイム
ステップ数 は RLwAE SD の方が少ないことを示している．これは，RLwAE SD
の方が RLwAE より学習が高速であることを示している．
17
0.04
RLwAE
Mean square error
RLwAE_SD
0.03
0.02
0.01
0
0
6
2 10
6
4 10
6
6 10
6
8 10
7
1 10
Number of learning time steps
図 11 行動確率予測の二乗平均誤差（ 獲物が 3 体の追跡問題）
図 9 の結果は，他エージェントの政策の推定誤差が，7,000,000 学習タイムス
テップぐらいまでは RLwAE SD の方が RLwAE より小さいことを示している．
また，推定誤差の値が収束するまでに費やす学習タイムステップ数は RLwAE SD
の方が少ないことを示している．
図 10 の結果は，RLwAE SD は RLwAE よりも獲物捕獲までに費やした平
均タイムステップ数が小さい値で収束する．獲物が 3 体の追跡問題においても
RLwAE SD の方が RLwAE より学習が高速であることを示している．
図 11 の結果は，他エージェントの政策の推定誤差が，5,000,000 学習タイムス
テップぐらいまでは RLwAE SD の方が RLwAE より小さいことを示している．
また，推定誤差の値が収束するまでに費やす学習タイムステップ数は RLwAE SD
の方が少ないことを示している．
RLwAE SD が RLwAE より学習が高速になった原因は， RLwAE SD におけ
18
る状態空間のサイズが RLwAE における状態空間のサイズよりも小さいためであ
ると考えられる（例えば，獲物が 2 体の追跡問題を適用した実験では，RLwAE
jS j = 493 であるのに対し，RLwAE SD における
状態空間のサイズは 2 2 jC j = 2 2 492 である）．状態空間のサイズが小さくなる
における状態空間のサイズは
ことにより，他エージェントの政策の推定誤差の影響が学習関数に乗ることによ
る学習の遅れが軽減され，学習が速くなっていると思われる．ところで，学習が
高速化することは，エージェントが試行錯誤する時間が短くなることを意味して
おり，他エージェントが不適当な行動を実行する回数が減る．この不適当な行動
の減少が，他エージェントの政策の推定誤差を小さくしていると考えられる．そ
して，この推定誤差の縮小が，学習が速くなることを助けていると思われる．
19
5.
結論
本研究では，他エージェントの実行する行動を予測しながら学習を進行する強
化学習法に，状態空間を複数に分割して学習を進行する枠組みを組み込み，複数
の獲物が存在する追跡問題に適用した．実験の結果，状態空間を複数に分割して
学習を進行する枠組みを組み込んだ方が，組み込まないものに比べて，学習が高
速になった．また，他エージェントの行動予測もより正確にできるようになった．
学習の高速化には，状態空間の分割による状態数の削減だけではなく，より正
確な他エージェントの行動予測も影響しているものと考えられるが，行動予測の
向上がどの程度学習の高速化に寄与しているかについての調査は，今後の課題で
ある．
20
謝辞
本研究を進めるにあたり，数々の御指導をいただきました伊藤実教授に深く感
謝致します．
また，本研究について助言を与えて下さいました研究室の皆様に，厚く御礼申
し上げます．
21
参考文献
[1] R. S. Sutton, and A. G. Barto : Reinforcement Learning: An Introduction,
MIT Press (1998).
[2] Y. Nagayuki, S. Ishii, M. Ito, K. Shimohara, and K. Doya : A Multi-agent
reinforcement learning method with the estimation of the other agent's action, Proc. 5th International Symposium on Articial Life and Robotics,
pp.255-259 (2000).
[3] S. Whitehead, J. Karlsson, and J. Tenenberg : Learning Multiple Goal Behavior via Task Decomposition and Dynamic Policy Merging, ed. J. H. Connell et al., Robot Learning, pp.45-78, Kluwer Academic Press (1993).
[4] N. Ono, and K. Fukumoto : Multi-agent reinforcement learning: a modular approach, Proc. 2nd International Conference on Multi-Agent Systems,
pp.252-258 (1996).
[5] C. J. C. H. Watkins, and P. Dayan : Technical Note Q-Learning, Machine
Learning, Vol.8, No.3, pp.279-292 (1992).
[6] 西田 豊明 : 人工知能の基礎, 丸善, pp.268-272 (1999).
[7] T. Kohri, K. Matsubayashi, and M. Tokoro : An adaptive architecture for
modular Q-learning, Proc. 15th International Joint Conference on Articial
Intelligence, pp.820-825 (1997).
[8] I. Ono, T. Nijo, and N. Ono : A Genetic Algorithm for Automatically Designing Modular Reinforcement Learning Agents, Proc. of the Genetic and
Evolutionary Computation Conference, pp.203-210 (2000).
[9] 三上 貞芳 : 強化学習のマルチエージェント系への応用, 人工知能学会誌,
Vol.12, No.6, pp.845-849 (1997).
22
[10] 荒井 幸代, 宮崎 和光, 小林 重信 : マルチエージェント強化学習の方法論{ QLearning と Prot Sharing による接近 {，人工知能誌，Vol.13, No.4, pp.609618 (1998).
[11] 長行 康男, 石井 信 : 他エージェントの内部モデル推定を利用したマルチエー
ジェント強化学習法, 電子情報通信学会技術研究報告, AI2000-4, pp.21-28
(2000).
[12] L. Gasser, N. F. Rouquette, R. W. Hill, and J. Lieb : Representing and
using organizational knowledge in distributed AI systems, ed. L. Gasser,
and M. N. Huhns, Distributed Articial Intelligence, Vol.2, pp.55-78, Morgan
Kaufmann (1989).
[13] 稲垣 浩司, 長行 康男, 伊藤 実 : 他エージェントの行動予測を利用したマル
チエージェント強化学習の状態空間分割による高速化, 第 14 回自律分散シス
テム・シンポジウム資料, pp.89-94 (2002).
23