論文の概要: Pure Exploration via Frank-Wolfe Self-Play

• arxiv url: http://arxiv.org/abs/2509.19901v1
• Date: Wed, 24 Sep 2025 08:55:21 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-25 20:53:19.749199
• Title: Pure Exploration via Frank-Wolfe Self-Play
• Title（参考訳）: フランク=ウルフセルフプレイによる純粋探査
• Authors: Xinyu Liu, Chao Qin, Wei You,
• Abstract要約: 我々は、有限個の代替案から正しい仮説を効果的に同定することを目的として、構造化された多腕包帯の純粋な探索について研究する。 我々の分析は連続時間ステア(英語版)を通し、減衰するリャプノフ函数との微分包含は、失効する双対性ギャップと最適値への収束を示唆する。
• 参考スコア（独自算出の注目度）: 9.025261095806309
• License: http://creativecommons.org/licenses/by/4.0/
• 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.
• Abstract（参考訳）: 構成された確率的マルチアームバンディットの純粋探索について検討し、有限個の代替案から正しい仮説を効率的に同定することを目的とした。 幅広いタスクのクラスにおいて、漸近解析は、実験者と懐疑者の間の2つのプレイヤーゼロサムゲーム解釈を許容する最大最適化に還元される。 我々は、懐疑派が混合戦略を採用することを許し、凹凸サドルポイント問題を生じさせることで、ゲームを再構成する。 この視点はFWSP(Frank-Wolfe Self-Play)に通じており、プロジェクションフリー、正規化フリー、チューニングフリーの手法であり、両側のワンホット更新はバンドレートサンプリングのパラダイムと一致する。 しかしながら、構造的制約はアルゴリズムの設計と解析を複雑にするシャープな病理を伴い、線形帯域ケーススタディでは、最適な腕にゼロ質量の非特異な最適設計、境界における双線型目的、非平滑性を示す。 我々はこれらの課題を、微分包摂的議論(differential-inclusion argument)を通じて解決し、線形包帯におけるベストアーム識別のためのゲーム値の収束を証明した。 我々の解析は、ラプノフ関数との差分包含が指数関数的に減衰し、失効する双対性ギャップと最適値への収束を示唆する連続時間極限を経る。 Lyapunov 解析は境界上で保証されていない目的の微分可能性を必要とするが、連続的な軌道は、そのアルゴリズムが病理的非滑らかな点から遠ざかって、最適なゲーム値への一様大域収束を達成することを示す。 次に、離散時間更新を摂動フローに埋め込んで、離散ゲーム値も収束することを示す。 さらに,FWSPに基づく後続サンプリングに基づく学習アルゴリズムを提案する。 数値実験は、消滅する双対性ギャップを示す。

関連論文リスト

• Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [60.414548453838506]
  非線形リンク関数を組み込んで古典線形モデルを拡張したコンテキスト型多武装バンディットフレームワークである一般化線形バンディット問題(GLB)について検討する。 GLBは現実世界のシナリオに広く適用できるが、その非線形性は計算効率と統計効率の両方を達成する上で大きな課題をもたらす。 本稿では,$mathcalO(1)$時間と1ラウンドあたりの空間複雑度をほぼ最適に再現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-07-16T02:24:21Z)
• Performative Reinforcement Learning with Linear Markov Decision Process [14.75815792682734]
  提案手法がマルコフ決定過程の報酬と遷移の両方に影響を及ぼすような表現的強化学習の設定について検討する。 大規模MDPの主要な理論モデルであるEmphlinear Markov決定過程を一般化する。
  論文  参考訳（メタデータ） (2024-11-07T23:04:48Z)
• Trust-Region Sequential Quadratic Programming for Stochastic Optimization with Random Models [57.52124921268249]
  本稿では,1次と2次の両方の定常点を見つけるための信頼逐次準計画法を提案する。 本手法は, 1次定常点に収束するため, 対象対象の近似を最小化して定義された各イテレーションの勾配ステップを計算する。 2階定常点に収束するため,本手法は負曲率を減少するヘッセン行列を探索する固有ステップも計算する。
  論文  参考訳（メタデータ） (2024-09-24T04:39:47Z)
• Non-Convex Robust Hypothesis Testing using Sinkhorn Uncertainty Sets [18.46110328123008]
  非破壊仮説テスト問題に対処する新しい枠組みを提案する。 目標は、最大数値リスクを最小限に抑える最適な検出器を探すことである。
  論文  参考訳（メタデータ） (2024-03-21T20:29:43Z)
• Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
  我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。 我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。 新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
  論文  参考訳（メタデータ） (2023-04-04T04:32:29Z)
• Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Games [16.09467599829253]
  本研究では,2プレーヤゼロサムゲームにおけるナッシュ平衡を求める問題について検討する。 我々の主な貢献は、正規化パラメータの適切な選択の下で、勾配が元の非正規化問題のナッシュ平衡に傾くことを示すことである。
  論文  参考訳（メタデータ） (2022-05-27T03:24:12Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。 定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。 我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
  論文  参考訳（メタデータ） (2021-06-30T18:32:46Z)
• Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination [29.85468294601847]
  線形回帰と文脈的帯域幅という2つの古典的高次元オンライン学習問題を再考する。 従来の手法が失敗した場合にアルゴリズムが成功することを示す。
  論文  参考訳（メタデータ） (2020-10-08T17:59:05Z)
• Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave Min-Max Problems with PL Condition [52.08417569774822]
  本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
  論文  参考訳（メタデータ） (2020-06-12T00:32:21Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  エミュレータと呼ばれる適応サンプリングを解析するための新しい手法を提案する。 適切なログファクタを組み込んだトップk問題の最初のインスタンスベースの下位境界を証明します。 我々の新しい分析は、後者の問題に対するこの種の最初のエミュレータであるベストアームとトップkの識別に、シンプルでほぼ最適であることを示した。
  論文  参考訳（メタデータ） (2017-02-16T23:42:02Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。