論文の概要: Near-Optimal Adversarial Reinforcement Learning with Switching Costs
- arxiv url: http://arxiv.org/abs/2302.04374v1
- Date: Wed, 8 Feb 2023 23:41:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-10 17:15:56.492136
- Title: Near-Optimal Adversarial Reinforcement Learning with Switching Costs
- Title（参考訳）: スイッチングコストによるほぼ最適対向強化学習
- Authors: Ming Shi, Yingbin Liang, Ness Shroff
- Abstract要約: 本稿では, スイッチングコストを伴い, 効率の良いRLアルゴリズムの開発方法について述べる。
我々の下限は、敵RLのコストを切り替えるという根本的な課題のため、最も達成された後悔はもはや達成不可能であることを示している。
本稿では,遷移関数が知られているときの下位境界に一致することを後悔する2つの新しいスイッチング・リデュースアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 43.895798638743784
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Switching costs, which capture the costs for changing policies, are regarded
as a critical metric in reinforcement learning (RL), in addition to the
standard metric of losses (or rewards). However, existing studies on switching
costs (with a coefficient $\beta$ that is strictly positive and is independent
of $T$) have mainly focused on static RL, where the loss distribution is
assumed to be fixed during the learning process, and thus practical scenarios
where the loss distribution could be non-stationary or even adversarial are not
considered. While adversarial RL better models this type of practical
scenarios, an open problem remains: how to develop a provably efficient
algorithm for adversarial RL with switching costs? This paper makes the first
effort towards solving this problem. First, we provide a regret lower-bound
that shows that the regret of any algorithm must be larger than
$\tilde{\Omega}( ( H S A )^{1/3} T^{2/3} )$, where $T$, $S$, $A$ and $H$ are
the number of episodes, states, actions and layers in each episode,
respectively. Our lower bound indicates that, due to the fundamental challenge
of switching costs in adversarial RL, the best achieved regret (whose
dependency on $T$ is $\tilde{O}(\sqrt{T})$) in static RL with switching costs
(as well as adversarial RL without switching costs) is no longer achievable.
Moreover, we propose two novel switching-reduced algorithms with regrets that
match our lower bound when the transition function is known, and match our
lower bound within a small factor of $\tilde{O}( H^{1/3} )$ when the transition
function is unknown. Our regret analysis demonstrates the near-optimal
performance of them.
- Abstract（参考訳）: 政策変更のコストを捉えた切り替えコストは、標準的な損失(報酬)の指標に加えて、強化学習(RL)における重要な指標とみなされる。
しかし、スイッチングコスト(厳密に正で、T$とは独立な係数である$\beta$)に関する既存の研究は、主に静的RLに焦点を当てており、そこでは、損失分布は学習過程中に固定されていると仮定され、損失分布が非定常的あるいは対向的であるような現実的なシナリオは考慮されていない。
逆RLは、このような現実的なシナリオをより良くモデル化する一方で、オープンな問題として、切り替えコストを伴う対向RLの証明可能な効率的なアルゴリズムの開発方法が残されている。
本稿ではこの問題を解決するための最初の取り組みを行う。
まず、どんなアルゴリズムの後悔も$\tilde{\Omega}( ( H S A )^{1/3} T^{2/3} )$よりも大きいことを示し、$T$、$S$、$A$、$H$はそれぞれエピソード、状態、アクション、レイヤの数である。
我々の下限は、逆 RL のコストを切り替えるという根本的な課題のため、最も達成された後悔 ($T$ への依存は $\tilde{O}(\sqrt{T})$) の静的 RL における切替コスト (および切替コストのない逆 RL ) はもはや達成不可能であることを示している。
さらに、遷移関数が知られているときの下位境界に一致し、遷移関数が未知のときの小さな係数$\tilde{O}(H^{1/3} )$で下限に一致することを後悔する2つの新しい切り換え型アルゴリズムを提案する。
我々の後悔分析はそれらのほぼ最適性能を示している。
関連論文リスト
- The Limits of Transfer Reinforcement Learning with Latent Low-rank Structure [9.631640936820126]
多くの強化学習アルゴリズムは、問題の状態と行動空間のA$であるSが大きすぎるため、実際に使用するには高すぎる。
我々は、ソースとターゲットのMDPが遷移カーネルを持つ場合、遅延低ランク表現を転送する問題を考察する。
提案アルゴリズムは,各ソースMDPの潜在表現を学習し,その線形構造を利用して,ターゲットMDPの後悔境界における$S,A$,あるいは$SA$への依存を除去する。
論文 参考訳（メタデータ） (2024-10-28T23:12:08Z) - Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。
最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
論文 参考訳（メタデータ） (2023-07-25T15:42:11Z) - Bridging Distributional and Risk-sensitive Reinforcement Learning with
Provable Regret Bounds [24.571530193140916]
エントロピーリスク尺度(EntRM)が目的である有限エピソードマルコフ決定過程を考察する。
モデルフリーとモデルベースを含む2つの異なるスキームを用いて最適化を実装する2つの新しいDRLアルゴリズムを提案する。
いずれも$tildemathcalO(fracexp(|beta|H)-1|beta|HsqrtS2AK)$ regret upper bound, where $S$, $A$, $K$, $H$は数値を表す。
論文 参考訳（メタデータ） (2022-10-25T14:30:48Z) - The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret
and Policy Switches [84.54669549718075]
漸進的強化学習(RL)における後悔の最小化問題について検討する。
一般関数クラスと一般モデルクラスで学ぶことに集中する。
対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
論文 参考訳（メタデータ） (2022-03-03T02:55:55Z) - Sample-Efficient Reinforcement Learning with loglog(T) Switching Cost [31.04961854943877]
我々は,$widetildeO(sqrtH4S2AT)$を,切り替えコストが$O(HSA loglog T)$を要求されたことを後悔する新しいアルゴリズムを提案する。
副産物として、我々の新しいアルゴリズムは、最適な切替コストが$O(HSA)$のエンフレワードフリー探索アルゴリズムを導出することができる。
論文 参考訳（メタデータ） (2022-02-13T19:01:06Z) - Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free
Reinforcement Learning [52.76230802067506]
漸進的強化学習における後悔を最小限に抑えるために,新しいモデルフリーアルゴリズムを提案する。
提案アルゴリズムは、2つのQ-ラーニングシーケンスの助けを借りて、初期設定された参照更新ルールを用いる。
初期の分散還元法の設計原理は、他のRL設定とは独立した関心を持つかもしれない。
論文 参考訳（メタデータ） (2021-10-09T21:13:48Z) - The best of both worlds: stochastic and adversarial episodic MDPs with
unknown transition [49.78053380710322]
我々は,エピソードT$でマルコフ決定過程を学習する上で,両世界の最良の問題を考える。
最近の[Jin and Luo, 2020]による研究は、固定遷移が分かっているときにこの目標を達成する。
本研究では,同じFollow-the-Regularized-Leader(textFTRL$)フレームワークを新しいテクニックのセットと組み合わせることで,この問題を解決する。
論文 参考訳（メタデータ） (2021-06-08T05:46:35Z) - Revisiting Smoothed Online Learning [70.09792747315323]
オンライン学習者がヒットコストとスイッチングコストの両方に苦しむスムーズなオンライン学習の問題を調査します。
競争比を縛るために、各ラウンドで打つコストが学習者に知られていると仮定し、打つコストと切り換えコストの重み付け合計を単純に最小化する勾配アルゴリズムを調査します。
論文 参考訳（メタデータ） (2021-02-13T14:15:55Z) - Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in
Multi-Agent RL and Inventory Control [28.80743320843154]
非定常RLのための最初のモデルフリーアルゴリズムであるアッパー信頼境界を用いたリスタートQラーニング(RestartQ-UCB)を提案する。
我々は,情報理論的下限を$Omega(Sfrac13 Afrac13 Deltafrac13 Hfrac23 Tfrac23)$,非定常RLで最初の下限を設定すれば,アルゴリズムが最適であることを示す。
論文 参考訳（メタデータ） (2020-10-07T04:55:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。