論文の概要: Performative Reinforcement Learning with Linear Markov Decision Process
- arxiv url: http://arxiv.org/abs/2411.05234v1
- Date: Thu, 07 Nov 2024 23:04:48 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-11 14:53:41.694050
- Title: Performative Reinforcement Learning with Linear Markov Decision Process
- Title（参考訳）: 線形マルコフ決定過程を用いた変形的強化学習
- Authors: Debmalya Mandal, Goran Radanovic,
- Abstract要約: 提案手法がマルコフ決定過程の報酬と遷移の両方に影響を及ぼすような表現的強化学習の設定について検討する。
大規模MDPの主要な理論モデルであるEmphlinear Markov決定過程を一般化する。
- 参考スコア（独自算出の注目度）: 14.75815792682734
- License:
- Abstract: We study the setting of \emph{performative reinforcement learning} where the deployed policy affects both the reward, and the transition of the underlying Markov decision process. Prior work~\parencite{MTR23} has addressed this problem under the tabular setting and established last-iterate convergence of repeated retraining with iteration complexity explicitly depending on the number of states. In this work, we generalize the results to \emph{linear Markov decision processes} which is the primary theoretical model of large-scale MDPs. The main challenge with linear MDP is that the regularized objective is no longer strongly convex and we want a bound that scales with the dimension of the features, rather than states which can be infinite. Our first result shows that repeatedly optimizing a regularized objective converges to a \emph{performatively stable policy}. In the absence of strong convexity, our analysis leverages a new recurrence relation that uses a specific linear combination of optimal dual solutions for proving convergence. We then tackle the finite sample setting where the learner has access to a set of trajectories drawn from the current policy. We consider a reparametrized version of the primal problem, and construct an empirical Lagrangian which is to be optimized from the samples. We show that, under a \emph{bounded coverage} condition, repeatedly solving a saddle point of this empirical Lagrangian converges to a performatively stable solution, and also construct a primal-dual algorithm that solves the empirical Lagrangian efficiently. Finally, we show several applications of the general framework of performative RL including multi-agent systems.
- Abstract（参考訳）: 提案手法は報酬とマルコフ決定過程の遷移の両方に影響を及ぼす。
先行研究~\parencite{MTR23} は、この問題を表の設定の下で解決し、繰り返し再訓練の終点収束を確立した。
本研究では,大規模なMDPの主理論モデルである 'emph{linear Markov decision process} に結果を一般化する。
線形 MDP の最大の課題は、正規化対象がもはや強凸ではないことである。
最初の結果は、正規化対象の繰り返し最適化が \emph{performatively stable policy} に収束することを示している。
強い凸性がない場合、我々の分析は、収束を証明するために最適な双対解の特定の線形結合を利用する新しい再帰関係を利用する。
次に、学習者が現在の方針から引き出された一連の軌跡にアクセス可能な有限標本設定に取り組む。
予備問題の再パラメータ化版を考え,サンプルから最適化される経験的ラグランジアンを構築した。
この経験的ラグランジアンのサドル点を連続的に解き、性能的に安定な解に収束し、経験的ラグランジアンを効率的に解く原始双対アルゴリズムを構築することを示す。
最後に、マルチエージェントシステムを含むパフォーマンスRLの一般的なフレームワークのいくつかの応用について述べる。
関連論文リスト
- Double Duality: Variational Primal-Dual Policy Optimization for
Constrained Reinforcement Learning [132.7040981721302]
本研究では,訪問尺度の凸関数を最小化することを目的として,制約付き凸決定プロセス(MDP)について検討する。
制約付き凸MDPの設計アルゴリズムは、大きな状態空間を扱うなど、いくつかの課題に直面している。
論文 参考訳（メタデータ） (2024-02-16T16:35:18Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳（メタデータ） (2023-10-20T12:45:12Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Formal guarantees for heuristic optimization algorithms used in machine
learning [6.978625807687497]
グラディエント・Descent(SGD)とその変種は、大規模最適化機械学習(ML)問題において支配的な手法となっている。
本稿では,いくつかの凸最適化手法の形式的保証と改良アルゴリズムの提案を行う。
論文 参考訳（メタデータ） (2022-07-31T19:41:22Z) - Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic
Algorithm for Constrained Markov Decision Processes [22.07834608976826]
そこで我々は,コストの抑えられたマルコフ決定プロセス問題を解決するために,オンライン・プリマル・デュアル・アクター・クリティカル法について検討した。
本稿では,CMDP問題の解法として,オンライン・プリマル・デュアル・アクター・クリティカル法の有限時間複雑性を初めて検討した。
論文 参考訳（メタデータ） (2021-10-21T18:05:40Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳（メタデータ） (2021-10-20T02:57:21Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳（メタデータ） (2021-06-05T09:16:28Z) - A Retrospective Approximation Approach for Smooth Stochastic
Optimization [0.2867517731896504]
グラディエント(グラディエント、英: Gradient、SG)とは、最適化(SO)問題をスムーズ(ノンフィクション)な目標値で解くための補足的反復手法である。
論文 参考訳（メタデータ） (2021-03-07T16:29:36Z) - Posterior-Aided Regularization for Likelihood-Free Inference [23.708122045184698]
後補助正規化(PAR)は,モデル構造に関係なく,密度推定器の学習に適用可能である。
単一のニューラルネットワークを用いて逆KL項と相互情報項の両方を推定するPARの統一推定方法を提供する。
論文 参考訳（メタデータ） (2021-02-15T16:59:30Z) - Upper Confidence Primal-Dual Reinforcement Learning for CMDP with
Adversarial Loss [145.54544979467872]
マルコフ決定過程(CMDP)に対するオンライン学習の検討
本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。
我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
論文 参考訳（メタデータ） (2020-03-02T05:02:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。