論文の概要: Auditing Near-Optimal Policies Can Be Exponentially Hard: Conditional Query Lower Bounds via Occupancy Rashomon Capacity

• arxiv url: http://arxiv.org/abs/2606.00414v1
• Date: Fri, 29 May 2026 23:09:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-02 21:34:28.390954
• Title: Auditing Near-Optimal Policies Can Be Exponentially Hard: Conditional Query Lower Bounds via Occupancy Rashomon Capacity
• Title（参考訳）: ほぼ最適政策の監査は指数関数的に困難である: アクセシビリティ・ラショモン・キャパシティによる条件付きクエリローバウンド
• Abstract要約: 我々は,この現象を,羅生門容量の占有率の類似で定式化する。 占有度測定は、占有率のみの行動を特定する。 ノイズトリガー法則を処理後連続制御および視覚RL監査体制にマップする。
• 参考スコア（独自算出の注目度）: 6.908972852063454
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: When many reinforcement-learning policies achieve near-optimal return, a post-hoc auditor may have to distinguish among many behaviorally distinct but return-equivalent policies. We formalize this phenomenon through an occupancy-measure analogue of Rashomon capacity: the metric entropy of the near-optimal occupancy region, computed relative to an audited deployment class. Because occupancy measures identify behavior only up to occupancy equivalence, we formulate auditing at the occupancy-class level and distinguish exact local-query oracles from noisy sample-query oracles. Our main exact-query result is conditional: if the audited class contains a $2/H$-separated near-optimal packing whose local signatures are $b$-sparse, then exact local-query auditing requires $Ω(M/b)$ queries; when the packing realizes deployment-class capacity and $b=O(1)$, this becomes $Ω(2^{\Hopt^\cF(\eps)})$. We give a finite discounted hidden-branch MDP attaining this bound and show the exact Bayes success law. For noisy hidden-trigger testing, we prove a mixture lower bound of order $M/β$, where $β$ is the per-sample KL signal, yielding $Ω(2^{\Hopt^\cF(\eps)}/(ρ^2Δ^2))$ for capacity-order packings with $β=O(ρ^2Δ^2)$. We also provide a static target-recognition information lower bound, a transcript-compatible oracle-cover verification upper bound, and a canonical occupancy regularizer whose regularized audited capacity collapses when a trusted reference occupancy is available. Controlled benchmarks distinguish positive sparse-signature instances from high-capacity negative controls where exact auditing is easy, and map the noisy-trigger law to post-processed continuous-control and visual-RL auditing regimes.
• Abstract（参考訳）: 多くの強化学習政策がほぼ最適リターンを達成した場合、ポストホック監査官は行動学的に異なるが、リターン等価な政策を区別する必要があるかもしれない。 我々は,この現象を,監査された展開クラスに対して計算された,ほぼ最適占有領域の計量エントロピーという,ラショモン容量の占有率の類似で定式化する。 占有度測定は, 占有率のみの行動を特定するため, 被占領層レベルでの監査を定式化し, 局所的なオーラクルをノイズの多いサンプルオーラクルと区別する。 監査されたクラスが、ローカルシグネチャが$b$sparseである2/H$分離されたニア最適パッキングを含むなら、正確なローカルクエリ監査には$Ω(M/b)$クエリが必要です。 我々は、この限界に達した有限割引の隠れブランチ MDP を与え、ベイズの成功法を正確に示す。 ノイズの多い隠れトリガーテストでは、$M/β$の混合境界を証明し、$β$はサンプルごとのKL信号であり、$Ω(2^{\Hopt^\cF(\eps)}/(ρ^2Δ^2))$は$β=O(ρ^2Δ^2)$である。 また、静的な目標認識情報の下限、トランスクリプト互換のオラクル被覆検証上限、および、信頼された参照占有が利用可能になったときに正規化された監査能力が崩壊する正準占有正規化器を提供する。 制御されたベンチマークは、正のスパース署名インスタンスを、正確な監査が容易な高容量の負の制御と区別し、ノイズトリガー法則を後処理された連続的な制御と視覚的RL監査体制にマッピングする。

関連論文リスト

• Memorization Is Not Extraction: Tight Differential-Privacy Bounds and Audit Blind Spots [9.539275654775706]
  大規模言語モデルの記憶は、形式的関係が不明な定義の動物園を通じて測定される。 差分プライバシー(DP)は,これらすべてに対して同時にプロキシとして扱われることを示す。
  論文  参考訳（メタデータ） (2026-08-27T23:28:08Z)
• Learning Not to Optimize: Physics-Informed Action-Space Reshaping for Intent-Based Network Control [50.46501177871741]
  LNOQRD は小物候補を75.9% で削減し、90.8% でニアオラクルのカバレッジを維持している。 実験の結果、LNOQRDは実用性と意図の満足度が最も高く、かつ、法律違反が最低で、世代後レイテンシが低いことがわかった。
  論文  参考訳（メタデータ） (2026-08-02T00:27:01Z)
• One Human, $N$ Agents: Audit-Budget Allocation for LLM Agent Fleets under Miscalibrated, Correlated Confidence [41.99844472131922]
  一人の人間が1ラウンド当たり$N$ LLMエージェントを予算$B ll N$監査で監査しなければならない。 我々はこれを、2段階のガウス的コーパスに対する予算付きノイズ検査としてモデル化し、信頼度の高い監査がランダムである場合の誤校正しきい値($*$過去)を特定する。
  論文  参考訳（メタデータ） (2026-07-30T14:52:36Z)
• Which Model Is Actually Serving You? IRIS: Budgeted Black-Box Auditing of Model Substitution and Routing Dilution in LLM Gateways [6.964275075635626]
  返却されたテキストのみを必要とする監査である$mathrmIRIS$を提示します。 安価なパイロットは指数的なクエリエラーの崩壊に適合し、疑わしいクエリが発行される前にその予算を凍結する。 $mathrmIRIS$ match or beats detection on shared task, and adapt allocationss the matched-budget target-hit rate from 7,3$% to 8,7$%。
  論文  参考訳（メタデータ） (2026-07-23T02:32:08Z)
• BOKBO (Best of K Bad Options): Calibrated Abstention for VLA Policies [1.3918848543076061]
  VLA(Vision-suite-action)ポリシー、RoboMonkey、SEAL、MG-Select、V-GPSなどのメソッドに対するテストタイムスケーリングは、推論時にK候補アクションチャンクをサンプリングし、検証-ベストを実行する。 K-sample VLA推論のための最初の共形吸収層であるBOKBOを提案する。
  論文  参考訳（メタデータ） (2026-05-28T23:39:09Z)
• Auditing Privacy in Multi-Tenant RAG under Account Collusion [1.253312107729806]
  マルチテナント検索拡張生成サービスは、ログ単位の差分プライバシーを操作リーク境界として宣伝する。 我々は、同一インデックスのマルチアカウント共謀をプライバシ境界障害とみなす。 修正されていないRAGデプロイメントに対して動作する最初の監査プロトコルを設計する。
  論文  参考訳（メタデータ） (2026-05-19T13:41:59Z)
• A Benchmark for Strategic Auditee Gaming Under Continuous Compliance Monitoring [1.253312107729806]
  継続的デプロイ後のコンプライアンス監査は、戦略的なゲームのクラスを作成します。 我々は,時間的方針にコミットする監査者と適応監査人との間に,$T$ラウンドのStackelbergゲームとして継続的監査を形式化する。
  論文  参考訳（メタデータ） (2026-05-07T14:28:34Z)
• On the Optimal Sample Complexity of Offline Multi-Armed Bandits with KL Regularization [54.77408659142336]
  Kullback-Leibler (KL) の正規化は、オフラインの意思決定で広く使われている。 大規模な正規化の下では$tildeO(SAC*/)$のサンプル複雑性を実現する。 また、よりシャープなサンプル複雑性の下界も提供し、これは正規化強度の全範囲にわたる上界と一致する。
  論文  参考訳（メタデータ） (2026-05-04T01:46:35Z)
• Envy-Free Allocation of Indivisible Goods via Noisy Queries [66.16311857301167]
  エージェントのバリュエーションを直接観察できない、かなり分割不可能な商品を割り当てる問題を導入する。 本手法では,要求されるクエリ数の上限値と上限値の上限値を求める。 我々の上限は、非適応的なクエリと計算時間で実行される単純なしきい値に基づくアロケーションアルゴリズムに基づいている。
  論文  参考訳（メタデータ） (2026-02-06T03:44:40Z)
• Almost Asymptotically Optimal Active Clustering Through Pairwise Observations [59.20614082241528]
  そこで本研究では, ノイズと能動的に収集された応答を用いて, M$アイテムを未知数の$K$個別グループにクラスタリングするための新しい分析フレームワークを提案する。 クラスタリングの精度に対する望ましい信頼性を達成するのに必要なクエリ数の基本的下位境界を確立する。 我々は、一般化された同値比統計の計算可能な変種を開発し、その下限に対する性能ギャップを正確に推定できることを実証的に示す。
  論文  参考訳（メタデータ） (2026-02-05T14:16:47Z)
• Reinforcement Learning with Verifiable yet Noisy Rewards under Imperfect Verifiers [90.50039419576807]
  RLVR(Reinforcement Learning with Verifiable Rewards)は、人為的なラベル付けを避けるために、自動検証に対するポリシーを訓練する。 認証ハッキングの脆弱性を軽減するため、多くのRLVRシステムはトレーニング中にバイナリ$0,1$の報酬を破棄する。 この選択にはコストがかかる:textitfalse negatives(正しい回答、FNを拒絶)とtextitfalse positives(間違った回答、FPを受け入れる)を導入する。
  論文  参考訳（メタデータ） (2025-10-01T13:56:44Z)
• The Alignment Bottleneck [0.0]
  ループを2段階のカスケード$U to H to Y$ given$S$、認知能力$C_textcog|S$、平均総容量$barC_texttot|S$としてモデル化する。 これは、分離可能なコードブックと、KL項が$m, barC_texttot|S$で同じチャネルで制御されるPAC-Bayes上界とで証明されたデータサイズ非依存のファノ下界をペアする。
  論文  参考訳（メタデータ） (2025-09-19T12:38:30Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  我々は$f$-divergence-regularized offline policy learningを分析する。 逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。 これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
  論文  参考訳（メタデータ） (2025-02-09T22:14:45Z)
• Monotone Individual Fairness [3.20902205123321]
  オンライン学習者が予測精度を最大化し、類似した個人が同じように扱われることを保証することを目的として、オンライン学習の問題を個別の公正さで再考する。 監査者からのフィードバックを集約できる監査方式を検討する。 ここでは, 後悔, フェアネス違反の数に対して$(mathcalO(T2/3+2b),mathcalO(T5/6-b))$を0leq b leq$で上限とするオラクル効率アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-03-11T15:32:56Z)
• Efficient Reinforcement Learning with Impaired Observability: Learning to Act with Delayed and Missing State Observations [92.25604137490168]
  本稿では,制御系における効率的な強化学習に関する理論的研究を紹介する。 遅延および欠落した観測条件において,RL に対して $tildemathcalO(sqrtrm poly(H) SAK)$ という形でアルゴリズムを提示し,その上限と下限をほぼ最適に設定する。
  論文  参考訳（メタデータ） (2023-06-02T02:46:39Z)
• Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations [79.66404989555566]
  我々は、リッチな観測空間を持つより現実的な非依存的RLの設定と、近似的ポリシーを含まないような固定されたポリシーのクラス$Pi$を考える。 我々は,MDPの階数$d$の誤差が有界な設定のためのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-22T03:20:40Z)

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

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