論文の概要: Scalable First-Order Methods for Robust MDPs
- arxiv url: http://arxiv.org/abs/2005.05434v5
- Date: Thu, 14 Jan 2021 21:06:53 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-04 20:57:34.814821
- Title: Scalable First-Order Methods for Robust MDPs
- Title(参考訳): ロバストMDPのスケーラブル1次法
- Authors: Julien Grand-Cl\'ement, Christian Kroer
- Abstract要約: 本稿では、ロバストなMDPを解くための第1次フレームワークを提案する。
値イテレーション更新の精度とコストのトレードオフを慎重に制御することで、O left(A2 S3log(S)log(epsilon-1) epsilon-1 right)$のエルゴード収束率を達成する。
- 参考スコア(独自算出の注目度): 31.29341288414507
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Robust Markov Decision Processes (MDPs) are a powerful framework for modeling
sequential decision-making problems with model uncertainty. This paper proposes
the first first-order framework for solving robust MDPs. Our algorithm
interleaves primal-dual first-order updates with approximate Value Iteration
updates. By carefully controlling the tradeoff between the accuracy and cost of
Value Iteration updates, we achieve an ergodic convergence rate of $O \left(
A^{2} S^{3}\log(S)\log(\epsilon^{-1}) \epsilon^{-1} \right)$ for the best
choice of parameters on ellipsoidal and Kullback-Leibler $s$-rectangular
uncertainty sets, where $S$ and $A$ is the number of states and actions,
respectively. Our dependence on the number of states and actions is
significantly better (by a factor of $O(A^{1.5}S^{1.5})$) than that of pure
Value Iteration algorithms. In numerical experiments on ellipsoidal uncertainty
sets we show that our algorithm is significantly more scalable than
state-of-the-art approaches. Our framework is also the first one to solve
robust MDPs with $s$-rectangular KL uncertainty sets.
- Abstract(参考訳): Robust Markov Decision Processs (MDPs) は、モデル不確実性を伴うシーケンシャルな意思決定問題をモデル化するための強力なフレームワークである。
本稿では,堅牢なMDPを解くための第1次フレームワークを提案する。
提案手法は初等二次一階更新と近似値反復更新をインターリーブする。
反復更新の精度とコストのトレードオフを慎重に制御することにより、エルゴード収束率は$o \left(a^{2} s^{3}\log(s)\log(\epsilon^{-1}) \epsilon^{-1} \right)$ となる。
我々の状態と行動の数への依存は、純粋な値反復アルゴリズムよりもはるかに良い($O(A^{1.5}S^{1.5})$)。
楕円型不確かさ集合に関する数値実験において,本アルゴリズムは最先端手法よりもかなりスケーラブルであることを示した。
我々のフレームワークはまた、$s$-rectangular KL不確実集合で堅牢なMDPを解く最初のフレームワークである。
関連論文リスト
- Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳(メタデータ) (2024-05-10T09:58:47Z) - Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs [17.62509045102346]
本稿では,CMDP(Constrained Markov Decision Processs)における最適ポリシー識別問題について考察する。
私たちは、モデルフリーで、後悔の少ないアルゴリズムに興味を持ち、確率の高いほぼ最適なポリシーを特定しています。
オンラインCMDPのサブ線形後悔と制約違反を伴う既存のモデルフリーアルゴリズムでは、最適ポリシーに対する収束保証は提供されない。
論文 参考訳(メタデータ) (2023-09-27T04:33:09Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳(メタデータ) (2023-06-30T08:34:29Z) - Bayesian Learning of Optimal Policies in Markov Decision Processes with Countably Infinite State-Space [0.0]
離散時間可算状態空間マルコフ決定過程の族を最適に制御する問題について検討する。
動的サイズのエピソードを用いたトンプソンサンプリングに基づくアルゴリズムを提案する。
提案アルゴリズムは, 近似最適制御アルゴリズムの開発に応用可能であることを示す。
論文 参考訳(メタデータ) (2023-06-05T03:57:16Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-01-30T14:37:21Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes [13.908826484332282]
そこで我々は,コストの抑えられたマルコフ決定プロセス問題を解決するために,オンライン・プリマル・デュアル・アクター・クリティカル法について検討した。
本稿では,CMDP問題の解法として,オンライン・プリマル・デュアル・アクター・クリティカル法の有限時間複雑性を初めて検討した。
論文 参考訳(メタデータ) (2021-10-21T18:05:40Z) - An Adaptive State Aggregation Algorithm for Markov Decision Processes [10.494611365482028]
同様のコスト・ツー・ゴー値の状態を動的にグループ化することで、価値反復更新のコストを削減できるMDPを解くための直感的なアルゴリズムを提案する。
我々のアルゴリズムはほぼ確実に(2varepsilon / (1 - gamma) に収束し、(γ) は割引係数であり、集約された状態は最大で (varepsilon) 異なる。
論文 参考訳(メタデータ) (2021-07-23T07:19:43Z) - Correcting Momentum with Second-order Information [50.992629498861724]
最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。
我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
論文 参考訳(メタデータ) (2021-03-04T19:01:20Z) - Efficiently Solving MDPs with Stochastic Mirror Descent [38.30919646721354]
線形モデルに与えられた無限水平マルコフ決定過程(MDP)を近似的に解くための統一的な枠組みを提案する。
これらの結果は、より一般的なミラー降下フレームワークを用いて、単純なドメインとボックスドメインで大域的なサドルポイント問題を解くことによって達成される。
論文 参考訳(メタデータ) (2020-08-28T17:58:40Z) - Provably Efficient Reinforcement Learning for Discounted MDPs with
Feature Mapping [99.59319332864129]
本稿では,割引決定(MDP)のための強化学習について検討する。
本稿では,特徴写像を利用した新しいアルゴリズムを提案し,$tilde O(dsqrtT/ (1-gamma)2)$ regretを求める。
以上の結果から,提案した強化学習アルゴリズムは,最大1-γ-0.5$の係数でほぼ最適であることが示唆された。
論文 参考訳(メタデータ) (2020-06-23T17:08:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。