論文要旨
エージェント間で直接情報交換ができない分散環境において，エージェントが自分に割り当てられたタスクを達成する
ために共有資源をどの程度の期間確保するかを決定する問題を考える．このとき長期間確保すればタスクを多く達成できる可能性があるが，他のエージェントのタスク達成を妨害し，結果的にシステム性能の低下を招く．本論文では上記の競合を回避する協調的な制御規則を獲得するために，このような資源共有問題を優先順位のある多基準意思決定問題として取り扱う．すなわち，エージェント間に生じる競合の回避と性能の追求という複数の行動規範に弱いトレードオフを考慮した «  戦略を導入することにより，分散強化学習を用いて協調的な制御規則を獲得することを提案する．提案
手法を分散データベースシステムに適用し，協調的な政策の獲得により高いスループット性能が得られることを示す．

システム制御情報学会論文誌，

       論文«  戦略に基づく分散強化学習と資源共有問題への応用

圭 Ý ・池田青木

心 Þ ・木村元 Ü ・小林重信 Ý         «               Ý  Þ                 Ü     Ý  

 

                                                                   
      
                 
       
    
                                                 はじめに

いを観測できない複数のエージェントがいくつかの必要な共有資源を排他的に確保してジョブを処理する問題をネットワークで結ばれた分散システム上には，計算機考える．必要な資源が他のエージェントに既に確保されやデータなどの資源が複数存在し，それぞれ不特定多数ているとき，それが解放されるのを待つ時間を適切に制のエージェントによって共有されている !"．このような御し，処理量を最大化する問題を資源共有問題と呼ぶ．

環境の下では，一般に，各エージェントがそれぞれのタ

システム性能はエージェントの処理量の総和で与えられ，スクを処理するために利己的に性能を追求すると競合がシステムの目的はこの総処理量の最大化である．

生じて，結果としてシステムの性能も各エージェントの本問題の難しさは，各エージェントは他のエージェン

性能も低下してしまう状況に陥る．

トの情報を得ることはできないので，それぞれの処理量

本論文ではその様な問題の典型的なクラスとして，互を最大化するように意思決定を行ったとしても，システ£ 原稿受付

ムの目的が達成されるとは限らないことにある．例えば，

年 月 日
大 学院 総合 理工学研究科


      
!   " #$  
%! &!  '( $$) $ *+,+
Þ
京都大学 学術情報メディアセンター +% -
 -%  .  ' /0"1%  !! ' ))  *+,+Ü九州大学 大学院 工学研究院 2  
 ' /0" ) 1!3! 1!
2!! $  *+,+  4 5 %  % % «%  %
 %!   5% 55 %
Ý 東京 工業大学

近視眼的な視点では各エージェントは資源に対する待ち時間を長く設定した方が処理量を最大化する上で有利である．しかし，すべてのエージェントが同じ視点で処理量の最大化を追求すると，互いに既に確保した資源を待
ちあうデッドロック状態を引き起こしやすい．デッドロッ
ク状態に陥ると，いずれかのエージェントが処理をあきらめて資源を解放しない限り，どちらも処理を完了することができないだけでなく，それまでに確保している資源を必要とする他のエージェントの処理をも妨げてしまう．結果的に各エージェントの処理量は低下し，システ
ム性能が損なわれる．このように資源共有問題は各エー
ジェントの利己的な性能追求が競合を生じ，結果的にシ
# $ #



システム制御情報学会論文誌

第 巻 第  号 67abort

ステム性能に悪影響を及ぼすという難しい課題である．
また，実システムを扱うためには不確実性などの特徴を考慮して制御規則を設定する必要がある．これに対してマルチエージェントシステム %&  ' ( &'() という枠組みの下で分散強化学習 %*

+

S1

2 

得が注目されている $-" が，上記の競合を解決する方法は知られていない．そこで本研究では競合回避のために，待ち時間をなるべく短く設定すればデッドロックが生じ

commit 8(    

 問題設定
るシステムと定義する．システム全体を集中制御できな己的な性能追求と利他的な譲歩という２つの行動規範にい分散環境において &'( を扱うために，各エージェン

基づいてシステム性能を向上させる制御規則を獲得する

トが自律的に意思決定を行う自律分散制御の考え方が必ために優先順位のある多基準意思決定問題として資源共要である．そのような &'( において制御規則の獲得を

有問題を定式化する．各行動規範に対してそれぞれ報酬

難しくする問題のひとつにシステムとエージェントの利を設定して価値関数を定義し，強化学習の１手法である

益が相反するという問題がある．このときエージェント('+(' 学習を用いて更新する．

の利己的な挙動はシステムの利益と反するため，協調的

２つの行動規範に基づく意思決定は以下のように行な制御が同時に要求される．本章ではこのような特徴をう．まず，各エージェントは任意の状態において２つの有する対象問題クラスとして資源共有問題を取りあげる．

行動規範の価値関数で構成される空間上に実行できる

以下では資源共有問題をモデル化し，その問題の所在を

全行動を並べる．そして，多目的最適化の分野で池田ら明らかにする．

によって提案された弱いトレードオフによって導かれる 戦略 /" を資源共有問題のモデル化

互いを観測できない複数のエージェントがいくつかの用いることにより，有望な行動集合を選別することがで必要な共有資源を排他的に確保してジョブを処理する問きる．そのようにして得られた有望な行動集合から任意

題を考える．必要な資源が既に確保されているとき，その探索戦略に従って性能追求の観点で一意に行動を選択

れが解放されるのを待つ時間を適切に制御し，処理量をすることにより，競合回避と性能追求のバランスを実現最大化する問題を本論文では資源共有問題と呼ぶ．

することが期待できる．このとき，探索行動空間として

環境  2  はエージェント集合  と資源集合 からなる．各エージェント    はジョブ  を保持する．   は  の実行に必要な資源であり， はその. 集合を利用することにより，全行動空間が大きい場合でも探索を有望な行動集合に絞って行うことができる．本論文では競合回避のための行動規範である譲歩Smすることにより何らかの利益を獲得することを目的とすな行動規範である譲歩を導入する．各エージェントの利の導入による多基準化と....

本論文では &'( を環境内のエージェントが相互作用にくくなるというヒューリスティクスを用いて，利他的



S3

allocate , *+,) を用いた制御規則の獲. 集合を効率的に求める

S2

数である．

 戦略による選択

 2     と探索の効率化により資源共有問題のシステム性能の向上を目指す．

%$)

ジョブに必要な資源  には順序があるので，3 $ に

本論文では資源共有問題の一例である分散データベー
スシステムのトランザクション処理を実験対象に取り上示すようにエージェント  は  に対してげる．これをベンチマークとしてモデル化した問題に提の順に 3 ! の要領で確保を試みる．

  が他のエージェントに確保されていなければ 

案手法を適用して，いくつかの環境でシミュレーション実験を行って獲得した性能を示し， を排他的に確保し，つぎに  の確保を試みる．
  がすでに確保されている場合，解放されるまで利 戦略に基づく分散強化学習の有効性と有用性を確認する．

用できない．そこで期間以下では ! 章で対象問題として資源共有問題を取りあ競合回避のための行動規範である譲歩を導入し，多基準






%  ) の間待機し，解放されなければジョブを一度あきらめてこれまでげてモデル化し，問題の所在を明らかにする．- 章ではの価値関数を基に  

2 $ ! action : timeout(si) 戦略で有望な行動集合

allocateを絞り込む分散強化学習アルゴリズムを提案する．0 章

WaitingSi

では提案手法を分散データベースシステムのトランザク

abort& resource release

ション処理のベンチマーク問題に適用してその有効性と有用性を確認する．1 章はまとめである．

2 $# ! #S i +1    

S1

% 戦略に基づく分散強化学習と資源共有問題への応用

青木・池田・木村・小林：«

RequestJ1

 接近法

Allocate

上述したように資源共有問題では各エージェントが利

Job

R1

R2

AllocateRequestJ22 9

己的に性能を追求すると競合が発生し，システムの性能

Resourceを低下させる．したがって性能追求と共に競合を回避する方法が必要であるが，環境中の他のエージェントと情報交換できないために，競合するエージェント同士が明  ! 

示的に相互作用して競合を検出・回避するような協調制
御を行うことは困難である．したがって協調制御を導く確保した資源を全て解放し， から再度開始する．

必要な資源を全て確保したらジョブ  を処理して処理ためには，分散環境を前提に何らかの情報を与えて競合制御変数は各エージェント  が各必要資源  を待つ用して競合回避のための行動規範として譲歩を導入し，を増やし，新たなジョブ  ¼ を開始する．

を回避する必要がある．そこでヒューリスティクスを利

待機時間間隔であるタイムアウト政策    である．

多基準の観点から適切に意思決定を行う方法を提案する．

数   2 )   %%  )



%!)が原因で生じる．デッドロックに陥るといずれかのエー

本問題では分散環境を考慮し，互いのエージェントのジェントがジョブを放棄して資源を解放しない限り，ど情報を全く得ることができないと仮定する．相互作用ののジョブも処理を完了できない．したがって，競合を回結果として得る自己の処理量を通じてのみ，システムと避するためにはデッドロック状態をなるべく早く解消すの関連を知覚できる．これはインターネットやイントラる必要があるが，エージェント間で情報を交換できない

ネット環境を通じて共有資源を扱うことが多くなりつつため，デッドロックを検出することは容易ではない．

ある近年の状況に合致する．したがって，各エージェント

そこでデッドロックの検出を行わずに競合を回避すはシステム全体を知覚できないため，システムの目的にる方法を考える．エージェント  は必要な資源  が他直接貢献できない．そこで，各エージェントの性能としてのエージェントによって既に確保されている場合，それそれぞれが処理完了した単位時間あたりのジョブの処理 

ティクスを利用して以下のように譲歩する行動規範を定を基に，システム

義する．

の目的である全エージェントが処理完了した単位時間あたりのジョブの総処理量の最大化



 





が求められる．

%  ) だけ待つが，これが短いほどデッドロックになりにくいというヒューリス

により，それぞれ性能向上を目指す．このような各エー

が解放されるのを時間量が与えられ，タイムアウト政策を適切に決定すること
ジェントの性能追求

競合回避のための譲歩

資源共有問題において競合は一時的なデッドロック






% )

%-)

しかし，各エージェントができるだけ競合が起きないよ

問題の所在

各エージェントにとってジョブを確実に処理完了する

うに譲歩しすぎてタイムアウト時間が短い政策を選択す

ためにはなるべく長く待つタイムアウト政策を選択し，れば，競合回避は促進されるものの，当然ながら必要資

必要資源を確保している他のエージェントの処理が完了源の確保が難しくなり，各エージェントの性能が損なわするか，処理をあきらめて資源が解放されるまで待つこれ，結局システムの性能も得られない．そのため，このとが有効である．しかし，既に確保されている資源に対行動規範は副次的なものとして扱う必要がある．

して長く待つという政策は，3 - に示すような互いに

各エージェントにとって性能追求の行動規範のみに従確保している資源を要求しあうことにより膠着状態に陥うと競合を生じ，譲歩の行動規範のみに従うと性能が低るデッドロック状態を引き起こしやすい．この状態に陥下することを考慮して，双方のバランスをとる優先順位

ると，いずれかのエージェントが処理をあきらめて資源付きの多基準意思決定問題として資源共有問題を扱う．

を解放しない限り，どちらも処理を完了することができ

すなわち，主目的を性能追求ないだけでなく，それまでに確保している資源を必要と

を譲歩



する他のエージェントの処理をも妨げてしまう．結果的

最大化



に各エージェントの処理量は低下し，システムの性能が



 
 





 

，副目的

%  ) として，システム性能のを目指す．

分散強化学習を用いた自律分散制御

損なわれることになる．このように資源共有問題は本来競合のために各エージェントの単位時間あたりの処理

システム性能に結びつくはずの各エージェントの利己的量には不確実なノイズが含まれることは避けられない．

な性能追求がデッドロックという競合を生み，結果的にこの場合，政策の長期的な評価を行える強化学習を用いシステムの性能低下を招くという困難な問題点を持つ．

て制御政策を獲得することは有望である $0" ．
本論文では性能追求と譲歩の行動規範に関する報酬を
# - #



システム制御情報学会論文誌

   第

 巻 第  号 67
Qc

それぞれ設定し，各エージェントにベクトルで与える．

 2






% )  


Qc

OC
X

%0)

X
X

X
X

O

 %) 2  %) %)
%1)
 %) 2 %$  ) %)4 % 4   %  )) %/)2 #¼

ここで  は性能追求のためのジョブの処理量に関する価値関数， は譲歩のための政策の待ち時間に関する価値関数で， は学習率， は割引率である． は観測した状態， は選択した行動，¼ は遷移後の観測状態で，

 は  で選択する行動である．
 «  戦略に基づく行動選択
¼

OD
O

X
X

O
X

X

を用いてそれぞれ更新 %%/) 式) する．

¼

O

X

価値関数をそれぞれ定義 %%1) 式) し，('+(' 学習 $0"

¼

XC
X

OD

X
Qt

O
X

Qt

 ,   67   «,   67    2+      5  Æ ( %      % 

されないからといって同等に扱うことは無駄である．このとき，１ユーロは少なくとも 7$ ドルよりは価値があるといった知識を利用して，１ユーロ＞ 7$ ドル，$ ド
ル＞ 7$ ユーロといった最低限の価値関係が記述できる

本論文では２つの行動規範に基づく意思決定において，

とき，これを弱いトレードオフとして定義することによ

まず行動空間全体を対象に多基準の観点から有望な行動

り，有用な候補だけを選択肢に残すことができる /" ．

集合 %3  ' ( 3'() を選別する．そして得

この弱いトレードオフ関係を用いて 3 0%右) に示す

ように「 の観点で行動られた 3'( を対象に性能向上の観点から任意の探索戦が行動  に少々劣っていても、 の観点で行動 が行動  におおいに勝る」場合は略を用いて行動を一意に決定する方法を提案する．
3 0（左）に示すように２つの行動規範に関する価行動  を . 集合から排除することができる．この値関数で構成される空間に，任意の状態において選択で場合を行動

きる全行動をプロットする．このとき，多目的最適化のして得られる集合を. 集合の観点から，ある程度有望な行動集合を選別

はが行動  を するといい，こう. 集合という /" ．本論文で. 集合を 3'( とし，優先順位に基づき をすることができる．しかし，55と5 5のついた行動に着最大化する行動を  戦略などの探索戦略を用いて目すると，行動3'( から一意に決定する．

に対してわずかに性能に関する  が高いけれども，譲歩に関する  がかなり低い行動  も

また



 戦略は探索効率を向上させる効果に対も期待できる． 戦略などのランダム性を用いたして性能向上は少ししか期待できないにもかかわらず，

探索戦略は単純さなどから良く用いられるが，連続値の競合を引き起こすリスクが大きい行動  は望ましくない行動を離散化するなどして行動空間が大きい場合などでが，従来の性能追求のみの行動選択ではこのような行動

は，行動空間全域をランダムに探索するのは効果的ではが優先的に選択され，競合が引き起こされやすい．

ない．また，他のエージェントとの競合を考慮すると，. 集合に含まれてしまうことがわかる．行動

そこで



 戦略 /" を 3'( の選択に用いることにする． 

ランダムなどを利用した探索的な選択によって他のエー 戦略は多目的な要素に対しジェントの性能に大きい影響を与える行動を実行するこて， 判定に弱いトレードオフを導入する手法とは望ましくない．このとき２つの行動規範の価値関数

で， 抵抗解を . 集合から効率よく排除からあるトレードオフの下で選別された 3'( を探索空間できる有効性が示されている．弱いトレードオフ関係はとして利用することにより，探索による競合の発生と無次式で表現される．

駄な探索を低減し，効率よく学習することが期待できる．

 $

%6)
 


ここで  と  は  と  の変化量，  ， 

以上が競合回避のために譲歩という行動規範を定義した優先順位付多基準意思決定問題を対象とする


ある．3 1 にその概要を示す．

はトレードオフパラメータである．本論文では単純に
2 戦略に基づく分散強化学習アルゴリズムで 2  とした．

関連研究

各価値関数間のトレードオフ比が厳密に設定できない環境を共有する意思決定エージェントで構成する &'(ことはしばしば言われることだが、その上下限を設定すはゲーム理論の分野で古くから研究が行われ，特に 8

ることは比較的容易である．例えば，ドルとユーロの為均衡という観点から多くの有益な分析や知見が得られて替レートを固定して考えることはできないけれども，$77

いる $7" ．しかしゲーム理論の観点では環境の完全観測

ドル＋ $77 ユーロの価値と $ ドル＋ $71 ユーロの価値は性が前提にあり，資源共有問題のように情報が限定され常識的に差があることが明らかであり，共に た環境を扱うことはできない．また，( $!" らや


# 0 #



% 戦略に基づく分散強化学習と資源共有問題への応用

青木・池田・木村・小林：«%$) 価値関数%!) 状態

 を初期化

DatabaseSite5 

 を観測%-) 意思決定

並列動作トランザクション数

 処理時間
処理時間

  に関して 3'( から探索戦略（

他サイトへのリクエスト率
自サイトへのメッセージ遅延選択など）により一意に行動  を決定2 )

¼



%6)

2

 2  ， 2  として，%0) に戻る¼¼

 5 %  %5  «% 

他サイトへのメッセージ遅延Transaction¼%/) %/) 式で各価値関数を更新〜
 

 ％

 

コミットまでに必要な資源数

集合を 3'( に登録（3 0 右の Æ の行動）

 を実行して報酬  と次状態  を観測%1) 意思決定 %-) を行い，行動  を決定

値

データベースサイト数

. となる行動%0) 行動 %

パラメータ

Network %)  に関して %  ::;

まで待機状態に入る．
このとき資源を一定時間待ったトランザクションをデッドロックとみなし，強制的にアボートさせる方法を
タイムアウトといい，単純かつ実用的なため広く用いられている．しかし，動的で不確実な環境において良い性
能を引き出すタイムアウトの設定は非常に難しい $1" ．

9  0" らは限定された通信を行える &'( においてシステムの目的は各エージェントが単位時間あたりに協調制御を獲得できる有効な手法を提案しているが，完コミットした処理量を表すスループットの総計を最大化

全な分散環境である資源共有問題などには適用できない．

することであり，本論文ではこのスループットの総計を

これ対して協調行動を学習する政策勾配法 $$" や分散システムの性能として評価する．



強化学習 1" を 8 均衡の観点で捉える研究がある．こ実験設定

れらの研究は分散環境に適用できるが利己的なエージェ

トランザクション自体の処理は詳細を観察することはント間に生じる競合とシステム性能低下の問題を想定すできない．そこで本論文では 3 / に示す **: の各サ

るものではない．我々の知る限りでは &'( におけるこイトをエージェントとし，そこから生成されるトランザの困難な問題を直接扱うことができる効果的な分散強化

クションは同じタイムアウト政策に従うものとする．

学習手法は知られていない．

トランザクションはコミットまでに複数の様々なデー

また &'( ではないが多目的性の取り扱いについてはタの確保を必要とするため，%!) 式をそのまま政策とす

辞書的順序を利用した手法 -" や目標領域に平均報酬ベ

ることはできない．そこでトランザクション処理の特性

クトルを指向する強化学習 6" がある。これらの手法はを利用して確保データ数に関する関数としてタイムアウ

意思決定そのものを多目的の観点から行うものであるが，ト政策を定義する <" ．

本論文は優先順位のある行動規範に基づく多基準性の下



で，行動選択の候補を効率的に絞り込むものである．

 分散データベースシステムへの応用
 *  (   

2 $ ! %=)にトランザクションを生成してスループットを受け取る．
実験では   $ に示すパラメータで **: を設定し，

 **:)

各サイトの保持データ数が $77 の均一環境と，ひとつののトランザクション処理をモデル化した問題に提案手法サイトが $77 で他の 0 サイトが -77 の不均一環境に対を適用し，有効性と有用性を示す．

   

各サイトは政策パラメータ % ) を決定し，一定期間環境

本章では資源共有問題のベンチマークとして分散データ
ベースシステム %*% ) 2は政策パラメータである．

して適用した．これは限界性能を計算するために単純なトランザクション処理とデッドロック

設定を用いている．また，並列動作トランザクション数

トランザクション処理とは，並列処理において個別に%&  .

 , &.,) を固定した定常環境

行われる動作の集合からなる計算処理をいい，統一概念

で $7 から !77 まで実験した．&., が大きいほど環境がとして原子性，一貫性，分離性，持続性という '; * 特

混雑しデッドロックが起こりやすくなる．本課題の詳細性が定義されている．各トランザクションはジョブが与は参考文献 =" に記述されている．

えられると処理を開始し，処理の終了をコミット，途中

実験期間は全体で $1

$7

，$7

$7

 間隔で意で中止することをアボートという．アボートした処理は思決定し，学習終盤の $7 $7

全て元通りに戻さなければならないなどデータの一貫性

予備実験に基づき強化学習パラメータは学習率 7$，割引を維持するために参照や書換えが行われるデータをロッ

率 7<， 

クする方法が広く使用されている $" ．あるトランザク$7 から $77 で 7771，$$7 から !77 で 777$ を用いた．不ションがデータをロックすると，他のトランザクション

均一環境では全 &., で 7777$ を用いた．政策パラメー

はそのデータにアクセスできなくなりロックが外される# 1 # 戦略の 間の性能で評価を行う．

は均一環境では &., が

システム制御情報学会論文誌

第 巻 第  号 67
Performance of DB (uniform 5site, MPL10-200)

タは  は 177 間隔で %1776177) の範囲を $1 段階， は12

771 間隔で %$71$1) の範囲を $7 段階に離散化した．しThroughput

ム全体ではサイト数  に対して $17 の組合せとなる．
3 6 から 3 $7 は $7 試行の平均値をプロットした．

-domination
Q-Learning
Fix Best

10

たがって各サイトは行動数 $17 から意思決定し，システ

比較手法

従来運用に用いられる固定値のタイムアウト政策 %3:) とスループット最大化を行う > 政策と比

86Theoretical Limit

4
2

較を行う．3 : 政策は確保データ数に関係なく固定
値のタイムアウト時間をとる最もよく使われる政策であ20

り，3 6 では各 &., に関して固定タイムアウト時間

2 <

を %177!7777) の範囲で離散的に全探索して得られた最良値を求め，それをプロットした．



80 100 120 140 160 180 200
MPLり性能を向上できることから確認された．提案手法は範である処理数最大化

が，譲歩の行動規範を用いずに60  %  .,=$  % ::;> 政策は各エージェントが性能追求の行動規  
のみで学習を行
い，競合は考慮しない．各設定は提案手法と同じである

40

ほぼ全ての &., において処理量最大化のみを追求する 戦略では> を上回り，限界性能である組合せ最良解と同なく全行動空間から  戦略で意思決定すること，等の性能を獲得した．以上より，譲歩の行動規範の導入

価値関数の更新を > $/" で行う点が異なる．

とまた，限界性能を示すために，全サイトを一括した集 戦略によって探索行動空間を絞り込む

分散強化学習の有効性が確認された．
均一環境において &.,17 の時の学習曲線を 3 = に

中管理の下で政策パラメータを離散的に全探索して得ら示す．学習序盤における性能差は， 

れた組合せ最良解も示す．このために全探索のための予 戦略

備実験では，均一環境では全てのサイトに同じ政策を共により早い段階から多くの価値の低い行動が 有させ，不均一環境では保持データ数が $77 のサイトとされるためと考えられる．報酬は他のサイトの政策によ-77 のサイト毎にそれぞれ政策を共有させた．このようり大きく変動するため，学習序盤の探索的な行動によっに同じパラメータのエージェントが同一の共有政策を用て競合が起きやすいが， . 集合である 3'( に有いることにより，システム全体で決定する政策パラメー

望な行動が登録されることでこの競合が早期に解消でき

タ空間をかなり小さくし，その中で網羅的に全探索してていると考えられる．以上より，アルゴリズム以外は同組合せ最良解を求めた．これは分散環境では実行不可

設定の実験で学習速度の違いが観察されることから，提能な方法であるが獲得性能の理論的な限界 %

案手法の探索の効率化が有望であることが確認された．

,

不均一環境において各 &., 毎に得られたスループッ) を示すことができる．
 戦略の有効性を示すための実験では，追求の行動規範に関する報酬とト性能を 3 < に示す．極端に混雑するサイトと他の 0サイトとの性能はトレードオフ関係にある．限界性能を提案手法で用いた譲歩の行動規範に関する報酬を性能をトレードオフ比の

Performance of DB (unifrom 5site, MPL50)

パラメータと見なして重み付け線形和することにより単目的化する > %,

 (,(>) との比較を行う．トレードオフパラメータ

>

8

に



Throughput

関しては性能追求と譲歩の優先関係から %6) 式の左式の関係が重要であることを考慮している．

 2 %$  ) 


4





% )

%<)

6

4

実験結果と考察-domination( = 0.005)
Q-Learning
1000 3000 5000 7000 9000 11000 13000 15000
step (x100000 ms)

均一環境において各 &., 毎に得られたスループット
性能を 3 6 に示す．従来運用でよく用いられている固2

定タイムアウト政策は最良の値を選択しても十分な性能が得られていないことがわかる．すなわち，タイムア
ウト時間を保持資源数に関して設定する %=) 式で示される政策表現の妥当性が，従来の固定タイムアウト政策よ# / #  0  .,=    %::;     0  %   % 6 7   5   0

% 戦略に基づく分散強化学習と資源共有問題への応用

青木・池田・木村・小林：«Performance of DB (uniform 5site, MPL100)

表す組み合わせ最良解は混雑するサイトをある程度犠牲6にすることで全体の性能を向上させる政策群であり，混-domination
LWS-Q

雑するサイトのスループットは他のサイトの約 $/ 程
Throughput

度となる．提案手法ではそのような政策群の他に，ある程度揃った政策群が学習される試行が確認された．このときスループットは他のサイトの約 $- 程度となる．これはスループットの総計を観測できないことと実験パラメータなどの設定が同一なためであると考えられる．こ5

4

れらのことから理論的な限界性能には平均で至っていな
いが，処理量最大化のみを追求する > よりも性

10

-5

10

-4

10

-3

5x10-3

能は良い．

2 

なお，不均一環境では競合の問題の他に，システム全
体の性能の最大化とサイト間の平等性とのバランスと  5( «   
% 6 % ::; .,=7

いった質の異なる問題がある．これは一般に運営者のポリシーに依存するものであるため，どちらを優先させる

験では全サイトが短いタイムアウト政策を選択するようかを決めることは困難なので本論文では扱わなかった．

になり，急激な性能悪化が見られた． を小さくしてい«

 戦略において



くにつれて競合のリスクは許容され， . 集合に含戦略の効果
は性能追求と譲歩の間まれる行動数は増加していくはずだが，相互作用を介しの弱いトレードオフ関係を表すパラメータで，獲得性能て競合しづらい行動が結果的に評価されて 3'( に選択に影響する．本問題において &.,$77 程度の場合は経験され易い傾向があり，性能の低下は徐々に起こることが的にスループット性能を $ 向上させるために !77

確認された．

 から% ) の増加は許容を適切に調節することは突き詰めれば適切なトレーできるが，それ以上は費用対効果が悪いことがわかってドオフ比を求めることになる．そこで，単純に比較すいる =" ．また待ち時間を増加させる場合に処理量もかることはできないけれどもなり増加しないと許容しないといったように譲歩しすぎ,(> と提案手法の結果を並べ，その違いを考察する．

-77

 程度までの待ち時間

3 $7 では 3 = の学習曲線で述べたことと同様に，

れば，性能追求がないがしろになってしまうと考えられ,(> は大きな行動空間での探索の困難さなどから全る．したがって， が大きすぎると主目的が達成されずに性能が急速に悪化し，-7$7  から 17をトレードオフ比とした$7  程度

体的に性能が低いことが確認された．特にが小さいとで適切なトレードオフ関係が得られて性能が良くなり，

きは性能追求が重視されて競合が発生しやすく，性能が小さくなるにつれて性能が悪化すると予想される．

低下していく様子が観察されたという点で提案手法の結果と異なることがわかった．

均一環境において &.,$77 の時， を変化させたときのスループット性能を 3 $7 に示す．予想通り適切な以上のことから提案手法は ,(> と同様にトレード

 から 17 $7  で良い

オフを用いるものの，どの程度譲歩するかという観点でトレードオフ比である -7$7を選択すれば ,(> よりも良い性能をロバス

性能を示した． を大きく設定することは譲歩しすぎる適度にことになるので，そのような設定は本来用いないが，実トに獲得できることが確認された．

 おわりに

Performance of DB (uneven 5site, MPL10-200)-domination
Q-Learning

Throughput

14

資源共有問題を対象に，競合回避のための譲歩という 戦略に基づく分散強化

行動規範の導入と10

学習手法を提案した．資源共有問題はエージェントの利Theoretical Limit8

己的な性能追求がシステムの性能を低下させる競合の問

6

題から，分散環境ではシステム性能を向上するために協調的な制御が同時に要求されるが，優先順位付多基準意

4

思決定問題にモデル化して提案手法を適用することによ2

り，高いシステム性能を獲得できることを **: の課題
20

2



12

40

60

で実験的に示した．

80 100 120 140 160 180 200
MPL

本手法は競合回避を実現する行動規範として譲歩に限  %  .,=$  0 ::;定するものではない．競合回避に貢献する任意の報酬が設計できれば適用することができる．このとき，完全な競合回避のための行動規範を設定することは必ずしも要# 6 #システム制御情報学会論文誌

第 巻 第  号 67=  0 0  "    )     *   # +       # # ) 6$7>$? *   E ' E + .  .
D%4 :5 0 "     )                9< 9< 6 7
>9? ,   . 4 . %4 +0 %  %  0" #"
 " ,-    9  9# 9 9 6$7>#? D    + ;4 ,     .
#  "    + ; ;!  . ,
6 7> ? 魚田 小碇4 データベース 日科技連 6 97>)? - * - 1 E!  , :4  4/=      0   $< $ $ 6 $7

求されず，ある程度行動を絞り込むヒントとなれば良いと考えられる．また，互いに情報交換できない &'( におけるエージェントの利己的な性能追求による競合とシステム性能の低下の問題は，資源共有問題に限らず様々な実問題に存在し，それらの制御規則の獲得を困難にする．例えばエージェントが何らかの制約を持つ &'( であれば，システム性能と制約充足の間には少なからず競合が存在する．提案手法はこのような課題に広く拡張できる可能性があると考えている．また，提案手法は２つ以上の行動規範に基づく多基準意思決定にもそのまま適用することができる．例えば複数の目的や制約充足などを扱うより複雑な問題への適用が考えられる．
今後は上記のことを考慮し，本論文で扱わなかった動的環境を扱う課題に提案手法の適用を考えている．

参 考 文 献著 者 略 歴>? , ;   (%4           . '% ,5
6 <7 6「トランザクション処理システム入門」，大77
磯，小野沢，木下，中山，早瀬 6訳7．日経 ;, 6>$?  2@4 + A% 5 !% B 5( !A% %"         )<  #     < 6 7
>9? C 5 C '%  - 304 .
 % "                      < $ 6 7>#? -  . =!  D ,4 -
% "                      $$< $9#
6$$7> ? * 1  . , E%4 B%  
F  %  %"                     #< ## 6$7>)? ' ! 1 '   '54 2 5 .G+4 : % 
%   %H"         ! "    "    < )$6$7><?  .   %!4   
 % % " #! $"       % &    )9
 < 6$$7> ? 大金4 分散データベースにおける協調機構の実現" 東京工業大学知能システム科学専攻修士学位論文 6$97> ? 大金，木村，小林4 分散データベースにおける協調機構の実現"     ' % %  "     %  <9 < 6$97>? . * G5  + D54 # "  (   . , 6 #7>? = ,! ' '%  .  = '54

あお

き

けい

青 木

圭

$$ 年東京工業大学大学院知能システ
ム科学専攻修士課程修了．同年４月博士課
程在籍中．マルチエージェント，強化学習，
協調システムに関する研究に従事．

いけ

だ

こころ

池 田

心

 9 9

年 月，東京大学理学部数学科卒
業．同年４月，東京工業大学大学院総合理
年
月，
工学研究科修士課程入学．

$9 9#$ 

年 月，同修了．博
同博士課程進学，
士（工学）．同年 月京都大学学術情報メディアセンター助手，現在に至る．主に最適化，高度な意思決定システム，ゲームの研究に従事．
むら

はじめ

木 村

き

元

 <

年東京工業大学大学院知能科学専
攻博士課程修了．同年 月日本学術振興会
年 月，東京工業大学
ＰＤ研究員．

##$# #

年 月，九州
総合理工学研究科助手．
大学工学研究院助教授．現在に至る．人工知能，特に強化学習に関する研究に従事．

こ

ばやし

小 林

しげ のぶ

重 信 %正会員)

 <#年東京工業大学大学院経営工学専
攻博士課程終了．同年４月，同大学工学部

 年８月，同大学大制御工学科助手．
年８
学院総合理工学研究科助教授．
月，教授．現在に至る．問題解決と推論制
御，知識獲得と学習などの研究に従事．

# = # 