論文の概要: Optimal and Practical Batched Linear Bandit Algorithm

• arxiv url: http://arxiv.org/abs/2507.08438v1
• Date: Fri, 11 Jul 2025 09:29:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-14 18:03:54.304861
• Title: Optimal and Practical Batched Linear Bandit Algorithm
• Title（参考訳）: 最適かつ実用的なバッチ線形帯域幅アルゴリズム
• Authors: Sanghoon Yu, Min-hwan Oh,
• Abstract要約: 本稿では, 線形バンドイット問題(バッチ化線形バンドイット)について, 限定適応性の下で検討する。 我々は、腕の除去と正規化G-最適設計を統合する新しいバッチアルゴリズムである textttBLAE を提案する。 本分析では,バッチワイド最適設計と改良された濃度境界のための新しい手法を提案する。
• 参考スコア（独自算出の注目度）: 8.087699764574788
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We study the linear bandit problem under limited adaptivity, known as the batched linear bandit. While existing approaches can achieve near-optimal regret in theory, they are often computationally prohibitive or underperform in practice. We propose \texttt{BLAE}, a novel batched algorithm that integrates arm elimination with regularized G-optimal design, achieving the minimax optimal regret (up to logarithmic factors in $T$) in both large-$K$ and small-$K$ regimes for the first time, while using only $O(\log\log T)$ batches. Our analysis introduces new techniques for batch-wise optimal design and refined concentration bounds. Crucially, \texttt{BLAE} demonstrates low computational overhead and strong empirical performance, outperforming state-of-the-art methods in extensive numerical evaluations. Thus, \texttt{BLAE} is the first algorithm to combine provable minimax-optimality in all regimes and practical superiority in batched linear bandits.
• Abstract（参考訳）: 本稿では, 線形バンドイット問題(バッチ化線形バンドイット)について, 限定適応性の下で検討する。 既存のアプローチは理論上、ほぼ最適の後悔を達成できるが、実際は計算的に禁止されるか、不十分であることが多い。 我々は,腕の除去を正規化されたG-最適設計と統合する新しいバッチアルゴリズムである‘texttt{BLAE} を提案し,大口$K$と小口$K$の両レジームにおいて,最小限の最適後悔(最大$T$の対数係数まで)を達成すると同時に,O(\log\log T)$バッチのみを使用する。 本分析では,バッチワイド最適設計と改良された濃度境界のための新しい手法を提案する。 重要なことに、‘texttt{BLAE} は計算オーバーヘッドが低く、経験的性能が強く、広範な数値評価において最先端の手法よりも優れていた。 したがって、 \texttt{BLAE} は全てのレジームにおける証明可能なミニマックス最適性と、バッチ化された線形帯域における実用的な優越性を組み合わせた最初のアルゴリズムである。

関連論文リスト

• Optimal Batched Linear Bandits [9.795531604467406]
  本稿では,探索・推定・探索の枠組みを取り入れたバッチ線形バンドイト問題に対するE$4$アルゴリズムを提案する。 探索速度の適切な選択により、E$4$は、$O(loglog T)$バッチのみで有限時間ミニマックス最適後悔を達成する。 探索レートの別の選択で、E$4$は、少なくとも$O(log T)$バッチを必要とするインスタンス依存の後悔境界を達成することを示す。
  論文  参考訳（メタデータ） (2024-06-06T14:57:52Z)
• Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits [55.938644481736446]
  Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。 UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。 我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
  論文  参考訳（メタデータ） (2024-05-24T04:11:58Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
  カーネル化されたバンディットアルゴリズムは、この問題に対して強い経験的および理論的性能を示した。 本稿では、未知関数を$epsilon$-一様近似で近似できるエンフェミス特定カーネル化帯域設定を、ある再生カーネルヒルベルト空間(RKHS)において有界ノルムを持つ関数で導入する。 提案アルゴリズムは,不特定性に関する事前知識を伴わず,$epsilon$への最適依存を実現する。
  論文  参考訳（メタデータ） (2021-11-09T09:00:02Z)
• Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits [45.43968161616453]
  バッチ線形文脈帯域に対する最適バッチ-regretトレードオフについて検討する。 時間的地平線が成長するにつれて2相表現を特徴とする後悔の保証を証明します。 また, 動的上界に依存した新しい行列不等式濃度を証明した。
  論文  参考訳（メタデータ） (2021-10-15T12:32:33Z)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
  論文  参考訳（メタデータ） (2021-10-15T00:54:04Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Lenient Regret and Good-Action Identification in Gaussian Process Bandits [43.03669155559218]
  我々は、あるしきい値を超える関数値が「十分良い」という緩和された最適化基準の下で、ガウス過程(GP)バンディットの問題を研究する。 実用面では、既知のしきい値に従って1つの「良い行動」を見つけることの問題を考えるとともに、しきい値の知識を生かしたいくつかの善行動識別アルゴリズムを導入する。
  論文  参考訳（メタデータ） (2021-02-11T01:16:58Z)
• Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
  敵対的レジリエントな分散最適化。 機械は独立して勾配を計算し 協力することができます 私達のアルゴリズムは新しい集中の技術およびサンプル複雑性に基づいています。 それは非常に実用的です:それはないときすべての前の方法の性能を改善します。 セッティングマシンがあります。
  論文  参考訳（メタデータ） (2020-12-28T17:19:32Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)

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

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