論文の概要: Stochastic Principal-Agent Problems: Efficient Computation and Learning
- arxiv url: http://arxiv.org/abs/2306.03832v3
- Date: Thu, 12 Sep 2024 10:22:10 GMT
- ステータス: 処理完了
- システム内更新日: 2024-09-13 22:51:28.614406
- Title: Stochastic Principal-Agent Problems: Efficient Computation and Learning
- Title（参考訳）: 確率的主問題:効率的な計算と学習
- Authors: Jiarui Gan, Rupak Majumdar, Debmalya Mandal, Goran Radanovic,
- Abstract要約: プリンシパルとエージェントは環境の中で相互作用し、それぞれが互いに利用できない状態に関する観察を行う。
このモデルは、特殊ケースワイドフォームゲーム(EFG)を包含し、マルコフ決定プロセス(POMDP)のゲームにアプローチする。
遷移確率が未知のエピソード強化学習環境において,効率的なアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 25.637633553882985
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We introduce a stochastic principal-agent model. A principal and an agent interact in a stochastic environment, each 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 players communicate with each other and then select actions independently. Each of them receives a payoff based on the state and their joint action, and the environment transitions to a new state. The interaction continues over a finite time horizon. Both players are far-sighted, aiming to maximize their total payoffs over the time horizon. The model encompasses as special cases extensive-form games (EFGs) and stochastic games of incomplete information, partially observable Markov decision processes (POMDPs), as well as other forms of sequential principal-agent interactions, including Bayesian persuasion and automated mechanism design problems. We consider both the computation and learning of the principal's optimal policy. Since the general problem, which subsumes POMDPs, is intractable, we explore algorithmic solutions under hindsight observability, where the state and the interaction history are revealed at the end of each step. Though the problem becomes more amenable under this condition, the number of possible histories remains exponential in the length of the time horizon, making approaches for EFG-based models infeasible. We present an efficient algorithm based on the inducible value sets. The algorithm computes an $\epsilon$-approximate optimal policy in time polynomial in $1/\epsilon$. Additionally, we show an efficient learning algorithm for an episodic reinforcement learning setting where the transition probabilities are unknown. The algorithm guarantees sublinear regret $\tilde{O}(T^{2/3})$ for both players over $T$ episodes.
- Abstract（参考訳）: 確率的主エージェントモデルを導入する。
プリンシパルとエージェントは確率的な環境で相互作用し、それぞれが他で利用できない状態に関する観測を行う。
校長は、エージェントから情報を引き出すことと、自身の情報に関する信号を提供するという、コミットメントの力を持っている。
プレイヤーは互いにコミュニケーションし、個別に行動を選択する。
それぞれが、状態と共同動作に基づいてペイオフを受け取り、環境が新しい状態に遷移する。
相互作用は有限時間水平線上で続く。
両選手とも遠視力があり、時間軸を超えて全報酬を最大化することを目指している。
このモデルは、不完全な情報、部分的に観測可能なマルコフ決定過程(POMDP)、ベイズ的説得や自動メカニズム設計問題を含む他の逐次的主エージェント相互作用の形式を含む特別なケースである。
我々は,プリンシパルの最適政策の計算と学習について考察する。
POMDPを仮定する一般的な問題は難解であるため、各ステップの最後に状態と相互作用履歴が明らかになるような、後向きの観測可能性の下でアルゴリズムによる解を探索する。
この条件下では、この問題はより和らげられるが、時間的地平線の長さにおいて、可能なヒストリーの数は指数関数的のままであり、EFGベースのモデルに対するアプローチは実現不可能である。
帰納的値集合に基づく効率的なアルゴリズムを提案する。
このアルゴリズムは、時間多項式で$\epsilon$-approximateの最適ポリシーを1/\epsilon$で計算する。
さらに,遷移確率が未知のエピソード強化学習環境において,効率的な学習アルゴリズムを示す。
このアルゴリズムは、サブ線形後悔$\tilde{O}(T^{2/3})$を、両プレイヤーに対して$T$のエピソードに対して保証する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。