論文の概要: Achieving PAC Guarantees in Mechanism Design through Multi-Armed Bandits

• arxiv url: http://arxiv.org/abs/2412.00345v2
• Date: Sun, 18 May 2025 09:37:48 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-20 17:08:51.735308
• Title: Achieving PAC Guarantees in Mechanism Design through Multi-Armed Bandits
• Title（参考訳）: マルチアーマッドバンドによる機構設計におけるPAC保証の達成
• Authors: Takayuki Osogami, Hirota Kinoshita, Segev Wasserkrug,
• Abstract要約: 自動機構設計のための線形プログラム(LP)に最適解のクラスを解析的に導出する。 これらの解は、元の定式化における変数の総数よりも指数関数的に小さい基本変数の集合を用いて表すことができる。 本稿では,この用語の評価をマルチアーム・バンディット(MAB)問題に翻訳することでこの問題に対処する。
• 参考スコア（独自算出の注目度）: 8.013444110633223
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We analytically derive a class of optimal solutions to a linear program (LP) for automated mechanism design that satisfies efficiency, incentive compatibility, strong budget balance (SBB), and individual rationality (IR), where SBB and IR are enforced in expectation. These solutions can be expressed using a set of essential variables whose cardinality is exponentially smaller than the total number of variables in the original formulation. However, evaluating a key term in the solutions requires exponentially many optimization steps as the number of players $N$ increases. We address this by translating the evaluation of this term into a multi-armed bandit (MAB) problem and develop a probably approximately correct (PAC) estimator with asymptotically optimal sample complexity. This MAB-based approach reduces the optimization complexity from exponential to $O(N\log N)$. Numerical experiments confirm that our method efficiently computes mechanisms with the target properties, scaling to problems with up to $N=128$ players -- substantially improving over prior work.
• Abstract（参考訳）: 我々は、効率、インセンティブの整合性、強い予算収支(SBB)、個人合理性(IR)を満たす自動メカニズム設計のための線形プログラム(LP)に対する最適解のクラスを解析的に導出した。 これらの解は、元の定式化における変数の総数よりも指数関数的に小さい基本変数の集合を用いて表すことができる。 しかし、ソリューションにおける重要な項を評価するには、プレイヤーの数が増加するにつれて指数関数的に多くの最適化ステップが必要となる。 本稿では,この用語の評価をマルチアーム・バンディット(MAB)問題に翻訳し,漸近的に最適なサンプル複雑性を持つほぼ正確なPAC推定器を開発することにより,この問題に対処する。 このMABベースのアプローチは、最適化の複雑さを指数関数から$O(N\log N)$に還元する。 数値実験により,提案手法は目標特性を持つ機構を効率的に計算し,最大128ドルのプレイヤーを持つ問題にスケールする。

関連論文リスト

• Stochastic Optimization with Optimal Importance Sampling [49.484190237840714]
  本稿では,両者の時間的分離を必要とせずに,意思決定とIS分布を共同で更新する反復型アルゴリズムを提案する。 本手法は,IS分布系に対する目的的,軽度な仮定の凸性の下で,最小の変数分散を達成し,大域収束を保証する。
  論文  参考訳（メタデータ） (2025-04-04T16:10:18Z)
• Global Optimization: A Machine Learning Approach [7.052596485478637]
  Bertsimas と Ozturk (2023) は、ブラックボックスのグローバル最適化問題を解決する方法として OCTHaGOn を提案した。 我々は、他のMIO表現可能なMLモデルを用いて、元の問題を近似することで、このアプローチの拡張を提供する。 多くの場合において、ソリューションの実現可能性と最適性の改善を示す。
  論文  参考訳（メタデータ） (2023-11-03T06:33:38Z)
• Sample-Efficient Multi-Agent RL: An Optimization Perspective [103.35353196535544]
  一般関数近似に基づく汎用マルコフゲーム(MG)のためのマルチエージェント強化学習(MARL)について検討した。 汎用MGに対するマルチエージェントデカップリング係数(MADC)と呼ばれる新しい複雑性尺度を導入する。 我々のアルゴリズムは既存の研究に匹敵するサブリニアな後悔を与えることを示す。
  論文  参考訳（メタデータ） (2023-10-10T01:39:04Z)
• An Optimization-based Deep Equilibrium Model for Hyperspectral Image Deconvolution with Convergence Guarantees [71.57324258813675]
  本稿では,ハイパースペクトル画像のデコンボリューション問題に対処する新しい手法を提案する。 新しい最適化問題を定式化し、学習可能な正規化器をニューラルネットワークの形で活用する。 導出した反復解法は、Deep Equilibriumフレームワーク内の不動点計算問題として表現される。
  論文  参考訳（メタデータ） (2023-06-10T08:25:16Z)
• Optimal Learning via Moderate Deviations Theory [4.6930976245638245]
  我々は、中等度偏差原理に基づくアプローチを用いて、高精度な信頼区間の体系的構築を開発する。 提案した信頼区間は,指数的精度,最小性,整合性,誤評価確率,結果整合性(UMA)特性の基準を満たすという意味で統計的に最適であることが示されている。
  論文  参考訳（メタデータ） (2023-05-23T19:57:57Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Runtime Analysis of Single- and Multi-Objective Evolutionary Algorithms for Chance Constrained Optimization Problems with Normally Distributed Random Variables [11.310502327308575]
  独立して通常は分散しているコンポーネントのシナリオについて研究する。 期待されるコストとその分散をトレードオフする問題を多目的に定式化する。 また,本手法は,木に散らばった最小限の問題に対して最適解の集合を計算するためにも有効であることを示す。
  論文  参考訳（メタデータ） (2021-09-13T09:24:23Z)
• Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
  高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。 我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。 また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
  論文  参考訳（メタデータ） (2021-07-02T16:21:52Z)
• Modeling the Second Player in Distributionally Robust Optimization [90.25995710696425]
  我々は、最悪のケース分布を特徴付けるために神経生成モデルを使うことを議論する。 このアプローチは多くの実装と最適化の課題をもたらします。 提案されたアプローチは、同等のベースラインよりも堅牢なモデルを生み出す。
  論文  参考訳（メタデータ） (2021-03-18T14:26:26Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。 この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。 我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
  論文  参考訳（メタデータ） (2021-02-16T06:04:27Z)
• Uncertainty aware Search Framework for Multi-Objective Bayesian Optimization with Constraints [44.25245545568633]
  高価な関数評価を用いた制約付きマルチオブジェクト(MO)ブラックボックス最適化の問題点を考察する。 本稿では,制約付き多目的最適化のための不確実性認識検索フレームワークを提案する。 UeMOCは最適化回路の探索に必要なシミュレーション数を90%以上削減できることを示す。
  論文  参考訳（メタデータ） (2020-08-16T23:34:09Z)
• Simplified Swarm Optimization for Bi-Objection Active Reliability Redundancy Allocation Problems [1.5990720051907859]
  信頼性冗長性割り当て問題(RRAP)は、システム設計、開発、管理においてよく知られた問題である。 本研究では, コスト制約を新たな目標として変更することにより, 両対象RRAPを定式化する。 提案課題を解決するために,ペナルティ関数を備えた新しい簡易スワム最適化 (SSO) ,実効1型ソリューション構造,数値ベースの自己適応型新しい更新機構,制約付き非支配型ソリューション選択,および新しいpBest代替ポリシーを開発した。
  論文  参考訳（メタデータ） (2020-06-17T13:15:44Z)

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

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