論文の概要: On Best-Arm Identification with a Fixed Budget in Non-Parametric Multi-Armed Bandits

• arxiv url: http://arxiv.org/abs/2210.00895v1
• Date: Fri, 30 Sep 2022 10:55:40 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-04 14:59:12.572382
• Title: On Best-Arm Identification with a Fixed Budget in Non-Parametric Multi-Armed Bandits
• Title（参考訳）: 非パラメトリックマルチアーマバンドにおける固定予算付きベストアーム同定について
• Authors: Antoine Barrier (UMPA-ENSL, LMO, CELESTE), Aur\'elien Garivier (UMPA-ENSL, LIP), Gilles Stoltz (LMO, CELESTE)
• Abstract要約: 我々は、腕上の分布の一般、おそらくはパラメトリックでないモデルDを考える。 情報理論量に基づいて最適なアームを誤識別する平均対数確率の上限を提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We lay the foundations of a non-parametric theory of best-arm identification in multi-armed bandits with a fixed budget T. We consider general, possibly non-parametric, models D for distributions over the arms; an overarching example is the model D = P(0,1) of all probability distributions over [0,1]. We propose upper bounds on the average log-probability of misidentifying the optimal arm based on information-theoretic quantities that correspond to infima over Kullback-Leibler divergences between some distributions in D and a given distribution. This is made possible by a refined analysis of the successive-rejects strategy of Audibert, Bubeck, and Munos (2010). We finally provide lower bounds on the same average log-probability, also in terms of the same new information-theoretic quantities; these lower bounds are larger when the (natural) assumptions on the considered strategies are stronger. All these new upper and lower bounds generalize existing bounds based, e.g., on gaps between distributions.
• Abstract（参考訳）: 我々は、腕上の分布に対する一般的な、おそらく非パラメトリックなモデル d を考える。 包括的な例として、[0,1] 上のすべての確率分布のモデル d = p(0,1) が挙げられる。 そこで本稿では,D の分布と与えられた分布との間に存在するクルバック・リーブラーの不等式に対応する情報理論量に基づいて,最適アームを誤同定する平均対数確率の上限を提案する。 これは Audibert, Bubeck, Munos (2010) の連続再帰戦略の洗練された解析によって可能となった。 我々は最終的に、同じ平均対数確率に対する下限を、同じ新しい情報理論量の観点からも提供し、これらの下限は、検討された戦略に対する(自然な)仮定がより強いときに大きい。 これらの新しい上界と下界は、例えば分布間のギャップに基づいて既存の境界を一般化する。

関連論文リスト

• Gradual Domain Adaptation via Manifold-Constrained Distributionally Robust Optimization [0.4732176352681218]
  本稿では、多様体制約データ分布のクラスにおける段階的領域適応の課題に対処する。 本稿では,適応的なワッサースタイン半径を持つ分布ロバスト最適化(DRO)を基礎とした手法を提案する。 我々のバウンダリは、新たに導入されたそれとの互換性尺度に依存しており、シーケンスに沿ったエラー伝搬のダイナミクスを完全に特徴付けています。
  論文  参考訳（メタデータ） (2024-10-17T22:07:25Z)
• Non-asymptotic bounds for forward processes in denoising diffusions: Ornstein-Uhlenbeck is hard to beat [49.1574468325115]
  本稿では,全変動(TV)における前方拡散誤差の非漸近的境界について述べる。 我々は、R$からFarthestモードまでの距離でマルチモーダルデータ分布をパラメライズし、加法的および乗法的雑音による前方拡散を考察する。
  論文  参考訳（メタデータ） (2024-08-25T10:28:31Z)
• 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)
• A General Recipe for the Analysis of Randomized Multi-Armed Bandit Algorithms [14.33758865948252]
  我々は2つの有名なバンディットアルゴリズム、Minimum Empirical Divergence (MED)とThompson Sampling (TS)を再検討する。 MEDがこれらのモデルすべてに最適であることを示すとともに、最適性がすでに知られているTSアルゴリズムの簡単な後悔解析も提供する。
  論文  参考訳（メタデータ） (2023-03-10T16:43:48Z)
• Beyond the Best: Estimating Distribution Functionals in Infinite-Armed Bandits [40.71199236098642]
  無限武装バンディット問題では、各アームの平均報酬は未知の分布からサンプリングされる。 我々は、最大以上の分布関数の一般的なクラスを検討し、オフラインとオンラインの両方で統一されたメタアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-11-01T18:20:10Z)
• Targeted Separation and Convergence with Kernel Discrepancies [61.973643031360254]
  カーネルベースの不一致測度は、(i)ターゲットPを他の確率測度から分離するか、(ii)Pへの弱収束を制御する必要がある。 本稿では, (i) と (ii) を保証するのに十分な,必要な新しい条件を導出する。 可分距離空間上のMDDに対して、ボヒナー埋め込み可測度を分離するカーネルを特徴づけ、すべての測度を非有界カーネルと分離するための単純な条件を導入する。
  論文  参考訳（メタデータ） (2022-09-26T16:41:16Z)
• From Optimality to Robustness: Dirichlet Sampling Strategies in Stochastic Bandits [0.0]
  本研究では、腕の観察を再サンプリングした経験的指標のペア比較に基づいて、ジェネリックディリクレサンプリング(DS)アルゴリズムについて検討する。 この戦略の異なる変種は、分布が有界であるときに証明可能な最適後悔保証と、半有界分布に対して軽度量子状態の対数後悔を実現することを示す。
  論文  参考訳（メタデータ） (2021-11-18T14:34:21Z)
• Robust Learning of Optimal Auctions [84.13356290199603]
  本研究では、入札者の評価値のサンプルを逆向きに破損させたり、逆向きに歪んだ分布から引き出すことができる場合に、サンプルから収益-最適マルチバイダオークションを学習する問題について検討する。 我々は,コルモゴロフ-スミルノフ距離における元の分布に対して$alpha$-closeの「全ての真の分布」に対して,収入がほぼ同時に最適であるメカニズムを学習できる新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-07-13T17:37:21Z)
• Distributional Reinforcement Learning via Moment Matching [54.16108052278444]
  ニューラルネットワークを用いて各戻り分布から統計量の有限集合を学習する手法を定式化する。 我々の手法は、戻り分布とベルマン目標の間のモーメントの全ての順序を暗黙的に一致させるものとして解釈できる。 Atariゲームスイートの実験により,本手法は標準分布RLベースラインよりも優れていることが示された。
  論文  参考訳（メタデータ） (2020-07-24T05:18:17Z)
• Lower bounds in multiple testing: A framework based on derandomized proxies [107.69746750639584]
  本稿では, 各種コンクリートモデルへの適用例を示す, デランドマイズに基づく分析戦略を提案する。 これらの下界のいくつかを数値シミュレーションし、Benjamini-Hochberg (BH) アルゴリズムの実際の性能と密接な関係を示す。
  論文  参考訳（メタデータ） (2020-05-07T19:59:51Z)
• Distributionally Robust Bayesian Quadrature Optimization [60.383252534861136]
  確率分布が未知な分布の不確実性の下でBQOについて検討する。 標準的なBQOアプローチは、固定されたサンプル集合が与えられたときの真の期待目標のモンテカルロ推定を最大化する。 この目的のために,新しい後方サンプリングに基づくアルゴリズム,すなわち分布的に堅牢なBQO(DRBQO)を提案する。
  論文  参考訳（メタデータ） (2020-01-19T12:00:33Z)

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

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