論文の概要: Learning Dynamic Mechanisms in Unknown Environments: A Reinforcement Learning Approach

• arxiv url: http://arxiv.org/abs/2202.12797v2
• Date: Sun, 25 Feb 2024 08:43:57 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-27 19:45:09.271047
• Title: Learning Dynamic Mechanisms in Unknown Environments: A Reinforcement Learning Approach
• Title（参考訳）: 未知環境における動的メカニズムの学習 : 強化学習アプローチ
• Authors: Shuang Qiu, Boxiang Lyu, Qinglin Meng, Zhaoran Wang, Zhuoran Yang, Michael I. Jordan
• Abstract要約: 本稿では,複数ラウンドの対話を通して動的ビックレー・クラーク・グローブ(VCG)機構を回復するための新しい学習アルゴリズムを提案する。 当社のアプローチの重要な貢献は、報酬のないオンライン強化学習(RL)を取り入れて、リッチな政策分野の探索を支援することである。
• 参考スコア（独自算出の注目度）: 130.9259586568977
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Dynamic mechanism design studies how mechanism designers should allocate resources among agents in a time-varying environment. We consider the problem where the agents interact with the mechanism designer according to an unknown Markov Decision Process (MDP), where agent rewards and the mechanism designer's state evolve according to an episodic MDP with unknown reward functions and transition kernels. We focus on the online setting with linear function approximation and propose novel learning algorithms to recover the dynamic Vickrey-Clarke-Grove (VCG) mechanism over multiple rounds of interaction. A key contribution of our approach is incorporating reward-free online Reinforcement Learning (RL) to aid exploration over a rich policy space to estimate prices in the dynamic VCG mechanism. We show that the regret of our proposed method is upper bounded by $\tilde{\mathcal{O}}(T^{2/3})$ and further devise a lower bound to show that our algorithm is efficient, incurring the same $\tilde{\mathcal{O}}(T^{2 / 3})$ regret as the lower bound, where $T$ is the total number of rounds. Our work establishes the regret guarantee for online RL in solving dynamic mechanism design problems without prior knowledge of the underlying model.
• Abstract（参考訳）: 動的メカニズム設計は、メカニズム設計者が時間変化のある環境でエージェント間でリソースを割り当てる方法を研究する。 エージェントが未知のマルコフ決定プロセス(MDP)に従ってメカニズムデザイナと相互作用する問題について考察し、エージェント報酬とメカニズムデザイナの状態は未知の報酬関数と遷移カーネルを持つエピソードMDPに従って進化する。 本稿では,線形関数近似によるオンライン設定に着目し,複数ラウンドのインタラクションを通じて動的ビックレー・クラーク・グローブ(vcg)機構を復元する新しい学習アルゴリズムを提案する。 当社のアプローチの重要な貢献は、報酬のないオンライン強化学習(RL)を導入して、リッチな政策空間を探索し、動的VCGメカニズムの価格を見積もることである。 提案手法の後悔は$\tilde{\mathcal{o}}(t^{2/3})$で上限され、さらに下限を考案し、我々のアルゴリズムが効率的であることを示し、同じ$\tilde{\mathcal{o}}(t^{2/3})$を下限として後悔することを示し、ここで$t$はラウンドの総数である。 我々の研究は、基礎となるモデルについて事前知識のない動的メカニズム設計問題の解決において、オンラインRLに対する後悔の保証を確立します。

関連論文リスト

• Nash Incentive-compatible Online Mechanism Learning via Weakly Differentially Private Online Learning [6.869373893556194]
  本研究では,複数ラウンドの機構設計問題について検討し,一組のエージェントと一組のラウンドで対話する。 我々は、アプリケーション固有の目的を最大化するために、インセンティブ互換(IC)オンライン学習スキームを設計したいと考えています。
  論文  参考訳（メタデータ） (2024-07-06T00:02:25Z)
• GOV-REK: Governed Reward Engineering Kernels for Designing Robust Multi-Agent Reinforcement Learning Systems [2.867517731896504]
  マルチエージェント強化学習システムにおけるエージェントに報酬分布を動的に割り当てるGOVerned Reward Engineering Kernels (GOV-REK)を提案する。 我々はまた、意味のあるエージェント報酬分布を割り当てるために、状態または共同アクション空間の基盤構造を利用するガバナンスカーネルも導入する。 我々の実験は、有意義な報奨が、異なるMARL問題を効果的に学習する学習プロセスを開始することを実証している。
  論文  参考訳（メタデータ） (2024-04-01T14:19:00Z)
• Refined Mechanism Design for Approximately Structured Priors via Active Regression [50.71772232237571]
  我々は、大量の商品を戦略的入札者に販売する収益を最大化する販売業者の問題を考える。 この設定の最適かつほぼ最適のメカニズムは、特徴付けや計算が難しいことで有名である。
  論文  参考訳（メタデータ） (2023-10-11T20:34:17Z)
• On Reward Structures of Markov Decision Processes [4.13365552362244]
  マルコフ決定過程は、遷移カーネルと報酬関数によってパラメータ化することができる。 ロボット応用の需要に触発された強化学習に関連する様々な「コスト」について検討する。 単一状態値を推定するためのインスタンス固有のエラーを$tildeO(sqrtfractau_sn)$にバインドした新しい推定器を開発する。
  論文  参考訳（メタデータ） (2023-08-28T22:29:16Z)
• Pessimism meets VCG: Learning Dynamic Mechanism Design via Offline Reinforcement Learning [114.36124979578896]
  オフライン強化学習アルゴリズムを用いて動的メカニズムを設計する。 我々のアルゴリズムは悲観主義の原理に基づいており、オフラインデータセットのカバレッジについて軽度な仮定しか必要としない。
  論文  参考訳（メタデータ） (2022-05-05T05:44:26Z)
• Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
  マルチエージェントシステムにおける学習に有効なモデルベース強化学習アルゴリズムを提案する。 我々の理論的な貢献は、MFCのモデルベース強化学習における最初の一般的な後悔の限界である。 コア最適化問題の実用的なパラメトリゼーションを提供する。
  論文  参考訳（メタデータ） (2021-07-08T18:01:02Z)
• VCG Mechanism Design with Unknown Agent Values under Stochastic Bandit Feedback [104.06766271716774]
  本研究では,エージェントが自己の価値を知らない場合に,マルチラウンドの福祉最大化機構設計問題について検討する。 まず、福祉に対する後悔の3つの概念、各エージェントの個々のユーティリティ、メカニズムの3つの概念を定義します。 当社のフレームワークは価格体系を柔軟に制御し、エージェントと販売者の後悔のトレードオフを可能にする。
  論文  参考訳（メタデータ） (2020-04-19T18:00:58Z)
• Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
  マルコフ決定過程(CMDP)に対するオンライン学習の検討 本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。 我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
  論文  参考訳（メタデータ） (2020-03-02T05:02:23Z)

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

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