論文の概要: PAC Learnability of Scenario Decision-Making Algorithms: Necessary Conditions and Sufficient Conditions

• arxiv url: http://arxiv.org/abs/2501.08887v2
• Date: Wed, 27 Aug 2025 10:01:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-08-28 14:51:02.897812
• Title: PAC Learnability of Scenario Decision-Making Algorithms: Necessary Conditions and Sufficient Conditions
• Title（参考訳）: シナリオ意思決定アルゴリズムのPAC学習可能性:必要条件と十分条件
• Authors: Guillaume O. Berger, Raphaël M. Jungers,
• Abstract要約: シナリオ決定アルゴリズムの確率的近似(PAC)特性について検討する。 これらの条件は一般に必要ではないことを実証する。 シナリオ決定アルゴリズムにおけるVC次元の類似として機能する,dVC次元と呼ばれる新しい量を導入する。
• 参考スコア（独自算出の注目度）: 1.2031796234206136
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate the Probably Approximately Correct (PAC) property of scenario decision algorithms, which refers to their ability to produce decisions with an arbitrarily low risk of violating unknown safety constraints, provided a sufficient number of realizations of these constraints are sampled. While several PAC sufficient conditions for such algorithms exist in the literature -- such as the finiteness of the VC dimension of their associated classifiers, or the existence of a compression scheme -- it remains unclear whether these conditions are also necessary. In this work, we demonstrate through counterexamples that these conditions are not necessary in general. These findings stand in contrast to binary classification learning, where analogous conditions are both sufficient and necessary for a family of classifiers to be PAC. Furthermore, we extend our analysis to stable scenario decision algorithms, a broad class that includes practical methods like scenario optimization. Even under this additional assumption, we show that the aforementioned conditions remain unnecessary. Furthermore, we introduce a novel quantity, called the dVC dimension, which serves as an analogue to the VC dimension for scenario decision algorithms. We prove that the finiteness of this dimension is a PAC necessary condition for scenario decision algorithms. This allows to (i) guide algorithm users and designers to recognize algorithms that are not PAC, and (ii) contribute to a comprehensive characterization of PAC scenario decision algorithms.
• Abstract（参考訳）: シナリオ決定アルゴリズムの確率的近似(PAC)特性について検討する。これは、未知の安全制約に違反するリスクを任意に低く抑えながら決定を下す能力を示すものであり、これらの制約の十分な数の実現が得られた場合のものである。 このようなアルゴリズムには、関連する分類器のVC次元の有限性や圧縮スキームの存在など、いくつかのPACの十分な条件が存在するが、これらの条件も必要かどうかは不明である。 本研究では,これらの条件が一般には不要であることを示す。 これらの知見は、分類器のファミリーがPACであるのに、類似条件が十分かつ必要である二分分類学習とは対照的である。 さらに、シナリオ最適化のような実践的な手法を含む幅広いクラスである、安定したシナリオ決定アルゴリズムに分析を拡張します。 この追加仮定の下でも、上記の条件はいまだに不要であることを示す。 さらに、シナリオ決定アルゴリズムのVC次元の類似として機能する、dVC次元と呼ばれる新しい量を導入する。 この次元の有限性はシナリオ決定アルゴリズムのPAC要求条件であることを示す。 これにより (i)PAC以外のアルゴリズムを利用者やデザイナーが認識できるように誘導し、 (II)PACシナリオ決定アルゴリズムの包括的特徴付けに寄与する。

関連論文リスト

• Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning [66.4260157478436]
  政策学習における強化学習について検討する。 目的は、特定の種類の利害関係において最高の政策と競争力のある政策を見つけることである。
  論文  参考訳（メタデータ） (2025-07-06T14:40:05Z)
• Constrained Online Decision-Making: A Unified Framework [14.465944215100746]
  本稿では,段階的実現可能性制約による逐次意思決定の一般的な定式化について検討する。 本稿では,既存の制約付き学習問題を抽出する統一的なアルゴリズムフレームワークを提案する。 この結果は、理論と実践の両方において、制約付きシーケンシャルな意思決定のための原則化された基盤を提供する。
  論文  参考訳（メタデータ） (2025-05-11T19:22:04Z)
• Improved Compression Bounds for Scenario Decision Making [0.7673339435080445]
  我々は、不確実性のサンプルを描画し、そのサンプルに基づいて意思決定を行うことにより、不確実な環境での意思決定方法を示す。 確率保証は、障害のリスクが与えられた最大許容値を超える決定につながるシナリオの集合をサンプリングする確率に縛られる。 我々は,問題に対するより強い仮定を必要とせず,既存の問題を改善する新たな限界を提案する。
  論文  参考訳（メタデータ） (2025-01-15T15:53:34Z)
• Flipping-based Policy for Chance-Constrained Markov Decision Processes [9.404184937255694]
  本稿では,CCMDP(Chance-Constrained Markov Decision Processs)のためのテキストフリップに基づくポリシーを提案する。 フリップベースのポリシーは、2つのアクション候補の間で潜在的に歪んだコインを投げて次のアクションを選択する。 提案手法は,既存の安全RLアルゴリズムの性能を安全性の制約と同じ限度で向上させることを実証する。
  論文  参考訳（メタデータ） (2024-10-09T02:00:39Z)
• Algorithms for learning value-aligned policies considering admissibility relaxation [1.8336820954218835]
  価値認識工学の新たな分野は、ソフトウェアエージェントとシステムは価値を意識すべきである、と主張している。 本稿では,局所的なアライメントに基づく戦略のための$epsilontext-ADQL$と,一連の決定のための$epsilontext-CADQL$という2つのアルゴリズムを提案する。 干ばつシナリオにおいて,水分散問題における効率性を検証した。
  論文  参考訳（メタデータ） (2024-06-07T11:10:07Z)
• Learning Adversarial MDPs with Stochastic Hard Constraints [37.24692425018]
  我々は,制約付きマルコフ決定過程(CMDP)におけるオンライン学習について,敵対的損失と厳しい制約を伴って検討した。 我々の研究は、敵の損失と厳しい制約の両方にかかわるCMDPを初めて研究した。
  論文  参考訳（メタデータ） (2024-03-06T12:49:08Z)
• Resilient Constrained Reinforcement Learning [87.4374430686956]
  本稿では,複数の制約仕様を事前に特定しない制約付き強化学習(RL)のクラスについて検討する。 報酬訓練目標と制約満足度との間に不明確なトレードオフがあるため、適切な制約仕様を特定することは困難である。 我々は、ポリシーと制約仕様を一緒に検索する新しい制約付きRLアプローチを提案する。
  論文  参考訳（メタデータ） (2023-12-28T18:28:23Z)
• Likelihood Ratio Confidence Sets for Sequential Decision Making [51.66638486226482]
  確率に基づく推論の原理を再検討し、確率比を用いて妥当な信頼シーケンスを構築することを提案する。 本手法は, 精度の高い問題に特に適している。 提案手法は,オンライン凸最適化への接続に光を当てることにより,推定器の最適シーケンスを確実に選択する方法を示す。
  論文  参考訳（メタデータ） (2023-11-08T00:10:21Z)
• Offline Minimax Soft-Q-learning Under Realizability and Partial Coverage [100.8180383245813]
  オフライン強化学習(RL)のための値ベースアルゴリズムを提案する。 ソフトマージン条件下でのバニラQ関数の類似した結果を示す。 我々のアルゴリズムの損失関数は、推定問題を非線形凸最適化問題とラグランジフィケーションとしてキャストすることによって生じる。
  論文  参考訳（メタデータ） (2023-02-05T14:22:41Z)
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
  目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。 アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
  論文  参考訳（メタデータ） (2022-11-29T05:52:17Z)
• Safe Exploration Incurs Nearly No Additional Sample Complexity for Reward-free RL [43.672794342894946]
  Reward-free reinforcement learning (RF-RL) は、未知の環境を探索するランダムなアクションテイクに依存する。 このような安全な探索要求が、得られた政策の計画における望ましい最適性を達成するために、対応するサンプルの複雑さにどのように影響するかは、いまだ不明である。 本稿では,Safe reWard-frEe ExploraTion (SWEET) フレームワークを提案し,Tabular-SWEET と Low-rank-SWEET というアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-06-28T15:00:45Z)
• Stochastic Conservative Contextual Linear Bandits [8.684768561839146]
  不確実性の下での安全なリアルタイム意思決定の問題について検討する。 我々は、リアルタイム意思決定のための保守的な文脈的帯域幅の定式化を定式化する。
  論文  参考訳（メタデータ） (2022-03-29T14:50:50Z)
• Pointwise Feasibility of Gaussian Process-based Safety-Critical Control under Model Uncertainty [77.18483084440182]
  制御バリア関数(CBF)と制御リアプノフ関数(CLF)は、制御システムの安全性と安定性をそれぞれ強化するための一般的なツールである。 本稿では, CBF と CLF を用いた安全クリティカルコントローラにおいて, モデル不確実性に対処するためのガウスプロセス(GP)に基づくアプローチを提案する。
  論文  参考訳（メタデータ） (2021-06-13T23:08:49Z)
• Risk-Constrained Thompson Sampling for CVaR Bandits [82.47796318548306]
  CVaR(Conditional Value at Risk)として知られる量的ファイナンスにおける一般的なリスク尺度について考察する。 本稿では,トンプソンサンプリングに基づくCVaR-TSアルゴリズムの性能について検討する。
  論文  参考訳（メタデータ） (2020-11-16T15:53:22Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。