logo logo

June 13, 2019 08:16

C#による多腕バンディット問題シミュレーション

多腕バンディット問題(Mult-armed bandit problem)とは?

  • 多腕バンディット問題とは、強化学習に入門する際に頻繁に目にする古典的な例題の一つで、例えばSuttonの強化学習でも冒頭で扱われるような問題
  • 多腕バンディットの前に強化学習のwikipediaの要約

強化学習(きょうかがくしゅう、英: Reinforcement learning)とは、ある環境内におけるエージェントが、現在の状態を観測し、取るべき行動を決定する問題を扱う機械学習の一種。エージェントは行動を選択することで環境から報酬を得る。強化学習は一連の行動を通じて報酬が最も多く得られるような方策(policy)を学習する。代表的な手法としてTD学習やQ学習が知られている。

  • わかりやすく翻訳:あなたがゲームしているような時、あなたはゲーム画面の状態を見て、次に何ボタン押すか(=行動)決めてますよね?それでボタンを押した結果次の状態に移って、敵を倒したり、コインもらえたり、スコアアップしたり(=報酬)、逆にやっつけられたり、逆戻りしたりする(=負の報酬)。強化学習はゲームをプレーする中で、どうやったらこの報酬を最大化できるかというボタン押し戦略(=方策)を学習していくアルゴリズムのことです
  • 多腕バンディット問題:腕を引くと一定の確率で、(その確率は外からは見えないけど)報酬をくれるスロットマシンが$n$個並んでいるとします。あなたが腕を引ける回数は決められているとして、その報酬を最大化するような方策はどのようなものでしょうか?
  • 例えば一番最初に適当に座ったスロットを引き続けるのは愚策かもしれませんが、一番確率の高いスロットにたまたま座った場合、報酬は最大化されることもありえます。その逆に一番悪いスロットに座れば残念。ただ方策の優秀さはあくまで何回もこの競技を行なって、その平均で比べることにしましょう。
  • 最初は適当な回数、全部のスロットに座っておいて、その時点で一番よかった台に座り続けるのはどうでしょうか?何はともあれ、このゲームで勝つには、台を複数試す探索と、探索の結果得た台毎の統計的情報を利用して、その台に座り続けるのが良さそうです。探索が不十分ならその時点の情報利用時に失敗の可能性が高まりますし、探索しすぎると、早い段階で良い台を見つけたプレーヤーに水をあけられてしまいます。ギャンブルと思うなかれ、まさに人生の縮図が詰まった解くべき問題のような気がしてきませんか?

より具体的な問題設定

  • プレーヤーは10台のスロットから毎度1台を選んでスロットをまわす。1セットの試行では1000回これを行う
  • 2000セットの試行回数の平均で方策の比較を行うことにする
  • 各スロットの報酬設定値は、各試行の開始毎に以下のルールでリフレッシュされる
    • 平均0,分散1で決まるガウス分布から生成される
    • プレーヤーはこのようにして決定した各試行毎のスロットの設定値を直接知ることはできない
  • 1回ごとのスロット報酬は設定値を平均値とし、分散1のガウス分布に従う

ε-greedyアルゴリズム

まずは最もシンプルで基本的な$\epsilon$-greedyという方策をシミュレーションし、比較する。
この方策では各回毎に、プレーヤーは$\epsilon$の確率で完全ランダムにスロットをまわし、$1-\epsilon$の確率でその時点で最も期待値の良かったスロットを回す。この$\epsilon$の値を変えながら、平均報酬(各ステップにおける2000回の平均)の比較を行ってみる

C#でのシミュレーションコード

using System;
using System.Collections.Generic;
using System.Linq;

namespace nBandit
{
    class Program
    {
        //Box-Muller法により、ガウシアンに従うランダム値を返す
        public class GaussianDist
        {
            private double mu;
            private double sigma;
            private Random r;

            public GaussianDist(double Mu, double Sigma, int Seed)
            {
                this.mu = Mu;
                this.sigma = Sigma;
                this.r = new Random(Seed);
            }
            public double GaussianRandom()
            {
                double x = r.NextDouble();
                double y = r.NextDouble();
                double result = sigma * Math.Sqrt(-2.0 * Math.Log(x)) * Math.Cos(2.0 * Math.PI * y) + mu;

                return result;
            }
        }

        static void Main(string[] args)
        {
            int n = 10; //n-bandit
            double epsilon = 0.01;
            int tryNumber = 2000; //試行回数
            int maxStepNum = 1000; //各試行における最大ステップ数
            double initEstimation = 0.0;
            var Q = new List<double>();
            double mu = 0.0;
            double sigma = 1.0;
            var q_star = new List<double>();
            var gaussian = new GaussianDist(mu, sigma, 543);
            var whiteNoise = new GaussianDist(mu, sigma, 653);
            double reward = 0.0;
            var RewardSum = new List<double>();
            var eachArmChosenNum = new List<int>();


            //totalRewardを初期化
            for (int i = 0; i < maxStepNum; i++)
            {
                RewardSum.Add(0.0);
            }

            var randomForEach = new Random();
            var randomForEpsilon = new Random(478);
            //tryNumまでの各試行のループルーチン
            for (int i = 0; i < tryNumber; i++)
            {
                for (int k = 0; k < n; k++)
                {
                    q_star.Add(gaussian.GaussianRandom());
                    Q.Add(initEstimation);
                    eachArmChosenNum.Add(0);
                }

                for (int j = 0; j < maxStepNum; j++)
                {
                    //行動決定ルーチン+行動実行ルーチン
                    var random = randomForEach.NextDouble();
                    var maxQ = Q.Max();
                    var maxIndex = Q.IndexOf(maxQ);
                    if (random <= epsilon) {
                        int randomIndex = randomForEpsilon.Next(10);
                        reward = q_star[randomIndex] + whiteNoise.GaussianRandom();
                        eachArmChosenNum[randomIndex] = eachArmChosenNum[randomIndex] + 1;
                        Q[randomIndex] = Q[randomIndex] + (reward - Q[randomIndex]) / (double)(eachArmChosenNum[randomIndex]);
                    } else {
                        reward = q_star[maxIndex] + whiteNoise.GaussianRandom();
                        eachArmChosenNum[maxIndex] = eachArmChosenNum[maxIndex] + 1;
                        Q[maxIndex] = Q[maxIndex] + (reward - Q[maxIndex]) / (double)(eachArmChosenNum[maxIndex]);
                    }
                    //合計報酬の計算
                    RewardSum[j] += reward;
                }
                q_star.Clear();
                Q.Clear();
                eachArmChosenNum.Clear();
            }

            for (int k = 0; k < maxStepNum; k++)
            {
                Console.WriteLine("{0}\t{1}", k+1, RewardSum[k] / (double)tryNumber);
            }
        }
    }
}

シミュレーション結果

以下が3パターンでのシミュレーション結果です。
まったくランダム探索をしない$\epsilon = 0$の場合よりも、適度な探索を行った場合のほうが成績が良いことがわかります。本来はもっと大きい値で比較もしてみて、トレードオフの様子を探ってみたいところですが、Suttonの教科書を検証することが目的だったのでよしとします。

ところでこの$\epsilon$は各プレーヤーの好奇心の程度の差と言えます。自分個人の経験や見分だけからベストな選択を行うことは、実は機会損失に繋がってしまう場合があります。ちょっと阿保っぽく見えても未知のものをランダムにでも試してみるぐらいの人のほうが成功しやすそうだと、少なくともこのゲームの中では結論づけられるわけです。また完全に探索ばかりしていると、やはり上手くいかないという微妙なトレードオフも人生の選択を難しくしている要因と言えます。(このゲーム設定の場合、完全ランダムな酔っ払い方策の期待値は0になります。)単純なルールでそんな示唆をあたえてくれる本実験が好きなのでみなさんにも共有してみました。

参考