強化学習と決定木による汎用 エージェントの構成の試み 理学部 数理情報科学科 本田研究室 黄 嵩 学籍番号：B003G025k 発表の流れ ・本研究の背景 ・本研究の目的 ・エージェントの行動様式の学習法 ・強化学習 ・決定木 ・エージェント汎用ルールの習得実験 ・問題設定と前提条件 ・強化学習の結果 ・決定木による汎用ルールのマイニング ・実験Demo ・結論と課題 研究の背景 エージェント（Agent)：環境を知覚し、自分の内部には行 動規範を持ち、それに従って、自律的に行動する知的シス テム。 センサ群 単純エージェント 認識 静的に、変化しない エージェント 環境 新環境 (行動規範) 行動 ? 報酬 学習エージェント 動的に、更新される 問題点： 強化学習によって得られた行動ルールは必 ずしも新しい環境に適用できるとは限らない 強化学習 探査的な行動を行い、目的に沿った行動をした時に報酬を与 え、報酬によって行動規範を改善していく 本研究の目的 ・強化学習と決定木による汎用エージェントの構成 強化学習 環境１ Ａｇｅｎｔ 環境2 行動 環境 クラス 属性 決定木学習 汎用Ａｇｅｎｔ 環境３ 汎用ルール 強化学習 ・報酬に基づいて行動規範を学習する 例：Q学習 知覚 st 環境 s Ａｇｅｎｔ Ｑ（ｓ，ａ） 行動 at 方策 π 報酬 ｒt t:ステップ 行動価値 関数 Ｍａｘ選択 ε-greedy選択 Q(st,at)=Q(st,at)+α(rt+γr’t+1-Q(st,at)) 学習率 割引度 Ｍａｘ選択： 最大の行動価値を持つ行動arg maxa Q(s, a) を選択する ε-greedy選択： 確率εでランダムな行動を選択し、それ以外は，最大の 行動価値を持つ行動arg maxa Q(s, a) を選択する 決定木による汎用ルールのマイニング 決定木とは： データ項目間の関係を木構造で 表示する分析手法 （葉：クラス 根、節：条件式） 行動 環境 決定木学習アルゴリズム Ｃ４．５（Ｑｕｉｎｌａｎ，１９９３） 条件式１ No Yes クラス3 条件式2 Yes クラス1 S S1 エントロピー (データ集合（S）内のクラス分布の乱雑さの指標) Ｈ（Ｓ）=－∑pj log pj(j：クラス、 pj：クラスｊの出現確率) No クラス2 S2 汎用ルール 相互情報量ゲイン率 (分割の効率の指標) Gain＝Ｈ（Ｓ）－（｜Ｓ１｜*Ｈ（Ｓ１）＋｜Ｓ２｜＊Ｈ（Ｓ２））／｜Ｓ｜ 分割前 分割後 分割テストの際に、相互情報量ゲイン率を最大化する条件式を選択 しながら木構造を成長させることによって、最適な決定木を学習 エージェント汎用ルールの習得実験 問題設定 2次元空間内で、壁に沿って時計回りするエージェント 環境：座標 行動：上、下、左、右のいずれかへ移動 孤立した障害物、幅が1になる通路は存在しないと仮定 強化学習の手法 報酬（ｒ）： 0 (case1 & case2の時) ＝ －1 (それ以外の時) Case1 ←A Case2 ←A 動線の左に壁が存在 角から壁上に戻り、かつ動線の 左に壁が存在 ・方策：Max選択、ε－greedy選択｛ε=0.1, 0.3, 0.5, 0.7｝ ・エピソード数：150 ・1エピソードのステップ数：1000 強化学習の学習結果 エピソード：１ エピソード：150 ε－greedy選択（ε=0.5） 赤：報酬0 緑：報酬-1 決定木の学習に使用するデータ(強化学習によりサンプリング) 強化学習の結果からMax選択 で取得 a=argmax Q(s,a) 左上 左 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1：壁 0：通路 環境 左下 上 下 右上 1 1 0 1 1 0 1 0 1 1 0 1 1 0 0 0 1 0 1 0 1 1 0 1 1 0 0 0 ・ 属性 ・ ・ 行動 右 右下 0 0 rightward 0 1 upward 0 0 rightward 0 0 upward 0 1 upward 0 0 rightward 0 0 upward サンプル数：１４７ C4.5に投入 クラス C4.5によって形成された決定木（汎用ルール） 左 エラー率：40％ 周りに壁がない場合を除く エラー率：０％ 下 0 0 左下 0 1 右 0 右上 0 1 上 0 下移動 右移動 1 上移動 右移動 0 1 左移動 1 下移動 1 上 左移動 右下 0 1 上移動 1：壁 0：通路 1 右移動 汎用ルールの異なる環境への適用実験 学習に用いたマップ 新しいマップ（環境） 結論 ・強化学習の結果から汎用ルールを決定木として習得し、汎用 エージェントを構成する枠組みを提示した ・壁に沿って時計回りに移動するエージェントの学習に適用し、 その有効性を確認した 課題 ・難しい或は現実的な問題に対する適用性の追及 ・強化学習の学習法の変更（Profit Sharingなど)によって、汎用 エージェント構成の検証 強化学習とエージェントの関係 機械学習の1つである強化学習は，報酬を利用して方策を 最適化することで，エージェントを環境に適応させることを 目的とする．強化学習エージェントが得た知識を利用して， 方策を改善する手法を提案する． 動的計画法（DP） 最適方策を計算するためのアルゴリズムであり、環境の完全なモデ ルがマルコフ決定過程(MDP)として与えられている場合に適用できる。 マルコフ決定過程（MDP) 行動の決定が現在の状態の観察のみに基づく過程 Vπ0 I 方策評価： E π0 E π１ E Vπ１ 方策改善： I I π2 E ・・・ I π* E V＊ モンテカルロ法 ・モンテカルロ法は、サンプル収益を平均化することに基づいて 強化学習問題を解く方法である。 ・モンテカルロ法は環境の完全な知識を仮定しない、経験 (experience)のみを必要とする。 制御：一般化方策反復(GPI) 評価 Q Qπ π Q π greedy(Q) 改善 目的 本研究 強化学習と決定木によるエージェント 汎用行動ルールの習得 目的 ・強化学習による学習エージェントの構成 ・決定木によるエージェント汎用行動ルールの習得 ・行動ルールの汎用性についての検証 学習エージェントとは 通常のエージェント 目的に沿った行動をするようにルールを作りこむ 学習するエージェント 経験に基づいて自律的に行動規範を見つける 振る舞いを改善できない 学習しないエージェント 経験に基づいて 振る舞いを改善できる 学習するエージェント 強化学習 ・報酬に基づいて行動規範を学習する ・各行為の推定価値を元に試行錯誤を通じて自立的に学習する 強化学習の構成要素 方策（policy): （π） ある時点での学習エージェントの振舞い方を定義する。 報酬関数（reward function): (r) 強化学習問題において目標を定義する。 価値関数（value functions): (Q;V) 最終的に何が良いのかを指定する。 モデル（model）： 環境の挙動を模倣するような何かである。 TD制御(時間的差分学習；Temporal Difference Learning) 環境のダイナミクスのモデルを用いずに、経験から直接学習することができ、 最終結果を待たずに、他の推定値の学習結果を一部利用し、推定値を更新する。 ①Sarsa：方策オン型TD制御(St,at,rt+1,st+1,at+1) s:状態 a:行動 r:報酬 t:時刻 最初に状態価値関数ではなく、行動価値関数を学習するよう ②Q学習：方策オフ型TD制御 1ステップQ学習 学習で獲得される行動価値関数Qは、使われている方策とは独 立にQ＊(最適行動価値関数)を直接近似する left(0) lowerleft(0) lowerleft(1) leftward right(0) upperright(1) rightward upperright(0) down(0) upperleft(0) lowerright(0) leftward right(1) lowerright(1) down(0) downward upperleft(1) up(0) down(1) upward leftward downward 図 up(1) down(1) leftward left(1) up(0) up(1) rightward upward rightward オールゼロ属性を含まない場合の決定木 Q-learning ・現在の状態における行動の評価値を学習 Q(st,at) Q(st,at)+α[r(t+1)+γmaxQ(st+1,at+1)-Q(st,at)] at+1 αの割合で近づける ように更新 rt r(t+1)+γmaxQ(st+1,at+1) Q(ｓｔ,at) maxQ(st+1,at+1) 状態Sｔ＋１ 状態Sｔ 報 酬 rt Q：行動価値関数 α：学習率 γ：割引率 遷移先の状態における行動で 最大のQ値を持つものを探す Q-learningのアルゴリズム ・ Q(s, a) を任意に初期化 ・ 各エピソードに対して繰り返し： ・ s を初期化 ・ エピソードの各ステップに対して繰り返し： ・ Q から導かれる方策(例えばQ に対するεgreedy 方策) を使って， s での行動a を選択する ・ 行動a を取り，r，sｔ＋１を観察する ・ Q(s, a) ← Q(s, a) + α[r + γ maxaQ(sｔ＋１, aｔ＋１) − Q(s, a)] ・ s ← sｔ＋１ ・ s が終端状態ならば繰り返しを終了 強化学習の結果 各エピソードにおける報酬の合計 100 0 -100 -200 -300 Max選択 ε＝0.5 -400 -500 -600 -700 -800 -900 0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 エピソード数
© Copyright 2024 ExpyDoc
