論文の概要: Adaptive Discretization in Online Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2110.15843v1
- Date: Fri, 29 Oct 2021 15:06:15 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-01 14:20:54.474511
- Title: Adaptive Discretization in Online Reinforcement Learning
- Title（参考訳）: オンライン強化学習における適応的離散化
- Authors: Sean R. Sinclair, Siddhartha Banerjee, Christina Lee Yu
- Abstract要約: 離散化に基づくアルゴリズムを設計する際の2つの大きな疑問は、離散化をどのように生成し、いつそれを洗練するかである。
オンライン強化学習のための木に基づく階層分割手法の統一的理論的解析を行う。
我々のアルゴリズムは操作制約に容易に適応し、我々の理論は3つの面のそれぞれに明示的な境界を与える。
- 参考スコア（独自算出の注目度）: 9.560980936110234
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Discretization based approaches to solving online reinforcement learning
problems have been studied extensively in practice on applications ranging from
resource allocation to cache management. Two major questions in designing
discretization-based algorithms are how to create the discretization and when
to refine it. While there have been several experimental results investigating
heuristic solutions to these questions, there has been little theoretical
treatment. In this paper we provide a unified theoretical analysis of
tree-based hierarchical partitioning methods for online reinforcement learning,
providing model-free and model-based algorithms. We show how our algorithms are
able to take advantage of inherent structure of the problem by providing
guarantees that scale with respect to the 'zooming dimension' instead of the
ambient dimension, an instance-dependent quantity measuring the benignness of
the optimal $Q_h^\star$ function.
Many applications in computing systems and operations research requires
algorithms that compete on three facets: low sample complexity, mild storage
requirements, and low computational burden. Our algorithms are easily adapted
to operating constraints, and our theory provides explicit bounds across each
of the three facets. This motivates its use in practical applications as our
approach automatically adapts to underlying problem structure even when very
little is known a priori about the system.
- Abstract（参考訳）: 資源割り当てからキャッシュ管理に至るまで,オンライン強化学習問題に対する離散化に基づくアプローチが,実際に広く研究されている。
離散化に基づくアルゴリズムを設計する際の2つの大きな疑問は、離散化をどのように生成し、いつそれを洗練するかである。
これらの問題に対するヒューリスティックな解法に関する実験結果がいくつかあるが、理論的な処理は少ない。
本稿では,オンライン強化学習のための木ベース階層分割法の統一的理論解析を行い,モデルフリーおよびモデルベースアルゴリズムを提供する。
最適値Q_h^\star$関数の良性を測定するインスタンス依存量である環境次元ではなく,「ズームング次元」に対するスケールの保証を提供することで,我々のアルゴリズムが問題の固有構造をいかに活用できるかを示す。
コンピュータシステムや運用研究における多くの応用は、サンプルの複雑さの低さ、ストレージ要件の低さ、計算負荷の低さという3つの側面で競合するアルゴリズムを必要とする。
我々のアルゴリズムは操作制約に容易に適応し、我々の理論は3つの面のそれぞれに明確な境界を与える。
これは、システムに関する優先順位がほとんど分かっていない場合でも、そのアプローチが基盤となる問題構造に自動的に適応するので、実用的なアプリケーションでの使用を動機付けます。
関連論文リスト
- Limits and Powers of Koopman Learning [0.0]
力学系は様々な科学にまたがって複雑で変化する振る舞いを研究する包括的方法を提供する。
クープマン作用素は、線形手法を用いた非線形力学の研究を可能にするため、支配的なアプローチとして現れてきた。
テキスト 動的システムの軌道データからクープマン作用素のスペクトル特性を頑健に学習することは可能か?
論文 参考訳（メタデータ） (2024-07-08T18:24:48Z) - Multi-Timescale Ensemble Q-learning for Markov Decision Process Policy
Optimization [21.30645601474163]
元々のQ-ラーニングは、非常に大きなネットワークにわたるパフォーマンスと複雑性の課題に悩まされている。
従来のQ-ラーニングに適応したモデルフリーアンサンブル強化学習アルゴリズムを提案する。
計算結果から,提案アルゴリズムは平均ポリシエラーを最大55%,実行時複雑性を最大50%削減できることがわかった。
論文 参考訳（メタデータ） (2024-02-08T08:08:23Z) - Towards model-free RL algorithms that scale well with unstructured data [1.3799571823220778]
本稿では,経験ストリームから直接予測構造を発見し,活用するための報奨関連一般値関数質問を構築するアルゴリズムを提案する。
提案アルゴリズムは,これらのスケーリング問題に対して,従来のディープRLアルゴリズムよりも確実に性能を向上する。
論文 参考訳（メタデータ） (2023-11-03T20:03:54Z) - Representation Learning with Multi-Step Inverse Kinematics: An Efficient
and Optimal Approach to Rich-Observation RL [106.82295532402335]
既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。
所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。
我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
論文 参考訳（メタデータ） (2023-04-12T14:51:47Z) - Stabilizing Q-learning with Linear Architectures for Provably Efficient
Learning [53.17258888552998]
本研究では,線形関数近似を用いた基本的な$Q$-learningプロトコルの探索変種を提案する。
このアルゴリズムの性能は,新しい近似誤差というより寛容な概念の下で,非常に優雅に低下することを示す。
論文 参考訳（メタデータ） (2022-06-01T23:26:51Z) - Exploring Viable Algorithmic Options for Learning from Demonstration
(LfD): A Parameterized Complexity Approach [0.0]
本稿では,パラメータ化複雑性解析を用いて,アルゴリズムの選択肢を体系的に探索する方法を示す。
環境、実演、ポリシーに対する多くの(しばしば同時に)制限に対して、我々の問題は、一般的にも、あるいは相対的に、効率的に解決できないことを示す。
論文 参考訳（メタデータ） (2022-05-10T15:54:06Z) - Neural Combinatorial Optimization: a New Player in the Field [69.23334811890919]
本稿では,ニューラルネットワークに基づくアルゴリズムの古典的最適化フレームワークへの導入に関する批判的分析を行う。
性能, 転送可能性, 計算コスト, 大規模インスタンスなど, これらのアルゴリズムの基本的側面を分析するために, 総合的研究を行った。
論文 参考訳（メタデータ） (2022-05-03T07:54:56Z) - Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
マルチエージェントシステムにおける学習に有効なモデルベース強化学習アルゴリズムを提案する。
我々の理論的な貢献は、MFCのモデルベース強化学習における最初の一般的な後悔の限界である。
コア最適化問題の実用的なパラメトリゼーションを提供する。
論文 参考訳（メタデータ） (2021-07-08T18:01:02Z) - Learning to Actively Learn: A Robust Approach [22.75298609290053]
本研究では,アクティブラーニングや純粋探索型マルチアームバンディットといった適応データ収集タスクのアルゴリズム設計手法を提案する。
我々の適応アルゴリズムは、情報理論の下界から導かれる問題の同値クラスに対する逆学習によって学習される。
我々は,訓練手順の安定性と有効性を正当化するための合成実験を行い,実データから導出される課題について評価する。
論文 参考訳（メタデータ） (2020-10-29T06:48:22Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。
特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。
提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文 参考訳（メタデータ） (2020-06-18T20:09:53Z) - Beyond Worst-Case Analysis in Stochastic Approximation: Moment
Estimation Improves Instance Complexity [58.70807593332932]
近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。
最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。
提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
論文 参考訳（メタデータ） (2020-06-08T09:25:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。