論文の概要: The Greedy Advantage in Finite-Horizon Bandits

• arxiv url: http://arxiv.org/abs/2607.29375v1
• Date: Fri, 31 Jul 2026 12:59:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-03 14:29:40.715568
• Title: The Greedy Advantage in Finite-Horizon Bandits
• Title（参考訳）: 有限・水平バンドにおけるグリーディアドバンテージ
• Authors: Kai Zhou, Michael Lingzhi Li, Kai Wang,
• Abstract要約: 我々は、多武装ベルヌーイ・バンディットのための正規化グリーディ・アルゴリズムのクラスを開発する。 有限水平後悔は過渡的な探索コストと準最適収束項に分解されることを示す。 これらの結果は、正規化された欲求政策が有限水平バンディット問題に効果的なアプローチをもたらすことを示唆している。
• 参考スコア（独自算出の注目度）: 10.249946467967286
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Organizations increasingly rely on sequential experimentation to improve decision-making. While the multi-armed bandit literature has developed algorithms with strong asymptotic regret guarantees, many practical applications operate over finite and externally imposed horizons. Motivated by the finite-horizon setting, we develop a class of regularized greedy algorithms for multi-armed Bernoulli bandits. We derive the first finite-horizon regret envelopes for regularized greedy bandits, showing that finite-horizon regret decomposes into transient exploration costs and a suboptimal convergence term that decays exponentially with the regularization strength. This characterization yields principled calibration rules for the regularization parameters and, as a limiting case, sharper regret guarantees for the classical greedy policy. Across extensive numerical experiments, calibrated regularized greedy policies consistently match or outperform state-of-the-art algorithms. These results suggest that regularized greedy policies can provide an effective approach for finite-horizon bandit problems.
• Abstract（参考訳）: 組織は意思決定を改善するために、シーケンシャルな実験をますます頼りにしています。 多武装のバンディット文学は、強い漸近的後悔の保証を持つアルゴリズムを開発したが、多くの実践的応用は有限および外部に課された地平線上で動作している。 有限ホライゾン設定によって動機づけられた我々は、多武装ベルヌーイ・バンディットに対する正規化グリーディアルゴリズムのクラスを開発する。 正規化グリーディ・バンディットに対する最初の有限水平後悔封筒を導出し、有限水平後悔は過渡的な探索コストと、正規化強度とともに指数関数的に減衰する準最適収束項に分解されることを示す。 この特徴付けにより、正規化パラメータに対する原則化された校正規則が得られ、制限された場合として、古典的な欲求政策に対するよりシャープな後悔の保証が与えられる。 広範な数値実験を通じて、キャリブレーションされた正規化グリーディのポリシーは、常に最先端のアルゴリズムに適合または優れる。 これらの結果は、正規化された欲求政策が有限水平バンディット問題に効果的なアプローチをもたらすことを示唆している。

関連論文リスト

• Near-Constant Strong Violation and Last-Iterate Convergence for Online CMDPs via Decaying Safety Margins [31.581870065866568]
  制約付きマルコフ決定過程(CMDP)における安全なオンライン強化学習を,強い後悔と違反の指標の下で研究する。 サブリニアの強い報酬を後悔させる既存の原始二重法は、強い制約違反の増大を招いたり、あるいは固有振動による平均点収束に制限されたりしている。 本稿では,マルチ正規化探索(FlexDOME)アルゴリズムによるフレキシブルセーフティドメイン最適化を提案する。
  論文  参考訳（メタデータ） (2026-02-11T14:54:26Z)
• 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)
• Contextual bandits with concave rewards, and an application to fair ranking [108.48223948875685]
  CBCR (Contextual Bandits with Concave Rewards) に対する反省点のある最初のアルゴリズムを提案する。 我々は,スカラー・リワード問題に対するCBCRの後悔から,新たな縮小を導出した。 推薦の公正さによって動機づけられたCBCRの特別事例として,ランク付けと公正を意識した目的について述べる。
  論文  参考訳（メタデータ） (2022-10-18T16:11:55Z)
• A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
  我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。 目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。 本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
  論文  参考訳（メタデータ） (2022-09-15T16:59:19Z)
• Slowly Changing Adversarial Bandit Algorithms are Efficient for Discounted MDPs [10.68896183306706]
  強化学習は、長期計画の地平線と未知の遷移カーネルのさらなる困難を伴って、多武装のバンディット問題を一般化する。 また, 無限水平割引マルコフ決定過程において, 逆帯域設定における最適後悔を達成するために, 徐々に変化する逆帯域設定アルゴリズムが最適後悔を達成できることを示す。
  論文  参考訳（メタデータ） (2022-05-18T16:40:30Z)
• Be Greedy in Multi-Armed Bandits [22.301793734117805]
  グレディアルゴリズムは、各ラウンドで局所最適選択を行う、シーケンシャルな決定問題の最も単純なものである。 We provide a generic worst-case bound on the regret of the Greedy algorithm。 連続・無限・多武装バンディット問題において,ほぼ最適の最悪の後悔境界を検証できることを証明した。
  論文  参考訳（メタデータ） (2021-01-04T16:47:02Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。 本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-08-20T03:48:14Z)
• Corruption-Tolerant Gaussian Process Bandit Optimization [130.60115798580136]
  未知(典型的には非生成)関数を有界ノルムで最適化する問題を考察する。 我々は「高速だが非ローバスト」と「スロー」に基づく高速スローGP-UCBに基づくアルゴリズムを提案する。 ある種の依存関係は、汚職レベルによっては要求できない、と我々は主張する。
  論文  参考訳（メタデータ） (2020-03-04T09:46:58Z)
• A General Theory of the Stochastic Linear Bandit and Its Applications [8.071506311915398]
  本稿では,線形バンディット問題に対する一般解析フレームワークとアルゴリズム群を紹介する。 予測における最適化という新たな概念は、OFULの過剰探索問題を減少させるSieeved greedy(SG)と呼ばれる新しいアルゴリズムを生み出します。 SGが理論的に最適であることを示すことに加えて、実験シミュレーションにより、SGはgreedy、OFUL、TSといった既存のベンチマークよりも優れていることが示された。
  論文  参考訳（メタデータ） (2020-02-12T18:54:41Z)

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

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