1. 本章では, 強化学習の中の2つの手法SarsaとQ-learningを用いて強化学習から行動規範を学習し, その結果から環境とエージェントがとる行動をサンプリングして決定木学習をおこない, 汎用行動ルールを決定木として構成する方法について述べる。この方法を実際に簡単なエージェント移動問題に適用し, その有効性を議論する。
図4.1にその概要を示す。
図4.1 強化学習と決定木による汎用エージェント構成の概略
Agentは, 環境1である目的に対して, 強化学習によって, 行動と環境の関係を学習します。行動を分類すべきクラスとし, 環境を属性として, その対応関係を決定木学習によって, 汎用ルールとして形成する。そして, この汎用ルールを使って, 異なる環境にも適用する新たな汎用Agentを構成する。
4.1 実験の問題設定－壁に沿い時計回りに移動するエージェント
今回の実験は, 壁に沿い時計回りに移動するエージェントの設計とする。2次元のグリッド状空間内に壁に沿った障害物が設定され, エージェントは任意の位置から放浪し, 最後に壁に沿い時計回りに移動するものとする。
エージェントは, 1ステップ後に上下左右いずれかにその方向に壁がなければ1グリッド進む, という行動をとることができるものとする。また, エージェントの観測する環境は2次元空間内の座標とする。なお, 問題の単純化のため, 壁から遊離した障害物や, 幅１の壁は存在しないものとする。
なお空間のマップは以下の21×21の2種類を使用した。図4.2のマップで, 強化学習を使って学習する。そして, 習得した行動ルールを使って, 図4.3のマップに適用し, 汎用性を検証する。
図4.2 マップ1(学習用) 図4.3 マップ２（検証用）
4.2 手法
4.2.1 強化学習による行動様式のサンプリング
強化学習によって, SarsaとQ-learning両方使って, 実行してみた。学習の効果を, 各エピソードの報酬合計のエピソードに対する変化として示すと, 図4.4のようになる。
図4.4 Sarsa & Q-learning
最大のエピソード数は150回に設定し, トレース減衰パラメータλを0.9に設定した。以上のサンプリングから見るとSarsaもQ-learningも今回の実験において, 大きな差異は出てなかったので, 両方とも, 今回の実験に学習手法として適用できるとわかった。そして, 以下の実験も比較必要性がないと考え, すべてQ-learningを用いて, 実験を行った。
4.2.1.1 学習アルゴリズム
本実験の強化学習には予備実験の結果, Q(λ)を選択し, 使用した。Q(λ)アルゴリズムは前章の表3.5に示したとおりである。λは予備実験の結果λ=0.9を選択し, 学習率はα=0.1とした。また, 方策にはMax選択とε-greedy選択の2種類を使用した。これは, この問題において, 探索の比重がどの程度重要であるか不明であり, 試行錯誤が必要であると判断したためである。なお, ε-greedy選択の場合, ε={0.1, 0.3, 0.5, 0.7}の4ケースを検討した。
4.2.1.2 報酬の設定
この問題の目的はエージェントに, 壁に沿い時計回りするような行動を学習させるということである。よって報酬関数は以下のように与えた。
時計回りとは動線の左に壁があるという状態を意味する。よって図4.5のようにエージェントがあらかじめ壁上にいた場合は, 次に行動を取ったときに動線の左に壁があるときにエージェントに大きな報酬を与える。また, 図4.6のようにエージェントが壁の角上にあるときには, エージェントが壁から離れないように, 上記の条件に加えて次の行動でエージェントが壁上に戻ってきたとき大きな報酬を与えるものとした。今回の実験の報酬関数ｒは式(4.1)のように作成した。灰色のセルは壁, Ａは現在のエージェントの位置, 矢印は動線（現在から次のステップ）を示す
(4.1)
図4.5 報酬を与える場合（case1）
図4.6 報酬を与える場合（case2）
4.2.1.3 決定木の学習に使用するデータのサンプリング
強化学習から得られた環境と行動の関係から決定木学習によって行動ルールを決定木として取得する。決定木学習についてのデータは下記のようにして取得した。
決定木学習に使用する属性は, 強化学習で用いた環境（座標）は異なり, より詳細な環境情報である“8近傍の壁の有無”とした。これをサブ環境と呼ぶことにする。
データのサンプリングには, 空間内でエージェントがとりうるあらゆる環境（座標）を事例とし, サブ環境を属性ベクトルとして取得する。そして, このそれぞれの環境に対し, 強化学習の結果得られた行動価値関数Q(s, a)を参照してmax選択によって示唆される最適な行動(argmaxQ(s, a))をこの事例（環境）に対するクラスとしてサンプリングする。このようにして得られた事例は図4.7のような形式になる。
左上 左 左下 上 下 右上 右 右下
1 1 1 1 0 1 0 0
upward
rightward
upward
upward
rightward
upward
| |
1 1 1 0 1 0 0 1
1 1 1 1 0 1 0 0
1 1 1 0 0 0 0 0
1 1 1 0 1 0 0 1
1 1 1 1 0 1 0 0
1 1 1 0 0 0 0 0
図4.7 決定木の学習に使用するデータ
4.2.2 決定木による汎用ルール形成
図4.7の事例では, 属性が強化学習のエージェントのサブ環境, クラスが行動となっている。よって事例の属性値に対して, クラスを予測するような決定木を構成すれば, 環境に対してとるべき行動を示唆する行動ルールを取得することになる。
4.2.3 汎用ルールによるシミュレーション
このように作成された汎用ルールをエージェントに埋め込み, 学習に用いたマップや少しび違うマップで, エージェントの動作をシミュレートし, そのエラー率から得られた汎用ルールの有効性を評価する。
4.3 実験結果
4.3.1 実験条件
今回の強化学習の実験条件を以下にまとめておく。
表4.1 実験条件のまとめ
|
各項目 |
内容 |
|
目的 |
壁に沿った障害物がある2次元のグリッド状空間において, 壁に沿い時計回りに移動する行動を習得する |
|
環境 |
座標 |
|
行動 |
上, 下, 左, 右のいずれかへ１ステップに１セル移動 |
|
学習アルゴリズム |
Q(λ) |
|
λ係数 |
0.9 |
|
学習係数α |
0.1 |
|
方策 |
Max選択
ε-greedy選択(ε={0.1, 0.3, 0.5, 0.7}} |
|
エピソード数 |
150 |
|
1エピソードのステップ数 |
1000 |
|
初期条件 |
エージェントをマップの左上隅に設置（壁上） |
4.3.2 強化学習の結果
まず方策の学習への影響を評価するため, 図4.8に全ての方策で得られた強化学習の効果をエピソードごとの報酬和の時間変化として示す。
グラフからMax選択の場合は最初急激に報酬和が増加するものの, エピソード回数5回から比較的小さな一定値になってしまい, ある種の局所解に陥ってしまったことがわかる。よってこの問題には探索の要素がかなり重要であるとわかる。
ε-greedy選択の場合は, ε＝0.1, 0.3の時, 学習過程で報酬和に大きな周期的変動が観測され, エージェントは定期的に振り出しに近い状態に戻って, 学習し直しているものと思われる。一方, ε＝0.5, 0.7の場合は安定に学習し, エピソード数50回程度で比較的大きな一定値に達する。この報酬和については, ε－greedy選択で得た報酬和は実際の学習量と違ってランダム選択による報酬の減少があるため, 実際の報酬和（学習の効果）は, 報酬和からランダム選択による効果を取り除いた上で評価する必要があることに注意しなければならない。
図4.8 報酬和の時間的変化
図4.９にランダム選択の効果を取り除いた正味の報酬和の変遷を示す。今回は作業の簡単化のために, greedy選択の場合は学習過程の最後の一回だけをMax選択に変更して報酬和を観測した。エピソード回数は5回おきに150回までの値をサンプリングした。このため, この各プロファイルは同じ学習シークエンスの結果ではないが, 各設定で最終的に達成できる報酬和の特徴という大勢にはあまり影響がないため, 大まかな目安として使用できる。
この図から一番報酬の合計が0に近づいたのは, ε＝0.5の時であった。そのほかの場合は, 探索の効果が大きすぎ, または少なすぎたものと考えられる。よって本研究の以降ではεの値は0.5に固定してε-greedy選択によって実験を行った。
図4.10, 図4.11には, この条件での強化学習による学習の効果をエージェントの移動の様子として示す。図中の赤また緑で示されているセルは, エージェントであり, 赤は最後の行動で報酬0, 緑は報酬-1を得たことを示す。エピソード1の時は, ほとんど学習されていないので, エージェントはデタラメな行動を取っている。エピソードの進行につれ, 徐々に学習の効果が現れ, エピソード150では正しく行動をするようになった。
図4.9 ランダム選択の効果を差し引いた正味の報酬和の時間変化
図4.10 エピソード１のエージェントの行動。白は通路, 灰色は壁, 赤, または緑はエージェントを示し, 赤は最後の行動で報酬０を, 緑は報酬―１を得たことを示す。
図4.11 エピソード150のエージェントの行動。表記は図4.10と同様。
4.3.3 取得された決定木
ε＝0.5のQ（λ）学習の結果から, 4.2．2.3で述べた手法により, 属性ベクトルをサブ環境（エージェント8近傍の壁の有無）, クラスをQ値を最大化として, 決定木学習の入力データとして保存した。この結果, エージェントの周りにまったく壁がない場合も含め, 全273個の事例をサンプリングした（実際のデータは付録Aに示す）。このデータに対してC4.5を適用することにより, サブ環境ととるべき行動の関係を決定木として形成した。
図4.12すべての事例に対して形成された決定木を示す。ここではある片方の枝に長く伸張した, 比較的単純な決定木が得られた。これをエージェントの行動ルールとして使用するには, 根ノードから葉ノードにたどり着くまで, 8近傍の壁の状態に関する条件式をたどることにより, エージェントの行動を決定する。木の深さが高々6でしかも伸張している枝がごく限られていることから, 簡単なIF－THENルール形式でも容易に記述できる。
この決定木の精度について検証すると, エラー率は40％と比較的高くなった。しかし, 詳細に調べると, サンプリングした事例の行動と決定木が示唆する行動が不一致である場合は, いずれも周囲にまったく壁がない状況であった。周囲に壁がない場合は, どちらに動いてもよい（ただし同一方向に移動したほうが壁にたどり着く可能性が高い）ことを考えると, 周囲に壁がない場合の学習データと決定木による予測が示す行動の不一致はむしろ自然であり, エージェントの行動にあまり支障ないと考えられる。
念のため周囲に壁がまったくない事例を除いた上で決定木学習を行うと, 図4.13のような決定木が得られた。図4.12の場合と比べると, 深さは同じだが枝の数が増えて構造が複雑化したが, エラー率0％という非常に正確な学習が行われた。
左
0 1
左下 上
0 1 0 1
下 左移動 上移動 右移動
0 1
右下 左移動
0 1
右 下移動
0 1
右上 下移動
0 1
上 右移動
0 1
上移動 右移動
図4.12 すべての事例に対する学習より得られた決定木
左
0 1
左下 上
0 1 0 1
右 左移動 上移動 右移動
0 1
右上 下
0 1 0 1
左上 右移動 下移動 左移動
0 1
右下 上
0 1 0 1
左移動 下 上移動 右移動
0 1
下移動 左移動
図4.13 周りに壁がない時例を除いた学習から得られた決定木
4.3.4 シミュレーションによる汎用ルールの異なる環境への適用性検査
以上で強化学習の手法の1つ(Q-learning)を用いて, 一種類の環境の中で, 壁に沿って時計回りをするエージェントの行動を学習した。獲得した決定木は汎用ルールとして, 異なる環境にも適用可能であることが期待できる。
よって, 形成された決定木の行動ルールを使用して動く汎用エージェントを作成し, 異なる環境(図4.3 マップ２)での適用性をシミュレーションし検証した。ここで, 使用するエージェントは決定木として形成された汎用行動ルールをIf-then形式で用いた。また, 異なる初期状態での動きも検証するため, エージェントの初期位置はマップの中央に設定して, 検証を行った。
図4.12の決定木に基づくシミュレーションの結果を図4.14, 図4.15で示す。図4.14は, 学習に用いたマップ１(図4.2)に対する実験である。もともと学習時のエラー率が0でるため当然ではあるが正しく行動することを確認した。図4.15は, 少し異なる新しい環境マップ２(図4.3)に対する検証結果である。この図で示されるように, 壁の配置が若干異なる環境でのシミュレーションでも, その違いに影響されず, エージェントは正しく行動することが確認できた。
なお, このマップ以外の複数のマップ, および, 図4.13の決定木を利用した場合も, 例外なく正しい行動を観測することができた。
よって, 今回の問題に対して, 強化学習と決定木によって形成された行動ルールは十分な汎用性を持っており, 汎用エージェントの構成が実現できたことを確認した。
図4.14 学習に用いたマップ1での汎用エージェントの動作シミュレーション結果。表記方法は図4.10同様。
図4.15 新しい環境（マップ2）での汎用エージェントの動作シミュレーション結果。表記方法は図4.10同様。
4.4 議論
ここでは, 本論文の最初に提示した応答－刺激型エージェントSRマリオ（単純エージェント）と, 強化学習によって構成されたエージェント, および強化学習と決定木学習の組み合わせによって構成された汎用エージェントの3種類を比較して議論してみよう。
SRマリオ（単純エージェント）は, センサ3つを持ち, 行動ルールは人工的に取り入れられ, 各状態でセンサへの刺激から行動ルールを参照して, 行動する。このようなエージェントは迅速かつ明確に行動ができ, 情報収集も少なく, 非常にコンパクトである。しかし, 応答－刺激型のエージェントの行動ルールは人間によって作られたもので, 複雑な問題では人間によるルール構成自体が困難となる可能性が高く, その適用性に問題がある。
強化学習のみで構成されたエージェントは状態認識によって学習して自己の行動規範を改善する。すなわち環境モデルに依存せず経験のみから学習できる。しかし, 今回の問題では環境を座標として扱ったため, 壁の状態やグリッドの数が変化すると以前の学習結果を利用することができなくなり, 環境の変化に弱いエージェントになってしまった。
一方, 強化学習と決定木で構成されたエージェントは, 強化学習によって得られた環境（属性ベクトル）と行動（クラス）を事例として決定木学習によって汎用ルールを作る。まず, 強化学習によってエージェントを学習させるので, より複雑な問題でのルール構成に適用性があるといえる。そして, 決定木学習を使って行動ルールを形成したので, SRマリオの行動ルールのようにコンパクト性, かつ汎用性のあるルールを構成できる。よって, 強化学習と決定木学習では, 人間によってルールを構成するが困難な複雑な問題にも適応できかつ環境の変化にも強いエージェントを構成できる可能性がある。
このような比較から, 今回の実験で試みた強化学習と決定木で構成された汎用エージェントは, 応答－刺激型エージェントと強化学習によって構成されたエージェント両方の長所を集めたことがわかった。また, このアプローチは, 構成したいエージェントの目的ははっきりしているものの, 形成すべきルールの見通しが立ちにくい（何を環境とすべきかもはっきりしない）場合に, ステップバイステップでルールを発掘していくのに有効であるといえる。これは, 環境を粗く設定して目的に応じた行動を強化学習で習得させたうえで, さらに環境をサブ環境に分解しながら, 環境と行動の関係をデータマイニング的なアプローチで発掘していく, という手法によって可能になった
ただ, この手法では強化学習で用いた環境が十分なサンプリング環境になっていないと機能しないという問題がありうる。今回の実験では問題が簡単であったため, そのようなケースは観測されなかったが, より複雑な問題では十分予想される。この様な場合には, 複数の強化学習結果の利用や, 反復の導入によってさらに汎用性を確実にすることができるものと考えられるが, 具体的な検証は今後の課題である。
2. まとめ
本論文では, ある程度の汎用性を持ったエージェントの構成のために, 強化学習の結果から決定木学習（C4.5）を用いて汎用ルールを発掘し, これをエージェントの行動規範に埋め込むことにより汎用エージェントを構成することを検討した。
この考えを, 壁にそって障害物が存在する2次元空間内で壁上を時計周りに移動するエージェントの移動問題に適用した。ここで, 環境は座標, 行動は上下左右いずれかへの移動とし, 学習にはQ（λ）を用いて方策にはMax選択とε-greedey選択の両者を使用した。予備的な実験の結果, ε-greedey選択（ε=0.5）で, 150エピソード程度で安定な学習に成功し正しい行動を習得することができた。この強化学習の結果からさらに詳細な環境（8近傍の壁の状態）とそれに対応する行動（Q値からMax選択で決定）を, 属性とクラスのデータとしてサンプリングし, C4.5で学習をおこなった。その結果, 周囲に壁が全くない状況（解不定）をのぞくとエラー率0という精度のよい決定木を得ることができた。この決定木をルールとして埋め込んだ汎用エージェントを他の環境に適用した結果, 異なる環境しかし正しい行動をとることを観測し, このような枠組みが汎用エージェントの構成に有用であることを確認した。
これからの課題としては, 本研究では基本的な問題（Toy model）についての検証にとどまったため, より現実的な問題に対する適用性を探求する必要があると考えられる。さらに異なる強化学習の学習法(Profit Sharingなど)の導入の効果について更に検証したいと考えている。
謝辞
このほどの卒業研究に際して、理学部情報数理科学科、本田 理恵博士の多大なご指導を承りました。また、研究室の研究生達とも協力を頂ました。ここで皆さんに、心から感謝の意を申し上げたいと思います。本当にありがとう御座いました。
参考文献
2 福田 剛志＆森本 康彦＆徳山 豪： データマイニング 共立出版 2001年
3 長尾 確： エージェントの拓く未来， 41巻5号 情報処理，2000年5月
4 小倉 久和＆小高 知宏著： 人工知能システムの構成， 近代科学社， 2001
5 三上 貞芳＆皆川 雅章共訳： 強化学習， 森北出版株式会社，2000年
6 森 紘一郎： 強化学習研究の最新動向調査，2002年度早稲田大学卒業論文
7 J・R・キンラン： AIによるデータ解析, トッパン, 1995年5月
8 J・R・キンラン C4.5プログラムソース
http://www.cse.unsw.edu.au/~quinlan/
9 森 紘一郎 迷路問題プログラム
http://www.yama.info.waseda.ac.jp/~mori/program/maze/maze.html
付録：
A 決定木の学習に使用したデータ・・・・・・・・・・・・・・・・・・・・・・・・ 1
B プログラムリスト：・・・・・・・・・・・・・・・・・・・・・・・・・・・・・ 9
B-1. 問題環境と報酬方法設定のヘッダファイル・・・・・・・・・・・・・・・・・9
B-2. 時計回りするエージェントの行動の強化学習プログラム・・・・・・・・・・ 25
B-3. 汎用ルールによるエージェント移動プログラム・・・・・・・・・・・・・・ 30
