論文の概要: Near-optimal Regret Bounds for Stochastic Shortest Path

• arxiv url: http://arxiv.org/abs/2002.09869v1
• Date: Sun, 23 Feb 2020 09:10:14 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-29 09:21:05.748245
• Title: Near-optimal Regret Bounds for Stochastic Shortest Path
• Title（参考訳）: 確率的最短経路に対する準最適回帰境界
• Authors: Alon Cohen, Haim Kaplan, Yishay Mansour and Aviv Rosenberg
• Abstract要約: 最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。 任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
• 参考スコア（独自算出の注目度）: 63.029132134792555
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Stochastic shortest path (SSP) is a well-known problem in planning and control, in which an agent has to reach a goal state in minimum total expected cost. In the learning formulation of the problem, the agent is unaware of the environment dynamics (i.e., the transition function) and has to repeatedly play for a given number of episodes while reasoning about the problem's optimal solution. Unlike other well-studied models in reinforcement learning (RL), the length of an episode is not predetermined (or bounded) and is influenced by the agent's actions. Recently, Tarbouriech et al. (2019) studied this problem in the context of regret minimization and provided an algorithm whose regret bound is inversely proportional to the square root of the minimum instantaneous cost. In this work we remove this dependence on the minimum cost---we give an algorithm that guarantees a regret bound of $\widetilde{O}(B_\star |S| \sqrt{|A| K})$, where $B_\star$ is an upper bound on the expected cost of the optimal policy, $S$ is the set of states, $A$ is the set of actions and $K$ is the number of episodes. We additionally show that any learning algorithm must have at least $\Omega(B_\star \sqrt{|S| |A| K})$ regret in the worst case.
• Abstract（参考訳）: 確率的最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。 問題の学習定式化において、エージェントは、環境力学(すなわち遷移関数)に気付かず、問題の最適解を推論しながら、所定の回数のエピソードに対して繰り返しプレーしなければならない。 強化学習(RL)における他のよく研究されたモデルとは異なり、エピソードの長さは所定の(あるいは境界づけられた)ものではなく、エージェントの行動に影響される。 最近、tarbouriech et al. (2019)は、後悔の最小化の文脈でこの問題を研究し、最小の瞬時コストの平方根に対して、後悔の境界が逆比例するアルゴリズムを提供した。 この作業では、この最小コストへの依存を排除し、$\widetilde{O}(B_\star |S| \sqrt{|A| K})$, where $B_\star$ is a upper bound on the expected cost of the optimal policy, $S$ is the set of state, $A$ is the set of action and $K$ is the number of episodes。 さらに、最悪の場合、任意の学習アルゴリズムは少なくとも$\omega(b_\star \sqrt{|s||a|k})$ regretを持つ必要があることを示す。

関連論文リスト

• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
  本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。 ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。 我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
  論文  参考訳（メタデータ） (2023-02-07T02:22:31Z)
• Minimal Expected Regret in Linear Quadratic Control [79.81807680370677]
  オンライン学習アルゴリズムを考案し、その期待された後悔を保証します。 当時のこの後悔は、$A$と$B$が未知の場合、$widetildeO((d_u+d_x)sqrtd_xT)$によって上界(i)となる。
  論文  参考訳（メタデータ） (2021-09-29T14:07:21Z)
• 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)
• 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)
• Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case [29.99619764839178]
  敵の費用と未知の遷移を伴う最短経路問題に対して,大きな進展をみせている。 具体的には、全情報設定を後悔する$widetildeO(sqrtS3A2DT_star K)を実現するアルゴリズムを開発する。 私たちはまた、最も難しい組み合わせとして、敵のコストによる盗聴フィードバックと未知の移行を最初に検討しています。
  論文  参考訳（メタデータ） (2021-02-10T06:33:04Z)
• Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition [37.6975819766632]
  我々は、敵対コストと既知の移行で最短経路問題を研究します。 ミニマックスの後悔は,全情報設定と盗聴フィードバック設定に対して$widetildeO(sqrtDTstar K)$および$widetildeO(sqrtDTstar SA K)$であることを示す。
  論文  参考訳（メタデータ） (2020-12-07T20:55:28Z)

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

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