論文の概要: How Much Does Correctness Cost? Budgeted Placement of Strong Correctors in a Weak Multi-Agent Swarm
- arxiv url: http://arxiv.org/abs/2607.09765v1
- Date: Tue, 07 Jul 2026 05:48:17 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-14 15:40:48.184752
- Title: How Much Does Correctness Cost? Budgeted Placement of Strong Correctors in a Weak Multi-Agent Swarm
- Title（参考訳）: 矯正費はいくらか? 弱いマルチエージェントの群れに強い矯正具を埋め込む
- Abstract要約: 信頼性の低いエージェントの安価な群れは、強力で高価な「オークル」修正器によって正しいコンセンサスに導かれる。
私たちは、どのくらいの費用を使わなければならないのか、そしてオラクルをどこに置けばよいのかを尋ねます。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A cheap swarm of unreliable agents can be steered to a correct consensus by a few strong, expensive "oracle" correctors. We ask how much one must spend, and where to place the oracles. We model the swarm as a consensus on a graph in which each oracle pins one node toward the truth at a cost-coupled, concave strength, and measure quality by the coherence H(R)=tr M(R)^{-1}. Our first result is that H stays submodular (each added oracle helps less than the last) even when the oracles differ in strength, so a cost-benefit greedy comes within 1-1/e of the best placement at any budget. Inverting the budget gives the budget-correctness frontier B*(eps), the least spend that guarantees an eps-correct consensus: closed-form on the complete graph, and a minimal oracle count k* when oracles cost the same. Whether a budget then buys a few strong oracles or many medium onese curvature of the cost-quality law: diminishing returns favour spreadsharply increasion. Measured onthe Qwen3 ladder (0.6-32B), the law is concave for math verificatio convex foremergent code tracing, so the verdict is genuinely task-dependent.https://github.com/YehudaItkin/budgeted-oracle-placemen
- Abstract（参考訳）: 信頼性の低いエージェントの安価な群れは、強力で高価な「オークル」修正器によって正しいコンセンサスに導かれる。
私たちは、どのくらいの費用を使わなければならないのか、そしてオラクルをどこに置けばよいのかを尋ねます。
我々は、スワムを1つのノードをコスト結合で真理に向かってピンするグラフ上のコンセンサスとしてモデル化し、コヒーレンス H(R)=tr M(R)^{-1} で品質を測定する。
我々の第一の結果は、H が部分モジュラー(各付加オラクルは、強度の相違があっても、最後より小さい)であるため、費用対効果の欲求は、どの予算でも最良配置の 1-1/e 以内である。
予算の反転は予算補正フロンティア B*(eps) を与えるが、これは eps-correct consensus を保証する最小の費用である。
予算がその後、いくつかの強いオークルを購入するか、あるいはコスト品質の法則の多くの中核的な曲率を購入するかのどちらかである。
Qwen3 ladder (0.6-32B) 上で測定されたこの法則は、数学の検証凸の前処理コードトレースのための凹凸であるので、判定は真にタスク依存である。
関連論文リスト
- Minimax Alternating Regret for the Experts Problem and Online Convex Optimization [13.08870048693199]
ミニマックスの交互後悔は地平線から独立して$(log d)$であることを示す。
さらに、この結果を$d$次元コンパクト凸集合上で一般のOCOに拡張する。
論文 参考訳（メタデータ） (2026-08-25T21:56:20Z) - Top-$k$ Pareto Bandits: Hypervolume Regret for Multi-Objective Slate Selection [48.83076933238825]
我々は,各ラウンドにおいてエージェントが$k$アームのスレートを選択し,それらの$d$次元報酬ベクトルを半帯域フィードバック下で観察する多目的バンディット問題を考える。
この目的を、選択されたアームのサブセットによって誘導される支配的な超体積を通して定式化し、最高のサイズに対して$$$-approximate hypervolume regretを定義する。
ギャップのない後悔境界を持つ$tildeO(dsqrtnkT)$を、ギャップとともにすべてのインスタンスに保持する。
論文 参考訳（メタデータ） (2026-07-28T21:10:39Z) - Fundamental Limitations of Fixed-Budget Best-Arm Identification [0.0]
固定予算のベストアーム識別では、ランキングとセレクションとしても知られ、アルゴリズムはK$アームに分散するサンプリング予算を持つ。
任意のアルゴリズムに対して、誤差崩壊率が静的オラクルの少なくとも$left(+ fraclog(K)8right)-1$である少なくとも1つの例が存在することを示す。
論文 参考訳（メタデータ） (2026-07-13T14:50:32Z) - Instance-Optimal Estimation with Multiple LLM Judges on a Budget [84.31744861038106]
我々は、この問題を*予算付きヘテロスケダティックなマルチジャッジ推定*として定式化する。
K$のプロンプト-レスポンスペア、J$の既知のコストと未知のクエリ-ジャッジ分散が与えられた場合、目標は、$ell_p$-errorを最小化しながら、有界スコアベクトルを推定することである。
EST-IVWEは,予算の低次項までのオラクルIVWEレートと一致していることを示す。
論文 参考訳（メタデータ） (2026-05-22T08:26:08Z) - Top-k on a Budget: Adaptive Ranking with Weak and Strong Oracles [2.233624388203003]
ACEは、重要な境界項目に対する強力なクエリに焦点を当てた適応的な認証アルゴリズムである。
次に、ACEを実行する前に、弱い予算を適応的に割り当てる完全適応型2相法であるACE-Wを紹介する。
論文 参考訳（メタデータ） (2026-01-28T19:41:37Z) - Gradient-Free Approaches is a Key to an Efficient Interaction with Markovian Stochasticity [80.65200796386168]
このような問題を解決するための新しい微分自由法を提案し,解析する。
基礎となる雑音列の混合時間$$が問題の次元$d$より小さい場合、我々の手法の収束推定は$$に依存しないことを示す。
論文 参考訳（メタデータ） (2026-01-03T11:27:07Z) - Oracle-Efficient Combinatorial Semi-Bandits [38.838934613131535]
エージェントがベースアームのサブセットを選択し、個別のフィードバックを受け取るという半帯域問題について検討する。
我々は,厳格な後悔の保証を維持しつつ,オラクル呼び出しを大幅に削減するオラクル効率の高いフレームワークを提案する。
論文 参考訳（メタデータ） (2025-10-24T13:07:08Z) - A New Benchmark for Online Learning with Budget-Balancing Constraints [14.818946657685267]
本稿では,オートバイディングなどの実世界の応用と,その基礎となる数学的構造を比較対象とする新しいベンチマークを提案する。
サブリニアな消費パターンが$o(T2)$以内である戦略に対して,サブリニアな後悔は達成可能であることを示す。
論文 参考訳（メタデータ） (2025-03-19T00:14:20Z) - Computational Lower Bounds for Regret Minimization in Normal-Form Games [68.66209476382213]
乗算重み更新などの既存の学習アルゴリズムが最適に近いことを示す。
結果はKothari と Mehta が提案したアルゴリズムの枠組みで得られた。
論文 参考訳（メタデータ） (2024-11-04T00:39:52Z) - The Hardness Analysis of Thompson Sampling for Combinatorial
Semi-bandits with Greedy Oracle [16.50998008977657]
トンプソンサンプリング(TS)は、バンディット地域に多くの関心を集めている。
1930年代に導入されたが、理論上は近年まで証明されていない。
論文 参考訳（メタデータ） (2021-11-08T06:40:03Z) - Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
論文 参考訳（メタデータ） (2021-10-25T02:53:24Z) - Towards Minimax Optimal Best Arm Identification in Linear Bandits [95.22854522340938]
固定予算設定における線形包帯における最適な腕識別の問題について検討する。
G-最適設計の特性を活用し、アーム割り当て規則に組み込むことにより、パラメータフリーなアルゴリズムを設計する。
OD-LinBAIの故障確率に関する理論的解析を行った。
論文 参考訳（メタデータ） (2021-05-27T09:19:10Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Budget-Constrained Bandits over General Cost and Reward Distributions [32.63624728528415]
我々は,各アームがランダムなコストを発生させ,その見返りにランダムな報酬を与える,予算制約付きバンディット問題を考える。
ある$gamma > 0$ に対して位数 $(2+gamma)$ のモーメントが存在するならば、$O(log B)$ regret は予算 $B>0$ に対して達成可能である。
論文 参考訳（メタデータ） (2020-02-29T23:50:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。