問題設定
期待値\(\small \mu_1,\cdots,\mu_n\)を持つ選択肢の中から、任意の選択肢を一つ選ぶ賭けを一定回数\(\small T\)回だけ繰り返して得られる収益を最大化する方法を考える。ただし、一般的な問題と異なり、ギャンブラーは事前にそれぞれの選択肢の本当の期待値\(\small \mu_1,\cdots,\mu_n\)を知らないものと仮定する。そのため、期待値を推定するには一定回数試行して得られる情報を用いなければならないものとする。事前に確率分布が分かっている意思決定問題と異なり、確率分布が事前にわからない意思決定問題は不完全情報問題と言われる。この問題は情報探索の機会（Exploration）と得られた情報を活用して収益を得る機会（Exploitation）のトレードオフを扱う最適化問題の一種であり、多腕バンディット問題という。
多腕バンディット問題の例としてよく挙げられるギャンブルはスロットマシーン（日本ではパチンコ。ちなみにパチンコはほぼ日本独自の文化で海外では禁止されているか、ほとんど流行っていないらしい。）である。どの台のマシーンが期待値が高めに設定されているかを探索し、発見した期待値が高い台のマシーンを継続して打つことでより多くの収益を得ようとする意思決定ということになる。現実には、不完全情報ゲームの多くは多腕バンディット問題として定式化することができるし、テキサスホールデムもスロットマシーンでレイズ、コール、フォールドというどのアームを引くのが期待値が最大かということを探索し、そこで得られた情報を元にエクスプロイトするという点では等価な数理問題ということになるかもしれない。
筆者は詳しく知らないが、日本のパチンコも真面目に期待値を推定しようとすると数学的にはそこそこ難しい問題であるようである。当選確率や平均的な出玉の数だけで良ければ容易かもしれないが、確率が変動するイベントがいくつかある（確率過程としてモデリングする必要がある）ようであり、これを考慮して期待値を計算しないといけないらしい。それら様々な事象の観測値からその台の期待値がいくらかをベイズ推定する必要があるということだろう。このように考えるとテキサスホールデムの面白さはパチンコ（スロットマシーン）の面白さに類似しているのかもしれない。まあ、”パチンコは知的な数理ゲーム！”とか言われたら、笑ってしまいそうであるけど・・・もしかしたら、”テキサスホールデムは知的なマインドスポーツ！”も同じノリなのかな？まあ、テキサスホールデムにおける応用はそのうち考えるとして、多腕バンディット問題について難しい証明や計算を抜きにして概要をまとめておこうというのが本稿の趣旨である。
不完全情報下における確率的最適化問題と期待リグレット最小化
期待値\(\small \mu_1,\cdots,\mu_n\)を持つ\(\small n\)個のスロットマシーンについて、最初から各台の期待値が分かっていると仮定する。このとき、最適化問題は完全情報問題（Complete Information Problem）であり、最適な行動は最も期待値が大きい台を\(\small T\)回打つことになる。\(\small u_i(t)\)を\(\small i\)の台で観測される収益とすれば、この時得られる期待収益は
\[ \small P_\sigma(T) = E\left[\sum_{t=1}^T u_{\sigma(t)}(t)\right]=\mu^{\ast} T, \quad \mu^\ast=\max\{\mu_1,\cdots,\mu_n\} \]
で与えられる。これは
\[ \small \max_{\sigma} E\left[\sum_{t=1}^T u_{\sigma(t)}(t)\right] \]
となるように最適な方策\(\small \sigma\)を定めた結果と見ることができる。期待値の計算がたとえ複雑であっても、モデルを構築してモンテカルロシミュレーションを行えば、この期待値を計算することは一般的に可能だろう。
現実には、各台の期待値は不明であるため、何らかの方策（Policy）\(\small \pi\)に従って台を選んだ場合の収益を
\[ \small \hat{Q}_{\pi}(T) = \sum_{t=1}^T u_{\pi(t)} \]
と表すことにする。\(\small \hat{Q}(T)\)は不完全情報問題の解として得られる収益ということになるだろう。多腕バンディット問題のような不完全情報下における確率的最適化問題においても、単純に
\[ \small \max_{\pi} Q_{\pi}(T) = E[\hat{Q}_{\pi}(T)]= \sum_{t=1}^T \mu_{\pi(t)} \]
となるように最適な方策\(\small \pi\)を定めれば良いと考えるかもしれない。
しかし、完全情報問題と異なり、不完全情報では各台の期待値が不明であるから、事前に各台の収益をシミュレーションして\(\small Q_{\pi}(T)\)を推定するということができない。各台の期待収益は実際に台を打ってみるまで分からないということであり、事前にモンテカルロシミュレーションを行って最適な方策を定めることができないことになる。そのため、事後的に得られる情報に基づいて最適な方策を決定する必要がある。各台の\(\small t\)回目に観測される収益（事後的な観測値）を\(\small u_1(t),\cdots,u_n(t)\)と表し、事後的な平均収益を
\[ \small \hat{\mu}_i = \frac{1}{T}\sum_{t=1}^T u_i(t) \]
と表したときに、事後的な情報を元に完全情報問題として最適な方策を決定すれば、事後的な平均収益が最も大きい台を\(\small T\)回打つことが最適解になるのであるから
\[ \small \hat{P}_\sigma(T) = \sum_{t=1}^T u_{\sigma(t)}(t)=\hat{\mu}^{\ast} T, \quad \mu^\ast=\max\{\hat{\mu}_1,\cdots,\hat{\mu}_n\} \]
となる。この事後的な情報を元にした完全情報問題の最適方策から得られる収益\(\small \hat{P}_{\sigma}(T)\)と方策\(\small \pi\)に従ってゲームをプレイした場合の不完全情報問題における収益\(\small \hat{Q}_{\pi}(T)\)の差
\[ \small R(T) =\hat{P}_\sigma(T)-\hat{Q}_{\pi}(T) \]
を後悔、あるいは、リグレット（Regret）という。不完全情報問題ではこのリグレットの期待値
\[ \small E[R(T)] =\hat{\mu}^{\ast} T -\sum_{t=1}^T \hat{\mu}_{\pi(t)} \]
を最小化するように最適な方策\(\small \pi^\ast\)を決定する必要がある。
リグレットの定義式から、完全情報問題では最適方策\(\small \sigma^\ast\)に従ってゲームをプレイした場合、期待レグレットは0になることは容易に理解できるだろう。不完全情報問題では一般的に\(\small E[R(T)]>0\)であり、この値の大きさが情報が不完全であることのコストに相当するということになる。最適な方策はこの情報を得るための探索コストと得られた情報を元に収益を獲得する行動のトレードオフを最適な割合で配分したものということになるだろう。ちなみに、機械学習や人工知能の問題で強化学習（Reinforcement Learning）と言われる数理問題と一般的な確率的な動学的最適化問題の違いは、情報が不完全であるか完全であるかであり、強化学習が対象にしている数理問題は不完全情報下における確率的な動学的最適化問題であることに注意しておく。
解法アルゴリズムの例
多腕バンディット問題についてよく知られている代表的な解法アルゴリズムを紹介する。ε-greedy法、UCB法、確率一致法という3つの方法について簡単に説明する。
1. ε-greedy法
ε-greedy法は、試行可能回数\(\small T\)のうち一定の比率\(\small 0 < \epsilon < 1\)（\(\small \epsilon T\)回分）について、それぞれの台の期待値を推定するための探索に割り当て、残りの\(\small (1-\epsilon)T\)回について、推定した期待値のうち最も期待値が台を試行するのに割り当てる解法である。台の期待値を推定するための探索行動にはバリエーションがあるが、通常はすべての選択肢を均等に引いて
\[ \small \hat{\mu_i} = \frac{n}{\epsilon T}\sum_{t=(i-1)\epsilon T/n}^{i\epsilon T/n} u_i(t) \]
と推定すればよいだろう。\(\small \epsilon\)はハイパーパラメータであり、適当な値を外生的に与える必要がある。
2. UCB法
ε-greedy法は、観測される平均値にかかわらずすべての台を均等に探索するため、探索のコスト（損失）が大きくなってしまう可能性がある。そのため、観測される収益が低い台の探索を少なめにし、収益が高い台を多めに探索することで探索のコストを抑えられるかもしれない。一方で、試行回数が少なくなるとその台の期待値の推定精度が悪くなるというデメリットがある。このバランスをうまくとる方法として、それぞれの台の期待値を
\[ \small \hat{\mu}_i(\tau) =\frac{1}{N_i(\tau)}\sum_{t=1}^{\tau} 1_{\{\pi(t)=i\}}u_{\pi(t)}(t)+\sqrt{\frac{\log \tau}{2N_i(\tau)}} \]
と推定し、\(\small t\)回目において、最も\(\small \hat{\mu}_i(t)\)が高い選択肢を選ぶ。ここで、\(\small N_i(\tau)\)は\(\small \tau\)回目までに選択肢\(\small i\)が選ばれた回数を表す。これにより、観測される収益が低い場合でも、選ばれた回数が少ない選択肢が選ばれる機会を増やすことができる。計算式自体は収益がベルヌーイ分布に従う場合という前提から計算されているようである。
3. 確率一致法
ゲーム理論の混合戦略のように、選択肢\(\small i\)を選ぶ確率分布を多項ロジットモデル
\[ \small p_i = \frac{e^{f(\hat{\mu}_i)}}{\sum_{i=1}^n e^{f(\hat{\mu}_i)}} \]
から計算して、その確率分布に従ってランダムに選択肢を選ぶという方法である。どの選択肢を選ぶべきかの重みであるスコア\(\small s=f(\hat{\mu}_i)\)は各選択肢の収益の確率分布の事前予測（事前分布）から定める必要がある。これはベイズ推定（事前分布についてギャンブラーの信念に基づいて定め、観測値からパラメータを更新する）を用いて推定することになる。
最も洗練された方法は確率一致法であろうが、人間の頭で考えて実行するには難しい部分もあるように感じる。現実にはε-greedy法が経験的に扱いやすい方法であるが、\(\small \epsilon\)をどのように設定するかで期待リグレットが大きく変わるため、問題に応じて適切な\(\small \epsilon\)を設定するための経験や勘のようなものが必要になるのかもしれない。
おまけ：パチンコ玉はなぜ同じ軌道で運動しないのか
筆者はパチンコをやったことがないし、仕組みも詳しく知らないのであるが、不思議に感じるのは同じようにパチンコ玉を打っているのになぜ全く異なるランダムな軌道を描くのかということである。古典力学的に考えれば、同じ質量の物質に同じ強さの力を加えれば、たとえ釘がたくさんあるパチンコ台でも同じ軌道で運動するのではないかという気がしてくる。これは初期条件にランダムな要素があるようであり、それをパチンコ台の釘が増幅させることでカオスのようなランダムな運動になっているらしい。初期条件として以下のような要因がランダムであるようである。
- パチンコ玉を打ち出す仕掛けがばね仕掛けであり、レバーを完全に固定しても力の加わる方向や玉の回転に不確定性がある（ランダムな振動や回転が加えられているのかもしれない。）。
- パチンコ玉はすべて同じ質量で作られているように見えて、微妙な個体差を意図的に入れているらしく、これが原因で同じ力を加えても同じ軌道に運動しないようになっている。
- 複数のパチンコ玉が同時にパチンコ台にあるため、複数の玉がぶつかり合ってランダムな要素を生み出している。
これらの要因でパチンコのレバーの打ち方で勝率を上げるということは基本的にできないようになっているようである。
同じように海外のスロットマシーンも回転するリールを3つ止めるが、これはタイミングを計ることで当たりを出やすくできるかという問題も気になるかもしれない。残念ながら、これもやはり不可能であるようである。実をいうと、スロットマシーンはレバーを引いた時点で機械やデジタル制御で乱数の決定が行われており、プレイヤーがリールを止めるタイミングの時点で既に当たりか外れかが決まっているということであった。リールを止める操作はあたかもプレイヤーが自分で決定しているかのように見せる演出であり、当たりが出た時にプレイヤーに高揚感を与える効果があるようである。実はどのタイミングで止めるかはまったく意味を持っていないようなので、効率的にプレイしたい場合はさっさと止めろよということらしい。
プレイヤーのスキルによって、ギャンブルの結果に影響を及ぼす操作のことを技術介入（skill-based play）というらしい。パチンコもスロットマシーンも基本的には技術介入が不可能であり、打つ台を選択する多腕バンディット問題として扱う以外の要因はほとんどないようである（日本のパチスロには、正しい手順でボタンを押したり、タイミングを合わせることで若干確率に影響を及ぼすことができる機種もあるようである。）。ポーカーは対人戦であるため、もちろん技術介入があるギャンブルということになるが、それがどの程度なのかは筆者にはよくわからない。頭脳戦のように見えて、ただの運ゲーとしての要素がほとんどである可能性も無きにしも非ずなのかもしれない。例えば、すべてのプレイヤーが合理的な戦略（ナッシュ均衡戦略）を採用している場合は運以外の要素で勝敗の説明を付けることができなくなる。そういった状況は現実にはあり得ないにしても、プレイヤーのスキルレベルが近い場合は運ゲー化してしまうのだろう。
