Abstract
本稿では、学習者が実際に選択したアーム以外の複数のアームの損失も観測できる、敵対的なマルチアームバンディット問題を考えます。各非選択アームは、互いに独立かつ学習者の行動やそれ以外の要因に依存せず、固定ではあるが未知の確率r でその損失を明らかにするとします。異なる r の範囲に対して機能する2つのアルゴリズムを提案します。バンディット問題で N 個のアームを T ラウンド行った後、最初のアルゴリズムの期待後悔（regret）は、r\ge(
\log T)/(2N) のとき O(\sqrt{(T /r) \log N }) で抑えられることを示します。一方で2つ目のアルゴリズムは、より小さい r に対して O(\sqrt{(T/r) \log (N+T)}) の後悔を達成します。また、~r の範囲を決定するための迅速な推定手順も提示します。これらの上界はいずれも、たとえアルゴリズムが~r を知っていることが許されていても達成可能な最良の性能の、対数因子の範囲内に収まっています。
