論文の概要: Provably Efficient Exploration in Constrained Reinforcement
Learning:Posterior Sampling Is All You Need
- arxiv url: http://arxiv.org/abs/2309.15737v1
- Date: Wed, 27 Sep 2023 15:48:36 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-28 13:04:02.034584
- Title: Provably Efficient Exploration in Constrained Reinforcement
Learning:Posterior Sampling Is All You Need
- Title(参考訳): 制約付き強化学習における潜在的に効率的な探索:余剰サンプリングがすべて必要である
- Authors: Danil Provodin, Pratik Gajane, Mykola Pechenizkiy and Maurits Kaptein
- Abstract要約: 本稿では,制約付きマルコフ決定過程(CMDP)における学習のための後方サンプリングに基づく新しいアルゴリズムを提案する。
このアルゴリズムは,既存のアルゴリズムと比較して経験的に有利でありながら,ほぼ最適の後悔境界を達成している。
- 参考スコア(独自算出の注目度): 15.113053885573171
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We present a new algorithm based on posterior sampling for learning in
constrained Markov decision processes (CMDP) in the infinite-horizon
undiscounted setting. The algorithm achieves near-optimal regret bounds while
being advantageous empirically compared to the existing algorithms. Our main
theoretical result is a Bayesian regret bound for each cost component of
\tilde{O} (HS \sqrt{AT}) for any communicating CMDP with S states, A actions,
and bound on the hitting time H. This regret bound matches the lower bound in
order of time horizon T and is the best-known regret bound for communicating
CMDPs in the infinite-horizon undiscounted setting. Empirical results show
that, despite its simplicity, our posterior sampling algorithm outperforms the
existing algorithms for constrained reinforcement learning.
- Abstract(参考訳): 本稿では,制約付きマルコフ決定過程(CMDP)における学習のための後方サンプリングに基づく新しいアルゴリズムを提案する。
このアルゴリズムは,既存のアルゴリズムと比較して経験的に有利でありながら,ほぼ最適の後悔境界を達成する。
我々の主要な理論的結果は、S状態、A作用、および打点時間Hとの通信CMDPの各々のコスト成分に対するベイズ的後悔境界(HS \sqrt{AT})であり、この後悔境界は時間水平線Tの順序で下界と一致し、無限水平非割当な設定でCMDPを通信するための最もよく知られた後悔境界である。
実験の結果,提案アルゴリズムは単純性に拘わらず,既存の強化学習アルゴリズムよりも優れていることがわかった。
関連論文リスト
- Minimizing the Thompson Sampling Regret-to-Sigma Ratio (TS-RSR): a
provably efficient algorithm for batch Bayesian Optimization [5.461310760509014]
我々の目標は、不確実点間の冗長性を最小化する方法で、各バッチで選択されたアクションを調整できることです。
予測バッチアルゴリズムにおいて、最先端の理論的保証を提供する。
論文 参考訳(メタデータ) (2024-03-07T18:58:26Z) - A Single-Loop Deep Actor-Critic Algorithm for Constrained Reinforcement
Learning with Provable Convergence [8.191815417711194]
Deep Actorriticアルゴリズムは、ActorriticとDeep Neural Network(DNN)を組み合わせる
本稿では,一般対話のための単一ループアクタ・クライブアルゴリズムを提案する。
SL-Criticアルゴリズムは、優れた学習近似と優れた性能に収束することを示す。
論文 参考訳(メタデータ) (2023-06-10T10:04:54Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳(メタデータ) (2022-02-26T19:10:48Z) - Uniform-PAC Bounds for Reinforcement Learning with Linear Function
Approximation [92.3161051419884]
線形関数近似を用いた強化学習について検討する。
既存のアルゴリズムは、高い確率的後悔と/またはおよそ正当性(PAC)サンプルの複雑さの保証しか持たない。
我々はFLUTEと呼ばれる新しいアルゴリズムを提案し、高い確率で最適ポリシーへの均一PAC収束を享受する。
論文 参考訳(メタデータ) (2021-06-22T08:48:56Z) - Experimental Design for Regret Minimization in Linear Bandits [19.8309784360219]
オンライン・リニア・バンドレットにおける後悔を最小限に抑える設計に基づく新しいアルゴリズムを提案する。
我々は、現在最先端の有限時間後悔保証を提供し、このアルゴリズムが帯域幅と半帯域幅の両方のフィードバックシステムに適用可能であることを示す。
論文 参考訳(メタデータ) (2020-11-01T17:59:19Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳(メタデータ) (2020-10-23T09:12:47Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳(メタデータ) (2020-09-28T15:22:24Z) - Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。
この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。
古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文 参考訳(メタデータ) (2020-07-01T18:43:32Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳(メタデータ) (2020-02-24T17:55:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。