論文の概要: 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（参考訳）: 無限大のバンディット問題では、各アームの平均報酬は未知の分布からサンプリングされ、さらに各アームをサンプリングすることで、そのアームの平均報酬のノイズ推定が得られる。 先行研究は、最高の腕、すなわち平均報酬分布の最大値を推定することに焦点を当てている。 本稿では,最大値を超える分布関数の一般クラスを考察し,オフラインとオンラインの両方に統一されたメタアルゴリズムを提案する。 学習者が新しいアームや既存のアームのサンプルを順次選択できるオンライン推定では、平均機能の推定にオフライン設定よりも有利な点はないが、中央値、最大値、トリミング平均などの他の機能ではサンプルの複雑さが著しく減少する。 一致する下限はいくつかの異なるワッサースタイン距離を利用する。 中央値推定の特別な場合について,ガウス畳み込みと独立な関心を持つであろう雑音レベルとの区別可能性について,好奇心をそそるしきい値化現象を同定する。

関連論文リスト

• Continuous K-Max Bandits [54.21533414838677]
  我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。 この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。 我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
  論文  参考訳（メタデータ） (2025-02-19T06:37:37Z)
• Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
  我々は、各アームが選択時にM$Dのベクトル報酬を得られる多腕バンディット設定を考える。 最終的なゴールは、最も短い(予想される)時間において、エラーの確率の上限に従属する全ての目的の最良のアームを特定することである。 本稿では,各ステップでアームをサンプリングするために,エミュロゲート比例という新しいアイデアを用いたアルゴリズムを提案し,各ステップにおける最大最小最適化問題を解く必要をなくした。
  論文  参考訳（メタデータ） (2025-01-23T12:28:09Z)
• Minimax Optimal Simple Regret in Two-Armed Best-Arm Identification [10.470114319701576]
  簡単な後悔に対して、ネーマン割当の極小極小性を証明した。 局所正規度に局所性制限を課すことなく、最適性が達成できることが示される。
  論文  参考訳（メタデータ） (2024-12-23T18:06:20Z)
• 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.362793507416177]
  カーネルをベースとした近傍の分布一般化を導入し,その基礎となる分布を推定する。 2つ以上の測定値にアクセスできれば, 近接するアプローチがヘテロセシダスティックノイズに対して堅牢であることを示す。
  論文  参考訳（メタデータ） (2024-10-17T09:36:01Z)
• 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)
• Mean-based Best Arm Identification in Stochastic Bandits under Reward Contamination [80.53485617514707]
  本稿では,ギャップベースアルゴリズムと逐次除去に基づく2つのアルゴリズムを提案する。 具体的には、ギャップベースのアルゴリズムでは、サンプルの複雑さは定数要素まで最適であり、連続的な除去では対数因子まで最適である。
  論文  参考訳（メタデータ） (2021-11-14T21:49:58Z)

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

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