論文の概要: Finding good policies in average-reward Markov Decision Processes without prior knowledge

• arxiv url: http://arxiv.org/abs/2405.17108v1
• Date: Mon, 27 May 2024 12:24:14 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-28 15:32:42.523092
• Title: Finding good policies in average-reward Markov Decision Processes without prior knowledge
• Title（参考訳）: 事前知識のない平均回帰マルコフ決定過程における良い政策の発見
• Authors: Adrienne Tuynman, Rémy Degenne, Emilie Kaufmann,
• Abstract要約: 平均回帰決定(MDP)における$varepsilon$-Optimal Policyの同定を再考する。 直径推定法を用いて,$(varepsilon,delta)$-PAC-PACポリシー識別のための最初のアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 19.89784209009327
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We revisit the identification of an $\varepsilon$-optimal policy in average-reward Markov Decision Processes (MDP). In such MDPs, two measures of complexity have appeared in the literature: the diameter, $D$, and the optimal bias span, $H$, which satisfy $H\leq D$. Prior work have studied the complexity of $\varepsilon$-optimal policy identification only when a generative model is available. In this case, it is known that there exists an MDP with $D \simeq H$ for which the sample complexity to output an $\varepsilon$-optimal policy is $\Omega(SAD/\varepsilon^2)$ where $S$ and $A$ are the sizes of the state and action spaces. Recently, an algorithm with a sample complexity of order $SAH/\varepsilon^2$ has been proposed, but it requires the knowledge of $H$. We first show that the sample complexity required to estimate $H$ is not bounded by any function of $S,A$ and $H$, ruling out the possibility to easily make the previous algorithm agnostic to $H$. By relying instead on a diameter estimation procedure, we propose the first algorithm for $(\varepsilon,\delta)$-PAC policy identification that does not need any form of prior knowledge on the MDP. Its sample complexity scales in $SAD/\varepsilon^2$ in the regime of small $\varepsilon$, which is near-optimal. In the online setting, our first contribution is a lower bound which implies that a sample complexity polynomial in $H$ cannot be achieved in this setting. Then, we propose an online algorithm with a sample complexity in $SAD^2/\varepsilon^2$, as well as a novel approach based on a data-dependent stopping rule that we believe is promising to further reduce this bound.
• Abstract（参考訳）: 我々は、平均回帰マルコフ決定過程(MDP)における$\varepsilon$-optimal Policyの同定を再考する。 そのようなMDPでは、直径、$D$、最適バイアス幅、$H$という2つの複雑さの尺度が文献に現れており、これは$H\leq D$を満たす。 以前の研究は、生成モデルが利用可能である場合にのみ、$\varepsilon$-Optimal Policy IDの複雑さについて研究してきた。 この場合、$D \simeq H$ の MDP が存在し、$\varepsilon$-optimal policy を出力するサンプルの複雑さは $\Omega(SAD/\varepsilon^2)$ であり、$S$ と $A$ は状態空間と行動空間のサイズである。 近年、サンプル複雑性が$SAH/\varepsilon^2$のアルゴリズムが提案されているが、その知識は$H$である。 まず最初に、$H$を見積るために必要なサンプルの複雑さは、$S,A$と$H$の任意の関数によって境界づけられていないことを示し、以前のアルゴリズムを$H$に非依存にすることができる可能性を除外する。 直径推定法に代えて,MDPの事前知識を必要としない$(\varepsilon,\delta)$-PACポリシー識別のための最初のアルゴリズムを提案する。 サンプルの複雑さは、ほぼ最適である小さな$\varepsilon$の状態で、SAD/\varepsilon^2$でスケールする。 オンライン設定では、最初のコントリビューションは下界であり、これは、$H$のサンプル複雑性多項式がこの設定では達成できないことを意味する。 そこで我々は,SAD^2/\varepsilon^2$のサンプル複雑性を持つオンラインアルゴリズムを提案する。

関連論文リスト

• 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)
• Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path [106.37656068276902]
  本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。 学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。 我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
  論文  参考訳（メタデータ） (2022-10-10T18:34:32Z)
• 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)
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs [132.88757893161699]
  我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。 DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
  論文  参考訳（メタデータ） (2020-12-29T14:06:09Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。 十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
  論文  参考訳（メタデータ） (2020-06-06T13:34:41Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。