鏡像を利用した追跡問題の高速学習 Accelerating Reinforcement

DEIM Forum 2016 C7-5
鏡像を利用した追跡問題の高速学習
Accelerating Reinforcement Learning by Mirror Images
北尾 健大†
三浦 孝夫†
† 法政大学 理工学部 184–8584 東京都小金井市梶野町 3-7-2
E-mail: †[email protected], ††[email protected]
あらまし 本研究では，強化学習の代表的な手法の Q 学習を使用して，追跡問題のための学習速度の向上手法を提案
する．本研究のアイデアは，鏡像による対称性を利用して，フィールドの Q 値を学習することにある．このことで左
右の対象差のみを伴う学習をすることが可能である．また，Q 値の同時更新による収束性についても論じる．
In this investigation we propose how to accelerate Q-learning which is one of the most successful reinforcement
learning methods using mirror images for hunting problems. Mirror images have symmetric differences on right and
left views, they allow us to accelerate Q-learning dramatically. In addition, we show Q-values’ convergence while
they are kept updated during the process.
キーワード
強化学習，Q 学習，同時更新，鏡像
1. 前 書 き
今日のセンサ技術の発達により広範囲の環境を正確かつ，効
(2) 提案手法では学習精度の微かな悪化のみで，鏡が
1 枚のとき収束速度が 2 倍，2 枚のとき収束速度が 3
倍に向上する．
率的に知覚することが可能である．特に高性能センサは自律的
(3) 鏡がない Q 学習が収束するならば，提案手法を収
に解決したい問題に適した知識や戦略を得るために，環境から
束することを証明する．
大量の情報を集めることができる．
知識や戦略を獲得するための学習方法として様々な方法が提
案されている．強化学習はその中でも強力な学習方法の 1 つと
して知られている [5][7]. なぜならば，訓練データを必要とせ
ず，環境からの報酬のみで自動的に知識を抽出できるためであ
る．目標獲物に対して動作主 (エージェント) がこれを追跡し捕
獲するために取るべき戦略を選択する問題を，追跡問題という．
多くの場合，決定的な解が無いため，機械学習的手法に基づい
て戦略で追跡問題を解決する．
本研究では，追跡問題を強化学習の 1 つである Q 学習を利
用する．Q 学習はある問題に対して，柔軟な解を得るために訓
練データを使用しない，教師なしで学習する方法である．加え
て，常に最適な解を得ることが重要である．しかし，一般的に
効率よく解を得るのは困難である．
過去の追跡問題の学習を高速化するための研究 [4] として，
エージェントの知覚範囲の制限 [3] や粗野化 [2] を行い，状態数
を減らす方法がとられる. しかし，状態数の減少は学習精度の
悪化を生じさせる．
本研究では追跡問題の学習精度を維持したまま，学習速度を
高速化する手法を提案する．主なアイデアは鏡像イメージを利
第 2 章で強化学習と Q 学習について述べ，第 3 章で今回扱う
追跡問題を定義する．第 4 章で提案手法の説明を行い，第 5 章
で提案手法の有用性を論じ、第 6 章で結論とする．
2. 強化学習の基本要素と Q 学習
2. 1 強 化 学 習
強化学習では，エージェントはセンサなどによって現在の環
境を知覚し，何らかの行動を選択・実行しながら状態を遷移し
て，目的を達成する．一般的な手法として Q 学習や TD 学習が
挙げられる．ここでは状態を離散値として扱い、現在の時刻 t
における状態 st ，行動 at とし，次の状態の時刻 t+1 とすると
状態は st+1 となる. 状態間の遷移確率 pastt，s
t+1
と表すと，こ
れは条件確率として記述できる.
pastt,st+1 = P {st+1 |st ，at ，st−1 ，at−1・
・
・s0 ，a0 }
このように n ステップ前まで考慮している場合を n 重マルコ
フ過程と呼ぶ．また，1 ステップ前までを考慮することを (単
純) マルコフ過程と呼び下記の式で表す．
pastt,st+1 = P {st+1 |st , at }
用して同時学習を実行することにある．本研究の貢献は以下の
3 つである．
エージェントが何らかの行動 a を決定することで状態が遷移
し，それに依存して何らかの報酬 (正負を含める) を得る．この
(1) 追跡問題を通して，学習率におけるトレードオフ
ような離散マルコフ決定過程をもとにした逐次的な決定過程の
の関係 (収束速度と学習精度) を示す．学習速度の向上
ことをマルコフ決定過程と呼ぶ．
は学習精度の悪化を引き起こす．
状態ｓにおいて実行可能な行動 A(s) がいくつも存在すると
き，実行すべき行動の選択基準を政策という．政策は，状態 s
ジェントによる追跡問題を扱う. 追跡問題は m × m の格子状
において行動 a を行う確率π (s,a) で表現される. エージェント
の 2 次元空間のフィールドで実行する. ハンタエージェントと
は問題を効率的に解く政策や最終的に受け取る報酬を最大化さ
獲物エージェント，各 1 体ずつランダムに配置し，各エージェ
せるような政策を獲得するようになる.
ントが同時に行動を選択実行する. エージェントの選択できる
強化学習では，解決したい問題に対して，目標を設定する.
行動として，上下左右のどれか 1 マスの移動，その場に停滞の
目標に合わせて報酬を決定し，報酬は知覚した状態において何
5 種類から選択可能である. ハンタエージェントは学習しながら
の行動を選択したにより報酬を獲得する. この報酬の総和を最
それを行動選択に利用，獲物エージェントは無作為に行動を選
終的に最大化することが強化学習の目的である. しかし報酬は
択する. ハンタエージェントは獲物エージェントを知覚すると
選択・実行した行動が後続の報酬に影響することが考えられる.
きハンタ自身を中心とした相対位置で知覚するものとする. 各
この遅延報酬を考慮して報酬を最大化したい．
エージェントが隣り合った場合を捕獲とし，ゲームを終了とす
強化学習では報酬を使いルールの価値 (状態行動対) を決定
る. 捕獲した場合に正の報酬，捕獲にできなければ負の報酬を
する．特に，本研究で使用する Q 学習では推定値ベースの価値
与える. エージェント同士が同じマスに移動してしまった場合，
Q を利用する．すなわち，ある状態においてある行動を実行す
お互い元のマスに戻りまた，外壁は超えられないものとする.
れば，どれだけの報酬を得ることができるかの期待値を Q は表
図 1 のような，3 × 3 フィールドの追跡問題を考える. 各エー
している．ここで状態 s, 行動 a の時の価値を Q(s,a) とすると，
ジェントの初期配置として，ハンタエージェント (hunter agent)
と Q 値は適切に更新されば最適な期待報酬値に近づいていく．
は (2,1)，獲物エージェント (prey agent) は (3,3) とする. この
適切な評価値に近づけるためには，報酬 (直接的な報酬と遅延
時点で，ハンタエージェントは獲物を相対的に知覚する. 初期配
報酬を含めた) を手掛かりに試行錯誤しながら更新しなければ
置の図 1 と相対的に獲物を知覚したときの図 2 を示す. そのあ
ならない．
エージェントはルールの価値を政策に変換して，その政策を
もとに行動に決定する．しかし，政策を行動選択手法に変更す
るのではなく直接ルールの価値から行動を選択することが可
能である．主な行動選択手法として「グリーディ手法」「ε-グ
リーディ手法」「ソフトマックス手法」などがある [7].
2. 2 Q 学 習
強化学習の代表的な手法に，Q 学習がある．Q 学習は，Q 値
を報酬の推定値とみなして更新していく学習法である．Q 学習
には 2 つの特徴を持ち，1 つ目にベルマン方程式と呼ばれる手
法により，Q 値の更新を行う．2 つ目に政策として Q 値が最大
の行動を選択する前提の更新式になっている点である．
′
′
Q(s, a) ← Q(s, a) + α[r + γ ′max ′ Q(s , a ) − Q(s, a)]
a ∈A(s )
ここで，s は現在の状態，a は状態 s のときにとる行動であり，
図2
ハンタの相対視野 1
図 1 エージェント初期配置図
と，ハンタエージェントは報酬の期待値を最大化するような行
動，獲物はランダムに行動を選択する. この例ではハンタエー
ジェントは右，獲物エージェントは左に移動すると，お互いは
隣り合うので捕獲となり，正の報酬を獲得してこのゲームは終
了になる. その時のフィールドの図 3 と相対視野の図 4 を示す.
Q(s,a) はそのときの価値を表している. 同じく Q(s’,a’) のとき，
s’ は遷移先の状態，a’ はそのときのとった行動の価値を表現
している. また r は状態ｓから s’ へ遷移したに得られる報酬を
表しており，A(s’) は s’ において選択可能な行動の集合，α（
0<α<
= 1）は割引率を表している.
=γ<
= 1）は学習率，γ（0 <
Q 学習では Q 値を次の状態の中で選択可能なルール集合の
中で最大の値に近づくように更新している. すなわち最大の値
との誤差を小さくし，Q 値の精度を高めている. Q 学習はマル
図4
ハンタの相対視野 2
図 3 フィールドの概念図
コフ決定過程であり，学習率が適切に調節され，十分に学習が
行われると最適な評価値に収束することが証明されている [6].
4. 提 案 手 法
しかし学習規模が大きいほど更新すべき Q 値が多くなり，更新
効率が低下する [4]. また，学習できない範囲が増加し，学習範
囲の偏りが発生するため，Q 学習の特徴である収束が保証され
なくなってしまう問題がある [1][5].
4. 1 鏡像とその性質
現実世界で鏡の前に自分が立つと鏡の奥に，自分と同じ像が
現れる. 例えば右手を挙げると，鏡像は左手を挙げる. このよ
うな左右の方向の差のみを伴って実際に動きと対応している性
3. 追 跡 問 題
質を利用し，同時に複数の Q 値を更新することを考える. 限定
本研究では強化学習の標準的なタスクであるシングルエー
的ではあるが，1 つの動作が複数の学習を伴う事ができる. 本
研究では追跡問題を実行する格子上のフィールドを 2 次元座標
空間と考え，その中心に X 軸，Y 軸において鏡を仮想的に設け
る．鏡に映った獲物エージェントを，鏡像の獲物として，実物
を実物の獲物，実物のハンタエージェントをハンタと区別する.
仮想的な鏡を各エージェントは超えることができるとする. ハ
ンタと鏡像の獲物は同じマスに同時に存在する場合があるが，
その場合衝突は発生しないものとする. 本研究では鏡像の鏡像
は考えないものとする．たとえば y 軸に鏡 (図中の Mirror) を
仮想的に設けた状況を図 5 に示す. ハンタは右へ移動，実物の
獲物は左へ移動している状況とそのときのハンタと実像の獲物，
鏡像の獲物を表している.
図 6 干渉ありの概念図
4. 3 鏡像を利用した Q 学習の性質
鏡を複数枚並べたとき，1 回の行動で同じ Q 値を複数回更新
する．本論文ではこのことを干渉と呼ぶ．本来の Q 学習であ
れば，同時に複数個の Q 値を更新することはないので干渉は
発生しない. しかし提案手法では複数の鏡像が同じマスにいる
ために，ハンタから見た相対位置が重なるために同じ状態で知
覚してしまう. そのため，Q 値を更新する際に同じ Q 値を重複
して更新してしまう. 図 6 の場合，状態 (-2,-2) を重複して知
覚しているため，同じ Q 値を 2 回更新をする. Q 学習では 1
図 5 干渉なしの概念図
回の更新で同じ Q 値を複数回更新することを考慮しておらず，
収束の保証がなくなる. また，状態 (-2,-2) を 2 回更新している
各エージェントの配置は相対的である. 即ち，ハンタは相対
ため，本来あるべき Q 値の値とズレが発生する. ズレが発生す
位置でものを見るため，ハンタ自身を座標の中心とみなし，両
ることで，得られる知識や戦略の精度の悪化，この例では獲物
方の獲物を 2 つの状態，実像の獲物 (1,-2) と鏡像の獲物 (-2,-2)
エージェントを捕獲するまでの行動回数の増加を指す. それに
として知覚する. そのため更新できる Q 値が 2 つあり実像と鏡
加えて，収束したとして学習速度の低下が考えられる.
像の両方を同時に学習可能である.
学習速度がどの程度向上するかを調べるためにモデル化する
鏡を y 軸に 2 枚並べて仮想的に設置した状態では，鏡像の獲
ことを考える. 追跡問題において鏡像を利用して Q 値を同時に
物は 2 重写りのような同じマスに 2 体いるように見えるものと
並列で更新するとき，同時更新をプロセッサが実行していると
する. 鏡像同士なので衝突は発生しないことに注意したい. ハン
考えると，このようなマルチプロセッサ環境で問題を並列実行
タが知覚できる状態は (1,-2),(-2,-2),(-2,-2) の 3 つだが，学習
することと同じである. マルチプロセッサの下での性能向上を
位置は 2 種類となる. これも上と同じように更新できる Q 値は
調べるアムダールの法則がある [1]. 以下にその式を示す.
3 つある.
4. 2 鏡像を利用した Q 学習
鏡像の対称性を利用する Q 学習の利点として 3 つある. まず
更新量の増加が挙げられる. 通常 1 回の行動では 1 つの Q 学習
しか生じず，学習速度が遅い. しかし提案手法では，実物と鏡
像の獲物の数が増加するにつれて，更新量も増加，広範囲に学
習することが可能である.
2 つ目に学習速度の高速化が期待できる. 同じ位置をより多
く学習することから高速学習が可能となり，広範囲な領域を高
速に学習する.
3 つ目に鏡像の獲物の類似性である. 鏡を使用しているため，
S(N ) =
1
(1 − P ) +
ここで P は並列実行できる時間の割合を示し N はプロセッサー
数を表している．
もしすべてが並列実行可能であると仮定する (P=1.0) と式は
簡略化され以下になる．
S(N ) =
1
1
N
=N
Q 値の同時更新によって生じる遅れが生じないと仮定すると，
上記の式は鏡の枚数を増やすにしたがって，収束速度が向上す
鏡像は実像の獲物の動きに方向の対称さ (鏡の対称性) を伴って
ることを示している．
対応している．そのため，鏡像の獲物も実物の獲物と同じ動き
4. 4 Q 値の収束性
をするとみなすことができ，サンプリングやシミュレーション
とは異なってプロセスモデルを必要としない．
P
N
提案手法では Q 学習を使用しているため，学習率を適切に調
整し，充分に学習すれば収束するはずである [6]．しかし，同時
更新を行っているためこの収束の枠組みに入らない．本節では
ここで，鏡を使用していない通常の Q 学習の学習率の部分に当
Q 学習の収束性を維持することを証明する.
たる α(2−α) に注目する. もともと学習率 α は範囲 (0 < α <
= 1)
Q 学習の Q 値の収束の条件は十分に学習を行い，学習率
α(0 < α <
= 1) で時間:t の関数が以下の条件を満たすとき収束
であるため，α(2 − α) を α の関数と考えると α = 1 のとき，
することが証明されている [6].
え方と同じである．
∞
∑
α(t) = ∞,
∞
∑
t=0
式 (4) の α(2 − α) を α1 として，もう 1 枚鏡を重ねる状況を
α (t) < ∞
2
(1)
t=0
とき，特に学習率が次第に減少する場合，Q 学習では収束が保証
される．(例えば α(t) = (1/t) これは右記を満たす:
∑
考える (合計 3 枚) と式は以下のようになる. はじめに 2 回目の
更新を終えたときの式である.
学習率はその値が変動する場合と定数の場合がある. 変動する
かつ
最大値 1 をとる上に凸の関数である. よってこれは Q 学習の考
∑
Q(s, a)now ← Q(s, a)old
+ α1 [r + γ ′max ′ Q(s′ , a′ ) − Q(s, a)old ](5)
α(t) = ∞
α2 (t) = π 2 /6) 一方，α が定数である場合は，Q 値が
収束する保証はない．しかし上記の条件 (1) は十分条件であり
必要条件ではない．本研究で扱う追跡問題は，捕獲する獲物は
a ∈A(s )
3 回目の更新式は
Q(s, a)new ← Q(s, a)now
+ α[r + γ ′max ′ Q(s′ , a′ ) − Q(s, a)now ](6)
常に移動しているため非定常環境と考えることができるため，
a ∈A(s )
ここでは学習率を定数としてよい. また実際的には収束のため
に学習率が定数であっても，条件 (1) を満たすと仮定する．
鏡を軸上に 1 枚のみを設置した場合，同じ Q 値を同時に更
新することはない. そのため，同じタイミングで別々の Q 値を
式 (5) を式 (6) に代入すると
Q(s, a)new ← Q(s, a)old
+ (α1 + α − αα1 )
複数更新することになる. これは通常の Q 学習の更新式をベク
∗[r + γ ′max ′ Q(s′ , a′ ) − Q(s, a)old ] (7)
トルを使って更新しているとみなすことができる. 図 5 では下
記のようにモデル化できる.
[
[
α
Q((1, −2), 右)
Q((−2, −2), 右)
]
←
[
Q((1, −2), 右)
Q((−2, −2), 右)
となり，学習率の部分を α2 とすると漸化式の形で干渉のとき
]
の学習率を α2 = α1 + α − αα1 と表現できる.α2 を αn+1 ,α1
+
r + γ maxa′ ∈A((−1,2)) Q((−1, 2), a′ ) − Q((1, −2), 右)
′
a ∈A(s )
]
′′
を αn として，この漸化式を解くと一般項を求めることができ
ここで r が実像の獲物によって得られる報酬，r’ が鏡像のよっ
αn−1 = 1 − (1 − α)n (0 <
= αn−1 <
= 1) となる.n は鏡の重なって
いる枚数，言い換えると 1 回の更新で n 回同じ Q 値 Q(s,a) を
て得られる報酬，また a’ は実像が次状態で選択する行動，a”
更新した回数である. ここで 1 − (1 − α)n をβとすると式 (7) は
r + γ maxa′′ ∈A((−2,−2)) Q((−2, −2), a ) − Q((−2, −2), 右)
が鏡像が次状態で選択する行動としている．
Q(s, a)new ← Q(s, a)old
鏡を軸上で同じ場所に複数枚以上設置した場合，鏡像の獲物
+ β [r + γ ′max ′ Q(s′ , a′ ) − Q(s, a)old ](8)
は同じマスに重なっている鏡の数と同じ数存在する. このため，
このような干渉が発生する. 図 6 の例では，実像の状態の更新
a ∈A(s )
は鏡を使用しない通常の更新と同じである. しかし鏡像側の更
と表せる. ここでβの範囲は 0 < β <
= 1 となりこれまでと同様
に Q 学習と同じとして扱うことができる. よってこの場合では
新は獲物が重なっているため，通常の更新式と異なる. ここで
実像を更新する際は通常の更新式で学習率 α を使用し，鏡像で
鏡像側の更新の方を考える. まず，Qold が更新前の Q 値とし，
干渉が発生しているところでは学習率βの式で更新し，学習中
Qnow が 1 回目の更新を終えたところ，Qnew が 2 回目の更新
に 2 種類の学習率を使用して Q 値を更新する．また α と β は
を終えたところである.2 重に重なっている Q 値の 1 回目の更
0<
=α<
=β<
= 1 を満たす. 図 6 では，y 軸に 2 枚鏡が重なって
いるので n=2 とすると以下の式で表せる.
新は以下の式である.
[
Q(s, a)now ← Q(s, a)old
+ α[r + γ ′max ′ Q(s′ , a′ ) − Q(s, a)old ] (2)
Q((1, −2), 右)
Q((−2, −2), 右)
a ∈A(s )
←
[
[
+
[
2 回目の更新式は
]
α
0
0
α(2 − α)
r + γ maxa′ ∈A((1,2)) Q((−1, 2), a′ ) − Q((1, −2), 右)
′
]
Q((1, −2), 右)
Q((−2, −2), 右)
]
×
]
′′
r + γ maxa′′ ∈A((−1,2)) Q((−2, −2), a ) − Q((−2, −2), 右)
Q(s, a)new ← Q(s, a)now
′
ここで β が条件 (1) を満たすことを示す．β が Σt β(t) = ∞ な
′
+ α[r + γ ′max ′ Q(s , a ) − Q(s, a)now ](3)
a ∈A(s )
k+1 k
∞ と仮定したならば，β = 1 − (1 − α)n = Σn
α =
k=1 (−1)
n
k+1
k−1 <
n
<
α(1 + Σk=2 (−1)
C
α
)
α(1
+
Σ
C
)
α
2n と
n k
k=2 n k =
=
式 (2) を式 (3) で簡略化すると以下の式になる.
なる．これは，Σt β 2 (t) < Σt α2 (t) × 22n < ∞. を表している．
Q(s, a)new ← Q(s, a)old
+α(2 − α)[r + γ ′max ′ Q(s′ , a′ ) − Q(s, a)old ]
a ∈A(s )
2
ので， Σt α(t) = ∞ かつ α <
= β が仮定できる．また Σt α (t) <
(4)
よって α が条件 (1) を満たしているのであれば，β も (1) を満
たしていることを示した．
5. 実
験
5. 1 実 験 準 備
鏡のない Q 学習の Q 値は 10000 回目において 76%も上昇して
いるのに対して，X 軸と Y 軸に鏡を置いた Q 学習では 25000
回目において 5%しか上昇していない．
提案手法を実際に使用して有用性を示す. 本研究の実験では
表 1 Q 値 (α = 0.1)
干渉なし，干渉あり両方とも 10 × 10 のフィールドを使用し
獲物捕獲で+10 の報酬，捕獲できないとき-1 の報酬に設定す
る. 全ハンタエージェントの Q 値は初期値として小さな値の乱
数を使用し，フィールド全状態を知覚できるものとし，割引率
γ = 0.9, 行動選択手法を ϵ = 0.2 のϵ − グリーディ法 とする. 定
点観測する Q 値をハンタエージェントを中心とした相対位置
(-1,1) とし，サンプリング値は 20 万回の繰り返しを 1 セット
として，30 セット実行するときの 500 回ごとの平均値である．
また Q 値の更新順序は実像，鏡像関係なくランダムにする.
試行回数
500
5000
10000
15000
20000
25000
30000
35000
40000
45000
50000
100000
150000
200000
鏡なし
2.86
18.45(+546%)
28.00(+52)
32.00(+14)
33.75(+05)
34.68(+03)
35.13(+01)
36.24(+03)
36.67(+01)
37.29(+02)
39.88(+07)
70.27(+76)
79.49(+13)
78.82(-01)
試行回数
500
5000
10000
15000
20000
25000
30000
35000
40000
45000
50000
100000
150000
200000
鏡なし
5.14
27.26(+430%)
31.64(+16)
34.70(+10)
37.20(+07)
41.12(+11)
45.56(+11)
51.47(+13)
61.13(+19)
65.47(+07)
70.03(+07)
77.59(+11)
78.58(+01)
77.32(-02)
試行回数
500
5000
10000
15000
20000
25000
30000
35000
40000
45000
50000
100000
150000
200000
鏡なし
6.26
31.07(+396%)
36.34(+17)
43.07(+19)
48.28(+12)
55.76(+15)
64.55(+16)
68.92(+07)
74.32(+08)
75.96(+02)
76.44(+01)
76.56(+0)
77.77(+02)
77.61(+0)
X 軸
5.67
25.09(+342%)
37.45(+49)
45.21(+21)
49.55(+10)
54.41(+10)
61.55(+13)
66.29(+08)
70.52(+06)
74.95(+06)
75.99(+01)
79.22(+04)
79.95(+01)
80.06(+0)
Y 軸
4.43
23.80 (+437%)
36.87(+55)
46.06(+25)
51.68(+12)
56.73(+10)
61.69(+09)
64.87(+05)
69.48(+07)
74.17(+07)
75.32(+02)
79.33(+05)
78.97(+0)
79.23(+0)
X,Y 軸
6.74
38.57 (+472%)
55.80(+45)
67.61(+21)
72.90(+08)
76.53(+05)
79.18(+03)
78.35(-01)
79.76(+02)
80.09(+0)
80.30(+0)
80.98(+01)
80.11(-01)
80.59(+01 )
実験の評価方法として 2 つの指標を使用する．1 つ目に学習
済み Q 値を使用して，実物の獲物をどのくらいの行動回数で捕
表 2 Q 値 (α = 0.2)
獲したかを表す捕獲ステップである．これは回数が少ないほど
より良い政策が獲得できたとし，また Q 値の学習がうまく行わ
れたか，つまり得られた知識の質をみている．2 つ目に収束す
るまでの回数を表す収束ステップである．詳しくは下記 5.2 に
示す．
干渉なしの実験では通常の学習と比較して何倍収束したかを
鏡像の数，学習率の大きさから比較を行う. 鏡の置く位置を X
軸，Y 軸，X 軸と Y 軸の 3 種類とする. その場合，鏡像の数は
X 軸，Y 軸は 1 体，X 軸と Y 軸のときは鏡の反転を 2 回する
X 軸
10.45
37.80(+262%)
53.79(+42)
66.05(+23)
72.27(+09)
76.07(+05)
77.94(+02)
79.43(+02)
79.22(+0)
80.66(+02)
81.11(+01)
80.06(-01)
79.43(-01)
81.46(+03)
Y 軸
7.93
37.83(+377%)
53.10(+40)
62.58(+18)
70.92(+13)
76.38(+08)
76.57(+0)
76.40(+00)
78.18(+02)
78.52(+0)
79.39(+01)
79.90(+01)
77.60(-03)
79.90(+03)
X,Y 軸
12.51
57.95(+363%)
71.36(+23)
76.63(+07)
80.18(+05)
81.34(+01)
81.72(+0)
79.90(-02)
81.15(+02)
80.79(+00)
81.19(+00)
80.60(-01)
79.86(-01)
80.77(+01)
ために 3 体となる. また学習率 α = 0.1, 0.2, 0.3 を 3 三種類を
使用するため，鏡の位置 4 種類 (鏡を置かない状態も含む) と
表 3 Q 値 (α = 0.3)
学習率 3 種類の合計 12 パターンの実験を行う.
干渉ありの実験では追跡する獲物エージェントによる収束ス
テップと収束値，捕獲ステップの違いを比較する. この実験で
は学習率 α = 0.1，鏡の位置を x 軸に 2 枚置いた状況を考える.
追跡する獲物エージェントを実像と鏡像の 2 種類，比較対象と
して鏡がない Q 学習と X 軸に鏡を 1 枚置いた干渉なしの Q 学
習と比較する. また鏡像の獲物を捕獲した場合，鏡が 2 枚置い
てあるため，2 回正の報酬を得るが，ゲームの終了条件として
正の報酬を得たときにゲームが終了のため，干渉している Q 値
X 軸
12.78
47.37(+271%)
66.36(+40)
75.00(+13)
80.31(+07)
79.10(-02)
81.28(+03)
81.10(+0)
80.75(+0)
78.63(-03)
80.23(+02)
78.38(-02)
77.60(-01)
78.53(+01)
Y 軸
10.71
48.19(+350%)
64.66(+34)
74.64(+15)
76.90(+03)
76.18(-01)
78.99(+04)
78.51(-01)
77.52(-01)
78.45(+01)
77.16(-02)
76.84(+0)
78.27(+02)
78.33(+0)
X,Y 軸
17.26
65.98(+282%)
75.88(+15)
79.14(+04)
81.68(+03)
80.68(-01)
79.24(-02)
80.36(+01)
82.27(+02)
80.85(-02)
81.13(+0)
80.64(-01)
80.82(+0)
80.22(-01)
が 1 度しか更新されない．そのため，干渉している Q 値を 2 回
目まで更新する Q 学習も比較対象とする．
5. 2 収 束 条 件
学習率を固定しているため本来は収束する保証はない. その
為，ここで新たな収束条件を定義する. 最適な収束値として鏡
を使用しない Q 学習の 20 万回の時点での値の 30 セットの平
均値とする. 最適値±標準偏差に過去 1 万回範囲内のとき収束
したとみなし，その時点の学習回数を収束ステップとする．
5. 3 実 験 結 果
干渉なしの実験では表 1,2,3 は学習率 α = 0.1, 0.2, 0.3 それ
ぞれの Q 値の変化と，前回と比較して何%変化したかを表し
ている．例として，表 1 の鏡のない Q 学習において，18.45 は
2.86 と比べて (+546%)Q 値が上昇している．鏡のない Q 学習
と比較して鏡を 1 枚，または 2 枚置いたときの Q 学習は収束が
早くなっていることがわかる．例えば，学習率 α = 0.1 のとき
表 4 では学習率 α = 0.1, 0.2, 0.3 それぞれの収束ステップと
鏡のない Q 学習と比較して，どのくらい収束速度が向上した
比率を表している．比率が小さければ速く収束していること
を意味している．どの学習率においても，鏡を X 軸または Y
軸に置いたとき 2 倍速くなっており，また，X 軸と Y 軸に鏡
を置いたとき 3 倍速くなっている．最も速くなったケースが学
習率 α = 0.1 で X 軸と Y 軸に鏡を置いたとき 26.4%(または
3.78=1/0.264) に減少している．
表 5 では学習率，鏡の位置ごとに 200000 回繰り返した捕獲
ステップ (学習済み Q 値を使用して本物の獲物を捕獲するにの
かかるステップ数) を表している．鏡のない Q 学習と比較して
鏡を使用している Q 学習はすべてのケースにおいて，数値が
悪化 (捕獲にまでにステップ数が更に必要) している．しかし，
に鏡を 2 枚置いて本物の獲物を追跡する Q 学習 (Real) のケー
表 4 収束ステップ
α
0.1
鏡なし
130500
0.2
64500
0.3
49000
α
0.1
鏡なし
6.66
0.2
6.84
0.3
6.90
X 軸
62000
(47.5%)
30500
(47.3)
22500
(45.9)
Y 軸
67500
(51.7)
32000
(49.6)
23500
(48.0)
X,Y 軸
34500
(26.4)
20500
(31.8)
17000
(34.7)
スで微かに悪化していることがわかる．
表 8 捕獲ステップ (干渉あり)
NoMirror
6.66
RealNoInt
6.76
(+2%)
Real
6.75
(+1%)
Mirror
6.63
(+0%)
MirrorDbl
6.44
(-3%)
表 5 捕獲ステップ
X 軸
6.76
(+1.5%)
6.90
(+0.9)
7.13
(+3.3)
Y 軸
6.77
(+1.7)
6.91
(+1.0)
6.98
(+1.2)
X,Y 軸
6.90
(+3.6)
7.02
(+2.6)
7.17
(+3.9)
5. 4 考
察
表 4 と 5 から学習率の役割がわかる．鏡なしの Q 学習に注
目してみると，収束回数は 130500 回,64500 回,49000 回と学習
率 α の値が大きくなると，収束ステップは減少して速く収束す
る．捕獲ステップ (学習によって得られる政策の質) は，捕獲ま
学習が 2，3 倍速くなってるにも関わらず，最大でも 3.9%(0.27
での行動数が 6.66 回，6.84 回，6.90 回となり，学習率 α が大
ステップ) 悪化で抑えられている．
きくなるに伴い質が悪化している．したがって，学習率 α が小
干渉ありの実験では表 6 は学習率 α = 0.1 のときの Q 値
さいほど学習速度は低下するが，得られる政策の質は向上し，
の変化を表している．実験したパターンは鏡のない Q 学習
反対に学習率 α が大きくなるほど学習速度は向上し，政策の質
(NoMirror),X 軸に鏡を 1 枚置いて本物の獲物を追跡する Q 学
が低下するトレードオフの関係があることがわかる
習 (RealNoInt),X 軸に鏡を 2 枚置いて本物の獲物を追跡する Q
提案手法の有用性を示すため鏡の位置ごとに回帰分析を行
学習 (Real),X 軸に鏡を 2 枚置いて鏡像の獲物を追跡して Q 値
う．表 9 が回帰分析の結果であり，X は収束ステップ,Y は捕獲
の更新を１回行う Q 学習 (Mirror),X 軸に鏡を 2 枚置いて鏡像
ステップを表している．鏡のない Q 学習の相関 (Correlation)
の獲物を追跡して Q 値の更新を 2 回行う Q 学習 (MirrorDbl)
は-0.998 であり，この他の場合も同様に明らかな逆相関である
である．他と比べて明らかに X 軸に鏡を 2 枚置いて鏡像の獲
ことがわかる．しかし，X 軸に鏡の置いた場合は回帰直線の傾
物を追跡して Q 値の更新を１回行う Q 学習 (Mirror) の Q 値
き (回帰係数) が-0.008 のため回帰式の当てはまりが有効ではな
が小さいことがわかる．一方で，X 軸に鏡を 2 枚置いて本物
い．また 2 枚鏡を置いたとき，回帰係数が-0.135 であるため強
の獲物を追跡する Q 学習 (Real) の Q 値は鏡のない Q 学習
い確信を持って弱い負の相関があるといえる．その理由は，も
(NoMirror) と近い値となっており，かつ速く収束している．た
し鏡のない Q 学習の学習率 α が収束条件を満たしていれば，提
とえば 10000 回目では，Q 値は鏡のない Q 学習 (NoMirror) は
案手法の学習率 β も収束条件かつ，α <
= β を満たす．したがっ
て，常に学習速度の速いがパワフルではない Q 値が得られる．
76%も上昇しているが，X 軸に鏡を 2 枚置いて鏡像の獲物を追
跡して Q 値の更新を１回行う Q 学習 (Mirror) は 9%の上昇に
表9
留まっている．
鏡の位置
鏡なし
X 軸
Y 軸
X,Y 軸
表 6 Q 値 (干渉あり)
試行回数
500
5000
10000
15000
20000
25000
30000
35000
40000
45000
50000
100000
150000
200000
NoMirror
2.86
18.45 (+546%)
28.00 (+52)
32.00 (+14)
33.75 (+5)
34.68 (+3)
35.13 (+1)
36.24 (+3)
36.67 (+1)
37.29 (+2)
39.88 (+7)
70.27 (+76)
79.49 (+13)
78.82 (-1)
RealNoInt
5.67
25.09
37.45
45.21
49.55
54.41
61.55
66.29
70.52
74.95
75.99
79.22
79.95
80.06
Real
5.31
21.47(+304%)
32.73 (+52)
42.03 (+28)
46.40 (+10)
51.37 (+11)
55.69 (+8)
61.94 (+11)
66.95 (+8)
69.44 (+4)
72.31 (+4)
78.63 (+9)
78.33 (+0)
79.20 (+1)
Mirror
5.31
24.61
39.97
51.42
60.89
67.24
69.55
70.59
71.32
72.13
72.93
73.02
73.21
72.57
MirrorDbl
4.56
28.34
39.13
48.67
58.04
58.04
72.77
77.03
78.91
80.31
81.62
81.73
81.82
81.63
相関係数
-0.998
-0.891
-0.989
-0.922
回帰分析
回帰式
Y = -0.029X+21.10
Y = -0.008X+21.71
Y = -0.045X + 21.22
Y = -0.135X + 22.06
表 4 より逆相関であるから，学習の質がより悪くなるかもし
れないが，Q 学習の学習速度が 2 倍 (鏡１枚) や 3 倍 (鏡 2 枚)
になることが予測することができる．
表 7 から干渉が原因により収束が遅くなることがわかる．
干渉なしの X 軸と Y 軸に鏡を置いたとき 34,500 (26.4%) ス
テップなのに対し，干渉ありの X 軸に鏡を 2 枚重ねたとき
77,500(59.4%) ステップも収束に要している．しかし，表 8 で
捕獲までの行動回数が 6.90 から 6.75(-2.2%) になっている．本
表 7 では干渉ありの収束ステップを示している．干渉なしの
X 軸と Y 軸に鏡を置いたときと比較して，学習速度が 2 倍遅
くなっている (34,500 ステップ と 77,500 ステップ) が鏡のな
い Q 学習と比較して 1.67(=1/0.594) 倍速くなっている．
実験の結果から，鏡像を利用した干渉あり状況を想定して改善
することは無いことがわかる．
6. 結
論
Q 学習は教師なしのタスクに対して幅広く使用され，また知
表 7 収束ステップ (α = 0.1)
NoMirror
130500
RealNoInt
62000 (47.5%)
Real
77500(59.4)
Mirror
識抽出に優れた学習法である．しかし，学習効率が悪くまた収
MirrorDbl
43500(33.3)
束しないことがある．本研究では，鏡像を利用した Q 学習の高
速学習を提案を行い，鏡のない Q 学習が収束するなら，提案手
表 8 では干渉ありのときの捕獲ステップを示している．X 軸
法が収束することも示した．提案手法を使用することで学習の
質が微かに落ちるが，鏡が１枚のとき速度が 2 倍に，2 枚のと
き 3 倍に向上する．追跡問題の実験結果から考察を行い，得ら
れる知識の質がたかだか 4%の悪化で抑えられることを示した．
Q 学習は確しかに強力な学習方法の一つであるが，それは多
くの人々が理論的な堅実さに固執するからである．提案手法で
は Q 学習の性質を維持したまま，提案手法の有用性を示した．
文
献
[1] Culler, D. et al: Parallel Computer Architecture: A Hardware/Software Approach, Morgan Kaufmann, 1998
[2] Ito, A. and Kanabuchi, M.: Speeding up Multi-Agent Reinforcement Learning by Coarse-Graining of Perception - The
Hunter Game, Electronics and Communications in Japan
(Part II: Electronics), Volume 84-12, pp.3745, 2001
[3] 桑原 直也， 三浦孝夫: Q 学習による知覚情報の粗視化による追
跡動作の学習， 情報処理学会第 73 回全国大会， 5Q-3， 2011
[4] Richard S.Sutton， Andrew G.Barto， 三上貞芳 (訳)，皆川
雅章 (訳): 「強化学習」森北出版 2000
[5] 高玉 圭樹: マルチエージェント学習， コロナ社，2004.
[6] Watkins C.J.C.H and Dayan P.: Q-Learning - Technical
Note, Machine Learning, 8, pp.279-292, 1992, Kluwer Academic Publishers
[7] Wooldridge, M.: An Introduction to MultiAgent Systems
(2nd ed.), John Wiley, 2009