論文の概要: Making Non-Stochastic Control (Almost) as Easy as Stochastic

• arxiv url: http://arxiv.org/abs/2006.05910v2
• Date: Mon, 5 Oct 2020 03:03:16 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-23 05:05:06.931970
• Title: Making Non-Stochastic Control (Almost) as Easy as Stochastic
• Title（参考訳）: 非確率制御を確率的に簡単にする(ほとんど)
• Authors: Max Simchowitz
• Abstract要約: より一般的な非確率的制御モデルにおいても、同じ後悔率が達成可能であることを示す。 学習者にとってダイナミクスが不明な場合に、最適な$widetildemathcalO(sqrtT)$ regretを得る。
• 参考スコア（独自算出の注目度）: 27.736345095024276
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent literature has made much progress in understanding \emph{online LQR}: a modern learning-theoretic take on the classical control problem in which a learner attempts to optimally control an unknown linear dynamical system with fully observed state, perturbed by i.i.d. Gaussian noise. It is now understood that the optimal regret on time horizon $T$ against the optimal control law scales as $\widetilde{\Theta}(\sqrt{T})$. In this paper, we show that the same regret rate (against a suitable benchmark) is attainable even in the considerably more general non-stochastic control model, where the system is driven by \emph{arbitrary adversarial} noise (Agarwal et al. 2019). In other words, \emph{stochasticity confers little benefit in online LQR}. We attain the optimal $\widetilde{\mathcal{O}}(\sqrt{T})$ regret when the dynamics are unknown to the learner, and $\mathrm{poly}(\log T)$ regret when known, provided that the cost functions are strongly convex (as in LQR). Our algorithm is based on a novel variant of online Newton step (Hazan et al. 2007), which adapts to the geometry induced by possibly adversarial disturbances, and our analysis hinges on generic "policy regret" bounds for certain structured losses in the OCO-with-memory framework (Anava et al. 2015). Moreover, our results accomodate the full generality of the non-stochastic control setting: adversarially chosen (possibly non-quadratic) costs, partial state observation, and fully adversarial process and observation noise.
• Abstract（参考訳）: 近年の文献では、学習者が完全な観測状態を持つ未知の線形力学系を最適に制御しようとする古典的制御問題の現代的学習論的考察である \emph{online lqr}: a modern learning-theoretic take on the classical control problem の理解に多くの進歩がある。 現在、時間的地平線上での最適後悔は、最適制御法則に対して$T$であり、$\widetilde{\Theta}(\sqrt{T})$である。 本稿では,より一般的な非定型制御モデルにおいても,同一の後悔率(適切なベンチマークの場合)が達成可能であること,また,システムには<emph{arbitrary adversarial} ノイズ (agarwal et al. 2019) があることを示す。 言い換えれば、'emph{stochasticity' はオンライン LQR の利点をほとんど示さない。 最適の$\widetilde{\mathcal{O}}(\sqrt{T})$ regretは、学習者にとってダイナミクスが未知のときに、$\mathrm{poly}(\log T)$ regretは、コスト関数が(LQRのように)強く凸であることを保証する。 提案手法はオンラインニュートンステップ (hazan et al. 2007) の新たな変種に基づき, 逆行性障害によって引き起こされる幾何構造に適応し, oco-with-memory framework (anava et al. 2015) における構造的損失に対する汎用的 "policy regret" 境界に依拠する。 さらに,本研究は,非確率的制御設定の完全汎用性,すなわち,対角的選択コスト,部分的状態観察,全対角的プロセスと観測ノイズについて評価した。

関連論文リスト

• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• Dynamic Regret for Strongly Adaptive Methods and Optimality of Online KRR [13.165557713537389]
  我々は、強い適応性(SA)アルゴリズムを、動的後悔を制御するための原則的な方法と見なせることを示した。 我々は,オンラインKernel Ridge Regression(KRR)の最小限の最適性を確立する,ある罰則による新たな下限を導出する。
  論文  参考訳（メタデータ） (2021-11-22T21:52:47Z)
• Near-Optimal No-Regret Learning for Correlated Equilibria in Multi-Player General-Sum Games [104.74734408204749]
  マルチプレイヤーの汎用正規形式ゲームにおいて,OMWU(Optimistic Multiplicative Weights Update)を用いているエージェントが全員,O(textrmpolylog(T))$(T$)$(T$)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$)であることを示す。 外部の後悔から内部の後悔へと結果を拡張し、後悔を交換することで、近似した平衡に収束する非結合学習ダイナミクスを確立する。
  論文  参考訳（メタデータ） (2021-11-11T01:19:53Z)
• Dynamic Regret Minimization for Control of Non-stationary Linear Dynamical Systems [18.783925692307054]
  本稿では,$tildemathcalO(sqrtST)$を最適にリセットするアルゴリズムを提案する。 本アルゴリズムの要点は適応的非定常性検出戦略であり,最近開発されたコンテキスト多重武装バンドイット問題に対するアプローチに基づいている。
  論文  参考訳（メタデータ） (2021-11-06T01:30:51Z)
• Finite-time System Identification and Adaptive Control in Autoregressive Exogenous Systems [79.67879934935661]
  未知のARXシステムのシステム識別と適応制御の問題について検討する。 我々は,オープンループとクローズループの両方のデータ収集の下で,ARXシステムに対する有限時間学習保証を提供する。
  論文  参考訳（メタデータ） (2021-08-26T18:00:00Z)
• Adaptive Control and Regret Minimization in Linear Quadratic Gaussian (LQG) Setting [91.43582419264763]
  我々は不確実性に直面した楽観主義の原理に基づく新しい強化学習アルゴリズムLqgOptを提案する。 LqgOptはシステムのダイナミクスを効率的に探索し、モデルのパラメータを信頼区間まで推定し、最も楽観的なモデルのコントローラをデプロイする。
  論文  参考訳（メタデータ） (2020-03-12T19:56:38Z)
• Naive Exploration is Optimal for Online LQR [49.681825576239355]
  最適後悔尺度は$widetildeTheta(sqrtd_mathbfu2 d_mathbfx T)$で、$T$は時間ステップの数、$d_mathbfu$は入力空間の次元、$d_mathbfx$はシステム状態の次元である。 我々の下界は、かつての$mathrmpoly(logT)$-regretアルゴリズムの可能性を排除する。
  論文  参考訳（メタデータ） (2020-01-27T03:44:54Z)
• Improper Learning for Non-Stochastic Control [78.65807250350755]
  逆方向の摂動, 逆方向に選択された凸損失関数, 部分的に観察された状態を含む, 未知の線形力学系を制御することの問題点を考察する。 このパラメトリゼーションにオンライン降下を適用することで、大規模なクローズドループポリシーに対してサブリニア後悔を実現する新しいコントローラが得られる。 我々の境界は、線形力学コントローラの安定化と競合する非確率的制御設定における最初のものである。
  論文  参考訳（メタデータ） (2020-01-25T02:12:48Z)

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

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