論文の概要: Instance-Dependent Regret for CMDPs with Step-Wise Constraints
- arxiv url: http://arxiv.org/abs/2610.02520v1
- Date: Thu, 01 Oct 2026 21:49:16 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-06 00:14:30.095465
- Title: Instance-Dependent Regret for CMDPs with Step-Wise Constraints
- Title（参考訳）: ステップワイズ制約付きCMDPのインスタンス依存レグレット
- Abstract要約: 本稿では,段階的安全性制約によるマルコフ決定過程におけるオンライン学習について検討する。
本稿では,安全な部分グラフを効率よく学習する SVAE (Safe Variance-Adaptive Exploration) を提案する。
SVAEは$widetildemathcalO(sqrtSAHminmathbbV_,KmathrmVarstar+SsqrtAH3minK,mathcalC+S2AH2)$ over $K$の累積後悔を実現する。
- 参考スコア（独自算出の注目度）: 14.423965854349262
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study online learning in episodic tabular constrained Markov decision processes with step-wise safety constraints. In such a setting, the constraints induce a safe subgraph that shapes the variance of cumulative rewards under feasible policies and, consequently, the difficulty of learning. Exploiting this structure, however, requires learning which actions are safe while controlling constraint violations. We propose Safe Variance-Adaptive Exploration (SVAE), an efficient algorithm that learns candidate safe subgraphs and performs variance-adaptive optimistic planning within them. With high probability, SVAE achieves cumulative regret of order $\widetilde{\mathcal{O}}(\sqrt{SAH\min\{\mathbb{V}_Σ,K\mathrm{Var}^{\star}\}}+S\sqrt{AH^3\min\{K,\mathcal{C}\}}+S^2AH^2)$ over $K$ episodes, where $H$ is the horizon of a single episode, while $S$ and $A$ are the numbers of states and actions, respectively. Here, $\mathrm{Var}^{\star}$ is the maximum return variance among safe policies, $\mathbb{V}_Σ$ is the variance accumulated before the first unsafe action is encountered, and $\mathcal{C}$ captures the statistical complexity of eliminating actions incorrectly considered potentially safe. SVAE additionally attains $\widetilde{\mathcal{O}}(H\sqrt{SAK}+S^2AH^2)$ step-wise constraint violation and a gap-dependent violation bound that is polylogarithmic in $K$. Finally, we establish a lower bound showing that dependence on these instance-specific quantities is unavoidable.
- Abstract（参考訳）: 本研究では,段階的安全性制約を伴う表層制約付きマルコフ決定過程におけるオンライン学習について検討する。
このような設定では、制約は、実行可能なポリシーの下で累積報酬の分散を形作る安全なサブグラフを誘導し、その結果、学習の困難さを生じさせる。
しかし、この構造をエクスプロイトするには、制約違反を抑えながら、どのアクションが安全かを学ぶ必要がある。
本稿では,安全な部分グラフを学習し,その内部で分散適応型楽観的計画を実行するアルゴリズムである SVAE (Safe Variance-Adaptive Exploration) を提案する。
高確率で、SVAEは階数$\widetilde{\mathcal{O}}(\sqrt{SAH\min\{\mathbb{V}_Σ,K\mathrm{Var}^{\star}\}}+S\sqrt{AH^3\min\{K,\mathcal{C}\}}+S^2AH^2)$の累積後悔を達成する。
ここでは、$\mathrm{Var}^{\star}$は安全ポリシーの最大戻り分散であり、$\mathbb{V}_Σ$は、最初の安全でないアクションに遭遇する前に蓄積された分散であり、$\mathcal{C}$は、誤って潜在的に安全と考えられるアクションを排除する統計的複雑さをキャプチャする。
さらに、SVAEは$\widetilde{\mathcal{O}}(H\sqrt{SAK}+S^2AH^2)$ ステップワイド制約違反と、$K$で多対数となるギャップ依存の違反境界を得る。
最後に、これらのインスタンス固有の量への依存が避けられないことを示す低い境界を確立する。
関連論文リスト
- Improved Regret Bound for Safe Reinforcement Learning via Tighter Cost Pessimism and Reward Optimism [1.4999444543328293]
本稿では,新しいコストと報酬関数推定器に基づくモデルベースアルゴリズムを提案する。
我々のアルゴリズムは、$widetildemathcalO((bar C - bar C_b)-1H2.5 SsqrtAK)$の残念な上限を達成する。
論文 参考訳（メタデータ） (2024-10-14T04:51:06Z) - Safe Reinforcement Learning with Instantaneous Constraints: The Role of
Aggressive Exploration [20.630973009400574]
本稿では,線形関数近似を用いた安全強化学習(セーフRL)について,短時間の制約下で検討する。
提案アルゴリズムであるLSVI-AEは,コスト関数が線形であれば$tildecO(sqrtd3H4K)$ハード制約違反,コスト関数がRKHSに属する場合は$cO(Hgamma_K sqrtK)$ハード制約違反を実現する。
論文 参考訳（メタデータ） (2023-12-22T06:45:45Z) - Variance-aware robust reinforcement learning with linear function
approximation with heavy-tailed rewards [6.932056534450556]
AdaOFUL と VARA という2つのアルゴリズムを,重み付き報酬の存在下でのオンラインシーケンシャルな意思決定のために提案する。
AdaOFULは、$widetildemathcalObigの最先端の後悔境界を達成する。
VarA は $widetildemathcalO(dsqrtHmathcalG*K)$ のより厳密な分散を考慮した後悔境界を達成する。
論文 参考訳（メタデータ） (2023-03-09T22:16:28Z) - A Near-Optimal Algorithm for Safe Reinforcement Learning Under
Instantaneous Hard Constraints [43.895798638743784]
我々は,安全でない状態と動作を持つマルコフ決定過程に対して,第1次近似安全RLアルゴリズムを開発した。
これは、その設定における最先端の後悔と密に一致する後悔の$tildeO(fracd H3 sqrtdKDelta_c)$を達成する。
また、$tildeOmega(maxdH sqrtK, fracHDelta_c2)$の低いバウンドも提供しています。
論文 参考訳（メタデータ） (2023-02-08T23:42:04Z) - Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。
ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。
我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
論文 参考訳（メタデータ） (2023-02-07T02:22:31Z) - Horizon-Free and Variance-Dependent Reinforcement Learning for Latent
Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。
我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文 参考訳（メタデータ） (2022-10-20T21:32:01Z) - Safe Exploration for Constrained Reinforcement Learning with Provable
Guarantees [2.379828460137829]
そこで我々は,OPSRL(Optimistic-Pessimistic Safe Reinforcement Learning)アルゴリズムと呼ぶモデルベースの安全なRLアルゴリズムを提案する。
学習中の安全性制約に違反することなく, $tildemathcalO(S2sqrtA H7K/ (barC - barC_b)$ cumulative regretを達成できることを示す。
論文 参考訳（メタデータ） (2021-12-01T23:21:48Z) - Minimal Expected Regret in Linear Quadratic Control [79.81807680370677]
オンライン学習アルゴリズムを考案し、その期待された後悔を保証します。
当時のこの後悔は、$A$と$B$が未知の場合、$widetildeO((d_u+d_x)sqrtd_xT)$によって上界(i)となる。
論文 参考訳（メタデータ） (2021-09-29T14:07:21Z) - The Curse of Passive Data Collection in Batch Reinforcement Learning [82.6026077420886]
高い利害関係のアプリケーションでは、アクティブな実験は危険すぎると考えられ、データはしばしば受動的に収集される。
バンディットやパッシブ、アクティブなデータ収集などの単純な場合も同様に効果的であるが、制御された状態のシステムからデータを集める場合、パッシブサンプリングの価格ははるかに高い。
論文 参考訳（メタデータ） (2021-06-18T07:54:23Z) - Provably Efficient Safe Exploration via Primal-Dual Policy Optimization [105.7510838453122]
制約付きマルコフ決定過程(CMDP)を用いた安全強化学習(SRL)問題について検討する。
本稿では,関数近似設定において,安全な探索を行うCMDPの効率の良いオンラインポリシー最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-03-01T17:47:03Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。