論文の概要: Safe Posterior Sampling for Constrained MDPs with Bounded Constraint
Violation
- arxiv url: http://arxiv.org/abs/2301.11547v1
- Date: Fri, 27 Jan 2023 06:18:25 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-30 16:23:16.113159
- Title: Safe Posterior Sampling for Constrained MDPs with Bounded Constraint
Violation
- Title（参考訳）: 拘束型MDPの安全な後方サンプリング
- Authors: Krishna C Kalagarla, Rahul Jain, Pierluigi Nuzzo
- Abstract要約: 制約付きマルコフ決定プロセス(CMDP)は、多くのアプリケーションにおいてますます重要になっている複数の目的を持つシーケンシャルな意思決定のシナリオをモデル化する。
我々は,そのような仮定を必要とせず,しかも非常によく機能するSafe PSRL (posterior sample-based RL)アルゴリズムを提案する。
準線形$tildemathcal Oleft(H2.5 sqrt|mathcalS|2 |mathcalA|K right)$上界をベイズ賞の目的的後悔と、有界なイデアルとともに成立させる。
- 参考スコア（独自算出の注目度）: 8.849815837266977
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Constrained Markov decision processes (CMDPs) model scenarios of sequential
decision making with multiple objectives that are increasingly important in
many applications. However, the model is often unknown and must be learned
online while still ensuring the constraint is met, or at least the violation is
bounded with time. Some recent papers have made progress on this very
challenging problem but either need unsatisfactory assumptions such as
knowledge of a safe policy, or have high cumulative regret. We propose the Safe
PSRL (posterior sampling-based RL) algorithm that does not need such
assumptions and yet performs very well, both in terms of theoretical regret
bounds as well as empirically. The algorithm achieves an efficient tradeoff
between exploration and exploitation by use of the posterior sampling
principle, and provably suffers only bounded constraint violation by leveraging
the idea of pessimism. Our approach is based on a primal-dual approach. We
establish a sub-linear $\tilde{\mathcal{ O}}\left(H^{2.5} \sqrt{|\mathcal{S}|^2
|\mathcal{A}| K} \right)$ upper bound on the Bayesian reward objective regret
along with a bounded, i.e., $\tilde{\mathcal{O}}\left(1\right)$ constraint
violation regret over $K$ episodes for an $|\mathcal{S}|$-state,
$|\mathcal{A}|$-action and horizon $H$ CMDP.
- Abstract（参考訳）: 制約付きマルコフ決定プロセス(CMDP)は、多くのアプリケーションにおいてますます重要になっている複数の目的を持つシーケンシャルな意思決定のシナリオをモデル化する。
しかし、モデルはしばしば不明であり、制約が満たされているか、少なくとも違反は時間に縛られていることを保証しながら、オンラインで学ぶ必要がある。
いくつかの最近の論文では、この非常に困難な問題を進展させているが、安全な政策の知識のような不満足な仮定を必要とするか、あるいは累積的後悔が高いかのどちらかである。
本稿では,このような仮定を必要とせず,理論的後悔境界や経験的にも非常によく機能するSafe PSRL(posterior sample-based RL)アルゴリズムを提案する。
このアルゴリズムは、後方サンプリング原理を用いて探索と搾取の効率的なトレードオフを実現し、悲観主義の考え方を活用し、限定的な制約違反のみに対処できる。
我々のアプローチは原始的アプローチに基づいている。
サブリニア $\tilde{\mathcal{O}}\left(H^{2.5} \sqrt{|\mathcal{S}|^2 |\mathcal{A}| K} \right)$上限はベイズ報酬目的後悔、すなわち$\tilde{\mathcal{O}}\left(1\right)$制約違反は$K$で$|\mathcal{S}|$-state,$|\mathcal{A}|$-state, $|\mathcal{A}|$-action and horizon $H$CMDPである。
関連論文リスト
- Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文 参考訳（メタデータ） (2024-01-14T14:14:19Z) - Model-Free, Regret-Optimal Best Policy Identification in Online CMDPs [17.62509045102346]
本稿では,CMDP(Constrained Markov Decision Processs)における最適ポリシー識別問題について考察する。
私たちは、モデルフリーで、後悔の少ないアルゴリズムに興味を持ち、確率の高いほぼ最適なポリシーを特定しています。
オンラインCMDPのサブ線形後悔と制約違反を伴う既存のモデルフリーアルゴリズムでは、最適ポリシーに対する収束保証は提供されない。
論文 参考訳（メタデータ） (2023-09-27T04:33:09Z) - Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
我々のアルゴリズムが $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping is linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ is the standardities of the state and action space。
論文 参考訳（メタデータ） (2023-05-15T05:37:32Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Towards Painless Policy Optimization for Constrained MDPs [46.12526917024248]
我々は、無限の地平線における政策最適化、$gamma$-discounted constrained Markov decision process (CMDP)について研究する。
我々の目標は、小さな制約違反で大きな期待された報酬を達成する政策を返却することである。
本稿では,任意のアルゴリズムに対して,報酬の準最適性と制約違反を拘束できる汎用的原始双対フレームワークを提案する。
論文 参考訳（メタデータ） (2022-04-11T15:08:09Z) - Achieving Zero Constraint Violation for Constrained Reinforcement
Learning via Primal-Dual Approach [37.80609997145897]
強化学習は、環境と対話しながらシーケンシャルな決定を行う必要があるアプリケーションで広く使われている。
決定要件がいくつかの安全制約を満たすことを含むと、問題はより難しくなります。
CMDP問題をモデルのない方法で解き、$epsilon$-optimal cumulative rewardを$epsilon$-factible Policyで達成することができる。
ここでの重要な疑問は、制約違反ゼロで$epsilon$-optimal cumulative rewardを達成できるかどうかである。
論文 参考訳（メタデータ） (2021-09-13T21:27:03Z) - Learning Policies with Zero or Bounded Constraint Violation for
Constrained MDPs [17.825031573375725]
我々は、マルコフ決定過程のエピソディックな枠組みで問題を提起する。
$tildemathcalO(sqrtK)$を許容し、$tildemathcalO(sqrtK)$制約違反を許容しながら、$tildemathcalO(sqrtK)$の報酬後悔を達成することができる。
厳密な安全ポリシーが知られている場合、任意の確率で制約違反をゼロに抑えることができることを示す。
論文 参考訳（メタデータ） (2021-06-04T19:46:55Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - Kernel-Based Reinforcement Learning: A Finite-Time Analysis [53.47210316424326]
モデルに基づく楽観的アルゴリズムであるKernel-UCBVIを導入する。
スパース報酬を伴う連続MDPにおける我々のアプローチを実証的に検証する。
論文 参考訳（メタデータ） (2020-04-12T12:23:46Z) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-03-01T17:47:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。