マルチエージェント学習における探査率の進化的更新と全体最適 からの乖離 Updating Method of Exploration Rate and It Deviated From Optimal Rate in Multi-agent Learning 岡野 拓哉 1∗ 野田 五十樹 1,2,3 Takuya Okano1 and Itsuki Noda1,2, 3 1 東京工業大学総合理工学研究科知能システム科学専攻 1 Tokyo Institute of Technology 2 産業技術総合研究所 2 AIST 3 JST,CREST Abstract: We investigate feature of simple evolutionary adaptation of exploration rate in reinforcement learning, and show a evolutionarily-acquired rate will deviate from the optimal rate. Although exploration rate is an important parameter to determine learning ability of learning agents, it is not well known how to choose the rate especially in multiagent and nonstationary environments. We conducted several experiments to adapt exploration ratio in an evolutionary way, and confirmed a result of theoretical analysis of our previous work, in which evolutionarily acquired exploration rate is relatively smaller than its optimal value in the most of conditions. 1 はじめに 本研究ではマルチエージェント学習 (以下、MAL) に おいて、各エージェントが進化的に探査率を更新して いった場合に、全体最適の探査率を獲得できるかにつ いて実験をし考察を行う。 シングルエージェントによる強化学習と同様に、探 査率は MAL の性能を大きく左右する重要なパラメー タである。このパラメータの調整法に関しては、数多 く研究されてきた。[1, 2, 3] 多くの研究はシングルエー ジェントのみを対象にした探査率の調整法や、静的な 環境での調整法などであった。しかし、エージェント 学習を実社会の問題に応用するとした場合には、環境 が動的であり、複数のエージェントによる同時学習の 場合も考慮しなければならない。そのため、動的な環 境下の MAL における探査率の調整法が、必要不可欠 である。ところが、そのような探査率の調整法は未だ に確立していない。 そこで、全体最適の探査率を各エージェントが自律 的に獲得する手法として、各エージェントが進化論的 に探査率を更新した場合に全体最適な探査率を獲得で ∗ 連絡先：東京工業大学 〒 152-8550 東京都目黒区大岡山 2 丁目 12-1, 03-37261111 E-mail: [email protected] きるかどうかが検討されている。 しかし [4] によると全体最適な探査率と、各エージェ ントが進化論的に探査率を更新した際に獲得できる探 査率は異なる可能性があることが指摘されている。 本研究では実際に各エージェントが進化的に探査率 を更新した際の収束値と、全体最適な探査率とが等し くなるかを繰り返し動的資源共有問題を用いて実験を 行い検証した。 2 探査率 探査率は強化学習を行う際に各エージェントの学習 性能を大きく左右する重要なパラメータである。その うえ、マルチエージェント環境下ではこのパラメータ は他のエージェントにも影響を与えるため、様々な効 果を持つパラメータになる。 本稿では、各エージェントは一般的な強化学習 [6] に より学習すると仮定する。強化学習とは、学習エージェ ントが行動を行うたびに報酬を得て、得られる報酬を 最大化するように行動を修正していき最適な行動を学 習するような学習方法である。 探査率は強化学習エージェントが環境の情報を得る ための探査をどの程度行うかを示す 0 から 1 の間の値 を取るパラメータである。このパラメータの値が大き いほど探査を行う割合が多くなり、小さいほど探査を 行う割合は少なくなる。強化学習では、過去の行動に よって得られた知識を元に行動を選択することで、よ り高い報酬を得る。その知識を充実させるために知識 によらない行動、つまり探査をしなければならない。そ のため、強化学習では探査と知識利用の割合を決定す る探査率は非常に重要なパラメータである。 このパラメータは静的環境では、学習開始時には正 の値からはじめ、学習の進行とともに徐々にゼロに収 束させればよいことが知られている。しかし、動的環 境では常に環境が変化するため、このパラメータを 0 に収束させることはできない。探査率は大きすぎると 探索過剰により、エージェントが得られる利得が不 安定になる。 また、小さすぎると探索が足りず局所解 に陥ってしまう危険性がある。そのため、各環境に合 わせてこのパラメータをうまく調整する必要がある。 マルチエージェント環境下での探査率は、その探査 率を持つエージェントの学習過程に影響を与えるだけ でなく、その他のエージェントの学習にも影響を与え る。そのため、よりいっそう調整が困難であり、重要 なパラメータになる。 3 探査率の進化的更新 本研究では MAL の探査率調整法においての進化的 アルゴリズムの有効性を検討するために、単純な進化 的アルゴリズムを用いて実験を行い評価する。先に述 べたように全体最適な探査率の調整は困難である。一 方、マルチエージェント環境下では、エージェント毎 に異なる探査率を持たせることが可能であり、その違 いによる報酬獲得効率の差を使えば、進化的な方法で 探査率を調整していく事が可能となる。 そこで、まず各エージェントが相互に探査率を共有 することにより、全体最適な探査率を獲得する手法を 考える。従って、本研究で用いる MAL では各エージェ ントが自分以外のエージェントの探査率をある条件下 では知ることができること仮定し、進化的に探査率を 更新することとする。 3.1 探査率の均衡点と最適値 [4] では各エージェントが利己的に探査率を更新した 際に収束する均衡点と全体最適の探査率とは異なるこ とが可能性があることが指摘されている。進化的に更 新した探査率も均衡点に近似することが予想され、全 体最適な探査率の分布を獲得できない可能性がある。 本研究では実際に進化的に各エージェントが探査率 を更新した場合に全体最適の探査率を獲得できるかを 実験的に検証する。 3.2 進化的な探査率の更新手順 本実験では基本的な進化的アルゴリズムを用いて各 エージェントが探査率を更新していく。 ゲーム中にある確率で更新するフェーズに入る。 更 新フェーズではトーナメント選択し、突然変異を行う。 具体的な手順は以下の通りである。 1. エージェントをランダムで二人選択する。 2. 平均報酬の高いエージェントの探査率を負けてる エージェントがコピーをする。 3. 各エージェントの探査率にノイズを加える。 上記の操作をエージェント数分繰り返す 4 理想の探査率について 本稿では目指すべき理想の探査率を、全エージェン ト探査率が画一である MAL において最も高い報酬を 得られる探査率とする。 資源配分問題における MAL では、全体最適な探査 率の存在が確認されてる [5]。図 2、図 1 は全エージェ ントの探査率が画一であり、探査率別の MAL の性能 を示したグラフである。x 軸は全エージェントの探査 率、y 軸は全エージェントのゲーム終了後の平均報酬 を示す。図 2 から、上に凸のグラフであり、最も高い 報酬を得ることができるような探査率が存在すること がわかる。その他の設定でも図 1 のように凸の場所は 異なるが上に凸のグラフになることが確認されている。 また、野田は数学的に最適探査率が存在することを示 している [4]。 本研究では厳密な最適な探査率分布は明らかでない ため、各設定における図 2、図 1 のようなグラフの凸 の部分の探査率を目指すべき理想の探査率とする。 5 問題設定 本研究では資源配分問題の一つである動的資源共有 問題を用いて実験をし評価を行う。 1. エージェント ai ∈ A は各々の方策に従って資源 rj ∈ R を選択する。 uniformity.ec0.0001.alf0.1 0.41 0.4 2. エージェント ai は以下の報酬関数 Uj に従って報 酬を得る。 average reward 0.39 0.38 Uj = 0.37 1 1 + totalAgent(rj )/Crj (2) 0.36 totalAgent(rj ) は資源 rj を選択したエージェン ト数である。Uj は totalAgent(rj ) が多くなるに つれて、つまり同じ資源を共有するエージェント 数が多くなるにつれて各エージェントに分配され る報酬が小さくなる。Cj は報酬の減少度合いを 左右する。 0.35 uniformity 0.34 0 0.2 0.4 0.6 0.8 1 exploration 図 1: 環境の変化率が低い設定 3. エージェント ai は得られた報酬を元に自らの報酬 テーブル Vi (rj ) を以下の更新式による更新する。 uniformity.ec0.003.alf0.1 0.45 0.445 0.44 Vi (rj ) = (1 − α)Vi (rj ) + αUj average reward 0.435 (3) 0.43 α は学習率を示す。(i)、(ii)、(iii) を順に繰り返し行い、 最終的な全エージェントの平均報酬により評価を行う。 0.425 0.42 0.415 0.41 uniformity 0.405 0 0.2 0.4 0.6 0.8 1 exploration 図 2: 環境の変化率が高い設定 5.1 図 3: 資源共有問題イメージ図 資源共有問題 資源共有問題とは複数の資源を複数のエージェント で共有するマルチエージェントゲームの一つである。タ イムステップ毎に各エージェントは一つ資源を選択し、 選択した資源に応じて報酬を得る。それを繰り返し行 うゲームである。 各エージェントは強化学習により学習行動を行うの で、利己的に行動をする。各資源のキャパシティとい うパラメータに応じて、適切に配分された時に高い報 酬をエージェントが得ることができる。 資源共有問題 (RRSP) を下記のように定義する。 RRSP = {R, C, A} R = {r1 , r2 , . . . , rn } 5.2 動的資源共有問題 本研究では資源共有問題を実社会の問題に近づける ために、ある一定の確率で資源のキャパシティCj が変 動する「動的資源共有問題」を実験に用いる。 実社会の資源共有問題の多くが動的資源共有問題と いえる。実社会の動的資源共有問題を渋滞問題で例え ると、資源を道路、エージェントを車としてとらえる ことができる。そうした場合、資源である道路は道路 工事などによっていきなり通れなくなる、道幅が狭く なる、広くなるなどの資源のキャパシティが動的に変 化することが考えられる。そのため、本研究では資源 のキャパシティをある一定の確率により変化させる動 的資源共有問題により実験を行う。 C = {Cr1 , Cr2 , . . . , Crn } A = {a1 , a2 , . . . , am } (1) R は資源の集合、A はエージェントの集合を示す。 Cj は資源 j のキャパシティというパラメータである。 また、資源共有問題のゲームの流れを以下に示す。 実験と考察 6 6.1 実験設定 実験設定は以下の通りである。 • ゲーム全体の試行回数:5 回 • エージェント数:200 体 • エージェントの行動選択法 : ϵ-greedy • 資源の初期設定 資源 id キャパシティ(C) 0 5 1 10 2 10 3 15 4 15 5 20 6 35 • 資源のキャパシティの変動：各資源はゲームの一 試行毎にある確率で資源のキャパシティを変化 させる。本実験では、資源の元のキャパシティか ら倍にする、倍になっているキャパシティは元の キャパシティに戻すことでキャパシティを変化さ せる。 • 初期の exploration 率の分布:一様乱数により決定 する 査率が近似していれば、図 5 の equilibrinum=optimun の線状にプロットされる。 図 4 の一番下グラフ、図 5 から、理想の探査率が非 常に小さい設定、つまり追従すべき環境の変化が小さ く、エージェントが探査をあまりする必要のない環境 では、進化的更新により理想の探査率に近い値を獲得 していることがわかる。一方で、理想の探査率が高い 設定、つまり、追従すべき環境の変化率が大きい設定 では、理想の探査率より小さな値を獲得してしまって いる。環境の変化が激しく、探査を頻繁に行う必要が ある設定では、今回のような単純な進化的更新ではう まく探査率を調整できていないことがわかる。 average exploration rate of every time step ec0.0001alf0.1 1 average epsilon standard deviation optimum 0.8 average exploration • ゲームの反復回数:10000 回 0.6 0.4 0.2 • 進化的に探査率を更新するタイミングゲーム一試 行毎に 1%の確率で進化的に更新する。 0 0 1000 6.2.1 5000 6000 7000 8000 9000 10000 average exploration rate of every time step ec0.003alf0.1 1 average epsilon standard deviation optimum 0.8 average exploration 理想の探索率と進化的更新による探査率 4000 (a) • トーナメント選択回数: 200 回 (エージェント数 と同等に設定) 実験結果と考察 3000 cycle • トーナメントサイズ:2 6.2 2000 0.6 0.4 0.2 図 4 はゲーム中の全体エージェントの平均の探査率の 推移を示したグラフである。x 軸はゲームのサイクル、 y 軸は全エージェントの平均の探査率を示す。average epsilon のグラフが optimun のグラフ付近に近似して いけば進化的更新が理想の探査率を獲得できていると いえる。図 4 を見てわかるように、進化的に更新する と理想の探査率以上に、小さく推移してしまっている ことがわかる。 また、図 5 は様々な設定で、理想の探査率と進化的 に更新させた際の最終的な平均の探査率との関係を示 したグラフである。x 軸が理想の探査率、y 軸は進化的 更新により得られた探査率である。 プロットしてある点は各設定においての理想の探査 率と進化的更新により得られた探査率の組である。つま り、各設定での図 4 のようなグラフの optimun の値と average epsilon の最終値の組み合わせである。従って、 各設定での理想の探査率と進化的更新により獲得した探 0 0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 cycle (b) 図 4: 各設定での全エージェントの探査率のゲーム中の 推移。a) 環境の変化率、小。b) 環境の変化率、大 ec0.0001.alf0.1 0.5 (optinum,convergence) optimum = convergence 0.4075 evolution diversity 0.407 0.4065 0.406 averate reward convergence epsilon 0.4 0.3 0.4055 0.405 0.4045 0.404 0.4035 0.403 0.2 0.4025 0.402 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 initial average exploration rate 0.1 (a) ec0.003.alf0.1 0.446 0 0 0.1 0.2 0.3 0.4 0.5 evolution diversity 0.4455 optimal epsilon 0.445 0.4445 averate reward 図 5: 理想の探査率と進化的更新による探査率との関係 0.444 0.4435 0.443 0.4425 6.2.2 進化的に更新させた MAL と更新させない MAL のシステム全体の性能について 0.442 0.4415 0.441 次に進化的に探査率を更新させた MAL の性能につ いて述べる。図 8 は初期の探査率の分布別の進化的更 新を行った MAL と進化的更新を行わなかった MAL の 性能を示している。探査率は一様分布としている。x 座 標が探査率の分布の平均、y 座標が MAL の性能を示し ている。 進化的に探査率を更新させる MAL では初期の探査 率が小さすぎなければ、安定して高い報酬を獲得して いることがわかる。初期値の幅が小さすぎると進化が 追いつかずあまり高い報酬を得ることはできないが、試 行回数を増やすことで改善することが推測できる。従っ て、進化的に更新することで一定の効果があることが わかる。 しかし、必ずしも初期の探査率の分布以上の性能を 獲得できているわけではなく、初期の探査率の分布よ り性能が落ちてしまっている場合もある。図 8 の右のよ うな環境の変化が大きいようなときには多くの場合に おいて元の探査率の分布以下の報酬を獲得してしまっ ている。これは上記に述べたように、高い探査率が必 要な環境下においても比較的小さな探査率を獲得して しまっていることが原因であると考えられる。 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 initial average exploration rate (b) 図 6: 探査率を進化的に更新させた MAL と更新させ なかった MAL の初期の探査率の分布別の性能の比較。 a) 環境の変化が小さい時。b) 環境の変化率が大きい時 7 終わりに 本研究では、マルチエージェント学習においての探 査率調整法として、単純に進化的に探査率を更新する 手法について実験を行いに検証した。その結果、単純 に進化的に探査率を更新するだけでは、全体最適な探 査率以上に低い探査率を獲得してしまい、全体最適な 探査率に近似しないことがわかった。 しかし、ある程度高い性能を安定して獲得できるた め、この手法により一定の効果があることが言える。 単純に探査率を進化的更新するだけでは、大きな探 査率が必要な環境においても小さな探査率を獲得して しまうため、今後としては、追従すべき環境の変化が 激しい環境では、探査率を引き上げるような社会的イ ニシアティブを導入することを検討している。 参考文献 [1] Tokic,M.,Palm,G.:Adaptive Exploitation Using Stochastic Neurons Artificial Neural Networks and Machine LearningICANN, pp.42–49 (2012) [2] Tokic,M.Schwenker, F.Palm,G.:Meta-Learning of Exploration and Exploitation Parameters with Replacing Eligibility Traces ,in Second IAPR International Workshop, pp.13–14 (2013) [3] P Auer,N.Cesa-Bianchi and P Fischer,Finite-time analysis of the multiarmed bandit problem,Machine Learning,pp.235-256(2002) [4] Noda,I.:Exploration 率の進化計算的改善の可能性につ いて, 人工知能学会, (2015) [5] 野田 五十樹, 動的環境におけるマルチエージェント同 時学習における最適 Exploration に関する考察. JAWS (2013). [6] Richard,S.Sutton and Andrew G.Barto.:Reinforcement Learning An Introduction, MIT Press,(1998) average exploration rate of every time step ec0.0002alf0.1 1 average exploration rate of every time step ec0.0002alf0.05 1 average epsilon standard deviation optimum 0.8 average exploration average exploration 0.8 average epsilon standard deviation optimum 0.6 0.4 0.2 0.6 0.4 0.2 0 0 0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 0 1000 2000 3000 4000 cycle average exploration rate of every time step ec0.0005alf0.1 1 8000 9000 10000 average epsilon standard deviation optimum 0.8 average exploration average exploration 7000 average exploration rate of every time step ec0.0005alf0.05 0.6 0.4 0.2 0.6 0.4 0.2 0 0 0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 0 1000 2000 3000 4000 cycle 5000 6000 7000 8000 9000 10000 cycle average exploration rate of every time step ec0.001alf0.1 1 average exploration rate of every time step ec0.001alf0.05 1 average epsilon standard deviation optimum average epsilon standard deviation optimum 0.8 average exploration 0.8 average exploration 6000 1 average epsilon standard deviation optimum 0.8 0.6 0.4 0.2 0.6 0.4 0.2 0 0 0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 0 1000 2000 3000 4000 cycle 5000 6000 7000 8000 9000 10000 cycle average exploration rate of every time step ec0.003alf0.1 1 average exploration rate of every time step ec0.003alf0.05 1 average epsilon standard deviation optimum average epsilon standard deviation optimum 0.8 average exploration 0.8 average exploration 5000 cycle 0.6 0.4 0.2 0.6 0.4 0.2 0 0 0 1000 2000 3000 4000 5000 cycle 6000 7000 8000 9000 10000 0 1000 2000 3000 4000 5000 cycle 図 7: 探査率のタイムステップ毎の推移。その他の設定 6000 7000 8000 9000 10000 ec0.0002.alf0.1 ec0.0002.alf0.05 0.413 0.414 evolution diversity evolution diversity 0.4125 0.412 0.412 0.41 averate reward averate reward 0.4115 0.411 0.4105 0.41 0.4095 0.408 0.406 0.404 0.409 0.402 0.4085 0.408 0.4 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.05 0.1 initial average exploration rate 0.15 ec0.0005.alf0.1 0.443 0.442 0.442 0.44 averate reward averate reward 0.3 0.35 0.4 0.45 0.5 0.444 evolution diversity 0.441 0.44 evolution diversity 0.438 0.436 0.439 0.434 0.438 0.432 0.437 0.43 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.05 0.1 initial average exploration rate 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 initial average exploration rate ec0.001.alf0.1 ec0.001.alf0.05 0.442 0.442 evolution diversity 0.441 0.44 0.44 0.438 averate reward averate reward 0.25 ec0.0005.alf0.05 0.444 0.439 evolution diversity 0.436 0.438 0.434 0.437 0.432 0.436 0.43 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.05 0.1 initial average exploration rate 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 initial average exploration rate ec0.003.alf0.1 ec0.003.alf0.05 0.446 0.446 evolution diversity 0.4455 evolution diversity 0.445 0.445 0.444 0.4445 0.443 averate reward averate reward 0.2 initial average exploration rate 0.444 0.4435 0.443 0.442 0.441 0.44 0.4425 0.439 0.442 0.438 0.4415 0.441 0.437 0.05 0.1 0.15 0.2 0.25 0.3 0.35 initial average exploration rate 0.4 0.45 0.5 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 initial average exploration rate 図 8: 探査率を進化的に更新させた MAL と更新させなかった MAL の初期の探査率の分布別の性能の比較。その 他の設定
© Copyright 2024 ExpyDoc
