論文の概要: 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-10-16 13:59:04.191236
- 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:
- 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})$ と一致する最小境界を確立する。
本研究は,在庫管理問題に関する実験的研究により理論的知見を補完するものである。
関連論文リスト
- Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit
Feedback and Unknown Transition [71.33787410075577]
線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。
我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-03-07T15:03:50Z) - Efficient Reinforcement Learning with Impaired Observability: Learning
to Act with Delayed and Missing State Observations [92.25604137490168]
本稿では,制御系における効率的な強化学習に関する理論的研究を紹介する。
遅延および欠落した観測条件において,RL に対して $tildemathcalO(sqrtrm poly(H) SAK)$ という形でアルゴリズムを提示し,その上限と下限をほぼ最適に設定する。
論文 参考訳(メタデータ) (2023-06-02T02:46:39Z) - Reinforcement Learning with Exogenous States and Rewards [15.18610763024837]
外因性状態変数と報酬は、報酬信号に制御されていない変動を注入することで強化学習を遅くすることができる。
本稿では内因性状態変数と報酬を定式化し、報酬関数が内因性成分と内因性成分に付加的に分解した場合、MDPは2つのプロセスに分解できることを示す。
論文 参考訳(メタデータ) (2023-03-22T23:37:28Z) - Computationally Efficient PAC RL in POMDPs with Latent Determinism and
Conditional Embeddings [97.12538243736705]
大規模部分観測可能決定プロセス(POMDP)の関数近似を用いた強化学習に関する研究
我々のアルゴリズムは、大規模POMDPに確実にスケールする。
論文 参考訳(メタデータ) (2022-06-24T05:13:35Z) - 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) - Value Function Approximations via Kernel Embeddings for No-Regret
Reinforcement Learning [10.828727066443909]
我々は,CME-RLというオンラインモデルに基づくRLアルゴリズムを提案し,Hilbert空間への埋め込みとして遷移分布の表現を学習する。
絶対定数と多対数係数のみを隠蔽する次数$tildeObig(Hgamma_NsqrtNbig)$footnote $tildeO(cdot)$の頻繁な(Worst-case)後悔境界を証明してアルゴリズムの有効性を実証する。
論文 参考訳(メタデータ) (2020-11-16T11:40:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。