論文の概要: Minimax Regret for Stochastic Shortest Path
- arxiv url: http://arxiv.org/abs/2103.13056v1
- Date: Wed, 24 Mar 2021 10:11:49 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-25 13:52:45.586019
- Title: Minimax Regret for Stochastic Shortest Path
- Title（参考訳）: 確率的最短経路に対する Minimax Regret
- Authors: Alon Cohen, Yonathan Efroni, Yishay Mansour and Aviv Rosenberg
- Abstract要約: 我々は、エージェントが最小の総予想コストで目標状態に達する必要がある最短パス(SSP)問題を研究します。
この設定に対するminimaxの後悔は、$widetilde O(B_star sqrt|S| |A|K)$であり、$B_star$は任意の状態から最適なポリシーの予想コストに拘束されることを示しています。
本アルゴリズムは, 有限水平MDPにおける強化学習の新たな削減を基礎として, エピソードごとのインタイム動作を行う。
- 参考スコア（独自算出の注目度）: 63.45407095296692
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the Stochastic Shortest Path (SSP) problem in which an agent has to
reach a goal state in minimum total expected cost. In the learning formulation
of the problem, the agent has no prior knowledge about the costs and dynamics
of the model. She repeatedly interacts with the model for $K$ episodes, and has
to learn to approximate the optimal policy as closely as possible. In this work
we show that the minimax regret for this setting is $\widetilde O(B_\star
\sqrt{|S| |A| K})$ where $B_\star$ is a bound on the expected cost of the
optimal policy from any state, $S$ is the state space, and $A$ is the action
space. This matches the lower bound of Rosenberg et al. (2020) up to
logarithmic factors, and improves their regret bound by a factor of
$\sqrt{|S|}$. Our algorithm runs in polynomial-time per episode, and is based
on a novel reduction to reinforcement learning in finite-horizon MDPs. To that
end, we provide an algorithm for the finite-horizon setting whose leading term
in the regret depends only logarithmically on the horizon, yielding the same
regret guarantees for SSP.
- Abstract（参考訳）: 本稿では,エージェントが目標状態に到達しなければならない確率的短経路(SSP)問題を,最小総コストで検討する。
問題の学習定式化において、エージェントはモデルのコストとダイナミクスについて事前の知識を持っていない。
彼女は繰り返しこのモデルと$K$のエピソードをやりとりし、可能な限り最適なポリシーを近似することを学ぶ必要がある。
この研究において、この設定に対するミニマックスの後悔は、$\widetilde O(B_\star \sqrt{|S| |A| K})$ ここで、$B_\star$は任意の状態からの最適ポリシーの期待コストに縛られ、$S$は状態空間、$A$は行動空間であることを示す。
これはローゼンバーグらの下限と一致する。
(2020) 対数的因子まで到達し、その後悔を $\sqrt{|S|}$ の係数によって改善する。
本アルゴリズムは,有限ホライゾンmdpにおける強化学習に対する新しい還元法に基づいて,エピソード毎の多項式時間で動作する。
この目的を達成するために, 有限ホライズン設定に対するアルゴリズムを提案し, 後悔の先頭項は水平方向に対数的にのみ依存し, SSP に対して同じ後悔の保証を与える。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。
最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
論文 参考訳（メタデータ） (2023-07-25T15:42:11Z) - 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) - Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary
Environments [40.027926921772355]
目標指向強化学習における動的後悔の研究を行う。
この下位境界における$Delta_c$と$Delta_P$の異なる役割は、コストと遷移を別々に見積もるアルゴリズムを設計するきっかけとなった。
論文 参考訳（メタデータ） (2022-05-25T20:29:01Z) - 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 with Adversarial Costs and
Known Transition [37.6975819766632]
我々は、敵対コストと既知の移行で最短経路問題を研究します。
ミニマックスの後悔は,全情報設定と盗聴フィードバック設定に対して$widetildeO(sqrtDTstar K)$および$widetildeO(sqrtDTstar SA K)$であることを示す。
論文 参考訳（メタデータ） (2020-12-07T20:55:28Z) - Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。
任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
論文 参考訳（メタデータ） (2020-02-23T09:10:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。