Pythonで〇×ゲームのAIを一から作成する その247 多腕バンディット問題における探索と活用のトレードオフ

目次と前回の記事

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 の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。

今回の記事の内容

前回の記事では、モンテカルロ木探索における、「1 手先（深さ 1）の局面だけに、限られたプレイアウトの総数をどう分配するか」という課題を、「得られるコインの枚数を最大ために、スロットマシンをどのように選択するか」というシンプルな 多腕バンディット問題 に完全に置き換えられることを説明しました。

今回の記事では、多腕バンディット問題の核心である「探索」と「活用」を具体的にどのように行うかについて解説します。また、前回の記事で紹介した目的関数である「累積報酬の期待値（平均してどれくらいコインが稼げるか）」は、実は「探索」と「活用」のバランスが良くないと高くならない仕組みになっています。何故バランスが良くなければ駄目なのかについて説明します。

なお、強化学習の用語や記号については以前の記事と以前の記事を参照して下さい。

「探索」と「活用」のトレードオフ

最初に強化学習のおさらいをした上で、「探索」と「活用」の目的と、それらの間に生じるトレードオフについて説明します。

環境が既知な場合のおさらい（プラニング問題）

以前の記事で説明したように、強化学習の目的は、スタート地点（初期状態）での状態価値(累積報酬の期待値）を最大化する最適方策を見つけることです。

以前の記事では、〇× ゲームのルール（環境の設定）がすべてあらかじめわかっているという前提で¹に、原始モンテカルロ法の最適方策を求める手順を紹介しました。このように、ゲームのルールや確率といった環境の設定が最初からすべて明らかになっている状態で、頭の中でベストな作戦（最適方策）を組み立てる問題を「プランニング問題」と呼びます。プランニング問題の最大の特徴は、「実際にゲームを遊んでみることなく、机の上の数式を解くだけで完璧な作戦を導き出せる」点にあります。すべての情報が最初から見えているため、わざわざ未知の選択肢を試して調べるという「探索」を行う必要は一切ありません。

一般的な強化学習の環境は、多腕バンディット問題よりもはるかに複雑です。そのため、一般的なプランニング問題を数式で解く具体的な手順（動的計画法など）については、今後の記事で紹介する予定です。

環境が未知の場合の探索と活用

残念ながら、現実の強化学習では「プランニング問題」を解くというアプローチを取ることはできません。そもそもルールや確率が分からない「環境が未知の状態」からスタートすることがほとんどだからです。

また、たとえチェスや将棋、囲碁のようにルールが完全にわかっていたとしても、盤面のパターン（状態の数）が膨大すぎるような場合は、数式で完璧な答えを計算しようとすると宇宙が誕生してから今に至るまでの時間をかけたとしてもまったく解くことができなほど時間がかかるため、現実的には不可能です。

そのような場合は、数式を解く代わりにエージェント（AI）が「実際にゲームを遊んでみて、その結果（経験）からルールの確率を推測する」というアプローチをとる必要があります。ここで登場するのが、強化学習の重要キーワードである「探索」と「活用」です。

• 探索（Exploration）：まだ見ぬ可能性を求めて、いろいろな行動を試すこと。原始モンテカルロ法で、どの手が強いかを調べるために「ランダムにプレイアウトを繰り返した処理」が相当する
• 活用（Exploitation）：これまでの経験をもとに「これがベストだ」と判断した行動を選ぶこと。原子モンテカルロ法で、探索で集めたデータから「一番勝率が高かった手」を最善手だと信じて実際に着手することで、勝利（累積報酬の最大化）を目指すという作業が相当する

プランニング問題との違い

プランニング問題との最大の違いは、「AI がデータをもとに『これがベストだ』と推測した選択肢は、本当の正解（本物の最適方策）とはズレているかもしれない」という点にあります。たまたま最初の数回で調子が良かっただけの「見かけ倒しの選択肢」を活用し続けてしまったり、逆に本当は100 点満点なのに 1 回目にたまたま失敗したせいで最善手を無視してしまうという危険性が常に付きまといます。

探索と活用のトレードオフ

当然ですが、AIの「推測の精度」は実験データ（経験）が多ければ多いほど高くなります。つまり、「探索」を行なえば行うほど、本当のルールや確率に近づく ということです。

しかし、ここには大きなジレンマがあります。探索とは、中身を知るためにあえてランダムな手（最適とは程遠い手）を試す行動です。そのため、探索をしている最中は、ゲームに負けやすくなり、得られる累積報酬（コイン）がどうしても低くなってしまうのです。

そのため、強化学習には下記の「トレードオフ（二者択一）」の関係が付きまといます。

• 探索を増やす： 未来の活用のための「推測の精度」は上がるが、その時点で得られる「即時報酬」は減る
• 活用を増やす： その時点で得られる「即時報酬」は稼げるが、データ不足で間違った作戦を選び続ける危険性が上がる

このことから、累積報酬を最大にするためには、限られた時間（プレイ回数）の中で「探索」と「活用」のどちらか片方に偏るのではなく、両者をいかにバランスよく割り当てるかが極めて重要 になります。

原始モンテカルロ法における極端な「探索」と「活用」の割り当て

ここで、以前に実装した「原始モンテカルロ法」における「探索」と「活用」の割り当てについて考えてみることにします。このアルゴリズムの探索と活用は、次のようなアルゴリズムで行われます。

• 決められた回数（または時間）のほぼすべてを使って、ひたすら「探索（プレイアウト）」を繰り返す
• 探索で得られたデータの中で、勝率が一番高い手を「活用」して、本番の 1 手を選択する

上記から、原始モンテカルロ法は「先に探索を 100 % 済ませてから、最後に活用を 1 回だけ行う」という、時間を限界まで「探索」に全振り した極端な割り当て方を行うアルゴリズムであったことがわかります。

この極端な割り当て方のせいで、「探索の途中で得られたせっかくの経験を、その後の探索にまったく活かせない」という重大なデメリットが生じます。

例えば、100 回のプレイアウトのうち、最初の 10 回で「どうやらこの合法手は絶対に勝てない（真の勝率が著しく低い）」ことが薄々わかってきたとしても、原始モンテカルロ法は途中で作戦を変更できません。残りの 90 回も、その「絶対に勝てない合法手」に対して、バカ正直に平等な回数のプレイアウト（探索）を割り当て続けてしまいます。これが、以前の記事で紹介した「真の勝率が低い局面に対する無駄なプレイアウトの割り当て」が発生する原因です。

探索と活用を組み合わせた方策（作戦）の改善

ここからは、多腕バンディット問題における「探索」と「活用」を、具体的なプログラムによるシミュレーションや数式を使って考えていくことにします。「たくさん実験（探索）する」ことと「いまわかっているベストを選ぶ（活用）」ことをどんなバランスで組み合わせれば、AI の方策（作戦）が最も効率よく改善（進化）していくのかを説明します。

前回の記事で説明したように、多腕バンディット問題は、考えるべき状態がたった 1 つしか存在しないという、強化学習の中で極めてシンプルな問題です。そのため、複雑な数式を使わずに、アルゴリズムの核心である「探索と活用」の本質を理解できるという大きなメリットがあります。

より複雑な強化学習での探索と活用については、今後の記事で紹介する予定です。

多腕バンディット問題の設定

以後の説明では、前回の記事で説明した強化学習としての多腕バンディット問題の記号を用いて説明を行うことにします。

最初に強化学習としての多腕バンディット問題の設定のおさらいを行います。多腕バンディット問題は下記のように、$n$ 台のスロットマシンがあり、合計 $m$ 回レバーを引くチャンスがある中で、「手に入るコインの総数（累積報酬の期待値）」をどれだけ増やせるか（最大化）という問題です。

• スロットマシンの台数：$n$ 台
• 各スロットマシンのコインが当たるの確率：$p_i$²
• スロットマシンのレバーを引く総数：$m$

文字のままだと少しイメージしづらいので、ここからは下記のような具体的な数値を当てはめてながら説明を進めていきます。

• スロットマシンの台数：$3$ 台
• 各スロットマシンの当たりの確率：$0.3, 0.5, 0.7$
• スロットマシンのレバーを引く総数：$100$

上記の設定で、それぞれのスロットマシンの設定を知らないものとして、コインを最も稼ぐ方法について少し考えてみて下さい。

多腕バンディット問題の最高得点（目的関数の最大値）の計算

今後さまざまな AI の作戦（アルゴリズム）を紹介していきますが、それらの性能を評価するためには、まず「理論上の最高得点」を知っておく必要があります。AI が稼いだコインがこの最高得点に近ければ近いほど、「優秀なアルゴリズムだ」と判断できるからです。

多腕バンデット問題では、スロットマシンのレバーを何度引いても、各マシンの当たりの確率が変わらないという性質があります。そのため、$m$ 回レバーを引いて得られるコインの総数の期待値（目的関数）を最大化する方策は、複雑な数式を用いるまでもなく 最初から最後まで当たりの確率が最大となるスロットマシンのレバーを引き続ける ことになります。

一番当たる確率が高いスロットマシンの番号を $max$、その当たる確率を $p_{max}$ とします。このとき、合計 $m$ 回レバーを引いて得られるコインの期待値の最大値（$f_{max}$) は、単純な掛け算で次のように表せます。 

$$f_{max} = m \times p_{max}$$

この「一番良い台だけを引き続ける」という、理論上の最強の作戦を、強化学習の「方策関数 $\pi(a \mid s)$」の数式で表すと、以下のようになります。

$π(a \mid s) = \begin{cases}
1 & \text{行動 }a \text{ が }max \text{ 番のレバーを引くとき}\\
0 & \text{それ以外のレバーを引くとき}
\end{cases}$

上記の数式の意味はとても単純です。「状態 $s$ の場合に、確率 $1 (100 \%)$ で $max$ 番の台を選び、それ以外の台を選ぶ確率を $0(0 \%)$ にする」という、一点全振りの極端なルールを数学的に書いているだけです。

多腕バンディット問題では、エージェントが意思決定を行う状態 $s$ が 1 つしか存在しないため、作戦を表す方策関数もこのように 1 つの状態 $s$ だけを考えたシンプルな式で表すことができます。

具体例の場合

先ほど決めた具体的な設定（3 台のマシンの確率が 0.3, 0.5, 0.7）を当てはめると、一番当たりやすいのは「2 番のマシン（確率 $0.7$）」³なので、$max = 2$ となります。

そのため、下記の方策に従って常に 2 番のスロットマシンのレバーだけを 100 回引き続けることができれば、得られるコインの枚数の期待値は最大値である $f_{max} = 0.7 \times 100 = 70$ 枚となります。

$π(a \mid s) = \begin{cases}
1 & \text{行動 }a\text{ が 2 番のレバーを引くとき}\\
0 & \text{それ以外のレバーを引くとき}
\end{cases}$

つまり、今回の設定における絶対的な最高得点は「70 枚」であることがわかりました。

最大値には絶対に到達しないという現実

上記で計算した「70 枚」という最高得点は、あくまですべての確率があらかじめ見えているという、神様の視点で計算したスコアです。

実際の多腕バンディット問題では、どのマシンが何 % で当たるかは完全に秘密にされています。もし AI が 100 点満点の $f_{max}$（70 枚）のコインを得ようと思ったら、「何も知らない状態の 1 回目から、100 回連続で一番当たりの良い 2 番のマシンを選択し続ける」という、超能力か神業のような奇跡を起こさなければなりません。

もちろん、「カジノの経営者に賄賂（わいろ）を渡してこっそり設定を教えてもらう」といったズル（不正）をしない限り、そんな魔法のようなアルゴリズムは存在しません。確率を調べるために他の台を様々なスロットマシンを試した（探索）時点で、最高得点の 70 枚からは必ず数枚分のコインがマイナスされていくことになります。

従って、多腕バンディット問題の本質 は、絶対に作ることができない「理論上の最高得点（$f_{max}$）を取るアルゴリズムを作ること」ではなく、「限られた情報の中で、いかに理論上の最高得点に限界まで近づける賢い作戦（アルゴリズム）を編み出すか」という点にあることを覚えておいてください。 

「3 台のうち 1 台が当たりなら、当てずっぽうで選んだ 1 台を 100 回引き続ければ、$1/3$ の確率で最高得点の 70 枚をゲットできるから『神業』は大げさでは？」と思った人がいるかもしれません。

確かに、運が良ければ結果的に最高得点に届くことはあります。しかし、ここで「神業」と言っているのは、たまたま運良く当てることではありません。 多腕バンディット問題（強化学習）の本質は、「中身がまったく分からない状態で、1 回目から 100 % 確実に、一番当たるマシンを狙い撃ちできる『魔法のような数式（アルゴリズム）』を作れるか」という点にあります。情報がゼロの状態で、いつでも絶対に正解のスロットマシンを選び出すアルゴリズムを考えることは、人間にも AI にも不可能な「神業」である ことは、言うまでもないでしょう。

多腕バンディット問題における「探索」と「活用」

以前の記事では、モンテカルロ木探索における「探索」と「活用」について下記のように説明しました。

• 探索（Exploration）：未知の局面の「本当の実力（真の勝率）」を正しく推測するために、いろんな手を幅広く試すこと
• 活用（Exploitation）：これまでに行った探索から「この手が強そうだ」とわかった有望な手に、プレイアウトを多く割り当てる（えこひいきする）こと

これを、今回のテーマである「多腕バンディット問題（スロットマシン）」に当てはめると、次のようになります。

• 探索（Exploration）：各スロットマシンの「コインが当たる確率」を正しく推測するために、いろんなスロットマシンを幅広く試すこと
• 活用（Exploitation）：これまでに行った探索から「儲かりそうだ（コインがでやすそうだ）」とわかった有望なスロットマシンを集中的に選択する（えこひいきする）こと

ただし、「幅広く試す」や「集中的に選択する」といった抽象的な説明のままだと、プログラムで記述したり、数学的に計算したりすることができません。そこで、これらの作戦を「方策関数 $\pi(a \mid s)$」の数式に落とし込む作業（定式化）を行うことにします。数式という共通の物差しに直すことで、「この作戦だと、100 回で何枚のコインが手に入るか」を計算できるようになります。

「探索（完全なランダム）」を表す方策の定式化

「探索」の目的は、先入観（それまでの経験）にとらわれずに、スロットマシンの本当の確率を調べるための実験データを集めることです。

最もシンプルで裏表のない探索方法は、「これまでの結果がどうであれ、すべての台を完全にランダム（平等）に試す」という作戦です。今回の記事ではは、このランダムな探索の性質について詳しく説明します。

探索のアルゴリズムの中には、モンテカルロ木探索で用いられる「UCB1」のように、未知の状態を効率よく調べるために これまでに試していなかった行動を積極的に選択する という少し賢い方法もあります。UCB1 については今後の記事で詳しく紹介する予定です。

スロットマシンが全部で $n$ 台あるとき、完全に平等にランダムで選ぶということは、どの台も $\frac{1}{n}$ の確率で選ぶ ということです。この「完全にランダムに選択する作戦」の方策関数は、次のように定義できます。

$$\text{すべての行動 }a \in \mathcal{A} \text{ に対して、 }π(a \mid s) = \frac{1}{n}$$

先程の具体的な設定では、スロットマシンの台数が 3 なので下記のようになります。

$$\text{すべての行動 }a \in \mathcal{A} \text{ に対して、 }π(a \mid s) = \frac{1}{3}$$

オセロや将棋のように「複数の状態（局面）」が存在する一般的な強化学習で、完全にランダムな探索を行う場合の方策関数は次のように定式化されます。ただし、$\mathcal{A}(s)$ は状態 $s$ でとることができる行動の集合を、$|\mathcal{A}(s)|$ は行動の数を表します。

$\text{すべての状態 }s \text{ に対して、}π(a \mid s) = \begin{cases}
\dfrac{1}{|\mathcal{A}(s)|} & a \in \mathcal{A}(s)\\
0 & a \notin \mathcal{A}(s)
\end{cases}$

多腕バンディット問題は「いつでも $n$ 台すべてのレバーを引ける（反則手がない）」ため、上の数式の 1 行目の $\frac{1}{n}$ だけで方策関数を簡潔に表すことができます。

「活用」を表す方策の定式化

現実の多腕バンディット問題では、どのスロットマシンが何 % で当たるかは秘密です。そのため、それまでに行った「探索と活用」によって集められたデータ（経験）を元に「これが一番当たりそうだ」と推測した、現時点で最高と思われるマシンのレバーを集中的に引くことが「活用」の具体的な行動になります。

上記の『「探索と活用」によって集められたデータ』について、『「探索」によって得られたデータだけを使うのではないか？』思った人がいるかもしれません。実は、「活用」として選んだ行動からデータも立派な経験として蓄積されます。その理由は 「活用」であっても下記のような経験が得られることに変わりはない からです。

• 思い描いていた通りの結果が得られることによって、「間違いなく正しい」と考えていたことの確証が得られる
• ごくたまに思わぬ発見が得られることがある

例えば、いつもお気に入りのラーメンを頼んで「やっぱりこの店はこれが一番美味い」という確信が深まるように、活用を繰り返すことで「この台はやっぱり間違いなく最も当たる台だ」という確証（データの信頼度）が高まっていきます⁴。また、活用を続けるなかで、ごくたまに思わぬ新事実が見つかることもあります。

スロットマシンの当たりの確率を推測する方法はシンプルで、「各スロットマシンでこれまでに得られたコインの平均値（標本平均）」を計算します。スロットマシンの確率は何度引いても変わらない（独立同分布）ため、レバーを引く回数を増やせば増やすほど、以前の記事で詳しく説明した大数の法則から得られたコインの平均値は「本物のスロットマシンの確率」へと限りなく近づいていきます。

従って、多腕バンディット問題における「活用のアルゴリズム」は下記のようになります。

1. これまでの「探索」と「活用」のすべての履歴データから、各スロットマシンにごとに「コインが当たった回数の平均値」を計算する
2. その平均値をそのスロットマシンの当たる確率とみなして、平均値が一番高かったスロットマシンのレバーを引く

上記の「活用」を表す方策は、下記の方策関数で定式化することができます⁵。

$π(a \mid s) = \begin{cases}
1 & \text{行動 }a \text{ が「コインの平均が最大のスロットマシン」のレバーを引くとき}\\
0 & それ以外の場合
\end{cases}$

上記の活用の方策は、「現時点で一番稼げているスロットマシンだけを確率 $100 \%$ で選び、それ以外のスロットマシンはすべて $0 \%$ で無視する」という、目の前の利益に全振りした決定論的な作戦 を数学的に表現しています。 

今回の記事で紹介した「活用」の方策は、1 台のスロットマシンにすべてを賭ける「決定論的」な活用方法です。これに対して、「平均値が高いマシンほど『選ばれる確率』を高めにする」という、柔軟な「確率的」な活用アルゴリズムも存在します。その代表例である「ソフトマックス方策」については、今後の記事で詳しく紹介する予定です。

「経験」によって進化する活用の方策

ここまでに説明した 2 つの作戦（方策）には、以下のような決定的な違いがあります。

• 探索（ランダム）の方策：これまでに何回レバーを引いたか（ステップ数）に関係なく、各スロットマシンを選択する確率は最初から最後までずっと一律で $\pi(a \mid s) = \frac{1}{n}$（具体例では $\frac{1}{3}$）のまま変わらない
• 活用（えこひいき）の方策：それまでに得られたデータ（経験）をもとにその都度方策を計算し直すため、レバーを引けば引くほど、作戦の内容（$100 \%$ の確率を割り当てるスロットマシン）が次々と変化（進化）していく

最初はたった 1 回のマグレ当たりで「0.3 のハズレ台」を最高のスロットマシンと勘違いして活用していたとしても、回数を重ねてデータが蓄積されれば、大数の法則によって各スロットマシンの本当の実力（確率）が見えてきます。その結果、AI は「やっぱりあっちの台の方が優秀だ！」と気づき、より正しいマシンが選択されるように方策が進化（アップデート）していきます。

以前の記事で説明した、下記の 強化学習の定義の言い換え を覚えているでしょうか。

『強化学習は、エージェントと環境が「方策に従う行動」と「その結果変化した状態と得られた報酬の報告」という相互作用を繰り返して得られた経験を元に方策を改善することで、累積報酬の期待値を最大化するような方策を学習するという仕組みである』

先程説明した「探索」と「活用」を表す作戦（方策関数）の組み合わせは、まさにこの 「経験を元に作戦をどんどん改善していく強化学習の仕組み」そのものを数学的に表現 したものなのです。

多腕バンディット問題の本質

ここまでの説明から、「探索」と「活用」という全く性質の異なる 2 つの作戦を、方策関数という数式で定式化することができました。これらを踏まえると、多腕バンディット問題という、一見するとシンプルなスロットマシンのゲームの本質が、合計 $m$ 回（具体例では 100 回）レバーを引くチャンスがある中で、「今の 1 回は、データを集めるための『探索』に使うべきか？ それとも、コインを稼ぐための『活用』に使うべきか？」を、毎ステップごとに賢く選び分ける最適化問題 であることがわかります。

この「毎回の選択」を、どのようなアルゴリズムで制御すれば、最高得点の 70 枚にギリギリまで近づけることができるかについては、次回以降の記事で詳しく説明します。

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

強化学習における目的関数は、AI がどれだけ目標をうまく達成されたか を表す指標となるスコア（数値）です。例えば、本記事の題材である 〇× ゲームの場合は「勝利する」ことが目標だったので、スコア（目的関数）には「勝率の期待値」を設定しました。

一方、Wikipedia の解説にもある通り、多腕バンディット問題は 「探索と活用のジレンマ（トレードオフ）」を研究するために生まれた歴史ある問題 です。

そのため、多腕バンディット問題のスコア（目的関数）である 「累積報酬の期待値（平均してどれくらいコインが稼げるか）」は、「探索」と「活用」のバランスが良くないと高得点にならない という、面白い性質を持っています。

ここからは、なぜこの目的関数が「作戦のバランスの良さ」を正しく評価できる指標（物差し）になるかについて説明します。

目的関数の計算方法

多腕バンディット問題では、合計 $m$ 回（具体例では 100 回）レバーを引く中で、AI は毎回「探索」か「活用」のどちらかの作戦を選んで行動します。そこで、この 2 つの行動が最終的なスコアにどんな影響を与えるのかを、別々に切り分けて考えてみることにします。 

最終的なスコア（目的関数 $f$）は、「探索によって稼いだコインの期待値 $f_{探}$」と、「活用によって稼いだコインの期待値$f_{活}$」の 2 つの合計を求める下記の式で計算できます。

$$f = f_{探} + f_{活}$$

この「探索の稼ぎ（$f_{探}$）」と「活用の稼ぎ（$f_{活}$）」のそれぞれの内訳がどうなっているかについて、具体的な数字を当てはめてながら計算を進めていくことにします。

数式の添字に上記のような日本語が用いられることはあまりありませんが、探索（Exploration）と活用（Exploitation）は英語の綴り（スペル）がそっくりなため、数式の添字に記述すると見た目の区別がつかなくなってしまいます。そこで、本記事ではこの 2 つを一目で直感的に区別できるよう、あえて添字に日本語の「探」と「活」を採用しました。

「探索」で稼げるコインの期待値

探索ではランダムにスロットマシンを選択してレバーを引くため、「1 回の探索によって得られるコインの期待値」は、すべてのスロットマシンの当たりの確率を足して、台数で割った「平均値（mean）」 になります。その平均の確率 $p_{mean}$ と表記すると $p_{mean}$ は下記の式で計算することができます。

$$p_{mean} = \frac{\sum_{i=1}^{n}p_i}{n}$$

従って、$m$ 回のうち「探索」に割り当てた回数を $m_{探}$ と表記すると、探索によって稼げるコインの総数の期待値を表す $f_{探}$ は下記のシンプルな掛け算でで求めることができます。

$$f_{探} = m_{探} × p_{mean}$$

今回の設定（3 台の確率が 0.2, 0.5, 0.8）に当てはめてみると、すべての確率の平均値 $p_{mean}$ は次のようになります。 

$$p_{mean} = \frac{0.3 + 0.5 + 0.7}{3} = 0.5$$

このことから、どの台も平等に引くと平均して「2 回に 1 回当たる（確率 0.5）」ことがわかります。従って、今回の設定における探索のスコアは、以下の式で計算できます。

$$f_{探} = m_{探} × 0.5$$

例えば、100 回のうち 30 回を探索に使った場合は、平均して $30 × 0.5 = 15 枚$ のコインが探索で稼げることになります。

「活用」で稼げるコインの期待値

活用では「これまでのデータ（平均値）が一番高かったスロットマシンのレバーを引く」という、コインをできる限り多く稼ぐための選択 を行います。

以前の記事で統計学（正規分布）を使って証明したように、AI がデータの誤差に騙されず、本当の（確率 0.7 の）最高に当たりやすいスロットマシンを見極めて選択できる確率は、これまでに各スロットマシンをどれだけバランスよく、十分に選択（探索）できていたかによって決まります⁶。

このことから、コインをできるだけ多く稼ぐために行う「活用」で 1 回あたりで稼げるコインの期待値 には、次のような性質があることがわかります。

• 探索が十分な場合：「すべてのスロットマシンを均等に選択する」という、「探索」が多く行われていればいるほどデータの信頼度（精度）が高まります。その結果、AI は勘違いすることなく「確率が 0.7 の最高のスロットマシン」を選べるようになり、活用したときのコインの期待値は最大値である $p_{max}$（0.7 枚） に限りなく近づきます。 
• 探索が少ない場合：探索が不十分であるとデータの信頼度が低くなるため、当たる確率が低いスロットマシンでそれまでに得られたコインの枚数が偶然一番多くなった結果、間違ったスロットマシンを勘違いして選択する確率が高くなります。その結果、間違ったスロットマシンをえこひいきして選択し続ける可能性が高くなるため、活用したときのコインの期待値は低くなってしまいます。

このように、「事前にどれだけ探索を済ませておいたか」が、その後の活用の稼ぎの効率を大きく左右します。

上記では、探索が少ない場合のコインの期待値が低くなると説明しましたが、具体的にどれくらい少なくなるのでしょうか。そのことを調べるために、まずは「はじめてレバーをく場合」からスタートして、徐々に探索を増やした場合についてシミュレーションを交えて検証を行うことにします。

はじめてレバーを引く場合（探索が 0 回）

まだ一度も実験をしていない、データ（経験）がまったくない状態で、いきなり活用を行なおうとした場合はどうなるでしょうか。

当然ですが、すべてのスロットマシンのデータ（平均値）は 0 のままで横並びになるため、どのスロットマシンの当たりの確率が高いかの見当をつけることはできません。そのため、3 つの台から当てずっぽう（ランダム）に選ぶしかありません。従って、はじめてレバーを引く場合に「活用」を選んだとしても、得られるコインの期待値は探索（完全なランダム）と同じ $p_{mean} = 0.5$ になってしまいます。 

探索の回数が極めて少ない場合（探索が 1 ~ 4 回）

それでは、活用を行う前にほんの数回（1 ~ 4 回）だけ探索を行うとどうなるでしょうか。

探索が少なすぎると、大数の法則が全く働かないため「データの大きな誤差」が発生します。例えば、確率 $0.7$ の最高の当たり台を活用で選択して運悪くハズレが出た場合は、AI のデータ上は「この台の期待値は 0（確率 0 %）だ」と記録されてしまいます。逆に確率 $0.3$ のハズレ台でマグレ当たりが出ると「この台は期待値 1（確率 100 %）の当たり台だ」と勘違いしてしまうのです。

このように、探索が少なすぎる場合は「活用」のよりどころとなるデータの精度が低くまったくあてにならないため、「活用」を行っても、AI は高確率でハズレ台を選択してしまいます。結果として、活用の期待値は最高得点である $p_{max} = 0.7$ からは程遠いスコアになってしまいます。

シミュレーションによる検証

この「早すぎる活用はうまくいかない」という現象を、実際にプログラムによるシミュレーションで検証してみることにします。具体的には事前に「0 回〜 4 回」の探索を行った後で、それぞれ 10 万回の活用を繰り返したときのスコア（得られたコインの平均）を計算するプログラムです。

プログラムの変数の意味は以下の通りです。

変数	意味
mab	当たる確率が 0.3, 0.5, 0.7 の 3 台のスロットマシンを持つ多腕バンディット問題のシミュレーションを行う MAB クラスのインスタンス（MAB クラスについては 前回の記事を参照）
num	活用を行う回数（10 万回）
tnum	活用の前に行う探索の回数。0 ~ 4 回のそれぞれの値に対する処理を 7 ~ 30 行目のループで行う
exploitation_coins	活用（exploitation）で得られたコインの枚数を表す list
bestarm_selectnum	活用で各スロットマシンが選択された回数を表す list
total_coin	tnum 回の探索で各スロットマシンで得られたコインの総数を表す list
mean_coin	tnum 回の探索で各スロットマシンで得られたコインの平均を表す list
selectnum	tnum 回の探索で各スロットマシンが選択された回数を表す list
bestarms	tnum 回の探索で得られたコインの枚数の平均が最大となるスロットマシンの番号を表す list
bestarm	活用で選択するスロットマシンの番号（bestarms の中からランダムに選択する）

• 7 ~ 30 行目：0 ~ 4 回の探索を行う繰り返し処理
• 10 ~ 28 行目：「tnum 回の探索の後に活用を行う」処理を 10 万回行う繰り返し処理
• 14 ~ 19 行目：tnum 回の探索を行い、その結果を記録する処理
• 20 ~ 27 行目：探索の後の活用を行う処理
  • 21 ~ 24 行目：得られたコインの枚数の平均が最大となるスロットマシンが複数存在する可能性があるため、最初に最大値を計算し、最大値と一致するスロットマシンの番号を bestarms に記録する
• 28 ~ 30 行目：探索を tnum 回行った場合の結果を表示する

 1  from ai import MAB
 2  import numpy as np
 3  
 4  mab = MAB(p = [0.3, 0.5, 0.7])
 5  
 6  num = 100000
 7  for tnum in range(5):
 8      exploitation_coins = []
 9      bestarm_selectnum = [0] * 3
10      for _ in range(num):
11          total_coin = [0] * 3
12          mean_coin = [0] * 3
13          selectnum = [0] * 3
14          for _ in range(tnum):
15              arm = np.random.choice(3)        
16              if mab.play(arm) > 0:
17                  total_coin[arm] += 1
18                  selectnum[arm] += 1
19                  mean_coin[arm] = total_coin[arm] / selectnum[arm]
20          bestarms = []
21          max_coin = max(mean_coin)
22          for arm in range(3):
23              if mean_coin[arm] == max_coin:
24                  bestarms.append(arm)
25          bestarm = np.random.choice(bestarms)
26          bestarm_selectnum[bestarm] += 1
27          exploitation_coins.append(mab.play(bestarm))
28      print(f"探索を {tnum} 回行った場合")
29      print(f"  活用の期待値: {np.mean(exploitation_coins):.3f}")
30      print(f"  活用で各スロットマシンが選択された回数 {bestarm_selectnum}")

行番号のないプログラム

from ai import MAB
import numpy as np

mab = MAB(p = [0.3, 0.5, 0.7])

num = 100000
for tnum in range(5):
    exploitation_coins = []
    bestarm_selectnum = [0] * 3
    for _ in range(num):
        total_coin = [0] * 3
        mean_coin = [0] * 3
        selectnum = [0] * 3
        for _ in range(tnum):
            arm = np.random.choice(3)        
            if mab.play(arm) > 0:
                total_coin[arm] += 1
                selectnum[arm] += 1
                mean_coin[arm] = total_coin[arm] / selectnum[arm]
        bestarms = []
        max_coin = max(mean_coin)
        for arm in range(3):
            if mean_coin[arm] == max_coin:
                bestarms.append(arm)
        bestarm = np.random.choice(bestarms)
        bestarm_selectnum[bestarm] += 1
        exploitation_coins.append(mab.play(bestarm))
    print(f"探索を {tnum} 回行った場合")
    print(f"  活用の期待値: {np.mean(exploitation_coins):.3f}")
    print(f"  活用で各スロットマシンが選択された回数 {bestarm_selectnum}")

実行結果（乱数が使われているため、実行結果は毎回下記の内容と若干異なります）

探索を 0 回行った場合
  活用の期待値: 0.498
  活用で各スロットマシンが選択された回数 [33357, 33467, 33176]
探索を 1 回行った場合
  活用の期待値: 0.527
  活用で各スロットマシンが選択された回数 [26504, 33380, 40116]
探索を 2 回行った場合
  活用の期待値: 0.538
  活用で各スロットマシンが選択された回数 [23515, 33128, 43357]
探索を 3 回行った場合
  活用の期待値: 0.548
  活用で各スロットマシンが選択された回数 [21727, 33504, 44769]
探索を 4 回行った場合
  活用の期待値: 0.545
  活用で各スロットマシンが選択された回数 [21410, 33514, 45076]

シミュレーションの結果から、下記のような予想通りの結果が得られました。

• 探索が 0 回の場合：
  • 活用のスコアの期待値はほぼびったり 0.5（$p_{mean}$）なる
  • 各スロットマシンの選択回数も約 3.3 万回ずつと完全に均等（あてずっぽう）になる
• 探索が 1 ~ 4 回の場合：
  • 探索を増やすごとに、一番優秀な「確率 0.7 のスロットマシン」が選ばれる回数が（約 3.3 万回 $\rightarrow $ 約 4.5 万回）徐々に増えている。これは、AI が少しずつ正解に気づき始めている証拠である
  • それでも活用の期待値は 0.52〜0.54 のように $p_{mean} = 0.5$ の付近で低迷しており、最高得点の 0.7 には、まだまだ遠く及ばない

このように、たった数回の探索（実験）だけでは、本当の当たり台を見極めて大儲けするような「価値のある活用」はできないということが、シミュレーションの結果としてはっきりと示されました。

また、上記の結果から 探索の回数が少ない場合は、1 回の活用の期待値が $p_{mean} = 0.5$ とほぼ同じになる ことがわかりました。

14〜19 行目の探索の処理では、コインの平均を割り算を使って地道に更新しています。一方、29 行目の活用の評価では np.mean という平均を計算する便利な numpy の関数を使って一発で計算しています。

同じ平均を計算する処理をこのように異なる手順で求めている理由は、「探索回数が少なすぎると、一度も選ばれないスロットマシンが出てくるから」です。

一度も引いていないスロットマシンの平均値を np.mean や単純な割り算で計算しようとすると、分母（引いた回数）が 0 であるため計算がうまく行われません⁷。

探索のコインの平均の計算ではそれを防ぐために、あらかじめ平均を表す mean_coin を [0] * 3 で初期化しておき、引いた回数 selectnum[arm] が 1 以上になった台だけを安全に割り算する、という実装上の工夫を行ないました。

バランスが非常に悪い場合（「活用」だけを連続して行った場合）

実験の回数はそこそこあるが、「1 つのスロットマシンだけがこれまで選択され続けている」ような、バランスが非常に悪い場合はどうなるでしょうか。

そのような状況が実際に起こり得るのかという疑問がある人がいるかもしれませんが、例えば最初から 10 回連続して「活用」を行った場合は下記のように 1 つのスロットマシンが 10 回連続で選択されることが高い確率で十分にあり得ます。

具体的には、「活用」だけを行い続けると、以下のように AI が 1 つのスロットマシンだけに執着して思考停止するループ（まちぼうけ状態）が発生します⁸。

• 1 回目：まだデータがないので、あてずっぽうでランダムにスロットマシンを選び、運良くコインが当たった。その結果、選んだ台の平均 = 1, それ以外の台の平均 = 0 がになる
• 2 回目：活用のルールに従い、平均値が最大の 1 である最初に選んだスロットマシンのレバーを引く。選んだスロットマシンの平均は当たった場合が 1、外れた場合が 0.5 になり、それ以外のスロットマシンの平均は 0 になる
• 3 回目：2 回目の当たりはずれの結果に関わらず、最初に選んだスロットマシンの平均だけが必ず 1 より大きく、それ以外の平均は 0 になる。そのため、活用では必ず最初のスロットマシンが選択される
• 4 回目以降：同様の理由で、最初に選んだスロットマシンの平均だけが必ず 1 より大きく、それ以外の平均は 0 になる。そのため、活用では必ず最初のスロットマシンが選択される

このように 「活用」だけを行うと、最初に当たり引いたスロットマシンが最善であるとかたくなに信じ込み、当たりが出ていない他のスロットマシンを一生無視して 同じスロットマシンだけを引き続ける という現象が起きてしまうのです。

たまたま運良く 1 回成功しただけの体験を「これがこの世の真理（正解）だ！」と信じ込んで思考停止し、大失敗した人はいないでしょうか？初心者やせっかちな人にありがちなこの失敗は、童謡の「まちぼうけ」（切り株にウサギがぶつかったのを見て、畑仕事をサボって一生切り株を見張り続けた農夫の歌）の歌詞にそっくりです。興味がある方は下記のリンク先の歌詞を読んでみてください。

もし、最初に当たりを引いたスロットマシンがたまたま確率 0.7 の最高のスロットマシンであれば大勝利ですが、もし確率 0.3 のハズレだったら、AI は一生ハズレを引いて「まちぼうけ」し続けることになります。これは、まさにギャンブルでいう所の、ハイリスク・ハイリターンな作戦です。

シミュレーションによる検証

この「まちぼうけ現象」が起きるとスコアがどうなるのかを、10 万回のシミュレーションプログラムで実際に検証してみることにします。

先ほどのプログラムでは、活用を行うためにそれぞれのスロットマシンで得られたコインの平均を実際に計算する必要がありましたが、今回は「1 回でも当たりが出たら、その台を bestarm として記憶し、以後はその台だけをひたすら引き続ける（＝それ以外の台の平均値 0 を上回り続けるため）」という性質をうまく利用したプログラムにしました。

プログラムの変数の意味は以下の通りです。なお、先ほどのプログラムと同じ意味を持つ変数は省略しました。

変数	意味
coins	10 万回の処理の各回で得られたコインの総数の一覧を表す list
coin	10 回の活用で得られたコインの総数
bestarm	当たりが出た後に選択し続けるスロットマシン。最初はまだ当たりが出ていないので None で初期化する（5 行目）

• 4 ~ 17 行目：10 万回の繰り返し処理
• 7 ~ 17 行目：10 回連続活用を行う繰り返し処理
  • 8 ~ 11 行目：スロットマシンを選択する
    • 当たりが出ていない場合（bestarm が None）はランダムに選択する
    • 当たりが出ている場合は bestarm のスロットマシンを選択する
  • 12 ~ 16 行目：スロットマシンのレバーを引いて結果を記録する処理。当たりの場合はコインを増やし、bestarm がまだ None の場合は bestarm と、そのスロットマシンが選択された回数（bestarm_selectnum）を更新する
  • 17 行目：10 回の活用で得られたコインの総数を coins に記録する

 1  num = 100000
 2  coins = []
 3  bestarm_selectnum = [0] * 3
 4  for _ in range(num):
 5      bestarm = None
 6      coin = 0
 7      for i in range(10):
 8          if bestarm is None:
 9              arm = np.random.choice(3)
10          else:
11              arm = bestarm
12          if mab.play(arm) > 0:
13              coin += 1
14              if bestarm is None:
15                  bestarm = arm
16                  bestarm_selectnum[arm] += 1
17      coins.append(coin)
18  print(f"10 回の活用で得られたコインの平均　　　 {np.mean(coins):5.2f}")
19  print(f" 1 回あたりの活用で得られたコインの平均 {np.mean(coins) /10:5.2f}")
20  print(f"各スロットマシンが選択された回数 {bestarm_selectnum}")

行番号のないプログラム

num = 100000
coins = []
bestarm_selectnum = [0] * 3
for _ in range(num):
    bestarm = None
    coin = 0
    for i in range(10):
        if bestarm is None:
            arm = np.random.choice(3)
        else:
            arm = bestarm
        if mab.play(arm) > 0:
            coin += 1
            if bestarm is None:
                bestarm = arm
                bestarm_selectnum[arm] += 1
    coins.append(coin)
print(f"10 回の活用で得られたコインの平均　　　 {np.mean(coins):5.2f}")
print(f" 1 回あたりの活用で得られたコインの平均 {np.mean(coins) /10:5.2f}")
print(f"各スロットマシンが選択され続けた回数 {bestarm_selectnum}")

実行結果（乱数が使われているため、実行結果は毎回下記の内容と若干異なります）

10 回の活用で得られたコインの平均　　　  5.42
 1 回あたりの活用で得られたコインの平均  0.54
各スロットマシンが選択され続けた回数 [20081, 33345, 46464]

シミュレーションの結果から、活用だけを 10 回連続で行うと下記のような性質があることがわかります。

• 当たりの確率が高いスロットマシンほど多く選択され続ける（確率 0.3 の台が約 2.0 万回、0.5 の台が約 3.3 万回、確率 0.7 の台が約 4.6 万回）
• 1 回あたりの活用で得られたコインの平均（0.54）は $p_{mean} = 0.5$ よりも若干高くなる

活用しかしていないのに、「一番良い確率 0.7 のスロットマシンが一番多く選ばれている」、「平均も 0.5 より高い」という上記の結果の見た目から、『実は「活用」のみを行う作戦は意外と優秀ではないか？』と思った人がいるかもしれませんが、それは強化学習の初心者によくある大きな勘違い（罠）です。

当たりの確率が高いスロットマシンほど多く選択され続ける理由

下記は「活用」だけを行った場合に、特定のスロットマシンが選択され続ける条件です。

• まだ当たりが一度も出ていない
• そのスロットマシンがランダムに選択される
• レバーを引いて当たりが出る

当たりが出ていない状態では、すべてのスロットマシンが同じ確率で選択されます。従って、最後の条件から明らかに「当たりが出る確率」が高いスロットマシンほど最初に当たりを引いて選択され続ける確率が高くなります。

つまり、当たりの確率が高いスロットマシンほど多く選択され続けるという事実は、ごく当たり前の現象にすぎません。

ここで重要なのは、「確率 0.3 の最悪なハズレのスロットマシンも、2 万回（全体の 20 %）もの確率で『最高のスロットマシンだ』と勘違いされて、一生引き続けられている」という悲惨な事実です。そのせいで、1 回あたりの稼ぎは理論上の最大値 $f_{max} = 0.7$ からほど遠い 0.54 になってしまいます。もし事前にしっかり探索をして「2 番が最高だ」と 100 % 確信できていれば、活用の期待値を 0.7 にできたはずです。それと比べると、今回の 0.54 というスコアは、チャンスを大きくドブに捨てていることがわかります。

「活用だけ」でも全体の平均を上回る理由

事前の探索をせず、最初から「活用」だけを行った場合に、1 回あたりの稼ぎの平均は、（完全にランダムな）探索を行った場合の $p_{mean} = 0.5$ よりも 必ず高い値 になります。その理由は、下記の確率の「引っかかりやすさ」にあります。

• 確率が高い優秀なスロットマシン：あてずっぽうの 1 回目で、$70 \%$ や $90 \%$ といった高確率で一発で当たりを引く。そのため、すぐに「活用され続ける台」として選ばれやすくなる
• 確率が低いハズレなスロットマシン：あてずっぽうで選ばれても、$10 \%$ や $30 \%$ のような低い確率でしか当たりが出ない。ハズレた場合は「活用され続ける台」として選ばれず、また別の台へとチャンスが移ってしまう

つまり、「優秀なスロットマシンほど AI の思考停止のループに捕まりやすく、ハズレなスロットマシンほど AI にスルーされやすい」 という性質があるため、トータルで見ると、1 回あたりの稼ぎは全体の平均確率 $p_{mean}$ よりも必ず高くなります。

1 回あたりの稼ぎの平均の性質

この「平均より高くなる度合い」は、各スロットマシンの確率がどれくらい離れているか（ばらついているか）によって大きく変わります。

先ほどのスロットマシン確率が 0.3, 0.5, 0.7 という設定では、1 回あたりの活用で得られるコインの期待値である 0.54 は、平均の 0.50 よりほんの少し高いだけでした。それに対してスロットマシンの確率を 0, 0.5, 1.0 という、大きく偏った設定（下記のプログラムの mab2）に変えたらどうなるでしょうか？

全体の当たりの確率の平均は $\frac{0 + 0.5 + 1.0}{3} = 0.5$ で、先程と全く同じです。しかし、活用だけを 10 回連続で行った場合の下記のシミュレーションの実行結果は、0.54 から大幅に上昇した 0.77 になります。

なお、下記のプログラムは mab を、スロットマシンの当たりの確率を 0, 0.5, 1 に設定した mab2 に変えただけです。

mab2 = MAB(p = [0, 0.5, 1.0])

num = 100000
coins = []
bestarm_selectnum = [0] * 3
for _ in range(num):
    bestarm = None
    coin = 0
    for i in range(10):
        if bestarm is None:
            arm = np.random.choice(3)
        else:
            arm = bestarm
        if mab2.play(arm) > 0:
            coin += 1
            if bestarm is None:
                bestarm = arm
                bestarm_selectnum[arm] += 1
    coins.append(coin)
print(f"10 回の活用で得られたコインの平均　　　 {np.mean(coins):5.2f}")
print(f" 1 回あたりの活用で得られたコインの平均 {np.mean(coins) /10:5.2f}")
print(f"各スロットマシンが選択され続けた回数 {bestarm_selectnum}")

実行結果

10 回の活用で得られたコインの平均　　　  7.67
 1 回あたりの活用で得られたコインの平均  0.77
各スロットマシンが選択され続けた回数 [0, 33269, 66627]

このように結果が大きく上昇する理由は、確率 1.0（100 %）で当たるスロットマシンは、1 回目に選ばれたら絶対に当たりが出るため、高確率（上記のシミュレーションでは約 3 回に 2 回）で AI が選択し続けます。逆に確率 0（絶対に当たらない）の大外れのスロットマシンは、何度選ばれても永遠に当たりが出ないため、AI が選択し続ける確率は完全にゼロ（シミュレーションの選択回数 が 0）になるからです。このように、スロットマシンの実力のばらつきが激しい環境ほど、事前の探索をしなくても「活用一択のゴリ押し」がそこそこ通用してしまうという面白い特性があることがわかります。

「活用」に全振りした場合のまとめ

ここまでの考察とシミュレーションの結果から、事前の実験（探索）をさぼって、「活用」だけで突き進んだときの性質が以下のようになることがわかります。

• 基本のスコア： 1 回あたりに稼げるコインの平均は、全体の平均確率 $p_{mean} = 0.5$ よりも必ず高くなる
• ばらつきの影響： 各スロットマシン確率の「ばらつき」が小さいほど $p_{mean} = 0.5$ に近くなり、ばらつきが極端に大きいほどスコアは跳ね上がる

具体例の 0.3, 0.5, 0.7 のような現実的な設定であれば、稼ぎは 0.54 のように平均の 0.50 とそこまで大きく離れません。従って、0, 0.5, 1.0 のような極端な設定でない限りは、計算をシンプルにするために「活用だけを行うという作戦の 1 回あたりの稼ぎは、だいたい全体の平均（$p_{mean}$）と同じくらいとして扱っても良い」と考えても大きな問題はありません。

探索の回数と 1 回の活用の期待値の関係

ここまでの検証から、「事前にどれだけ実験（探索）をしたか」によって、その後の「活用」でどれだけコインを稼げるかが決まることがわかりました。この重要な関係を表で整理すると下記のようになります。

探索の回数	1 回の活用の期待値
小ない（データ不足）	全体の平均確率 $p_{mean}$ に近づく
そこそこ（中くらい）	平均 $p_{mean}$ と最大 $p_{max}$ の中間になる
多い（データが十分）	最大 $p_{max}$ に限りなく近づく

目的関数の性質

探索と活用でどれだけコインが稼げるかが検証できたので、いよいよ全体のスコア（目的関数 $f$）が「探索」と「活用」のバランスによってどのように変わるかについて検証することにします。

多腕バンディット問題では、スロットマシンのレバーを引ける合計回数（$m$）があらかじめ決められているため、探索の回数（$m_{探}$）と活用の回数（$m_{活}$）の合計は下記の式のように $m$ になります。

$$m = m_{探} + m_{活}$$

これはつまり、「探索を増やせば勝負（活用）の回数が減り、探索をサボれば勝負（活用）の回数が増える」という、限られたパイの奪い合い（トレードオフ） を意味しています。

そこで、探索の回数を 小、中、大と変化させたときに、トータルのスコアがどのように変化するかについてそれぞれ考察することにします。

探索の回数が小さい場合（活用に全振りする）

最初に、「できるだけ多くのコインを稼げるように、探索の回数を減らして活用をできる限り多く行う」という 積極的にコインを稼ぎに行く作戦 を考えてみることにします。

先程示したように、探索の稼ぎ $f_{探}$ は、探索の回数に関係なく下記の式で計算できます。

$$f_{探} = m_{探} × p_{mean}$$

また、先程の「まちぼうけの現象」で示したように、事前の探索の回数が小さすぎると活用のクオリティがが減少するため、1 回あたりの活用の期待値は $p_{mean}$ まで落ち込みます。つまり、活用の稼ぎ $f_{活}$ は次の近似式で表すことができます⁹。

$$f_{活} \approx m_{活} × p_{mean}$$

この 2 つの稼ぎを足し合わせて、全体のスコア（目的関数 $f$）を計算すると、下記のように $f$ の近似式を共通因数である $p_{mean}$ でくくった結果、$m_{探} + m_{活}$ を合計回数の $m$ にまとめることができます。

$$
\begin{aligned}
f & = f_{探} + f_{活} \\
& \approx m_{探} \times p_{mean} + m_{活} \times p_{mean} \\
& = (m_{探} + m_{活}) \times p_{mean} \\
& = m \times p_{mean}
\end{aligned}
$$

この式は、「せっかく勝負（活用）の回数（$m_{活}$）を増やしたのに、事前の実験をサボったせいで活用の精度がボロボロになり、結果的に 100 回すべてを完全ランダム（あてずっぽう）で引いたときと全く同じスコア $m \times p_{mean}$ まで落ち込んでしまう」ということを意味しています。

具体例の設定 $p_{mean} = 0.5$、$m = 100$ であれば、スコアは 100 × 0.5 = 50 枚になります。

探索の回数が大きい場合（探索に全振りする）

今度は逆に、「絶対にハズレ台に騙されたくないから、事前の探索を限界まで行う」という、石橋を叩いて渡るような慎重な作戦 を考えてみましょう。

探索を大きく増やせば、AI はそれぞれのスロットマシンの当たりの確率を正確に推測できるようになるため、一番当たりのスロットマシン（確率 0.7）をほぼ 100 % 完璧に見極められるようになります。そのため、1 回の活用の期待値は最大値 $p_{max} = 0.7$ とほぼ同じ値になります。全体のスコア（目的関数 $f$）の式に当てはめると、次のようになります。

$$
\begin{aligned}
f & = f_{探} + f_{活} \\
& \approx m_{探} \times p_{mean} + m_{活} \times p_{max} \\
\end{aligned}
$$

今回は、探索側が $p_{mean} = 0.5$ で、活用側が $p_{max} = 0.7$ となるため、掛ける数字が一致しません。そのため、先程のようにうまく $m$ の式にまとめることはできないように思えるかもしれません。しかし、ここで 「探索が極端に大きい（全振りに近い）」 という前提条件を使うと、合計回数のルール $m = m_{探} + m_{活}$ から、探索の回数（$m_{探}$）を限界まで増やせば増やすほど、下記の 2 つの近似式が成り立ちます。

• $m_{探} \approx m$：探索の回数 $m_{探}$ は、最大値である全体の回数 $m$ に限りなく近づく
• $m_{活} \approx 0$：その代わり、活用の回数 $m_{活}$ は、最小値である $0$ 向かって激減する

この探索にほぼ全振りした場合の近似式を全体のスコアの数式に当てはめると $f$ は下記の式で近似することができます。

$$
\begin{aligned}
f & = f_{探} + f_{活} \\
& \approx m_{探} \times p_{mean} + m_{活} \times p_{max} \\
& \approx m \times p_{mean} + 0 \times p_{max} \\
& = m \times p_{mean}
\end{aligned}
$$

今度は活用側の稼ぎが 0 を掛けられて消滅してしまいます、その結果、またしても 100 回すべてを完全ランダム（あてずっぽう）で引いたときと全く同じスコア $m \times p_{mean}$ まで落ち込んでしまいました。

この式は、「最高のスロットマシンを見分ける精度を完璧に高めた（$p_{max}$）のに、探索に時間を使い果たしたせいで、いざコインを稼ぎに行く本番の回数（$m_{活}$）が残っておらず、結局のところ完全なランダムと同じ 50 枚しか稼げなかった」という残念な結末を表します。

これこそが、まさに以前の記事で紹介した「原始モンテカルロ法が、真の勝率が低い負け筋の手に対しても平等にプレイアウトを割り当ててしまうという無駄を出して大損していた」原因の正体です。

参考までに、今回の具体例に対して原始モンテカルロ法を適用した場合のスコアが $m \times p_{mean}$ とほぼ同じなることを示します。

原始モンテカルロ法では、最後の 1 回を除いて探索を行い、最後に活用を行うため、$m_{探} = 99, m_{活} = 1$ になります。

従って、スコアは以下の式から 50.2 であることがわかります。これは $m \times p_{mean} = 100 \times 0.5 = 50$ とほぼ同じ値です。

$$
\begin{aligned}
f & = f_{探} + f_{活} \\
& \approx m_{探} \times p_{mean} + m_{活} \times p_{max} \\
& = 99 \times 0.5 + 1 \times 0.7 \\
& = 50.2
\end{aligned}
$$

99 回もの探索のおかげで、AIは「2 番のスロットマシンが確率 0.7 で最高だ」と完璧に見抜くことができます。しかし、見抜いたところで、それを活かせる活用が最後のたった 1 回しか残っていないため、スコアにはわずか 0.7 しか貢献できません。

探索と活用をバランスよく行う場合

ここまでは、探索か活用のどちらかに全振りをするとうまくいかないことを説明しました。それでは、探索と活用をバランスよく割り当てた場合の目的関数 $f$ はどのようになるでしょうか。

探索をそこそこ行っておけば、大数の法則がゆるやかに働いて誤差が減少するため、AI は騙されにくくなります。その結果、活用での 1 回あたりの稼ぎの期待値は、完全ランダム $p_{mean}$ よりも確実に高いが、最高の $p_{max}$ よりも低い中間（middle）の実力 $p_{mid}$ まで向上させることができます。 

このときの全体のスコア（目的関数 $f$）の数式は、次のようになります。

$$f = f_{探} + f_{活} \approx m_{探} × p_{mean} + m_{活} \times p_{mid}$$

この時に、活用の稼ぎがランダムな探索の稼ぎを上回っている（$p_{mid} \gt p_{mean}$）という性質を適用すると、目的関数が下記の不等式で表されることがわかります。

$$
\begin{aligned}
f & = f_{探} + f_{活} \\
& \approx m_{探} \times p_{mean} + m_{活} \times p_{mid} \\
& \gt m_{探} \times p_{mean} + m_{活} \times p_{mean} \\
& = (m_{探} + m_{活}) \times p_{mean} \\
& = m \times p_{mean}
\end{aligned}
$$

この不等式は「探索と活用をバランスよく行う事で、探索または活用に全振りをした場合（$m \times p_{mean}$）よりも多くのコインを稼ぐことができる」ということ表します。

今回の設定（$m \times p_{mean} = 50$ 枚）であれば、探索と活用をバランスよく割り当てることで、50 枚の壁を越えて最高得点である 70 枚に向かって近づけることがわかりました。

探索と活用のトレードオフのまとめ

下記はここまでの考察とシミュレーションを一つにまとめた表です

探索 回数	活用 回数	探索のスコア （$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 枚)）

この表を見れば、強化学習の世界を支配する「探索と活用のトレードオフ」という重要なルールが一目でわかります。

• 極端な作戦（全振り）は絶対に破綻する：探索が少なすぎても、多すぎても、合計スコアは最悪のベースラインである $m \times p_{mean}$ まで落ち込んでしまう
• 探索と活用のバランスが重要：探索と活用のバランスを上手に噛み合わせることで初めて、スコアを完全なランダムよりも大きな値へと引き上げることができる 

これはまさに、この記事の冒頭で説明した「多腕バンディット問題の目的関数は、探索と活用のバランスが完璧に噛み合っていないと高得点にならない指標である」ということを表しています。

探索と活用のトレードオフに関する補足

ここまでは、探索と活用をどれくらいの割合（回数）で割り当てるか」という話をしてきました。しかし、強化学習のトレードオフを完璧にコントロールするためには、もうひとつ絶対に無視できない重要なルールがあります。それが、「探索と活用を行う『順番』」です。

例えば、具体例で探索と活用を半々の 50 回 ずつ行うことにしたとします。この時に AI が「先に 50 回活用を行い、その後で探索を 50 回行う」という最悪のスケジュールを組んでしまうと、下記のように スコアがまたもや最低の $m \times p_{mean}$ まで落ち込んでしまいます。

• 最初の 50 回の活用は探索なしで行われるので「まちぼうけの現象」がおき、下記のように活用の精度は完全なランダムと同じまで落ちてしまう
  $$f_{活} \approx m_{活} \times p_{mean} = 50 \times p_{mean}$$
• 残りの 50 回はランダムな探索を行うので、稼ぎは下記のように平均確率のままになる
  $$f_{探} = m_{探} \times p_{mean} = 50 \times p_{mean}$$
• それらを足し合わせた目的関数は下記のよう平均確率そのものになる
  $$f = f_{探} + f_{活} = 100 \times p_{mean}$$

活用という仕組みは、事前にたっぷり実験（探索）をして「正確なデータ」を持っているからこそ初めて輝きます。探索を行う前に活用を行っても全く意味がない のです。

つまり、多腕バンディット問題を解くアルゴリズムには、「探索と活用のバランスを取りつつ、ゲームの進行（ステップ数）に合わせて上手に順番を割り当てるという賢さ」が求められます。

そのようなアルゴリズムについては、今後の記事で詳しく説明します。

専門書によく出る「リグレット（後悔）」という指標

今回の記事では、多腕バンディット問題のスコアを評価するために「コインをどれだけ多く稼げたか（目的関数の最大化）」という視点で解説を行いました。しかし、多腕バンディット問題の専門書や論文を開くと、これとは真逆の「リグレット（Regret ＝ 後悔）」という関数を目的関数として扱い、「リグレットを最小化する問題」として定式化されているのが一般的です。

リグレットとは、一言でいえば 「最初から正解を知っている神様と比べて、自分のアルゴリズムの得点がどれだけ損（稼ぎ損ね）をしてしまったか」の差 を表す指標です。

リグレット ＝ 目的関数の最大値（$f_{max}$） － 実際のアルゴリズムの期待値（$f$）

今回の記事の冒頭で、すべての確率をあらかじめ知っている状態で、一番当たりやすいスロットマシン（$p_{max}$）だけを $m$ 回引き続けた場合の最高得点（$f_{max} = m \times p_{max}$）を計算しました。これは現実のアルゴリズムには不可能な「神業」ですが、数学上の「基準値」として使うことができます。

自分が必死にプレイして出したゲームのスコア（$f$）と、この理論上の神業のスコアを見比べて、「最初に正解が分かっていればこれだけ貰えていたはずなのに、確率を調べる（探索する）ために他のスロットマシンを試したせいで、これだけコインを損してしまった・・・」と悔やむ引き算の数値が「リグレット（後悔）」の正体です。

このリグレットと稼いだコインはどちらかが大きくなると、もう片方が小さくなるという表裏一体の関係にあります。従って、専門書に書かれている 「リグレットを最小化する」という目標は、本記事で解説した「コインの期待値を最大にする」ことと、数学的にまったく同じ意味 になります。

最高得点である $f_{max}$ のスコアを常に達成するためには、絶対にあらかじめスロットマシンの確率をすべて知っておく必要があります。そのため、スロットマシンの確率を知らされていない場合に リグレットを 0 にするアルゴリズムは存在しません。

今回の記事のまとめ

今回の記事では、多腕バンディット問題における探索と活用のトレードオフについて詳しく説明し、探索と活用のバランスと順番をバランスよく割り当てることが、多腕バンディット問題の目的関数（コインの期待値）を最大化するために重要であることを説明しました。

次回の記事では、そのための具体的なアルゴリズムについて紹介します。

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

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

次回の記事

1. 状態空間、行動空間、状態遷移関数、報酬関数、初期状態、エピソードの終了条件のことです。詳細は以前の記事を参照して下さい ↩

2. $p_i$ の添字は何回目にレバーを引くか（ステップ数）ではなく、スロットマシンの番号を表します ↩

3. プログラムでのインデックスの番号にならって、スロットマシンの番号を 0, 1, 2 番のように 0 から数えることにします ↩

4. その数学的な根拠となるのが以前の記事で詳しく説明した大数の法則です ↩

5. 当たりの確率が最大となるスロットマシンが複数ある場合は、それらのスロットマシンを引く確率の合計が 1 となるように設定します ↩

6. 以前の記事で説明したように、もう一つの条件として、当たりの確率が高いスロットマシンをより多く選択するというものがあります。ただし、ここでは話を簡単にするために、それぞれのスロットマシンをバランスよく選択することだけに注目して説明することにします ↩

7. 0 で割り算を行うと ZeroDivisionError というエラーが発生します。一方、np.mean で空の list の平均を計算しようとすると、nan（not a number の略）という数値として表せないことを表す特殊な値が計算されます。 ↩

8. この例では 1 回目で当たりがでたことになっていますが、1 回目で当たりが出なかった場合は当たりが出るまでランダムにスロットマシンを選択し、その後で当たりが出た 1 つのスロットマシンだけを選択し続けます ↩

9. $\approx$ は近似値を表す記号です ↩