スパース報酬への応用を伴う、半バンディットのための共分散適応アルゴリズム

要旨: 私たちは、確率的な組合せセミバンディットを調査します。この分野では、結果の全ての同時分布が問題インスタンスの複雑性に影響します（標準的なバンディットとは異なります）。典型的に考えられる分布は、特定のパラメータ値に依存しており、理論上は事前知識が必要とされるものの、実際には推定がかなり難しいです。例として、一般に仮定されるサブガウス族があります。私たちはこの問題を、代わりにサブ指数分布の新しい一般族を考えることで緩和します。この族には有界な分布やガウス分布が含まれます。この族に対して、未知の結果の共分散行列によってパラメータ化された期待レグレットに関する新しい下界を証明します。これは、サブガウス行列よりもより厳密な量です。次に、この共分散の推定値を用いるアルゴリズムを構成し、レグレットに関するタイトな漸近解析を示します。最後に、私たちの結果を、応用先が多くのレコメンダシステムにある疎な結果の族へ適用し、さらに拡張します。