論文の概要: SHPRR: An Algorithm for Pure Exploration under Constrained Regret

• arxiv url: http://arxiv.org/abs/2610.39837v1
• Date: Thu, 29 Oct 2026 11:15:57 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-31 05:25:12.496656
• Title: SHPRR: An Algorithm for Pure Exploration under Constrained Regret
• Title（参考訳）: SHPRR:制約付き回帰の下での純探索アルゴリズム
• Abstract要約: BAI(Best Arm Identification)は、通常、収集されたサンプルの数によって実験のコストを測定する。 固定サンプリングの地平線と後悔の予算の下で,BAIについて検討する。 理論的には, シークエンシャル・ハルヴィングの段階にわたって, 探索の後悔のコストが減少することを示す。
• 参考スコア（独自算出の注目度）: 5.490340617337839
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Best Arm Identification (BAI) conventionally measures the cost of experimentation by the number of samples collected. In many operational settings, however, the cost of exploration relative to a trusted baseline already in place is equally important. We study BAI under both a fixed sampling horizon and a regret budget. Unlike generic resources considered in constrained pure exploration, regret has a distinctive structure: sampling better arms is less costly relative to the baseline. We theoretically show that the regret cost of exploration decreases across the phases of Sequential Halving, a widely used pure-exploration algorithm. This observation yields improved guarantees on the probability of identifying the best arm and motivates a more effective allocation of the regret budget. We propose Sequential Halving with Proportional Regret Rationing (SHPRR), which front-loads the regret budget to allow more exploration when many arms remain. Experiments on synthetic and real-world instances show that SHPRR improves best-arm identification performance over uniform regret allocation and existing baselines.
• Abstract（参考訳）: BAI(Best Arm Identification)は、通常、収集されたサンプルの数によって実験のコストを測定する。 しかし、多くの運用環境では、既に存在する信頼されたベースラインに対する探査コストも同様に重要である。 我々は,固定サンプリング地平線と後悔の予算の下で,BAIについて検討する。 制約された純粋な探査で考慮された一般的な資源とは異なり、後悔は独特な構造を持つ。 理論的には、探索の後悔のコストはシークエンシャル・ハルヴィング(Sequential Halving)の段階にわたって減少する。 この観察により、最高の腕を特定する確率が向上し、後悔の予算をより効果的に割り当てる動機となる。 我々は,多くの武器が残されている場合のさらなる探索を可能にするために,遺書予算を最前線に積載する,逐次Halving with Proportional Regret Rationing (SHPRR)を提案する。 合成および実世界のインスタンスに対する実験により、SHPRRは、一様後悔の割り当てや既存のベースラインよりも、最高の武器識別性能を向上させることが示された。

関連論文リスト

• On the Benefits of Free Exploration for Regret Minimization in Multi-Armed Bandits [54.384522012368556]
  我々は,後悔が蓄積する前に,エージェントに自由な探査予算が与えられる,多武装の盗賊問題について検討する。 我々は、この後悔の最小化を自由探索問題で定式化し、自由探査予算が時間軸と対数的にスケールする興味深い体制を特定する。 本稿では,二相保存アルゴリズムUFE-KLUCB-Hを提案する。
  論文  参考訳（メタデータ） (2026-05-25T12:36:43Z)
• Delightful Exploration [1.1886634182318419]
  textitDelight-gated Explorion (DE) はホストオーバーライドのルールで、探索的な行動に費やすのは彼らの期待がゲート価格を超える場合に限られる。 この実践によって古典的な結果が回復する:Pandoraの高価な検索のための予約値ルール。
  論文  参考訳（メタデータ） (2026-05-13T10:03:11Z)
• Cost-Ordered Feasibility for Multi-Armed Bandits with Cost Subsidy [17.48220873982007]
  応用において、目標は最小限の許容報酬(MAB-CS)の制約を受けるコストを最小限にすることである。 我々は、インスタンス依存の下位境界を証明することによって、任意のポリシーで要求される期待される準最適サンプルを特徴づける。 そこで我々は,安価なアームの実用性を評価するために,すべてのアームのサンプルをインテリジェントに組み合わせたコストオーダーフィジビリティ(COF)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-05-08T03:07:25Z)
• Cost-Aware Optimal Pairwise Pure Exploration [20.624054807637425]
  この研究は、純粋な探索を研究するための汎用的なフレームワークを導入し、標的となるアームペア間のペア関係を特定することに重点を置いている。 アーム固有のコストでペアで純粋な探索を行う一般的な枠組みの下では、性能の低い境界が導出される。 CAET(Cost-Aware Pairwise Exploration Task)と呼ばれる新しいアルゴリズムが提案されている。
  論文  参考訳（メタデータ） (2025-03-10T21:50:35Z)
• Diminishing Exploration: A Minimalist Approach to Piecewise Stationary Multi-Armed Bandits [17.02018075805672]
  片側定常バンドイット問題は、報酬分布の急激な変化を考察する。 既存のアルゴリズムは、変化点の数に関する知識を$M$とするか、非常に高い計算複雑性を必要とする。 そこで本研究では,MM$に関する知識の必要をなくす,減少探索と呼ばれる新奇で汎用的な探索機構を提案する。
  論文  参考訳（メタデータ） (2024-10-08T06:51:32Z)
• 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)
• 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)

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

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