論文

遅れ報酬に基づく遺伝的アルゴ リズムによる部分観測マルコフ決定問題の
解決手法
山城

啓秀y3

上野

敦志y

英明yy33

武田

Delayed Reward-based Genetic Algorithms for Partially Observable Markov
Decision Problems
Yoshihide YAMASHIROy3, Atsushi UENOy , and Hideaki TAKEDAyy33
あらまし 強化学習は通常マルコフ性が仮定されていることが多い．しかし，エージェントが環境を完全に観測できるとは限らず，そのような場合，異なる状態を同一の状態として観測する．本研究ではこのような知覚の見せかけ問題を伴う部分観測マルコフ決定問題（ POMDP ）を解決する手法として，遅れ報酬に基づく遺伝的アルゴリ

ズム（ DRGA ）を開発した．DRGA は POMDP を複数のサブタスクに分割し，エージェントを複数のサブエー
ジェントに分割することで POMDP を解決する．それぞれのサブエージェントは遅れ報酬を用いることで環境に適した政策を獲得し，政策自体は学習を通して得られた遅れ報酬に基づき遺伝的アルゴリズムによって進化する．
淘汰されて生き残った有効な政策を組み合わせることによって環境に適応する．本手法を知覚が限定された迷路探索問題に適用し，その有効性を示す．
キーワード

強化学習，遺伝的アルゴリズム，部分観測マルコフ決定問題，知覚の見せかけ問題

ための環境モデルをエージェント内部に構築できれば

1. ま え が き
強化学習は マル コフ決定過程（

Markov decision

process, MDP）を対象と することが 多いが ，エー

良い．こういった観点から本研究はエージェントを複数のサブエージェントに分割し，知覚の見せかけ問題
がタスク達成に影響を与える前に別のサブエージェン

ジェントが知覚できる情報は不十分なことが多い．不トに制御を渡す．このような分割によって各サブエー

十分な知覚によって複数の異なる状態を同じ状態としジェントは問題をて知覚してし まうという問題が起こる．これを知覚としての見せかけ問題（

分割は，各サブタスクにサブゴールを設定することでperceptual aliasing ）[1] という．こMDP として扱うことができ，全体

POMDP を解決することができる．タスクののような知覚の見せかけ問題が生じる部分観測マル

行う．分割されたサブエージェントはサブゴールに到

コフ決定問題（達することを目的とする．問題は，タスクをうまく分

partially observable Markov decision
problem, POMDP）環境下ではエージェントが現状態を正確に知ることは不可能で，MDP を対象としたアルゴリズムでは十分な学習結果が得られなくなる．

割するためのサブゴールの学習と，各サブエージェン
トにおける

MDP の学習である二つのレベルに分けられる．

しかし，エージェントはタスクを遂行することに関このような不完全知覚の問題では，知覚が不完全なしては，環境を完全に知る必要はなく，タスク達成のためにかえってうまく抽象化することができて，色々な場面で同じ政策が共通して通用するということがy 奈良先端科学技術大学院大学 情報科学研究科，生駒市

Graduate School of Information Science, Nara Institute of
Science and Technology (NAIST)あり得る．異なる地点が同じように見える場合，それぞれで違う行動を選択する必要がある場合にはタス

yy 国立情報学研究所，東京都

ク達成が困難になるが，どちらも同じ行動を選択すれ

3 現在，（ 株）三洋電機
33 併任 奈良先端科学技術大学院大学

ば良い場合には，知識をうまく再利用することできる

National Institute of Informatics (NII)

電子情報通信学会論文誌のである．そこで，本論文では，このような不完全知D{I Vol. Jxx{D{I No. xx pp.1{13 xxxx 年 xx 月

1

電子情報通信学会論文誌 'xx/xx Vol. Jxx{D{I No. xx

Agent

Q-TABLE 1

1***

S3 S4 S5
*1**

**1*

S2

S6

0101

0101

S1

S7

0111

0111

Q-TABLE|O| x |A| matrix*: 0 or 1
Perceptual input gained by the agent
when each grid is a part of a wall

Perceptual input in each grid

(a)

(b)

図 1 グ リッド 環境での知覚の見せかけ問題
Fig. 1 Perceptual aliasing in grid space.

HQ-TABLE 1

TRANSFERCONTROL

1001 1010 1100***1

Subagent 1

Q-TABLE 2

When ariving at the subgoal, the control
is passed to the next subagent.
HQ-TABLE
Subagent 2|O| x 1 matrix
HQ-TABLE 2
TRANSFERCONTROL

used for deciding the
behavioral policy ofthe subagent

used for deciding
the subgoal of
the subagent

Active agent
Q-TABLE m

Subagent m

覚の大規模問題において色々な場面で同一の小問題がたくさん現れるような問題を対象として，遅れ報酬に

The last agent has only a Q-table.

Delayed Reward-based
Genetic Algorithm for POMDP, DRGA）を提案す
る．DRGA では，タスク全体を見て問題を MDP に

図2

HQ-learning − サブエージェント構成図
Fig. 2 Agent architecture of HQ-learning.

基づく遺伝的アルゴリズム（

2. 2 HQ-learning

HQ-learning は Q-learning[3] を階層的に拡張した
POMDP として問題とされて分割しながら，色々な場面で役に立つ政策が生き残り，再利用可能な場面を見つけてそれらの有効な政策を適用していくことによって大規模な部分観測マルコフ決定問題に対応する．

アルゴ リズムである．

いる知覚の見せかけ問題を解くことを対象としてい

POMDP をサブタスクに分割して解く る．部分観測問題において，サブゴールをおくことでタスクをサブタスクに分割し ，各サブタスクに対し先行研究として HQ-learning[2] が 提案されている．
て Q-learning を用いて学習する枠組である．図 2 に
しかし ，HQ-learning では 個々のサブ エージェント
HQ-learning でのエージェントの構成図を示す．
が全く独立に学習を行っていて，有効な政策の再利
このように用は全く考えていない．同一の小問題に分けることができるような不完全知覚の大規模問題を扱う場合，全く独立に学習するのは非効率的である．本稿ではHQ-learning との比較実験を通して DRGA の有効性を示す．

エージェントは複数のサブエージェントによって構成され，サブエージェント

1 からサブエージェント mmまで順番に制御が移される． はあらかじめ決められた数である．制御が移るタイミングは各々のサブエー

ジェントが自身のサブゴールに到達した時である．サ
ブゴールは知覚状態の内の一つとして定義される．

2. POMDP
2. 1 グリッド 環境における知覚の見せかけ問題
本研究では，次のようなグリッド 環境における知覚の見せかけ問題を扱う．エージェントの知覚能力はグ
リッド 環境において隣接したグリッドに壁があるかな
いかだけを知覚できるものとする．すなわち，エー
ジェントの知覚入力は４ビットで表され，先頭のビットから順に，１である時，それぞれ北東南西方向のグ1a）．図1b において，エージェントは S1 と S7 の位置，S2 とS6 の位置ではそれぞれ同じ知覚入力を得るため，どリッドに壁があることを示すものとする（図各サブエージェントは Q テーブルに基づいて MaxBoltzmann ル−ルで行動を決定する．Q テーブルは
Q 値（ 行為価値 ）のテーブルであり，知覚状態集合

O，行動集合 A とすると，知覚と行動の組合せである
O A の大きさを持つ．Max-Boltzmann ル−ルは
確率 Pmaxで最大 Q 値の行動を選択し，確率 1 Pmax
j

j2j

j

0

で次の式

(1) で表されるボルツマン分布に基づく確率

で行動を選択する．

Q(o;a)=T
a0 2A

probo(a) = P e eQ(o;a0 )=T(1)

ちらの位置であるかを知ることはできない．この問題

probo(a) は知覚状態 o で行動 a を選択する確率である．T は行動を選ぶ際のランダム性を調整する温度パでは，環境はマルコフ的であるがエージェントの知覚

ラメ−タである．

能力の不足によって

2

POMDP と見なせる．

サブゴ ールの学習は

HQ テーブルを 用いて行う．

論文／遅れ報酬に基づく遺伝的アルゴリズムによる部分観測マルコフ決定問題の解決手法

HQ テーブルは HQ 値（ 各知覚状態のサブゴ ールとO 1の大きさを持つ．サブゴ ールは HQ テーブルに基づいて Max-Random ルールで決定される．すなわち，
確率 Pmaxで最大 HQ 値の知覚状態を選択し ，確率
1 Pmaxでランダムに選ぶ．
HQ-learning では ，各状態遷移を 記憶し て おき ，エージェントがタスク終了時に一括して Q 値，HQ
値の更新を行う（オフライン更新 ）．Q 値は oine
Q()-learning[4] を用いて更新され，HQ 値は以下の式 (2) で更新される．

しての適切さの評価値）のテーブルであり，jj 2

0

X t0t R(st; at)Ri =ti+1 0100(0 <= <= 1) は報酬の割引率であり，将来報酬と即時報酬のトレード オフの割合を示している．R(s; a) は状態 s で行動 a をとった時に得られる
ここでRiはサブエージェント i の動作している時刻 tiから ti+1 1 に得た報酬の総計を示している．HQi (o) はサブエージェント i の知覚状
態 o に対する HQ 値，o^iはサブエージェント i でその時選ばれたサブゴ ール， HQ (0 <= HQ <= 1) は0
HQ テーブルの学習率である．HQi(o) は eligibility
報酬である．従って，

0

traces 1 を用いた場合の目指すべき HQ 値であり，
 (0 <=  <= 1) は eligibility traces を用いる程度を表）す定数である．

2. 3 HQ-learning の問題点

HQ-learning は，問題を MDP で表されるところまで分割し，決められた順番通りにサブエージェントを適用していく．このようにエージェントの内部変数のみに基づいてサブエージェントを決定する手法では，サブエージェントを切り替える地点でどの政策が有効かの指標が全くないので，既知の政策を手当り次第に試してみるか，全く独立に学習し 直すしか方法がな

HQ-learning では後者の方法を用いていて，有効

い．

1 ）：eligibility traces とは，状態における評価値（ Q 値や HQ 値）を計算する時に，状態の遷移系列上の直後の 状態の評価値のみを考慮するのではなく，それ以降の状態の評価値も考慮に 入れて計算するという概念であって，強化学習の報酬の分配を効率良くした り，部分的にマルコフ性が成り立たない（

大規模問題を扱う場合，全く独立に学習するのは非効率的である．そのため，ゴールに到達するまでに多くのサブエージェントが必要な時には環境に適応できな

HQ-learning の元論文 [2] で扱っていい場合がある．

る問題は，最も難しい問題でも最小で３サブエージェ
ントで解けてしまうので，もっと大規模な問題に対する適用性は検証の余地がある．

3. 本研究の目的と手段
本研究では，部分観測マルコフ決定問題において，i（注うな同一の小問題に分けることができる不完全知覚の色々な場面で同一の小問題がたくさん現れるような

t=ti
0
0
HQi (^oi ) Ri + ti+10ti [(1 )max
o0 2O HQi+1(o )+ HQ0i+1(^oi+1)]
HQi (^oi ) (1 HQ )HQi (^oi )+ HQ HQ0i (^oi ) (2)（注

な政策の再利用は全く考えていない．本論文で扱うよnon-Markov）問題に対応したりす る効果がある．詳しくは文献 [5] 参照．

問題を対象とする．そして，タスク全体を見て問題をMDP に分割しながら，知覚的見せかけを利用して色々な場面で同じ政策を再利用することによって，大規模な部分観測マルコフ決定問題に対応できる手法の開発を目的とする．
知覚の見せかけ問題を対象とする手法があえて知覚的見せかけを残すのは不自然に思われるかも知れない．しかし，異なる地点が同じように見える場合，それぞれで違う行動を選択する必要がある場合には困った問題を引き起こすが，どちらも同じ行動を選択すれば良い場合には，知識をうまく再利用することができる．従って，政策を再利用しようとする学習シス
テムにとって，サブエージェントの切替え地点で知覚的見せかけが起こるのは本質的な特徴である．本研究では，タスク達成にとって障害となる知覚的見せかけを排除し，障害とならない場合は逆にうまく利用して効率良く問題を解くことを目指す．
そのための手段として，サブエージェントの切替え
地点の知覚情報に基づくサブエージェントの選択を提案する．これは，例えば「前に壁がある」という知覚情報に基づいて「壁に沿って歩く」という政策を選択するといった人間の政策選択法からの類推である．
色々な場面で同一の小問題がたくさん現れるような問題を扱う場合，ある政策がどの場面で有効であるかは環境に依存している．切替え地点の知覚情報に基づいてサブエージェントを選択することによって，環境に応じたサブエージェントの切替えが期待できる．

4. DRGADRGA アルゴ リズムの全体像と特徴を本章では，示し，その実現方法について説明する．

3

電子情報通信学会論文誌 'xx/xx Vol. Jxx{D{I No. xx

AgentSubgoal0 1

Subagent 0

Subagent 1

Subagent G

Policy 0-0
Policy 0-1
Policy 0-2

Policy 1-0
Policy 1-1
Policy 1-2

Policy G-0
Policy G-1
Policy G-2

Policy 0-NP

Policy 1-NP

Policy G-NP

Policy g-i

Perceptual Input (0,1,...15)

15

4 digits
Subgoal:
0000
0001

16 digits
Behavior:
Each number expresses
0each behavior.
1
In this case, four kindsof behaviors are expressed2in the quaternary number
3

Binary code
explained in Fig. 1

system.

1111

g : Subagent number
i : Policy number

図4

DRGA における遺伝子表現（ 図 1 の問題の場合）
Fig. 4 Genotype in DRGA (case of Fig.1).

図 3 エージェントとサブエージェント

Fig. 3 Agent and subagent.

4. 2 政策の進化 − GA
4. 2. 1 コード 化（ encoding/decoding ）4. 1 DRGA − 構成

DRGA ではエージェントが環境との試行錯誤により得た経験に基づいて強化学習を行い，一定の試行数が終了するとエージェント自体が遺伝的アルゴリズム（

Genetic Algorithm, GA ）[6] によって進化する．
DRGA は複数のサブエージェントから成り立っており，各サブエージェントは，それが適用されるべきスタート地点（ 注 2 ）の知覚情報（スタート情報）を持
つ．サブエージェントは知覚状態の種類数だけ存在

3

し，各サブエージェントは複数の政策を持つ（図 ）．
政策の数はサブエージェントに共通でOj 21 ）と，サブゴールとなる知覚状

態の二つをあわせたものである（ 注 3 ）．

エージェントは，サブエージェントの切替え地点において，その知覚情報に対応するサブエージェントの持つ政策の中から一つを選び，その政策に基づいてサブゴールに到達するまで行動する．サブゴールに到達したら，その知覚情報をスタート情報とするサブエー
ジェントに切り替わる．
サブエージェントが持つ政策のレパートリはGA によって進化し，サブエージェント内での政策の選択にはQ()-learning[7] を用いる．GA と Q()-learning

は，環境中でゴールした時などに得られる報酬を時間にさかのぼって分配したもの（遅れ報酬）に基づいて行われる．サブゴール学習とサブエージェントの行動

GA によって探索範囲を絞られた上で，Q()-learning によって実現されている．

の学習は，どちらも（注（注2 ）：3 章の「サブエージェントの切替え地点」と同じ．
3 ）：4.5 節の実施例で示すように，サブゴールに到達できること自体が政策の有効性に大きく関係しているので，サブゴールを政策に含める．

4

政策は一種の先天的行動とみなせる．

DRGA では図 4 に示すように，一つの政策を 1 染

色体として表現する．すなわち，染色体にはサブゴ−
ル情報と各知覚状態から行動へのマッピングが記述

A種
O 個であれば ，染色体はされている．例えばエージェントの動作種類が j
で知覚できる知覚種類が j

A jOj

j

j

2j

j

j

O 種類の組合せを持つことになる 4 ．
（注

j

）

4. 2. 2 進 化 手 順

NP とする．こ

こで，政策とは各知覚状態から行動への固定されたマッピング（ j

DRGA ではエージェントの知覚情報に対する決定GA によって形成される．これらの的な行動政策がGA では一般的にまず個体が環境に対し行動などを起こし，環境からの評価として適応度を得る．この適応度をもとに集団に対して選択・淘汰が行われ，生き残った個体集団に対して交叉などのGA オペレータが施される．

DRGA では GA 処理（選択・淘汰，GA オペレー
タ）はサブエージェント内で行う．Goldberg[6] によると GA は building-block hypothesis によって集団（複数点）を適応度の高い集団（結果的に 1 点）にもっていく性質があるという．このため，全てのサブエー
ジェントを一緒にしてGA 処理を行うとサブエージェ

ントでなく一つのエージェントとなるため，一つのサ
ブ タスクしか対応できなくなる．従って異なるサブ
エージェント間でのGA 処理は行わない．

まず学習開始時に，各サブエージェント内でランダ
ムに政策の初期集団（ 大きさNP ）を作る．この時，明らかに壁方向に向かう政策は初期値にならないよ
うに省いている．そして，エージェントが環境中で活4 ）：図 4 の問題の場合は，GA の探索空間は 6:9 × 1010 の大きさを持GA は非常に大きな探索空間中で準最適な解を発見するのに向いている手法なので，このような探索空間の大きい問題に GA を用いることにした．

（注つ．

論文／遅れ報酬に基づく遺伝的アルゴリズムによる部分観測マルコフ決定問題の解決手法

4.3 節で説明する Q()-learning によって，各DRGA では，各政策の適応度として，政策選択の学習において獲得される Q 値（式 (5) 遅れ報酬に基づく評価値）を用いる．
GA 処理として行うのは以下のもので，全てのサブ

1 prob でラ動し，最大の評価値を持った行動を選び，確率政策の適応度を求める．

ンダムに選択する方法や，ボルツマン分布を使って行を用いる．

Q(g;p)=T

probg (p) = P e eQ(g;p0 )=T
p0 2P

+

選択・
・
・
・
・
・
・
・エリート ルーレット戦略

1 3[8]．DRGA(3) で示されるボルツマン分布による選択

動を決定する方法など様々なものがある
では次の式

エージェントで同様に行う．


0

(3)

g



交叉・
・
・
・
・
・
・
・
・ 〜 点交叉

突然変異・・・遺伝子の置換（ランダム）

択する．その再生された親染色体集団からランダムにprobg (p) はサブエージェント g でサブエージェント
内の政策 p を選ぶ確率である．Pg はサブエージェン
ト g 内の政策集合を表す．Q(g; p) はサブエージェン
ト g における政策 p の評価値，すなわち Q 値である．
T は政策を選ぶ際のランダム性を調整する温度パラ

２本ずつ染色体を抜き出し，メータである．

まず初めに現在の政策集団から次世代の親となるNP本を選択する．その際，エリート戦略で適応度の高い順にNe 本を選び，残りは適応度に比例した確率で選Cpの確率で交叉させる．

1 3

4. 3. 2 学習更新式

交叉とは，ランダムに交叉点（ 〜 点 ）を決め，交Q 値の更新には oine Q()-learning を用いる．時叉点の間で交互に親の遺伝コードを入れ換える処理でMpある．その後，各染色体の各遺伝子座に対して，

i

giで政策 piを実行し刻 においてサブエージェントのレパートリの中から適切な政策を選択するために，

Q 値を更新する式を以下の式 (4)，(5) に記す．
0
Q0 (gi ; pi ) Ri + [(1 ) p 2max
P +1 Q(gi+1 ; p )+ Q0(gi+1 ; pi+1 )](4)
Q(gi ; pi ) (1 )Q(gi ; pi ) + Q0 (gi ; pi ) (5)
ここで i = 1; 2; ::: はサブエージェントの推移系列を

後天的学習を行う．この後天的学習にあらわす離散時間である．サブエージェントのそれぞの確率で突然変異を起こす．突然変異の際にはランダた時にシステムがムな遺伝子に入れ換えるが，明らかに壁方向に向かう

式

変異は起こさないように省いている．再生された親染色体集団に対してこの処理を

NP =2 回繰り返すことによって，新たな世代の政策集団を形成する．

4. 3 政策選択の学習 − Q()-learning

各サブエージェントは，遺伝的に保持している政策

Q()-learningを使用する．

0

0

gi

0

れで動作している時間は異なるが，サブエージェント

4. 3. 1 政 策 選 択

DRGA では，各サブエージェントにおいて政策学習に強化学習を用いる．一般的な強化学習は行動学習手DRGA では政策の学習に用いる．DRGA
で使用する強化学習アルゴリズムは Q()-learning である．DRGA での Q 値は各政策の評価値であり，政策テーブルで表現する．通常の Q テーブルでの状態が政策テーブルではサブエージェントに相当し，Q テー
法であるが，

1
R
giの得た報酬の総計である． は割引率，は学習率で，共に 0 <= <= 1，0 <= <= 1 である．
0
Q (gi ; pi ) は eligibility traces（ 2.2 節注１参照）を用いた場合の目指すべき Q 値であり， (0 <=  <= 1) はの制御が移ることを カウントとしている． iはサブエージェントeligibility traces を用いる程度を表す定数である．
学習の更新は i = I; I 1; ::; 2; 1 の順に計算する．
0

I はエージェントがタスクを行い，その終了条件（タブルでの各状態における行動が，政策テーブルでは各スク達成またはエージェントのタスクに対する寿命）

サブエージェントにおける政策に相当する．

を満たした時点での時刻である．エージェントが終了

DRGA

では，知覚状態から行動へのマッピングが決定的であるため，あるサブエージェントで政策を選んだ時にサブゴールに到達するかどうかは環境に対して決定的である．
強化学習を行う場合，通常，常に最大Q 値の行動条件を満たすまでを１試行と呼ぶ．式 (4) を計算し式(5) に代入し，Q(gi; pi) を更新する．この時，時刻 I
では Q0 (gI ; pI ) = RI として計算する．
各政策はサブゴ ールに到達するか，タスクを達成するまで，もしくはエージェントの寿命（

MaxStep ）を選択するのではなく，ある程度の探索機能を残しなが尽きるまで継続される．サブゴールに到達すると微がら行動を選択する．選択方策としては確率小な報酬を得て，その時の知覚情報に応じて次のサ

prob で5電子情報通信学会論文誌 'xx/xx Vol. Jxx{D{I No. xx

ブエージェントに切り替わる．タスクを達成すると大The optimal route

きな報酬を得る．寿命が尽きると報酬は得られない．
寿命はエージェントが持っており，１政策で寿命を使

g2 g3

い切る時もあれば，複数の政策で寿命を使い切る時もThe most frequent routeafter learning
g4

g5

ある．

4. 4 DRGA − 全体像
図

5 は DRGA の全体像を示したものである．エーG

ジェントは環境との試行錯誤により得た経験に基づいて強化学習を行い，ある一定の試行数（

SIZET ）を

GA によって進化する．この時，GA における個体表現は DRGA でのサ

g6

終了するとエージェント自体がg1
S

ブエージェント内の政策にあたるため，進化の評価基準である適応度を各政策のQ 値で表現し，GA を用い

図 6 10210 迷路
Fig. 6 10210 maze.

て進化を行う．進化後，政策テーブルの値を初期化して，また新たな政策集合を保持したエージェントが環境に対して試行錯誤を繰り返しタスク達成を目指す．
各政策はサブゴ ールに到達した時に微小な報酬を見せかけが 発生している．知覚的見せかけによりこMDP ではなくなっていて，１サブエージェ

得るので，強化学習によって各サブエージェント内での問題ははサブゴールに到達できる政策の選択確率が高まる．

ントでは解くことができない．例えば，図中に実線でサブゴールに到達できる政策は，環境中である程度の示された最短経路をとる場合，東西に壁がある知覚状

距離を移動していることが多いので，一度もゴールに辿り着いていない段階での探索範囲の拡大に役立つ．

`0101' では，最初に北へ移動（Ｓ→ g4 ），次に南へ移動（ g4 → g6 ），最後に北へ移動（ g6 →Ｇ）しな態

また一度ゴ ールに到達すると大きな報酬が得られる

ければＧには辿り着かない．この問題では，最小で二ので，ゴール到達に役立つ政策は強く強化される．こつのサブゴールを置かなくてはならない．

の強化学習の評価値

Q(g; p) を適応度として GA を

この問題を

DRGA で解く場合，まずＳでは南西に`0011' をスタート情報とするサブ行うので，サブエージェント中では，タスク全体を見壁がある知覚情報て色々な場面で役に立つ政策が次第に優位になってく

エージェントが起動する．このサブエージェントの政(3) によって一つの政策が選択される．
Q 値が 0 なので，全くる．学習初期の段階では，サブエージェント内で政策策集団から式の競合が起こる場合もあるが，学習開始時には全ての政策の行動やサブゴ ールを少しずつ変化させ，環境中では

ランダ ムに選ばれることになる．選ばれた政策のス

競合の起こらない経路を見つけ，強化していくことにタート情報における行動が北進だった場合は実線の方

よって，次第に競合を解消する．そして，各サブエー

向に一マス（ジェントに一つの優位な政策が生き残り学習が収束

向に一マス進む．政策集団を初期化する際に明らかにする．

壁に進む政策は除いているので，ここで南進や西進す

GA の近傍探索能力で4. 5 DRGA 実施例

DRGA の動きを図 6 の 10 10 迷路を使って説明す2

g1 の位置），東進だった場合は破線の方る政策が選ばれることはない．
北進した場合の続きを考える．次に得られる知覚情とであり，そのタスクを達成する経路を獲得すること

DRGA の目的である．エージェントが行えるのは
1 マス移動，東へ 1 マス移動，南へ 1 マス移動，
西へ 1 マス移動」の 4 行動である．エージェントが`0101' で，これに対する現在の政策の行動は北進と南進とこの知覚情報をサブゴールとする場合の 3が通りがあり得る．南進だった場合は再びＳに戻る．政「北へ

策の行動は決定的なので，この政策は「北南北南…」という行動を得られる知覚情報は隣接したグリッドに壁があるかな

とらないまま寿命が尽きる．一方，北進だった場合にいかだけである（図は，北に一マス進み，また同じ知覚情報なので北に一る．タスクは初期位置Ｓから目的地Ｇに到達するこ

1 参照）．この限定された知覚情
16 種類しかなく，知覚的報では得られる知覚種類が

6

報はMaxStep まで繰り返して報酬を受け

g2 の位置に到達す

マス進むというのを繰り返して，

論文／遅れ報酬に基づく遺伝的アルゴリズムによる部分観測マルコフ決定問題の解決手法

Generation Loop
Trial Loop
Agent

New Agent
Subagent

Subagent

Subagent

Policy 0
Policy 1

Policy 0
Policy 1

Policy 0
Policy 1

Policy Np

Policy Np

Policy Np

Genetic Algorithm

Environment

GA operations are
performed in eachsubagent on thebasis of the utilitiesof policies.

Agent behaves catenating its subagents
until arriving at the goal or MaxStep.

Old Agent

No
Yes

Agent gains rewards according
to the result of its behavior.

# of trials> SIZET

Reinforcement Learning
図 5 DRGA 全体像
Fig. 5 Outline of DRGA.

る．ここで得られる知覚情報は`1001' で，これに対表 1 サブゴールまで到達する政策
Table 1 Policies that can reach a subgoal

する行動は南進と東進とこの知覚情報をサブゴ ールとする場合の3 通りがあり得る．南進だった場合には一マス南に戻り，そこでの行動は必ず北進なので，「南北南北…」という行動をMaxStep まで繰り返して報酬を受けとらないまま寿命が尽きる．東進だった
場合にはさらに実線の経路を辿っていくことになる．

政策

南西壁

p1
p2
p3
p4
p5

北進
北進
北進
北進
北進

0011

東西壁

0101
sg
北進
北進
北進
北進

北西壁

南北壁

＊

sg

＊
＊

東進
東進
東進

東進
東進

1001

このように考えると，Ｓから北進する政策のうち

1010
sg

北

壁

1000
＊
＊
＊

sg

北東壁

1100
＊
＊
＊
＊

sg
sg: サブゴール＊: 任意の行動
東進

1 に示す 5 種類で10 種の知覚情報に対しては任意の行動で良い．p1〜p4 はそれぞれ実線上を通って g1〜g4まで，p5 は g4 を通過して g5 まで到達して微小な報汰によって，有効な政策がますます優勢となる．

酬を受けとり，次のサブエージェントに制御を譲る．

を用いることを考える．

このようにサブゴールまで到達できる政策は限られて

Ri = (MaxStep step)2 =10:0(6)
Ri = (observenumber)(7)
step は初期位置からゴ ール 到達までの ステップ 数，
observenumber はサブエージェントがサブゴ ールに

サブゴ ールまで到達するのは，表ある．表にない

いて，微小な報酬によって次第に優勢になってくる．
一つ目のサブゴール以降のサブエージェントやＳから東進した場合も，同様にサブゴールまで到達できる政策が次第に優勢となる．そしてそのような政策の組合せでＧまで到達した時，大きな報酬を受けとり，Q()-learning の報酬の分配によって経路上の全ての政策が強く強化される．Q 値に基づく GA による淘

ここで，ゴ ール到達時の大きな報酬として次の式(6)，サブゴール到達時の微小な報酬として次の式 (7)0

到達するまに知覚した知覚情報の種類数である．同じ知覚状態の観測を続けてもobservenumber は増えず，新しい知覚情報を得た時に，その数をカウント

7電子情報通信学会論文誌 'xx/xx Vol. Jxx{D{I No. xx

し，これをサブゴール到達時の微小報酬とする．

GA の近傍探索能力で行動やサブゴールを少しずつ変1 5 種の政策の場合，サブゴール到達時の報酬は下にいくほど大きくなり，pn に対して n + 1 の報化させ，環境中では競合の起こらない経路を見つけ，酬となる．一方，ゴール到達時の報酬はそれぞれのサ

そして，各サブエージェントに一つの優位な政策が生

ブゴールから最短経路を通ったと仮定すると，き残り，学習が収束する．このように知覚的見せかけ

表 の強化していくことによって，次第に競合を解消する．

p1〜p4を使用した場合は 518:4，p5 を使用した場合は 384:4

がタスク達成の障害となる場合でも，準最適解を見となる．こうして，ゴ ールまでの最短経路上にあり，p4 が最も強化されるこ

つけて知覚の見せかけ問題を回避する機能を持ってかつ長い距離を移動しているいる．

ただし，この最短経路はサブゴールでの知覚的見せできない場合もあり得る．ゴールまでの経路が限られかけによってゴール到達が困難になる経路となっていていて，競合の起こらない経路が存在しない場合など

また，障害となる知覚的見せかけを排除することがとになる．

る．それについては次節で詳述する．

4. 6 DRGA の効果と欠点
前節の10 10 迷路のタスクを例として，DRGA のDRGA では，タス2である．例えば図6 の迷路において，g5 の位置が壁に塞がれている場合がそうである．そのような問題は探索問題としてもともと難しい問題で，スタート地点

本質的な効果と欠点を説明する．

の情報だけではなく，その前後の状態変化に基づいてク達成にとって障害となる知覚的見せかけを排除し，サブエージェントを選ぶような手法が考えられるが，障害とならない場合は逆にうまく利用して，大規模問そのような柔軟な政策の切替えは今後の課題である．

題を複数の類似した小問題に分ける．そのため，必ずしも最適解に収束するとは限らない．

10 10 迷路のタスクでは，図 6 の g4 と g6 の地点
2にサブゴールを置いた実線の経路が最適解（最も報酬の高い経路）である．Ｓとg6 は同じ知覚情報 `0011'

HQ-learning と比較してみると，HQ-learning におMDP に分割することのみが目的であるが，DRGA におけるサブゴール

けるサブゴ ール学習は，問題を学習は，それに加えて，有効な政策がうまく連鎖することも目的としている．そのためにDRGA のサブを持ち，同じサブエージェントが起動する．しかし，ゴール学習は少し制約が大きい．一方，サブゴール間

Ｓでは北進，の政策については，

g6 では東進しなければならないため，

このサブエージェント内では政策の競合が起こり，うまくゴールに到達できないことが多い．それに対し，

g5 と g6 の地点にサブゴールを置いた破線の経路の場
合は，Ｓから g5 までと g6 からＧまでは同じ政策を再利用することが可能で，政策の競合も起こらない．
この場合，ゴールに到達するために二つの政策だけを学習すれば良いので，学習効率も良い．実際，このタDRGA で学習してみたところ，学習収束時に74:8%の高い確率でこの経路が選択された．
この例に示すように，DRGA では有効な政策の再

スクをはDRGA では再利用が可能なので，各々独立に学習する HQ-learning と比較すると学習が非常に効率的である．また，DRGA では，ゴールまでに必要なサブエージェントの数をあらかじめ予想する必要がないという点も利点である．

5. シミュレーション実験
5. 1 タスク (a) − Key and door タスク
5. 1. 1 タスク設定
一つ目の実験として，図7 に示す 26 23 迷路のタ
HQ-learning の元論文 [2]2スクを扱う．このタスクは，利用によって，ゴールまでに必要な政策の数を減らすにおいて挙げられていた最も複雑な問題である．この機能がある．そのため，ゴールまでに多数のサブエー

実験では，このタスクを用いて，ジェント切替えを必要とするタスクに対しても，再利る程度の複雑な問題を用可能な有効な政策を見つけることによって探索空間ことを示す．

HQ-learning で解け
DRGA でも解くことができるに収束しないことが挙げられる．知覚的見せかけが(1) 位置Ｋ(2) 鍵を使ってドア（グレー部分）をくぐり抜けて，(3) Ｇへ到達することである．この迷路においてエージェントが得られる知覚情報は 11障害となる場合，サブエージェント内で政策の競合が種類である．この迷路は鍵を取らないとドアをくぐり起こっている．その場合には，学習の進行とともに，抜けられない．そこで，鍵を持っていることを区別すを制限し，うまく学習することが期待できる．
一方，欠点としては，タスク達成にとって障害となる知覚的見せかけを排除するために，必ずしも最適解8

このタスクは，初期位置Ｓから始まり，にある鍵をとって，

論文／遅れ報酬に基づく遺伝的アルゴリズムによる部分観測マルコフ決定問題の解決手法

K: Key: Door

表 2 各ステップ数の割合 − Key and door タスク
Table 2 Ratio of each step - Key and door task.

One of the optimal routes

No.1
No.2
No.3

K

タスク失敗

DRGA
47.0%(87step)
3.63%(89step)
2.95%(85step)
31.1%(250step)

HQ-learning
40.0%(87step)
21.0%(89step)
8.00%(91step)
8.00%(1000step)[2] より HQ-learning のパラ メー
500，ゴ ー
ルし な い 全 て の 行 動 に 0:1 の 報 酬 を 与え る ．Q
値 更 新に は DRGA の 式 (4), (5) と 同 様 の Q()learning の更新式，HQ 値更新には式 (2) を用いる．
= 1:0;  = 0:9; = 0:05; HQ = 0:1; T = 0:2;
MaxStep = 1000 と定める．Pmaxは最初の試行では0:4 で，最後の試行までに線形的に 0:8 に上昇させる．
; ; Pmaxは Q 値の式と HQ 値の式で共通である．ここで，MaxStep（エ−ジェントの寿命）が DRGA と大きく異なるが，DRGA は行動にランダム性が全くあわせて ，文献

タも載せておく．ゴ ール到達時の報酬を
0SG

図 7 Key and door タスク
Fig. 7 Key and door task.

960 状態存在する．また，Ｇまで
83 ステップ，必要最低サブゴ−ル数はると，全状態数はの最短経路は2 である．従って，政策の再利用の可能性はほとんどない 5）ので，再利用性の効果の検証は行わない．
（注[2] によると，1000 ステップを限界とするランダムウォークでは，20000 試行行って 1 回もゴールに到達することが無かった．また，10000 ステップを限界とするランダムウォークでは，3000 試行行って最短経路は 1174 ステップだった．
文献

5. 1. 2 報酬およびパラメータ設定

報酬は4.5 節で説明したものを用いる．すなわち，(6)，サブゴール到達時には式 (7)

ゴール到達時には式

なく，政策選択時にのみランダ ム性がある．このため，寿命である

MaxStep を多く取る必要性がない．

5. 1. 3 結果 − タスク (a)8HQ-learning のグラフ
8 エージェントシステムで行った実験の結果である．HQ-learning では 60000 試行行っていて，600 試
図 に経路長分布図を示す．

は行毎のゴ ールまでのステップ数の分布を示している．

100 回の実験の平均である．また，実験が終了した時点（ DRGA は 100 世代目，HQ-learning
は最後の 600 試行）での，経路長分布図の最も割合
この実験はを占めたステップ数から上位三つとタスクを失敗しGA に関しては NP = 30; Ne = 4; た割合を表 2 にまとめる．図 8 と表 2 より DRGA，
HQ-learning ともに POMDP を解決し ていると 言
Cp = 0:9; Mp = 0:15 と定める．交叉は 2 点交叉のみえる．
とする．Q()-learning に関しては = 0:7; = 0:15;
5. 1. 4 考察 − タスク (a) = 0:4 とし ，各政策の Q 値の初期値は 0:0 と定め
DRGA，HQ-learning 共に過半数以上がゴ ールにる．行動選択のための温度パラメータ T は 3:0 とす
到達している（学習終了時にゴールに到達出来なかっる．全体に関しては MaxStep = 250 とし，世代更新た割合がDRGA は 31:1%，HQ-learning は 8:00%）
するための試行回数 SIZET は，初期値を 1000 とし，
POMDP を解決しので，共にこのタスクの難易度の世代ごとに 100 ずつ，7500 まで増加させる．この時ていると言って良い．DRGA では最終的なタスク失の世代は 65 世代目であり，その後の世代では 7500
敗率がかなり大きいが，これは世代更新時に政策テーのままとする．実験終了までの世代数（ generation ）ブルがクリアされ，新しく始まった世代の初期では，は 100 とする．
ランダムに政策が選ばれるので試行の失敗率が高くな
5
ることが一つの原因となっている．しかし，100 回のの報酬を与える．

各パラメータは，（注）：スタート情報とサブゴールが等しい政策はスタートできず役に立たないので，サブゴールの前後の政策は必ず異なる．従って，サブゴールが二つしかない場合は，一つ目の政策と三つ目の政策が等しくなる組合せ以外に政策の再利用の可能性はない．

実験においてタスクを成功させるサブエージェントがDRGA で知形成されなかったケースは一度もなく，

9電子情報通信学会論文誌 'xx/xx Vol. Jxx{D{I No. xx
One of the optimal routes(a) DRGADRGA histogram

percentgoal(%)

G

1
100
0.8
80
0.6
60

*

0.4
40
0.2
20
00
20
40
60

generation

generation

80
100

80

100

120

140

160

180

200

220

240

step

*

step

(b) HQ-learning
8 subagents
HQ-learning 8agent

goal(%)
percent
1
100
0.9

S

0.8
80
0.7
0.6
60

If subgoals are located at ‘‘ ’’s and ‘‘ ’’s, the agent can reuse the policie

*

0.5
0.4
40
0.3

図 9 30225 迷路
Fig. 9 30225 maze.

0.2
20
0.1
00

10

20

30

40

trial(x600)

50

trial(x600)

図8

60

70

80

90

100

0

100

200

300

400

500

600

700

800

900

1000

step

step

経路長分布図 − Key and door タスク

Fig. 8 Histogram of the number of steps to the goal.

知覚状態において最もQ 値の大きい行動を繰り返し選択する可能性が高いのである．このタスクにおいては，全ての行動に微小な負の報酬を与えることによって，さらに直進性を高める工夫をしている．すなわ

覚の見せかけ問題を解決できているといえる．

1000 ステップ まで のランダ ム

このタ スクでは ，20000 試行で一度もゴ ールに到達しなDRGA では 250 ステップ，HQ-learning

ウォークではち，この負の報酬によって，一度もゴールに到達していない段階でも

5. 2 タスク (b) − オリジナル迷路（ 30225 迷路）
5. 2. 1 タスク設定

かったのに，
でも1000 ステップの試行を繰り返すことで適切な政

二つ目の実験として，先程の策が獲得できている．これは，行動のランダム性を制限して，直進性を高めているためだと考えられる．

Q 値の差が出てきて，Q 値の大きい行動を繰り返す可能性が高まるのである．

Key and door タスク

よりも難易度の高いオリジナル迷路を作成した（ 図このようにゴールまでに多くのステップ数を必要と9）．このタスクを用いて，DRGA の有効性，すなわするタスクでは，学習の開始時点において全くのラン

ち有効な政策の再利用によって，大規模な部分観測マ

ダムウォークでは同じ場所を繰り返し探索してなかな

ルコフ決定問題が解けることを示す．

か探索範囲を広げられないし，万が一ゴールに到達しても，ゴールまでのステップ数が多すぎてうまく報酬

この迷路は30 25 の大きさでタスク (a) の 26 23
22の迷路よりも広いが，鍵，ド アなどが 無いため状態(a) が 状態数 960
551 である．しを分配することができない．エージェントに直進性を空間としては小さくなる．タスク

持たせると，探索範囲が広がりやすく，探索効率が良だったのに対して，この迷路は状態数くなると期待できる．

かし，

DRGA は各知覚状態に対する行動を固定している

DRGA や HQ-learning にとっての難易度とはゴールまでに必要なサブエージェントの数と経路の長5.2.3 節参照）．このタスク

ので直進性が非常に高い手法であり，このようなゴーさに主に依存している（

ルまでの経路が長いタスクを解く場合に有効である．

は知覚の見せかけ問題がタスク達成の妨げになる部分

HQ-learning も，2.2 節で述べたようにタスク終了時
Q 値の更新を行うことによって，行動の直進性を高めている．すなわち，このようなオフライ

5 か所ある．すなわち，サブエージェントの切替え
4 回行わなくてはならない．最短経路は
131 ステップである．従って，タスク (a) よりもかな

ン更新では，試行中にり難易度が高い．

に一括して

10

Q 値に変化がないので，同じ

が

を最低でも

論文／遅れ報酬に基づく遺伝的アルゴリズムによる部分観測マルコフ決定問題の解決手法

サブエージェントの冗長性が低くなり（表DRGA histogram

1 の＊のように任意の行動で良い知覚状態が少なくなる），行動

percentgoal(%)の学習が困難になる点もタスクの難易度を増す．

1100(b) は M = 5; lmin = 131 とど ちらも大き(a)（ M = 3; lmin = 83）と比較すると，かなり難易度が高い．しかし DRGA では，学習後のこのタスクの失敗率は 18:8%と，タスク (a) と比較し
タスク

0.8
80
0.6
60

く，タスク

0.4
40
0.2
20
00

240

20

220
200

40
generation

generation

図 10ても小さくなっている．これは，スタート情報に基づ

180

60

160

80

step

step

140
100

120

くサブエージェント選択によって政策の再利用を行っ

DRGA では，図 9 の×と＊にサているためである．

経路長分布図 − 30225 迷路（ DRGA ）ブゴールを置くことによって，×でスタートする政策

Fig. 10 Histogram of the number of steps to the goal.

と＊（およびＳ）でスタートする政策の二つの政策の表3(416 16)5

各ステップ数の割合 − 30225 迷路（ DRGA ）みでゴ ールすることができる．従って，

No.1
No.2
No.3
タスク失敗

2

の探索空間を，実質 (416 2 16)2 まで限定して解くことができる．タスク (a) の探索空間は (416 2 16)3でTable 3 Ratio of each step - DRGA.
DRGA
24.0%(145step)
18.2%(131step)
9.73%(155step)
18.8%(250step)あり，この差がタスク失敗率の逆転現象につながっている．少し恣意的な迷路構造ともいえるが，迷路構造に関して何のアプリオリな知識も与えておらず，(416 16)2の探索空間は環境との試行錯誤した結果
2

5. 2. 2 結果 - タスク (b)(a) と 同じ 報 酬や パ ラ メー タを 用 い て ，DRGA に この タ スクを 学習させた ．図 10 に 経路
長分布図を示す．この図もタスク (a) の図 8 と同様に 100 回の実験の平均である．また，表 3 に実験が終了した時点（ 100 世代目）での，経路長分布図の最タスク

うまくサブゴールを配置することで得られたものであDRGA では環境に応じてサブエージェントを決る．

定する適応性によって，このような大規模な問題を簡単にして扱う機能がある．

lminが大きくなったことによる (1),(2) の問題点は(1) に関しては，DRGA の行動の250 ステップの避けられないが，も割合を占めたステップ 数から上位三つとタスクを高い直進性によって，このタスクでも失敗した割合を示す．図

行動の繰り返しでうまくゴールを発見することができ10 と表 3 により，DRGA は十分にこのタスクの POMDP を解決していると言える．100 世代目のエージェントではタスクを達成できない試行が 18:8%に過ぎず，この値は世代更新すると適応度，Q 値がクリアされることを考えると，十分な成績であると言える．

DRGA のように，不完全知覚の迷路問題を MDPに分割して解く手法では，学習空間は ( A jOj O )M
j

j

2j

j

A は行動の種類数， Ojjj

M はゴ ールまでに必要なサブ
エージェントの数である． A ; O は定数なので，このうち重要なのは M である．また，タスクの難易度には，ゴールまでの最短経路の長さ（ lmin ）も大きく
は知覚情報の種類数，j

HQ-learning との比較
比較のために，HQ-learning でもこの 30 25 のオ
5. 2. 42

リジナル迷路のタスクを学習させてみた．報酬とパ(a) と同じとしたが，サブ
16 で設定した．このタスクでは，
ゴ ールまでに最低 5 個のサブエ−ジェントが必要であり，16 という数は多少余裕を持たせるためである．
HQ-learning においてサブエージェント 数を増やす
ラメータに関してはタスク

5. 2. 3 考察 − タスク (b)の大きさを持つ．ただし，j

ている．

j j

j

エージェント 数はと，タスクに対する適応力は高くなるが，サブエー
ジェントの数だけQ テーブルが存在するので，学習
DRGA ではサブエージェンの収束時間が増加する．

トの切替え数をあらかじめ定める必要はないので，こ関係している．ゴールまでの経路が長いと，当然，必のような適応性と収束時間のトレードオフを考慮する

要なサブエージェントの数も増える傾向があり，さら必要はない．

に，

図 11 に 経路長分布図を 示す．HQ-learning では(1) 最初に偶然にゴールに到達するのが非常に困(2) サブゴ ール間の経路も長くなって， 120000 試行行っていて，600 試行毎のゴ ールまでの難になる点，

11電子情報通信学会論文誌 'xx/xx Vol. Jxx{D{I No. xx

まく政策の再利用を行って，探索空間を限定すること"hq-30x25-ave-final.line"

でタスク

percent(b) のような大規模な問題を解決することが

できた．

1
100
0.9
0.8

6. む す び

80

0.7
0.6

60

0.5
0.4

40

本論文では，部分観測マルコフ決定問題において

0.3
0.2

20

0.1
00

20

40

60

80

100

trial(x600)

図 11

120

140

160

180

200

100

200

300

400

500

600

700

800

900

1000

step

経路長分布図 − 30225 迷路（ HQ-learning ）Fig. 11 Histogram of the number of steps to the goal.

色々な場面で同一の小問題がたくさん現れるようなDRGA を提案した．DRGA は，遅れ報酬に基づく GA と強化学習の組合せで，サブ問題を対象として，

ゴ ールの配置の学習とサブゴ ール間の行動政策の学

DRGA では，タスク全体を見て問習を同時に行う．
題を

表4

各ステップ数の割合 − 30225 迷路（ HQ-learning ）Table 4 Ratio of each step - HQ-learning.
No.1
No.2
No.3
タスク失敗

HQ-learning
4.00%(161step)
4.00%(164step)
3.00%(153step)
71.0%(1000step)(a)
100 回の実験の平均である．また，表MDP に分割しながら，色々な場面で役に立つ政策が生き残り，再利用可能な場面を見つけてそれらの有効な政策を適用していくことによって大規模な部分
観測マルコフ決定問題に対応する．シミュレーション
実験を通して，従来の同様な

POMDP をサブタスクに分割して解く手法では解けなかった大規模な問題をDRGA が解けることを示した．
DRGA では，政策を適用するかど うかの判断を，

ステップ数の分布を示している．この図もタスク

スタート地点の知覚情報に基づいて行っている．そのの図 と同様にため，スタート地点の知覚的見せかけによって解けな

8

4 に最後の 600 試行の，経路長分布図の最も割合を占めたステップ数から上位三つとタスクを失敗した割合を示す．

図 11 と表 4 により，HQ-learning はこのタスクのPOMDP を解決しているとは言い難い．120000 試行の段階で行動のステップ数としては合計 10661 万ス
テップであり，DRGA の 100 世代までの合計 9701 万
ステップと比較しても，十分に長時間学習しているといえる．図11 で，まだタスク失敗率が線形的に減少いような問題も存在する．スタート地点の知覚的見せかけが回避できないことが判断できた場合には，その前後の状態変化など別の指標に切替えて知覚的見せかけを回避するのが望ましい．そのような柔軟な政策のDRGA で扱える
POMDP は，分割すれば MDP となるものだけであ

切替えは今後の課題である．また，

る．今後，実問題として，そのような性質を持つものに本手法を適用することを目指している．
謝辞 なお，本研究の一部は文部省科学研究費基盤B 2

しているように見えるのは，行動のランダム性を線形研究（ ）（ ）課題番号的に減少させていることが主な原因であると考えられわれた．

る．実は，この実験は初め，タスク(a) と同じ 60000

試行で行ったのだが，この時も同様にタスク失敗率は
線形的に減少し，最終的には

67:0% だった．試行数
71:0%と改善がを倍に増やして再実験を行った結果が見られないので，これ以上試行数を増やしても，大きな性能の向上は期待できない．

HQ-learning では政策の再利用を行っていないの(b) の探索空間は (416 16)5のままであり，タスク (a)（ (416 16)3 ）と比較するとかなり大きい．HQ-learning でタスク (a) が解けたのに対して
タスク (b) が解けなかったのは，難易度通りの結果といえる．それに対し提案手法である DRGA では，う
で，タスク

2

2

12

文

11480078 の援助によって行
献[1] S. D. Whitehead and D. H. Ballard, \Learning to perceive and act by trial and error," Machine Learning,vol.7, pp.45{83, 1991.
[2] M. Wiering and J. Schmidhuber, \HQ-learning,"
Adaptive Behavior, vol.6, no.2, pp.219{246, 1997.
[3] C. J. C. H. Watkins and P. Dayan, \Technical note:
Q-learning," Machine Learning, vol.8, pp.279{292,1992.
[4] L.-J. Lin, Reinforcement Learning for Robots Using
Neural Networks, PhD thesis, Carnegie Mellon University, Pittsburgh, 1993.
[5] R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction, The MIT Press, Cambridge,
1998.

論文／遅れ報酬に基づく遺伝的アルゴリズムによる部分観測マルコフ決定問題の解決手法[6] D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley,
1989.
[7] J. Peng and R. Williams, \Incremental multi-step
Q-learning," Machine Learning, vol.22, pp.283{290,1996.
[8] S. D. Whitehead and D. H. Ballard, \Active perception and reinforcement learning," Proc. of 7th International Conference on Machine Learning, pp.162{
169, 1990.
（ 平成年月日受付，月日再受付）

山城啓秀

平 10 大阪教育大学・教・情報卒，平 12
奈良先端科学技術大学院大学・情報科学研
究科修士課程了．同年三洋電機入社．在学
中は人工知能，とりわけ強化学習，遺伝的アルゴ リズムの研究に従事．

上野敦志

平 3 東京大学工学部航空学科卒業．平 8 同
大学院航空宇宙工学専攻博士課程単位取得退学．同年，奈良先端科学技術大学院大学情報科学研究科助手，現在に至る．博士（工学）．ロ
ボットの学習，自律システムの研究に従事．人
工知能学会会員

武田英明 （ 正員）

昭 61 東京大学・工卒，平 3 東京大学大学
院工学系研究科博士課程修了．財団法人日本システム開発研究所嘱託研究員，ノルウエー
工科大学 Postdoctoral Fellow，奈良先端科
学技術大学院大学院助手，助教授を経て現在
国立情報学研究所知能システム研究系助教授．
工学博士．知的 CAD ，人工知能，設計学の研究に従事．人工知能学会，電子情報通信学会，日本ロボット学会，精密工学会，AAAI各会員．人工知能学会誌編集委員．電子情報通信学会論文誌編集委員．

13