論文の概要: Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation

• arxiv url: http://arxiv.org/abs/2105.01593v1
• Date: Tue, 4 May 2021 16:05:08 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-05 13:04:39.874197
• Title: Regret Bounds for Stochastic Shortest Path Problems with Linear Function Approximation
• Title（参考訳）: 線形関数近似を用いた確率的最短経路問題に対する後悔境界
• Authors: Daniel Vial, Advait Parulekar, Sanjay Shakkottai, R. Srikant
• Abstract要約: 線形関数近似を用いたエピソディック最短経路問題に対する2つのアルゴリズムを提案する。 1つは計算コストが高いが、$tildeo (sqrtb_star3 d3 k/cmin )$ regret が得られる。 2つ目は実際は計算的に効率的であり、同じ後悔境界が得られると推測する。
• 参考スコア（独自算出の注目度）: 29.549633678730054
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose two algorithms for episodic stochastic shortest path problems with linear function approximation. The first is computationally expensive but provably obtains $\tilde{O} (\sqrt{B_\star^3 d^3 K/c_{min}} )$ regret, where $B_\star$ is a (known) upper bound on the optimal cost-to-go function, $d$ is the feature dimension, $K$ is the number of episodes, and $c_{min}$ is the minimal cost of non-goal state-action pairs (assumed to be positive). The second is computationally efficient in practice, and we conjecture that it obtains the same regret bound. Both algorithms are based on an optimistic least-squares version of value iteration analogous to the finite-horizon backward induction approach from Jin et al. 2020. To the best of our knowledge, these are the first regret bounds for stochastic shortest path that are independent of the size of the state and action spaces.
• Abstract（参考訳）: 線形関数近似を用いた確率的最短経路問題に対する2つのアルゴリズムを提案する。 1つは計算コストが高いが、確実に$\tilde{O} (\sqrt{B_\star^3 d^3 K/c_{min}} )$ regret, where $B_\star$ is a (known) upper bound on the optimal cost-to-go function, $d$ is the feature dimension, $K$ is the number of episodes, $c_{min}$ is the minimal cost of non-goal state-action pairs ( assumed as be positive)。 2つ目は実際は計算的に効率的であり、同じ後悔境界が得られると推測する。 どちらのアルゴリズムも、ジンらによる有限水平後方帰納法に類似した楽観的な値反復の最小二乗バージョンに基づいている。 2020. 我々の知る限りでは、これらは状態と作用空間の大きさに依存しない確率的最短経路に対する最初の後悔の限界である。

関連論文リスト

• Achieving Tractable Minimax Optimal Regret in Average Reward MDPs [19.663336027878408]
  我々は,$widetildemathrmO(sqrtmathrmsp(h*) S A T)$のミニマックス最適後悔を伴う最初の抽出可能なアルゴリズムを提案する。 注目すべきは、我々のアルゴリズムは$mathrmsp(h*)$に関する事前情報を必要としないことである。
  論文  参考訳（メタデータ） (2024-06-03T11:53:44Z)
• Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation [67.8414514524356]
  本稿では,MNL関数近似を用いたMDPの新しいクラスについて検討し,状態空間上の確率分布の正当性を保証する。 非線型関数の導入は、計算効率と統計効率の両方において大きな課題を提起する。 我々は,$mathcalO(1)$$コストで同じ後悔を実現するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-27T11:31:54Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDP [31.62899359543925]
  線形MDPを用いた最短経路問題(SSP)に対する2つの新しい非回帰アルゴリズムを提案する。 我々の最初のアルゴリズムは計算効率が高く、後悔すべき$widetildeOleft(sqrtd3B_star2T_star Kright)$を達成している。 第2のアルゴリズムは計算的に非効率であるが、$T_starに依存しない$widetildeO(d3.5B_starsqrtK)$の最初の「水平な」後悔を実現する。
  論文  参考訳（メタデータ） (2021-12-18T06:47:31Z)
• Learning Stochastic Shortest Path with Linear Function Approximation [74.08819218747341]
  線形関数近似を用いた強化学習における最短経路 (SSP) 問題について検討し, 遷移カーネルを未知モデルの線形混合として表現する。 本稿では,線形混合SSPを学習するための新しいアルゴリズムを提案し,このアルゴリズムにより,$tilde O(d B_star1.5sqrtK/c_min)$ regretを実現する。
  論文  参考訳（メタデータ） (2021-10-25T08:34:00Z)
• Minimax Regret for Stochastic Shortest Path [63.45407095296692]
  我々は、エージェントが最小の総予想コストで目標状態に達する必要がある最短パス(SSP)問題を研究します。 この設定に対するminimaxの後悔は、$widetilde O(B_star sqrt|S| |A|K)$であり、$B_star$は任意の状態から最適なポリシーの予想コストに拘束されることを示しています。 本アルゴリズムは, 有限水平MDPにおける強化学習の新たな削減を基礎として, エピソードごとのインタイム動作を行う。
  論文  参考訳（メタデータ） (2021-03-24T10:11:49Z)
• Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
  最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。 任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
  論文  参考訳（メタデータ） (2020-02-23T09:10:14Z)

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

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