論文の概要: Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms

• arxiv url: http://arxiv.org/abs/2102.00815v1
• Date: Mon, 1 Feb 2021 13:13:58 GMT
• ステータス: 処理完了
• システム内更新日: 2021-02-02 16:54:57.690578
• Title: Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Title（参考訳）: Bellman Eluder Dimension: RL問題の新しいリッチクラスとサンプル効率の高いアルゴリズム
• Authors: Chi Jin, Qinghua Liu, Sobhan Miryoosefi
• Abstract要約: 本稿では,ベルマン・エルダー(BE)次元という新しい複雑性尺度を導入する。 低BE次元のRL問題の族は極めて豊富であり、既存のトラクタブルなRL問題の大部分を仮定している。
• 参考スコア（独自算出の注目度）: 31.854180530060745
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Finding the minimal structural assumptions that empower sample-efficient learning is one of the most important research directions in Reinforcement Learning (RL). This paper advances our understanding of this fundamental question by introducing a new complexity measure -- Bellman Eluder (BE) dimension. We show that the family of RL problems of low BE dimension is remarkably rich, which subsumes a vast majority of existing tractable RL problems including but not limited to tabular MDPs, linear MDPs, reactive POMDPs, low Bellman rank problems as well as low Eluder dimension problems. This paper further designs a new optimization-based algorithm -- GOLF, and reanalyzes a hypothesis elimination-based algorithm -- OLIVE (proposed in Jiang et al. (2017)). We prove that both algorithms learn the near-optimal policies of low BE dimension problems in a number of samples that is polynomial in all relevant parameters, but independent of the size of state-action space. Our regret and sample complexity results match or improve the best existing results for several well-known subclasses of low BE dimension problems.
• Abstract（参考訳）: サンプル効率の学習を促進する最小限の構造的仮定を見つけることは、強化学習(RL)において最も重要な研究方向の1つである。 本稿では,新しい複雑性尺度であるbellman eluder(be)次元を導入することで,この基本的な問題に対する理解を深める。 我々は,低BE次元のRL問題の族が極めて豊富であることを示し,これは表付きMDP,線形MDP,反応性PMDP,低ベルマンランク問題,低エルダー次元問題など,既存のトラクタブルRL問題の大部分を仮定している。 本稿ではさらに,新しい最適化に基づくアルゴリズム -- ゴルフ,および仮説除去に基づくアルゴリズム -- olive (jiang et alで提案) を再分析する。 (2017)). 両アルゴリズムは、全ての関連するパラメータの多項式である多数のサンプルにおいて低BE次元問題の準最適ポリシを学習するが、状態-作用空間のサイズには依存しないことを示す。 我々の後悔とサンプルの複雑さの結果は、BE次元の低いいくつかのよく知られたサブクラスに対して、最良の既存の結果と一致または改善する。

関連論文リスト

• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning [53.445068584013896]
  低ランク構造を持つ強化学習(RL)における行列推定問題について検討した。 低ランク帯では、回収される行列は期待される腕の報酬を指定し、低ランクマルコフ決定プロセス(MDP)では、例えばMDPの遷移カーネルを特徴付ける。 簡単なスペクトルベースの行列推定手法は,行列の特異部分空間を効率よく復元し,ほぼ最小の入力誤差を示すことを示す。
  論文  参考訳（メタデータ） (2023-10-10T17:06:41Z)
• GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyond [101.5329678997916]
  対話型意思決定の一般的な枠組みの下で, サンプル高能率強化学習(RL)について検討した。 本稿では,探索とエクスプロイトの基本的なトレードオフを特徴付ける,新しい複雑性尺度である一般化エルダー係数(GEC)を提案する。 低 GEC の RL 問題は非常にリッチなクラスであり、これは低ベルマン楕円体次元問題、双線型クラス、低証人ランク問題、PO-双線型クラス、一般化正規PSR を仮定する。
  論文  参考訳（メタデータ） (2022-11-03T16:42:40Z)
• Optimistic MLE -- A Generic Model-based Algorithm for Partially Observable Sequential Decision Making [48.87943416098096]
  本稿では,一般的な逐次決定のための簡単な学習アルゴリズムを提案する。 我々は,OMLEが極めて豊富な逐次的意思決定問題のクラスにおいて,ほぼ最適ポリシーを学習していることを証明する。
  論文  参考訳（メタデータ） (2022-09-29T17:56:25Z)
• Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs [24.256960622176305]
  エピソードマルコフ決定過程におけるPAC RLのサンプル複雑性について, 上界と下界の整合性について検討した。 私たちの境界は、決定論的リターンギャップ(deterministic return gap)と呼ばれる状態-作用ペアに対して、新たな最適ギャップ(sub-optimality gap)を特徴とする。 彼らの設計と分析は、最小フローや最大カットといったグラフ理論の概念を含む新しいアイデアを採用している。
  論文  参考訳（メタデータ） (2022-03-17T11:19:41Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  本研究では,隠れ構造物の存在を検知する作業において,低次構造物のパワーについて検討する。 大規模な「信号+雑音」問題に対して、任意の程度に達成可能な最良の平均二乗誤差に対して、ユーザフレンドリな下界を与える。 応用として,植込みサブマトリクスに対する低次平均2乗誤差の厳密な評価と高密度サブグラフ問題について述べる。
  論文  参考訳（メタデータ） (2020-08-05T17:52:10Z)

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

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