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

• arxiv url: http://arxiv.org/abs/2409.14557v1
• Date: Mon, 14 Oct 2024 23:46:09 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-06 22:08:18.159483
• 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, 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 are affected by the actions, and evolve in a deterministic and known way conditional on the exogenous states. Exo-MDPs are a natural model for various applications including inventory control, finance, power systems, ride sharing, among others. Despite seeming restrictive, this work establishes that any discrete MDP can be represented as an Exo-MDP. Further, Exo-MDPs induce a natural representation of the transition and reward dynamics as linear functions of the exogenous state distribution. This linear representation leads to near-optimal algorithms with regret guarantees scaling only with the (effective) size of the exogenous state space $d$, independent of the sizes of the endogenous state and action spaces. Specifically, when the exogenous state is fully observed, a simple plug-in approach achieves a regret upper bound of $O(H^{3/2}\sqrt{dK})$, where $H$ denotes the horizon and $K$ denotes the total number of episodes. When the exogenous state is unobserved, the linear representation leads to a regret upper bound of $O(H^{3/2}d\sqrt{K})$. We also establish a nearly matching regret lower bound of $\Omega(Hd\sqrt{K})$ for the no observation regime. We complement our theoretical findings with an experimental study on inventory control problems.
• Abstract（参考訳）: 状態空間を2つの成分に分割することで特徴付けられるExo-MDP(Exo-MDPs)として知られる構造化マルコフ決定過程(MDPs)のクラスについて検討する。 外因性状態はエージェントの行動に影響されない方法で確率的に進化し、内因性状態はアクションに影響され、外因性状態に対して決定論的で既知の方法で進化する。 Exo-MDPは、在庫管理、金融、電力システム、ライドシェアリングなど、様々な応用の自然なモデルである。 制限的なように見えるが、この研究は任意の離散MDPをExo-MDPとして表現できることを証明している。 さらに、Exo-MDPは遷移と報酬ダイナミクスの自然な表現を外生状態分布の線形関数として導き出す。 この線形表現は、内因性状態と作用空間のサイズによらず、外因性状態空間$d$の(有効)サイズでのみスケーリングが保証されるような、ほぼ最適アルゴリズムにつながる。 具体的には、外因性状態が完全に観察されると、単純なプラグインアプローチは、$O(H^{3/2}\sqrt{dK})$の後悔の上界を達成し、$H$は地平線を表し、$K$はエピソードの総数を表す。 外因性状態が観測されないとき、線型表現は、後悔の上限である$O(H^{3/2}d\sqrt{K})$に導く。 また、無観測系に対して$\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)

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

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