論文の概要: Cost-Aware Optimal Pairwise Pure Exploration

• arxiv url: http://arxiv.org/abs/2503.07877v1
• Date: Mon, 10 Mar 2025 21:50:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-12 15:45:02.748186
• Title: Cost-Aware Optimal Pairwise Pure Exploration
• Title（参考訳）: コストを考慮した最適ペアワイド純粋探索
• Authors: Di Wu, Chengshuai Shi, Ruida Zhou, Cong Shen,
• Abstract要約: この研究は、純粋な探索を研究するための汎用的なフレームワークを導入し、標的となるアームペア間のペア関係を特定することに重点を置いている。 アーム固有のコストでペアで純粋な探索を行う一般的な枠組みの下では、性能の低い境界が導出される。 CAET(Cost-Aware Pairwise Exploration Task)と呼ばれる新しいアルゴリズムが提案されている。
• 参考スコア（独自算出の注目度）: 20.624054807637425
• License:
• Abstract: Pure exploration is one of the fundamental problems in multi-armed bandits (MAB). However, existing works mostly focus on specific pure exploration tasks, without a holistic view of the general pure exploration problem. This work fills this gap by introducing a versatile framework to study pure exploration, with a focus on identifying the pairwise relationships between targeted arm pairs. Moreover, unlike existing works that only optimize the stopping time (i.e., sample complexity), this work considers that arms are associated with potentially different costs and targets at optimizing the cumulative cost that occurred during learning. Under the general framework of pairwise pure exploration with arm-specific costs, a performance lower bound is derived. Then, a novel algorithm, termed CAET (Cost-Aware Pairwise Exploration Task), is proposed. CAET builds on the track-and-stop principle with a novel design to handle the arm-specific costs, which can potentially be zero and thus represent a very challenging case. Theoretical analyses prove that the performance of CAET approaches the lower bound asymptotically. Special cases are further discussed, including an extension to regret minimization, which is another major focus of MAB. The effectiveness and efficiency of CAET are also verified through experimental results under various settings.
• Abstract（参考訳）: 純粋な探査は、マルチアーム・バンディット(MAB)の基本的な問題の一つである。 しかし、既存の研究は主に特定の純粋な探査課題に焦点を合わせており、一般的な純粋な探査問題の全体像は見当たらない。 この研究は、純粋な探索を研究するために汎用的なフレームワークを導入することで、このギャップを埋める。 さらに、停止時間のみを最適化する既存の作業(例:サンプルの複雑さ)とは異なり、本研究は、学習中に発生した累積コストを最適化するために、アームが潜在的に異なるコストと目標に結びついていると考えている。 アーム固有のコストでペアで純粋な探索を行う一般的な枠組みの下では、性能の低い境界が導出される。 次に,CAET(Cost-Aware Pairwise Exploration Task)と呼ばれる新しいアルゴリズムを提案する。 CAETは、トラック・アンド・ストップの原則をベースとして、腕固有のコストを処理する新しい設計を採用しており、これはゼロになる可能性があり、非常に難しいケースだ。 理論的解析はCAETの性能が漸近的に下界に近づくことを証明している。 MABのもう一つの主要な焦点である、後悔の最小化の延長など、特別事例がさらに議論されている。 CAETの有効性と有効性も,様々な条件下で実験により検証した。

関連論文リスト

• Best Arm Identification with Minimal Regret [55.831935724659175]
  最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。 エージェントの目標は、所定の信頼度で最高の腕を特定することである。 二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
  論文  参考訳（メタデータ） (2024-09-27T16:46:02Z)
• Optimal Multi-Fidelity Best-Arm Identification [65.23078799972188]
  バンディットのベストアーム識別において、アルゴリズムは、できるだけ早く特定の精度で、最高平均報酬の腕を見つけることを任務とする。 マルチフィデリティのベストアーム識別について検討し、低コストで低いフィデリティ(正確な平均推定値を持たない)で腕をサンプリングすることを選択できる。 この問題に対処するためのいくつかの方法が提案されているが、その最適性は、特に最適な腕を特定するのに必要な総コストのゆるやかな下限のため、未解決のままである。
  論文  参考訳（メタデータ） (2024-06-05T08:02:40Z)
• Cost Aware Best Arm Identification [13.380383930882784]
  emphCost Aware Best Arm Identification (CABAI)と呼ぶ。 平方根規則に基づくemphChernoff Overlap (CO)と呼ばれる単純なアルゴリズムを提案する。 この結果から,不均一な動作コストを無視すると,実行時の準最適性が得られ,また,簡単なアルゴリズムにより,幅広い問題に対してほぼ最適性能が得られることがわかった。
  論文  参考訳（メタデータ） (2024-02-26T16:27:08Z)
• TrackFlow: Multi-Object Tracking with Normalizing Flows [36.86830078167583]
  トラッキング・バイ・ディテクトをマルチモーダル・セッティングに拡張することを目的としている。 3D情報の大まかな見積も利用可能であり、他の伝統的なメトリクスとマージする必要がある。 提案手法は,複数のトラッキング・バイ・検出アルゴリズムの性能を継続的に向上させる。
  論文  参考訳（メタデータ） (2023-08-22T15:40:03Z)
• ReAct: Temporal Action Detection with Relational Queries [84.76646044604055]
  本研究は,アクションクエリを備えたエンコーダ・デコーダフレームワークを用いて,時間的行動検出(TAD)の進展を図ることを目的とする。 まず,デコーダ内の関係注意機構を提案し,その関係に基づいてクエリ間の関心を誘導する。 最後に、高品質なクエリを区別するために、推論時に各アクションクエリのローカライズ品質を予測することを提案する。
  論文  参考訳（メタデータ） (2022-07-14T17:46:37Z)
• Multi-task Learning of Order-Consistent Causal Graphs [59.9575145128345]
  我々は、$K関連ガウス非巡回グラフ(DAG)の発見問題を考える。 マルチタスク学習環境下では, 線形構造方程式モデルを学習するためのMLE ($l_1/l$-regularized maximum chance estimator) を提案する。 理論的には、関係するタスクにまたがるデータを活用することで、因果順序を復元する際のサンプルの複雑さをより高めることができることを示す。
  論文  参考訳（メタデータ） (2021-11-03T22:10:18Z)
• Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Bandits [91.8283876874947]
  本稿では,BoBW-lil'UCB$(gamma)$アルゴリズムの設計と解析を行う。 i) RMとBAIの両方の目的に対して最適なアルゴリズムを同時に実行できないことを示す。 また、BoBW-lil'UCB$(gamma)$は、時間複雑性と後悔の点で競合よりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-10-16T17:52:32Z)
• Combinatorial Pure Exploration with Full-bandit Feedback and Beyond: Solving Combinatorial Optimization under Uncertainty with Limited Observation [70.41056265629815]
  最適化アルゴリズムを開発する際、エッジウェイトなどのパラメータが入力として正確に知られていることが一般的である。 本稿では、最近、限られたフィードバックを伴う純粋探索問題に対する手法について概説する。
  論文  参考訳（メタデータ） (2020-12-31T12:40:52Z)
• Present-Biased Optimization [8.775878711928591]
  論文は,akerlof (1991) が提唱した,時間的一貫性のない計画に関する人間の行動の様々な側面を研究する枠組みを拡張した。 その結果,現在偏りのあるエージェントが計算している解のコストと最適解のコストの比率は,問題制約によって大きく異なることがわかった。
  論文  参考訳（メタデータ） (2020-12-29T12:40:59Z)

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

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