論文の概要: Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions

• arxiv url: http://arxiv.org/abs/2409.04840v2
• Date: Thu, 3 Oct 2024 16:23:07 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-07 22:49:49.440357
• Title: Sample and Oracle Efficient Reinforcement Learning for MDPs with Linearly-Realizable Value Functions
• Title（参考訳）: 線形化可能な値関数を持つMDPのためのサンプルとOracle効率的な強化学習
• Authors: Zakaria Mhammedi,
• Abstract要約: 本稿では,線形作用が特徴写像に一般化される決定法(MDP)の効率的な強化アルゴリズムを提案する。 具体的には、この設定において、最適に近いポリシーを効率的に見つける新しいアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 10.225358400539719
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Designing sample-efficient and computationally feasible reinforcement learning (RL) algorithms is particularly challenging in environments with large or infinite state and action spaces. In this paper, we advance this effort by presenting an efficient algorithm for Markov Decision Processes (MDPs) where the state-action value function of any policy is linear in a given feature map. This challenging setting can model environments with infinite states and actions, strictly generalizes classic linear MDPs, and currently lacks a computationally efficient algorithm under online access to the MDP. Specifically, we introduce a new RL algorithm that efficiently finds a near-optimal policy in this setting, using a number of episodes and calls to a cost-sensitive classification (CSC) oracle that are both polynomial in the problem parameters. Notably, our CSC oracle can be efficiently implemented when the feature dimension is constant, representing a clear improvement over state-of-the-art methods, which require solving non-convex problems with horizon-many variables and can incur computational costs that are exponential in the horizon.
• Abstract（参考訳）: サンプル効率で計算可能な強化学習(RL)アルゴリズムの設計は、大または無限の状態と行動空間を持つ環境では特に困難である。 本稿では,任意のポリシの状態-作用値関数が与えられた特徴写像に線形であるマルコフ決定過程(MDP)に対して,効率的なアルゴリズムを提案することによって,この取り組みを進める。 この挑戦的な設定は、無限の状態と動作を持つ環境をモデル化し、古典的線形MDPを厳密に一般化し、現在、MDPへのオンラインアクセス下での計算効率のよいアルゴリズムを欠いている。 具体的には、この設定において、複数のエピソードを用いて、最適に近いポリシーを効率的に見つける新しいRLアルゴリズムを導入し、問題パラメータの2つの多項式であるコスト感受性分類(CSC)オラクルを呼び出します。 特に,我々のCSCオラクルは,特徴次元が一定である場合に効率よく実装可能であり,非凸問題を水平多変数で解き,地平線で指数関数的な計算コストを発生させる技術よりも明確な改善が求められる。

関連論文リスト

• Two-Stage ML-Guided Decision Rules for Sequential Decision Making under Uncertainty [55.06411438416805]
  SDMU (Sequential Decision Making Under Uncertainty) は、エネルギー、金融、サプライチェーンといった多くの領域において、ユビキタスである。 いくつかのSDMUは、自然にマルチステージ問題(MSP)としてモデル化されているが、結果として得られる最適化は、計算の観点からは明らかに困難である。 本稿では,2段階の一般決定規則(TS-GDR)を導入し,線形関数を超えて政策空間を一般化する手法を提案する。 TS-GDRの有効性は、TS-LDR(Two-Stage Deep Decision Rules)と呼ばれるディープリカレントニューラルネットワークを用いたインスタンス化によって実証される。
  論文  参考訳（メタデータ） (2024-05-23T18:19:47Z)
• Offline RL via Feature-Occupancy Gradient Ascent [9.983014605039658]
  大規模無限水平割引マルコフ決定過程(MDP)におけるオフライン強化学習の研究 我々は,特徴占有空間における勾配上昇の形式を実行する新しいアルゴリズムを開発した。 結果として得られた単純なアルゴリズムは、強い計算とサンプルの複雑さの保証を満たすことを示す。
  論文  参考訳（メタデータ） (2024-05-22T15:39:05Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。 既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。 提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
  論文  参考訳（メタデータ） (2023-07-08T15:41:48Z)
• Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP [81.00800920928621]
  部分的に観測可能なマルコフ決定過程(POMDP)における表現学習の研究 まず,不確実性(OFU)に直面した最大推定(MLE)と楽観性を組み合わせた復調性POMDPのアルゴリズムを提案する。 次に、このアルゴリズムをより広範な$gamma$-observable POMDPのクラスで機能させる方法を示す。
  論文  参考訳（メタデータ） (2023-06-21T16:04:03Z)
• Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Exploration [87.53543137162488]
  我々はtextttMEX というオンライン強化学習(オンラインRL)フレームワークを提案する。 textttMEXは、自動的に探索エクスプロイトのバランスをとりながら、見積もりと計画コンポーネントを統合する。 様々な MuJoCo 環境では,ベースラインを安定的なマージンで上回り,十分な報酬を得られる。
  論文  参考訳（メタデータ） (2023-05-29T17:25:26Z)
• Reinforcement Learning Methods for Wordle: A POMDP/Adaptive Control Approach [0.3093890460224435]
  我々は、新しい強化学習手法を用いて、人気のあるWordleパズルの解法に対処する。 Wordleパズルでは、比較的控えめな計算コストで最適に近いオンラインソリューション戦略が得られる。
  論文  参考訳（メタデータ） (2022-11-15T03:46:41Z)
• Multi-Objective Policy Gradients with Topological Constraints [108.10241442630289]
  本稿では, PPOアルゴリズムの簡単な拡張により, TMDPにおけるポリシー勾配に対する新しいアルゴリズムを提案する。 シミュレーションと実ロボットの両方の目的を任意に並べた実世界の多目的ナビゲーション問題に対して,これを実証する。
  論文  参考訳（メタデータ） (2022-09-15T07:22:58Z)
• Computational-Statistical Gaps in Reinforcement Learning [23.517741855454044]
  そこでは,CNF式を決定論的遷移,動作の定数数,低次元線形最適値関数を備えたMDP仮説に変換する。 この結果は線形関数近似を用いた強化学習における最初の計算統計的ギャップを示す。
  論文  参考訳（メタデータ） (2022-02-11T04:48:35Z)
• Learning the Step-size Policy for the Limited-Memory Broyden-Fletcher-Goldfarb-Shanno Algorithm [3.7470451129384825]
  本稿では,L-BFGSアルゴリズムのステップサイズポリシの学習方法について考察する。 入力として電流勾配の局所的な情報を用いたニューラルネットワークアーキテクチャを提案する。 ステップ長ポリシは、同様の最適化問題のデータから学習され、目的関数のさらなる評価を回避し、出力ステップが予め定義された間隔内に留まることを保証します。
  論文  参考訳（メタデータ） (2020-10-03T09:34:03Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Efficient Planning in Large MDPs with Weak Linear Function Approximation [4.56877715768796]
  大規模意思決定プロセス(MDP)は、MDPの状態を独立して計画アルゴリズムを必要とする。 線形値関数近似を用いたMDPの計画問題を考える。
  論文  参考訳（メタデータ） (2020-07-13T04:40:41Z)

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

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