論文の概要: Learning Lotteries with Minimal Stakeholder Violations from Membership Queries

• arxiv url: http://arxiv.org/abs/2610.37828v1
• Date: Tue, 27 Oct 2026 18:40:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-31 05:25:12.314555
• Title: Learning Lotteries with Minimal Stakeholder Violations from Membership Queries
• Title（参考訳）: メンバーシップ・クエリーから最小のステークホルダー・バイオレーションによるロテリの学習
• Abstract要約: AI開発者は、しばしばシステムのいくつかの候補バージョンを持っている。 各利害関係者は、期待されるパフォーマンスが自身の標準を満たす場合に正確に混合を受け付ける。 この問題は、すべてのハーフスペースが知られている場合でもAPXハードであることが示される。
• 参考スコア（独自算出の注目度）: 11.780724567890303
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: An AI developer often has several candidate versions of a system and can deploy a mixture of them, sending each request to a randomly chosen version, as in A/B testing. Each stakeholder (e.g., a safety team, a regulator, or a customer with private test data) accepts a mixture exactly when its expected performance (e.g., its rate of harmful replies) meets the stakeholder's own standard, which the developer can learn only by asking whether a proposed mixture is acceptable. We model this as choosing a lottery over $m$ alternatives for $n$ agents, each of whom accepts exactly the lotteries in an unknown halfspace and answers such binary membership queries. While Choo et al. (ICML 2026) sought a lottery that every agent accepts, none may exist when, say, safety and helpfulness requirements conflict, so we minimize the number of rejecting agents. We show that this problem is APX-hard even when all halfspaces are known and all utilities are $0$ or $1$. We then give exact algorithms that run in polynomial time when $m$ is constant, and in quasi-polynomial time when, for a constant $η$, some optimal lottery has no accepting agent within $η$ of its threshold. When only some agents can be queried, optimizing over a uniform sample of agents gives additive and relative guarantees for the whole population, with a sample size that does not depend on $n$, and a linear program gives a polynomial-time method for any $m$. On the other hand, for $m\ge 3$, a deterministic algorithm that queries only $K$ distinct agents cannot guarantee fewer than $n-K$ extra rejections, and this is achievable; in other words, it can guarantee nothing for the agents it does not ask. Small synthetic experiments indicate that our worst-case bounds are conservative on random instances.
• Abstract（参考訳）: AI開発者は、しばしばシステムのいくつかの候補バージョンを持ち、それらを混合してデプロイし、A/Bテストのように、ランダムに選択されたバージョンに各リクエストを送信することができる。 各利害関係者(例えば、安全チーム、規制当局、またはプライベートテストデータを持つ顧客)は、期待性能(例えば、有害な応答率)が利害関係者自身の基準を満たした場合に正確に混合を受け付け、開発者は、提案された混合が許容されるかどうかを問うだけで学べる。 私たちはこれを$m$の代わりに$n$エージェントを選択するようにモデル化し、それぞれが未知のハーフスペース内の抽選を正確に受け入れ、そのようなバイナリメンバシップクエリに答えます。 Choo et al (ICML 2026) は、すべてのエージェントが受け入れる宝くじを求めたが、例えば安全性と有用性の要件が相反する場合には、存在しないため、拒否するエージェントの数が最小になる。 すべてのハーフスペースが知られ、すべてのユーティリティが0ドルまたは1ドルである場合でも、この問題はAPXハードであることを示す。 すると、$m$が定数の多項式時間で実行され、準多項式時間において、定数$η$に対して、ある最適な宝くじはそのしきい値の$η$の範囲内で受容エージェントを持たないとき、正確なアルゴリズムを与える。 いくつかのエージェントのみをクエリできる場合、一様のエージェントのサンプルを最適化することで、サンプルのサイズは$n$に依存しないため、全集団に対して加法的および相対的な保証を与え、線形プログラムは任意の$m$に対して多項式時間法を与える。 一方、$m\ge 3$の場合、異なるエージェントのみをクエリする決定論的アルゴリズムは、$n-K$余分な拒絶を保証できない。 小さな合成実験は、最悪のケース境界がランダムなインスタンスでは保守的であることを示している。

関連論文リスト

• AI Research Preference Models [87.14303218008381]
  研究エージェントは、独自の機械学習実験を提案し、実装し、評価することができる。 フロンティア作業の進行は コストで妨げられています 我々は、複数の候補ソリューションのどれが実行価値が最も高いかを予測するAI Research Preference Models(RPM)を紹介する。
  論文  参考訳（メタデータ） (2026-08-14T04:20:37Z)
• Probe-then-Commit Multi-Objective Bandits: Theoretical Benefits of Limited Multi-Arm Feedback [2.1772197319352498]
  マルチラジオアクセス選択とモバイルエッジコンピューティングのオフロードによるオンラインリソース選択問題について検討する。 各ラウンドでエージェントは、$d$-dimensionalベクターのパフォーマンスを持つ$K$候補リンク/サーバを選択する。 我々は、楽観的なプローブ-then-commitアルゴリズムであるtextscPtC-P-UCB を開発した。
  論文  参考訳（メタデータ） (2026-02-03T06:44:00Z)
• Batched Stochastic Matching Bandits [43.651070266360954]
  本稿では,MNL選択モデルに基づくマッチングのための新しい帯域幅フレームワークを提案する。 私たちの設定では、一方の$N$エージェントは他方の$K$アームに割り当てられます。 目的は、すべてのエージェントで成功した試合から累積収入を最大化することで、後悔を最小限に抑えることである。
  論文  参考訳（メタデータ） (2025-09-04T13:16:32Z)
• Online Fair Division for Personalized $2$-Value Instances [51.278096593080456]
  オンラインフェアディビジョン(オンラインフェアディビジョン)では,商品が一度に1つずつ到着し,定額のエージェントが配置されている。 善が現れると、各エージェントの持つ値が明らかになり、エージェントの1つに即時かつ不可逆的に割り当てられなければならない。 我々は、よく知られた公平性の概念に関して、最悪の場合の保証を得る方法を示す。
  論文  参考訳（メタデータ） (2025-05-28T09:48:16Z)
• Cooperative Multi-Agent Constrained Stochastic Linear Bandits [2.099922236065961]
  N$エージェントのネットワークがローカルに通信し、期待されるコストを所定の閾値$tau$で保持しながら、全体的な後悔を最小限に抑える。 我々は、textitMA-OPLBと呼ばれる安全な分散上信頼度有界アルゴリズムを提案し、そのT$ラウンドの後悔に基づく高い確率を確立する。 我々の後悔の限界は次数$ MathcalOleft(fracdtau-c_0fraclog(NT)2sqrtNsqrtTlog (1/|lambda|)であることを示す。
  論文  参考訳（メタデータ） (2024-10-22T19:34:53Z)
• Federated Combinatorial Multi-Agent Multi-Armed Bandits [79.1700188160944]
  本稿では,Banditを用いたオンライン最適化に適したフェデレーション学習フレームワークを提案する。 この設定では、エージェントのアームサブセットは、個々のアーム情報にアクセスせずにこれらのサブセットに対するノイズの多い報酬を観察し、特定の間隔で協力して情報を共有することができる。
  論文  参考訳（メタデータ） (2024-05-09T17:40:09Z)
• Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
  確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。 トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
  論文  参考訳（メタデータ） (2023-03-30T02:51:00Z)
• Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits [81.60136088841948]
  本稿では,時間軸における後悔を最小限に抑えるアルゴリズムを提案する。 提案アルゴリズムは,レコメンデーションシステムや交通機関などの分野に適用可能である。
  論文  参考訳（メタデータ） (2023-01-31T03:49:00Z)

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

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