論文の概要: Learning Unanimously Acceptable Lotteries via Queries

• arxiv url: http://arxiv.org/abs/2604.17505v1
• Date: Sun, 19 Apr 2026 15:51:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-21 21:52:52.561203
• Title: Learning Unanimously Acceptable Lotteries via Queries
• Title（参考訳）: 総体的に受け入れられるロテリをクエリーで学ぶ
• Authors: Davin Choo, Paul W. Goldberg, Nicholas Teh,
• Abstract要約: 本稿では,アルゴリズムが宝くじを提案し,二進的アセプション/リジェクトフィードバックのみを受信するクエリモデルについて検討する。 決定論的かつランダムなアルゴリズムは、全会一致で許容される宝くじを見つけたり、実現不可能性を証明したりする。 我々は、自然形態のアドバイスを利用する学習強化アルゴリズムを開発した。
• 参考スコア（独自算出の注目度）: 17.857261852690346
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Many high-stakes AI deployments proceed only if every stakeholder deems the system acceptable relative to their own minimum standard. With randomization over a finite menu of options, this becomes a feasibility question: does there exist a lottery over options that clears all stakeholders' acceptability bars? We study a query model where the algorithm proposes lotteries and receives only binary accept/reject feedback. We give deterministic and randomized algorithms that either find a unanimously acceptable lottery or certify infeasibility; adaptivity can avoid eliciting many stakeholders' constraints, and randomization further reduces the expected elicitation cost relative to full elicitation. We complement these upper bounds with worst-case lower bounds (in particular, linear dependence on the number of stakeholders and logarithmic dependence on precision are unavoidable). Finally, we develop learning-augmented algorithms that exploit natural forms of advice (e.g., likely binding stakeholders or a promising lottery), improving query complexity when predictions are accurate while preserving worst-case guarantees.
• Abstract（参考訳）: 多くの高度なAIデプロイメントは、すべてのステークホルダーが自身の最小限の基準に対してシステムを許容できるとみなす場合にのみ実行される。 オプションの有限メニューをランダムにすると、これは実現可能な問題になる: すべてのステークホルダーの受け入れバーをクリアするオプションに対して、宝くじがあるだろうか? 本稿では,アルゴリズムが宝くじを提案し,二進的アセプション/リジェクトフィードバックのみを受信するクエリモデルについて検討する。 適応性は、多くの利害関係者の制約を課すことを回避し、ランダム化は、完全な利害関係者に対して期待される利息コストをさらに削減する。 特に利害関係者数への線形依存と精度への対数依存は避けられない)。 最後に、自然形態のアドバイス(例えば、バインディング利害関係者や有望な宝くじ)を活用する学習強化アルゴリズムを開発し、最悪の保証を保ちながら予測が正確である場合のクエリ複雑性を改善する。

関連論文リスト

• Consistency of Selection Strategies for Fraud Detection [0.0]
  我々は、保険業者が詐欺を捜査する主張をどう選ぶかを研究する。 これは一貫性のない学習につながる可能性があり、ランダムな代替案を提案する。
  論文  参考訳（メタデータ） (2025-09-23T07:33:33Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• High-Dimensional Prediction for Sequential Decision Making [9.684829814477526]
  本研究では,任意の条件付けイベントの収集対象である逆選択された高次元状態の予測を行う問題について検討する。 この問題を解決するための効率的なアルゴリズムと、適切な条件付けイベントを選択することに起因する多くのアプリケーションを提供します。
  論文  参考訳（メタデータ） (2023-10-26T17:59:32Z)
• High-Probability Risk Bounds via Sequential Predictors [20.741036493022442]
  一般的なオンライン学習アルゴリズムに適用されたオンラインからバッチへの変換は、後悔の限界を回避できることを示す。 いくつかの古典的統計的推定問題に対して、ほぼ最適な高確率リスク境界を得る。 我々の分析は、多くのオンライン学習アルゴリズムが不適切であるという事実に依存している。
  論文  参考訳（メタデータ） (2023-08-15T06:19:31Z)
• Agnostic Multi-Robust Learning Using ERM [19.313739782029185]
  頑健な学習における根本的な問題は非対称性である: 学習者は指数関数的に多くの摂動の全てを正しく分類する必要がある。 これとは対照的に、攻撃者は1つの摂動を成功させる必要がある。 本稿では,新しいマルチグループ設定を導入し,新しいマルチロバスト学習問題を提案する。
  論文  参考訳（メタデータ） (2023-03-15T21:30:14Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。 我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。 また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-21T00:17:24Z)
• Root-finding Approaches for Computing Conformal Prediction Set [18.405645120971496]
  共形予測は、以前の同一分布および交換可能な観測に基づいて、特徴ベクトルの未観測応答に対する信頼領域を構築する。 我々は,共形予測集合が古典的ルートフィンディングソフトウェアによって効率的に近似できる区間であるという事実を活用する。
  論文  参考訳（メタデータ） (2021-04-14T06:41:12Z)
• Batched Neural Bandits [107.5072688105936]
  BatchNeuralUCBはニューラルネットワークと楽観性を組み合わせ、探索と探索のトレードオフに対処する。 BatchNeuralUCBは、完全なシーケンシャルバージョンと同じ後悔を達成しつつ、ポリシー更新の数を大幅に減らしています。
  論文  参考訳（メタデータ） (2021-02-25T17:36:44Z)
• Adaptive Combinatorial Allocation [77.86290991564829]
  割り当てが繰り返し選択され、戻り値は不明だが学習可能であり、決定には制約が伴う。 我々のモデルは、複雑な制約があっても、両側のマッチングと一方のマッチングをカバーしています。
  論文  参考訳（メタデータ） (2020-11-04T15:02:59Z)
• Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
  平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。 我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
  論文  参考訳（メタデータ） (2020-03-05T21:29:27Z)

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

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