論文の概要: Last Iterate Analyses of FTRL in Stochasitc Bandits

• arxiv url: http://arxiv.org/abs/2510.22819v1
• Date: Sun, 26 Oct 2025 20:20:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-28 19:54:32.563427
• Title: Last Iterate Analyses of FTRL in Stochasitc Bandits
• Title（参考訳）: 確率帯域におけるFTRLの最後の反復解析
• Authors: Jingxin Zhan, Yuze Han, Zhihua Zhang,
• Abstract要約: 対数的後悔は, 最終項目収束率$t-1$に対応するべきである。 BOBW FTRLアルゴリズムに付随する正規関数 $Psi(p)=-4sum_i=1dsqrtp_i$ で定義されるブレグマン発散は、$t-1/2$ の速度で減衰する。
• 参考スコア（独自算出の注目度）: 11.223878908981725
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The convergence analysis of online learning algorithms is central to machine learning theory, where last-iterate convergence is particularly important, as it captures the learner's actual decisions and describes the evolution of the learning process over time. However, in multi-armed bandits, most existing algorithmic analyses mainly focus on the order of regret, while the last-iterate (simple regret) convergence rate remains less explored -- especially for the widely studied Follow-the-Regularized-Leader (FTRL) algorithms. Recently, a growing line of work has established the Best-of-Both-Worlds (BOBW) property of FTRL algorithms in bandit problems, showing in particular that they achieve logarithmic regret in stochastic bandits. Nevertheless, their last-iterate convergence rate has not yet been studied. Intuitively, logarithmic regret should correspond to a $t^{-1}$ last-iterate convergence rate. This paper partially confirms this intuition through theoretical analysis, showing that the Bregman divergence, defined by the regular function $\Psi(p)=-4\sum_{i=1}^{d}\sqrt{p_i}$ associated with the BOBW FTRL algorithm $1/2$-Tsallis-INF (arXiv:1807.07623), between the point mass on the optimal arm and the probability distribution over the arm set obtained at iteration $t$, decays at a rate of $t^{-1/2}$.
• Abstract（参考訳）: オンライン学習アルゴリズムの収束分析は機械学習理論の中心であり、学習者の実際の決定を捉え、時間の経過とともに学習プロセスの進化を記述するため、最終段階の収束が特に重要である。 しかし、多武装の盗賊では、既存のアルゴリズム分析は主に後悔の順序に焦点をあてるが、最後の(単純な後悔)収束速度は、特に広く研究されているFTRL(Follow-the-Regularized-Leader)アルゴリズムでは、まだ明らかにされていない。 近年,FTRLアルゴリズムのBest-of-Both-Worlds(BOBW)特性がバンドイット問題で確立され,特に確率的バンドイットにおける対数的後悔が達成されている。 しかし、その最後の収束速度はまだ研究されていない。 直観的には、対数的後悔は$t^{-1}$ last-iterate convergence rateに対応するべきである。 本稿では、この直観を理論解析により部分的に確認し、正則函数 $\Psi(p)= 4\sum_{i=1}^{d}\sqrt{p_i}$ と BOBW FTRL アルゴリズム $1/2$-Tsallis-INF (arXiv:1807.07623) と、反復$t$ で得られたアームセット上の点質量と確率分布の間のブレグマン偏差が $t^{-1/2}$ で崩壊することを示す。

関連論文リスト

• Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback [61.49239204705301]
  本研究では,有限水平マルコフ決定過程(MDP)におけるオンライン学習について,包括的包括的包括的フィードバックモデルを用いて検討する。 本研究は, オンライン最短経路問題の近年の進展に触発された, 占領対策, 自己拘束技術, 新たな損失推定器の組合せに依拠する。
  論文  参考訳（メタデータ） (2025-10-20T02:28:08Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。 我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
  論文  参考訳（メタデータ） (2025-06-03T02:56:26Z)
• On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Games [71.73971094342349]
  ゲームにおける学習力学の非エルゴード収束は、理論と実践の両方において重要であるため、広く研究されている。 近年の研究では、最適乗算重み更新を含む学習力学の幅広いクラスが、任意に遅い最終項目収束を示すことが示されている。 OMWUは、同じクラスのゲームにおいて、その遅い最終点収束とは対照的に、$O(T-1/6)$est-iterate convergence rateを達成することを示す。
  論文  参考訳（メタデータ） (2025-03-04T17:49:24Z)
• Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds [46.30750729936261]
  FTRL(Follow-the-regularized-leader)は近年,バンドイット問題における適応性獲得の最も有望なアプローチの1つである。 我々は3種類の適応性を持ついくつかのアルゴリズムを確立する:空間性、ゲーム依存性、およびベスト・オブ・ボス・ワールド(BOBW)である。
  論文  参考訳（メタデータ） (2023-05-26T23:20:48Z)
• The Power of Regularization in Solving Extensive-Form Games [28.043425786728157]
  より弱い仮定かより強い収束保証を条件として,ゲームのファンクションペイオフの正規化に基づく,一連の新しいアルゴリズムを提案する。 我々の知る限り、これらは、非摂動EFGのNEを求める際に、最先端の平均収束率と整合しながら、CFR型アルゴリズムの最終的な収束結果を構成する。
  論文  参考訳（メタデータ） (2022-06-19T22:10:38Z)
• Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation [107.54516740713969]
  本研究は,RL(Human-in-the-loop reinforcement learning)を軌道的嗜好で検討する。 各ステップで数値的な報酬を受ける代わりに、エージェントは人間の監督者から軌道上のペアよりも優先される。 一般関数近似を用いたPbRLの楽観的モデルベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-05-23T09:03:24Z)
• A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants [39.28675942566465]
  本稿では,値に基づく非同期RLアルゴリズムのクラスに対する有限サンプル収束保証について検討する枠組みを開発する。 副産物として、偏差トレードオフ、すなわちRLにおけるブートストラップの効率に関する理論的知見を提供する。
  論文  参考訳（メタデータ） (2021-02-02T15:48:19Z)

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

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