論文の概要: Minimal Expected Regret in Linear Quadratic Control
- arxiv url: http://arxiv.org/abs/2109.14429v1
- Date: Wed, 29 Sep 2021 14:07:21 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-30 14:55:17.036213
- Title: Minimal Expected Regret in Linear Quadratic Control
- Title（参考訳）: 線形二次制御における最小期待後悔
- Authors: Yassir Jedra, Alexandre Proutiere
- Abstract要約: オンライン学習アルゴリズムを考案し、その期待された後悔を保証します。
当時のこの後悔は、$A$と$B$が未知の場合、$widetildeO((d_u+d_x)sqrtd_xT)$によって上界(i)となる。
- 参考スコア（独自算出の注目度）: 79.81807680370677
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We consider the problem of online learning in Linear Quadratic Control
systems whose state transition and state-action transition matrices $A$ and $B$
may be initially unknown. We devise an online learning algorithm and provide
guarantees on its expected regret. This regret at time $T$ is upper bounded (i)
by $\widetilde{O}((d_u+d_x)\sqrt{d_xT})$ when $A$ and $B$ are unknown, (ii) by
$\widetilde{O}(d_x^2\log(T))$ if only $A$ is unknown, and (iii) by
$\widetilde{O}(d_x(d_u+d_x)\log(T))$ if only $B$ is unknown and under some mild
non-degeneracy condition ($d_x$ and $d_u$ denote the dimensions of the state
and of the control input, respectively). These regret scalings are minimal in
$T$, $d_x$ and $d_u$ as they match existing lower bounds in scenario (i) when
$d_x\le d_u$ [SF20], and in scenario (ii) [lai1986]. We conjecture that our
upper bounds are also optimal in scenario (iii) (there is no known lower bound
in this setting).
Existing online algorithms proceed in epochs of (typically exponentially)
growing durations. The control policy is fixed within each epoch, which
considerably simplifies the analysis of the estimation error on $A$ and $B$ and
hence of the regret. Our algorithm departs from this design choice: it is a
simple variant of certainty-equivalence regulators, where the estimates of $A$
and $B$ and the resulting control policy can be updated as frequently as we
wish, possibly at every step. Quantifying the impact of such a
constantly-varying control policy on the performance of these estimates and on
the regret constitutes one of the technical challenges tackled in this paper.
- Abstract（参考訳）: 状態遷移および状態-作用遷移行列が$A$および$B$である線形二次制御系におけるオンライン学習の問題について考察する。
オンライン学習アルゴリズムを考案し、その期待する後悔の保証を提供する。
この後悔は 時給$t$ は上限より上です
(i) by $\widetilde{o}((d_u+d_x)\sqrt{d_xt})$ when $a$ と $b$ は未知である。
(ii) by $\widetilde{O}(d_x^2\log(T))$ if only $A$ is unknown, and
(iii) by $\widetilde{O}(d_x(d_u+d_x)\log(T))$ if $B$が未知で、ある穏やかな非退化条件下では$d_x$と$d_u$はそれぞれ状態と制御入力の次元を表す。
これらの残念なスケーリングは、シナリオにおける既存の下位境界と一致するため、$T$, $d_x$, $d_u$で最小限である
(i)$d_x\le d_u$ [SF20] の場合、シナリオ
(ii) [lai1986]
我々の上界も シナリオで最適だと推測します
(三)(この設定では下限は知られていない)
既存のオンラインアルゴリズムは、(典型的には指数関数的に)成長期間のエポックで進行する。
制御ポリシーは、各エポック内で固定され、$A$と$B$における推定誤差の分析をかなり単純化する。
このアルゴリズムは、A$とB$の推定値と結果の制御ポリシーを、私たちが望むように、おそらくすべてのステップで、頻繁に更新できるような、確実な等価性規制の単純な変種である。
このような一定変化の制御ポリシがこれらの見積のパフォーマンスに与える影響の定量化と,その後悔は,本稿で取り組んだ技術的課題の1つである。
関連論文リスト
- Sample-Efficient Reinforcement Learning with loglog(T) Switching Cost [31.04961854943877]
我々は,$widetildeO(sqrtH4S2AT)$を,切り替えコストが$O(HSA loglog T)$を要求されたことを後悔する新しいアルゴリズムを提案する。
副産物として、我々の新しいアルゴリズムは、最適な切替コストが$O(HSA)$のエンフレワードフリー探索アルゴリズムを導出することができる。
論文 参考訳（メタデータ） (2022-02-13T19:01:06Z) - Logarithmic Regret from Sublinear Hints [76.87432703516942]
自然クエリモデルにより,アルゴリズムが$O(log T)$ regretsを$O(sqrtT)$ hintsで得ることを示す。
また、$o(sqrtT)$ hintsは$Omega(sqrtT)$ regretより保証できないことも示しています。
論文 参考訳（メタデータ） (2021-11-09T16:50:18Z) - 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) - $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) - Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。
任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
論文 参考訳（メタデータ） (2020-02-23T09:10:14Z) - Logistic Regression Regret: What's the Catch? [3.7311680121118345]
パラメータに対する$L_infty$制約の下で、対数的後悔を伴う下界を導出する。
L$の制約については、十分に大きな$d$の場合、後悔は$d$で線形であるが、$T$で対数化されなくなることが示されている。
論文 参考訳（メタデータ） (2020-02-07T18:36:39Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。