論文の概要: Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret

• arxiv url: http://arxiv.org/abs/2104.11186v1
• Date: Thu, 22 Apr 2021 17:20:48 GMT
• ステータス: 処理完了
• システム内更新日: 2021-04-23 13:48:59.423438
• Title: Stochastic Shortest Path: Minimax, Parameter-Free and Towards Horizon-Free Regret
• Title（参考訳）: 確率的最短経路:ミニマックス,パラメータフリーおよび水平自由回帰に向けて
• Authors: Jean Tarbouriech, Runlong Zhou, Simon S. Du, Matteo Pirotta, Michal Valko, Alessandro Lazaric
• Abstract要約: エージェントが目標状態に到達する前に蓄積される期待コストを最小限に抑えるために,最短経路(ssp)設定で学習する問題について検討する。 我々は,経験的遷移を慎重に歪曲し,探索ボーナスで経験的コストを摂動する新しいモデルベースアルゴリズムEB-SSPを設計する。 私達はEB-SSPが$widetildeO(B_star sqrtS A K)$のミニマックスの後悔率を達成することを証明します。
• 参考スコア（独自算出の注目度）: 144.6358229217845
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of learning in the stochastic shortest path (SSP) setting, where an agent seeks to minimize the expected cost accumulated before reaching a goal state. We design a novel model-based algorithm EB-SSP that carefully skews the empirical transitions and perturbs the empirical costs with an exploration bonus to guarantee both optimism and convergence of the associated value iteration scheme. We prove that EB-SSP achieves the minimax regret rate $\widetilde{O}(B_{\star} \sqrt{S A K})$, where $K$ is the number of episodes, $S$ is the number of states, $A$ is the number of actions and $B_{\star}$ bounds the expected cumulative cost of the optimal policy from any state, thus closing the gap with the lower bound. Interestingly, EB-SSP obtains this result while being parameter-free, i.e., it does not require any prior knowledge of $B_{\star}$, nor of $T_{\star}$ which bounds the expected time-to-goal of the optimal policy from any state. Furthermore, we illustrate various cases (e.g., positive costs, or general costs when an order-accurate estimate of $T_{\star}$ is available) where the regret only contains a logarithmic dependence on $T_{\star}$, thus yielding the first horizon-free regret bound beyond the finite-horizon MDP setting.
• Abstract（参考訳）: エージェントが目標状態に到達する前に蓄積される期待コストを最小化しようとする確率的短経路(ssp)設定における学習の問題について検討する。 我々は,経験的遷移を慎重に歪め,探索ボーナスで経験的コストを摂動させ,関連する値反復スキームの最適化と収束を両立させる新しいモデルベースアルゴリズムEB-SSPを設計する。 EB-SSP が minimax regret rate $\widetilde{O}(B_{\star} \sqrt{S A K})$, where $K$ is the number of episodes, $S$ is the number of state, $A$ is the number of action and $B_{\star}$ bounds the expected cumulative cost of the optimal policy from any state。 興味深いことに、EB-SSPはパラメータフリーでありながらこの結果を得る、すなわち、任意の状態からの最適ポリシーの期待時間とゴールを束縛する$B_{\star}$や$T_{\star}$の事前知識を必要としない。 さらに、様々なケース(例えば、$T_{\star}$のオーダー精度の推定値が利用可能である場合の正のコストや一般的なコストなど)について、後悔は$T_{\star}$に対する対数依存のみを含むので、有限ホリゾン MDP 設定を超えて、最初の地平面自由な後悔をもたらす。

関連論文リスト

• Improved Regret Bound for Safe Reinforcement Learning via Tighter Cost Pessimism and Reward Optimism [1.4999444543328293]
  本稿では,新しいコストと報酬関数推定器に基づくモデルベースアルゴリズムを提案する。 我々のアルゴリズムは、$widetildemathcalO((bar C - bar C_b)-1H2.5 SsqrtAK)$の残念な上限を達成する。
  論文  参考訳（メタデータ） (2024-10-14T04:51:06Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• 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)
• 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)
• 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)
• Stochastic Shortest Path with Adversarially Changing Costs [57.90236104782219]
  最短経路 (SSP) は計画と制御においてよく知られた問題である。 また, 時間とともにコストの逆変化を考慮に入れた逆SSPモデルを提案する。 我々は、この自然な逆SSPの設定を最初に検討し、それに対するサブ線形後悔を得る。
  論文  参考訳（メタデータ） (2020-06-20T12:10:35Z)
• Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
  最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。 任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
  論文  参考訳（メタデータ） (2020-02-23T09:10:14Z)

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

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