論文の概要: Exploiting Exogenous Structure for Sample-Efficient Reinforcement Learning

• arxiv url: http://arxiv.org/abs/2409.14557v2
• Date: Mon, 14 Oct 2024 23:46:09 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-06 22:08:18.156298
• Title: Exploiting Exogenous Structure for Sample-Efficient Reinforcement Learning
• Title（参考訳）: サンプル効率の良い強化学習のための爆発的外生構造
• Authors: Jia Wan, Sean R. Sinclair, Devavrat Shah, Martin J. Wainwright,
• Abstract要約: 本研究では,Exo-MDPsとして知られる構造化マルコフ決定過程(MDPs)のクラスについて検討する。 Exo-MDPは、在庫管理、ポートフォリオ管理、電力システム、ライドシェアリングなど、様々なアプリケーションに自然なモデルを提供する。
• 参考スコア（独自算出の注目度）: 44.17068570786194
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a class of structured Markov Decision Processes (MDPs) known as Exo-MDPs. They are characterized by a partition of the state space into two components: the exogenous states evolve stochastically in a manner not affected by the agent's actions, whereas the endogenous states can be affected by actions, and evolve according to deterministic dynamics involving both the endogenous and exogenous states. Exo-MDPs provide a natural model for various applications, including inventory control, portfolio management, power systems, and ride-sharing, among others. While seemingly restrictive on the surface, our first result establishes that any discrete MDP can be represented as an Exo-MDP. The underlying argument reveals how transition and reward dynamics can be written as linear functions of the exogenous state distribution, showing how Exo-MDPs are instances of linear mixture MDPs, thereby showing a representational equivalence between discrete MDPs, Exo-MDPs, and linear mixture MDPs. The connection between Exo-MDPs and linear mixture MDPs leads to algorithms that are near sample-optimal, with regret guarantees scaling with the (effective) size of the exogenous state space $d$, independent of the sizes of the endogenous state and action spaces, even when the exogenous state is {\em unobserved}. When the exogenous state is unobserved, we establish a regret upper bound of $O(H^{3/2}d\sqrt{K})$ with $K$ trajectories of horizon $H$ and unobserved exogenous state of dimension $d$. We also establish a matching regret lower bound of $\Omega(H^{3/2}d\sqrt{K})$ for non-stationary Exo-MDPs and a lower bound of $\Omega(Hd\sqrt{K})$ for stationary Exo-MDPs. We complement our theoretical findings with an experimental study on inventory control problems.
• Abstract（参考訳）: 本研究では,Exo-MDPsとして知られる構造化マルコフ決定過程(MDPs)のクラスについて検討する。 内因性状態はエージェントの行動に影響されない方法で確率的に進化し、内因性状態は行動に影響されうるが、内因性状態と外因性状態の両方を含む決定論的ダイナミクスに従って進化する。 Exo-MDPは、在庫管理、ポートフォリオ管理、電力システム、ライドシェアリングなど、さまざまなアプリケーションに自然なモデルを提供する。 表面上は限定的であるように思われるが、最初の結果は、任意の離散MDPをExo-MDPとして表現できることを証明した。 基礎となる議論は、遷移力学と報酬力学を外因性状態分布の線形関数として記述し、Exo-MDPが線形混合MDPのインスタンスであることを示す。 Exo-MDP と線形混合 MDP との接続は、たとえ外因性状態が観測されていないとしても、内因性状態と行動空間のサイズによらず、外因性状態空間の(有効)サイズでスケールすることを後悔する、サンプル最適に近いアルゴリズムをもたらす。 外因性状態が観測されないとき、後悔の上限は$O(H^{3/2}d\sqrt{K})$で、地平線は$K$ trajectories of horizon $H$ and unobserved exogenous state of dimension $d$である。 また、非定常 Exo-MDP に対して $\Omega(H^{3/2}d\sqrt{K})$ と、定常 Exo-MDP に対して $\Omega(Hd\sqrt{K})$ と一致する最小境界を確立する。 本研究は,在庫管理問題に関する実験的研究により理論的知見を補完するものである。

関連論文リスト

• Learning a Fast Mixing Exogenous Block MDP using a Single Trajectory [87.62730694973696]
  STEELは、単一軌道から外因性ブロックマルコフ決定過程の制御可能なダイナミクスを学習するための、最初の証明可能なサンプル効率アルゴリズムである。 我々は,STEELが正解であり,サンプル効率が良いことを証明し,STEELを2つの玩具問題で実証した。
  論文  参考訳（メタデータ） (2024-10-03T21:57:21Z)
• Moving-Horizon Estimators for Hyperbolic and Parabolic PDEs in 1-D [2.819498895723555]
  観測者PDEの数値解の必要性をリアルタイムに除去するために,PDEの移動水平推定器を導入する。 我々は、双曲型PDEと放物型PDEの両方のクラスに対して、移動水平状態推定を明示的に生成するPDEバックステッピング法を用いてこれを実現する。
  論文  参考訳（メタデータ） (2024-01-04T19:55:43Z)
• Reinforcement Learning with Exogenous States and Rewards [15.18610763024837]
  外因性状態変数と報酬は、報酬信号に制御されていない変動を注入することで強化学習を遅くすることができる。 本稿では内因性状態変数と報酬を定式化し、報酬関数が内因性成分と内因性成分に付加的に分解した場合、MDPは2つのプロセスに分解できることを示す。
  論文  参考訳（メタデータ） (2023-03-22T23:37:28Z)
• Optimality Guarantees for Particle Belief Approximation of POMDPs [55.83001584645448]
  部分的に観測可能なマルコフ決定プロセス(POMDP)は、現実の意思決定と制御の問題に対する柔軟な表現を提供する。 POMDPは、特に状態と観測空間が連続的またはハイブリッドである場合、解決するのが非常に難しい。 本稿では,これらのアルゴリズムが使用する粒子フィルタリング手法の近似誤差を特徴付ける理論を提案する。
  論文  参考訳（メタデータ） (2022-10-10T21:11:55Z)
• Provable RL with Exogenous Distractors via Multistep Inverse Dynamics [85.52408288789164]
  実世界の強化学習(RL)の応用は、メガピクセルカメラから生成されたような高次元の観察にエージェントが対処する必要がある。 従来の研究は表現学習でこのような問題に対処しており、エージェントは生の観察から内因性、潜伏状態の情報を確実に抽出することができる。 しかし、このような手法は観測において時間的に相関するノイズの存在下では失敗する可能性がある。
  論文  参考訳（メタデータ） (2021-10-17T15:21:27Z)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  有限水平マルコフ決定過程(MDPs)における新たな問題依存的下界を導出する。 我々の下界は一般の場合よりもかなり小さく、最小の作用ギャップでスケールしないことが示される。 この最後の結果($poly(H)$の条件で、$H$は地平線である)は、楽観的なアルゴリズムのポリシーギャップに基づいて、後悔の意を表すことによって達成可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-24T13:46:09Z)
• Exploiting Submodular Value Functions For Scaling Up Active Perception [60.81276437097671]
  アクティブな知覚タスクでは、エージェントは1つ以上の隠れ変数の不確実性を減少させる感覚行動を選択することを目的としている。 部分的に観測可能なマルコフ決定過程(POMDP)は、そのような問題に対する自然なモデルを提供する。 エージェントが利用できるセンサーの数が増えるにつれて、POMDP計画の計算コストは指数関数的に増加する。
  論文  参考訳（メタデータ） (2020-09-21T09:11:36Z)

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

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