論文の概要: Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path

• arxiv url: http://arxiv.org/abs/2210.04946v1
• Date: Mon, 10 Oct 2022 18:34:32 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-12 13:35:29.718077
• Title: Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path
• Title（参考訳）: 目標達成は難しい - 確率的最短経路のサンプル複雑性を解決する
• Authors: Liyu Chen, Andrea Tirinzoni, Matteo Pirotta, Alessandro Lazaric
• Abstract要約: 本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。 学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。 我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
• 参考スコア（独自算出の注目度）: 106.37656068276902
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the sample complexity of learning an $\epsilon$-optimal policy in the Stochastic Shortest Path (SSP) problem. We first derive sample complexity bounds when the learner has access to a generative model. We show that there exists a worst-case SSP instance with $S$ states, $A$ actions, minimum cost $c_{\min}$, and maximum expected cost of the optimal policy over all states $B_{\star}$, where any algorithm requires at least $\Omega(SAB_{\star}^3/(c_{\min}\epsilon^2))$ samples to return an $\epsilon$-optimal policy with high probability. Surprisingly, this implies that whenever $c_{\min}=0$ an SSP problem may not be learnable, thus revealing that learning in SSPs is strictly harder than in the finite-horizon and discounted settings. We complement this result with lower bounds when prior knowledge of the hitting time of the optimal policy is available and when we restrict optimality by competing against policies with bounded hitting time. Finally, we design an algorithm with matching upper bounds in these cases. This settles the sample complexity of learning $\epsilon$-optimal polices in SSP with generative models. We also initiate the study of learning $\epsilon$-optimal policies without access to a generative model (i.e., the so-called best-policy identification problem), and show that sample-efficient learning is impossible in general. On the other hand, efficient learning can be made possible if we assume the agent can directly reach the goal state from any state by paying a fixed cost. We then establish the first upper and lower bounds under this assumption. Finally, using similar analytic tools, we prove that horizon-free regret is impossible in SSPs under general costs, resolving an open problem in (Tarbouriech et al., 2021c).
• Abstract（参考訳）: 確率的短経路 (ssp) 問題における$\epsilon$-optimal policy の学習のサンプル複雑性について検討した。 まず,学習者が生成モデルにアクセスできる場合に,サンプルの複雑性境界を導出する。 S$状態、$A$アクション、最小コスト$c_{\min}$、および全ての状態に対する最適ポリシーの最大期待コスト$B_{\star}$、任意のアルゴリズムが、高い確率で$\epsilon$-Optimalポリシーを返すために少なくとも$\Omega(SAB_{\star}^3/(c_{\min}\epsilon^2)のサンプルを必要とする、最悪のSSPインスタンスが存在することを示す。 驚くべきことに、$c_{\min}=0$のSSP問題はいつでも学習できないので、SSPでの学習は有限ホリゾンや割引設定よりも厳密である。 この結果は、最適政策の打点時間に関する事前知識が利用可能である場合や、限界打点時間を持つ政策と競合することによって最適性を制限した場合に、低い限界で補完する。 最後に,これらの場合の上限値に一致するアルゴリズムを設計する。 これにより、SSPにおける$\epsilon$-optimal Policesを生成モデルで学習する際の複雑さが解決される。 また、生成モデルにアクセスせずに$\epsilon$-optimalポリシーを学習する研究(いわゆる最良の政治識別問題)を開始し、サンプル効率のよい学習は一般に不可能であることを示す。 一方で、エージェントが固定コストを払えば、任意の状態から直接目標状態に到達することができると仮定すれば、効率的な学習が可能になる。 そして、この仮定の下で第一上界と下界を定めます。 最後に、同様の分析ツールを用いて、一般コスト下でのSSPでは地平面自由後悔は不可能であることが証明され(Tarbouriech et al., 2021c)。

関連論文リスト

• Finding good policies in average-reward Markov Decision Processes without prior knowledge [19.89784209009327]
  平均回帰決定(MDP)における$varepsilon$-Optimal Policyの同定を再考する。 直径推定法を用いて,$(varepsilon,delta)$-PAC-PACポリシー識別のための最初のアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-27T12:24:14Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes [21.77276136591518]
  我々はマルコフ決定過程(MDPs)のための証明可能なモデルフリー強化学習(RL)アルゴリズムを開発した。 シミュレータ設定では,$widetildeO left(fracSAmathrmsp(h*)epsilon2+fracS2Amathrmsp(h*)epsilon2right)$サンプルを用いて,$epsilon$-optimal Policyを求める。
  論文  参考訳（メタデータ） (2023-06-28T17:43:19Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structure [9.759209713196718]
  我々は、対応する最適$Q*$関数が低ランクであるMDPのクラスを考える。 より強い低階構造仮定の下では、生成モデル(LR-MCPI)と低階経験値イテレーション(LR-EVI)が、ランクに対して$tildeOleft((|S|+|A|)mathrmpoly(d,H)/epsilon2right)$の所望のサンプル複雑性を実現することが示されている。
  論文  参考訳（メタデータ） (2022-06-07T20:39:51Z)
• Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret [144.6358229217845]
  エージェントが目標状態に到達する前に蓄積される期待コストを最小限に抑えるために,最短経路(ssp)設定で学習する問題について検討する。 我々は,経験的遷移を慎重に歪曲し,探索ボーナスで経験的コストを摂動する新しいモデルベースアルゴリズムEB-SSPを設計する。 私達はEB-SSPが$widetildeO(B_star sqrtS A K)$のミニマックスの後悔率を達成することを証明します。
  論文  参考訳（メタデータ） (2021-04-22T17:20:48Z)
• 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)

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

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