論文の概要: Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms
for Stochastic Shortest Path
- arxiv url: http://arxiv.org/abs/2106.08377v1
- Date: Tue, 15 Jun 2021 19:15:17 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-17 17:39:36.563376
- Title: Implicit Finite-Horizon Approximation and Efficient Optimal Algorithms
for Stochastic Shortest Path
- Title（参考訳）: 確率的最短経路に対する暗黙的有限ホリゾン近似と効率的な最適アルゴリズム
- Authors: Liyu Chen, Mehdi Jafarnia-Jahromi, Rahul Jain, Haipeng Luo
- Abstract要約: 本稿では,最短経路(SSP)モデルにおいて,後悔するアルゴリズムを開発するための汎用テンプレートを提案する。
まず、厳密な正のコストでモデルフリーとミニマックス最適の2つの新しいアルゴリズムを開発する。
どちらのアルゴリズムも高度にスパースな更新を認めており、既存のアルゴリズムよりも計算効率が良い。
- 参考スコア（独自算出の注目度）: 29.289190242826688
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We introduce a generic template for developing regret minimization algorithms
in the Stochastic Shortest Path (SSP) model, which achieves minimax optimal
regret as long as certain properties are ensured. The key of our analysis is a
new technique called implicit finite-horizon approximation, which approximates
the SSP model by a finite-horizon counterpart only in the analysis without
explicit implementation. Using this template, we develop two new algorithms:
the first one is model-free (the first in the literature to our knowledge) and
minimax optimal under strictly positive costs; the second one is model-based
and minimax optimal even with zero-cost state-action pairs, matching the best
existing result from [Tarbouriech et al., 2021b]. Importantly, both algorithms
admit highly sparse updates, making them computationally more efficient than
all existing algorithms. Moreover, both can be made completely parameter-free.
- Abstract（参考訳）: 本稿では,SSP(Stochastic Shortest Path)モデルにおいて,特定の特性が確保される限り,最小限の後悔を実現するため,後悔最小化アルゴリズムを開発するための汎用テンプレートを提案する。
我々の分析の鍵は暗黙的有限水平近似と呼ばれる新しい手法であり、これは明示的な実装なしに解析においてのみ有限水平近似によってSSPモデルを近似する。
このテンプレートを用いて, モデルフリー(第1報) とミニマックス(第2報) を厳密な正のコストで最適とし, モデルベースとミニマックス(第2報) をゼロコストのステートアクションペアでも最適とし, [Tarbouriech et al., 2021b] から得られる最良の結果に適合するアルゴリズムを開発した。
重要なことに、両方のアルゴリズムは高度にスパースな更新を認めており、既存のアルゴリズムよりも計算効率が良い。
さらに、どちらもパラメータフリーにすることもできる。
関連論文リスト
- Self-concordant Smoothing for Large-Scale Convex Composite Optimization [0.0]
2つの凸関数の和を最小化する自己協和スムージングの概念を導入し、そのうちの1つは滑らかであり、もう1つは非滑らかである。
本稿では, 近位ニュートンアルゴリズムであるProx-N-SCOREと近位一般化したガウスニュートンアルゴリズムであるProx-GGN-SCOREの2つのアルゴリズムの収束性を証明する。
論文 参考訳（メタデータ） (2023-09-04T19:47:04Z) - Online Learning Under A Separable Stochastic Approximation Framework [20.26530917721778]
分離可能な近似フレームワークを用いて,機械学習モデルのクラスに対するオンライン学習アルゴリズムを提案する。
提案アルゴリズムは,他の一般的な学習アルゴリズムと比較して,より堅牢でテスト性能が高いことを示す。
論文 参考訳（メタデータ） (2023-05-12T13:53:03Z) - Constrained Online Two-stage Stochastic Optimization: Near Optimal Algorithms via Adversarial Learning [1.994307489466967]
有限地平線上の長期制約付きオンライン2段階最適化をT$周期で検討する。
対戦型学習アルゴリズムからオンライン二段階問題のオンラインアルゴリズムを開発する。
論文 参考訳（メタデータ） (2023-02-02T10:33:09Z) - Implicit Parameter-free Online Learning with Truncated Linear Models [51.71216912089413]
パラメータフリーアルゴリズムは、設定された学習率を必要としないオンライン学習アルゴリズムである。
そこで我々は,「単純」なフレーバーを持つ新しい更新によって,切り離された線形モデルを活用できる新しいパラメータフリーアルゴリズムを提案する。
後悔の新たな分解に基づいて、新しい更新は効率的で、各ステップで1つの勾配しか必要とせず、切り捨てられたモデルの最小値をオーバーシュートすることはない。
論文 参考訳（メタデータ） (2022-03-19T13:39:49Z) - Accelerated SGD for Non-Strongly-Convex Least Squares [14.010916616909743]
非強凸設定における最小二乗回帰問題の近似を考察する。
本稿では,問題のノイズに依存して最適な予測誤差率を実現するための,最初の実用的なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-03-03T14:39:33Z) - Online Model Selection for Reinforcement Learning with Function
Approximation [50.008542459050155]
我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。
また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
論文 参考訳（メタデータ） (2020-11-19T10:00:54Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Gradient Free Minimax Optimization: Variance Reduction and Faster
Convergence [120.9336529957224]
本稿では、勾配のないミニマックス最適化問題の大きさを非強設定で表現する。
本稿では,新しいゼロ階分散還元降下アルゴリズムが,クエリの複雑さを最もよく表すことを示す。
論文 参考訳（メタデータ） (2020-06-16T17:55:46Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z) - Stochastic Proximal Gradient Algorithm with Minibatches. Application to
Large Scale Learning Models [2.384873896423002]
非滑らかな成分を持つ汎用合成対象関数に対する勾配アルゴリズムのミニバッチ変種を開発し解析する。
我々は、最小バッチサイズ$N$に対して、$mathcalO(frac1Nepsilon)$$epsilon-$subityが最適解に期待される二次距離で達成されるような、定数および変数のステップサイズ反復ポリシーの複雑さを提供する。
論文 参考訳（メタデータ） (2020-03-30T10:43:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。