Abstract
本研究では、確率的マルチアームド・バンディット（MAB）およびUCB（Upper Confidence Bound）に基づく探索を行う線形バンディットに対する、再現可能（replicable）なアルゴリズムを考察する。バンディットアルゴリズムが、共有された内部乱数を用いた2つの実行において、報酬の実現が独立であるにもかかわらず、少なくとも1-
hoの確率で同一の行動系列を生成する場合、そのアルゴリズムを
ho-再現可能（
ho-replicable）と呼ぶ。先行研究は主として除去（elimination）に基づくものであり、無限個の行動をもつ線形バンディットでは離散化に依存している。その結果、次元dと
hoに関する依存が最適ではないものとなっている。本研究では、両設定に対する楽観的（optimistic）な代替手法を開発する。確率的マルチアームド・バンディットに対しては、再現可能なバッチUCBアルゴリズムであるRepUCBを提案し、次のことを示す：この手法は損失（regret）O\!\left(\frac{K^2\log^2 T}{\rho^2}\sum_{a:\Delta_a>0}\left(\Delta_a+\frac{\log(KT\log T)}{\Delta_a}\right)\right) を達成する。確率的線形バンディットに対しては、まず、信頼（confidence）の保証と
ho-再現可能性の保証の両方を満たす、再現可能なリッジ回帰推定器RepRidgeを導入する。この推定器とその保証は、我々のバンディットアルゴリズムにおける役割にとどまらず、他の統計的推定の設定においても独立して関心を持たれうる。続いて、RepRidgeを用いて、確率的線形バンディット向けの再現可能な楽観的アルゴリズムRepLinUCBを設計し、その損失がO\!\left(\big(d+\frac{d^3}{\rho}\big)\sqrt{T}\right)で抑えられることを示す。これは、先行する最良の損失保証をO(d/\rho)の因子だけ改善し、我々の楽観的アルゴリズムが再現可能性に対する代償（price of replicability）を大幅に削減し得ることを示している。
