pptx

2009/11/24
先端論文紹介ゼミ
山口大学大学院理工学研究科
M1 兼平龍
1
紹介論文
「A strategy for improving performance of Qlearning with prediction information(2006)」
“予測情報でQ-学習のパフォーマンスを
向上させるための戦略”
Choonghyeon Lee Kyungeun Cho *Kyhyun Um
Dept. of Game & Multimedia Engineering
Dongguk University, Seoul, Korea
* Corresponding Author
2
Abstract/１．Introduction

エージェントに学習させ、ゲーム環境に対応させ
るためには多くの時間がかかってしまう…
本論文では…
 学習速度をあげるため予測モジュールに基づいた
第２の報酬によるQ値の更新方法のアルゴリズム
を提案.
 その結果、シミュレーションにおいて平均して9%の
効率化をもたらし性能の向上に成功した.
3
2．Related works


強化学習は周りの環境を入力を基に行動を決定
します.その行動から生じる報酬の価値を蓄えそ
の状態での価値を使って行動を選択します.
最近では、学習速度を速めるために様々な研究
が行われています。
4
2．Related works
2.1 Function Approximation Method for Q-learning
 関数近似法(Fuzzy Q-Map)を用いて次元の呪い（状態空間の爆
発）を回避し、学習速度をはやめる方法（文献[5]）.
 Fuzzy Q-Mapではファジー集合の（中心でのQ値,行動）といった2
次元テーブルで構成され、距離やあいまいな定数などの多次元
の入力は様々な集合に属することになります.
2次元テーブル上では、
列の数:[ユーザによって指定された集合の数]
行の数:[状態空間の遷移可能な行動の数]
5
2．Related works
2.2 A Reinforcement Learning Using the Complex System Network
 実世界のような状態数が拡大された場合、関数近似法では学習
パラメータの数は指数関数的に増加してしまい、次元の呪いが
起こってしまう.
 発達するネットワークに用いることで問題が拡大されたとしても
ネットワークのサイズは増大せず、問題複雑さもサイズによって
増加しないためこの問題を回避することが出来ます（文献[6]）.
 本論文のように強化学習の効率を高めることを目的とし、環境
または状態が与えられるとき、全アルゴリズムはその状態での
ネットワークをふさわしくするために更新します。
6
3．A Q-learning Method Using Predictive
Information


本論文の提案では強化学習自体の構造を変えずに、既
存の学習アルゴリズムに予測情報計算モジュールを組
み込むことによって実現します.
学習はエージェントが現在の環境状態の中で最高の結
果を得るために必要となる.
強化学習アルゴリズムは、現在の状
態の下で最適な行動（政策）を計算し
ます。報酬価値を政策決定に反映す
ることによってエージェントは最も良
い動作を選択するようになります。
（例：オンラインFPSゲームでの状態：場所、数、タイプと避難所の方向、敵の位置、・・・)
7
3.1 A Basic Structure of Q-learning Using
Predictive Information
①予測情報を求めるため、Q-学習アル
ゴリズムにおいてQ-テーブルの正の報
酬価値を更新するとき参照します。
Q値の更新・テーブル保存
Q値による行動決定
②正の報酬の価値が得られる行動は、
予測情報を計算する予測モジュールの
P-テーブルに保存されます。
③P-テーブルおいて最も高い頻度によ
る行動は、通常の更新とは別に正の報
酬を得る行動として更新されます。
図1 予測情報を用いたQ学習の基本構造
8
3.2 Computation of Predictive Information


正の報酬が得られるとき予測モジュールでは、各々の状態での行動の頻度を
予測するために状態ごとの行動をP-テーブルで保存します。
P-テーブルに格納された動作の中で、予測モジュールは動作としての最も高
い頻度がある行動を指定し、第2の報酬(正の報酬)により更新します。
図2 P-テーブル例
Status1・3 :[指定された行動が1である場合は、第2の報酬を受ける行動と認められます]
Status2 :[2つ以上の行動ならば、信頼性が減少することから第2の報酬は得られません]

P-テーブルスペースのサイズが大きすぎると処理時間・メモリがかかり、小さ
すぎると予測の信頼性が低下してしまうため問題に合わせた適当なサイズが
望ましい。
9
3.3 The Learning Algorithm Using the P-table
for(each a’ in s’):新状態での各行動について行う
{


第2の報酬によるQ値の更新
r2 = Prediction(Q(s’,a’)) ; (s’,a’)での最大頻度の行動
Q(s,a) += α * (r2 + γ * best - Q(s,a)) ;
通常のQ値の更新
if ( Q(s`,a`) > best ) best = Q(s`,a`);次状態の最大Q値
Q(s,a) += α * (r + γ * best ? Q(s,a)) ;
}
10
4. Experiment and Analysis

迷路問題
①サイズとして縦横25マス計625のフ
10の異なるマップ（障害の位置の違
い）を使います。
②マップは1つのスタート地点、1つの
ゴール地点、1人のエージェントと壁で
組織されています。
③Q-学習法と比較するために、1つのス
クリーンで2つ同じマップを配置しました。
図3 シミュレーションのスクリーンレイアウト
④エージェントは上、下、左、右、静止
と行動でき、ゴール地点への到着した
時、その時間に基づき行動の結果の
報酬価値を定めました。
[Best Rec:最短ステップ数,Avg Rec:平均ステップ数,Learning Count:到達回数Map Level:マップの種類,Time Count:試行回数] 11
4.2 Experimental procedures



迷路問題では、各々のエージェントはフィー
ルドの出発点から出発して、同じ環境と同じ
状況の下で到着点に最も短い経路を見つ
けます.
マップ上でエージェントは現在の場所情報と
周囲の壁に関する情報を分析し、繰り返し
行動することで学習します.
ゴールへの到達回数、プロセスの間での学
習速度で性能評価します.
図4 実験の結果を示しているスクリーンフォーマット
[左端の赤数字:ステップ回数]
12
4.3 Experimental Results and Analysis

Learning count (到達回数)の比較
⇒中盤以降に差が開き、性能ではQ学
習法と比較して提案手法は平均して
9%改善した。
図5 ゴールへの到達回数の比較
横軸でのLevelは100,000ステップ[(5000＝500ステップ×10マップ)×20試行]ごと
13
4.3 Experimental Results and Analysis

Path length (到達ステップ数平均)の比較
⇒図5と類似した結果になった。
図6 平均ステップ数の比較
この理由として、第2の報酬でのQ値を受けた行動が信頼性を成し遂げる時間を必
要とします。つまり、P-テーブルは特定の価値を統計データを作るために保存します。
よって、全てのP-テーブルの統計データを完全な形で反映し第2の報酬でQ値を更新
するのには時間がかかる。
14
4.3 Experimental Results and Analysis

Path length (最短ステップ数)の比較
⇒最短ステップはあまり変わらない
図7 最短ステップ数の比較
最短ステップ数ではランダムに行動しても、より早く着くルートを見つけることは
可能です。しかも特定のステップ以後にも類似した結果を与えるため、最短ステッ
プ数が２つの方法の性能評価に影響を及ぼさないことが判明した。
15
5.Conclusions



本論文では、Q-学習アルゴリズムに基づく予測情報を使
い、学習速度を向上させる方法を提案します。
提案手法では、シミュレーション結果に平均して9%の性
能改善に成功したが信頼できる第2のQ-価値を生成する
まで時間を必要とします。
メモリと計算コストを考えて、予測モジュールを設計しな
ければならず、今後の課題となっている。
16

Download Report