論文の概要: Mechanism design with multi-armed bandit

• arxiv url: http://arxiv.org/abs/2412.00345v1
• Date: Sat, 30 Nov 2024 03:59:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-04 15:41:44.371966
• Title: Mechanism design with multi-armed bandit
• Title（参考訳）: マルチアームバンディットを用いた機構設計
• Authors: Takayuki Osogami, Hirota Kinoshita, Segev Wasserkrug,
• Abstract要約: 自動メカニズム設計の一般的なアプローチは、ソリューションが望ましい特性を持つメカニズムを提供する線形プログラム(LP)を定式化することである。 我々は、効率、インセンティブ整合性、強い予算収支(SBB)、個人合理性(IR)の標準的な特性を達成するメカニズムを提供する、そのようなLPのための最適解のクラスを解析的に導出した。
• 参考スコア（独自算出の注目度）: 8.013444110633223
• License:
• Abstract: A popular approach of automated mechanism design is to formulate a linear program (LP) whose solution gives a mechanism with desired properties. We analytically derive a class of optimal solutions for such an LP that gives mechanisms achieving standard properties of efficiency, incentive compatibility, strong budget balance (SBB), and individual rationality (IR), where SBB and IR are satisfied in expectation. Notably, our solutions are represented by an exponentially smaller number of essential variables than the original variables of LP. Our solutions, however, involve a term whose exact evaluation requires solving a certain optimization problem exponentially many times as the number of players, $N$, grows. We thus evaluate this term by modeling it as the problem of estimating the mean reward of the best arm in multi-armed bandit (MAB), propose a Probably and Approximately Correct estimator, and prove its asymptotic optimality by establishing a lower bound on its sample complexity. This MAB approach reduces the number of times the optimization problem is solved from exponential to $O(N\,\log N)$. Numerical experiments show that the proposed approach finds mechanisms that are guaranteed to achieve desired properties with high probability for environments with up to 128 players, which substantially improves upon the prior work.
• Abstract（参考訳）: 自動メカニズム設計の一般的なアプローチは、ソリューションが望ましい特性を持つメカニズムを提供する線形プログラム(LP)を定式化することである。 我々は、効率、インセンティブ整合性、強い予算収支(SBB)および個人合理性(IR)の標準的な特性を達成するメカニズムを提供するLPの最適解のクラスを解析的に導出した。 特に、我々の解は、LPの元の変数よりも指数関数的に少ない本質変数で表される。 しかし、我々の解には、プレイヤー数($N$)が増加するにつれて、ある最適化問題を指数関数的に解く必要のある、正確な評価の項が含まれる。 そこで我々は,マルチアームバンディット(MAB)におけるベストアームの平均報酬を推定する問題として,この用語をモデル化し,確率的および略補正推定器を提案し,サンプルの複雑さの低い境界を確立することで,その漸近的最適性を証明した。 このMABアプローチは、最適化問題が指数関数的に解かれる回数を$O(N\,\log N)$に減らす。 数値実験により,提案手法は,最大128人のプレイヤーの環境に高い確率で所望の特性を達成できることが保証され,従来よりも大幅に改善されていることがわかった。

関連論文リスト

• 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)

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

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