論文の概要: Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case

• arxiv url: http://arxiv.org/abs/2102.05284v1
• Date: Wed, 10 Feb 2021 06:33:04 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-11 14:47:49.238667
• Title: Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case
• Title（参考訳）: 低レグレト率の確率的最短経路の発見 : 逆行性コストと未知遷移例
• Authors: Liyu Chen and Haipeng Luo
• Abstract要約: 敵の費用と未知の遷移を伴う最短経路問題に対して,大きな進展をみせている。 具体的には、全情報設定を後悔する$widetildeO(sqrtS3A2DT_star K)を実現するアルゴリズムを開発する。 私たちはまた、最も難しい組み合わせとして、敵のコストによる盗聴フィードバックと未知の移行を最初に検討しています。
• 参考スコア（独自算出の注目度）: 29.99619764839178
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We make significant progress toward the stochastic shortest path problem with adversarial costs and unknown transition. Specifically, we develop algorithms that achieve $\widetilde{O}(\sqrt{S^2ADT_\star K})$ regret for the full-information setting and $\widetilde{O}(\sqrt{S^3A^2DT_\star K})$ regret for the bandit feedback setting, where $D$ is the diameter, $T_\star$ is the expected hitting time of the optimal policy, $S$ is the number of states, $A$ is the number of actions, and $K$ is the number of episodes. Our work strictly improves (Rosenberg and Mansour, 2020) in the full information setting, extends (Chen et al., 2020) from known transition to unknown transition, and is also the first to consider the most challenging combination: bandit feedback with adversarial costs and unknown transition. To remedy the gap between our upper bounds and the current best lower bounds constructed via a stochastically oblivious adversary, we also propose algorithms with near-optimal regret for this special case.
• Abstract（参考訳）: 逆境コストと未知の遷移を伴う確率的最短経路問題に向けて大きな進展を遂げる。 具体的には、$\widetilde{o}(\sqrt{s^2adt_\star k})$全情報設定に対する後悔と$\widetilde{o}(\sqrt{s^3a^2dt_\star k})$$d$が直径、$t_\star$が最適ポリシーの期待到達時間、$s$が状態数、$a$がアクション数、$k$がエピソード数であるバンディットフィードバック設定を後悔するアルゴリズムを開発する。 私たちの仕事は、完全な情報設定で(Rosenberg and Mansour, 2020)厳格に改善され、既知の遷移から未知の遷移へ(Chen et al., 2020)拡張され、また、最も難しい組み合わせとして、敵のコストによる盗聴フィードバックと未知の遷移を初めて検討する。 確率的に難解な対向を通して構築された上界と現在の最下界のギャップを補うために,この特別事例に対してほぼ最適に後悔するアルゴリズムを提案する。

関連論文リスト

• 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)
• Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary Environments [40.027926921772355]
  目標指向強化学習における動的後悔の研究を行う。 この下位境界における$Delta_c$と$Delta_P$の異なる役割は、コストと遷移を別々に見積もるアルゴリズムを設計するきっかけとなった。
  論文  参考訳（メタデータ） (2022-05-25T20:29:01Z)
• Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits [99.86860277006318]
  本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。 Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。 この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
  論文  参考訳（メタデータ） (2022-02-12T21:55:44Z)
• The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition [49.78053380710322]
  我々は,エピソードT$でマルコフ決定過程を学習する上で,両世界の最良の問題を考える。 最近の[Jin and Luo, 2020]による研究は、固定遷移が分かっているときにこの目標を達成する。 本研究では,同じFollow-the-Regularized-Leader(textFTRL$)フレームワークを新しいテクニックのセットと組み合わせることで,この問題を解決する。
  論文  参考訳（メタデータ） (2021-06-08T05:46:35Z)
• 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)
• Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition [38.28925339231888]
  我々は,世界最良保証付きの最初のアルゴリズムを開発した。 損失が逆ならば、$mathcalO(log T)$ regretを達成します。 より一般的には、中間設定で $tildemathcalO(sqrtC)$ regret を達成する。
  論文  参考訳（メタデータ） (2020-06-10T01:59:34Z)
• Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
  最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。 任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
  論文  参考訳（メタデータ） (2020-02-23T09:10:14Z)

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

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