論文の概要: HAVER: Instance-Dependent Error Bounds for Maximum Mean Estimation and Applications to Q-Learning

• arxiv url: http://arxiv.org/abs/2411.00405v1
• Date: Fri, 01 Nov 2024 07:05:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-05 14:44:16.689392
• Title: HAVER: Instance-Dependent Error Bounds for Maximum Mean Estimation and Applications to Q-Learning
• Title（参考訳）: HAVER:最大平均値推定のためのインスタンス依存エラー境界とQ-Learningへの応用
• Authors: Tuan Ngo Nguyen, Kwang-Sung Jun,
• Abstract要約: そこで本研究では,K$分布中の最大平均値の固有値をサンプルを用いて推定する問題について検討する。 HAVERと呼ばれる新しいアルゴリズムを提案し,その平均二乗誤差を解析する。
• 参考スコア（独自算出の注目度）: 11.026588768210601
• License:
• Abstract: We study the problem of estimating the \emph{value} of the largest mean among $K$ distributions via samples from them (rather than estimating \emph{which} distribution has the largest mean), which arises from various machine learning tasks including Q-learning and Monte Carlo tree search. While there have been a few proposed algorithms, their performance analyses have been limited to their biases rather than a precise error metric. In this paper, we propose a novel algorithm called HAVER (Head AVERaging) and analyze its mean squared error. Our analysis reveals that HAVER has a compelling performance in two respects. First, HAVER estimates the maximum mean as well as the oracle who knows the identity of the best distribution and reports its sample mean. Second, perhaps surprisingly, HAVER exhibits even better rates than this oracle when there are many distributions near the best one. Both of these improvements are the first of their kind in the literature, and we also prove that the naive algorithm that reports the largest empirical mean does not achieve these bounds. Finally, we confirm our theoretical findings via numerical experiments including bandits and Q-learning scenarios where HAVER outperforms baseline methods.
• Abstract（参考訳）: 本研究では,Q-ラーニングやモンテカルロ木探索などの機械学習タスクから生じる,K$分布の最大平均値の推定問題(最大平均値の推定よりも)について検討する。 提案されたアルゴリズムはいくつかあるが、その性能分析は正確な誤差測定よりもバイアスに限られている。 本稿では,HAVER(Head Averaging)と呼ばれる新しいアルゴリズムを提案し,その平均二乗誤差を解析する。 分析の結果,HAVERは2つの点で魅力的な性能を示した。 まず、HAVERは最適な分布の正当性を知っており、そのサンプル平均を報告している神託とともに、最大平均を推定する。 第二に、おそらく意外なことに、HAVERは、最も良いものの近くに多くの分布がある場合、このオラクルよりもずっと良いレートを示す。 これらの改善はともに文献上では最初のものであり、また、最も大きな経験的平均を報告したナイーブアルゴリズムがこれらの境界を達成できないことも証明している。 最後に,HAVERがベースライン法より優れる帯域幅やQ-ラーニングシナリオを含む数値実験により理論的知見を確認した。

関連論文リスト

• An Upper Confidence Bound Approach to Estimating the Maximum Mean [0.0]
  本研究では, 上限値の最大値の推定について, 上限値 (UCB) を用いて検討した。 両推定器の強い一貫性、平均二乗誤差、中央極限定理(CLT)を含む統計的保証を確立する。
  論文  参考訳（メタデータ） (2024-08-08T02:53:09Z)
• Score-based generative models are provably robust: an uncertainty quantification perspective [4.396860522241307]
  本研究では,スコアベース生成モデル (SGM) が実運用において複数の誤差源に対して確実に堅牢であることを示す。 我々の主要なツールは、ワッサーシュタイン不確実性伝播(WUP)定理である。 a) 有限サンプル近似による誤差, (b) 早期停止, (c) スコアマッチング対象選択, (d) スコア関数パラメトリゼーション, (e) 基準分布選択が生成モデルの品質に与える影響を示す。
  論文  参考訳（メタデータ） (2024-05-24T17:50:17Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Partial identification of kernel based two sample tests with mismeasured data [5.076419064097733]
  最大平均離散性(MMD)のような2サンプルテストは、機械学習アプリケーションにおける2つの分布の違いを検出するためにしばしば使用される。 我々は,1つの分布の非ランダムな$epsilon$%が互いに誤ってグループ化されるような,$epsilon$-contaminationに基づくMDDの推定について検討した。 そこで本研究では,これらの境界を推定する手法を提案し,サンプルサイズが大きくなるにつれてMDD上の最も鋭い限界に収束する推定値を示す。
  論文  参考訳（メタデータ） (2023-08-07T13:21:58Z)
• Learning to Estimate Without Bias [57.82628598276623]
  ガウスの定理は、重み付き最小二乗推定器は線形モデルにおける線形最小分散アンバイアスド推定(MVUE)であると述べている。 本稿では、バイアス制約のあるディープラーニングを用いて、この結果を非線形設定に拡張する第一歩を踏み出す。 BCEの第二の動機は、同じ未知の複数の推定値が平均化されてパフォーマンスが向上するアプリケーションにおいてである。
  論文  参考訳（メタデータ） (2021-10-24T10:23:51Z)
• Ensemble Bootstrapping for Q-Learning [15.07549655582389]
  Ensemble Bootstrapped Q-Learning(EBQL)という新しいバイアス低減アルゴリズムを紹介します。 EBQLライクな更新は、独立確率変数の集合の最大平均を推定する際に低いMSEをもたらす。 過大評価と過小評価の両方が準最適性能をもたらす領域が存在することを示す。
  論文  参考訳（メタデータ） (2021-02-28T10:19:47Z)
• Large-Scale Methods for Distributionally Robust Optimization [53.98643772533416]
  我々のアルゴリズムは、トレーニングセットのサイズとパラメータの数によらず、多くの評価勾配を必要とすることを証明している。 MNIST と ImageNet の実験により,本手法の 9-36 倍の効率性を持つアルゴリズムの理論的スケーリングが確認された。
  論文  参考訳（メタデータ） (2020-10-12T17:41:44Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)
• Computationally efficient sparse clustering [67.95910835079825]
  我々はPCAに基づく新しいクラスタリングアルゴリズムの有限サンプル解析を行う。 ここでは,ミニマックス最適誤クラスタ化率を,体制$|theta infty$で達成することを示す。
  論文  参考訳（メタデータ） (2020-05-21T17:51:30Z)

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

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