論文の概要: Online Learning for Stochastic Shortest Path Model via Posterior Sampling

• arxiv url: http://arxiv.org/abs/2106.05335v1
• Date: Wed, 9 Jun 2021 18:46:39 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-13 01:49:22.312119
• Title: Online Learning for Stochastic Shortest Path Model via Posterior Sampling
• Title（参考訳）: 後方サンプリングによる確率的最短経路モデルのオンライン学習
• Authors: Mehdi Jafarnia-Jahromi, Liyu Chen, Rahul Jain, Haipeng Luo
• Abstract要約: PSRL-SSPは、最短経路(SSP)問題に対する後方サンプリングに基づく強化学習アルゴリズムである。 これはそのような後方サンプリングアルゴリズムとしては初めてであり、これまで提案されていた楽観主義に基づくアルゴリズムよりも優れている。
• 参考スコア（独自算出の注目度）: 29.289190242826688
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of online reinforcement learning for the Stochastic Shortest Path (SSP) problem modeled as an unknown MDP with an absorbing state. We propose PSRL-SSP, a simple posterior sampling-based reinforcement learning algorithm for the SSP problem. The algorithm operates in epochs. At the beginning of each epoch, a sample is drawn from the posterior distribution on the unknown model dynamics, and the optimal policy with respect to the drawn sample is followed during that epoch. An epoch completes if either the number of visits to the goal state in the current epoch exceeds that of the previous epoch, or the number of visits to any of the state-action pairs is doubled. We establish a Bayesian regret bound of $O(B_\star S\sqrt{AK})$, where $B_\star$ is an upper bound on the expected cost of the optimal policy, $S$ is the size of the state space, $A$ is the size of the action space, and $K$ is the number of episodes. The algorithm only requires the knowledge of the prior distribution, and has no hyper-parameters to tune. It is the first such posterior sampling algorithm and outperforms numerically previously proposed optimism-based algorithms.
• Abstract（参考訳）: 吸収状態を持つ未知のMDPとしてモデル化された確率的短経路問題(SSP)に対するオンライン強化学習の問題点を考察する。 SSP問題に対する単純な後方サンプリングに基づく強化学習アルゴリズムであるPSRL-SSPを提案する。 アルゴリズムはエポックで動作します。 各エポックの開始時に、未知のモデルダイナミクスの後方分布からサンプルを抽出し、そのエポックの間、この描画されたサンプルに対する最適なポリシーに従う。 エポックは、現在のエポックにおけるゴール状態への訪問回数が前のエポックの訪問回数を超えるか、またはいずれかのステート-アクションペアへの訪問回数が倍になる場合に完了する。 ここで、$b_\star$は、最適なポリシーの期待されるコストの上限であり、$s$は、状態空間のサイズであり、$a$は、アクション空間のサイズであり、$k$は、エピソードの数である。 このアルゴリズムは、事前分布の知識のみを必要とし、チューニングするハイパーパラメータを持たない。 この種の後方サンプリングアルゴリズムとしては初めてであり、これまで提案されていたオプティミズムに基づくアルゴリズムよりも優れていた。

関連論文リスト

• Finite-Sample Analysis of the Monte Carlo Exploring Starts Algorithm for Reinforcement Learning [0.0]
  政策アルゴリズムの収束率に関する新しい結果を示す。 このアルゴリズムは、$tildeO(SAK3log3frac1delta)$ sampled episodesの後に最適なポリシーを返す。
  論文  参考訳（メタデータ） (2024-10-03T21:11:29Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Bayesian Learning of Optimal Policies in Markov Decision Processes with Countably Infinite State-Space [0.0]
  離散時間可算状態空間マルコフ決定過程の族を最適に制御する問題について検討する。 動的サイズのエピソードを用いたトンプソンサンプリングに基づくアルゴリズムを提案する。 提案アルゴリズムは, 近似最適制御アルゴリズムの開発に応用可能であることを示す。
  論文  参考訳（メタデータ） (2023-06-05T03:57:16Z)
• 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)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• 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)
• 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)
• Model-based Reinforcement Learning for Continuous Control with Posterior Sampling [10.91557009257615]
  連続状態空間における強化学習(PSRL)のためのモデルベース後方サンプリングについて検討した。 MPC-PSRLはモデルに基づく後部サンプリングアルゴリズムであり,行動選択のためのモデル予測制御を行う。
  論文  参考訳（メタデータ） (2020-11-20T21:00:31Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。 最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。 対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
  論文  参考訳（メタデータ） (2020-05-26T17:53:18Z)

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

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