論文の概要: PAC Approximation and DIRECT Optimization for Parametric Markov Models
- arxiv url: http://arxiv.org/abs/2608.02184v1
- Date: Mon, 03 Aug 2026 13:07:59 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-04 15:07:25.572699
- Title: PAC Approximation and DIRECT Optimization for Parametric Markov Models
- Title（参考訳）: パラメトリックマルコフモデルに対するPAC近似とDIRECT最適化
- Abstract要約: パラメトリック決定過程(pMDP)のパラメータ合成と最適化問題を考える。
我々は,ほぼ正しい近似(PAC)を効率的に合成するために,Emphscenarioアプローチを採用する。
このPACフレームワークが統計的モデル検査(SMC)とどのように組み合わせられるかを示す。
- 参考スコア（独自算出の注目度）: 14.245289730315635
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we consider the parameter synthesis and optimization problem for parametric Markov decision processes (pMDPs), the extension of classical MDPs where exact probability values are replaced by parametric expressions. Computing the rational function $f_{\lsf}$ that maps parameter valuations to the satisfaction value of a PRCTL property $\lsf$ is a computationally expensive task, particularly for pMDPs where the optimal policy may vary across the parameter space. We adopt the \emph{scenario approach} to efficiently synthesize a probably approximately correct (PAC) approximation $\ApproxFunOfProperty{f}$ of $f_{\lsf}$: by sampling parameter configurations and solving a linear program, we obtain a polynomial approximation whose error margin $\margin$ is guaranteed, with prescribed confidence, for all but an $\errorRate$-fraction of the parameter domain under the sampling distribution. We further show how this PAC framework can be combined with statistical model checking (SMC), enabling the analysis of black-box parametric models. Building on the PAC approximation, we integrate the DIRECT (DIviding RECTangles) algorithm for derivative-free global optimization over the parameter space. We establish conditional optimality-gap guarantees: under explicit Lipschitz and PAC-good-set assumptions, the difference between the true optimum $f_{\lsf}(\parameters^{*})$ and the value found by DIRECT is bounded by a partition-diameter term and, in the PAC case, an additional approximation-error term. An empirical evaluation on 2997 benchmarks focuses on the new DIRECT-based optimization component. The results show that DIRECT variants solve fewer instances than the scenario optimizer, but on their common successful instances they often return slightly better objective values and usually run faster, while remaining close to the scenario values within the PAC margin.
- Abstract（参考訳）: 本稿では,パラメトリックマルコフ決定過程(pMDP)のパラメータ合成と最適化の問題について考察する。
有理関数 $f_{\lsf}$ はパラメータ評価値を PRCTL プロパティの満足度値にマッピングする。
パラメータ設定をサンプリングし、線形プログラムを解くことにより、パラメータ領域の$\errorRate$-fractionを除くすべてのパラメータ領域に対して、エラーマージン$\margin$が所定の信頼を持って保証される多項式近似を得る。
さらに,このPACフレームワークを統計的モデル検査(SMC)と組み合わせることで,ブラックボックスパラメトリックモデルの解析を可能にした。
PAC近似に基づいて、パラメータ空間上の微分自由大域最適化のためのDIRECTアルゴリズムを統合する。
明示的なリプシッツとPAC-グッドセットの仮定の下で、真の最適値である $f_{\lsf}(\parameters^{*})$ と DIRECT で見つかる値の差は、パーティション・ディメータ項で有界であり、PACの場合、追加の近似・エラー項である。
2997ベンチマークでの実証的な評価は、新しいDIRECTベースの最適化コンポーネントに焦点を当てている。
その結果、DIRECTの変種はシナリオオプティマイザよりも少ないインスタンスを解決していることがわかったが、一般的な成功例では、PACマージン内のシナリオ値に近づきながら、目標値をわずかに改善し、通常より高速に実行されることが多い。
関連論文リスト
- Wall-Clock Complexity for Zeroth-Order Optimization with Tunable Oracle Fidelity [68.54852541944625]
ブラックボックス最適化は勾配が利用できない場合に適用され、客観的評価は高価なシミュレーションに依存する。
本稿では, オラクル型, ノイズモデル, 最適化方式の選択が, アルゴリズムパラメータに対する壁面最適選択をいかに引き起こすかを示す。
論文 参考訳（メタデータ） (2026-05-29T14:24:54Z) - Inversion-Free Natural Gradient Descent on Riemannian Manifolds [5.556612138252781]
本稿では,凸パラメータを持つ確率分布に対する逆フリーな自然勾配法を提案する。
多様体の設定にはいくつかの利点がある: パラメータ制約を暗黙的に強制することができる。
サブクアドラティックストレージの複雑さを伴うアルゴリズムの限定メモリ変種が提案されている。
論文 参考訳（メタデータ） (2026-04-03T11:08:59Z) - Automatic Laplace Collapsed Sampling: Scalable Marginalisation of Latent Parameters via Automatic Differentiation [0.4999814847776097]
ALCS は高次元潜伏変数 $z$ を最大 (MAP) 最適化とラプラス近似によってスカラー寄与に分解する。
これにより、有効次元を$d_+ d_z$から$d_$に減らし、ベイズ的エビデンス計算は高次元設定で計算可能である。
自動微分により,ラプラスの向こう側から学生=t$のようなパラメトリックな家族への局所近似が可能となり,重み付き潜伏者のエビデンス推定が向上することを示す。
論文 参考訳（メタデータ） (2026-03-27T17:47:45Z) - $κ$-Explorer: A Unified Framework for Active Model Estimation in MDPs [20.944349513772067]
固有推定複雑性と訪問頻度を明示的に組み込んだ目的関数のパラメタ化ファミリを$U_$で導入する。
本稿では,Frank-Wolfe方式の探索アルゴリズムである$-Explorerを提案する。
MDPのベンチマーク実験では、$$-Explorerが既存の探索戦略よりも優れたパフォーマンスを提供することが示された。
論文 参考訳（メタデータ） (2026-02-23T22:56:32Z) - Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization [85.91302339486673]
我々は、s-正方形および非正方形不確実性集合の下で、一般的な政策パラメータ化を伴うロバストマルコフ決定過程(RMDP)について検討する。
無限状態空間に拡張する一般政策パラメタライゼーションに対する新しいリプシッツ・リプシッツ・スムースネス特性を証明した。
本研究では,S-正方形不確かさに対する勾配降下アルゴリズムと非正方形不確かさに対するFrank-Wolfeアルゴリズムを設計する。
論文 参考訳（メタデータ） (2026-02-11T21:44:20Z) - Parameter-free Algorithms for the Stochastically Extended Adversarial Model [59.81852138768642]
拡張逆数(SEA)モデルの既存のアプローチは、ドメインの直径$D$や損失関数のリプシッツ定数$G$といった問題固有のパラメータの事前知識を必要とする。
パラメータを不要にするためにOptimistic Online Newton Step (OONS) アルゴリズムを利用するパラメータフリー手法を開発した。
論文 参考訳（メタデータ） (2025-10-06T10:53:37Z) - Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
確率分析形式が不明なシミュレーションベースモデルにおける推論について検討する。
我々は、スコアを同時に追跡し、パラメータ更新を駆動する比率のないネスト型マルチタイムスケール近似(SA)手法を用いる。
我々のアルゴリズムは、オリジナルのバイアス$Obig(sqrtfrac1Nbig)$を排除し、収束率を$Obig(beta_k+sqrtfracalpha_kNbig)$から加速できることを示す。
論文 参考訳（メタデータ） (2024-11-20T02:46:15Z) - Efficient Learning of POMDPs with Known Observation Model in Average-Reward Setting [56.92178753201331]
我々は,POMDPパラメータを信念に基づくポリシを用いて収集したサンプルから学習することのできる観測・認識スペクトル(OAS)推定手法を提案する。
提案するOAS-UCRLアルゴリズムに対して,OASプロシージャの整合性を示し,$mathcalO(sqrtT log(T)$の残差保証を証明した。
論文 参考訳（メタデータ） (2024-10-02T08:46:34Z) - Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimization [11.11876897168701]
対人的マルコフ決定過程における学習の問題を考える。
本稿では,APO-MVPと呼ばれるアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-07-08T08:06:45Z) - Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation [53.17668583030862]
一般関数近似の文脈において,無限水平平均逆マルコフ決定過程(AMDP)について検討する。
最適化最適化(LOOP)と呼ばれる新しいアルゴリズムフレームワークを提案する。
我々は LOOP がサブ線形 $tildemathcalO(mathrmpoly(d, mathrmsp(V*)) sqrtTbeta )$ regret を達成することを示す。
論文 参考訳（メタデータ） (2024-04-19T06:24:22Z) - Smoothing Policy Iteration for Zero-sum Markov Games [9.158672246275348]
ゼロサムMGの解法としてスムージングポリシロバストネス(SPI)アルゴリズムを提案する。
特に、対向ポリシーは、作用空間上の効率的なサンプリングを可能にする重み関数として機能する。
また,SPIを関数近似で拡張することにより,Smooth adversarial Actor-critic (SaAC) と呼ばれるモデルベースアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-12-03T14:39:06Z) - Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳（メタデータ） (2021-12-23T18:47:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。