論文の概要: Follow the Perturbed Leader for Linear Bandits: $\sqrt{T}$ Regret over General Convex Sets

• arxiv url: http://arxiv.org/abs/2610.17818v1
• Date: Tue, 13 Oct 2026 06:42:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-16 19:13:15.932372
• Title: Follow the Perturbed Leader for Linear Bandits: $\sqrt{T}$ Regret over General Convex Sets
• Title（参考訳）: 線形帯域における摂動的リーダーのフォロー:$\sqrt{T}$ Regret over General Convex Sets
• Abstract要約: 一般凸作用集合に対して$sqrtT$後悔を達成する最初の逆線形帯域幅アルゴリズムを与える。 我々のアルゴリズムは線形最適化オラクルのみを用いて,$widetildemathcalO(d5/4sqrtT)$ regretを達成した。
• 参考スコア（独自算出の注目度）: 19.08902782069551
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give the first adversarial linear bandit algorithm based on Follow-the-Perturbed-Leader (FTPL) that achieves $\sqrt{T}$ regret over general convex action sets. Our algorithm attains $\widetilde{\mathcal{O}}(d^{5/4}\sqrt{T})$ regret using only linear optimization oracles, and the near-optimal $\widetilde{\mathcal{O}}(d\sqrt{T})$ regret when an optimal-design exploration distribution is further available. This improves on the $T^{2/3}$ regret of the FTPL algorithm of Dani and Hayes (2006) for general convex sets, and generalizes the $\sqrt{T}$ regret of Lévy et al. (2026) over two special action sets (hypercube and Euclidean ball). Compared to previous oracle-efficient linear bandit algorithms based on continuous exponential weights, the FTPL approach generally has better computational efficiency, and is much simpler to implement. The key algorithmic element is a perturbation distribution that adapts to the estimated rewards. Its simplest form, an adaptive Gaussian perturbation, is straightforward to implement and already attains the regret bound above. We further extend it to two general constructions, random-weighting and elliptical perturbations, each covering distributions from light tails (Gaussian) to heavy tails (Student-$t_2$). On the technical side, we develop a systematic way to analyze the stability term in the FTPL regret through the Fisher information of the perturbation distribution. This builds a general framework for FTPL beyond existing ones such as the hazard rate and the FTRL-FTPL duality.
• Abstract（参考訳）: 本稿では,Follow-the-Perturbed-Leader (FTPL) をベースとした,一般凸作用集合に対して$\sqrt{T}$後悔を生じる最初の逆線形帯域化アルゴリズムを提案する。 我々のアルゴリズムは、線形最適化オラクルのみを用いて、$\widetilde{\mathcal{O}}(d^{5/4}\sqrt{T})を後悔し、最適設計探索分布がさらに利用可能になったときに、$\widetilde{\mathcal{O}}(d\sqrt{T})を後悔する。 これは、一般的な凸集合に対してDani and Hayes (2006) のFTPLアルゴリズムを後悔する$T^{2/3}$を改善し、2つの特別な作用集合 (hypercube と Euclidean ball) に対して $\sqrt{T}$ regret of Lévy et al (2026) を一般化する。 連続指数重みに基づく以前のオラクル効率の線形帯域幅アルゴリズムと比較して、FTPLアプローチは一般に計算効率が良く、実装もずっと簡単である。 鍵となるアルゴリズム要素は、推定された報酬に適応する摂動分布である。 その最も単純な形式、適応ガウス摂動は簡単に実装でき、上述の後悔を既に達成している。 さらに、ランダムな重み付けと楕円的な摂動という2つの一般的な構成に拡張し、それぞれが軽い尾(ガウス)から重い尾(Student-$t_2$)までの分布をカバーする。 技術面では、摂動分布のフィッシャー情報を用いてFTPL後悔の安定項を系統的に解析する方法を開発した。 これにより、ハザードレートやFTRL-FTPL双対性といった既存のフレームワークを超えてFTPLの一般的なフレームワークを構築する。

関連論文リスト

• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。 一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。 グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
  論文  参考訳（メタデータ） (2026-02-26T15:27:53Z)
• Note on Follow-the-Perturbed-Leader in Combinatorial Semi-Bandit Problems [10.435741631709403]
  小型不変半帯域問題におけるFollow-the-Perturbed-Leader(FTPL)ポリシーの最適性と複雑性について検討する。 我々は条件付き幾何再サンプリング(CGR)をサイズ不変半帯域設定に拡張し、計算の複雑さをオリジナルのGRの$O(d2)$から$Oleft(mdleft(log(d/m)+1right)$に縮める。
  論文  参考訳（メタデータ） (2025-06-14T13:06:30Z)
• Tangential Randomization in Linear Bandits (TRAiL): Guaranteed Inference and Regret Bounds [1.03590082373586]
  本稿では,線形帯域探索アルゴリズムTRAiLの提案と解析を行う。 TraiLは、設計(回帰器)行列の最小固有値によって測定された推論品質の$Omega(sqrtT)$成長を保証する。 我々は,期待された後悔に対して,任意のアルゴリズムに対して$Omega(sqrtT)$ minimax小境界を特徴付ける。
  論文  参考訳（メタデータ） (2024-11-19T01:08:13Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Best-of-Both-Worlds Algorithms for Linear Contextual Bandits [11.94312915280916]
  両世界のベスト・オブ・ワールドズ・アルゴリズムを$K$武器付き線形文脈包帯に対して検討する。 我々のアルゴリズムは、敵対的体制と敵対的体制の両方において、ほぼ最適の後悔の限界を提供する。
  論文  参考訳（メタデータ） (2023-12-24T08:27:30Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)

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

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