少ないバッチ数と小さなメモリ、しかし両方は同時には満たせない――確率的バンディットにおける同時の空間制約と適応性制約

要約: 確率的多腕バンディット問題を、空間と適応性の同時制約の下で研究する。学習者は環境と B バッチで相互作用し、持続的メモリを W ビットしか持たない。既存研究は、それぞれの制約が単独で意外にも穏やかであることを示している：完全に適応的な相互作用の下では、O("log T) ビットのメモリでほぼミニマックス後悔 ilde{O}(\sqrt{KT}) が達成可能であり、メモリが無制限の場合には、K に依存しない O(\log\\log T)-型のバッチ数で達成される。私たちはこの図が、同時制約下では崩れることを示す。私たちは、W ビットのメモリ制約を持つ任意のアルゴリズムは、適応的なグリッド下でも、ほぼミニマックス後悔 ilde{O}(\sqrt{KT}) を達成するには少なくとも ilde{{O}}(K/W) バッチを使用しなければならない。特に、対数的メモリでは K に依存しないバッチ複雑さは排除される。 本研究の証明は情報ボトルネックに基づく。ほぼミニマックス後悔は、適切な難しい事前分布の下で、学習者が良腕の隠れ集合について { ilde{O}}(K) ビットの情報を獲得することを強制する一方、B バッチと W ビットのメモリを持つアルゴリズムは情報を O(BW) ビットしか許容できない。重要な要素は、確率レベルのアーム探索保証を生み出す局所化された測度変更補題であり、これは独立した関心事である。また、O(\\log T) ビットのメモリと \ ilde{O}(K) バッチを用いるアルゴリズムを提示し、後悔を \ ilde{O}(\\sqrt{KT}) で達成する。これは下界にほぼ一致する。