JubatusにThompson samplingを実装する - Dust TheoryJubatus0.7.0についにBanditアルゴリズムが実装されたのですが、漸近最適なアルゴリズムがまだ実装されていないので、Thompson sampling (TS) を実装してみました。 TSの詳細はThompson sampling - Wikipedia, the free encyclopediaなどに詳しいです。TSはThompsonさんが1930年に提案された最も古いアルゴリズムの1つなのですが、バンディット業界ではUCBなどと比べるとほとんど知られていませんでした。Googleの中の人がABテストに利用したことや、NIPS2011でTSの性能を他のアルゴリズムと比較した論文が出版され、圧倒的に性能が良いことが示されたことでTSは一躍注目をされるようになりました。理論的にも、TSは漸近最適なアルゴリズム*1の１つとして知られています。このアルゴリズムはベイズ推定に基づくた
