多目的意思決定のα-domination 戦略に基づく分散強化学習と分散データベースへの応用○青木 圭，木村 元，小林 重信
東京工業大学 大学院総合理工学研究科

Distributed Reinforcement Learning based on α-domination Strategyfor Multi-criteria Decision Making
and its Application to Distributed Database Systems
Kei Aoki, Hajime Kimura, Shigenobu Kobayashi
Interdisciplinary Graduate School of Science and Eng., Tokyo Institute of Technology
Abstract— In the distributed systems in which information cannot be exchanged directly among agents, we deal with problems ofdeciding how each agent holds the shared resource. To achieve a lot of tasks greedily, agents tend to attempt to hold the resources
for a long term. However the system performance decreases consequentially because it competes with the processing of otheragents’ tasks. To acquire cooperative policies that avoid above competition, we formulate the resource sharing problems to multicriteria decision making problems with the priority level by using the domain knowledge into the reward. We propose distributed
reinforcement learning that narrows the choice of action space by using the α-domination strategy based on value functions for theobject and the cooperation. The proposed method is applied to the distributed database systems, and simulation results shows that
our method acquires cooperative policies and improves the throughput performance of the system.

1 はじめに
近年では様々な分散システムの自動化や自律エージェント群による協調システムなどの研究が盛んに行われている．特にネットワーク環境では不特定多数のタスクが存在し，その効率的な自動化や自律化が望まれている．しか行動集合 (Feasible Action Set, FAS) として選別する．これにより行動空間が大きい場合でも探索を有望な FAS に絞って行うことができる．我々は競合回避のための副目的導入による多目的化と α-domination 戦略による探索の効率化により資源共有問題のシステム性能の向上を目指す．

し，いくつかのマルチエージェントシステム (MAS) では提案手法の有効性を確認するために資源共有問題の一システム全体の効率的な運用が重要であるにもかかわら例である分散データベースシステム (Distributed Database

ず，一般にエージェント間の情報交換を行うことは簡便性

Systems, DDBs) のトランザクション処理をモデル化したやコストの点から困難であるため，各エージェントが独自ベンチマーク問題に適用し，いくつかの環境でシミュレーに性能を追求すると競合が発生し，結果的にシステムの性ション実験により獲得した性能を示す．

能が低下するという問題点がある．我々は MAS が扱うタ

以下では 2 章で MAS が扱うタスクについて分類し，資スクを分類し，競合する協調タスクの特徴を明示した後， 源共有問題をモデル化する．3 章では競合回避のための副典型的な問題クラスとして資源共有問題をモデル化する． 目的を導入し，多目的の価値関数を基に α-domination 戦
また実システムには不確実性や環境の変化といった特徴略で FAS を絞り込む DRL アルゴリズムを提案する．4 章があり，MAS においては分散強化学習 (Distributed Rein-

では DDBs のトランザクション処理のベンチマーク問題

forcement Learning, DRL) による接近法が注目されているに適用してその有効性を確認する．5 章はまとめである．

[10] が，上記の競合を解決する方法は知られていない．そこで我々は競合回避のために知識を報酬設計に導入し，副2 問題設定目的として譲歩タスクを定義することにより，資源共有問

本章では MAS が対象とするタスクについて，その目的題を優先順位のある多目的意志決定問題として扱う．性能の観点から分類する．そして従来の DRL において困難な追求のための主目的と競合回避のための副目的の２つの価問題の具体例を挙げ，資源共有問題をモデル化する．

値関数を基に，多目的最適化の分野で弱いトレードオフに2.1 競合を伴う協調タスク

よって導かれる pareto 集合を効率的に求める α-domination

我々は MAS を環境内のエージェントが相互作用するこ戦略 [4] を用いて行動空間全体から有望な行動を実行可能とにより何らかのタスクを達成することを目的とするシス

テムと定義する．まず，システム自体に目的がない場合とA1ある場合に分類する．
システムに目的がない場合：これらの問題には，売買エー

A2CD

ジェントを扱う市場問題やオークションシステム，チェスや 1 対 1 の対戦ゲームなどが挙げられる．エージェントは効果的な売買や勝利といったそれぞれの目的があるが，システムは単に環境である．また各エージェントの目的を達成しようという試みは，たいてい他のエージェントと競合するため，本論文ではこれを競合タスクと呼ぶ．

A1

C

D

(4,4)
(1,5)

(5,1)
(2,2)

Table1: 利得表 1,(r1 ,r2 ).

A2-C

D

(4,-)
(1,-)

(5,-)
(2,-)

Table2: 利得表 2,(r1 ,-).

しかし我々は分散環境を考慮し，表 2 に示すように完全な利得表も相手の行動も観測することができず，結果的に得られる利得のみを観測できる問題を考える．得られる利得を基に ri の最大化を部分タスクとする場合，相手の行動システムに目的がある場合：これらの問題には，追跡問題が一意に定まればいずれの場合も行動 D が行動 C よりもや箱押し問題といった協同作業問題や次節で述べる資源共高い利得を得るので，双方のエージェントは互いに行動 D有問題などが挙げられる．システムには各エージェントのを選択し，システムは最低の利得 ∑i ri = 4 を得る．この協調動作によって達成されるタスク（システムタスクと呼ときシステムタスクを向上させる協調行動は存在するが，ぶ）が最も重要だが，分散環境であるために各エージェン情報が足りないために発見することは難しい．また行動 C

トは直接システムタスクを制御することはできず，それぞを選択するとしたとき，同じ行動 C を選択しても相手次れ部分的なタスク（部分タスクと呼ぶ）を制御することに第で利得が 4 になったり 1 になったりするため，その行動なる．そこでこれを協調タスクと呼ぶ．の価値を決めることは容易ではない．

我々は協調タスク問題に興味がある．そこでさらに協調

本研究では競合する協調タスクである資源共有問題にタスク問題をシステムタスクのために部分タスクが競合し着目し，システムタスクを達成する協調的な行動政策を獲ない場合と競合する場合に分類する．

得できる手法を提案することを目的とする．

部分タスクが競合しない場合：これらの問題では一般に各2.2 資源共有問題のモデル化

エージェントによる部分タスクの達成はシステムタスクの達成につながる．そのため各エージェントはシステムや他のエージェントのタスクについて特別考慮せずに部分タスクの達成を目指せばよい．
部分タスクが競合する場合：これらの問題では各エージェントが利己的に部分タスクの性能を追求すると，競合によってシステムタスクの性能が低下する．そのため各エージェントは部分タスクの達成だけでは不十分で，システムタスクのために他のエージェントと協調的に相互作用する方法が必要になる．これを競合する協調タスクと呼ぶ．
このような競合する協調タスクは一般に多くの実問題

資源共有問題とは互いを観測できない複数のエージェントが必要な共有資源を排他的に確保してジョブを処理し，環境中の総処理量を最大化する問題である．
本問題において我々は各エージェントが相互作用の結果として得るそれぞれの利得以外，互いのエージェントの情報を全く得ることができないと仮定する．これはインターネットやイントラネット環境を通じて共有資源を扱うことが多くなりつつある近年の状況に合致する．
環境 E = {N, S} はエージェント集合 N と資源集合 S からなる．各エージェント n ∈ N はジョブ jn を保持する．に見られ，部分タスクの達成と協調することによるシステ

sni ∈ S は jn の実行に必要な資源，m はその数である．

ムタスクへの貢献のバランスを獲得しなければならない困

jn = {sn1 , sn2 , sn3 , · · · , snm }難な問題である．困難さを説明するために，繰り返し囚人のジレンマを拡張した例題を用いる．囚人のジレンマ問題
では，行動 (C or D) を提示したエージェント Ai はその組合せによって表 1 に示す利得 ri を獲得する．これを繰り返すとき，利得表と相手の出した行動を基に合理的な行動選択を獲得する問題で，ゲーム理論によれば合理的なエージェントは，互いに行動 D を出し合う Nash 均衡政策を選択することが知られている [8]．
ここで双方の利得の総和の最大化 maxaction ∑i ri をシス(1)

ジョブに必要な資源 sni には順序があるので，図 1 に示す
ようにエージェント n は sni に対して i = 0, 1, 2, · · · の順に
図 2 の要領で確保を試みる．

• sni が他のエージェントによって確保されていなければ sni を排他的に確保し，次に sni+1 の確保を試みる．
• sni がすでに確保されている場合，解放されるまで利用できない．そこで期間 timeoutn (sni ) の間待機し，解放されなければジョブを一度あきらめてこれまで確保した資源を全て解放し，s1 から再度開始する．

テムタスクと定義すれば，各エージェントは利得表より必要な資源を全て確保したらジョブ jn を処理して処理数最大の ∑i ri = 8 を得る行動 C を選択できるかもしれない． commit を増やし，新たなジョブ j を開始する．
nnaction : timeout(s)abortcommit
S1

S2

S3

Si+1

allocate....

Smabort

Sm+1

R1

R2

Allocate

ReqestResourceπn = {timeoutn(s1 ), · · · ,timeoutn (sm )}J2

Fig.3: デッドロック発生の模式図

Fig.2: 資源確保の模式図

制御変数は各タイムアウト政策 πn ∈ Π である．

AllocateS0

allocate

Fig.1: 資源確保の遷移図

J1

JobWaiting

SiReqest

そこで我々はデッドロックの検出は行わず，資源 si の(2)

解放を待つ時間 timeout(si ) が短いほどデッドロックになりにくいことを利用して譲歩タスクを定義する．

minπn ∑ timeoutn (sni )部分タスクは各エージェントが処理完了したジョブの総数の最大化であり，それらを基にシステムの目的である全(4)iエージェントが処理完了したジョブの総数の最大化を行う． ただしこれはシステムタスクに直結するものではないため
部分タスク

システムタスク

maxπn commitn→ maxΠ ∑n commitn(3)

副目的として扱う必要がある．譲歩タスクは競合回避を促進するものの，必要以上の譲歩はエージェントの利得の減少を招き，結果的にシステムタスクの性能も低下させる可ジョブを確実に処理完了するためにはなるべく長いタイムアウト政策を選択し，必要資源を確保している他のエージェントの処理が完了するかあきらめて資源が解放されるまで待つことが有効である．しかし，長いタイムアウト政策は図 3 に示すような既に確保されている資源を待ち合うデッドロックを引き起こしやすく，他のエージェントの処理を妨げてしまう．このように資源共有問題は各エージェントの利己的な性能追求が競合を生み，システムの性能低能性があるからである．
主目的である部分タスクによる利得の追求は競合を生じ，副目的である譲歩タスクによる競合回避の追求は利得減少となることを考慮して，資源共有問題を双方のバランスをとる優先順位付の多目的意志決定問題として扱う．
maxπn commitn(5)→ max ∑ commitn
Π nminπn ∑i timeoutn(si )下を招く競合する協調タスクの典型といえる．

3 接近法

3.2 α-domination 戦略に基づく分散強化学習
競合のために処理タスク数には不確実なノイズが含ま

資源共有問題では各エージェントが部分タスクの利得れることは避けられない．このような場合，政策の長期的を追求すると競合が発生し，システムタスクの性能を低下な評価を行う強化学習を用いることは有望である [10]．

させる．従って利得の追求と共に競合を回避する方法が必要であるが，環境中の他のエージェントと情報交換できないために，競合するエージェント同士が明示的に相互作用

我々は各エージェントに主目的と副目的に関する価値関数をそれぞれ定義し，Q-learning[10] を用いて更新する．

して競合を回避するような制御を行うことは困難である．

Qn (x, a) = {Qnc (x, a), Qtn (x, a)}

そこで我々は競合の回避を目的とするタスクを導入し，多Q (x, a) = (1−λ)Q (x, a)+λ(rn +γ max Q (x , a ))nn(6)n(7)目的の観点で効率的に意志決定を行う方法を提案する．
ここで Qc は主目的である処理数の価値関数，Qt は副目的

3.1 競合回避のための譲歩タスクである政策の待ち時間の価値関数で，λ は学習率，γ は割

我々は競合回避を目的とした副次的なタスクを導入し， 引率である．報酬 r は双方の目的に関して与えられる．

これを譲歩タスクと呼ぶ．一般に譲歩タスクは問題依存で
for Qccommitn
rn =(8)あるため，ここでは資源共有問題を対象として議論する．
∑ timeoutn(si ) for Qti

資源共有問題において競合は一時的なデッドロックが原因で生じる．デッドロックに陥るといずれかのエージェン
トがジョブを放棄して資源を解放しない限り，どのジョブも処理を完了できない．従って，競合を回避するためにはデッドロック状態をなるべく早く解消する必要があるが，エージェント間で情報を交換できないため，デッドロックを検出することは容易ではない．

我々は２つの価値関数に基づく多目的の意志決定において，まず行動空間全体から有望な行動の集合 (FAS) を選択する．そして FAS を探索行動空間としてその中から主目的を基準に行動を一意に決定する方法を用いる．
多目的最適化の pareto 集合の観点から，図 4(左) に示す
ようにある程度有望な行動集合を選別することができる．

Qc



Qc

OC
X

X
X

XC
X

OD
OX
X

X
OX

OD

２．状態 x を観測．
３．Q(x,a),∀a に関して α-pareto 集合を FAS に登録．
４．FAS から Qc (x,a) に関して ε-greedy 選択．
５．行動 a を実行して報酬 r を観測し，式 (7) で価値関数を更新．
６．２に戻る

OX
X

OX

X
Qt



１．価値関数 Q を初期化．

OX



Qt



Fig.5: 意志決定アルゴリズム

Fig.4: pareto 行動集合 (左) と α-pareto 行動集合 (右)．o は x をドミネイトする集合の要素で FAS に登録される．灰色部はドミネイト領域を表す．

を扱うことはできない．そこで協調行動を学習する政策勾配法 [9] や分散強化学習 [3] を Nash 均衡の観点で捉える

しかし，”a”と”b”のついた行動に着目すると，行動 b に対研究がある．これらは分散環境に適用できるが各エージェしてわずかに主目的の価値 Qc が高いけれども副目的の価ントが競合する場合は扱うことができない．我々の知る限値 Qt がかなり低い行動 a も pareto 集合に含まれてしまう

りでは分散環境で競合する協調タスクを直接扱うことがでことがわかる．行動 b に対して利得の向上は少ししか期待きる効果的な方法は知られていない．

できないにもかかわらず，競合を引き起こすリスクが大きい行動 a は望ましくない．そこで我々は α-domination 戦
略 [4] を用いることにする．α-domination 戦略は多目的な要素に対して，dominance 判定に弱いトレードオフを導入する手法で，dominance 抵抗解を pareto 集合から効率よく排除できる有効性が示されている．各価値関数間のトレーまた MAS ではないが多目的性の取り扱いについては辞書的順序を利用した手法 [2] や目標領域に平均報酬ベクトルを指向する強化学習 [5] がある。これらの手法は意志決定そのものを多目的の観点から行うものであるが，我々は優先順位付の多目的性を利用して行動選択の候補を効率的に絞り込むことを考えている．

ドオフ比が厳密に設定できないことはしばしば言われることだが、その上下限を設定することは比較的容易である． 4∆Qc
1
αtc ≤≤∆Qt
αct(9)

ここで ∆Qc と ∆Qt は Qc と Qt の変化量である
この弱トレードオフ関係を用いて図 4(右) に示すように「Qc の観点で b が a に少々劣っていても、Qt の観点で b が分散データベースシステムへの応用
本章では資源共有問題のベンチマークとして分散データベースシステム (DDBs) のトランザクション処理をモデル化した問題に提案手法を適用し，有効性と有用性を示す．

4.1 トランザクション処理とデッドロック

a におおいに勝る」場合は a を集合から排除する．この場

トランザクション処理とは，並列処理において個別に行合を b が a を α-dominate するといい，この集合を α-paretoわれる動作の集合からなる計算処理をいい，統一概念とし集合という．我々は α-pareto 集合を実行可能な行動集合て原子性，一貫性，分離性，持続性という ACID 特性が定(FAS) として利用することにする．図 5 に意志決定アルゴリズムを略記する．

義されている．各トランザクションはジョブが与えられる

また α-domination 戦略は探索効率を向上させる効果もことをアボートという．アボートした処理は全て元通りに期待できる．ε-greedy 戦略などのランダム性を用いた探索戦略は単純さなどから良く用いられるが，行動空間が大きい場合，空間全域をランダムに探索するのは効果的ではない．また，他のエージェントとの競合を考慮すると影響の大きい行動をランダムに選択することは望ましくない．と処理を開始し，処理の終了をコミット，途中で中止する
戻さなければならないなどデータの一貫性を維持するために参照や書換えが行われるデータをロックする方法が広く使用されている [1]．あるトランザクションがデータをロックすると，他のトランザクションはそのデータにアクセスできなくなりロックが外されるまで待機状態に入る．

そこであるトレードオフの下で選別された FAS を探索空

このとき資源を一定時間待ったトランザクションをデッ間として利用することにより，探索による競合の発生と無ドロック状態にあるとみなし，強制的にアボートさせる方駄な探索を低減し，効率よく学習することが期待できる． 法をタイムアウトといい，単純かつ実用的なため広く用いられている．しかし，動的で不確実な環境において良い性

3.3 関連研究

能を引き出すタイムアウトの設定は非常に難しい [11]．

環境を共有する意志決定エージェントで構成する MAS
はゲーム理論の分野で古くから研究が行われ，特に Nash

4.2 実験設定

均衡という観点から多くの有益な分析や知見が得られていトランザクション自体の処理は詳細を観察することはでる [8]．しかしゲーム理論の観点では環境の完全観測性がきない．そこで本研究では図 6 に示す DDBs の各サイト

前提にあり，資源共有問題のように情報が限定された環境をエージェントとし，そこから生成されるトランザクショ

Performance of DB (uniform 5site, MPL10-200)
12Database

Site

Table3: 実験パラメータ

Transaction

Fig.6: 実験モデル

パラメータ
データベースサイト数
コミットまでに必要な資源数
並列動作トランザクション数
CPU 処理時間
I/O 処理時間
他サイトへのリクエスト率
自サイトへのメッセージ遅延
多サイトへのメッセージ遅延値
5810〜200
15 ms
35 ms
40 ％
1 ms
100 msThroughput

Network-domination
Q-Learning
Fix Best

1086

Theoretical Limit

42
20406080 100 120 140 160 180 200
MPL

Fig.7: MPL10 から 200 の均一環境におけるスループット性能

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

α-domination 戦略の有効性を示すための実験では下式のトランザクションはコミットまでに複数の様々なデータように提案する副目的の報酬を主目的の報酬と α で重み付の確保を必要とするため，式 (2) をそのまま政策とするこけ線形和することにより単目的化する Q-learning(Linearlyとはできない．そこでトランザクション処理の特性を利用

Weighted Sum Q, LWS-Q) との比較を行う．

して確保データ数に関する関数としてタイムアウト政策を

rn = (1 − α)commitn + α ∑ timeoutn (si )定義する [7]．a, b は政策パラメータである．

timeout(si ) = a ∗ bi−4,i = 1, · · · , m.

(11)

i4.3 実験結果と考察(10)

各サイトは政策パラメータ (a,b) を決定し，一定期間環境均一環境において各 MPL の時のスループット性能を図7 に示す．従来運用で良く用いられている固定タイムアウにトランザクションを生成してスループットを受け取る． ト政策は最良の値を選択しても十分な性能が得られていな実験では表 3 に示す DDBs において各サイトの保持データ数が 100 の均一環境と，ひとつのサイトが 100 で他の4 サイトが 300 の不均一環境に対して適用した．これは組合せ最良解を計算するために単純な設定を用いている．また並列実行数 (MPL:Multi Programming Level) を固定した定常環境で 10 から 200 まで実験した．MPL が大きいほど環境が混雑しデッドロックが起こりやすくなる．
実験期間は全体で 1.5×10 9ms，評価は最終 1.0×10 7ms間の性能を示す．予備実験に基づき強化学習パラメータは学習率 0.1，割引率 0.9，α-domination 戦略の α は均一環境
では MPL が 10 から 100 で 0.005，110 から 200 で 0.001を用いた．不均一環境では全 MPL で 0.0001 を用いた．政策パラメータは a は 500 間隔で (500,7500) の範囲を 15 段いことがわかる．提案手法はほぼ全ての MPL においてスループット最大化を行う Q-learning を上回り，限界性能である組合せ最良解と同等の性能を獲得したことから，副目的の導入と α-domination 戦略による行動空間の絞り込みの有効性が確認された．
均一環境で MPL50 の時の学習曲線を図 8 に示す．学習序盤における性能差は，α-domination 戦略により早い段階から多くの価値の低い行動がドミネイトされるためと考えられる．報酬は他のサイトの政策により大きく変動するため，学習序盤の探索的な行動によって競合が起きやすいが，α-pareto 集合である FAS に有望な行動が登録されることでこの競合が早期に解消できている．また学習速度の違いは探索の効率化によるものと考えられる．

階，b は 0.05 間隔で (1.05,1.5) の範囲を 10 段階に離散化

不均一環境において各 MPL の時のスループット性能をした．従って各サイトは行動数 150 から意志決定し，シス

図 9 に示す．極端に混雑するサイトと他の 4 サイトとのテム全体ではサイト数 N に対して 150N の組合せとなる．

性能はトレードオフ関係にある．組み合わせ最良解は混雑

図 7 から図 10 は 10 試行の平均値をプロットしている．

するサイトをある程度犠牲にすることで全体の性能を向従来運用に用いられる固定値のタイムアウト政策 (Fix

上させる政策群であり，スループットは他のサイトの約 16
Performance of DB (unifrom 5site, MPL50)

Best) とスループット最大化を行う Q-learning 政策 (Q) と比較を行う．Fix Best は確保データ数に関係なく固定値ので離散的に探索して得られた最良値を示した．Q は各エージェントが部分タスクである処理数最大化 maxπn commitnを行い，競合は考慮しない．また限界性能を示すために，全サイトを一括管理の下で政策パラメータを離散的に全探索して得られた組合せ最良解も示す．これは分散環境
では実行不可能な方法であるが獲得性能の理論的な限界(Theoretical Limit) として示す．

8Throughput

タイムアウト期間をとるが，図 7 では (500,20000) の範囲

64-domination( = 0.005)
Q-Learning
1000 3000 5000 7000 9000 11000 13000 15000
step (x100000 msec)

Fig.8: MPL50 の均一環境における学習曲線．エラーバーは標準偏差を表す．

Performance of DB (uniform 5site, MPL100)

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

14-domination
LWS-Q

10

Theoretical Limit

864Throughput

Throughput

12
54

220

406080 100 120 140 160 180 200
MPL

Fig.9: MPL10 から 200 の不均一環境におけるスループット性能

10-510-410-3-35x10Fig.10: α とスループット性能との関係 (均一環境，MPL100)程度となる．提案手法ではそのような政策群の他に，ある以上のことから提案手法は LWS-Q と同様にトレードオ程度揃った政策群が学習される試行が確認された．このとフを用いるものの，α を適切に選択すれば LWS-Q よりもきスループットは他のサイトの約 13 程度となる．これは良い性能をロバストに獲得できることが確認された．

スループットの総計を観測できないことと実験パラメータなどの設定が同一ためであると考えられる．ただしスループットを最大化する Q-learning よりも性能は良い．

4.4 α に関する考察と実験

5 おわりに
我々は資源共有問題を対象に，競合回避のための副目的の導入と多目的意志決定の α-domination 戦略に基づく分散強化学習を提案した．資源共有問題は競合する協調タス

α-domination 戦略において α は主目的と副目的の間の弱いトレードオフ関係を表すパラメータで，獲得性能に影クに分類され，分散環境ではシステムタスクの達成が困難響する．本問題において MPL100 以下の場合は経験的にス提案手法を適用することでシステムタスクに関して良い性ループット性能を 1 向上させるために 200ms から 300ms能を獲得できることを DDBs の課題で実験的に示した．

であるが，優先順位付多目的意志決定問題にモデル化して程度までの待ち時間 ∑s timeout(s) の増加は許容できるが，本論文では問題の特性上，状態空間について議論しなそれ以上は費用対効果が悪いことがわかっている [6, 7]． かった．今後は状況の変化に対する対応などを考慮し，競また待ち時間が増加するならスループット性能もかなり向上しないと許容しないといったように副目的を重視しすぎれば，性能に直結する主目的がないがしろになってしまう合する協調タスクの様々な課題に適用を試みる．

R EFERENCES[1] Bernstein, P., Newcomer, E. (1997) Principles of Transaction
Processing. Morgan Kaufmann Publishers.
れずに性能が急速に悪化し，3.0×10 −3 から 5.0×10 −3 程 [2] Gabor Z., Kalmar, Z., Szepesvari, C. (1998) Multi-criteria Reinforcement Learning, Proc. of the 15th International Conference度で適切なトレードオフ関係が得られて性能が良くなり，
onMachine Learning, 197–205.
小さくなるにつれて性能が悪化すると予想される．
[3] Hu, J., Wellman, M.P. (2000) Experimental Results on Qlearning for General-Sum Stochastic Games, Proc. of the 17th
均一環境において MPL100 の時，α を変化させたときのInternational Conference on Machine Learning, 407–414.
スループット性能を図 10 に示す．予想通り適切なトレー[4] Ikeda, K., Kita, H., Kobayashi, S. (2001) Failure of Paretoドオフ比である 3.0×10 −3 から 5.0×10 −3 で良い性能を示
Based MOEAS: Does Non-Dominated Really Mean Near toOptimal?, Proc. of the 2001 Congress on Evolutionary Comした．副目的を重視しすぎる α が大きい設定は本来用い
putation, 957–962.
ないが，実験では全サイトが短いタイムアウト政策を選択 [5] Mannor, S., Shimkin, N. (2002) The Steering Approach for
し，急激な性能悪化が見られた．α を小さくしていくにつMulti-Criteria Reinforcement Learning, Advances in Neural Information Processing Systems 14, 1563—1570.
れて α-pareto 集合は増加していくが，相互作用を介して[6] 大金義規 (2003) 分散データベースにおける協調機構の実現，競合しづらい行動が結果的に学習されるために，性能の低
東京工業大学知能システム科学専攻修士学位論文．
下は徐々に起こることが確認された．
[7] 大金義規，木村元，小林重信 (2003): 分散データベースにおける協調機構の実現，30th SICE Symposium on Intelligent
α を適切に調節することは適切なトレードオフを求めてSystems, 73–78.
いることと同義である．そこで α をトレードオフ比とし [8] Osborne, M.J., Rubinstein, A. (1994) A Cource in Game Theory., The MIT Press.
た LWS-Q において同様の性能が得られるはずである．し[9] Peshkin, L., Kim, K., Meuleau, N., Kaelbling, L. (2000) Learnかし図 8 の学習曲線について述べたように，大きな行動空ing to Cooperative via Policy Search, Proc. of 16th Conference
on Uncertainty in Artificial Intelligence, 489–496.
間での探索の困難さなどから全体的に性能が低いことと，[10] Sutton, R.S., Barto, A. (1998) Reinforcement Learning: An
特に α が小さいときは部分タスクが重視されて競合が発Introduction. A Bradford Book, The MIT Press.と考えられる．従って，α が大きすぎると主目的が達成さ生し，性能が低下していく様子が確認されたという点で提案手法の結果と異なることがわかった．

[11] 魚田勝臣, 小碇暉雄.(1993): データベース, 日科技連.