論文の概要: Episodic Linear Quadratic Regulators with Low-rank Transitions
- arxiv url: http://arxiv.org/abs/2011.01568v2
- Date: Fri, 12 Feb 2021 04:40:14 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-30 05:39:00.968687
- Title: Episodic Linear Quadratic Regulators with Low-rank Transitions
- Title（参考訳）: 低ランク遷移をもつエピソード線形二次レギュレータ
- Authors: Tianyu Wang, Lin F. Yang
- Abstract要約: 本稿では,本システムの低ランク構造を効率よく学習するアルゴリズムを提案する。
我々のアルゴリズムは$K$-episode regret bound of order $widetildeO(m3/2 K1/2)$を達成する。
- 参考スコア（独自算出の注目度）: 31.8243883890202
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Linear Quadratic Regulators (LQR) achieve enormous successful real-world
applications. Very recently, people have been focusing on efficient learning
algorithms for LQRs when their dynamics are unknown. Existing results
effectively learn to control the unknown system using number of episodes
depending polynomially on the system parameters, including the ambient
dimension of the states. These traditional approaches, however, become
inefficient in common scenarios, e.g., when the states are high-resolution
images. In this paper, we propose an algorithm that utilizes the intrinsic
system low-rank structure for efficient learning. For problems of rank-$m$, our
algorithm achieves a $K$-episode regret bound of order $\widetilde{O}(m^{3/2}
K^{1/2})$. Consequently, the sample complexity of our algorithm only depends on
the rank, $m$, rather than the ambient dimension, $d$, which can be
orders-of-magnitude larger.
- Abstract（参考訳）: LQR(Linear Quadratic Regulators)は、現実世界の膨大な応用を実現する。
近年,LQRのダイナミクスが不明な場合,LQRの効率的な学習アルゴリズムに注目が集まっている。
既存の結果は、状態の環境次元を含むシステムのパラメータに依存するエピソード数を用いて、未知のシステムを効果的に制御することを学ぶ。
しかし、これらの伝統的なアプローチは、例えば状態が高解像度の画像であるような一般的なシナリオでは非効率になる。
本稿では,本システムの低ランク構造を効率的に学習するためのアルゴリズムを提案する。
ランク-$m$の問題に対して、我々のアルゴリズムは$K$-episode regret bound of order $\widetilde{O}(m^{3/2} K^{1/2})$を達成する。
その結果、アルゴリズムのサンプルの複雑さは、周囲の次元ではなくランクの$m$と、桁違いに大きい$d$にのみ依存する。
関連論文リスト
- Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instances [42.16343861129583]
オンライン学習アルゴリズムでは、シーケンス長が増加するにつれて、全体のコストが最高の$omega$に近づくように、一連のインスタンスに対してパラメータを選択できることが示される。
我々の研究は、高精度線形システム解法の最初の学習理論処理と、データ駆動型科学計算のエンドツーエンド保証を提供する。
論文 参考訳（メタデータ） (2023-10-03T17:51:42Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳（メタデータ） (2023-02-22T20:21:25Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - Adaptive Federated Minimax Optimization with Lower Complexities [82.51223883622552]
本稿では,これらのミニマックス問題の解法として,適応最小最適化アルゴリズム(AdaFGDA)を提案する。
運動量に基づく還元および局所SGD技術を構築し、様々な適応学習率を柔軟に組み込む。
論文 参考訳（メタデータ） (2022-11-14T12:32:18Z) - Computationally Efficient Horizon-Free Reinforcement Learning for Linear
Mixture MDPs [111.75736569611159]
線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。
我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。
これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
論文 参考訳（メタデータ） (2022-05-23T17:59:18Z) - Dynamic Regret Minimization for Control of Non-stationary Linear
Dynamical Systems [18.783925692307054]
本稿では,$tildemathcalO(sqrtST)$を最適にリセットするアルゴリズムを提案する。
本アルゴリズムの要点は適応的非定常性検出戦略であり,最近開発されたコンテキスト多重武装バンドイット問題に対するアプローチに基づいている。
論文 参考訳（メタデータ） (2021-11-06T01:30:51Z) - Scalable regret for learning to control network-coupled subsystems with
unknown dynamics [5.670584589057048]
相互接続されたサブシステムを見ることは、サブシステムの数とともに超直線的に増加する後悔をもたらす。
本稿では,基礎となるネットワークの構造を活かした新しいトンプソンサンプリングに基づく学習アルゴリズムを提案する。
提案アルゴリズムの期待された後悔は$tildemathcalO big(n sqrtT big)$, $n$はサブシステムの数, $T$は時間軸, $tildemathcalO(cdot)$表記は$nで対数項を隠していることを示す。
論文 参考訳（メタデータ） (2021-08-18T04:45:34Z) - Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and
Costs [45.87981728307819]
異種空間に居住する関連するデータセットを比較して整列する能力は、機械学習においてますます重要な役割を担っている。
グロモフ・ワッサーシュタイン (Gromov-Wasserstein, GW) 形式主義はこの問題に対処するのに役立つ。
論文 参考訳（メタデータ） (2021-06-02T12:50:56Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Logarithmic Regret for Learning Linear Quadratic Regulators Efficiently [0.0]
近年の研究では、意思決定ステップの平方根に後悔の念を抱く効率的な学習アルゴリズムが実証されている。
我々は、ステップ数と(多分)対数的にしかスケールしない、おそらく驚くべきことに、新しい効率的なアルゴリズムを提示する。
論文 参考訳（メタデータ） (2020-02-19T10:09:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。