論文の概要: Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path
- arxiv url: http://arxiv.org/abs/2402.08998v1
- Date: Wed, 14 Feb 2024 07:52:00 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-15 16:33:12.074235
- Title: Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path
- Title（参考訳）: 線形混合確率的最短経路学習のための最短最適後悔
- Authors: Qiwei Di, Jiafan He, Dongruo Zhou, Quanquan Gu
- Abstract要約: 線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
- 参考スコア（独自算出の注目度）: 80.60592344361073
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the Stochastic Shortest Path (SSP) problem with a linear mixture
transition kernel, where an agent repeatedly interacts with a stochastic
environment and seeks to reach certain goal state while minimizing the
cumulative cost. Existing works often assume a strictly positive lower bound of
the cost function or an upper bound of the expected length for the optimal
policy. In this paper, we propose a new algorithm to eliminate these
restrictive assumptions. Our algorithm is based on extended value iteration
with a fine-grained variance-aware confidence set, where the variance is
estimated recursively from high-order moments. Our algorithm achieves an
$\tilde{\mathcal O}(dB_*\sqrt{K})$ regret bound, where $d$ is the dimension of
the feature mapping in the linear transition kernel, $B_*$ is the upper bound
of the total cumulative cost for the optimal policy, and $K$ is the number of
episodes. Our regret upper bound matches the $\Omega(dB_*\sqrt{K})$ lower bound
of linear mixture SSPs in Min et al. (2022), which suggests that our algorithm
is nearly minimax optimal.
- Abstract（参考訳）: 本研究では, エージェントが繰り返し確率環境と相互作用し, 累積コストを最小化しつつ, ある目標状態に到達しようとする線形混合遷移カーネルを用いて, 確率的短経路(SSP)問題を考察する。
既存の作業はしばしば、コスト関数の厳密な正の下位境界や、最適ポリシーに対する期待される長さの上限を仮定する。
本稿では,これらの制約的仮定を解消する新しいアルゴリズムを提案する。
本アルゴリズムは,高次モーメントから分散を再帰的に推定する細粒度分散認識信頼セットを用いた拡張値反復に基づく。
このアルゴリズムは$\tilde{\mathcal o}(db_*\sqrt{k})$ regretboundを実現し、ここで$d$は線形遷移核における特徴マッピングの次元、$b_*$は最適方針の累積コストの上限、$k$はエピソード数である。
我々の後悔の上界は、Min et al. (2022) における線形混合 SSP の下界$\Omega(dB_*\sqrt{K})$ と一致する。
関連論文リスト
- Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Span [16.49229317664822]
本稿では,無限水平平均逆線形混合マルコフ決定過程(MDPs)を学習するための計算抽出可能なアルゴリズムを提案する。
線形混合MDPのアルゴリズムは,$widetildemathcalO(dsqrtmathrmsp(v*)T)$$$T$以上の最小限の後悔上限を実現する。
論文 参考訳（メタデータ） (2024-10-19T05:45:50Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Learning Stochastic Shortest Path with Linear Function Approximation [74.08819218747341]
線形関数近似を用いた強化学習における最短経路 (SSP) 問題について検討し, 遷移カーネルを未知モデルの線形混合として表現する。
本稿では,線形混合SSPを学習するための新しいアルゴリズムを提案し,このアルゴリズムにより,$tilde O(d B_star1.5sqrtK/c_min)$ regretを実現する。
論文 参考訳（メタデータ） (2021-10-25T08:34:00Z) - Regret Bounds for Stochastic Shortest Path Problems with Linear Function
Approximation [29.549633678730054]
線形関数近似を用いたエピソディック最短経路問題に対する2つのアルゴリズムを提案する。
1つは計算コストが高いが、$tildeo (sqrtb_star3 d3 k/cmin )$ regret が得られる。
2つ目は実際は計算的に効率的であり、同じ後悔境界が得られると推測する。
論文 参考訳（メタデータ） (2021-05-04T16:05:08Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。