Fugu-MT 論文翻訳(概要): Online Learning in Adversarial MDPs: Is the Communicating Case Harder than Ergodic?

論文の概要: Online Learning in Adversarial MDPs: Is the Communicating Case Harder than Ergodic?

arxiv url: http://arxiv.org/abs/2111.02024v1
Date: Wed, 3 Nov 2021 05:16:48 GMT
ステータス: 処理完了
システム内更新日: 2021-11-04 13:42:03.781210
Title: Online Learning in Adversarial MDPs: Is the Communicating Case Harder than Ergodic?
Title（参考訳）: 対立型MDPにおけるオンライン学習はエルゴードよりも難しいか?
Authors: Gautam Chandrasekaran and Ambuj Tewari
Abstract要約: 我々は、後述の最良の固定決定論ポリシーに関して、$O(sqrtT)$を後悔するアルゴリズムを与える。また、MDPの通信において、$O(sqrtT)$ regretを達成する非効率なアルゴリズムも提供する。
参考スコア（独自算出の注目度）: 30.533991006187865
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study online learning in adversarial communicating Markov Decision Processes with full information. We give an algorithm that achieves a regret of $O(\sqrt{T})$ with respect to the best fixed deterministic policy in hindsight when the transitions are deterministic. We also prove a regret lower bound in this setting which is tight up to polynomial factors in the MDP parameters. We also give an inefficient algorithm that achieves $O(\sqrt{T})$ regret in communicating MDPs (with an additional mild restriction on the transition dynamics).
Abstract（参考訳）: マルコフ決定過程を全情報で通信する対人コミュニケーションにおけるオンライン学習について検討する。我々は、遷移が決定論的である場合、後見において最良の固定決定論的ポリシーに対して$O(\sqrt{T})$を後悔するアルゴリズムを与える。また、この設定において、MDPパラメータの多項式因子に密接な後悔の少ない境界が証明される。また、MPPの通信において、$O(\sqrt{T})$の後悔を達成する非効率なアルゴリズムも与えている(遷移力学にさらなる制限を加えて)。

関連論文リスト

Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs [16.49229317664822]
線形MDPを用いた無限水平平均逆強化学習について検討する。本稿では,$widetildeO(sqrtT)$の後悔境界が,計算効率のよいアルゴリズムを実現することを提案する。
論文参考訳（メタデータ） (2024-05-23T20:58:33Z)
Online Reinforcement Learning in Markov Decision Process Using Linear Programming [1.0878040851638]
マルコフ決定過程(MDP)におけるオンライン強化学習について検討した。我々は,高い確率で$widetildeO(LXsqrtTA)$ regretを実現する,シンプルで効率的なモデルベースアルゴリズムを考案した。
論文参考訳（メタデータ） (2023-03-31T22:21:41Z)
Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraints [39.715977181666766]
本研究では,無限水平平均回帰マルコフ決定過程(MDP)のコスト制約による後悔について検討する。我々のアルゴリズムはエルゴディックMDPに対して$widetildeO(sqrtT)$ regret and constant constraint violationを保証します。これらは、MDPをコスト制約で弱い通信を行うための最初の証明可能なアルゴリズムである。
論文参考訳（メタデータ） (2022-01-31T23:52:34Z)
Online Markov Decision Processes with Non-oblivious Strategic Adversary [35.25621843666453]
オンラインマルコフ決定過程 (OMDP) において, 損失関数は非公開の戦略的敵によって選択される。 MDP-Expertは、暗黙の敵とうまく連携する既存のアルゴリズムで、$mathcalO(sqrtTlog(L)+tau2sqrt T log(|A|))$のポリシー後悔の限界を達成でき、$L$は敵の純粋な戦略セットのサイズであり、$|A|$はサイズを表す。
論文参考訳（メタデータ） (2021-10-07T16:32:37Z)
Beyond Value-Function Gaps: Improved Instance-Dependent Regret Bounds for Episodic Reinforcement Learning [50.44564503645015]
有限エピソードマルコフ決定過程における強化学習のための改良されたギャップ依存的後悔境界を提供する。楽観的なアルゴリズムでは,より強い後悔境界を証明し,多数のMDPに対して新たな情報理論的下限を伴う。
論文参考訳（メタデータ） (2021-07-02T20:36:05Z)
Regret Analysis in Deterministic Reinforcement Learning [78.31410227443102]
本稿では,最適学習アルゴリズムの分析と設計の中心となる後悔の問題を考察する。本稿では,システムパラメータに明示的に依存する対数問題固有の後悔の下位境界について述べる。
論文参考訳（メタデータ） (2021-06-27T23:41:57Z)
Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function Approximation [92.3161051419884]
我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
論文参考訳（メタデータ） (2021-02-17T18:54:08Z)
Online Apprenticeship Learning [58.45089581278177]
見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
論文参考訳（メタデータ） (2021-02-13T12:57:51Z)
Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping [99.59319332864129]
本稿では,割引決定(MDP)のための強化学習について検討する。本稿では,特徴写像を利用した新しいアルゴリズムを提案し,$tilde O(dsqrtT/ (1-gamma)2)$ regretを求める。以上の結果から,提案した強化学習アルゴリズムは,最大1-γ-0.5$の係数でほぼ最適であることが示唆された。
論文参考訳（メタデータ） (2020-06-23T17:08:54Z)
Upper Confidence Primal-Dual Reinforcement Learning for CMDP with Adversarial Loss [145.54544979467872]
マルコフ決定過程(CMDP)に対するオンライン学習の検討本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
論文参考訳（メタデータ） (2020-03-02T05:02:23Z)
Reinforcement Learning in Factored MDPs: Oracle-Efficient Algorithms and Tighter Regret Bounds for the Non-Episodic Setting [24.90164851620799]
非等化因子マルコフ決定過程(FMDP)における強化学習の研究 FMDPに対する2つの近似およびオラクル効率アルゴリズムを提案する。我々のオラクル効率のアルゴリズムは、コンピュータネットワーク管理シミュレーションにおいて、これまで提案されていた近似アルゴリズムよりも優れていた。
論文参考訳（メタデータ） (2020-02-06T15:19:53Z)

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