論文の概要: Towards Tight Bounds on the Sample Complexity of Average-reward MDPs
- arxiv url: http://arxiv.org/abs/2106.07046v1
- Date: Sun, 13 Jun 2021 17:18:11 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-15 15:31:11.025070
- Title: Towards Tight Bounds on the Sample Complexity of Average-reward MDPs
- Title（参考訳）: 平均回帰型MDPのサンプル複雑度について
- Authors: Yujia Jin, Aaron Sidford
- Abstract要約: 生成モデルにアクセス可能な無限水平平均回帰マルコフ決定過程の最適方針を求める。
状態-作用対あたりのサンプルを$widetildeO(t_mathrmmix epsilon-3)$ (oblivious) で解決するアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 39.01663172393174
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We prove new upper and lower bounds for sample complexity of finding an
$\epsilon$-optimal policy of an infinite-horizon average-reward Markov decision
process (MDP) given access to a generative model. When the mixing time of the
probability transition matrix of all policies is at most $t_\mathrm{mix}$, we
provide an algorithm that solves the problem using
$\widetilde{O}(t_\mathrm{mix} \epsilon^{-3})$ (oblivious) samples per
state-action pair. Further, we provide a lower bound showing that a linear
dependence on $t_\mathrm{mix}$ is necessary in the worst case for any algorithm
which computes oblivious samples. We obtain our results by establishing
connections between infinite-horizon average-reward MDPs and discounted MDPs of
possible further utility.
- Abstract（参考訳）: 生成モデルにアクセスできる無限水平平均回帰マルコフ決定過程 (MDP) において,$\epsilon$-optimal Policy を求める場合のサンプルの複雑さに対して,新しい上限と下位境界を証明した。
すべてのポリシーの確率遷移行列の混合時間が最大$t_\mathrm{mix}$である場合、状態-アクションペアあたり$\widetilde{o}(t_\mathrm{mix} \epsilon^{-3})$ (oblivious) サンプルを使用して問題を解決するアルゴリズムを提供する。
さらに,不明瞭なサンプルを計算するアルゴリズムでは,最悪の場合,$t_\mathrm{mix}$ に対する線形依存が必要であることを示す下限を与える。
我々は,無限水平平均回帰MDPと割引MDPの接続を確立することで,さらなる有用性を実現する。
関連論文リスト
- Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Span [16.49229317664822]
本稿では,無限水平平均逆線形混合マルコフ決定過程(MDPs)を学習するための計算抽出可能なアルゴリズムを提案する。
線形混合MDPのアルゴリズムは,$widetildemathcalO(dsqrtmathrmsp(v*)T)$$$T$以上の最小限の後悔上限を実現する。
論文 参考訳（メタデータ） (2024-10-19T05:45:50Z) - 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) - 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) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Near-Optimal Sample Complexity Bounds for Constrained MDPs [25.509556551558834]
減算CMDPにおける準最適政策を学習するために,サンプルの複雑さを極小値と下位値で表す。
CMDPの学習は,少ない制約違反を許す場合と同等に容易であるが,制約違反を要求しない場合には本質的に困難であることを示す。
論文 参考訳（メタデータ） (2022-06-13T15:58:14Z) - Settling the Sample Complexity of Model-Based Offline Reinforcement
Learning [50.5790774201146]
オフライン強化学習(RL)は、事前収集されたデータを用いて、さらなる探索を行わずに学習する。
事前のアルゴリズムや分析は、最適なサンプルの複雑さに悩まされるか、サンプルの最適性に到達するために高いバーンインコストがかかるかのいずれかである。
モデルベース(あるいは"プラグイン")アプローチは,バーンインコストを伴わずに,最小限のサンプル複雑性を実現することを実証する。
論文 参考訳（メタデータ） (2022-04-11T17:26:19Z) - Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov
Decision Processes [61.11090361892306]
Reward-free reinforcement learning (RL) は、エージェントが探索中に報酬関数にアクセスできないような環境を考える。
この分離は線形MDPの設定には存在しないことを示す。
我々は$d$次元線形 MDP における報酬のない RL に対する計算効率の良いアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-01-26T22:09:59Z) - Efficiently Solving MDPs with Stochastic Mirror Descent [38.30919646721354]
線形モデルに与えられた無限水平マルコフ決定過程(MDP)を近似的に解くための統一的な枠組みを提案する。
これらの結果は、より一般的なミラー降下フレームワークを用いて、単純なドメインとボックスドメインで大域的なサドルポイント問題を解くことによって達成される。
論文 参考訳（メタデータ） (2020-08-28T17:58:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。