Frank-Wolfe自己対戦による純粋探索
なぜ重要か: 企業や社会への影響が見込まれ、一般メディアにも波及する可能性があります。
arXiv:2509.19901v1 発表種別：新規
概要：本研究では、有限個の選択肢から正しい仮説を効率的に特定することを目指す、構造化確率的マルチアームバンディットにおける純粋探索を考察する。広範なタスクにおいて、漸近解析は、実験者と懐疑者の間の2人零和ゲーム解釈を許容する最大最小最適化に帰着する。実験者は選択肢を除外するために測定を割り当てる一方、懐疑者は選択肢を提案する。我々は、懐疑者が混合戦略を採用することを許容することでゲームを再定式化し、凹凸サドル点問題を得る。この観点は、Frank-Wolfe Self-Play (FWSP) を導く。これは、射影フリー、正則化フリー、チューニングフリーな手法であり、両側の一時的更新はバンディットサンプリングパラダイムと一致する。しかし、構造的制約は、アルゴリズム設計と解析を複雑にする鋭い病理を引き起こす。我々の線形バンディットのケーススタディは、非一意最適解、最良アームに質量ゼロの最適設計、双線形目的関数、境界における非滑らかさを示す。我々は微分包含議論を通じてこれらの課題に対処し、線形バンディットにおける最良アーム特定に対するゲーム値の収束を証明する。我々の解析は連続時間極限を通して進む。これは、指数関数的に減衰するリアプノフ関数を持つ微分包含であり、双対ギャップの消失と最適値への収束を意味する。リアプノフ解析は目的関数の微分可能性を必要とするが、境界では保証されないものの、連続軌道に沿ってアルゴリズムは病理的な非滑らかな点から離れて進み、最適ゲーム値への一様な大域的収束を達成することを示す。次に、離散時間更新を摂動流に埋め込み、離散ゲーム値も収束することを示す。FWSPに基づいて、我々はさらに事後サンプリングに基づく学習アルゴリズムを提案する。数値実験は、双対ギャップの消失を示す。
原文（英語）を表示
Title (EN): Pure Exploration via Frank-Wolfe Self-Play
arXiv:2509.19901v1 Announce Type: new
Abstract: We study pure exploration in structured stochastic multi-armed bandits, aiming to efficiently identify the correct hypothesis from a finite set of alternatives. For a broad class of tasks, asymptotic analyses reduce to a maximin optimization that admits a two-player zero-sum game interpretation between an experimenter and a skeptic: the experimenter allocates measurements to rule out alternatives while the skeptic proposes alternatives. We reformulate the game by allowing the skeptic to adopt a mixed strategy, yielding a concave-convex saddle-point problem. This viewpoint leads to Frank-Wolfe Self-Play (FWSP): a projection-free, regularization-free, tuning-free method whose one-hot updates on both sides match the bandit sampling paradigm. However, structural constraints introduce sharp pathologies that complicate algorithm design and analysis: our linear-bandit case study exhibits nonunique optima, optimal designs with zero mass on the best arm, bilinear objectives, and nonsmoothness at the boundary. We address these challenges via a differential-inclusion argument, proving convergence of the game value for best-arm identification in linear bandits. Our analysis proceeds through a continuous-time limit: a differential inclusion with a Lyapunov function that decays exponentially, implying a vanishing duality gap and convergence to the optimal value. Although Lyapunov analysis requires differentiability of the objective, which is not guaranteed on the boundary, we show that along continuous trajectories the algorithm steers away from pathological nonsmooth points and achieves uniform global convergence to the optimal game value. We then embed the discrete-time updates into a perturbed flow and show that the discrete game value also converges. Building on FWSP, we further propose a learning algorithm based on posterior sampling. Numerical experiments demonstrate a vanishing duality gap.
Published: 2025-09-24 19:00 UTC