論文の概要: Mean-based algorithms: A lower bound and regret

• arxiv url: http://arxiv.org/abs/2606.04931v1
• Date: Wed, 03 Jun 2026 14:23:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-04 20:44:18.823464
• Title: Mean-based algorithms: A lower bound and regret
• Title（参考訳）: 平均的アルゴリズム:低い境界と後悔
• Authors: Julius Durmann, Amelie Kleber,
• Abstract要約: 平均に基づくアルゴリズムは、平均的な報酬が低いアクションに低い確率を割り当てる。 時間的地平線が不明で,帯域幅フィードバックのみが利用可能である場合,平均に基づくアルゴリズムについて検討する。 実験によると、平均ベースのアルゴリズムはわずかに遅いが、他の帯域幅フィードバックアルゴリズムと競合する可能性がある。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Mean-based algorithms are a class of online learning algorithms that assign low probability to actions with low average rewards. Recent work indicates these algorithms converge favorably to serially undominated actions, which approximate Nash equilibria in economic games. However, empirical studies also show slower convergence compared to established algorithms in bandit-feedback scenarios. We study mean-based algorithms when the time horizon is unknown and only bandit feedback is available. In this setting, we provide the first lower bound on the algorithm-defining sequence $γ_t$ that formally establishes a limit on how fast these algorithms can learn. Additionally, we propose two mean-based algorithms: one generalizes $ε$-greedy, and the other extends the mean-based Exp3 to unknown horizons. Our experiments show that mean-based algorithms, although slightly slower, can perform competitively with other bandit-feedback algorithms. We further analyze the relationship to no-regret algorithms. Depending on the choice of $γ_t$, the intersection with no-regret algorithms is non-trivial, and we show that algorithms exist that are both mean-based and no-regret. This adds context to the "exploitability" of this class of algorithms that previous contributions suggest.
• Abstract（参考訳）: 平均に基づくアルゴリズムは、平均的な報酬が低いアクションに低い確率を割り当てるオンライン学習アルゴリズムのクラスである。 最近の研究は、これらのアルゴリズムが、経済ゲームにおけるナッシュ均衡を近似する直列的に支配されない行動に好適に収束していることを示している。 しかし、経験的研究は、バンディットフィードバックのシナリオにおいて確立されたアルゴリズムと比較して収束が遅いことも示している。 時間的地平線が不明で,帯域幅フィードバックのみが利用可能である場合,平均に基づくアルゴリズムについて検討する。 この設定では、アルゴリズム定義シーケンス $γ_t$ において、これらのアルゴリズムがどの程度の速さで学習できるかの制限を正式に定める最初の下界を提供する。 さらに、平均ベースのアルゴリズムを2つ提案する: 1つは$ε$-greedyを一般化し、もう1つは平均ベースのExp3を未知の地平線まで拡張する。 実験の結果,平均的アルゴリズムはわずかに遅いが,他の帯域フィードバックアルゴリズムと競合できることがわかった。 さらに,非regretアルゴリズムとの関係を解析する。 γ_t$を選択すると、非regretアルゴリズムとの交差は非自明であり、平均ベースと非regretの両方のアルゴリズムが存在することを示す。 このことは、以前のコントリビューションが示唆するこのクラスのアルゴリズムの"探索可能性"にコンテキストを追加する。

関連論文リスト

• Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards [40.99322897009357]
  トランケーションと平均中央値に基づく2つの新しいアルゴリズムを提案する。 我々のトラニケーションベースのアルゴリズムは、既存のトラニケーションベースのアプローチと区別して、オンライン学習をサポートする。 我々のアルゴリズムは,$epsilon=1$の既存アルゴリズムと比較して,対数係数による後悔境界を改善する。
  論文  参考訳（メタデータ） (2023-10-28T13:01:10Z)
• On Universally Optimal Algorithms for A/B Testing [49.429419538826444]
  ベルヌーイ報奨を伴う多腕バンディットにおける固定予算によるベストアーム識別の問題について検討する。 A/Bテスト問題としても知られる2つのアームの問題に対して,各アームを等しくサンプリングするアルゴリズムが存在しないことを証明した。
  論文  参考訳（メタデータ） (2023-08-23T08:38:53Z)
• Practical, Provably-Correct Interactive Learning in the Realizable Setting: The Power of True Believers [12.09273192079783]
  我々は、対話型学習を実現可能な設定で検討し、最適な腕の識別からアクティブな分類に至るまでの問題に対処する一般的な枠組みを開発する。 我々は,最小限の値と対数係数とを一致させる,計算効率のよい新しいアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2021-11-09T02:33:36Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  オンラインアルゴリズム選択(OAS)では、アルゴリズム問題クラスのインスタンスがエージェントに次々に提示され、エージェントは、固定された候補アルゴリズムセットから、おそらく最高のアルゴリズムを迅速に選択する必要がある。 SAT(Satisfiability)のような決定問題に対して、品質は一般的にアルゴリズムのランタイムを指す。 本研究では,OASのマルチアームバンディットアルゴリズムを再検討し,この問題に対処する能力について議論する。 ランタイム指向の損失に適応し、時間的地平線に依存しない空間的・時間的複雑さを維持しながら、部分的に検閲されたデータを可能にする。
  論文  参考訳（メタデータ） (2021-09-13T18:10:52Z)
• Corralling Stochastic Bandit Algorithms [54.10645564702416]
  相関アルゴリズムの後悔は、最も報酬の高い腕を含む最高のアルゴリズムの後悔よりも悪くはないことを示す。 最高報酬と他の報酬の差は、最高報酬と他の報酬の差に依存することを示す。
  論文  参考訳（メタデータ） (2020-06-16T15:33:12Z)
• Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
  基本アルゴリズムを選択できるメタアルゴリズムを開発した。 基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
  論文  参考訳（メタデータ） (2020-03-03T18:46:34Z)

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

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