POMDP 環境下での強化学習と GA の融合手法の提案

A Hybrid Method of Reinforcement Learning and Genetic Algorithm
for POMDP Environment
山城 啓秀

Yoshihide Yamashiro

上野 敦志

Atsushi Ueno

武田 英明

Hedeaki Takeda

奈良先端科学技術大学院大学 情報科学研究科

Graduate School of Information Science,
Nara Institute of Science and Technology (NAIST)

Abstract

Reinforcement learning methods usually assume the environments in which the Markov property
holds. But, an agent can not perceive states completely when the Markov property does not hold. Anagent observes di erent states for the same ones when it causes perceptual aliasing. It is dicult foran agent to solve the task in such environment. This research proposes a new method called Delayed
Reward-based Genetic Algorithm (DRGA) to solve POMDP (partially observable Markov decisionproblem) with perceptual aliasing. DRGA divides POMDP into multiple subtasks by decomposing
an agent into multi subagents. Each agent learns appropriate policy series for tting environment byusing delayed reward. The policy is evolved with GA based on delayed reward obtained through thelearning.

1 はじめに割し，知覚の見せかけ問題がタスク達成に影響を与える前に別のサブエージェントに制御を渡

強化学習はマルコフ決定過程 (Malkov decsion

す．このような分割によって各サブエージェント

process, MDP) を対象とすることが多いが、エーは問題を MDP として扱うことができ、全体とジェントが知覚できる情報は不十分なことが多して POMDP を解決する．それぞれのサブタス

い．このような知覚の見せかけ問題 (perceptual

クにサブゴールを設定し，分割されたサブエーaliasing) などの問題が生じる部分観測マルコフ

ジェントはサブゴールに到達することを目的と決定問題 (partially observable Markov decisionする．サブゴールの必要性は，知覚の見せかけ

problem, POMDP) 環境下ではエージェントが問題のために一つのエージェントでタスクを解現状態を正確に知ることは不可能で、MDP を対くのが困難なためであり，タスクをサブタスク象としたアルゴ リズムでは十分な学習結果が得に分解することで，タスクの難易度を下げる効られなくなる．

果がある．このようにエージェントをサブゴー

しかし，エージェントはタスク遂行することルを持ったサブエージェントに分割することで，に関しては，環境を完全に知る必要はなく，タス

POMDP を解決する手法として遅れ報酬に基づク達成のための環境モデルをエージェント内部く遺伝的アルゴリズム (Delayed Reward-basedに構築できれば良い．こういった観点から本研究

Genetic Algorithm, DRGA) を開発した．

はエージェントを複数のサブエージェントに分POMDP を対象とした強化学習システムであエージェント

Q-TABLE 11000

サブエージェント 1

S3 S4 S51001 1010 1100

0001

0100
0010

HQ-TABLE 1

TRANSFERCONTROL

S2

S60101

0101

S1

S7

Q-TABLE

0111

0111

｜O｜×｜A｜ map

サブゴールにたどり着いたら次のエージェントへコントロールを渡す
Q-TABLE 2

サブエージェント 2

HQ-TABLE 2

HQ-TABLE｜O｜×1 map

TRANSFERCONTROL

各グリッドに壁がある場合の入力

エージェントが得る観測値

図 1: グリッド 環境での知覚の見せかけ問題

各エージェントの行動政策を決定するのに使用

各エージェントのサブゴールを決定するのに使用

現在行動しているエージェント
Q-TABLE m

サブエージェント m

る HQ-learning[5] との比較実験を通して DRGA

最終エージェントはQ-tableだけ持つが有効な手法であることを示す．

2 POMDP2.1 知覚の見せかけ問題
知覚の見せかけ問題とは，不十分な知覚によって複数の異なる状態を同じ状態として知覚してしまうために起きる問題である．
グリッド 環境を使用し知覚の見せかけ問題の例を紹介する．エージェントの知覚能力はグリッド 環境で隣接したグリッドに壁があるかないか

図 2: HQ-learninig − サブエージェント構成図
ブルは知覚と行動の組合せである jO j 2 jAj のＱ
値テーブルで，ＨＱテーブルは各知覚状態のサブゴールとしての適切さの評価値で、jOj 2 1 のＨＱ値テーブルである．ここで，jOj はエージェントが知覚できる情報の種類数，jAj はエージェントが行える行動の種類数である．このようなだけを知覚できるものとする．その場合，エーエージェントの構成により，HQ-learning 異なる

ジェントは図 1のような知覚入力を得る．図 1にサブエージェントでの Q テーブルによる状態 !

おいて，エージェントは S1 と S7 状態，S2 と S6

行動を学習することで知覚の見せかけ問題を解状態ではそれぞれ同じ知覚入力を得るため，ど決している．

ちらの状態であるかを知ることはできない．このように環境がマルコフ性でもエージェントの知覚能力によって POMDP を引き起こしてしまっ

3 DRGA
本章では，DRGA の実現方法について説明すている．

る．DRGA は HQ-learning のエ−ジェント構成

2.2 HQ-learningに着想を得，その欠点を補い，より効果的なアしたアルゴ リズムである．POMDP として問題

3.1 表現方法

HQ-learning は Q-learning[4] を階層的に拡張とされている知覚の見せかけ問題を解くことをルゴリズムの設計を目指した．

3.1.1 コード 化 (encoding/decoding)

対象としている．部分観測をおこす問題で，サエージェントの知覚情報に対しての決定的なブゴールをおくことで，タスクをサブタスクに行動政策が GA においての遺伝子によって形成分割し，各サブタスクに対して Q-learning を用される．つまり，エージェントにおいて行動とはいて学習する枠組である．図 2に HQ-learning で先天的行動であり，行動系列とその行動系列ののエージェントの構成図を示す．

目標 (サブゴール) を合わせてエージェントにおエージェントは複数のサブエージェントによっける政策と呼ぶことにする．以後，政策と表現て構成され，サブエージェント 1 からサブエーするものは政策：知覚集合 ! 行動 + サブゴー

ジェント m まで順番に制御が移って行く．制御

ル情報のことを指す．

が移るタイミングは各々のサブエージェントが自一つの政策を 1 染色体として表現し，染色体身のサブゴールに到達したときである．Ｑテーにはサブゴ−ル情報と知覚!行動が遺伝的に記エージェント
サブゴール0

サブゴール
0000
0001

知覚情報(0,1,...15)
115’0’or’1’群0群1群M政策 0-0
政策 0-1
政策 0-2

政策 1-0
政策 1-1
政策 1-2

政策 M-0
政策 M-1
政策 M-236 bit
行動
図1に示す
表現

00011011a0a1a2a3

行動が4種類の場合は2ビットになりそれぞれの行動に割り当てる

政策 m-i1111

図 4: 群と集団

図 3: decording − genotype to phenotype
述されている．例えばエージェントの動作種類するサブエージェントが決定され，選ばれた群が A 種で知覚できる知覚種類が M 個であれば，内で政策を選別する．

1 遺伝子で3.1.3 進化手順

AM M 種類の組み合わせを持つこ2とになる．

m : 群番号i : 政策番号GA では一般的にまず個体が環境に対し行動

GA ではコード 化の設定が問題の解く性能をなどを起こし，環境からの評価として適応度を左右することが多い．そのため問題タスク依存得る．この適応度をもとに集団に対して選択・淘でコード 化をするのが望ましい．DRGA ではバ汰が行われ，生き残った個体集団に対して交叉イナリーコーディングを使用している．図 3でそなどの GA オペレータが施される．の手法について図示する．

DRGA では GA 処理 (選択・淘汰，GA オペレータ) は群内で行い，異なる群間での GA 処理

3.1.2 エージェントと群は行わない．Goldberg[1] によると GA は build-

エージェント内部は複数の群によって分けら

ingblock hypothesis によって集団 (複数点) を適れ，各群は複数の政策で構成される．政策は遺応度の高い集団 (結果的に 1 点) にもっていく性伝子によって表現されている染色体である．図 4

質があるという．このため，全ての群を一緒にしはサブエージェント＝群の説明を示したエージェて GA 処理を行うとサブエージェントでなく一ントの構成図である．

つのエージェントとなるため，一つのサブタス各群は初期位置 (サブゴ ール到達時の初期知クしか解けなくなる．したがって異なる群間で覚情報) を同じ くする政策の集合である．HQ-の GA 処理は行わない．GA 処理として行うのlearning アルゴ リズムがはサブエージェントのは以下のもので，全ての群で同様に行う．

順列固定のため，エージェントが観測した状態



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

系列でサブゴール系列を学習する．このため，途

交叉・・・・・・・・・1〜3 点交叉



突然変異・・・文字列変換 (ランダム)

中にサブゴールを置くと学習が破綻する．これを改善するために，DRGA ではサブエージェン
ト (群) の形成は，ある特定のサブエージェントが動き出す場面 (知覚情報) を記憶すること (サブエージェントの初期知覚情報を固定) で環境により頑強に対応する群形成となっている．サブ
ゴ ールの数は知覚情報の種類数と同じ数となる

ため，群数 M はサブゴールの種類数と同等数と通常 GA で用いる適応度関数と違い，DRGAで用いる適応度関数は遅れ報酬に基づいた評価値を使用して表現する (3.3節参照)．

3.2 遅れ報酬に基づく学習

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

先天的行動から ，適切な 政策を 選択するためなる．すなわち，サブゴール到達時に，その到に後天的学習を行う．この後天的学習に Q()-達したサブゴールの知覚情報によって次に行動

learning[2][3] を使用する．

Q-Table
状態

Policy-Table
群行動

おける政策 p の評価値であり，Q 値と記すことにする．T は政策を選ぶランダム率を調整する温度パラメータである．

3.2.2 学習更新式

政策lにおいて群 glで政策 plを選択し，報酬 rlが得らQ 値の更新には Q( )-learning を用いる．時刻

図 5: 学習テーブル表現

れた時にシステムが Q 値を更新する式を以下の

式 (2)，式 (3) に記す，ここで l はサブエージェ

ントの推移系列をあらわす離散時間である．サ

3.2.1 政策選択
DRGA では，各サブエージェントにおいて政策選択に強化学習を用いる．一般的な強化学習
は行動選択手法であるが，DRGA では政策の選択に用いる．DRGA で使用する強化学習アルゴ

リズムは Q()-learning である．DRGA での Q値を Policy 0 Table(政策テーブル ) と呼ぶと，図 5のように Q-Table と比較ができる．
Ｑテーブルでの状態は政策テーブルでは群を表し，Ｑテーブルで状態に対する行動とは，政策テーブルでは群に対する政策を表す．群内には複数の政策がありその政策種類がＱテーブルでの状態内の行動種類に相当する．政策を選択した時，知覚 ! 行動が決定的であるため，ある群で政策を選んだ時にサブゴールに到達するかど うかが暗に決定している．すなわち，ある群で任意の政策を選択したときの次の群は群の初期位置に対して決定的である．
強化学習を行う場合，ある程度の探索確率を残さなくてはならないため，行動の選択時に学習によって得た評価値によって各行動の選択確率を決定する．選択方策としては確率 p で最大の評価値を持った行動を選び，確率 (1 0 p) でランダムに選択する方法や，ボルツマン分布を使って行動を決定する方法など 様々なものがある．DRGA で用いている方策はボルツマン分布

ブエージェントのそれぞれで動作している時間は異なるが，サブエージェントの制御が移ることを 1 カウントとしている．

Rl = rl + [(1 ) max
q2P Q(gl ; q) + Rl ] (2)0+1+1Q(gl ; pl ) + Rl (3)は割引率， は学習率で，共に 0<< 1,0<<1 である．Rl はエリジビリティを表す．
はエリジビリティとユーティリティのトレードオフの割合で 0<  <1 である．
学習の更新は L; L 1; ::; 2; 1 の順に計算する．
L はエージェントがタスクを行い，その終了条件
Q(gl ; pl )(1 0)0(タスク達成またはエージェントのタスクに対する寿命) を満たした時点での時刻である．式 (2)を計算し式 (3) に代入し，Q(gl ; pl ) を更新する．
この時，時刻 L では RL = rL として計算する．
各政策はサブゴ ールに到達するか，タスクを達成するまで，もしくはエージェントの寿命が尽きるまで継続される．サブゴールに到達すると微小な報酬を得る．タスクを達成すると大きな報酬を得，その時の知覚状態に応じて次のサブエージェントに切りかわる．寿命が尽きると報酬は得られない．寿命はエージェントが持っており，1 政策で寿命を使い切るときもあれば，複数の政策で寿命を使い切るときもある．に基づく選択である．

Q g;p =Tprobability(p g) = P e eQ g;p =T(1)
q 2P
P は群内の政策集合を表す．gは群，p は群内の政策を示す．probability (p g) は群 gで，群内政策 p が選ばれる確率を示す．Q(g; p) は群 gに
(j)

(j)

3.3 DRGA 全体像

図 6は DRGA の全体像を示したものである．

エージェントは環境との試行錯誤により得た経験に基づいて強化学習を行い，ある一定の試行数が終了するとエージェント自体が GA によって進化する．この時，GA においての個体表現は

generation loop
trial loop*
エージェント

新しいエージェント

サブエージェント

サブエージェント

サブエージェント

政策0
政策1

政策0
政策1

政策0
政策1

政策m

政策m

政策m

部 分 観 測 迷 路で ，ＳからＧまでの経路の 走破 ． こ の迷路での最短経路
は 28 ステップ．＊，＃ は政策の再利用可能なサブゴ ールの位置

G#
適応度による
エージェントの進化を行なう

環境
S

進化

エージェントが環境中で適切な行動を獲得するために試行錯誤に行動を行なう

エージェントがそれまでに得た経験をもとに適応度を算出

図 7: 10x10 迷路

環境に適した行動は報酬を得る

今までのエージェント’average.line’

percentgoal(%)

No1Yes

世代更新のための一定の試行数が終了

0.80.6

1試行ごとにエージェントが得た経験を強化していく

図 6: DRGA 全体像

0.40.20010203040generation

DRGA での群内の政策にあたるため，進化の評価基準である適応度関数を図 5の政策テーブルの値で表現し GA を用いて進化を行う．進化後，今までの政策が変化するので政策テーブルの値を初期化する．そして，また新たな政策を保持したエージェントが環境に対して試行錯誤を繰り返しタスク達成を目指す．

4 シミュレーション実験

4.1 タスク − 10x10 迷路

5060generation

70809010030405060708090100

stepstep

図 8: 10x10 迷路 実験結果 − ヒストグラム
次に下へ移動，最後に上へ移動しなければＧにはたどり着かない．そのため DRGA(HQ-learningも同様) では最低でも 2 回のサブエ−ジェントの切り替えが必要となる．

4.2 結果 − 10x10 迷路

図 8は図 7の迷路を DRGA で解かせた結果でまず，図 7に示す単純な部分観測迷路で実験をある．各 generation 軸中の試行が何ステップで行った．この迷路は HQ-learning の著者が用意

タスクを達成したかの割合を高さで示す．最終したもので，タスクは初期位置Ｓから目的地Ｇ世代である 100 世代中では 38 ステップが一番多への経路を発見することである．エージェントがく試行の約 74%が 38 ステップを占めていること行えるのは上下左右への 1 グリッド 移動する 4 行になる．タスクを達成出来なかったものはステッ動である．エージェントが得られる知覚情報は図プ 100 の約 13%であることを示している．

1に示したような隣接したグリッドに壁があるか

HQ-learning では，サブエージェントの順序系ないかだけである．この限定された知覚情報では列に基づいて学習を行うため，サブエージェン得られる知覚種類が 16 種類しかない．そのため

トが最低 3 つ必要である．DRGA では順序系列

ＳからＧの経路中に同じ観測値で違った行動をに基づいた学習ではなく，サブエージェントが推とらなくてはならない箇所が存在する．例えば，移する時，次のサブエージェントは知覚情報に左右のみ壁である知覚入力では最初，上へ移動，応じて選ばれる．このため，同じ政策を再利用

G

DRGA histogram

DRGA

percentgoal(%)
＊
10.8×
＊

0.6
0.4

状態数：

551×0.2

最短経路：

00
220
200

40131step

S

240

20
180

60

generation

generation

160

80

step

step

140
100120

図 9: 30x25 迷路

HQ-learning
16subagent
HQ-learning 16agent

goal(%)
percent1することが可能である．例えば図 7の迷路であれ

0.9
0.80.7ば，最初に右へ移動して行き，1 つめのサブゴー

0.60.5ルを一番右端の' ＊' に置く．次のサブゴールは0.40.30.2

Ｓと同じ知覚情報となる' ＃' に置くと，最初に0.100

選択した政策を再利用しＧへたどり着くことが1020304050trial(x600)可能であり，サブエージェントが 2 つでゴ ール

60trial(x600)

708090100100200300

400500600

700

800

900

1000

stepstepにたどり着くことが可能になる．この場合，群の中で競合が起こらないので，DRGA が見つけ

図 10: 30x25 迷路 実験結果 − ヒストグラムやすい経路となるためこの経路 (38 ステップ ) の5 おわりに占有率が高い．

4.3 タスク − 30x25 迷路
次に，さらに難しい問題を用いて，DRGA とHQ-leraning の比較を行った．図 9に著者が作った迷路を示す．DRGA や HQ-learning にとっての難易度とはサブエージェントの切りかわり回数と経路の長さである．このタスクは知覚の見せかけ問題がタスク達成の妨げになる部分が 5 か所ある．すなわち，サブエージェントの切りかえを最低でも 4 回行わなくてはならない．図上の'＊' と ' ×' は DRGA が政策の再利用可能なサブDRGA は HQ-learning と違い 1 ステップごとの行動にランダム性が含まれず，決定的に行動するため，長い経路でも効率良くタスクをサブタスクに分割することができれば，十分に POMDPを解決できることが分かった．また，DRGA は政策の再利用を行うことで，タスクの難易度を下げ HQ-learning よりも良い結果を残すことができた．

参考文献
[1]

ゴールの位置である．

4.4 結果 − 30x25 迷路[2]績であると言える．

Peng,J.

:Ecient

Memory-Based

Dynamic

Pro-Proceedings of the 12th International Conference on Machine Learning, pp.438-446 , 1995.

[3]

Peng, J. and Williams, R. :Incremental multi-step Qlearning,[4]Machine Learning, 22, pp.283-290 , 1996.

Watkins, C.J.C.H.,and Dayan, P. :Q-learning,chine Learninig

Ma-, 8, pp.279-292 , 1992.

18.8%に過ぎず，この値は世代更新すると適応度，Ｑ値がクリアされることを考えると，十分な成,graming

タスクを解くことに失敗しているといえる．100
世代目の実験結果ではタスクを解けないものがAddison-Wesley

1989.

比較実験の結果を図 10に示す．この図より
DRGA はタスクを解いているが，HQ-learning はGoldberg, D.E. :Genetic Algorithms in Search, Optimizetion, and Machine Learning,[5]Wiering,M.

andAdaptive Behavior

Schmidhuber,J.

:HQ-Learning,, Vol. 6, No. 2 , 1997.