論文の概要: Unified Algorithms for RL with Decision-Estimation Coefficients:
No-Regret, PAC, and Reward-Free Learning
- arxiv url: http://arxiv.org/abs/2209.11745v1
- Date: Fri, 23 Sep 2022 17:47:24 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-26 13:25:58.299398
- Title: Unified Algorithms for RL with Decision-Estimation Coefficients:
No-Regret, PAC, and Reward-Free Learning
- Title(参考訳): 決定推定係数を持つRLの統一アルゴリズム:非回帰・PAC・逆学習
- Authors: Fan Chen, Song Mei, Yu Bai
- Abstract要約: DEC(Decision-Estimation Coefficient)は、サンプル効率の非回帰RLに必要かつ十分な複雑性尺度である。
本稿では,DECフレームワークを用いたRLの統一理論に向けて前進する。
我々は2つの新しいDEC型複雑性尺度(Explorative DEC (EDEC)とReward-free DEC (RFDEC))を提案する。
- 参考スコア(独自算出の注目度): 25.658930892561735
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Finding unified complexity measures and algorithms for sample-efficient
learning is a central topic of research in reinforcement learning (RL). The
Decision-Estimation Coefficient (DEC) is recently proposed by Foster et al.
(2021) as a necessary and sufficient complexity measure for sample-efficient
no-regret RL. This paper makes progress towards a unified theory for RL with
the DEC framework. First, we propose two new DEC-type complexity measures:
Explorative DEC (EDEC), and Reward-Free DEC (RFDEC). We show that they are
necessary and sufficient for sample-efficient PAC learning and reward-free
learning, thereby extending the original DEC which only captures no-regret
learning. Next, we design new unified sample-efficient algorithms for all three
learning goals. Our algorithms instantiate variants of the
Estimation-To-Decisions (E2D) meta-algorithm with a strong and general model
estimation subroutine. Even in the no-regret setting, our algorithm E2D-TA
improves upon the algorithms of Foster et al. (2021) which require either
bounding a variant of the DEC which may be prohibitively large, or designing
problem-specific estimation subroutines. As applications, we recover existing
and obtain new sample-efficient learning results for a wide range of tractable
RL problems using essentially a single algorithm. Finally, as a connection, we
re-analyze two existing optimistic model-based algorithms based on Posterior
Sampling or Maximum Likelihood Estimation, showing that they enjoy similar
regret bounds as E2D-TA under similar structural conditions as the DEC.
- Abstract(参考訳): サンプル効率学習のための統一された複雑性尺度とアルゴリズムの発見は、強化学習(RL)研究の中心的なトピックである。
決定-推定係数(Decision-Estimation Coefficient, DEC)は、最近Fosterら(2021)によって、サンプル効率の非回帰RLに必要な複雑さの尺度として提案されている。
本稿では,DECフレームワークを用いたRLの統一理論に向けて前進する。
まず,探索的DEC (Explorative DEC) とReward-Free DEC (RFDEC) の2つの新しいDEC型複雑性尺度を提案する。
サンプル効率のよいpac学習と報酬のない学習には必要で十分であることを示す。
次に、3つの学習目標すべてに対して,新しい統一サンプル効率アルゴリズムを設計する。
我々のアルゴリズムは, モデル推定サブルーチンを用いて, E2Dメタアルゴリズムの変種をインスタンス化する。
アルゴリズムE2D-TAは,不規則に大きいDECの変種を限定するか,あるいは問題固有の推定サブルーチンを設計する必要があるFoster et al. (2021)のアルゴリズムを改良する。
応用として,既存のサンプル効率のよい学習結果を,本質的に1つのアルゴリズムを用いて,広い範囲の扱いやすいrl問題に対して取得する。
最後に,2つの既存楽観的モデルベースアルゴリズムを再解析し,DECと似た構造条件下でのE2D-TAと同様の後悔境界を享受することを示す。
関連論文リスト
- Representation Learning with Multi-Step Inverse Kinematics: An Efficient
and Optimal Approach to Rich-Observation RL [106.82295532402335]
既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。
所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。
我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
論文 参考訳(メタデータ) (2023-04-12T14:51:47Z) - Tight Guarantees for Interactive Decision Making with the
Decision-Estimation Coefficient [51.37720227675476]
我々は、決定推定係数の新たな変種を導入し、それを用いて、3つの面における事前の作業を改善する新しい下界を導出する。
我々は同じ量でスケールした後悔について上界を与え、フォスター等における上界と下界の間のギャップの1つを除いて全てを閉じる。
この結果は、後悔のフレームワークとPACフレームワークの両方に適用され、我々が期待するいくつかの新しい分析とアルゴリズム設計技術を利用して、より広範な利用が期待できる。
論文 参考訳(メタデータ) (2023-01-19T18:24:08Z) - 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) - A General Framework for Sample-Efficient Function Approximation in
Reinforcement Learning [132.45959478064736]
モデルベースとモデルフリー強化学習を統合した汎用フレームワークを提案する。
最適化に基づく探索のための分解可能な構造特性を持つ新しい推定関数を提案する。
本フレームワークでは,OPERA (Optimization-based Exploration with Approximation) という新しいサンプル効率アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-09-30T17:59:16Z) - The Statistical Complexity of Interactive Decision Making [126.04974881555094]
複雑度尺度であるDecision-Estimation Coefficientは,サンプル効率のインタラクティブ学習に必要かつ十分であることが証明された。
統合アルゴリズム設計原則であるE2Dは、教師付き推定のための任意のアルゴリズムを、意思決定のためのオンラインアルゴリズムに変換する。
論文 参考訳(メタデータ) (2021-12-27T02:53:44Z) - Dual Optimization for Kolmogorov Model Learning Using Enhanced Gradient
Descent [8.714458129632158]
コルモゴロフモデル(コルモゴロフモデル、英: Kolmogorov model、KM)は、確率変数の集合の基本的な確率構造を学ぶための解釈可能で予測可能な表現手法である。
正規化双対最適化と拡張勾配降下法(GD)を併用した計算スケーラブルなKM学習アルゴリズムを提案する。
提案したKM学習アルゴリズムを用いた論理的関係マイニングの精度は80%以上である。
論文 参考訳(メタデータ) (2021-07-11T10:33:02Z) - Identifying Co-Adaptation of Algorithmic and Implementational
Innovations in Deep Reinforcement Learning: A Taxonomy and Case Study of
Inference-based Algorithms [15.338931971492288]
我々は、アルゴリズムの革新と実装決定を分離するために、一連の推論に基づくアクター批判アルゴリズムに焦点を当てる。
実装の詳細がアルゴリズムの選択に一致すると、パフォーマンスが大幅に低下します。
結果は、どの実装の詳細がアルゴリズムと共適応され、共進化しているかを示す。
論文 参考訳(メタデータ) (2021-03-31T17:55:20Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - A Hybrid PAC Reinforcement Learning Algorithm [5.279475826661642]
本稿では,マルコフ決定過程(MDPs)に対するほぼ正のPAC強化学習(RL)アルゴリズムを提案する。
設計アルゴリズムはDyna-Delayed Q-learning(DDQ)アルゴリズムと呼ばれ、モデルフリーとモデルベースラーニングのアプローチを組み合わせており、どちらの場合も性能が優れている。
論文 参考訳(メタデータ) (2020-09-05T21:32:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。