論文の概要: Policy Optimization in Adversarial MDPs: Improved Exploration via
Dilated Bonuses
- arxiv url: http://arxiv.org/abs/2107.08346v1
- Date: Sun, 18 Jul 2021 02:30:48 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-21 05:00:38.922758
- Title: Policy Optimization in Adversarial MDPs: Improved Exploration via
Dilated Bonuses
- Title(参考訳): 敵対的mdpにおける政策最適化:拡張ボーナスによる探索の改善
- Authors: Haipeng Luo, Chen-Yu Wei, Chung-Wei Lee
- Abstract要約: 我々は、グローバルな探索を容易にするために、ポリシー更新に拡張ボーナスを追加する一般的なソリューションを開発する。
本研究は,敵対的損失と盗聴フィードバックを伴って,複数のエピソードMDP設定に適用する。
シミュレータが利用できない場合、線形 MDP の設定を考慮し、$widetildemathcalO(T14/15)$ regret を得る。
- 参考スコア(独自算出の注目度): 40.12297110530343
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: Policy optimization is a widely-used method in reinforcement learning. Due to
its local-search nature, however, theoretical guarantees on global optimality
often rely on extra assumptions on the Markov Decision Processes (MDPs) that
bypass the challenge of global exploration. To eliminate the need of such
assumptions, in this work, we develop a general solution that adds dilated
bonuses to the policy update to facilitate global exploration. To showcase the
power and generality of this technique, we apply it to several episodic MDP
settings with adversarial losses and bandit feedback, improving and
generalizing the state-of-the-art. Specifically, in the tabular case, we obtain
$\widetilde{\mathcal{O}}(\sqrt{T})$ regret where $T$ is the number of episodes,
improving the $\widetilde{\mathcal{O}}({T}^{2/3})$ regret bound by Shani et al.
(2020). When the number of states is infinite, under the assumption that the
state-action values are linear in some low-dimensional features, we obtain
$\widetilde{\mathcal{O}}({T}^{2/3})$ regret with the help of a simulator,
matching the result of Neu and Olkhovskaya (2020) while importantly removing
the need of an exploratory policy that their algorithm requires. When a
simulator is unavailable, we further consider a linear MDP setting and obtain
$\widetilde{\mathcal{O}}({T}^{14/15})$ regret, which is the first result for
linear MDPs with adversarial losses and bandit feedback.
- Abstract(参考訳): 政策最適化は強化学習において広く使われている手法である。
しかし、その局所探索の性質から、大域的最適性に関する理論的保証は、大域的探索の難しさを克服するマルコフ決定過程(MDP)の余分な仮定に依存することが多い。
このような仮定の必要性をなくすため,本研究では,グローバル探索を容易にするために,政策更新に拡張ボーナスを追加する汎用ソリューションを開発した。
本手法のパワーと汎用性を示すために,敵対的損失と包帯的フィードバックを伴い,最先端技術の改善と一般化を図った複数のエピソードMDP設定に適用する。
特に表の場合、$\widetilde{\mathcal{O}}(\sqrt{T})$ regret where $T$ is the number of episodes, improve the $\widetilde{\mathcal{O}}({T}^{2/3})$ regret bound by Shani et al。
(2020).
状態の数が無限であるとき、状態-作用値がいくつかの低次元特徴において線型であるという仮定の下で、シミュレータの助けを借りて$\widetilde{\mathcal{O}}({T}^{2/3})$ regretを取得し、Neu と Olkhovskaya (2020) の結果と一致する。
シミュレータが利用できない場合、さらに線形 MDP の設定を考え、$\widetilde{\mathcal{O}}({T}^{14/15})$ regret を得る。
関連論文リスト
- Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimization [11.11876897168701]
本稿では,次数$tildemathcalO(mathrmpoly(H)sqrtSAT)$の残差を求めるアルゴリズムを提案する。
提案したアルゴリズムと分析は、占有対策によって与えられる典型的なツールを完全に回避する。
論文 参考訳(メタデータ) (2024-07-08T08:06:45Z) - Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with
General Utilities [12.104551746465932]
安全マルチエージェント強化学習について検討し、エージェントはそれぞれの安全制約を満たしつつ、局所的な目的の総和をまとめて最大化しようとする。
我々のアルゴリズムは、$mathcalOleft(T-2/3right)$のレートで1次定常点(FOSP)に収束する。
サンプルベースの設定では、高い確率で、我々のアルゴリズムは、$epsilon$-FOSPを達成するために$widetildemathcalOleft(epsilon-3.5right)$サンプルが必要です。
論文 参考訳(メタデータ) (2023-05-27T20:08:35Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-01-30T14:37:21Z) - Provably Efficient Offline Reinforcement Learning with Trajectory-Wise
Reward [66.81579829897392]
我々はPessimistic vAlue iteRaTionとrEward Decomposition (PARTED)という新しいオフライン強化学習アルゴリズムを提案する。
PartEDは、最小2乗ベースの報酬再分配を通じて、ステップごとのプロキシ報酬に軌道を分解し、学習したプロキシ報酬に基づいて悲観的な値を実行する。
私たちの知る限りでは、PartEDは、トラジェクティブな報酬を持つ一般のMDPにおいて、証明可能な効率のよい最初のオフラインRLアルゴリズムである。
論文 参考訳(メタデータ) (2022-06-13T19:11:22Z) - Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
我々は、無限の地平線における政策最適化、$gamma$-discounted constrained Markov decision process (CMDP)について研究する。
我々の目標は、小さな制約違反で大きな期待された報酬を達成する政策を返却することである。
本稿では,任意のアルゴリズムに対して,報酬の準最適性と制約違反を拘束できる汎用的原始双対フレームワークを提案する。
論文 参考訳(メタデータ) (2022-04-11T15:08:09Z) - 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) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-03-01T17:47:03Z) - Optimistic Policy Optimization with Bandit Feedback [70.75568142146493]
我々は,事前の報奨を後悔する$tilde O(sqrtS2 A H4 K)を定め,楽観的な信頼領域ポリシー最適化(TRPO)アルゴリズムを提案する。
我々の知る限り、この2つの結果は、未知の遷移と帯域幅フィードバックを持つポリシー最適化アルゴリズムにおいて得られた最初のサブ線形後悔境界である。
論文 参考訳(メタデータ) (2020-02-19T15:41:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。