論文の概要: Nearly Linear-Time Follow-the-Perturbed-Leader for Weakly Observable Graph Bandits

• arxiv url: http://arxiv.org/abs/2611.04307v1
• Date: Tue, 03 Nov 2026 04:38:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-11-10 12:06:06.514503
• Title: Nearly Linear-Time Follow-the-Perturbed-Leader for Weakly Observable Graph Bandits
• Title（参考訳）: 弱可観測グラフ帯域用ニアリニア時間追従形リーダ
• Abstract要約: Follow-the-Perturbed-Leader ポリシは、ほぼ線形な予測時間の複雑さで、最高の世界の保証を達成する。 本研究では, 強制探索, 条件付き幾何再サンプリング, 適応学習率と代理確率を組み合わせたグラフに基づく損失推定器を開発した。
• 参考スコア（独自算出の注目度）: 2.470815298095903
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study online learning with directed weakly observable feedback graphs and propose a Follow-the-Perturbed-Leader (FTPL) policy that achieves best-of-both-worlds guarantee with nearly linear expected time complexity. To preserve the simple structure of FTPL, we develop a novel graph-based loss estimator that combines forced exploration, conditional geometric resampling and adaptive learning rates with surrogate probabilities. Our policy achieves $\tilde{\mathcal{O}}(δ_*^{1/3} T^{2/3})$ regret for adversarial regimes as well as $\tilde{\mathcal{O}}(δ_* \log T / Δ_{\min}^2)$ regret for stochastic regimes, where $δ_*$ and $Δ$, respectively, denote the fractional weak domination number and the suboptimality gap. These results show that refined guarantees for problems with minimax regret of $Θ(T^{2/3})$ can be obtained through appropriately designed adaptive learning rates and loss estimators without sacrificing the simplicity of FTPL.
• Abstract（参考訳）: 本研究では,オンライン学習の方向性を弱く観測可能なフィードバックグラフを用いて研究し,ほぼ線形な予測時間で最良を保証できるFTPL(Follow-the-Perturbed-Leader)ポリシーを提案する。 FTPLの簡単な構造を維持するため,強制探索,条件付き幾何再構成,適応学習率と代理確率を組み合わせたグラフに基づく損失推定器を開発した。 我々の政策は、敵対的体制に対する後悔$\tilde{\mathcal{O}}(δ_*^{1/3} T^{2/3})と、確率的体制に対する後悔$\tilde{\mathcal{O}}(δ_* \log T / Δ_{\min}^2)を達成する。 これらの結果から, FTPL の単純さを犠牲にすることなく, 適応学習率と損失推定器を適切に設計することにより, 最小限の残差を $ (T^{2/3})$ に補正した保証が得られることがわかった。

関連論文リスト

• Follow the Perturbed Leader for Linear Bandits: $\sqrt{T}$ Regret over General Action Sets [19.08902782069551]
  一般のアクション集合に対して$sqrtT$の後悔を実現する最初の逆線形帯域幅アルゴリズムを与える。 我々のアルゴリズムは線形最適化オラクルのみを用いて,$widetildemathcalO(d5/4sqrtT)$ regretを達成した。
  論文  参考訳（メタデータ） (2026-10-13T06:42:02Z)
• Fine-Tuning on Self-Generated and Reward-Weighted Data: Learning Dynamics, Convergence Rates, and Benefits of Off-Policyness [69.00065140233411]
  REINFORCE -- RE(S) と呼ばれる -- は、$S ge 1$グルーフステップ毎にロールアウト分布を更新する。 我々は、$ ge 1$のスペクトルを網羅するRE(S) の統一理論を開発する。 任意の固定された$S$に対して、RE(S) は、ロールアウト分布の更新数$B = lfloor T / S rfloor rightarrow infty$ として最適ポリシーへの大域収束を楽しむ。
  論文  参考訳（メタデータ） (2026-09-29T07:54:06Z)
• Toward Simultaneously Optimal Regret in U-Calibration [41.366442572915496]
  既存のU校正アルゴリズムは、すべての有界固有損失に対して、最悪のケースの最適$O(sqrtT)$後悔を達成する。 正方形損失のような滑らかな損失であっても、最適の$O(log T)$後悔の代わりに$(sqrtT)$後悔を引き起こす。 具体的には,有界固有損失毎に$tilde O(sqrtT)$ regretを同時に達成する単一予測アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2026-06-16T22:44:37Z)
• Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPs [56.246783503873225]
  本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。 本稿では,ウィンドウ/リスタートベースアルゴリズムと同様に,より単純な重みに基づくアルゴリズムを提案する。 我々のフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
  論文  参考訳（メタデータ） (2026-01-03T04:50:21Z)
• Sparse Linear Bandits with Blocking Constraints [22.01704171400845]
  データ・ポーア・システマにおける高次元スパース線形包帯問題について検討する。 線形モデルに対するラッソ推定器の新たなオフライン統計的保証を示す。 本稿では,最小限のコストで最適空間パラメータ$k$の知識を必要としない相関に基づくメタアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-10-26T01:42:03Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
  バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。 最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
  論文  参考訳（メタデータ） (2023-07-25T15:42:11Z)
• Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
  本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。 より単純な重みに基づくアルゴリズムを生成する改良された分析フレームワークを提案する。 我々の新しいフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
  論文  参考訳（メタデータ） (2023-03-05T15:11:14Z)

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

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