これまで３回に渡って解説してきた「報酬が平均・分散が未知の正規分布に従うと仮定したThompson Sampling」ですが，ついに第４回目最終回です．

今回は，前回紹介した報酬が平均・分散が未知の正規分に従うと仮定したThompson Sampling（以降，簡単のためにTS-Gaussian-Sicqと呼ぶことにします）のアルゴリズムの性能を実験的に評価してみたいと思います．

TL;DR

• 平均・分散がどちらも未知の正規分布に従うと仮定したThompson Samplingと，平均のみ未知であると仮定したThompson Samplingを実験的に比較
  • ２つの腕の多腕バンディット問題で実験
• 平均のみ未知であると仮定したThompson Samplingは，最適でない腕を最後まで選択し続けることがあった
  • 仮定していた分散よりも実際の報酬の分散が大きい場合，推定に失敗する可能性がある
• 一方で，平均・分散がどちらも未知であると仮定したThompson Samplingは，推定に失敗することはなかった
  • しかし，その分報酬に関する情報が充分に得られるまでは不確実に腕を選択することになる
• 結局は，対象としている問題の設定によってバンディットアルゴリズムを決定するのが理想

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

腕$1$と腕$2$の２つの腕が存在していると設定します．

２つの腕からの報酬はどちらも正規分布に従うとします． ここで，腕$1$からの報酬は$N(\mu_1, \sigma^2_1)$に，腕$2$からの報酬は$N(\mu_2, \sigma^2_2)$に従うとします．

後の議論を簡単にするために，常に腕$1$が最適な腕，すなわち$\mu_1 > \mu_2$であるとします．

性能の評価方法

TS-Gaussian-Sicqのアルゴリズムの性能は，上記の設定の多腕バンディット問題において，腕選択を$20,000$回繰り返し，リグレット$R(T)$

$$R(T)=\sum_{t=1}^T(\mu^{\ast}-\mu_{ i_{max} })=(\mu_1-\mu_2)\cdot k_2(T+1)$$

を計測することによって評価します．

ただし，TS-Gaussian-Sicqのリグレットのみを見ても性能の善し悪しが分かりにくいため，Agrawalらが提案したアルゴリズムThompson Sampling using Gaussian priors（以降，簡単のためTS-Gaussianと呼びます）との比較を行います．

TS-Gaussianは，報酬が平均が未知，分散が$1$の正規分布に従うと仮定したThompson Samplingです． 分散を既知として扱っているかどうかが，TS-Gaussian-SicqとTS-Gaussianの違いになります．

２つのアルゴリズムの性能の詳細な比較を行うために，以下では，２つのパターンの実験を行います．

実験その①

実験設定

腕$1$の報酬分布のパラメータを$\mu_1=1.0,\sigma^2_1=3.0^2$，腕$2$の報酬分布のパラメータを$\mu_2=0.0,\sigma^2_2=0.3^2$と設定します．

腕$1$の期待値$\mu_1$は腕$2$の期待値$\mu_2$よりもだいぶ大きい値のため，比較的簡単にどちらの腕が最適かを判別することができそうです． その一方で，腕$1$の分散が大きい値なので，腕$1$の期待値を精度良く推定するのにはいくらかのサンプル数を要しそうです．

結果

TS-Gaussian-SicqとTS-Gaussianに対して，腕を$20,000$回選択させる実験をそれぞれ$100$回ずつ行いました．

以下の図は，TS-Gaussian-SicqとTS-Gaussianのリグレット$R(T)$の$100$試行平均の推移です．

TS-Gaussianはリグレットが発散気味になっているのに対し，TS-Gaussian-Sicqはリグレットがほぼ変化しなくなることが分かります． 腕の選択回数が$10^2$を超えたあたりから差が顕著になっていることも分かります．

実験その②

実験設定

腕$1$の報酬分布のパラメータを$\mu_1=1.0,\sigma^2_1=3.0^2$，腕$2$の報酬分布のパラメータを$\mu_2=0.9,\sigma^2_2=0.3^2$と設定します．

腕$2$の期待値$\mu_2$以外は実験その①と一緒の設定です． 腕$2$の期待値が腕$1$の期待値に近い値になった分，どちらが最適かを判別するのがより困難になることが予想されます．

結果

実験その①と同様に$100$試行行いました．

以下の図は，TS-Gaussian-SicqとTS-Gaussianのリグレット$R(T)$の$100$試行平均の推移です．

実験その①と比べて，リグレットのスケールが$10$倍程度になっていますね． $\mu_1-\mu_2$は実験その②の方が小さいのですが，それでもリグレットが大きくなるということは，それだけ最適な腕を判別するのに時間がかかった，ということでしょう．

しかし，こちらの実験の場合もTS-Gaussian-Sicqの方が低いリグレットの推移になりました．

考察

どちらの実験でもTS-Gaussian-Sicqの方がTS-Gaussianより低いリグレットの推移となりましたが，なぜこのような結果が得られたのか，ということについて，少し考察をしてみます．

TS-Gaussianにおける期待値の推定値の推移

以下の図は，実験その②においてTS-Gaussianが推定した各腕の期待値の推定値の推移（すなわち，乱数$\theta$の推移）の一例です．

また，以下の図は，その試行におけるリグレットの推移です．

腕$1$の期待値$\mu_1$は$\mu_1=1.0$であるはずなので，期待値の推定精度が高い場合，１つ目の図の青線は$1.0$付近を推移するはずです． しかし，この試行では青線は$1.0$より低い値で推移しており，その結果腕$1$が腕$2$より期待値が低いと推定されてしまっています． よって，腕$2$が最適な腕として推定されてしまっているので，腕$2$を選択することを繰り返してしまい，その分リグレットも増加してしまっています．

このようないわゆる失敗試行は，当然毎回のように起こるわけではなく，$9$割くらいの試行では腕$1$が最適な腕であると推定されてリグレットが後半にも増加するようなことはありません．

しかし，このような失敗試行が少なからず存在するために，$100$試行平均のリグレットがTS-Gaussian-Sicqより大幅に高い値を推移する結果となったと考えられます．

TS-Gaussian-Sicqにおける期待値の推定値の推移

一方で，TS-Gaussian-Sicqではこのような失敗試行は存在しませんでした．

実験その①において，TS-Gaussian-Sicqが推定した各腕の期待値の推定値とリグレットの推移は，おおむね以下の図のようになっていました．

腕$1$と腕$2$の期待値$\mu_1,\mu_2$を精度良く推定できるようになっていることが分かります． これによって，どの試行でも腕$1$が最適であると推定することができているので，結果としてリグレットも低い値で推移できています．

参考までに，この試行においてTS-Gaussian-Sicqが推定した各腕の分散の推定値の推移（すなわち，乱数$\phi$の推移）も貼っておきます．

なぜTS-Gaussianは最適な腕の推定に失敗するのか

ではなぜ，TS-Gaussianは「腕$2$が最適な腕である」と推定し続けてしまうことがあるのでしょうか？

それは，TS-Gaussian-Sicqが報酬の分散まで推定しているのに対し，TS-Gaussianは報酬の分散は$1$で固定であると決め打ちしていることが原因であると予想されます．

今回の実験では，実験その①でもその②でも腕$1$の報酬の分散が$3.0^2$と，TS-Gaussianが想定している報酬の分散の値$1$よりかなり大きめの値に設定されています．

これはつまり，分散が実際の値よりも小さいとみなして期待値の推定を行うということです．

今回の実験設定の場合，腕$1$の報酬の分散は$3.0^2$ですので，運が悪いと初めて腕$1$を選択したときにかなり低めの報酬がでてしまうこともあります．

しかし，TS-Gaussianは報酬の分散は$1.0$でそこまで高くないはずとみなしているため，初めて腕$1$を選択したときにかなり低めの報酬が出たとしても，それが分散によって発生するゆらぎによるものだと予測するのが困難です．

この結果として，初めて腕$1$を選択したときに低めの報酬が出てしまうと，「腕$1$は期待値が低い」とみなしてしまうことがあります．

一度腕$1$の期待値が低いとみなされてしまうと，腕$1$の期待値が低いとみなされる→腕$2$ばかり選択する→腕$1$の報酬に関する情報が得られない→腕$1$の期待値の推定は変わらないので相変わらず低いとみなされるといった負のループが回ってしまうため，終盤になっても腕$2$ばかり選択される，といったことにつながってしまいます．

実際，上の図のような失敗試行ではこのようなことが起こっています．

なぜTS-Gaussian-Sicqは最適な腕の推定に失敗しにくいのか

一方で，TS-Gaussian-Sicqは分散も未知であることを前提としているため，例え初めて腕$1$を選択したときに運悪くかなり低めの報酬が出たとしても，「分散が高いかもしれない」という可能性を残しつつ推定を行います．

言い換えると，TS-Gaussian-Sicqは，報酬に関する情報が充分に得られるまでは，期待値の推定をあえて不確実性を混ぜて行うという特徴を持っています．

この特徴によって，TS-Gaussian-Sicqは実験設定，特に腕の分散の設定に対して比較的柔軟になっていると言えるでしょう．

しかし，逆にこのような性質を持っている分，TS-Gaussianに比べて最適な腕を判別するまでに時間を要することがあります． 実際，腕の分散が$1.0$ちょうどの場合など，実験設定によってはTS-Gaussianの方がリグレットが低い値で推移することもあります．

まとめ

考察したように，バンディットアルゴリズムでも前提としている条件や問題設定が異なります． したがって，問題設定によってバンディットアルゴリズムを適切に選択することが重要です．

自分が対象としている問題がどのような問題設定なのか，ちゃんと整理ができた上でアルゴリズムを決定できると理想ですね．

コード

今回実験に使用したコードはGitHubに公開しています．