要旨: 競合バンディット（Competing Bandits）フレームワークは、オンライン学習における多腕バンディットとゲーム理論における安定マッチングを統合する、最近現れつつある分野です。従来のモデルは、すべてのプレイヤーとアームが常に利用可能であると仮定しますが、現実世界の問題では、それらの利用可能性は時間とともに任意に変化します。本論文では、この設定を睡眠状態の競合バンディット（Sleeping Competing Bandits）として定式化します。この問題を分析するために、既存の競合バンディットで用いられている後悔の定義を自然に拡張し、提案モデルに対する後悔の境界を導出します。合理的な仮定の下で、次の漸近的後悔境界を同時に達成するアルゴリズムを提案します。すなわち、\, ext{O} です。ここで
left(NK\log T_{i}/\Delta^2\right)N はプレイヤーの数、K はアームの数、T_{i} は各プレイヤー p_i のラウンド数、そして \Delta は最小報酬差です。同じ仮定の下で、後悔の下限も \, ext{\Omega}\left( N(K-N+1)\log T_{i}/\Delta^2 \right) を提供します。これは、アームの数 K がプレイヤーの数 N より相対的に大きい領域において、我々のアルゴリズムが漸近的に最適であることを意味します。
スリーピング競合バンディットの後悔分析
arXiv cs.LG / 2026/3/23
📰 ニュースIdeas & Deep AnalysisModels & Research
要点
- 本論文は、プレイヤーとアームの利用可能性が時間とともに変化する設定へと競合バンディットを拡張する『スリーピング競合バンディット』を提案する。
- この設定における後悔を再定義し、同じ仮定の下で一致する上界と下界を導出する。漸近的な上界は O(NK log Ti / Δ^2)、下界は Ω(N(K−N+1) log Ti / Δ^2) である。
- 同じ仮定の下で漸近的上界を達成するアルゴリズムを提案し、K が N より相対的に大きい領域において漸近的に最適である。
- 本研究はオンライン学習とゲーム理論の交差領域に位置しており、参加と資源が変動する動的な現実世界の意思決定問題に示唆を与える。
