論文の概要: Self-Concordant Perturbations for Linear Bandits

• arxiv url: http://arxiv.org/abs/2510.24187v1
• Date: Tue, 28 Oct 2025 08:47:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-29 15:35:36.909489
• Title: Self-Concordant Perturbations for Linear Bandits
• Title（参考訳）: 線形帯域に対する自己調和型摂動
• Authors: Lucas Lévy, Jean-Lou Valeau, Arya Akhavan, Patrick Rebeschini,
• Abstract要約: 本稿では,Follow-the-Regularized-Leader法とFollow-the-Perturbed-Leader法をブリッジする統合アルゴリズムフレームワークを提案する。 自己協和性バリアの役割を反映した確率分布のファミリーである自己協和性摂動を導入する。 我々のアプローチは、$d$次元ハイパーキューブとユークリッド球の両方で$O(dsqrtn ln)$を後悔する。
• 参考スコア（独自算出の注目度）: 9.957131269346096
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the adversarial linear bandits problem and present a unified algorithmic framework that bridges Follow-the-Regularized-Leader (FTRL) and Follow-the-Perturbed-Leader (FTPL) methods, extending the known connection between them from the full-information setting. Within this framework, we introduce self-concordant perturbations, a family of probability distributions that mirror the role of self-concordant barriers previously employed in the FTRL-based SCRiBLe algorithm. Using this idea, we design a novel FTPL-based algorithm that combines self-concordant regularization with efficient stochastic exploration. Our approach achieves a regret of $O(d\sqrt{n \ln n})$ on both the $d$-dimensional hypercube and the Euclidean ball. On the Euclidean ball, this matches the rate attained by existing self-concordant FTRL methods. For the hypercube, this represents a $\sqrt{d}$ improvement over these methods and matches the optimal bound up to logarithmic factors.
• Abstract（参考訳）: 本稿では,FTRL(Follow-the-Regularized-Leader)法とFTPL(Follow-the-Perturbed-Leader)法をブリッジする一貫したアルゴリズムフレームワークを提案する。 本枠組みでは,FTRLに基づくSCRiBLeアルゴリズムにおいて,自己協和障壁の役割を反映した確率分布系である自己協和摂動を導入する。 このアイデアを用いて、自己一致正則化と効率的な確率探索を組み合わせたFTPLに基づく新しいアルゴリズムを設計する。 我々のアプローチは、$d$次元ハイパーキューブとユークリッド球の両方で$O(d\sqrt{n \ln n})$を後悔する。 ユークリッド球では、これは既存の自己調和FTRL法によって達成された速度と一致する。 ハイパーキューブの場合、これはこれらのメソッドに対する$\sqrt{d}$の改善を表し、対数係数への最適境界に一致する。

関連論文リスト

• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  一般的な嗜好を伴う文脈的オンラインRLHFの問題を考える。 一般化された双線形選好モデルを用いて、低ランクなスキュー対称行列による選好を捉える。 グリーディポリシーの双対ギャップは推定誤差の正方形によって有界であることを示す。
  論文  参考訳（メタデータ） (2026-02-26T15:27:53Z)
• Graph-based Clustering Revisited: A Relaxation of Kernel $k$-Means Perspective [73.18641268511318]
  本稿では,クラスタリング結果を導出するための正規制約のみを緩和するグラフベースのクラスタリングアルゴリズムを提案する。 二重制約を勾配に変換するために、非負の制約をクラス確率パラメータに変換する。
  論文  参考訳（メタデータ） (2025-09-23T09:14:39Z)
• Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Bandits [3.448177863267093]
  コンテクスト的半帯域に対して,$widetildemathcalO(sqrtT)$ regretを同時に保証する,初めてのベスト・オブ・ボス・ワールド・アルゴリズムを導入する。 Karush-Kuhn-Tucker条件を利用することで、$K$凸射影問題を1次元のルートフィニング問題に変換する。 実証的な評価は、この組み合わせ戦略が、最高の世界のアルゴリズムの魅力的な後悔の限界に達するだけでなく、ラウンドごとの大幅なスピードアップをもたらすことを示している。
  論文  参考訳（メタデータ） (2025-08-26T07:51:22Z)
• Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [70.38810219913593]
  非線形リンク関数を組み込んで古典線形モデルを拡張したコンテキスト型多武装バンディットフレームワークである一般化線形バンディット問題(GLB)について検討する。 GLBは現実世界のシナリオに広く適用できるが、その非線形性は計算効率と統計効率の両方を達成する上で大きな課題をもたらす。 本稿では,$mathcalO(1)$時間と1ラウンドあたりの空間複雑度をほぼ最適に再現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-07-16T02:24:21Z)
• Reinforced Latent Reasoning for LLM-based Recommendation [92.56166822197919]
  大きな言語モデル(LLM)は、複雑な問題解決タスクにおいて印象的な推論能力を示している。 既存の手法は通常、明示的なチェーン・オブ・シント(CoT)データによる微調整に依存している。 本研究では, 明示的なCoT推論から, コンパクトで情報密度の高い潜伏推論へ移行する代替手法について検討する。
  論文  参考訳（メタデータ） (2025-05-25T11:03:45Z)
• A Near-optimal, Scalable and Corruption-tolerant Framework for Stochastic Bandits: From Single-Agent to Multi-Agent and Beyond [2.5217803205496283]
  我々はBARBATと呼ばれる新しいフレームワークを提案し、これは$K$の係数を排除し、対数係数に縛られた最適の後悔を実現する。 また,BARBATがグラフバンド,半帯域,バッチバンド,マルチエージェントバンドなど,さまざまな設定に拡張可能であることを示す。
  論文  参考訳（メタデータ） (2025-02-11T12:33:33Z)
• Optimism in the Face of Ambiguity Principle for Multi-Armed Bandits [6.075593833879357]
  FTRL (Follow-The-Regularized-Leader) アルゴリズムは、しばしば敵対的問題や盗賊問題に対して最適な後悔を味わう。 本稿では,逆方向と多重方向の両方の帯域に対して最適なポリシを生成する新しいFTPLアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-09-30T16:00:23Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
  固有の報酬は、探検と探検のトレードオフを扱う上で中心的な役割を果たす。 楕円ボーナスを効率的に近似するためのエンファンティ集中型信頼境界を導入する。 我々は,Atariベンチマーク上での現代固有の報酬と競合する,深層強化学習のための実用的な変種を開発する。
  論文  参考訳（メタデータ） (2021-10-21T15:25:15Z)
• A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants [39.28675942566465]
  本稿では,値に基づく非同期RLアルゴリズムのクラスに対する有限サンプル収束保証について検討する枠組みを開発する。 副産物として、偏差トレードオフ、すなわちRLにおけるブートストラップの効率に関する理論的知見を提供する。
  論文  参考訳（メタデータ） (2021-02-02T15:48:19Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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