論文の概要: Sequential Principal-Agent Problems with Communication: Efficient
Computation and Learning
- arxiv url: http://arxiv.org/abs/2306.03832v1
- Date: Tue, 6 Jun 2023 16:20:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-07 14:24:54.545981
- Title: Sequential Principal-Agent Problems with Communication: Efficient
Computation and Learning
- Title（参考訳）: コミュニケーションを伴う逐次主エージェント問題:効率的な計算と学習
- Authors: Jiarui Gan, Rupak Majumdar, Debmalya Mandal, Goran Radanovic
- Abstract要約: 両端に不完全な情報を持つ主要因とエージェント間の逐次的意思決定問題について検討する。
このモデルでは、プリンシパルとエージェントは環境の中で相互作用し、それぞれが他で利用できない状態についての観測にプライベートである。
本稿では,アルゴリズムのアルゴリズムを用いて,主成分の最適ポリシを加法近似まで計算する。
- 参考スコア（独自算出の注目度）: 19.613273684856075
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study a sequential decision making problem between a principal and an
agent with incomplete information on both sides. In this model, the principal
and the agent interact in a stochastic environment, and each is privy to
observations about the state not available to the other. The principal has the
power of commitment, both to elicit information from the agent and to provide
signals about her own information. The principal and the agent communicate
their signals to each other, and select their actions independently based on
this communication. Each player receives a payoff based on the state and their
joint actions, and the environment moves to a new state. The interaction
continues over a finite time horizon, and both players act to optimize their
own total payoffs over the horizon. Our model encompasses as special cases
stochastic games of incomplete information and POMDPs, as well as sequential
Bayesian persuasion and mechanism design problems. We study both computation of
optimal policies and learning in our setting. While the general problems are
computationally intractable, we study algorithmic solutions under a conditional
independence assumption on the underlying state-observation distributions. We
present an polynomial-time algorithm to compute the principal's optimal policy
up to an additive approximation. Additionally, we show an efficient learning
algorithm in the case where the transition probabilities are not known
beforehand. The algorithm guarantees sublinear regret for both players.
- Abstract（参考訳）: 両端に不完全な情報を持つ主要因とエージェント間の逐次的意思決定問題について検討する。
このモデルでは、プリンシパルとエージェントは確率的な環境で相互作用し、それぞれが互いに利用できない状態に関する観察を優先する。
校長は、エージェントから情報を引き出すことと、自身の情報に関する信号を提供するという、コミットメントの力を持っている。
プリンシパルとエージェントは互いにシグナルを伝達し、この通信に基づいて独立して行動を選択する。
各プレイヤーは、状態と共同動作に基づいてペイオフを受け取り、環境は新しい状態に移動する。
相互作用は有限時間水平線上で継続し、双方のプレイヤーは水平線上での合計ペイオフを最適化する。
本モデルでは,不完全情報とPOMDPの確率ゲーム,シーケンシャルベイズパースと機構設計の問題を含む。
我々は,最適政策の計算と学習の両方について検討する。
一般的な問題は計算に難解であるが、基礎となる状態観測分布の条件付き独立性仮定の下でアルゴリズム解を考察する。
本稿では,主成分の最適ポリシを加法近似まで計算する多項式時間アルゴリズムを提案する。
さらに,遷移確率が事前に分かっていない場合に,効率的な学習アルゴリズムを示す。
このアルゴリズムは両プレイヤーに対してサブ線形後悔を保証する。
関連論文リスト
- Refined Sample Complexity for Markov Games with Independent Linear Function Approximation [49.5660193419984]
マルコフゲーム(MG)はマルチエージェント強化学習(MARL)の重要なモデルである
本稿では、WangらによるAVLPRフレームワークを改良し(2023年)、最適部分ギャップの悲観的推定を設計する。
マルチエージェントの呪いに取り組み、最適な$O(T-1/2)収束率を達成し、同時に$textpoly(A_max)$依存性を避ける最初のアルゴリズムを与える。
論文 参考訳（メタデータ） (2024-02-11T01:51:15Z) - Decentralized Multi-Task Online Convex Optimization Under Random Link
Failures [5.513958040574729]
我々は不均一な確率を持つランダムリンク障害に対する頑健な分散型サドルポイントアルゴリズムを開発した。
我々はアルゴリズムと分析を2点の帯域フィードバックシナリオに拡張する。
論文 参考訳（メタデータ） (2024-01-04T00:57:33Z) - Task-Guided IRL in POMDPs that Scales [22.594913269327353]
逆線形強化学習(IRL)では、学習エージェントは、専門家のデモンストレーションを用いて、基礎となるタスクをコードする報酬関数を推論する。
ほとんどのIRL技術は、POMDPの計算前方問題(報酬関数を与えられた最適ポリシーを計算)を必要とする。
我々は,データ効率を向上しながら,情報量を削減するアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-12-30T21:08:57Z) - Independent Policy Gradient for Large-Scale Markov Potential Games:
Sharper Rates, Function Approximation, and Game-Agnostic Convergence [30.084357461497042]
状態空間と/またはプレイヤーの数が非常に大きいMPGのナッシュ均衡を学習する。
我々は,すべてのプレイヤーがタンデムで実行する独立ポリシー勾配アルゴリズムを提案する。
我々は、ゼロサムマルコフゲームとマルコフ協調ゲームの両方の収束性を楽しむ独立ポリシー勾配アルゴリズムのクラスを、ゲームの種類によらないプレイヤーと同定する。
論文 参考訳（メタデータ） (2022-02-08T20:09:47Z) - Cooperative Online Learning in Stochastic and Adversarial MDPs [50.62439652257712]
我々は、協調的オンライン学習と敵対的マルコフ決定過程(MDP)について研究する。
各エピソードでは、$m$エージェントが同時にMDPと対話し、個人の後悔を最小限に抑えるために情報を共有する。
協調強化学習(RL)を非フレッシュランダム性, あるいは敵対的MDPで検討したのは, 初めてである。
論文 参考訳（メタデータ） (2022-01-31T12:32:11Z) - Provably Efficient Reinforcement Learning in Decentralized General-Sum
Markov Games [5.205867750232226]
本稿では,一般のマルコフゲームにおいて平衡を効率的に学習する問題に対処する。
本稿では,各エージェントが独立して楽観的なV-ラーニングを実行し,未知の環境を効率的に探索するアルゴリズムを提案する。
エージェントは少なくとも$widetildeO(H6S A /epsilon2)$ episodesで$epsilon$-approximate CCEを見つけることができる。
論文 参考訳（メタデータ） (2021-10-12T02:01:22Z) - Reinforcement Learning in Reward-Mixing MDPs [74.41782017817808]
報酬混合マルコフ決定過程(MDP)におけるエピソード強化学習
cdot S2 A2)$ episodes, where$H$ is time-horizon and $S, A$ are the number of state and actions。
epsilon$-optimal policy after $tildeO(poly(H,epsilon-1) cdot S2 A2)$ episodes, $H$ is time-horizon and $S, A$ are the number of state and actions。
論文 参考訳（メタデータ） (2021-10-07T18:55:49Z) - Towards General Function Approximation in Zero-Sum Markov Games [126.58493169301012]
本稿では,同時移動を伴う2プレーヤゼロサム有限ホライゾンマルコフゲームについて考察する。
分離された設定とコーディネートされた設定の両方の効率的なアルゴリズムが開発されている。
論文 参考訳（メタデータ） (2021-07-30T15:25:13Z) - Bandit Linear Optimization for Sequential Decision Making and
Extensive-Form Games [102.23975166536326]
tree-form sequential decision making (tfsdm) は、エージェントと潜在的に敵対的な環境の間のツリー形式の相互作用をモデル化することで、古典的なワンショット意思決定を拡張する。
これは、各プレイヤーが幅広い形式のゲームで直面するオンライン意思決定問題、およびマルコフ決定プロセス、およびエージェントが観測された履歴を条件とする部分観察可能なマルコフ決定プロセスをキャプチャする。
本稿では, (i) 線形時間損失と (ii) $o(sqrtt)$ cumulative regret の両方を提供する拡張dmのバンディット線形最適化問題に対する最初のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-03-08T05:00:13Z) - Upper Confidence Primal-Dual Reinforcement Learning for CMDP with
Adversarial Loss [145.54544979467872]
マルコフ決定過程(CMDP)に対するオンライン学習の検討
本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。
我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
論文 参考訳（メタデータ） (2020-03-02T05:02:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。