Q学習を用いたエージェント交渉モデル

Q 学習を用いたエージェント交渉モデル

Agent-based Negotiation with Q-learning

北浦愼也 坂間千秋

Shinya Kitaura Chiaki Sakama

和歌山大学システム工学研究科

Graduate School of Systems Engineering, Wakayama University

Abstract: In this study, we consider a nonzero-sum bargaining game with imperfect information in which

two players exchange resources to achieve individual goals. One of the two players learns how to achieve the goal through repeated games using Q-learing. Experiment results show that a learning player can learn winning strategies against cooperative and non-cooperative players.

1. はじめに

複数のエージェントが個別の目標を持つ環境にお いては、合意形成を行うためのエージェント間交渉 が行われる。各エージェントは、自らの目標を達成 するための交渉戦略を持ち、交渉のプロセスで相手 エージェントを含む環境を学習することで、交渉を 有利に進めることができる。エージェント間交渉に おいて交渉戦略を学習する研究は、これまでにもい くつか行われている。大竹ら[1]はインターネットオ ークションで、自動入札を行うエージェントが強化 学習の一手法である Q 学習によって入札戦略を獲得 するアルゴリズムを提案している。伊藤ら[2] は非 ゼロ和二人ゲームを繰り返し行う状況で、過去の対 戦履歴に基づいてプレイヤーが利得を最大にするた めの最適戦略を Q 学習を用いて計算している。 Lazaric ら[3]は売り手と買い手の間の交渉ゲームに おいて Q 学習エージェントを導入し、学習率を動的 に変化させることで収束率が改善されることを報告 している。Efstathiou ら[4]は資源交換を行うトレー ディングゲームで、自らの目標を達成するための行 動戦略を Sarsa 学習によって実現し、その効果を実 験により検証している。 本研究では、2 人のエージェントが各々の目標を 達成するために資源交換を行う非ゼロ和不完全情報 ゲームにおいて、エージェントが Q 学習を用いて行 動戦略を学習する方法を導入し、その効果を実験に より確認する。以下では、2 章で交渉ゲームの説明 を行い、3 章でエージェントの学習方法と対戦相手 エージェントについて述べる。4 章で実験内容につ いて説明し、5 章で実験結果に基づく考察を行う。 最後に 6 章でまとめと今後の課題について述べる。

2. 交渉ゲーム

エージェント A とエージェント B の 2 人が、3 つ の資源(牛、馬、羊)のうちの 2 つを 5 頭ずつ集める ことを目標とする交渉取引を行う。これを以下では 交渉ゲームと呼ぶ。交渉ゲームは以下のステップで 行われる。 1．各エージェントは初期状態で牛、馬、羊を 2 頭 ずつ所持している。 2. 各エージェントは提案を行う前に一定数の資源 を取得または喪失する。 3. 各プレイヤーは自らが持つ資源１頭と相手プレ イヤーが持つ資源１頭との交換を提案し、相手プ レイヤーはそれに対する応答(受諾・拒否)を行う。 4. 上記ステップ 2, 3 をエージェント A, B について 交互に繰り返し、２人のうち一方の資源が目標数 に達するとゲームが終了する。 ゲーム開始後、各エージェントは目標の資源を集 めるために資源の交換の提案を行う。提案が受諾さ れた場合は資源の交換が行われ、拒否された場合は 各エージェントが所持する資源は変化しない。２人 のエージェントはそれぞれ３つの資源のうちの２つ を集めることを目標とするため、３つの資源のうち の一つは A, B が共に必要な資源となる。したがっ て、取引においては利害が衝突し、資源の交換に対 する提案が相手に受け入れられるとは限らない。な お、ゲームの過程で資源の交換を行う前に手持ちの 資源の数を調節している（ステップ２）。ここでは、 手持ちの資源の総数が 10 以下なら資源をランダム に 2 つ追加し、15 以上ならランダムに 1 つ削除し、 人工知能学会研究会資料 SIG-ALST-B402-04

11～14 なら 2 分の 1 の確率で手持ちの資源を 1 つ削 除、または 2 つ追加するという更新を行っている。 資源を追加するのは、ゲーム開始直後のように各エ ージェントの所持する資源が２つとも目標数に不足 している状態では、有効な資源の交換の提案ができ ないためである。また、資源を削除するのは追加の みを行うと、資源が単調に増え続け、取引が成功し なくてもゲームが終了する可能性があるためである。 交渉ゲームの過程では、各エージェントは資源交 換の履歴は保持することができるが、ステップ２で 資源の数の調整が行われるため、相手エージェント が所持する資源の数についての情報はもっていない。 したがって、自らの提案を決める際に相手の利益が わからないため、非ゼロ和不完全情報ゲームの一つ と考えることができる。

3. エージェント

3.1

Q

学習エージェント

Q 学習は強化学習の一つとして知られており、あ る状態においてエージェントの行動の有効性を示す Q 値を導入し、エージェントが行動するたびにその 値を更新することで最適な行動選択を学習するとい うものである[5]。交渉ゲームでは、エージェント A が所持する資源の状態 S とそこで行った提案 P に基 づく評価値 Q(S, P)を計算し、以下の式によってその 値を更新する。 Q(S,P):= Q(S,P) + α・[R + γmaxQ(S',P')－Q(S,P) ] … (†) (S: 現状態、P: S における提案、S':次状態、P': S'にお ける提案、R:報酬、α:学習率、γ:割引率) エージェント A は、現在の状態 S において提案 P を 行う。エージェント B が提案に応じた場合に状態 S は次状態 S' に変化し、次状態 S' で可能な提案 P' の 中で Q(S',P')の値が最も大きい提案を用いて評価値 の更新を行う。学習は提案が相手に受け入れられる たびに行い、提案が相手に断られた場合は行わない。 報酬 R は交渉ゲームが終了した時点において与えら れ、エージェント A が先にゴールしたときは＋1000、 エージェント B が先にゴールしたときは－100、エ ージェント A とエージェント B が同時にゴールした ときは＋500 とする。ゲームが終了していない段階 では R=0 とする。学習率αと割引率γは 0≦α,γ≦ 1 を満たす定数である。 Q 学習を行うエージェントは、提案、応答を決め るルールとして、ε-グリード手法を採用している。 これは、現在とれる提案の中から、式(†)によって 算出される Q(S,P)の値が最も大きいものを確率 1-ε で選び、確率εで現在とれる提案の中からランダム に選ぶものである。

3.2 対戦相手エージェント

学習エージェントＡの対戦相手 B として、非協力 的なエージェントと、協力的なエージェントの 2 種類を 考える。非協力的なエージェントは、自らが不必要 な資源を自らが必要な資源と交換する提案を行い、 自らが必要な資源を相手から要求された場合は提案 には応じない。必要な資源でも必要数以上持ってい る場合は、超過した分は不必要な資源として扱う。 つまり、自らの利益になるような提案以外は拒絶す る。一方、協力的なエージェントは、自らの提案の 仕方は非協力的なエージェントと同じであるが、相 手からの提案に対しては自らが損をしない限り応じ る。例えば、エージェントＢの目標が牛５頭、羊５ 頭の場合、牛３頭、羊３頭を所持している状態で、 エージェントＡからＡの所持する羊１頭とＢの所持 する牛１頭の交換を提案された場合、Ｂにとってこ の交換は損にはならないので応じる。

4. 実験

実験では「学習ゲーム」と「対戦ゲーム」の２種 類のゲームを行う。「学習ゲーム」は学習エージェン ト A に学習させる目的で行う。このゲームでは、学 習率が 0 になるまで繰り返しゲームを行う。「対戦ゲ ーム」は、Q 学習の効果を評価する目的で行う。こ のゲームでは、学習ゲームの結果得られた戦略を固 定して、対戦相手とゲームを 1 万回行う。この 2 種 類のゲームのセットを 10 回行い、その平均勝率、平 均負け率、学習ゲームにおける平均勝率の変化を調 べる。学習率の増減量は 0.01, 0.002 の２パターン、 学習率は 5 戦中 5 勝、７戦中７勝、10 戦中 10 勝し たとき減少し、5 戦中 5 敗、7 戦中 7 敗、10 戦中 10 敗したときに増加する 3 パターンを用意し、学習率 の増減量と増減する条件を組み合わせた 6 パターン の実験を行う。また、ε-グリード手法で用いられる εは 0～0.05 の値をとり、学習率が増減するタイミ ングで 0.01 増減する。実験における各エージェント の設定は以下の通り。 エージェントＡ（学習エージェント） ・最初の所持資源…羊、牛、馬を 2 頭ずつ ・目標状態…牛 5,羊 5

・学習エージェントの学習率 α=0.1 ・学習エージェントの割引率 γ=0.9 ・εの値 ε=0.03 ・エージェント A の学習前の提案、応答のルールは 対戦相手エージェント B と同じ状態から開始 エージェントＢ（対戦相手） ・最初の所持資源…羊、牛、馬を 2 頭ずつ ・目標状態…牛 5,馬 5、または、馬 5,羊 5 ・戦略…非協力的または協力的 エージェントＢの目標状態は、ゲームごとに変更さ れる。これは、同じ目標状態で繰り返しゲームを行 うと相手の提案から目標状態の予測が成り立つから である。エージェントＢがＡと同じ目標を持つと交 渉は成り立たないので、Ｂの目標は (牛 5,馬 5), (馬 5,羊 5)の２種類とした。いずれの目標もＡの目 標と共通の資源を一つ含んでいる。

5. 実験結果

5.1 学習前のゲーム結果

学習エージェントＡが Q 学習を行う前に２種類の 対戦相手エージェントＢと対戦を１万回行ったゲー ム結果の平均を図 1 に示す。図 1 の縦軸は勝率と負 け率、横軸は対戦相手エージェントを表す。ゲーム の勝率と負け率がほぼ等しくなっているが、これは 学習前のエージェントは対戦相手エージェントと同 じ提案、応答ルールでゲームを行うからである。ま た、勝ち負けのほかに同時に目標を達成した状態の 引き分けがあるが、それは表示していないため、勝 率と負け率を足しても 100％にならない。 図 1 ２種類の対戦相手エージェント B との 学習前の対戦ゲームの勝率(点線)と負け率(実線)

5.2 非協力的なエージェント

非協力的なエージェントとのゲームの結果を示す。 ただし、7 戦 7 勝または 7 戦 7 敗したときに学習率 を増減させる設定、10 戦 10 勝または 10 戦 10 敗し たときに学習率を増減させる設定ではゲームが終了 しなかった。これは、対戦相手エージェントの提案、 応答ルールが強力なため、終了条件を満たすことが 困難であるからだと考えられる。 図２は、学習ゲームにおける学習エージェントの 勝率の変化を 3000 ゲームごとに表示している。ここ で、縦軸は勝率を横軸はゲーム数を表している。勝 率の算出方法は現在の勝利数を現在のゲーム数で割 ることで求めた。学習ゲームで交渉が終了するまで の平均交渉回数は 6～7 回で、学習前と学習後の間に 交渉回数の変化は見られなかった。学習ゲームでは 学習率が０になるまで繰り返しゲームを行っている が、10 ゲームを行った結果、学習率が０になるまで に平均して 73967 回の繰り返しゲームが行われた。 図３は、学習エージェントと非協力的なエージェ ントの対戦ゲームにおける平均勝率と負け率を表し ている。ここで、縦軸は勝率と負け率を、横軸はゲ ームの設定パターンを表す。例えば、5-5-0.01 は 5 戦 5 勝、または 5 戦 5 敗すると学習率を 0.01 増減す るパターンを表す。 図 2 非協力的なエージェントとの学習ゲーム時の 勝率の変化 図 3 非協力的なエージェントとの対戦ゲームの 勝率(点線)と負け率(実線) 43 43.5 44 44.5 45 45.5 46 46.5 非協力的 協力的 40 41 42 43 44 45 46 38 40 42 44 46 48 5‐5‐0.01 5‐5‐0.002

5.3 協力的なエージェント

協力的なエージェントとのゲーム結果を図 4、図 5 に示す。図４は、学習ゲームでの勝率の変化を 200 ゲームごとに表し、縦軸は勝率を横軸はゲーム数を 表している。勝率の算出方法は図 2 と共通である。 学習ゲーム時の平均交渉回数は 4～5 回であり、学習 の前後で変化は見られなかった。また、10 ゲームを 行った結果、学習率が０になるまでに平均して 2963 回の繰り返しゲームが行われた。図５は、学習エー ジェントと協力的なエージェントの対戦ゲームにお ける平均勝率と負け率を表している。ここで、縦軸 は勝率と負け率を、横軸はゲームの設定パターンを 表す。 図 4 協力的なエージェントとのゲームの平均勝率 図 5 協力的なエージェントとの学習ゲーム時の 勝率(点線)と負け率(実線)

5.4 考察

図 2 より、非協力的なエージェントとの学習ゲー ムの平均勝率は、最初に一時的に下がった後は、ゆ るやかに増加している。この理由は、非協力的なエ ージェントとの対戦では、非協力的な提案、応答の ルールにはこれ以上強くなる可能性がなく、一度別 のルールを探す必要があり、その過程で勝率が下が ったのではないかと考えられる。一方、図４より、 協力的なエージェントとのゲームの勝率は単調に増 加し、1800 ゲーム以降は横ばいになっている。これ は、協力的なエージェントとの対戦では、協力的な 提案、応答のルールには最初から強くなる余地が存 在したためであると考えられる。 両者を比較すると、協力的なエージェントと対戦 した場合は、少ないゲーム数で高い勝率に到達して いる。この理由は、Q 学習エージェントは対戦相手 エージェントが提案を受け入れた場合に学習を行う ので、協力的なエージェントの方が提案を受け入れ やすく、学習を行う回数が多くなったからだと考え られる。 次に、図 3、図 5 より、対戦ゲームにおいては非 協力的なエージェント、協力的なエージェントの両 方のゲームで学習前の対戦(図１)と比較して勝率が 上がっている。両者を比較すると、非協力的なエー ジェントよりも協力的なエージェントに対しての勝 率が相対的に高くなっている。これは、協力的なエ ージェントは学習エージェントの提案に応じやすい ので、学習の効果が上がり目標に到達する可能性が 増えたためと考えられる。また、学習率の変化の違 いは勝率にあまり影響を与えていない。

6. おわりに

本研究では、非ゼロ和２人不完全情報ゲームにお いて、エージェントが交渉を有利に行うために Q 学 習を用いて学習する方法を提案した。実験の結果、 非協力的・協力的な対戦相手いずれに対しても学習 の 効 果 と 勝 率 の 向 上 を 確 認 す る こ と が で き た 。 Efstathiou ら[3]も資源交換を行うトレーディングゲ ームにおける学習エージェントを実装しているが、 [3]では対戦相手の目標が固定されているため、学習 エージェントは学習ゲームの終了時点で対戦相手の 目標を予想しやすくなっていると考えられる。一方、 本研究では対戦相手の目標をゲーム毎に変更してい るため、予想が立てにくい状況で学習を行っている。 また、[3]は Q 学習ではなく、Sarsa 学習を使用して いる。交渉ゲームでは Q 学習よりも Sarsa 学習の方 が優れているという研究報告もある[6]が、この比較 では交渉回数が定まったゲームにおける比較をして いるので、本研究における交渉ゲームの設定とは異 なる。今後は、Q 学習の代わりに Sarsa 学習を使っ た場合の学習効果の比較と、対戦相手エージェント の戦略を変更して実験を行う予定である。 50 52 54 56 58 60 62 64 200 800 1400 2000 2600 0 10 20 30 40 50 60 70

参考文献

[１] 大竹麗央、西田豊明: "強化学習を用いた交渉戦 略学習アルゴリズム", 電子情報通信学会技術 報告，人工知能と知識処理 101(210), pp. 37-44, 2001-07-16 (2001) [２] 伊藤昭、水野将史、松本達明、寺田和憲: "マル チエージェント強化学習による交渉問題への アプローチ", 電子情報通信学会技術研究報告. AI, 人工知能と知識処理 103(725), pp. 19-24, 2004-03-09 (2004)

[３] Lazaric, A., Munoz de Cote, E. and Gatti, N.: “Reinforcement learning in extensive form games with incomplete information: the bargaining case study”, Proc. AAMAS’07, Article No.46 (2007) [４] Efstathiou, I. and Lemon, O.: “Learning

non-cooperative behaviour for dialogue agents”,

Proc. SIGDIAL 2014, pp. 60–68 (2014)

[５] Sutton, R. S. and Barto, A. G. 著(三上、皆川共訳): 「強化学習」, 森北出版 (2000)

[６] 藤田裕典、高玉圭樹: "バーゲニングゲームにお ける強化学習エージェントの解析", 第 16 回自 由 分 散 シ ス テ ム ・ シ ン ポ ジ ウ ム 予 稿 集 , pp.259-264 (2004)