論文の概要: Improved No-Regret Algorithms for Stochastic Shortest Path with Linear
MDP
- arxiv url: http://arxiv.org/abs/2112.09859v1
- Date: Sat, 18 Dec 2021 06:47:31 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-21 17:17:56.346340
- Title: Improved No-Regret Algorithms for Stochastic Shortest Path with Linear
MDP
- Title（参考訳）: 線形mdpを用いた確率的最短経路のno-regretアルゴリズムの改良
- Authors: Liyu Chen, Rahul Jain, Haipeng Luo
- Abstract要約: 線形MDPを用いた最短経路問題(SSP)に対する2つの新しい非回帰アルゴリズムを提案する。
我々の最初のアルゴリズムは計算効率が高く、後悔すべき$widetildeOleft(sqrtd3B_star2T_star Kright)$を達成している。
第2のアルゴリズムは計算的に非効率であるが、$T_starに依存しない$widetildeO(d3.5B_starsqrtK)$の最初の「水平な」後悔を実現する。
- 参考スコア（独自算出の注目度）: 31.62899359543925
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce two new no-regret algorithms for the stochastic shortest path
(SSP) problem with a linear MDP that significantly improve over the only
existing results of (Vial et al., 2021). Our first algorithm is computationally
efficient and achieves a regret bound
$\widetilde{O}\left(\sqrt{d^3B_{\star}^2T_{\star} K}\right)$, where $d$ is the
dimension of the feature space, $B_{\star}$ and $T_{\star}$ are upper bounds of
the expected costs and hitting time of the optimal policy respectively, and $K$
is the number of episodes. The same algorithm with a slight modification also
achieves logarithmic regret of order
$O\left(\frac{d^3B_{\star}^4}{c_{\min}^2\text{gap}_{\min}}\ln^5\frac{dB_{\star}
K}{c_{\min}} \right)$, where $\text{gap}_{\min}$ is the minimum sub-optimality
gap and $c_{\min}$ is the minimum cost over all state-action pairs. Our result
is obtained by developing a simpler and improved analysis for the
finite-horizon approximation of (Cohen et al., 2021) with a smaller
approximation error, which might be of independent interest. On the other hand,
using variance-aware confidence sets in a global optimization problem, our
second algorithm is computationally inefficient but achieves the first
"horizon-free" regret bound $\widetilde{O}(d^{3.5}B_{\star}\sqrt{K})$ with no
polynomial dependency on $T_{\star}$ or $1/c_{\min}$, almost matching the
$\Omega(dB_{\star}\sqrt{K})$ lower bound from (Min et al., 2021).
- Abstract（参考訳）: 線形MDPを用いた確率的最短経路(SSP)問題に対する2つの新しい非回帰アルゴリズムを導入し、既存の結果(Vial et al., 2021)よりも大幅に改善した。
最初のアルゴリズムは計算効率が良く、後悔に満ちた$\widetilde{o}\left(\sqrt{d^3b_{\star}^2t_{\star} k}\right)$(ここで$d$は特徴空間の次元、$b_{\star}$と$t_{\star}$は、それぞれ最適なポリシーの期待コストとヒットタイムの上限であり、$k$はエピソードの数である。
わずかに修正された同じアルゴリズムは、次数$O\left(\frac{d^3B_{\star}^4}{c_{\min}^2\text{gap}_{\min}}\ln^5\frac{dB_{\star} K}{c_{\min}} \right)$, where $\text{gap}_{\min}$は最小の準最適ギャップであり、$c_{\min}$は全ての状態-作用対の最小コストである。
この結果は、(Cohen et al., 2021) の有限水平近似のより単純で改良された解析を、より小さい近似誤差で開発することで得られる。
一方,大域最適化問題において分散認識信頼セットを用いると,第2のアルゴリズムは計算量的に非効率であるが,第1の「ホリゾンフリー」な後悔は$\widetilde{o}(d^{3.5}b_{\star}\sqrt{k})$ であり,$t_{\star}$ や$/c_{\min}$ に多項式依存性を持たず,$\omega(db_{\star}\sqrt{k})$ とほぼ一致する(min et al., 2021)。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback [30.337826346496385]
線形マルコフ決定過程におけるオンライン強化学習について,敵対的損失と帯域幅フィードバックを用いて検討した。
既存の手法と比較して、後悔性能を向上させるアルゴリズムを2つ導入する。
論文 参考訳（メタデータ） (2023-10-17T19:43:37Z) - Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time [8.808780937701522]
我々は、より効率的でエラーの少ない最小化フレームワークに向けて、大きな一歩を踏み出します。
我々のアルゴリズムは時間$widetilde O(|Omega| k)$で実行され、解の検証にはほぼ線形である。
論文 参考訳（メタデータ） (2023-02-21T23:49:36Z) - Near-Optimal Goal-Oriented Reinforcement Learning in Non-Stationary
Environments [40.027926921772355]
目標指向強化学習における動的後悔の研究を行う。
この下位境界における$Delta_c$と$Delta_P$の異なる役割は、コストと遷移を別々に見積もるアルゴリズムを設計するきっかけとなった。
論文 参考訳（メタデータ） (2022-05-25T20:29:01Z) - The First Optimal Algorithm for Smooth and
Strongly-Convex-Strongly-Concave Minimax Optimization [88.91190483500932]
本稿では,スムーズで強靭なミニマックス最適化問題を再考する。
既存の最先端メソッドは、下限の$Omegaleft(sqrtkappa_xkappa_ylog3 (kappa_xkappa_y)logfrac1epsilonright)$にマッチしない。
我々は、$mathcalOleft( sqrtkappa_xkappa_ylog)で最初のアルゴリズムを提供することで、この根本的な問題を解決する。
論文 参考訳（メタデータ） (2022-05-11T17:33:07Z) - 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) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov
Decision Processes [91.38793800392108]
本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。
上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。
我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
論文 参考訳（メタデータ） (2020-12-15T18:56:46Z) - Logarithmic Regret for Reinforcement Learning with Linear Function
Approximation [99.59319332864129]
最近提案された2つの線形MDP仮定で対数的後悔が達成可能であることを示す。
我々の知る限り、これらは線型関数近似を持つRLに対する最初の対数的後悔境界である。
論文 参考訳（メタデータ） (2020-11-23T17:25:00Z) - $Q$-learning with Logarithmic Regret [60.24952657636464]
楽観的な$Q$は$mathcalOleft(fracSAcdot mathrmpolyleft(Hright)Delta_minlogleft(SATright)right)$ cumulative regret bound, where $S$ is the number of state, $A$ is the number of action, $H$ is the planning horizon, $T$ is the total number of steps, $Delta_min$ is the least sub-Optitimality gap。
論文 参考訳（メタデータ） (2020-06-16T13:01:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。