> おもちゃ箱 > 多腕バンディト問題
|
多腕バンディト問題 とは ここでは確率的多腕バンディト問題を扱う。複数のアームを持つスロットマシンがある。一回のゲームごとにアームを選んで引く。当たればコインが一個出る、外れればコインが出ない。各アームの当たりが出る確率はそれぞれに定まっているが、ゲームをする人には分からないとする。さて、決められたゲーム回数でできるだけ多くのコインを獲得するには、どのアームを引く回数をどのようにしたらよいか、という問題である。 戦略 について 種々の戦略が考案されているが、いずれにしても、「探索」と「活用」をどのようなバランスで行うかということである。 探索とは、情報収集（どのアームが最も当たる確率が大きいかさぐりを入れる）を行うために、適当にアームを選んで何回かゲームを行うことである。 活用とは、探索での結果に基づき、最も当たる確率が大きいアームでゲームを行うことである。 戦略としてよく知られているものは ε-greedy である。 戦略１ ε-greedy まず、確率 ε(0〜1) を定めておく。そしてゲームごとに 0〜1 のランダム数値を出し、それが ε 以下の値なら探索を、そうでないなら活用を行う。ε は 0.1 とした場合が最もよい結果が得られることが知られているが、値をいろいろ変えて実験をしてみると楽しめる。 さらにこれを工夫改良をすれば、手間暇の割に合う合わないは別として、いくらでも戦略は考えられるであろう。 戦略２ UCB1 (Upper Confidence Bound 1) 探索として、各アームで１回ずつゲームを行う。残りのゲームについては活用とし、アームの価値の最もよいものを選択する。各アームの価値はゲーム終了ごとに次式で与える。 アームの価値=成功率＋バイアス ここで 成功率=(このアームの獲得コイン数)÷(このアームでのゲーム回数) バイアス=(2×log(全アームでのゲーム回数)÷(このアームでのゲーム回数)) の 1/2 乗根 である。選択数が少ないアームほどバイアス項は大きく、成功率は小さくても選択回数が少ないアームも選ばれることがあるようにしてある。 ところで私のような素人には、本当にこのような戦略が役に立っているのだろうかといういう疑問が生じるのである。そこで、探索も活用もせずに、ゲームごとに全くランダムにアームを選択して行うこともできるようにした。 戦略３ ランダム これはもはや戦略とは言えないものであり、また実行結果も予想通りのつまらないものである。 また素人の私がカジノに行ったら、おそらくこうするであろうという戦略も試してみよう。 戦略４ 素人戦略 一般に標本調査を行う場合、標本の数を幾つにすればよいのかについての理論は既に統計学で確立されているはずである。だから、理論的に計算した標本の回数だけ前もって探索を行い、残りのゲームは、探索の結果最も良い成果を上げたアームのみでゲームを行う。ゲーム回数の内、何回を探索にするかの率を 探索率(0〜1) とする。本来この探索率をいくらにしたらよいかを統計理論を用いないで決めないと意味がないと思う。戦略１の ε-greedy でも ε 値は自分で決めておかなくてはならない。それに対して、戦略２の UCB1 は改善されており、実際に使える戦略であるように思う（カジノで実際に使えるかは？）。 まあ戦略４も、お遊びとしていろいろ変えて実験してみると楽しめ、意外とよい結果が得られたりする。 ∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞ |