Fugu-MT 論文翻訳(概要): The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition

論文の概要: The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition

arxiv url: http://arxiv.org/abs/2106.04117v1
Date: Tue, 8 Jun 2021 05:46:35 GMT
ステータス: 処理完了
システム内更新日: 2021-06-09 15:47:35.070957
Title: The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition
Title（参考訳）: 両世界の最良性:未知の遷移を伴う確率的および逆進的エピソードMDP
Authors: Tiancheng Jin, Longbo Huang, Haipeng Luo
Abstract要約: 我々は,エピソードT$でマルコフ決定過程を学習する上で,両世界の最良の問題を考える。最近の[Jin and Luo, 2020]による研究は、固定遷移が分かっているときにこの目標を達成する。本研究では,同じFollow-the-Regularized-Leader(textFTRL$)フレームワークを新しいテクニックのセットと組み合わせることで,この問題を解決する。
参考スコア（独自算出の注目度）: 49.78053380710322
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We consider the best-of-both-worlds problem for learning an episodic Markov Decision Process through $T$ episodes, with the goal of achieving $\widetilde{\mathcal{O}}(\sqrt{T})$ regret when the losses are adversarial and simultaneously $\mathcal{O}(\text{polylog}(T))$ regret when the losses are (almost) stochastic. Recent work by [Jin and Luo, 2020] achieves this goal when the fixed transition is known, and leaves the case of unknown transition as a major open question. In this work, we resolve this open problem by using the same Follow-the-Regularized-Leader ($\text{FTRL}$) framework together with a set of new techniques. Specifically, we first propose a loss-shifting trick in the $\text{FTRL}$ analysis, which greatly simplifies the approach of [Jin and Luo, 2020] and already improves their results for the known transition case. Then, we extend this idea to the unknown transition case and develop a novel analysis which upper bounds the transition estimation error by (a fraction of) the regret itself in the stochastic setting, a key property to ensure $\mathcal{O}(\text{polylog}(T))$ regret.
Abstract（参考訳）: 我々は,損失が対角的であれば$\widetilde{\mathcal{O}}(\sqrt{T})$ regretを達成し,損失が(ほぼ)確率的であれば$\mathcal{O}(\text{polylog}(T))$ regretを目標として,エピソディックなマルコフ決定過程を$T$で学習する最善の世界問題を考える。最近の[Jin and Luo, 2020]による研究は、固定的な遷移が分かっているときにこの目標を達成するもので、未知の遷移が主要なオープンな問題として残されている。そこで本研究では,Follow-the-Regularized-Leader ($\text{FTRL}$) フレームワークを新しい手法のセットと組み合わせることで,この問題を解決する。具体的には、まず、[Jin and Luo, 2020] のアプローチを大幅に単純化し、既知の遷移ケースに対する結果が既に改善されている$\text{FTRL}$解析において損失シフトのトリックを提案する。そして、このアイデアを未知の遷移ケースに拡張し、(一割の)確率的設定における後悔自体によって遷移推定誤差を上限とする新しい分析法を開発し、$\mathcal{O}(\text{polylog}(T))$ regret を保証するための鍵となる性質を述べる。

関連論文リスト

Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPs [63.47351876442425]
本研究は,完全情報フィードバックの下で,相変わらずの相変わらずの線形混合MDPについて検討した。本稿では,占領率に基づく手法と政策に基づく手法の利点を組み合わせた新しいアルゴリズムを提案する。我々のアルゴリズムは$widetildemathcalO(d sqrtH3 K + sqrtHK(H + barP_K$)$ dynamic regret, ここで$d$は特徴次元である。
論文参考訳（メタデータ） (2024-11-05T13:55:52Z)
No-Regret Online Reinforcement Learning with Adversarial Losses and Transitions [39.864174754882754]
対戦型マルコフ決定プロセスのための既存のオンライン学習アルゴリズムは、T$ラウンドのインタラクションの後、後悔して$O(sqrtT)を達成します。これは、対向遷移関数が非回帰学習を不可能にすることが示されているためである。我々は、$widetildeO(sqrtT + CtextsfP)$ regretというアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-05-27T06:10:17Z)
Near-Optimal Adversarial Reinforcement Learning with Switching Costs [43.895798638743784]
本稿では, スイッチングコストを伴い, 効率の良いRLアルゴリズムの開発方法について述べる。我々の下限は、敵RLのコストを切り替えるという根本的な課題のため、最も達成された後悔はもはや達成不可能であることを示している。本稿では,遷移関数が知られているときの下位境界に一致することを後悔する2つの新しいスイッチング・リデュースアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-02-08T23:41:29Z)
Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文参考訳（メタデータ） (2022-10-20T21:32:01Z)
Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文参考訳（メタデータ） (2022-10-15T09:22:22Z)
Double Thompson Sampling in Finite stochastic Games [10.559241770674724]
有限割引マルコフ決定プロセスの下での探索と利用のトレードオフ問題を考察する。このような問題を解決するために、二重トンプソンサンプリング強化学習アルゴリズム(DTS)を提案する。
論文参考訳（メタデータ） (2022-02-21T06:11:51Z)
Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally [58.463668865380946]
状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。 rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。 Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
論文参考訳（メタデータ） (2021-02-25T15:50:19Z)
Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case [29.99619764839178]
敵の費用と未知の遷移を伴う最短経路問題に対して,大きな進展をみせている。具体的には、全情報設定を後悔する$widetildeO(sqrtS3A2DT_star K)を実現するアルゴリズムを開発する。私たちはまた、最も難しい組み合わせとして、敵のコストによる盗聴フィードバックと未知の移行を最初に検討しています。
論文参考訳（メタデータ） (2021-02-10T06:33:04Z)
Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition [38.28925339231888]
我々は,世界最良保証付きの最初のアルゴリズムを開発した。損失が逆ならば、$mathcalO(log T)$ regretを達成します。より一般的には、中間設定で $tildemathcalO(sqrtC)$ regret を達成する。
論文参考訳（メタデータ） (2020-06-10T01:59:34Z)
Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
マルコフ決定過程(CMDP)に対するオンライン学習の検討本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
論文参考訳（メタデータ） (2020-03-02T05:02:23Z)

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

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