論文の概要: Stochastic Shortest Path with Adversarially Changing Costs
- arxiv url: http://arxiv.org/abs/2006.11561v4
- Date: Tue, 5 Apr 2022 10:29:29 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-18 22:10:28.538443
- Title: Stochastic Shortest Path with Adversarially Changing Costs
- Title（参考訳）: コスト変動に伴う確率的最短経路
- Authors: Aviv Rosenberg and Yishay Mansour
- Abstract要約: 最短経路 (SSP) は計画と制御においてよく知られた問題である。
また, 時間とともにコストの逆変化を考慮に入れた逆SSPモデルを提案する。
我々は、この自然な逆SSPの設定を最初に検討し、それに対するサブ線形後悔を得る。
- 参考スコア（独自算出の注目度）: 57.90236104782219
- 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 this paper we present the adversarial SSP model that also accounts for
adversarial changes in the costs over time, while the underlying transition
function remains unchanged. Formally, an agent interacts with an SSP
environment for $K$ episodes, the cost function changes arbitrarily between
episodes, and the transitions are unknown to the agent. We develop the first
algorithms for adversarial SSPs and prove high probability regret bounds of
$\widetilde O (\sqrt{K})$ assuming all costs are strictly positive, and
$\widetilde O (K^{3/4})$ in the general case. We are the first to consider this
natural setting of adversarial SSP and obtain sub-linear regret for it.
- Abstract（参考訳）: 確率的最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。
本稿では,コストの時間的変動を考慮した逆SSPモデルを提案するが,その基礎となる遷移関数は変化しない。
正式には、エージェントは$K$のエピソードに対してSSP環境と対話し、コスト関数はエピソード間で任意に変化し、エージェントへの遷移は未知となる。
我々は,逆sspに対する最初のアルゴリズムを開発し,すべてのコストが厳密に正であるとして$\widetilde o (\sqrt{k})$ と$\widetilde o (k^{3/4})$ という高い確率の後悔限界を証明する。
我々は、この自然な逆SSPの設定を最初に検討し、それに対するサブ線形後悔を得る。
関連論文リスト
- Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit
Feedback and Unknown Transition [71.33787410075577]
線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。
我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-03-07T15:03:50Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - 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) - Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。
任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
論文 参考訳（メタデータ） (2020-02-23T09:10:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。