論文の概要: A Unified Algorithm for Stochastic Path Problems

• arxiv url: http://arxiv.org/abs/2210.09255v1
• Date: Mon, 17 Oct 2022 16:56:54 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-18 17:15:12.119200
• Title: A Unified Algorithm for Stochastic Path Problems
• Title（参考訳）: 確率パス問題の統一アルゴリズム
• Authors: Christoph Dann, Chen-Yu Wei, Julian Zimmert
• Abstract要約: 経路(SP)問題における強化学習について検討する。 これらの問題の目標は、エージェントが終端状態に到達するまで、期待される報酬の総和を最大化することである。 簡単な楽観的アルゴリズムを解析することにより,この問題に対する最初の後悔の保証を提供する。
• 参考スコア（独自算出の注目度）: 33.13041034490332
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study reinforcement learning in stochastic path (SP) problems. The goal in these problems is to maximize the expected sum of rewards until the agent reaches a terminal state. We provide the first regret guarantees in this general problem by analyzing a simple optimistic algorithm. Our regret bound matches the best known results for the well-studied special case of stochastic shortest path (SSP) with all non-positive rewards. For SSP, we present an adaptation procedure for the case when the scale of rewards $B_\star$ is unknown. We show that there is no price for adaptation, and our regret bound matches that with a known $B_\star$. We also provide a scale adaptation procedure for the special case of stochastic longest paths (SLP) where all rewards are non-negative. However, unlike in SSP, we show through a lower bound that there is an unavoidable price for adaptation.
• Abstract（参考訳）: 確率経路問題における強化学習について検討した。 これらの問題の目標は、エージェントが終端状態に到達するまで、期待される報酬の総和を最大化することである。 簡単な楽観的アルゴリズムを解析することにより,この問題に対する最初の後悔の保証を提供する。 我々の後悔の束縛は、すべての非肯定的な報酬を伴う確率的短大経路(ssp)の、よく研究された特別な場合の最もよく知られた結果と一致する。 SSPの場合、報酬のスケールがB_\star$である場合の適応手順を示す。 我々は適応の代償がないことを示し、我々の後悔は既知の$B_\star$と一致している。 また,全ての報酬が非負である確率的最長経路(SLP)の特殊症例に対するスケール適応法も提案する。 しかし、SSPとは異なり、適応には避けられない価格があることが低い境界を通して示される。

関連論文リスト

• Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
  報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。 Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。 特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
  論文  参考訳（メタデータ） (2024-03-15T23:36:55Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• $(\epsilon, u)$-Adaptive Regret Minimization in Heavy-Tailed Bandits [29.966828248335972]
  我々は,学習者に対して,$epsilon$と$u$が不明な場合に,後悔の最小化問題を調査する。 AdaR-UCBは、適応しない重みを帯びたケースとほぼ一致した後悔の保証を享受する最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2023-10-04T17:11:15Z)
• Reward Learning as Doubly Nonparametric Bandits: Optimal Design and Scaling Laws [22.099915149343957]
  本稿では、報酬学習と関連する最適実験設計問題を研究するための理論的枠組みを提案する。 まず、リッジ回帰に基づく単純なプラグイン推定器の非漸近的過剰リスク境界を導出する。 次に、クエリセットの選択に関してこれらのリスク境界を最適化し、有限サンプル統計率を得ることにより、クエリ設計問題を解決する。
  論文  参考訳（メタデータ） (2023-02-23T22:07:33Z)
• 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)
• Stochastic Shortest Path with Adversarially Changing Costs [57.90236104782219]
  最短経路 (SSP) は計画と制御においてよく知られた問題である。 また, 時間とともにコストの逆変化を考慮に入れた逆SSPモデルを提案する。 我々は、この自然な逆SSPの設定を最初に検討し、それに対するサブ線形後悔を得る。
  論文  参考訳（メタデータ） (2020-06-20T12:10:35Z)
• Optimistic Policy Optimization with Bandit Feedback [70.75568142146493]
  我々は,事前の報奨を後悔する$tilde O(sqrtS2 A H4 K)を定め,楽観的な信頼領域ポリシー最適化(TRPO)アルゴリズムを提案する。 我々の知る限り、この2つの結果は、未知の遷移と帯域幅フィードバックを持つポリシー最適化アルゴリズムにおいて得られた最初のサブ線形後悔境界である。
  論文  参考訳（メタデータ） (2020-02-19T15:41:18Z)
• A General Theory of the Stochastic Linear Bandit and Its Applications [8.071506311915398]
  本稿では,線形バンディット問題に対する一般解析フレームワークとアルゴリズム群を紹介する。 予測における最適化という新たな概念は、OFULの過剰探索問題を減少させるSieeved greedy(SG)と呼ばれる新しいアルゴリズムを生み出します。 SGが理論的に最適であることを示すことに加えて、実験シミュレーションにより、SGはgreedy、OFUL、TSといった既存のベンチマークよりも優れていることが示された。
  論文  参考訳（メタデータ） (2020-02-12T18:54:41Z)

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

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