論文の概要: Online Learning in Dynamically Changing Environments
- arxiv url: http://arxiv.org/abs/2302.00103v1
- Date: Tue, 31 Jan 2023 21:10:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-02 18:19:16.957339
- Title: Online Learning in Dynamically Changing Environments
- Title（参考訳）: 動的に変化する環境におけるオンライン学習
- Authors: Changlong Wu, Ananth Grama, Wojciech Szpankowski
- Abstract要約: 一般的な未知の非定常過程からサンプルを引き出す際に,オンライン学習とオンライン後悔の問題を考察する。
我々は、任意の有限VC-次元クラスに対する予想される最悪のケースに対する厳密な($sqrtlog T$ factorまで)有界な$O(sqrtKTcdotmathsfVC(mathcalH)log T)$を証明する。
我々はこれらの結果を、未知の基準測度を持つ一般的なスムーズな逆過程に拡張する。
- 参考スコア（独自算出の注目度）: 11.731001328350983
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of online learning and online regret minimization when
samples are drawn from a general unknown non-stationary process. We introduce
the concept of a dynamic changing process with cost $K$, where the conditional
marginals of the process can vary arbitrarily, but that the number of different
conditional marginals is bounded by $K$ over $T$ rounds. For such processes we
prove a tight (upto $\sqrt{\log T}$ factor) bound
$O(\sqrt{KT\cdot\mathsf{VC}(\mathcal{H})\log T})$ for the expected worst case
regret of any finite VC-dimensional class $\mathcal{H}$ under absolute loss
(i.e., the expected miss-classification loss). We then improve this bound for
general mixable losses, by establishing a tight (up to $\log^3 T$ factor)
regret bound $O(K\cdot\mathsf{VC}(\mathcal{H})\log^3 T)$. We extend these
results to general smooth adversary processes with unknown reference measure by
showing a sub-linear regret bound for $1$-dimensional threshold functions under
a general bounded convex loss. Our results can be viewed as a first step
towards regret analysis with non-stationary samples in the distribution blind
(universal) regime. This also brings a new viewpoint that shifts the study of
complexity of the hypothesis classes to the study of the complexity of
processes generating data.
- Abstract（参考訳）: 一般的な未知の非定常過程からサンプルを引き出す際に,オンライン学習とオンライン後悔の最小化の問題を検討する。
動的に変化するプロセスの概念をコスト$K$で導入し、そのプロセスの条件境界は任意に変化するが、異なる条件境界の数は$K$以上のラウンドで制限される。
そのようなプロセスに対して、厳密な($\sqrt{\log T}$ factorへの)有界な$O(\sqrt{KT\cdot\mathsf{VC}(\mathcal{H})\log T})$ 有限VC次元クラスである $\mathcal{H}$ に対する絶対損失(すなわち、期待されるミス分類損失)を証明します。
すると、この境界は($\log^3 T$ factorまで)厳密な($O(K\cdot\mathsf{VC}(\mathcal{H})\log^3 T)$を成立させることで、一般的な混合可能な損失に対して改善される。
一般凸損失の下での1$次元しきい値関数に対する線形な後悔を示すことによって、これらの結果を未知の基準測度を持つ一般的な滑らかな逆過程に拡張する。
この結果は,分布ブラインド(ユニバーサル)レジームにおける非定常サンプルを用いた後悔分析への第一歩と見なすことができる。
これはまた、仮説クラスの複雑性の研究を、データを生成するプロセスの複雑さの研究にシフトさせる新しい視点をもたらす。
関連論文リスト
- Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
本稿では,円滑なベルマン作用素を持つ連続空間マルコフ決定過程(MDP)の一般クラスにおいて,$varepsilon$-optimal Policyを学習する問題を考察する。
我々のソリューションの鍵となるのは、調和解析のアイデアに基づく新しい射影技術である。
我々の結果は、連続空間 MDP における2つの人気と矛盾する視点のギャップを埋めるものである。
論文 参考訳（メタデータ） (2024-05-10T09:58:47Z) - Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge [0.704590071265998]
オンラインQ-ラーニング手法のサンプル複雑性について,動的知識が利用可能であったり,効率的に学習できたりした場合に検討する。
我々は,$f$の完全知識の下で,$tildemathcalO(textPoly(H)sqrtSAT)$ regretを達成する楽観的なQ-ラーニングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-19T19:53:58Z) - Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。
最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
論文 参考訳（メタデータ） (2023-07-25T15:42:11Z) - Horizon-Free and Variance-Dependent Reinforcement Learning for Latent
Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。
我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文 参考訳（メタデータ） (2022-10-20T21:32:01Z) - The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret
and Policy Switches [84.54669549718075]
漸進的強化学習(RL)における後悔の最小化問題について検討する。
一般関数クラスと一般モデルクラスで学ぶことに集中する。
対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
論文 参考訳（メタデータ） (2022-03-03T02:55:55Z) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文 参考訳（メタデータ） (2021-10-09T21:13:48Z) - Localization, Convexity, and Star Aggregation [0.0]
オフセットラデマッハ複体は、正方形損失に対する鋭く線形依存的な上界を示すことが示されている。
統計的設定では、オフセット境界は一定の均一な凸性を満たす任意の損失に一般化可能であることを示す。
論文 参考訳（メタデータ） (2021-05-19T00:47:59Z) - Upper Confidence Primal-Dual Reinforcement Learning for CMDP with
Adversarial Loss [145.54544979467872]
マルコフ決定過程(CMDP)に対するオンライン学習の検討
本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。
我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
論文 参考訳（メタデータ） (2020-03-02T05:02:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。