Pythonで〇×ゲームのAIを一から作成する その252 ε-greedy法の短期的な性質

目次と前回の記事

Python のバージョンとこれまでに作成したモジュール

本記事のプログラムは Python のバージョン 3.13 で実行しています。また、numpy のバージョンは 2.3.5 です。

リンク	説明
marubatsu.py	Marubatsu、Marubatsu_GUI クラスの定義
ai.py	AI に関する関数
mbtest.py	テストに関する関数
util.py	ユーティリティ関数の定義
tree.py	ゲーム木に関する Node、Mbtree クラスなどの定義
gui.py	GUI に関する処理を行う基底クラスとなる GUI クラスの定義

AI の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。

今回の記事の内容

前回の記事では、あらかじめ設定した確率 $ε$ によって探索と活用の割合をコントロールする ε-greedy法 のプログラムを実装し、様々な統計グラフを用いて、長期的な視点（試行回数が十分に大きい場合）におけるアルゴリズムの性質を多角的に説明しました。

しかし、現実の世界には時間の制約があるため、悠長に何千回もスロットマシンのレバーを引き続けられるような状況はめったにありません。「多腕バンディット問題（強化学習）」の真の本質は、長い時間ではなく、限られた短い期間（ステップ数）の中で、いかに効率よく多くの報酬を得られるか という、実戦的なアルゴリズムを求めることにあります。

そこで、今回の記事では ε-greedy 法について、より現実的な「短期的な視点での ε-greedy 法の性質」 について詳しく説明します。

ε-greedy 法の短期的な性質

$ε$ の設定値によって、短期的な ε-greedy 法の性質がどのように変化するかを明らかにするために、今回の記事でも大規模なシミュレーションを行います。実験の基本条件は、これまでの記事とまったく同じ以下の条件を設定します。

• スロットマシンの台数：3 台
• 各スロットマシンの当たりの真の確率：[0.3, 0.5, 0.7]

多腕バンディット問題の目的関数の性質のおさらい

以前の記事で説明したように、多腕バンディット問題の目的関数 $f$（累積報酬
の期待値）は、「探索と活用のトレードオフ」のバランスによって、下記の表の「合計スコア」のように変動します。

なお、今回の記事の具体的な設定では $p_{mean} = 0.5$、$p_{max} = 0.7$ となります。また、表の中の $m$ はスロットマシンを引いた合計回数（総ステップ数）を表します。

探索 回数	活用 回数	探索のスコア （$f_{探}$ の確定値）	活用のスコア （$f_{活}$ の近似値）	合計のスコア （$f$ の近似値）
小	大	$m_{探} \times p_{mean}$	$\approx m_{活} \times p_{mean}$	$\approx m \times p_{mean}$ （ただのランダム(50 枚)）
中	中	$m_{探} \times p_{mean}$	$\approx m_{活} \times p_{mid}$	$\gt m \times p_{mean}$ （50 枚を突破できる）
大	小	$m_{探} \times p_{mean}$	$\approx m_{活} \times p_{max}$	$\approx m \times p_{mean}$ （ただのランダム(50 枚)）

ε-greedy 法では、この「探索」と「活用」のトレードオフを調整するハイパーパラメータとして $ε$ を使います。従って、上記の表のにある探索回数の「小・中・大」は、そのまま $ε$ の値の大きさに置き換えて考えることができます。

この表は「探索と活用のどちらかに偏りすぎるのではなく、バランスよく行うこと」が多腕バンディット問題の目的関数を最大化するために重要であることを示していますが、これだけでは「具体的にどのようなバランス（$ε$ の値）がベストなのか？」まではわかりません。

そこで、ここからは探索と活用のバランスを決める $ε$ と「1 ステップあたりに稼ぐコインの平均枚数」の具体的な関係について考察していくことにします。

「1 ステップあたりに稼ぐコインの平均枚数」を分析の対象にする理由

これまでの記事では、目的関数である「稼いだコインの合計枚数」そのものではなく、「1 ステップあたりに稼ぐコインの平均枚数」を元に多腕バンディット問題のアルゴリズムの性能を評価してきました。「本来の目的関数とは違う値を使って評価を行っても大丈夫なのか？」と疑問に思う人がいるかもしれませんので、ここで「あえて平均枚数を分析に使う理由」について改めて整理しておきます。

多腕バンディット問題の目的関数は、先程のおさらいの表にあるとおり、$m \times p_{mean}$ 以上の値になります。ここで、すべてのスロットマシンの当たりの平均確率である $p_{mean}$ は、シミュレーションの途中で変わることがない「定数」です。そのため、目的関数（コインの合計枚数）の値は、総ステップ数 $m$ に比例してどこまでも大きくなる という性質があります。このように、シミュレーションの長さ（総ステップ数）によって基準が変わってしまうため、合計枚数のデータだけを見せられても、そのアルゴリズムが本当に優秀なのかどうかを直観的に判断しづらいという欠点があります。

それに対して、獲得したコインの合計枚数をステップ数 $m$ で割った「1 ステップあたりの平均枚数」には、下記のように、数値を見るだけで性能を一目で評価できるという大きなメリットがあります。

• 1 ステップで得られるコインの枚数は「0 枚（ハズレ）」か「1 枚（当たり）」のどちらかなので、総ステップ数 $m$ がどれだけ長くなろうとも、平均枚数は必ず 0 以上 1 以下の範囲に収まる
• 理想の最高得点は、最高の当たり台だけを引き続けた場合の真の確率 $p_{max}$ になる。そのため、アルゴリズムの性能が 「理想の $p_{max}$ にどれだけ近いか」 を見るだけで、直観的に一目で理解できる

さらに、「異なる数値を、同じを正の値で割っても、数値の大小関係（不等号の向き）は変わらない」 という性質があるため、「コインの合計枚数（目的関数）」を最大にする最強の作戦と、「1 ステップ当たりの平均枚数」を最大化する作戦は、計算の手順が変わるだけで、導き出される答え（最適化問題の結論）が完全に一致 します。

これらのことから、指標としてのわかりやすさを優先し、以後の記事でも「1 ステップあたりに稼ぐコインの平均枚数」をベースに分析を進めていくことにします。

記号の定義

ε-greedy 法では、総ステップ数が $s$¹ の場合に行われる探索と活用の回数の平均値は、それぞれ $ε \times s$、 $(1 -ε) \times s$ のように、$s$ と $ε$ によって決まります。そのため、ε-greedy 法で多腕バンディット問題を解いた場合の目的関数（累積報酬の期待値）は、$s$ と $ε$ の値によって結果が決まる関数であると考えることができます。

そこで、本記事では以下の記号を使って、「目的関数」と、それをステップ数で割った「1 ステップあたりに稼ぐコインの平均枚数」をそれぞれ表記することにします。

• $f(s, ε)$：ステップ $s$ での目的関数（累積報酬の期待値）
• $\bar{f}(s, ε)$²：ステップ $s$ での「1 ステップあたりに稼ぐコインの平均枚数」

なお、$\bar{f}(s, ε)$ は、強化学習の慣例に従ってステップを 0 から数えるため、総ステップ数は $s + 1$ となり、下記の式で計算されます³。

$$\bar{f}(s, ε) = \frac{f(s, ε)}{s + 1}$$

ここで、目的関数 $f(s, \varepsilon)$ を最大化する最適な $ε$（最適解）を、最適化問題の慣習に倣って $ε^*$（イプシロン・スター）と呼び、それぞれの関数の最大値を $f_{max}(s)$、$\bar{f}_{max}(s)$ と表記することにします。

$ε^*$ は総ステップ数 $s$ の値によって変化するので、本来は $ε^*(s)$ のように、「$s$ の関数」として定義したほうが厳密です。しかし、すべての数式に $(s)$ を付けると式が複雑になって見づらくなってしまうため、本記事ではシンプルに $ε^*$ と表記します。

以前の記事で説明した argmax を用いると、これらの値は下記の式で定式化できます。

$$ε^* = \operatorname{argmax}_{ε}f(s, ε)$$

$$f_{max}(s) = f(s, ε^*)$$

また、先程説明したように、$s$ と $ε$ に対する $f(s, ε)$ と $\bar{f}(s, ε)$ の大小関係は変化しないので、平均枚数の世界でも全く同じ $ε^*$ を使った下記の式が同時に成り立ちます。

$$ε^* = \operatorname{argmax}_{ε}\bar{f}(s, ε)$$

$$\bar{f}_{max}(s) = \bar{f}(s, ε^*)$$

ε と「1 ステップあたりに稼ぐコインの平均枚数」の関係

それでは、先ほど定義した記号を用いて、$ε$ と $\bar{f}(s, ε)$（1 ステップあたりに稼ぐコインの平均枚数）の関係についての具体的な考察を始めます。

探索が十分な場合（長期的な視点）

前回の記事では、長期的な視点（ステップ数 $s$ が十分に大きい場合）で $\bar{f}(s, ε)$ が下記の式で近似できる（$s$ が大きくなればなるほどこの理論値に近づく）ことを示しました。

$$\bar{f}(s, ε) \approx ε \times p_{mean} + (1 - ε) \times p_{max}$$

なぜこの式が成り立つかというと、ステップ数が十分に大きくなれば、すべてのスロットマシンに対して「本当の実力（真の確率）を見抜くのに十分な回数」だけ探索が行わるからです。ハズレ台を引く勘違いが完全に消えるため、確率が $1 - ε$ で活用が選ばれた時に最高の当たり台（神台）（$p_{max}$）だけを確実にえこひいきして選択できる ようになるからです。

この式を $ε$ でまとめると下記のようになります。

$$\bar{f}(s, ε) \approx ε \times (p_{mean} - p_{max}) + p_{max}$$

ここで、$p_{max}$ は「最高の当たり台の確率」、$p_{mean}$ は「全スロットマシンの平均確率」です。当然ですが、最高の当たり台の確率は全体の平均以上になるため、必ず $p_{max} \ge p_{mean}$ という関係が成り立ちます。

従って、$ε$ に掛けられている括弧の中身である $p_{mean} - p_{max}$ は必ず 0 以下のマイナスの値になります。傾きがマイナスになるということは、この式は $ε$ が増加すると、グラフが右肩下がりに単調減少する ことになります。

厳密にはすべてのスロットマシンの当たりの確率が完全に等しい場合に限っては $p_{mean} - p_{max} = 0$ となり、グラフの傾きは 0 の水平線（常に $p_{max}$ と同じ）になります。しかし、すべてのスロットマシンの実力が同じ多腕バンディット問題は、どんな作戦をとっても常に $\bar{f}(s, ε) = p_{max}$ となるため、問題の設定そのものに意味がありません。そのため、以後は $p_{mean} - p_{max} \lt 0$（$ε$ を増やすと単調減少する）であるものとして説明を行います。

最高の当たり台が完全に判明した後は、もはやそれ以上実験データを集める必要はありません。それにも関わらず、あらかじめ設定したルール通りに $ε$ の確率で完全ランダムな「探索」を続けてしまうと、「せっかく正解わかっているのに、わざわざ一定の確率でハズレ台を引いて大損しにいく」 という、ただの無駄な行動（機会損失）になってしまいます。

これが $ε$ を大きくすると、データが十分に集まりきった後（長期的な視点）に獲得コインの平均（$\bar{f}(s, ε)$）が減ってしまう原因です。

探索が足りない場合（短期的な視点）

先ほどの長期的な近似式が成り立つためには、すべてのスロットマシンに対して「最高の当たり台を見抜くのに十分な回数」だけ探索が行き渡っている 必要があります。

ステップ $s$ までに行われる探索回数の平均値は $ε \times s$ で計算されます⁴。そのため、この $ε \times s$ という「探索の絶対量」が十分に大きくならなければ、先ほどの右肩下がりの近似式は成り立ちません。

実際に、探索の回数の平均がたったの $ε \times s = 1$ 回となる、$s = 10,000$、$ε = 0.0001$ の場合は、前回の記事のシミュレーション結果では、平均獲得コインは $\bar{f}(10,000, 0.0001) = 0.566$ という非常に低い値にとどまりました。理論値である $ε \times 0.5 + (1 - ε) \times p_{max}$ の理論値である 0.69998 と比べると大幅に小さい値になります。

このように $ε$ に 0.0001 のような極端に小さな値を設定してしまうと、いくら制限時間が（$s$）が 1 万ステップのような長期戦であったとしても、探索がほとんど行われないため、実質的に最悪の性能である $ε = 0$（貪欲法）とほぼ変わらない「思考停止の大爆死ループ」に陥ってしまいます。

このような性質があるため、ε-greedy 法を実戦で使う際には、$ε$ に極端に小さな値を設定することは通常はありません。そこで、これ以降の解説では極端に小さな $ε$ は除外した上で⁵、ゲームの長さを以下のように定義して分析を進めていきます。

• 長期的な視点：$s$ が 1 万 のような、データを完全に調べ尽くせる大きな値の場合
• 短期的な視点：$s$ が 1,000 以下 のような、データが集まりきっていない小さな値の場合

探索の絶対量がまったく足りていない「短期的な視点」では、状況は長期戦のときとは完全に真逆になります。長期戦では「無駄な損失」でしかなかった探索が、短期決戦においては 「少しでも早く、最高の当たり台を見抜く可能性を引き上げるための、極めて有益な行動」 へと姿を変えるのです。

そのため、十分な探索データが集まりきるまでの初期の段階（短期的な視点）においては、$ε$（探索する確率）を増やせば増やすほど、ハズレの勘違いを早く脱出できるため、平均獲得コイン $\bar{f}(s, ε)$の値は右肩上がりに増加していく ことになります。

全体の傾向

ここまでの考察をまとめると $\bar{f}(s, ε)$ （1 ステップあたりの平均獲得コイン）には以下のような対照的な性質があることがわかります。

• 探索が十分な状態（長期戦）：すでにデータの精度が完璧なため、これ以上探索を増やしても活用の効率は上がらない。探索を増やすほどハズレ台を引く「デメリット」しか残らないため、$ε$ が増えると 単調減少（右肩下がり） する
• 探索が足りない状態（短期戦）：探索を増やすほどハズレの勘違いを早く脱出できるという「メリット」が活用を上回る。そのため $ε$ が増えると 増加（右肩上がり） する

長期戦において $ε$ を増やすと右肩下がりに「単調減少」することは、先ほどの数学的な近似式から明らかです。一方、短期戦において $ε$ を増やすと具体的に「どのように増加していくか」については、まだ数式だけではわかりません。

しかし、実験データ（経験）が集まれば集まるほど AI の推測は賢くなっていくはずなので、途中で AI の実力が突然後退するような不自然な挙動（一旦減少してから再び増加する）が起きることは考えづらいです。従って、短期戦では「単調増加」していくと推測できます。

以上の考察から、ハイパーパラメータ $ε$ と平均獲得コイン $\bar{f}(s, ε)$ の間には下記の表のような関係があることが推測できます。

$ε$	0	・・・	$ε^*$	・・・	1
$\bar{f}(s, ε)$	$\bar{f}(s, 0)$ 貪欲法	単調増加 右肩上がり	$\bar{f}_{max}(s)$ 最大値	単調減少 右肩下がり	$\bar{f}(s, 1)$ 完全ランダム $= p_{mean}$

この関係性の表から $\bar{f}(s, ε)$ という関数について、次のような 2 つの仮説 を立てることができます。

1. ε-greedy 法の平均獲得コイン（$\bar{f}(s, ε)$）のグラフは、横軸（x 軸）を $ε$ とすると、「最初は右肩上がりに登り、ピークを過ぎると右肩下がりに下がる」という、綺麗な山形のグラフ（凸関数）を描く
2. その山の頂点（最大値）、すなわち 「探索が足りない（有益）」から「探索が十分（無駄）」へと切り替わる境界線が、今回の本題である「最適な探索と活用のバランスを表す $ε^*$」になる

この仮説が本当に正しいかを、実際にシミュレーションを行って検証することにします。

複数エピソードの実行と保存

先ほど立てた「山形のグラフになる」という仮説を検証するために、様々な $ε$ の設定値に対する大規模なシミュレーションを行います。そのためには、「総ステップ数」と、比較する「ε の値」をどのように設定するかをあらかじめ決める必要があります。

ステップ数の検討

前回の記事では、十分にデータが集まりきった「長期的な性質」を調べるために 1 万ステップのシミュレーションを行いました。しかし、今回の目的である「短期的な性質」を検証するためには、そこまで長い時間をかける必要はありません。

そこで、今回の記事では、先ほど短期戦の基準として定めた 総ステップ数 1,000回（長期戦の 10 分の 1） を採用して、シミュレーションを実行することにします。

この「1,000ステップ」という設定は、「1,000 回も試行すれば、データが集まりきる前の短期的な性質を明らかにするのに十分だろう」という、これまでの実験を踏まえた筆者の直感（仮説）で決めたものです。

もし、出力されたグラフを分析した結果、「ステップ数が少なすぎて傾向が分からない」と判明した場合は、柔軟にステップ数を増やして実験をやり直すアプローチをとる必要があります。このように「まずはアタリを付けて実験し、結果を見て必要があれば修正（フィードバック）する」ことがデータの分析（データサイエンス）では非常に重要となります。

ε の検討

前回の記事では $ε$ の値として [0, 0.25, 0.5, 0.75, 1] の 5 種類の大まかな設定でシミュレーションを行いました。しかし、今回の目的である「短期戦における最高の探索と活用のバランス（最適解 $ε^*$）」を突き止めるためには、もっと細かく ε の値を刻んで変化させる必要があります。

ここで、大きな問題となるのが「コンピュータの計算時間」です。前回の記事では、1 つの $ε$ の設定に対するシミュレーション（1 万ステップ × 1,000 エピソード）の処理に約 5 分もの時間がかかっていました。今回はステップ数を 10 分の 1（1,000 ステップ）に縮小したため、1 回あたりの処理時間は単純計算で約 1 分程度まで短縮できると想定できます。

しかし、だからといって $ε$ の値を 0 から 1 まで 0.01 刻みで細かく変化させてしまうと、合計 100 回ものシミュレーションを実行することになり、トータルの処理時間は 1 時間半以上（約 100 分） もかかってしまいます。これでは、結果を手軽に確認して考察を進めるには少し長すぎます。

そこで今回は、闇雲にすべての範囲を計算する力任せな方法ではなく、「事前にシミュレーションを行う $ε$ の範囲を絞り込む」 ことで、計算時間を短縮するという実戦的な工夫を取り入れることにしました。

最適な ε がとりうる範囲の検証

先程の考察から、$ε^* \lt ε$ の範囲（データが集まりきった領域）では、探索が十分に行われた結果、$\bar{f}(s, ε)$ が $ε \times (p_{mean} - p_{max}) + p_{max}$ という式に従って単調減少することが理論的にわかっています。

つまり、すでに減少モードに入っている大きな $ε$ の領域をいくら細かく調べても、最適解（$ε^*$）が見つかるはずはありません。そこで今回は、その無駄な範囲をあらかじめ実験対象からすべて除外し、残りの $0 \le ε \le ε^*$ の範囲だけに狙いを定めてシミュレーションを行う　という絞り込みを行います。

では、肝心の「山の頂点（$ε^*$）」は一体どこにあるのでしょうか？それを調べるために、前回の記事で行った 1 万ステップのシミュレーションの結果から、ステップ数が [250, 500, 750, 1000] のそれぞれの地点における $\bar{f}(s, ε)$ の実測値を抜き出すことで、$ε^*$ が大体どのあたりの値になりそうか、事前の見当（アタリ）を付ける ことにします。

下記はその処理を行うプログラムです。

• 1 行目：Epsilion_Greedy_MAB_Agent クラスのインスタンスが保存されたデータをファイルから読み込む場合は、そのクラスをインポートしておく必要がある
• 3 ~ 7 行目：前回の記事でファイルに保存したシミュレーションのデータを読み込む
• 9 ~ 15 行目：[250, 500, 750, 1000] のそれぞれのステップの時点での、読み込んだ各シミュレーションデータの「1 ステップあたりに稼ぐコインの平均枚数（mean_mean_coins_by_step 属性）」を取り出し、データが集まりきった場合の理論値と並べて表示する

 1  from ai import MAB_Agent, Epsilon_Greedy_MAB_Agent
 2  
 3  egreedy_agents = []
 4  for i in range(5):
 5      epsilon = i / 4
 6      egreedy_agent = MAB_Agent.load(f"../data/egreedy_agent(e={epsilon})")
 7      egreedy_agents.append(egreedy_agent)
 8  
 9  for step in [250, 500, 750, 1000]:
10      print(f"step {step:4}")
11      for egreedy_agent in egreedy_agents:
12          epsilon = egreedy_agent.epsilon
13          print(f"epsilon = {epsilon:.2f}:",
14                f"1 ステップあたりに稼ぐコインの平均枚数 {egreedy_agent.mean_mean_coins_by_step[step]:.3f}",
15                f"理論値 {epsilon * 0.5 + (1 - epsilon) * 0.7:.3f}")

行番号のないプログラム

from ai import MAB_Agent, Epsilon_Greedy_MAB_Agent

egreedy_agents = []
for i in range(5):
    epsilon = i / 4
    egreedy_agent = MAB_Agent.load(f"../data/egreedy_agent(e={epsilon})")
    egreedy_agents.append(egreedy_agent)
    
for step in [250, 500, 750, 1000]:
    print(f"step {step:4}")
    for egreedy_agent in egreedy_agents:
        epsilon = egreedy_agent.epsilon
        print(f"epsilon = {epsilon:.2f}:",
              f"1 ステップあたりに稼ぐコインの平均枚数 {egreedy_agent.mean_mean_coins_by_step[step]:.3f}",
              f"理論値 {epsilon * 0.5 + (1 - epsilon) * 0.7:.3f}")

実行結果

step  250
epsilon = 0.00: 1 ステップあたりに稼ぐコインの平均枚数 0.555 理論値 0.700
epsilon = 0.25: 1 ステップあたりに稼ぐコインの平均枚数 0.631 理論値 0.650
epsilon = 0.50: 1 ステップあたりに稼ぐコインの平均枚数 0.589 理論値 0.600
epsilon = 0.75: 1 ステップあたりに稼ぐコインの平均枚数 0.545 理論値 0.550
epsilon = 1.00: 1 ステップあたりに稼ぐコインの平均枚数 0.501 理論値 0.500
step  500
epsilon = 0.00: 1 ステップあたりに稼ぐコインの平均枚数 0.555 理論値 0.700
epsilon = 0.25: 1 ステップあたりに稼ぐコインの平均枚数 0.640 理論値 0.650
epsilon = 0.50: 1 ステップあたりに稼ぐコインの平均枚数 0.595 理論値 0.600
epsilon = 0.75: 1 ステップあたりに稼ぐコインの平均枚数 0.547 理論値 0.550
epsilon = 1.00: 1 ステップあたりに稼ぐコインの平均枚数 0.500 理論値 0.500
step  750
epsilon = 0.00: 1 ステップあたりに稼ぐコインの平均枚数 0.556 理論値 0.700
epsilon = 0.25: 1 ステップあたりに稼ぐコインの平均枚数 0.644 理論値 0.650
epsilon = 0.50: 1 ステップあたりに稼ぐコインの平均枚数 0.596 理論値 0.600
epsilon = 0.75: 1 ステップあたりに稼ぐコインの平均枚数 0.548 理論値 0.550
epsilon = 1.00: 1 ステップあたりに稼ぐコインの平均枚数 0.500 理論値 0.500
step 1000
epsilon = 0.00: 1 ステップあたりに稼ぐコインの平均枚数 0.556 理論値 0.700
epsilon = 0.25: 1 ステップあたりに稼ぐコインの平均枚数 0.646 理論値 0.650
epsilon = 0.50: 1 ステップあたりに稼ぐコインの平均枚数 0.597 理論値 0.600
epsilon = 0.75: 1 ステップあたりに稼ぐコインの平均枚数 0.548 理論値 0.550
epsilon = 1.00: 1 ステップあたりに稼ぐコインの平均枚数 0.500 理論値 0.500

この実行結果のうちの、$ε \gt 0$ の結果に注目すると、もっとも序盤である「ステップ数 250」の段階でさえ、実測値がすでに理論値（データが完全に集まりきった後の上限）にかなり近いところまで肉薄していることが確認できます。

つまり、250ステップもあれば、$ε \ge 0.25$ のエージェントはハズレ台の勘違いを完全に克服し、すでに「右肩下がりの減少モード」に突入してしまっているということです。

このことから、短期決戦（ステップ数が 1,000 以下）における最適解（$ε^{*}$）は、ほぼ確実に「0 以上 0.25 以下の範囲」に存在する と推測することができます。

そこで今回は、探索範囲をさらに絞り込み、「$ε$ の値を 0 から 0.2 まで、0.01 刻みにした計 21 通り」 でシミュレーションを行うことします。

最大値を 0.25 ではなく、さらに手前の 0.20 まで絞り込んだ理由は、$ε = 0.25$ のときの実測値がどのステップでもすでに理論値（0.650）とほぼぴったり重なっていることから、山の頂点（$ε^{*}$）は 0.25 よりもさらに左側の、かなり小さな値になりそうだと推測できたからです。

シミュレーションの実行と保存

下記は 21 回のシミュレーションを行い、結果をファイルに保存するプログラムです。同様の処理を行った前回の記事のプログラムとの違いは以下の通りです。

• 繰り返しの回数を 5 回から 21 回に増やした
• $ε$ の計算を、0.01 刻みになるように i / 100 に変更した
• ステップ数を 1 万から 1,000 に変更した
• 長期戦のデータファイルと混ざって上書きされないように、ファイル名の括弧の中の最後にステップ数を表す ",step=1000" を加えた

p = [ 0.3, 0.5, 0.7 ]
egreedy_agents = []
for i in range(21):
    epsilon = i / 100
    egreedy_agent = Epsilon_Greedy_MAB_Agent(p=p, epsilon=epsilon)
    egreedy_agent.play_episodes(stepnum=1000, episodenum=1000)
    egreedy_agent.save(f"../data/egreedy_agent(e={epsilon},step=1000)")
    egreedy_agents.append(egreedy_agent)

実行結果

100%|██████████| 1000/1000 [00:28<00:00, 34.57it/s]
save completed.
100%|██████████| 1000/1000 [00:28<00:00, 34.84it/s]
save completed.
100%|██████████| 1000/1000 [00:32<00:00, 30.98it/s]
save completed.
100%|██████████| 1000/1000 [00:35<00:00, 28.11it/s]
save completed.
100%|██████████| 1000/1000 [00:35<00:00, 28.45it/s]
save completed.
100%|██████████| 1000/1000 [00:37<00:00, 26.94it/s]
save completed.
100%|██████████| 1000/1000 [00:37<00:00, 26.45it/s]
save completed.
100%|██████████| 1000/1000 [00:35<00:00, 28.50it/s]
save completed.
100%|██████████| 1000/1000 [00:35<00:00, 28.27it/s]
save completed.
100%|██████████| 1000/1000 [00:35<00:00, 28.48it/s]
save completed.
100%|██████████| 1000/1000 [00:35<00:00, 27.92it/s]
save completed.
100%|██████████| 1000/1000 [00:38<00:00, 26.18it/s]
save completed.
100%|██████████| 1000/1000 [00:36<00:00, 27.22it/s]
save completed.
100%|██████████| 1000/1000 [00:36<00:00, 27.56it/s]
save completed.
100%|██████████| 1000/1000 [00:36<00:00, 27.20it/s]
save completed.
100%|██████████| 1000/1000 [00:36<00:00, 27.68it/s]
save completed.
100%|██████████| 1000/1000 [00:36<00:00, 27.04it/s]
save completed.
100%|██████████| 1000/1000 [00:37<00:00, 26.41it/s]
save completed.
100%|██████████| 1000/1000 [00:36<00:00, 27.22it/s]
save completed.
100%|██████████| 1000/1000 [00:38<00:00, 25.84it/s]
save completed.
100%|██████████| 1000/1000 [00:36<00:00, 27.48it/s]
save completed.

実行結果から、1 回あたり約 35 秒、トータルで約 12 分という、100 分と比べるとかなり短い時間で処理が完了し、全データがファイルに保存されたことがわかります。

「1 ステップあたりに稼ぐコインの平均」の推移の比較

前回までの記事（長期戦の検証）では、アルゴリズムの性質を多角的に検証するために、MAB_Agent クラスに実装した様々な分析グラフをすべて描画して検証を行いました。

しかし、今回実行した短期戦（1,000 ステップ）のシミュレーション結果において、すべてのグラフを描画しても、その大半は長期戦のグラフを途中で切り取っただけの同じような見た目になってしまい、新たな発見は得られません。

そこで今回の記事では、短期的な視点で $\bar{f}(s, ε)$ がどのように変化していくのか、そのトレードオフの本質が現れる「重要なグラフ」だけにターゲットを絞って検証します。

具体的には、1,000 回ものエピソード（実験データ）を重ね合わせて集計した $\bar{f}(s, ε)$（1ステップあたりに稼ぐコインの平均枚数）の推移を重ね合わせて描画してみます。これによって、平均獲得コインが最大となる山の頂点 $ε^{*}$ が一体どのあたりに存在するかを視覚的に探ることができます。

なお、用意した 21 パターンすべての折れ線グラフを一度に描画してしまうと、グラフが込み合って非常にわかりづらくなってしまいます。そこでまずは、$ε$ の値を 0.0 から 0.20 まで 0.05 刻み にした 5 つの代表的な設定を重ね合わせてみることにします。

egreedy_agents に代入された list には $ε$ が 0.01 刻みで並んで記録されているので、下記のプログラムのように、 Python の スライス表記を利用して [::5]（5 つおきに取得）と記述するだけで、0.05 刻みのエージェントを抽出して比較することができます。

MAB_Agent.compare_mean_cumulative_reward_by_step(egreedy_agents[::5])

実行結果

描画されたグラフを見ると、一切探索を行わない $ε = 0$（青線）だけが、情報のアップデート（勘違いの修正）を行えないために、はるか下のライン（約 0.55 枚）で停滞しているのが一目でわかります。一方、探索が行われる他のエージェントたちは、スタート直後から急激な右肩上がりのカーブを描き、青線のベースラインを突き破っています。

しかし、このグラフには重要な問題があります。それは、$ε = 0$ 以外のグラフが、全区間でほぼぴったりと重なり合っている ため、「一体どの $ε$ の線が一番上にいて、もっとも多くのコインを稼ぎ出しているのか」がはっきりと識別できない というものです。

そこで、グラフの y 軸方向の縮尺（描画範囲）を狭めることで、重なり合ったグラフを拡大表示 して、個々のグラフの様子を識別できるようにプログラムを修正することにします。

y 軸の描画範囲の拡張設定

具体的には、このグラフを描画する compare_mean_cumulative_reward_by_step メソッドに以下の修正を行うことで、グラフの縮尺を設定できるようにします。

• グラフの y 軸の描画範囲の「最小値」と「最大値」を表す仮引数 miny と maxy を追加する（2 行目）
• 追加した 2 つの仮引数を、デフォルト値を 0 と 1 としたデフォルト引数として設定することで、miny と maxy を省略した場合に、これまでと同じグラフが描画されるようにする（2 行目）
• グラフの y 座標の描画範囲を設定を plt.ylim(miny, maxy) に置き換えることで、追加した 2 つの仮引数で指定した範囲でグラフが描画されるようになる（11 行目）

下記はそのように compare_mean_cumulative_reward_by_step を修正したプログラムです。

 1      @staticmethod
 2      def compare_mean_cumulative_reward_by_step(agent_list, miny=0, maxy=1):
 3          plt.title(f"ステップ当たりの累積報酬の平均の比較（{agent_list[0].episodenum} エピソード）")
 4          maxp = max(agent_list[0].mab.p)
 5          upperbounds = [maxp for step in range(agent_list[0].stepnum)]
 6          plt.plot(upperbounds, label="上限", c="k")
 7          for agent in agent_list:
 8              plt.plot(agent.mean_mean_coins_by_step, label=agent.title)
 9          plt.xlabel("ステップ数")
10          plt.ylabel("ステップ当たりの累積報酬の平均")
11          plt.ylim(miny, maxy)
12          plt.legend()
13          plt.show() 

行番号のないプログラム

    @staticmethod
    def compare_mean_cumulative_reward_by_step(agent_list, miny=0, maxy=1):
        plt.title(f"ステップ当たりの累積報酬の平均の比較（{agent_list[0].episodenum} エピソード）")
        maxp = max(agent_list[0].mab.p)
        upperbounds = [maxp for step in range(agent_list[0].stepnum)]
        plt.plot(upperbounds, label="上限", c="k")
        for agent in agent_list:
            plt.plot(agent.mean_mean_coins_by_step, label=agent.title)
        plt.xlabel("ステップ数")
        plt.ylabel("ステップ当たりの累積報酬の平均")
        plt.ylim(miny, maxy)
        plt.legend()
        plt.show() 

修正箇所

    @staticmethod
-   def compare_mean_cumulative_reward_by_step(agent_list):
+   def compare_mean_cumulative_reward_by_step(agent_list, miny=0, maxy=1):
        plt.title(f"ステップ当たりの累積報酬の平均の比較（{agent_list[0].episodenum} エピソード）")
        maxp = max(agent_list[0].mab.p)
        upperbounds = [maxp for step in range(agent_list[0].stepnum)]
        plt.plot(upperbounds, label="上限", c="k")
        for agent in agent_list:
            plt.plot(agent.mean_mean_coins_by_step, label=agent.title)
        plt.xlabel("ステップ数")
        plt.ylabel("ステップ当たりの累積報酬の平均")
-       plt.ylim(0, 1)
+       plt.ylim(miny, maxy)
        plt.legend()
        plt.show() 

折角なので、ヒストグラムを除いた他のグラフを描画するすべての関数に対しても同様の修正を行うことにします。ただし、plt.ylim で y 軸の描画範囲を指定していない draw_cumulative_reward のようなメソッドは、下記のような工夫を行なう必要があります。

• 仮引数 miny と maxy のデフォルト値を None にする
• plt.ylim(miny, maxy) を追加する。

plt.ylim の仮引数に None を指定した場合は範囲を変更しないことを表します。そのため、上記の工夫を行なうことで、miny と maxy を省略した場合は、修正前と同様に y 座標の範囲が matplotlib によって自動的に設定されたグラフが描画されるようになります。

    def draw_cumulative_reward(self, miny=None, maxy=None):
        plt.title(f"{self.title}\n累積報酬")
        maxp = max(self.mab.p)
        upperbounds = [step * maxp for step in range(self.stepnum)]
        plt.plot(upperbounds, label="上限", c="k")
        plt.plot(self.total_coins, label="コインの総数")
        for arm in range(self.mab.num):
            plt.plot(self.slot["total_coins"][arm], linestyle="--",
                     label=f"arm {arm} (p={self.mab.p[arm]:.2f})")
        plt.xlabel("ステップ数")
        plt.ylabel("コインの枚数")
        plt.ylim(miny, maxy)
        plt.legend()
        plt.show() 

修正箇所

-   def draw_cumulative_reward(self):
+   def draw_cumulative_reward(self, miny=None, maxy=None):
        plt.title(f"{self.title}\n累積報酬")
        maxp = max(self.mab.p)
        upperbounds = [step * maxp for step in range(self.stepnum)]
        plt.plot(upperbounds, label="上限", c="k")
        plt.plot(self.total_coins, label="コインの総数")
        for arm in range(self.mab.num):
            plt.plot(self.slot["total_coins"][arm], linestyle="--",
                     label=f"arm {arm} (p={self.mab.p[arm]:.2f})")
        plt.xlabel("ステップ数")
        plt.ylabel("コインの枚数")
+       plt.ylim(miny, maxy)
        plt.legend()
        plt.show() 

なお、今回の記事の ai.py は上記を修正済です。そのため、今回の記事の JupyterLab のプログラムでは、これらの修正を行うプログラムは実行していません。

グラフの再描画

先ほど拡張した機能を用いて、y 軸の範囲を 0.54 から 0.68 の範囲に絞り込んで拡大したグラフを再描画します。

MAB_Agent.compare_mean_cumulative_reward_by_step(egreedy_agents[::5], miny=0.54, maxy=0.68)

実行結果

グラフを拡大したことで、重なり合っていたグラフの推移の違いがはっきりしました。常に最下位（約0.55枚）で完全に水平線になっている $ε = 0$（貪欲法）を除外した上で、ステップ数（時間経過）ごとの推移詳しく分析してみます。

• ステップ数が 100 以下の超序盤
  まだどの台のデータも足りない時期です。オレンジ色の $ε = 0.05$ のグラフだけは探索が少なすぎて勘違いを脱出できずに立ち遅れていますが、それ以外の $ε \ge 0.10$ のグラフはほぼぴったりと重なり合っています。
• ステップ数が 100 ~ 400 の序盤戦
  探索の結果エージェントたちが正解を見抜き始め、以下の順で実力の差（不等号）が現れ始めます。

$$ε = 0.05 \lt ε = 0.2 \lt ε = 0.15 \lt ε = 0.1$$

• ステップ数が 400 ~ 600 の中盤戦
  ここで逆転現象が起きます。遅れていた $ε = 0.05$ が十分なデータを蓄えて本領を発揮しはじめ、逆に探索が多すぎる $ε = 0.2$ は「正解がわかっているのにハズレ台を引く無駄」のペナルティが重くなって失速し、順位が入れ替わります。

$$ε = 0.2 \lt ε = 0.05 \lt ε = 0.15 \lt ε = 0.1$$

• ステップ数が 600 以上の終盤戦
  時間が経つほど、無駄な探索を行うエージェントから順番に、長期的な理論値の坂を下って脱落していきます。ただし、この時点では $ε = 0.1$ は探索と活用のバランスが良い時期にあるため、トップの座を保っています。

$$ε = 0.2 \lt ε = 0.15 \lt ε = 0.05\lt ε = 0.1$$

グラフから、この激しい競争の中で、緑色の線である $ε = 0.1$ だけはスタート直後からゴールまで、すべてのステップで常に単独トップを維持し続けている ことがわかりました。

従って、この実験データから「今回の 1,000 ステップという時間制限においては、ステップ数に関わらず、最適な探索と活用のバランスを表す $ε^{*}$ は常に 0.1 のすぐ近く にあるはずだ」という見通しが立ちました。

大まかな山の位置が特定できたので、次はさらに細かくパラメータ $ε$ を刻んで「真の最適解 $ε^{*}$」がどのような値になるかを検証することにします。

0 ~ 0.05 の範囲のグラフの描画と考察

$ε^*$ のより正確な値 をつきとめるために、ここからは $ε$ を 0.01 刻みで実行した 21 パターンのシミュレーション結果をフルに活用した精密な分析へと移ります。ただし、すべての折れ線グラフを一度に描画するとわかりづらくなるため、ここでも 6 本ずつにグループを分けて段階的に比較・検証を進めていくことにします。

先ほどの大まかな検証から、山の頂点（$ε^*$）が 0 ~ 0.05 範囲に存在する可能性が極めて低いことがわかっています。しかし、強化学習の重要な性質である「探索を極端にケチると何が起きるのか」という挙動を視覚的に裏付けるため、あえてこの微小な範囲の折れ線グラフを拡大描画して観察してみることにします。

MAB_Agent.compare_mean_cumulative_reward_by_step(egreedy_agents[0:6], miny=0.54, maxy=0.68)

実行結果

出力されたグラフを観察すると、この範囲では例外なく 「すべてのステップにおいて、$ε$ の値（探索する確率）が大きければ大きいほど、平均獲得コイン $\bar{f}(s, ε)$ も高くなる」 という序列が確認できました。

この結果は、今回の記事の冒頭で立てた 「探索が足りない（短期的な）段階では、$ε$ を増やせば増やすほどスコアが右肩上がりに増加していく」 という仮説を証明しています。

$ε \le 0.05$ という小さな設定では、いくら制限時間を 1,000 ステップまで引き伸ばしたところで、AI が正解の神台を確信できるだけの十分なデータが全然集まりません。そのため、この領域では活用を増やすよりも、探索の確率をわずかでも引き上げて「データ不足による勘違い（自滅ループ）」を脱出するメリットのほうが圧倒的に上回る のです。

なお、グラフの右端（1,000 ステップ目）に注目すると、紫色の $ε=0.04$ の線が、茶色の $ε=0.05$ の線へとほぼぴったり重なる位置まで猛追している様子が捉えられます。この挙動から、「$ε=0.05$ の作戦をとれば、この 1,000 ステップの制限時間のちょうど終了間際あたりでようやく必要な探索がギリギリ行き渡り、長期的な理論値（減少モード）の入り口に到達できる」という、AI の知識獲得の様子を読み解くことができます。

0.05 ~ 0.1 の範囲のグラフの描画と考察

続いて、山の頂点（$ε^*$）が含まれている可能性が高い $ε$ が 0.05 ~ 0.1 の領域を、0.01 刻みで詳しく観察しすることにします。なお、境界となる $ε=0.05$ のデータは先ほどのグラフでも描画しましたが、この線を省略してしまうと、隣り合う $ε=0.05$ と $ε=0.06$ の実力差が比較できなくなってしまいます。そのため、ここでは $ε=0.05$ のグラフも含めて描画することにします。

MAB_Agent.compare_mean_cumulative_reward_by_step(egreedy_agents[5:11], miny=0.54, maxy=0.68)

実行結果

描画されたグラフを観察すると、0.01 という極小の刻み幅でライバルたちが並んでいるだけあって、お互いの折れ線グラフがかなり激しく重なり合っていることがわかります。そこで、グラフを時間帯ごとに細かく切り分けてさらに拡大表示することにします。具体的には、「50 〜 200 ステップの序盤戦」と、「200 ステップ以降の中盤・終盤戦」の 2 つの時間帯にスポットを当てて拡大を行います。

「0 ~ 50 ステップの超序盤戦」のグラフを拡大して検討しない理由を説明します。

スタート直後から 50 ステップ目までの超序盤戦では、この範囲の最小値である $ε = 0.05$ と最大値である $ε = 0.1$ を比べても、それまでに行われる探索回数の平均値（期待値）の差は、たったの 2.5 回（$50 \times 0.10 - 50 \times 0.05$）しかありません。

コインが当たるか外れるかの激しい乱数のゆらぎ（運のブレ）の中に、このわずか 2.5 回という差は完全に埋もれてしまいます。そのため、この時間帯はグラフを拡大しても、すべての線がほぼ完全に重なり合ってしまい、統計的な意味のある差を読み取ることはできません。また、仮にグラフに差が出たとしても、それは激しい乱数のゆらぎによる偶然の結果に過ぎない可能性が非常に高くなります。そのため、本記事ではこの超序盤のグラフを拡大表示した分析はあえて省略することにしました。

50 〜 200 ステップ付近の挙動の表示と考察

下記は 50 ~ 200 ステップの範囲のグラフを、y 軸の表示範囲を 0.57 から 0.64 へと絞り込むことで拡大して表示するプログラムです。

MAB_Agent.compare_mean_cumulative_reward_by_step(egreedy_agents[5:11], miny=0.57, maxy=0.64)

グラフの横軸（ステップ数）の動きを注意深く追っていくと、わずかな時間経過の中で、いくつかのグラフの上下が入れ替わっていく様子（逆転現象）が捉えられます。

• 50 〜 100 ステップの時点
  探索が少なすぎる $ε = 0.05$ と $0.06$ が下位に沈む中、トップはやはり最大の $ε = 0.1$ が独走しています。その中間に位置する $0.07 \le \varepsilon \le 0.09$ のエリアでは、わずかに $\varepsilon = 0.07$ と $0.08$ がほぼ同等の強さで並んでいます⁶。

$$ε = 0.05 \lt ε = 0.06 \lt ε = 0.09 \lt ε = 0.07 \fallingdotseq ε = 0.08 \lt ε = 0.1$$

• 100 〜 200 ステップの時点
  100 ステップを越えたあたりから、それまで拮抗していた中位集団の並び順に、以下のような逆転現象が発生します。

$$ε = 0.05 \lt ε = 0.06 \lt ε = 0.09 \lt ε = 0.08 \lt ε = 0.07 \lt ε = 0.1$$

この $0.07 \le \varepsilon \le 0.09$ の範囲で起きた順位の入れ替わり（探索の少ない $\varepsilon = 0.07$ が、探索の多い $0.08$ や $0.09$ を逆転していく挙動）は、強化学習の知識獲得のプロセスを物語っています。100 ステップを過ぎたこのあたりの時期になると、探索の確率がわずかに低かった $\varepsilon = 0.07$ であっても、AI の頭の中には「どの台が神台か」を見抜くのに十分なデータがようやく行き渡り始めます。

正解を見抜いてしまえば、あとは探索の確率が低い（＝無駄打ちをしない）ほうが手堅くコインを稼ぐことができるため、中盤に向かうにつれて効率よくスコアを伸ばして逆転できたのだと推測できます。

「探索がまだ十分ではない時期」ということは、裏を返せば、AI が頭の中で見積もっている確率のブレ（エピソード間の標準偏差）がまだ大きい時期であることも意味しています。

1,000 回という大規模なエピソードの平均をとっているとはいえ、この微小な線の上下関係には、まだ乱数のゆらぎ（運の要素）によるブレの影響が多く残っている可能性があります。従って、この序盤のグラフの逆転劇の順序だけを見て「これがアルゴリズムの絶対的な実力差だ」と100 % 断言してしまうのは少し早計です。

そのため、乱数のゆらぎが完全に消え去り、アルゴリズムの「真の実力の終着点」が確定する 200 ステップ以降から1,000 ステップ目にかけての後半戦の挙動 を合わせて検証していくことが重要になります。

200 〜 1,000 ステップ付近の挙動の表示と考察

下記は 200 ステップ以降のグラフを、y 軸の表示範囲を 0.61 から 0.68 へと絞り込むことで拡大して表示するプログラムです。

表示されたグラフでは、データサイズの削減のために NumPy のデータ型を float16（10 進数での有効桁数が約 3 桁）に落としたことが影響し、グラフの後半がわずかにカクカクとした階段状（ギザギザ）に描画される現象が見られます。しかし、全体としての実力の順位関係を読み解くには十分な精度が保たれています。

MAB_Agent.compare_mean_cumulative_reward_by_step(egreedy_agents[5:11], miny=0.61, maxy=0.68)

拡大されたグラフからは、激しい順位の入れ替えが行われていることが読み取れます。

• $\varepsilon = 0.07$ の逆転
  250 ステップを超えたあたりで、それまで常に首位を維持してきた $\varepsilon = 0.1$（茶色）を、緑色の $\varepsilon = 0.07$ が逆転します。その後は一度も首位を譲ることなく、1,000 ステップ目のゴールまで単独のトップを維持し続けています。
• 首位集団の総入れ替え
  序盤（200 ステップ付近まで）にあれほど強かった $\varepsilon = 0.1$ は、後半に進むにつれて無駄な探索の多さが重荷となり徐々に失速していき、最終的には、下から 3 番目の順位まで落ち込んでいきます。
• 底辺を這う $\varepsilon = 0.05$
  前節の $0 \le \varepsilon \le 0.05$ の検証では常にトップに君臨していたはずの $\varepsilon = 0.05$（青色）のグラフは、この $\varepsilon \ge 0.05$ の強豪が集まるグループの中に入ると、一転して最下位に沈んでいます。これは、$0 \le \varepsilon \le 0.1$ の範囲で見ると、最適なパラメータの山が $\varepsilon = 0.05$ より大きな値であることを数学的に意味しています。

ここまでのパラメータ探索の中間まとめ

ここまでの詳細な検証結果により、$0 \le \varepsilon \le 0.1$ の範囲における「制限時間（ステップ数）に応じた最強の作戦（$\varepsilon ^{*}$）」の変遷が、以下のようになることがわかりました。

• 50 ステップ以下の超短期戦
  どの設定値でも得られる探索データが少なすぎるため、実力に意味のある差が出ない。

$$\varepsilon ^{*}\approx \text{判別不能}$$

• 50 〜 250 ステップの短期戦
  ゲームがすぐに終わってしまうため、多少の無駄を覚悟で強気にデータを集めにいく作戦が最強となる。

$$\varepsilon ^{*}\approx 0.1$$

• 250 〜 1,000 ステップの中期戦
  中盤までに神台の特定が完了するため、後半戦で無駄な寄り道を極力抑え込む $ε=0.07$ の作戦が一番手堅く稼げる。

$$\varepsilon ^{*}\approx 0.07$$

この結果から、今回の目的である「1,000 ステップのゲーム」における真の最適解 $\varepsilon ^{*}$ は、当初にアタリを付けていた 0.1 ではなく、「0.07」付近の値であることが実証されました。

$ε$ が 0.07 を超えると得られるコインの平均が減少することから、$\varepsilon ^{*} \approx 0.07$ である可能性が極めて高いことが推測されますが、そのことを確定させるためには、まだ検証していない $\varepsilon = 0.11 \sim 0.20$ について検証する必要があります。

0.1 ~ 0.15 の範囲のグラフの描画と考察

残りの検証範囲の前半の、$ε$ が 0.1 ~ 1.5 の範囲のグラフを下記のプログラムで描画します。

MAB_Agent.compare_mean_cumulative_reward_by_step(egreedy_agents[10:16], miny=0.54, maxy=0.68)

実行結果

先程と同様に折れ線グラフが激しく密集して判別が難しいため、時間帯ごとに表示範囲を絞り込んでグラフの拡大表示を行います。なお、先程と同様の理由から、運の要素に左右されすぎる 50 ステップ以下の超序盤は除外します。

50 〜 200 ステップ付近の挙動の表示と考察

下記は 50 ~ 200 ステップの範囲のグラフを、y 軸の表示範囲を 0.60 から 0.64 へと絞り込むことで拡大して表示するプログラムです。

MAB_Agent.compare_mean_cumulative_reward_by_step(egreedy_agents[10:16], miny=0.60, maxy=0.64)

実行結果

範囲を拡大してもトップ集団のグラフは重なりあってはっきりとは判別できませんが、超序盤を抜けたあたりでは $ε= 0.13$、$0.14$、$0.15$ といった探索割合が高めのエージェントたちがトップ集団を形成している様子が確認できます。

まだゲーム全体のデータが圧倒的に不足しているこの時期においては、より強気に、高い確率で探索を選び、1 ステップでも早くスロットマシンの実力を見抜こうとする作戦が有利に働くという傾向がここでも裏付けられました。

200 〜 1,000 ステップ付近の挙動の表示と考察

下記は 200 ステップ以降の範囲のグラフを、y 軸の表示範囲を 0.61 から 0.67 へと絞り込むことで拡大して表示するプログラムです。

MAB_Agent.compare_mean_cumulative_reward_by_step(egreedy_agents[10:16], miny=0.61, maxy=0.67)

実行結果

250 ステップを越えたあたりから、それまでの勢力図とは一転して $ε = 0.1$（青線）が明確に単独首位へと躍り出ます。

そこから先のゴール（1,000ステップ）に向かうにつれて、「$ε$ の設定値が大きいエージェントほど、獲得コインの平均枚数が綺麗に右肩下がりに低迷していく」 という、長期的な理論値（減少モード）の性質が完全に支配する世界へと切り替わっています。

これは、既にすべての台の正解（スロット 2 が神台）を見抜き終えた中期戦以降では、余計な探索確率を大きく残してしまっている設定ほど、ハズレ台を引きにいって大損を重ねる「機会損失のペナルティ」が重くのしかかるためです。

ここまでのパラメータ探索の中間まとめ

ここまでの詳細な検証結果により、$0 \le \varepsilon \le 0.15$ の範囲における「ゲームの制限時間（総ステップ数）に応じた最強の作戦（$\varepsilon ^{*}$）」の変遷が、以下のようになることがわかりました。

• 50 ステップ以下の超短期戦
  どの設定値でも得られる探索データが少なすぎるため、実力に意味のある差が出ない。

$$\varepsilon ^{*}\approx \text{判別不能}$$

• 50 〜 250 ステップの短期戦
  ゲームがすぐに終わってしまうため、先程と同様に多少の無駄を覚悟で強気にデータを集めにいく作戦が最強となる。このグループ内では $\varepsilon = 0.15$ が優勢となる。

$$\varepsilon ^{*}\approx 0.15$$

• 250 〜 1,000 ステップの中期戦
  250 ステップを越えるとデータの収集が完全に完了するため、後半戦でいかに寄り道を抑え込むかの勝負になる。その結果、今回のグループ内（$0.1 \le \varepsilon \le 0.15$）での最小の探索率である $\varepsilon = 0.1$ が首位となるが、これまでの検証結果と合わせることで「$\varepsilon = 0.07$」が 1,000 ステップを戦い抜く上での真の最強作戦（最適解）であることが実証された。

$$\varepsilon ^{*}\approx 0.07$$

0.15 ~ 0.20 の範囲のグラフの描画と考察

ここまでの詳細な検証によって「短期的な性質」の全貌が見えてきましたが、念のために残された最後の領域である $ε$ が 0.15 ~ 0.2 の挙動をグラフで確認し、これまでの考察が正しいことを裏付けることにします。

MAB_Agent.compare_mean_cumulative_reward_by_step(egreedy_agents[15:21], miny=0.54, maxy=0.68)

実行結果

250 ステップ以降の後半戦に注目すると、線が密集していながらも綺麗な階層を保っており、グラフ同士が交差するような逆転現象は一切起きていません。ここでは完全に長期戦の理論が支配しており、「$ε$ が大きければ大きいほど、無駄な探索（ハズレ台の引き損）が増えて平均獲得コインが低迷する」 という右肩下がりの性質が確認できます。

一方、まだデータが集まりきっていない 250 ステップ以下の序盤戦のグラフは重なり合っておりうまく判別できません。そこで、変化の激しい「50 〜 250 ステップ」の範囲だけを、y 軸を 0.58 から 0.64 へと絞り込んで拡大表示することにします。

MAB_Agent.compare_mean_cumulative_reward_by_step(egreedy_agents[15:21], miny=0.58, maxy=0.64)

拡大したグラフを観察すると、以下のようなことがわかります。

• 200 ステップ未満の超序盤戦
  この範囲の中で 2 番目に高い探索率である $\varepsilon = 0.19$（紫色）が一時的にトップを走り、ステップ 200 の直前で、このグループ内で最も探索率の低い $\varepsilon = 0.15$（青色）に抜き去られています。
• 逆転が起きる理由
  $\varepsilon$ を $0.19$ という高い値に設定すると、ハイペースでスロットマシンが試行されるため、スタート直後のわずか 100 ステップ程度で「どの台が神台か」の見極め（十分な探索）が最速で完了します。そのため、他のライバルがまだ勘違いに惑わされている超序盤に限っては、このほぼ最速の知識獲得がアドバンテージとなって首位に立てるのです。しかし、正解を見抜き終えた後は、高い探索率がそのまま「ハズレ台を引きにいく無駄」へと変わるため、200 ステップの手前という極めて早い段階でこの無駄がメリットを上回り、失速（逆転）してしまいます。
• 探索のメリットの頭打ち：
  この時間帯のグラフはどの線もほぼ同じ位置にぴったりと重なり合っています。この現象から、短期戦におけるメリット（探索によって知識を早く得る恩恵）は、およそ $\varepsilon = 0.20$ あたりの設定で「単調増加の限界（頭打ち）」を迎えている ことが数学的に推測できます。これ以上探索率を上げても「早く見抜くメリット」は増えず、「無駄な探索による損失」というデメリットだけが膨らんでいくため、これより右側の領域（$\varepsilon \gt 0.20$）を調べる必要がないことが改めて実証されました。

全体のまとめと考察

今回の記事で行ってきた大規模シミュレーションと詳細な検証により、冒頭で立てた下記の 2 つの仮説 が正しいことが、実際のデータによって実証されました。

1. ε-greedy 法の平均獲得コイン（$\bar{f}(s, ε)$）のグラフは、横軸（x 軸）を $ε$ とすると、「最初は右肩上がりに登り、ピークを過ぎると右肩下がりに下がる」という、綺麗な山形のグラフ（凸関数）を描く
2. その山の頂点（最大値）、すなわち 「探索が足りない（有益）」から「探索が十分（無駄）」へと切り替わる境界線が、今回の本題である「最適な探索と活用のバランスを表す $ε^*$」になる

また、今回の実験を通じて、時間制限（ステップ数 $s$）の長さに応じて、最強のハイパーパラメータ $\varepsilon^{*}$ の値が次のように変化していく性質が明らかになりました。

• 50 ステップ以下の超短期戦
  どの設定値でも得られる探索データが少なすぎるため、乱数のゆらぎに埋もれて意味のある実力差が読み取れない。

$$\varepsilon ^{*}\approx \text{判別不能}$$

• 50 〜 250 ステップの短期戦
  ゲームがすぐに終わってしまうため、多少の無駄を覚悟してでも強気に最速でデータを集めにいく作戦が強くなる。ただし、$ε = 0.2$ 前後で $\bar{f}(s, ε)$ の成長の頭打ち（メリットの限界）が見られることから、この期間では $\varepsilon = 0.2$ 前後が最強のパラメータになる。

$$\varepsilon ^{*}\approx 0.2$$

• 250 〜 1,000 ステップの中期戦
  250 ステップを越えると神台の特定が完全に完了するため、後半戦でいかに余計な寄り道を抑え込めるかの勝負になる。これまでの多角的な検証結果を合わせることで、$\varepsilon = 0.07$ が、1,000 ステップを戦い抜く上での真の最適解であることが証明された。

$$\varepsilon ^{*}\approx 0.07$$

$ε$ をさらに細かく刻んでシミュレーションを行うことで、より精度の高い $\varepsilon^*$ を求めることもできますが、そのためには長い時間をかけて追加のシミュレーションを行う必要があります。そうやってより厳密な $\varepsilon^*$ を求めても、肝心の $\bar{f}_{max}(s)$ の値は大きくは変わらないので、本記事ではこれ以上細かい検証は行わないことにします。

時間経過とともに変化する最適解の性質

50 ステップ以下の超短期戦については、グラフから直接読み取ることはできませんでしたが、強化学習の「最初はとにかく探索が重要で、経験が溜まるにつれて徐々に活用が重要になる」という根本的な性質から、$\varepsilon ^{*}$ の数学的な挙動を予測（推測）することができます。

具体的には、ゲームがスタートした瞬間からステップ数が進むにつれて、最適なパラメータ $\varepsilon ^{*}$ の値は、理論上の最大値である「$1$」からスタートし、そこから急激に低下していく と考えられるのです。

上記の説明 $ε^*$ の値が最大の 1 から減少すると断言した点を疑問に感じる人がいるかもしれないので補足します。

ゲームの最初の瞬間（ステップ 0）では、AI はスロットマシンに関する知識を全く持っていません（すべてのスロットマシンの期待値が 0）。知識がゼロである以上、人間が $\varepsilon$ にどんな値を設定していようとも、AI は最初のレバーを完全にランダム（探索と同等）に選ぶしかありません。

従って、ステップ 0 においては $\varepsilon$ がどんな値であっても結果は変わらないため、最適解を「$\varepsilon^* = 1.0$（完全探索）」と定義しても数学的に全く問題はありません。

ここまでの考察の結果を統合すると、ゲームの制限時間（総ステップ数）と、設定すべき最適なハイパーパラメータ $\varepsilon^{*}$ の間には、以下のような関係が存在することがわかります。

• 最序盤（50 ステップ以下）：最大値 $1$ からスタートし、ステップ数の増加に伴って 猛烈な勢いで急激に減少していく
• 序盤（50 ~ 250 ステップ）：$0.2$ 前後の値をとりながら、緩やかに減少していく
• 中盤（250 ~ 1,000 ステップ）：$0.07$ 前後の値をとりながら、さらに緩やかに減少していく
• 後半（1,000 ステップ以降）：十分に調べ尽くした長期戦の世界へ向かうため、最終的に限りなく $0$ を目指して減少を続ける

上記の性質は、強化学習における重要な教訓である、「ステップ数が進めば進むほど、不確実性を解き明かす『探索の価値』は、序盤は劇的に、後半はゆっくりと失われていく」 という本質を表しているのです。

ε-greedy 法の弱点と改良

「ステップ数が進むほど探索の価値が失われていく」という強化学習の本質から、ε-greedy 法には 「正解が完全にわかった後でも、ずっと同じ確率 $\varepsilon$ で気まぐれにハズレ台を引きにいってしまう」 という深刻な弱点（構造的な限界） があることが明らかになりました。

ここまでの記事を読んだ方の中には 「だったら、$\varepsilon$ の値を最初から最後まで固定しないで、ステップ数（時間経過）に応じて、徐々に $\varepsilon$ を小さくしていけば最強の作戦になるのでは？」 と思ったがいるかもしれません。まさに、その直感をそのままにした「アニーリング（annealing：焼きなまし法）」 という強力な ε-greedy 法を発展させたアルゴリズムが存在します。このアニーリングについては今後の記事で詳しく解説します。

アニーリング（焼きなまし）とは、「金属を適切な温度に加熱し、時間をかけてゆっくり冷却することで内部組織を安定させる熱処理」のことです。「ゲームの序盤は熱く激しく冒険（探索）し、終盤に向けてゆっくりと冒険の熱を冷まして（探索の割合を減らす）手堅く稼ぐ（活用）」様子がこの「焼きなまし」と似ていることから、アルゴリズムの名前として採用されました。

今回の記事のまとめ

今回の記事では、ε-greedy 法の「短期的な性質」について、1,000ステップ、1,000 エピソードの大規模なシミュレーションの結果を元に深く考察しました。その結果、最適な探索と活用のバランスを表すハイパーパラメータ $\varepsilon ^{*}$ には、以下の 3 つの重要な性質 があることが実験結果によって実証されました。

1. ε-greedy 法の平均獲得コイン（$\bar{f}(s, ε)$）のグラフは、横軸（x 軸）を $ε$ とすると、「最初は右肩上がりに登り、ピークを過ぎると右肩下がりに下がる」という、綺麗な山形のグラフ（凸関数）を描く
2. その山の頂点（最大値）、すなわち 「探索が足りない（有益）」から「探索が十分（無駄）」へと切り替わる境界線が、今回の本題である「最適な探索と活用のバランスを表す $ε^*$」になる
3. $\varepsilon ^{*}$ の値は、理論上の最大値である「$1$」からスタートし、ステップ数が進めば進むほど、序盤は劇的に、後半はゆっくりと 0 に向かって減少していく

また、この「時間経過とともに探索の価値が失われていく」という性質を考慮して ε-greedy 法の弱点を克服するためのアルゴリズムとして、「アニーリング（焼きなまし法）」のアイデアについて簡単に紹介しました。

次回の記事ではすぐにそのアニーリングの具体的な仕組みや実装の解説を行いたいところですが、実はまだ解説していない重要な問題が一つ残っています。

それは、「今回の実験で導き出した結論は、他の設定のスロットマシンでも本当に通用するのか？」 という、アルゴリズムの一般化（汎用性） の問題です。

今回の記事のシミュレーションでは、「3 台のスロットマシンの当たりの確率が [0.3, 0.5, 0.7]」という特定の設定での検証を行いました。その結果、中期戦（250 〜 1,000 ステップ）において $\varepsilon^* \approx 0.07$ という具体的な最強のハイパーパラメータが判明しました。

しかし、もしスロットマシンの台数が 10 台に増えたり、当たりの確率が [0.68, 0.69, 0.70] のような大接戦の環境のように、設定条件が大きく異なった場合に、山の頂点である $\varepsilon ^{*}$ は、それでもなお「0.07」のままでいてくれるのでしょうか？ それとも、環境に応じて全く違う姿を見せるのでしょうか？

そこで次回の記事では、「スロットマシンの設定（環境）を変えたとき、最強の探索と活用のバランスを表す $\varepsilon ^{*}$ がどのように変化するのか」 について、シミュレーションによる実験を踏まえながら詳しく説明します。

本記事で入力したプログラム

今回の記事で行った修正は、ai.py に反映済みです。

リンク	説明
marubatsu.ipynb	本記事で入力して実行した JupyterLab のファイル

次回の記事

近日公開予定です

1. 先ほどの表では、以前の記事の表記に合わせて総ステップ数を $m$ と表記していましたが、ステップ（step）の頭文字の $s$ を使ったほうが直感的にわかりやすいと考えて、以後は $s$ を用いることにします。 ↩

2. $f$ の上にある棒（バー）は、数学や統計学の分野などで「平均値」を表す際によく用いられる記号です。 ↩

3. 例えば、ステップ 0 からステップ 99 まで進んだ場合は、実際の総ステップ数（試行回数）は 100 回になるため、分母が $s + 1$ になります。 ↩

4. 「ステップ $s$ の時点なら、総ステップ数は $s+1$ なのだから、探索回数は $ε \times (s + 1)$ ではないか？」思った人がいるかもしれません。しかし、今問題にしているのは「ステップ $s$ の時点で事前にデータがどれだけ集まっているか」です。その時点ではまだステップ $s$ の行動は行われていないため、ステップ 0 から ステップ $s-1$までの合計 $s$ 回を元にした $ε \times s$ が正しい式になります。 ↩

5. アルゴリズムの性能を比較するための基準点（最悪のベースライン）として、一切探索しない $ε = 0$（貪欲法）だけは例外的に設定します。 ↩

6. $\fallingdotseq$ は左右の値がほぼ等しいことを表す記号です。 ↩