論文の概要: Efficiently Solving MDPs with Stochastic Mirror Descent
- arxiv url: http://arxiv.org/abs/2008.12776v1
- Date: Fri, 28 Aug 2020 17:58:40 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-24 01:57:34.772054
- Title: Efficiently Solving MDPs with Stochastic Mirror Descent
- Title（参考訳）: 確率鏡によるMDPの効率的な解法
- Authors: Yujia Jin and Aaron Sidford
- Abstract要約: 線形モデルに与えられた無限水平マルコフ決定過程(MDP)を近似的に解くための統一的な枠組みを提案する。
これらの結果は、より一般的なミラー降下フレームワークを用いて、単純なドメインとボックスドメインで大域的なサドルポイント問題を解くことによって達成される。
- 参考スコア（独自算出の注目度）: 38.30919646721354
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a unified framework based on primal-dual stochastic mirror descent
for approximately solving infinite-horizon Markov decision processes (MDPs)
given a generative model. When applied to an average-reward MDP with $A_{tot}$
total state-action pairs and mixing time bound $t_{mix}$ our method computes an
$\epsilon$-optimal policy with an expected $\widetilde{O}(t_{mix}^2 A_{tot}
\epsilon^{-2})$ samples from the state-transition matrix, removing the
ergodicity dependence of prior art. When applied to a $\gamma$-discounted MDP
with $A_{tot}$ total state-action pairs our method computes an
$\epsilon$-optimal policy with an expected $\widetilde{O}((1-\gamma)^{-4}
A_{tot} \epsilon^{-2})$ samples, matching the previous state-of-the-art up to a
$(1-\gamma)^{-1}$ factor. Both methods are model-free, update state values and
policies simultaneously, and run in time linear in the number of samples taken.
We achieve these results through a more general stochastic mirror descent
framework for solving bilinear saddle-point problems with simplex and box
domains and we demonstrate the flexibility of this framework by providing
further applications to constrained MDPs.
- Abstract（参考訳）: 生成モデルから得られる無限水平マルコフ決定過程 (MDP) を近似的に解くために, 原始-双対確率的ミラー降下に基づく統一フレームワークを提案する。
a_{tot}$ の全状態-アクション対と混合時間バインド $t_{mix}$ の平均値 mdp に適用すると、この方法は、状態遷移行列から期待$\widetilde{o}(t_{mix}^2 a_{tot} \epsilon^{-2})$ のサンプルを持つ$\epsilon$-optimal ポリシーを計算し、以前のアートのエルゴディクティ依存を取り除く。
A_{tot} の総状態-作用対を持つ $\gamma$-discounted MDP に適用すると、我々のメソッドは $\epsilon$-optimal policy with a expected $\widetilde{O}((1-\gamma)^{-4} A_{tot} \epsilon^{-2})$ sample を計算する。
どちらのメソッドもモデルフリーで、状態値とポリシーを同時に更新し、取得したサンプル数を線形に実行します。
これらの結果は、より一般的な確率的ミラー降下フレームワークを用いて、単純度とボックス領域で双線形サドルポイント問題を解くことで実現し、制約付き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) - Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs [6.996002801232415]
平均回帰マルコフ決定過程(MDP)において,$varepsilon$-optimal Policyを生成モデルで学習する際のサンプル複雑性について検討した。
MDP を弱通信するためには、$widetildeO(SAfracHvarepsilon2 )$, $H$ は最適ポリシーのバイアス関数のスパンであり、$SA$ は状態作用空間の濃度である。
論文 参考訳（メタデータ） (2024-03-18T04:52:11Z) - Span-Based Optimal Sample Complexity for Average Reward MDPs [6.996002801232415]
平均回帰マルコフ決定過程(MDP)において,$varepsilon$-optimal Policyを生成モデルで学習する際のサンプル複雑性について検討した。
我々は、$widetildeOleft(SAfracH (1-gamma)2varepsilon2 right)$, ここで、$H$は最適ポリシーのバイアス関数のスパンであり、$SA$は状態作用空間の濃度である。
論文 参考訳（メタデータ） (2023-11-22T15:34:44Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳（メタデータ） (2022-10-05T22:52:00Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Towards Tight Bounds on the Sample Complexity of Average-reward MDPs [39.01663172393174]
生成モデルにアクセス可能な無限水平平均回帰マルコフ決定過程の最適方針を求める。
状態-作用対あたりのサンプルを$widetildeO(t_mathrmmix epsilon-3)$ (oblivious) で解決するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-06-13T17:18:11Z) - Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and
Variance Reduction [63.41789556777387]
非同期Q-ラーニングはマルコフ決定過程(MDP)の最適行動値関数(またはQ-関数)を学習することを目的としている。
Q-関数の入出力$varepsilon$-正確な推定に必要なサンプルの数は、少なくとも$frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$の順である。
論文 参考訳（メタデータ） (2020-06-04T17:51:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。