論文の概要: Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits

• arxiv url: http://arxiv.org/abs/2405.15200v1
• Date: Fri, 24 May 2024 04:11:58 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-27 18:09:00.233089
• Title: Indexed Minimum Empirical Divergence-Based Algorithms for Linear Bandits
• Title（参考訳）: 線形帯域に対する指数最小経験的ダイバージェンスに基づくアルゴリズム
• Authors: Jie Bian, Vincent Y. F. Tan,
• Abstract要約: Indexed Minimum Empirical Divergence (IMED)は、マルチアームバンディット問題に対する非常に効果的なアプローチである。 UCBベースのアルゴリズムとトンプソンサンプリングを実証的に上回ることが観察されている。 我々は、LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの新しい線形バージョンを提案する。
• 参考スコア（独自算出の注目度）: 55.938644481736446
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Indexed Minimum Empirical Divergence (IMED) algorithm is a highly effective approach that offers a stronger theoretical guarantee of the asymptotic optimality compared to the Kullback--Leibler Upper Confidence Bound (KL-UCB) algorithm for the multi-armed bandit problem. Additionally, it has been observed to empirically outperform UCB-based algorithms and Thompson Sampling. Despite its effectiveness, the generalization of this algorithm to contextual bandits with linear payoffs has remained elusive. In this paper, we present novel linear versions of the IMED algorithm, which we call the family of LinIMED algorithms. We demonstrate that LinIMED provides a $\widetilde{O}(d\sqrt{T})$ upper regret bound where $d$ is the dimension of the context and $T$ is the time horizon. Furthermore, extensive empirical studies reveal that LinIMED and its variants outperform widely-used linear bandit algorithms such as LinUCB and Linear Thompson Sampling in some regimes.
• Abstract（参考訳）: Indexed Minimum Empirical Divergence (IMED) アルゴリズムは,マルチアームバンディット問題に対するKL-UCBアルゴリズムと比較して,漸近的最適性の理論的保証が強いアルゴリズムである。 さらに、UCBベースのアルゴリズムとトンプソンサンプリングを経験的に上回ることが観察されている。 その効果にもかかわらず、線形ペイオフを伴う文脈的包帯へのこのアルゴリズムの一般化はいまだ解明されていない。 本稿では,LinIMEDアルゴリズムのファミリーと呼ぶIMEDアルゴリズムの線形バージョンについて述べる。 我々は、LinIMED が $\widetilde{O}(d\sqrt{T})$ upper regret bound を提供することを示した。 さらに、LinIMEDとその変種はLinUCBやLinar Thompson Samplingなど、広く使われている線形バンディットアルゴリズムよりも優れていた。

関連論文リスト

• Minimum Empirical Divergence for Sub-Gaussian Linear Bandits [10.750348548547704]
  LinMEDは、アームサンプリング確率のクローズドフォーム計算を許容するランダム化アルゴリズムである。 我々の実証研究は、LinMEDが最先端のアルゴリズムと競合する性能を持っていることを示している。
  論文  参考訳（メタデータ） (2024-10-31T21:54:44Z)
• An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。 既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。 本稿では,差分探索アルゴリズム (CombGapE) を提案する。
  論文  参考訳（メタデータ） (2023-06-15T15:37:31Z)
• A Framework for Adapting Offline Algorithms to Solve Combinatorial Multi-Armed Bandit Problems with Bandit Feedback [27.192028744078282]
  離散オフライン近似アルゴリズムをサブ線形$alpha$-regretに適応するためのフレームワークを提供する。 提案手法は準モジュラー地平線における多種多様な応用に適用できる。
  論文  参考訳（メタデータ） (2023-01-30T23:18:06Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)
• Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
  バンディットアルゴリズムを結合する簡単な手法を提案する。 私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
  論文  参考訳（メタデータ） (2020-12-24T05:36:29Z)
• An Empirical Study of Derivative-Free-Optimization Algorithms for Targeted Black-Box Attacks in Deep Neural Networks [8.368543987898732]
  本稿では,BOBYQAに基づく新しいアルゴリズムの導入とともに,既存のDFOベースの4つのアルゴリズムについて考察する。 我々は、これらのアルゴリズムを様々な設定で比較し、それらを誤分類した画像の数に応じて比較する。 実験では、敵の例を見つける確率が、使用されるアルゴリズムと攻撃の設定の両方に依存するかを明らかにする。
  論文  参考訳（メタデータ） (2020-12-03T13:32:20Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。 MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
  論文  参考訳（メタデータ） (2020-10-12T17:41:44Z)
• Bandit algorithms to emulate human decision making using probabilistic distortions [20.422725678982726]
  報奨分布に歪んだ確率を持つ2つの多重武装バンディット問題を定式化する。 以上のような後悔の最小化の問題と、マルチアームバンディットのための最高の腕識別フレームワークについて考察する。
  論文  参考訳（メタデータ） (2016-11-30T17:37:51Z)

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

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