Thompson Samplingの実験的な評価

Thompson Samplingの実戦投入の参考になりそうなので次の論文を精読した。

An Empirical Evaluation of Thompson Sampling
http://papers.nips.cc/paper/4321-an-empirical-evaluation-of-thompson-sampling

内容はアルゴリズムの紹介、パラメータチューニングとそれによる損失の変化の実験結果、オンライン広告とリコメンドエンジンへの適用例など。以降、Thompson SamplingはTSと表記。

UCBとの比較

実験ではどのパターンも、途中まではUCBと同じ損失だが試行回数がある程度増えた所でTSの損失がUCBを下回っている。腕の数が多い程、報酬の差が小さい程UCBとパフォーマンスが分かれる点は後ろにずれる。
理由は書いてないが、UCBは一旦報酬が低い事がわかった腕も定期的に引くのでこういう結果になるのだろう。TSは報酬の期待値が収束した後は良い物しか引かない。

事後確率の調節

ベータ分布のパラメータaとbについてそれぞれα∈(2, 1, 0.5, 0.25) で割った値にした実験。0.25にすると傾向として損失は下がるが、損失が増える駄目なケースも増える。腕の性能評価を早めるので、誤って評価してしまうのだろう。バリアンスが高くなるので玄人向けのチューニングに見える。

報酬のフィードバック遅延に対するロバスト性

腕を引いて即時に報酬が観測できない事はシステムの制約上良くあるよね、という前段に続いて報酬のフィードバックが遅れた場合の実験結果が載っている。1000ステップ遅れた場合にUCBの損失は10倍近くなるのに対して、TSは6倍程度。TSの方が性能良いという結果。

オンライン広告におけるCTR予測との組みあわせ

Contextual Banditな話。CTRの事後確率をベータ分布では無く、ロジスティック回帰で平均を求め、ラプラス近似でガウス分布にした物を利用する。PRMLでラプラス近似を見た時は何に使うのか理解できなかったが、なるほど納得。

この論文に書いてない事

腕の報酬が変化するパターンの実験はしていない。広告配信では腕の性能が変化する事は考慮しなければならないので気になる所。報酬の変化を捉えるにはUCBの様に一旦低く評価された腕を再度引くしかけが必要になるので、期待報酬の分散を増やすか利用する観測値は直近の物に限定する、といった工夫が必要だろう。