論文の概要: The regret lower bound for communicating Markov Decision Processes

• arxiv url: http://arxiv.org/abs/2501.13013v1
• Date: Wed, 22 Jan 2025 16:56:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-01-23 16:53:31.847925
• Title: The regret lower bound for communicating Markov Decision Processes
• Title（参考訳）: マルコフ決定過程を伝達するための後悔の低い境界
• Authors: Victor Boone, Odalric-Ambrym Maillard,
• Abstract要約: 我々は、エルゴード的マルコフ決定過程(MDPs)を超えて、後悔の少ない境界を延長する。 我々の下限は、一貫した学習エージェントに必要な爆発的振る舞いを再考する。 これら2つの爆発的・共同探索的行動は,航法制約に絡み合っていることを示す。
• 参考スコア（独自算出の注目度）: 15.108805347673401
• License:
• Abstract: This paper is devoted to the extension of the regret lower bound beyond ergodic Markov decision processes (MDPs) in the problem dependent setting. While the regret lower bound for ergodic MDPs is well-known and reached by tractable algorithms, we prove that the regret lower bound becomes significatively more complex in communicating MDPs. Our lower bound revisits the necessary explorative behavior of consistent learning agents and further explains that all optimal regions of the environment must be overvisited compared to sub-optimal ones, a phenomenon that we refer to as co-exploration. In tandem, we show that these two explorative and co-explorative behaviors are intertwined with navigation constraints obtained by scrutinizing the navigation structure at logarithmic scale. The resulting lower bound is expressed as the solution of an optimization problem that, in many standard classes of MDPs, can be specialized to recover existing results. From a computational perspective, it is provably $\Sigma_2^\textrm{P}$-hard in general and as a matter of fact, even testing the membership to the feasible region is coNP-hard. We further provide an algorithm to approximate the lower bound in a constructive way.
• Abstract（参考訳）: 本稿では,問題依存設定におけるエルゴード的マルコフ決定過程(MDP)を超えて,後悔の少ない境界の拡張に着目する。 エルゴード MDP に対する後悔の低い境界はよく知られ、抽出可能なアルゴリズムによって到達するが、その後悔の低い境界が MDP の通信において顕著に複雑になることを示す。 下限は、一貫した学習エージェントの必要な爆発的振る舞いを再考し、さらに、環境の全ての最適領域は、副最適領域よりも過度に視認されなければならない、と説明します。 タンデムでは、これらの2つの爆発的・共同探索的行動は、対数スケールで航法構造を精査することによって得られる航法制約と連動していることを示す。 結果の下位境界は最適化問題の解として表現され、MPPの多くの標準クラスにおいて、既存の結果を回復するために特殊化することができる。 計算の観点からは、一般には$\Sigma_2^\textrm{P}$-hardであり、実際、実現可能な領域へのメンバシップをテストしてもcoNP-hardである。 さらに、構築的な方法で下界を近似するアルゴリズムを提供する。

関連論文リスト

• Towards Instance-Optimality in Online PAC Reinforcement Learning [28.156332484814616]
  そこで本研究では,PACの同定に要するサンプルの複雑さに対する最初のインスタンス依存下限について提案する。 我々は、citeWagenmaker22linearMDPのPEDELアルゴリズムのサンプル複雑さがこの下界に近づいたことを実証する。
  論文  参考訳（メタデータ） (2023-10-31T19:26:36Z)
• Provably Efficient Exploration in Constrained Reinforcement Learning:Posterior Sampling Is All You Need [15.113053885573171]
  本稿では,制約付きマルコフ決定過程(CMDP)における学習のための後方サンプリングに基づく新しいアルゴリズムを提案する。 このアルゴリズムは,既存のアルゴリズムと比較して経験的に有利でありながら,ほぼ最適の後悔境界を達成している。
  論文  参考訳（メタデータ） (2023-09-27T15:48:36Z)
• Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs [24.256960622176305]
  エピソードマルコフ決定過程におけるPAC RLのサンプル複雑性について, 上界と下界の整合性について検討した。 私たちの境界は、決定論的リターンギャップ(deterministic return gap)と呼ばれる状態-作用ペアに対して、新たな最適ギャップ(sub-optimality gap)を特徴とする。 彼らの設計と分析は、最小フローや最大カットといったグラフ理論の概念を含む新しいアイデアを採用している。
  論文  参考訳（メタデータ） (2022-03-17T11:19:41Z)
• 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)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。 我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。 この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-24T13:46:09Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Towards Minimax Optimal Reinforcement Learning in Factored Markov Decision Processes [53.72166325215299]
  エピソード因子化マルコフ決定過程(FMDP)における最小強化学習について検討する。 第一に、分解された構造のリッチなクラスに対する最小限の後悔の保証を達成する。 2つ目は、少し悪い後悔をしながら、より良い計算複雑性を楽しみます。
  論文  参考訳（メタデータ） (2020-06-24T00:50:17Z)
• 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)

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

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