論文の概要: Loop Estimator for Discounted Values in Markov Reward Processes
- arxiv url: http://arxiv.org/abs/2002.06299v3
- Date: Wed, 3 Mar 2021 05:05:36 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-31 22:53:11.252033
- Title: Loop Estimator for Discounted Values in Markov Reward Processes
- Title（参考訳）: マルコフ報酬過程における割引値に対するループ推定器
- Authors: Falcon Z. Dai, Matthew R. Walter
- Abstract要約: 政策評価ステップは、マルコフポリシーに従って誘導されるマルコフ報酬プロセスからのサンプルで状態の値を推定する。
本稿では,マルコフ報酬過程の再生構造を利用したループ推定法を提案する。
予備的な数値実験では、ループ推定器はTD(k)のようなモデルフリーな手法よりも優れ、モデルベース推定器と競合する。
- 参考スコア（独自算出の注目度）: 19.011189395046014
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: At the working heart of policy iteration algorithms commonly used and studied
in the discounted setting of reinforcement learning, the policy evaluation step
estimates the value of states with samples from a Markov reward process induced
by following a Markov policy in a Markov decision process. We propose a simple
and efficient estimator called loop estimator that exploits the regenerative
structure of Markov reward processes without explicitly estimating a full
model. Our method enjoys a space complexity of $O(1)$ when estimating the value
of a single positive recurrent state $s$ unlike TD with $O(S)$ or model-based
methods with $O\left(S^2\right)$. Moreover, the regenerative structure enables
us to show, without relying on the generative model approach, that the
estimator has an instance-dependent convergence rate of
$\widetilde{O}\left(\sqrt{\tau_s/T}\right)$ over steps $T$ on a single sample
path, where $\tau_s$ is the maximal expected hitting time to state $s$. In
preliminary numerical experiments, the loop estimator outperforms model-free
methods, such as TD(k), and is competitive with the model-based estimator.
- Abstract（参考訳）: 強化学習の割引設定において一般的に用いられ研究されるポリシー反復アルゴリズムのワーキングハートにおいて、マルコフ決定プロセスにおいてマルコフポリシーに従うことで引き起こされるマルコフ報酬プロセスからサンプルを用いて状態の値を推定する。
我々は,マルコフ報酬過程の再生構造を利用するループ推定器(loop estimator)と呼ばれる簡易かつ効率的な推定器を提案する。
o(s)$のtdや、$o\left(s^2\right)$のモデルベースメソッドと異なり、単一の正の反復状態の値を推定する際には、o(1)$という空間の複雑さを享受する。
さらに、再生構造は、生成モデルアプローチを頼らずに、インスタンス依存収束率$\widetilde{O}\left(\sqrt{\tau_s/T}\right)$ over steps $T$, where $\tau_s$ is the maximal expected hit time to state $s$.
予備的な数値実験では、ループ推定器はTD(k)のようなモデルフリー手法よりも優れ、モデルベース推定器と競合する。
関連論文リスト
- Markov Chain Variance Estimation: A Stochastic Approximation Approach [14.883782513177094]
マルコフ連鎖上で定義される関数の分散を推定する問題は、定常平均の統計的推測の重要なステップである。
我々は,各ステップで$O(1)$を必要とする新しい再帰的推定器を設計し,過去のサンプルやラン長の知識を一切必要とせず,証明可能な有限サンプル保証付き平均二乗誤差(MSE)に対する最適な$O(frac1n)の収束率を有する。
論文 参考訳（メタデータ） (2024-09-09T15:42:28Z) - Convergence of a model-free entropy-regularized inverse reinforcement learning algorithm [6.481009996429766]
逆強化学習(IRL)は、専門家が最適である報酬を回復することを目的としている。
本研究では,エントロピー規則化IRL問題を解くためのモデルフリーアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-03-25T14:54:42Z) - A Specialized Semismooth Newton Method for Kernel-Based Optimal
Transport [92.96250725599958]
カーネルベース最適輸送(OT)推定器は、サンプルからOT問題に対処するための代替的機能的推定手順を提供する。
SSN法は, 標準正規性条件下でのグローバル収束率$O (1/sqrtk)$, 局所二次収束率を達成できることを示す。
論文 参考訳（メタデータ） (2023-10-21T18:48:45Z) - Improving Sample Efficiency of Model-Free Algorithms for Zero-Sum Markov Games [66.2085181793014]
モデルフリーのステージベースQ-ラーニングアルゴリズムはモデルベースアルゴリズムと同じ$H$依存の最適性を享受できることを示す。
本アルゴリズムは,楽観的値関数と悲観的値関数のペアとして参照値関数を更新するキーとなる新しい設計を特徴とする。
論文 参考訳（メタデータ） (2023-08-17T08:34:58Z) - Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳（メタデータ） (2021-12-23T18:47:50Z) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文 参考訳（メタデータ） (2021-10-09T21:13:48Z) - A Sharp Analysis of Model-based Reinforcement Learning with Self-Play [49.88233710867315]
マルチエージェントマルコフゲームのためのモデルベースセルフプレイアルゴリズムのシャープな解析を行う。
我々は,2プレイヤーゼロサムマルコフゲームのための最適化ナッシュ値イテレーション(Nash-VI)を設計する。
我々はさらに、ゼロサムマルコフゲームに対する証明可能な効率的なタスク認識アルゴリズムの設計に我々の分析を適用した。
論文 参考訳（メタデータ） (2020-10-04T15:27:39Z) - Efficiently Solving MDPs with Stochastic Mirror Descent [38.30919646721354]
線形モデルに与えられた無限水平マルコフ決定過程(MDP)を近似的に解くための統一的な枠組みを提案する。
これらの結果は、より一般的なミラー降下フレームワークを用いて、単純なドメインとボックスドメインで大域的なサドルポイント問題を解くことによって達成される。
論文 参考訳（メタデータ） (2020-08-28T17:58:40Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。