論文の概要: Beyond the Best: Estimating Distribution Functionals in Infinite-Armed Bandits

• arxiv url: http://arxiv.org/abs/2211.01743v1
• Date: Tue, 1 Nov 2022 18:20:10 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-04 13:09:23.735548
• Title: Beyond the Best: Estimating Distribution Functionals in Infinite-Armed Bandits
• Title（参考訳）: ベストを超えて:無限配列帯域における分布関数の推定
• Authors: Yifei Wang, Tavor Baharav, Yanjun Han, Jiantao Jiao, David Tse
• Abstract要約: 無限武装バンディット問題では、各アームの平均報酬は未知の分布からサンプリングされる。 我々は、最大以上の分布関数の一般的なクラスを検討し、オフラインとオンラインの両方で統一されたメタアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 40.71199236098642
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the infinite-armed bandit problem, each arm's average reward is sampled from an unknown distribution, and each arm can be sampled further to obtain noisy estimates of the average reward of that arm. Prior work focuses on identifying the best arm, i.e., estimating the maximum of the average reward distribution. We consider a general class of distribution functionals beyond the maximum, and propose unified meta algorithms for both the offline and online settings, achieving optimal sample complexities. We show that online estimation, where the learner can sequentially choose whether to sample a new or existing arm, offers no advantage over the offline setting for estimating the mean functional, but significantly reduces the sample complexity for other functionals such as the median, maximum, and trimmed mean. The matching lower bounds utilize several different Wasserstein distances. For the special case of median estimation, we identify a curious thresholding phenomenon on the indistinguishability between Gaussian convolutions with respect to the noise level, which may be of independent interest.
• Abstract（参考訳）: 無限大のバンディット問題では、各アームの平均報酬は未知の分布からサンプリングされ、さらに各アームをサンプリングすることで、そのアームの平均報酬のノイズ推定が得られる。 先行研究は、最高の腕、すなわち平均報酬分布の最大値を推定することに焦点を当てている。 本稿では,最大値を超える分布関数の一般クラスを考察し,オフラインとオンラインの両方に統一されたメタアルゴリズムを提案する。 学習者が新しいアームや既存のアームのサンプルを順次選択できるオンライン推定では、平均機能の推定にオフライン設定よりも有利な点はないが、中央値、最大値、トリミング平均などの他の機能ではサンプルの複雑さが著しく減少する。 一致する下限はいくつかの異なるワッサースタイン距離を利用する。 中央値推定の特別な場合について,ガウス畳み込みと独立な関心を持つであろう雑音レベルとの区別可能性について,好奇心をそそるしきい値化現象を同定する。

関連論文リスト

• Reward Maximization for Pure Exploration: Minimax Optimal Good Arm Identification for Nonparametric Multi-Armed Bandits [35.35226227009685]
  グッドアーム識別(グッドアームアイソレーション、英: Good Arm Identification、IGA)は、腕をできるだけ早くしきい値以上の手段でラベル付けすることを目的とした、実用的なバンドイット推論の目的である。 本稿では,報奨最大化サンプリングアルゴリズムと新たな非有意シーケンシャルテストを組み合わせることで,GAを効率よく解くことができることを示す。 我々の実験結果は、ミニマックス設定を超えるアプローチを検証し、すべての停止時間におけるサンプルの期待数を、合成および実世界の設定で少なくとも50%削減する。
  論文  参考訳（メタデータ） (2024-10-21T01:19:23Z)
• Learning Counterfactual Distributions via Kernel Nearest Neighbors [8.971989179518216]
  カーネルをベースとした近傍の分布一般化を導入し,その基礎となる分布を推定する。 2つ以上の測定値にアクセスできれば, 近接するアプローチがヘテロセシダスティックノイズに対して堅牢であることを示す。
  論文  参考訳（メタデータ） (2024-10-17T09:36:01Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Pure Exploration under Mediators' Feedback [63.56002444692792]
  マルチアームバンディット(Multi-armed bandits)は、各インタラクションステップにおいて、学習者が腕を選択し、報酬を観察する、シーケンシャルな意思決定フレームワークである。 本稿では,学習者が仲介者の集合にアクセスできるシナリオについて考察する。 本稿では,学習者には仲介者の方針が知られていると仮定して,最適な腕を発見するための逐次的意思決定戦略を提案する。
  論文  参考訳（メタデータ） (2023-08-29T18:18:21Z)
• Best Arm Identification in Bandits with Limited Precision Sampling [14.011731120150124]
  学習者が腕選択の精度に限界がある多腕バンディット問題の変種における最適な腕識別について検討する。 非特異な最適アロケーションを処理するために,修正されたトラッキングベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-05-10T12:07:48Z)
• Federated Best Arm Identification with Heterogeneous Clients [62.36929749450298]
  中央サーバと複数のクライアントを備えた多腕バンディット・セッティングにおける腕の識別について検討した。 予測停止時間上の上限が乗算定数までの下限と一致するアルゴリズム(ほぼ最適アルゴリズムの場合)について示す。 本稿では,指数時間瞬間に通信する新しいアルゴリズムを提案し,ほぼ最適であることを実証する。
  論文  参考訳（メタデータ） (2022-10-14T13:09:11Z)
• Semiparametric Best Arm Identification with Contextual Information [10.915684166086026]
  バンディット問題において,固定予算と文脈情報を用いたベストアーム識別について検討した。 本研究では,ターゲットアロケーション比とレコメンデーションルールを追跡するランダムサンプリングルールとからなる「コンテキストRS-AIPW戦略」を開発する。 提案手法は,予算が無限に進むと,誤識別確率の上限が半下限と一致するため,最適である。
  論文  参考訳（メタデータ） (2022-09-15T14:38:47Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)

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

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