計測自動制御学会東北支部第1丁9回研究集会（1998．1ユ．14）
資料番号179−10

非マルコフ環境におけるラベリングq一挙習Labelingq−LearningFbrPartial1yObservableMarkoYDecision

Pro亡eSS Environment○季梅軒−，釜谷博行■−，阿部健一■OHaeYbonLee−，HiroyukiKamaFa−−，KeIlichiAbe■♯東北大学大学院工学研究科，＊♯八戸高専＊SchoolofEngineering，TbhokuUniversi七y，掴HachinoheNationalCollegeofTe血nology
キーワード＝ 馴ヒ学習匝壷血相氾皿tLe町ning），マルコフ環境〔Ma血vDeci写i皿Pm亡閣E肌iro皿皿e叫，非マル
コ7環境（Pa山北yOb祀rⅧbleM札止。VDe亡i由nPr∝eS6Envimn皿組t），ラペリングq一字習（L且be山皿苫Q−Le皿i皿g），
連縮先＝ 〒閑恥鮎79 仙台市青葉区荒巻字青葉05東北大学大学院工学研究科電気・通信工学専攻阿部研究室

事海所」T組＝（02瑚1丁・TOT4．Fax・＝（02印63・9298．8皿扇1：J●OnO轟b＝仁Oi．t血山m．ac．jp

1． はじめに
近年、規模の大きい複雑なシステムの計画、制御問題を、複数の処理要素（あるいは、そ九白身ある程度自律したものの意味で、処理主体（AGEⅣT）と呼ぶことができる）によって、分散的に解決する仕組みに多くの研究者が関心を寄せている．本研究では、非マルコフ環境（POMDP：P訂tiallyObsemble
MarkovDedsionProce5S）における強化学習を処理

Fig．1削ヒ学習の枠組

費薫とする分散学習アルゴリズムを捏案し、その学習性能を実証する．

よって試行錯誤偶に行動選択を改変する．この改変の仕組みに削ヒ学習（R⊥：Rei止rc亡memtLeamhg）

2．強化学習が用いられる．ここで、環埴のある状態でのある行動に対する瞬時のRew町dをもとに、その最終日学習者（Agent）がある状腰（状況，State）である行標である、Rewdの累積値の最大化をはかるよう動をとると、環境からの刺激入力を受け取る．そ行動選択の仕方をうまく改変しなければならない．の刺激入力を報酬（R叩即d）と呼ぷ．Agen上の目標は、そのRewardの累積値を最大にする事である．
Agen＝土、乱標達成のために、環境との相互作用に−1−

3．MDPにぉける強化学習

3．三 代表的な学習アルゴリズム

まず、＃散マルコフ決定過程（De8CreteMark肝環境が未知のとき、学習によってq値を逐次的Ded5io血Proce88＝MDP、以下MDP）下の削ヒ学習に推定するアルゴリズムが必要である．代表的なを考える．MDPでは入出力変数の値域には離散

アルゴリズムにはQ−1earningl）とその原型となる値、取壊の性質にはマルコ7性を促克する，時間TernporalDi鮎rence法（TD法）望）がある．TD法はは環境認識、行動選択、実行を一つの由pとして、MDP環境の各状態の評価を同定するのに対し、q−難敵イヒされる．Rewardはs血訂圭であり、行動は

1earn血gは状腰の評価だけではな〈、状憩と行動の離散的に選ばれる．Rew甜dに応じた実行可能な行対の評価を割引期待氏eward呑もとに同定する．

動はルールとLて記述さ九る．各環境の観測に対
1）q一学習1）

し、選択すべきルールを与える関数を政策（Po鮎y）と呼び、単位行動当りの期待獲得報酬を最大化す

Q（恥叫）← Q（叫可＋叶亡＋るPol王cyを最適政策（0【心m山Po駄y）と呼且

7ma文句（勘＋l，d）■ 〔l一旬（軸叫】（4）

3．1MDPの学習問題
別ちロ）← Q（叩）MDPは碑填状憩の有限集合∫、行動の有限集合（払f山Ij≠dtO川≠叫）Aによって特徴付けられる．ある時点f∈r＝2）TD仙S町叫入）2）

IO，1，2，．‥1において、環境状腰が勘∈∫のとき、推定のみに使うのをTDといい、行動選択を伴Agentが行勅勘∈Aをとったとすると、Rewardr

う場合をSamaと呼んでいる．

を受け取り（Rewardr土は確率♪r（両町叫で得られる）、環境状熟ま遷移確率Pr（勘＋1l恥可でつぎ別印）一 別叩）＋叶 十佃（利十l湖＋1）の状潜句＋1に推移する．Age血の目標はRewardの割−Q（妬叫）】e（∂声）（5）

引期待利得β（∑芸。7h‡（0≦T≦1）を最大にす（血d18，□Jることである一環壕が既知のときは、DP（Dynami亡Pro許弧1mi喝）が適用できて、次式で解くことがで

ただし、e（叩）：eli由bilitytraceきる．

eligibil王tytraceの更新は次の通りである．

8（8f酋〕← 小e（妬ロー）＋1（6）

e〔古，り ← 7叫叩）

（7）Ⅴ〔印），q（町可を以下のように定義する．

匝Ⅰ・山lき≠jtO一皿≠dl）

Ⅴ（β）＝鷲器【rご＋7∑pr（拙叫′（用1）■lq（叫 ＝「ご＋7∑pr（柵dⅣ〔8′）（2）

また、eli由bilitytraceの変形とも言える■Jr言

reph血古け誠eが撞案さ九ている耳4）＝且工rl右αI＝⇒ 町〕＝聖Ⅹ帥，ロ）（3】

亡（軸句）ト1〔3）式を満たすⅤ、あるいはqを求めれば、最適政即一求まる・q（叩）をq値と呼ぶことにする．

e（叩）← 7ユe〔叩）（払r山1β≠j−Or8≠叫）−2−

3．3 行動の選択

でのA＄entのEr席もRewardの割引期待利得の最大化である．ただし、Agen＝ま各時点で、そのときの行動の選択のルールとしては次のようなものが状倭を知ることはできす、朝測情報のみが与えらある．

れる．そのため、POMDPの間違状況をin亡Omplete1）Greedy

perception，hiddenstateと呼ぶことがある．
□t＝昭讐Ⅹ帥t，□）（10）

4．3 代表的学習アルゴリズム
2）∈一Gredy1）MDPのアルゴリズムをそのまま用いた方法与）勘 ＝ 町g一丁㌘q（恥ヰ＝1一∈の確率か1）

通常のMDPのR⊥をPOMDPに適用する方法□f ＝＝ ra皿domsele亡tion（Eの確率）（12）である．ある種のクラスのPOMDPに有効に連用できるが、問題によってはゴールへの到

3）Bo帖man分布による方法

達を学習できないこともある，

行動叫を選択する確率を2）Recu汀entq壷aming￠）
eq（■・】d）／T∑咤β帥・困／T（13）

q一億をrecurrentneuralnetworkによって学習する方法で、過去の観測、行動の系列でq・値

T：温度係数と呼ぼれる正のパラメータを予測する構造になっている．
3）Eq・Le血ng（Ⅱi町祉C址山Learning）丁）4．POMDPにおける強化学習

POMDPな環境において、いくつかのsubgoal

4・1部分観測マルコフ決定過程（POMDP）のためのQ−leamingを用意し、当面の畠ub郡山

部分裡制マルコフ決定過眉は、不十分虻センサに応じてQJe乱mingを切替える方法である．
4）Cl購鮎r8yStem軋叶1叫のため状態朝潮に不確実性や不完全性の存在するシステムのモデルとして掛＝遺している．POMDP

Ho肋ndに上って提唱与れたcla血鮎．5y如mき）

における強化学習の厳密解法は、残念ながら橿端をPOMDPに適用できるように拡張する研究に小きいかあるいは複雑きの小きい間盈を除き、が理々なきれている．代表的なものはWil割叫S．W．

計算量的に実行不可能と考えら九ている．よって、が捷案したZCS9）がある．ZCSではQ−1e肌hg

POMDP環境下での強化学習問題は非常に意欲的と類似のアルゴリズムを用いて、それにメモな課題であると考えられる．

リを付け加えてPOMDPに対処する枠組を与えている．さらには、ZCSの改良バージョンのⅩCS叫も溝美幸れている．

4．2 POMDPの学習問題
POMDPは環境溝直接観測できないことでMDP

5．ラペリングQ一学習と異なる．環境状腰Ⅵ有限集合ぶ、行動の有限集合

5，1 日的Aとさらに観測の有限集合0とによって特徴付けられる・ある時点tにおいて、環境状態が8 ∈∫の以上の背景をもとに、POMDPにおける強化学

とき、Agentは確率Pr（8亡l可で観測口上∈0を得る．

習の一つのアルゴリズムとして既存のQ−1e且ming

このとき、Ag蝕tの叫の行動によるRewardrfを受をペースに、環境儲側にラベルを付け加えたラベけ取り、遷移確率で次の状唐勘＋1に推移する．ここ−3−

リングq−1earningを捷案する．A酢ntが∴現在おかGrid・勒rldの一例である．

れた環境を観測し，その上、その各状態にラベルを付け加えることにより、同じ状態観測値も区別できることになり、上り有効な学習を目指す．

5．コ アルゴリズム
POMDPでは、MDPのR上にぉける現場状態βの代りに観測8∈0を考える．〔訓士占の関数）その観Fig．2 Sim山a七iomに使用されたGrid測として、真野の観測値と新たにラベル針を結合させた∂を最終的な観潮と定義する．
2）観測ロ＝ （ロ，郎∈0）（8本8imulationでは、N（NQrth）、S（SouthトE（Ea叫、（14）W（鴨島t）の4方向観測が可能である土う設定

ラベル β∈㊥＝11，2，…，8爪。r†した．それぞれをビット値に認識し、10進数に換算した値をその状態の値とする．

5．3 ラペリングのアルゴリズム

3）行動の選択ラペリングは様々な方法が考えられるが、本研観測した状態値により、壁が存在し行動が不究では以下のょうに改変与せる．

可能な方向と行動可能な方向とに分け、行動舐甜t時点で、すべての観測に対するラベルを0と不可能な方向は選択から取り除く．その後、する．

行動可能な方向から∈一言reedyによって行動の叫叶1）古＝；佃．1）＋1

選択を行う．行動も最大で4方向のみ可青Eで（15）ある．

匝町叫≠8t＋11

叫8叶1〕← 叫．）（16）

6．Simulationの結果（如叫＋1＝8．）
叫叶1） ← 輿亡）

故m血七ion結果をFig．3に示す．Fig．3で、実線は通（17）常のQ一学習、一点斜線はラペリングQ一学習である．

（由一餅（叫十1）く仲川叫佃〕ト 叫叫H）

（18）

ど−greedyに行動選択を持続させた場合、雷の確率で、

匝r町叫1）≧即旬））

その影響が続くのに比べ、英行の途中から（学習がただL、在＝は右辺の値が軋明以上のとき、左辺終了されたと思われる時点）その影響を除く事にの値を♂m。壬と置くことを意味する．

より、酢dyに行動を選択する事になる（Fig．3の実線）・その贈異動率的な学習効果を得ることがで

古．3．1 Simuhtion

きた．

また、試行回数が増すにつれて亡を減少させるl）環境

本研究のsim山ationにはPOMDPの学習問題にと、Fig・4の結果を得る．（ただし、30回のsimuIationによく使われるGrid−Wbrldを用いた．Fig．2はの平均である）

ー4−丁・まとめと今後の課題
八−−−■ l巾如

制限等によって区別する辛ができない、POMDP環境においての削ヒ学習のアルゴリズムとしてラペリングq・学習を提案し、5imuIa七ionを行った．

月亨与E︳↑︳l︼！tm−i点♯

実際には異なる状腰であるが、環境認議能力の勾打UVW＼イh・ノQ ∝0 1叫 柑山 叫 加

なお、今後の課巷として
1）ラペリングq・1earningのアルゴリズムをより

御 伽 働 一l印 加
T▲■

複雑で規模の大きい環境に適用できるようラ

F料ユ ラベリングq学習アルゴリズムのSimu＿ペリングのアルゴリズムを改善する．

1ation結果2）ラペリングq−1emingを実際の移動ロボットに用いて、その実用性を確認する．

参考文献
1）Witki皿輯J・C且弧dDay叫P・：q一血ー血g，Ma一血ineLモ肌jng，印79／加2け992）

2）S山t叫R・S＝L乳mi札gtOpredic七by仙emet血od80ft皿pOrald騰托nce吉，Ma血；胱Lear皿1n苫，VOl・3，

亜町（19日即Fig．ヰ 学習結果

3）10血・J・弧dSingh，5＝UsingEligibilityTra亡e占toFi皿dtheBestMemorylessPolicYinPar七ial）y Ob
sembleMa血vDecisionProc鮎es，ICMLT98

次に、学習の進みを止めた際の学習きれた行動（1998）

4）SiⅡれ5・P・弧15utt叫R，5．：Rd止耶eme皿tLeamngwitlRepla血gEl王gibjlityt【蹴e＄，M心 血i皿eI止血皿g，3刺崩〔199句の傾向はFig．5である．
Fig・5の−は学習され

5）Li皿，⊥祉dMit血ell，T・M∴貼皿触ce皿entlea血g Wi払出dd

各gridにぉける耶叫方向を意味する．

ensta七郎−Pro亡地軸gortbeSecondIn＿ternalion乱ICo血仙亡eO皿Simu山元nofAdaptiYe
B血aYior（1992）

句Lin，L・：Rdn貼ceme扇Lea∫ning鈷rRob咄Using Ⅳ
細山Ⅳet甘口rk占，Pb・Dth鶴i6，CarnegieMellon
U山ver軸，Pi帖burg血亡19呵7）M肌凸WjeringむIdJ茹rgen s血midbuber：HQ−
k訂ning，Adaptive8ebaYior6＝2H9叩

B川011a叫J且＝鋸hptat血i且Ⅳeural弧dArti貼山Sy8血8，U血ersiけof山一i亡hig弧Pre6拍nnArbor（1975）

9）Wilmn，S・W∴ZCS＝且ZerOthleYel。．dercla戚航e，
野呂temEⅦⅠ雨血叩C白mpulatio山，2，日射19叫

10＝血血・P・L■＝ Solving pr￠blem5i皿Partヱ叫Fig・古 学習後の行動の傾向

Oh紺Ⅶble E皿Yironment with ClaBSi鮎r SY8・
teJnS；ExperimezL七島 On Adding Mem叩・Lo
XC5，Te血血山epDrtⅣ〔1g97）−5−