論文の概要: Exponential Hardness of Off-Policy Evaluation under History-Dependent Logging

• arxiv url: http://arxiv.org/abs/2609.19135v1
• Date: Wed, 16 Sep 2026 17:56:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-20 08:55:53.927745
• Title: Exponential Hardness of Off-Policy Evaluation under History-Dependent Logging
• Title（参考訳）: 履歴に依存したロギングにおけるオフポリティ評価の指数的硬さ
• Abstract要約: ログされたデータセットは、すべての隠れた状態を頻繁に訪問でき、それでもターゲットポリシーの価値について指数関数的に非形式的であることを示す。 有向二車線グリッドワールドは構成を実現し、軌道シミュレーションはその有限サンプル予測と一致する。
• 参考スコア（独自算出の注目度）: 0.10152838128195468
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Can a logged dataset visit every hidden state frequently and still be exponentially uninformative about a target policy's value? We show that it can when the logger depends on history. For every horizon $H \ge 3$, we construct two POMDPs with at most two latent states per stage, three actions, and a common logger with three memory states. Action coverage, belief coverage, and two behavior-marginal outcome-revealing conditions all have constants independent of $H$. Nevertheless, evaluating a known deterministic target policy to accuracy $1/8$ requires $Θ((3/2)^H \log(1/δ))$ logged episodes at confidence $1-δ$, for $0 < δ\le 1/4$, even when both candidate models are known. The mechanism is simple: a reset erases the unknown transition that determines the target value. We characterize the resulting statistical experiment exactly and obtain a matching optimal estimator. A directed two-lane gridworld realizes the construction, and trajectory simulations agree with its finite-sample prediction. The result establishes intractability for the history-dependent-logging, model-based case posed by Zhang and Jiang (2025, arXiv:2503.01134), under their behavior-marginal definition of revealing.
• Abstract（参考訳）: ログされたデータセットは、すべての隠れた状態を頻繁に訪れ、ターゲットポリシーの価値について指数関数的に非形式的であるか? ログが履歴に依存する場合、それが可能であることを示す。 すべての水平線$H \ge 3$に対して、ステージ毎に少なくとも2つの潜伏状態を持つ2つのPOMDP、3つのアクション、そして3つのメモリ状態を持つ共通のロガーを構築します。 行動のカバレッジ、信念のカバレッジ、および2つの行動結婚の成果報告条件はすべて、$H$とは無関係に定数を持つ。 それでも、既知の決定論的ターゲットポリシーを精度1/8$に評価するには、信頼度1-δ$で1-δ$$$0 < δ\le 1/4$のログ付きエピソードを、両方の候補モデルが知られている場合でも、$$((3/2)^H \log(1/δ))を要求される。 リセットは、ターゲット値を決定する未知の遷移を消去する。 得られた統計的実験を正確に特徴付け、一致した最適推定器を得る。 有向二車線グリッドワールドは構成を実現し、軌道シミュレーションはその有限サンプル予測と一致する。 この結果は、Zhang と Jiang (2025, arXiv:2503.01134) が提示した歴史に依存した、モデルに基づくケースに対する、その行動・文法的定義の下での難易度を確立している。

関連論文リスト

• The Variance of Thought: Policy Variance, Critical Forks, and Local Credit Assignment [2.6994604905555004]
  政策分散はリターン分散の唯一の源であり、臨界フォークと呼ばれる状態において離散パルスに注入される。 ブートストラッピングは、生存確率の積を和に変換することによってモンテカルロの利点推定を除去する。
  論文  参考訳（メタデータ） (2026-08-23T15:46:56Z)
• Reading the Room: Implicit Confusion Encoding in Recurrent World Model States [0.0]
  我々は、予測エラーのトラックの混乱を軽減するために、繰り返し発生する隠れ状態$h_t$を示す。 これは、新しい入力をフラグするアンサンブルの不一致と、現在悪い予測をフラグするリコンストラクションエラーとを機能的に区別している。
  論文  参考訳（メタデータ） (2026-08-21T19:32:38Z)
• Sensitivity to Subjective Expected Utility Maximization: A Methodological Study, with an Illustrative Application to LLM Decision-Making [0.0]
  車両はソフトマックス選択モデルであり、感度パラメータはSEU値の代替品に$$である。 コントリビューションは、$$と、Stansbergで検証された信念とユーティリティパラメータ$(, )$に対する識別可能性の結果のシーケンスである。 2対2のアプリケーションは、実際の選択データに基づいてエンドツーエンドで実行し、4つのセルのうち2つのセルで、構造化された$$エフェクトサンプリングを検出する。
  論文  参考訳（メタデータ） (2026-07-08T00:29:18Z)
• Score-Repellent Monte Carlo: Toward Efficient Non-Markovian Sampler with Constant Memory in General State Spaces [48.37754141688874]
  本稿では,スコアと状態表現の次元である$Rd$のスコア評価の実行平均で履歴を要約するフレームワークを提案する。 この歴史は指数的なスコア傾きによって代理対象に変換され、歴史に基づく反発の大きさを制御する際の反発の強さを表す$$がインデックス付けされる。 連続目標モデルと離散エネルギーベースモデルの実験では、メモリ使用率を$O(d)$に抑えつつ、推定値の分散とモードカバレッジを改善した。
  論文  参考訳（メタデータ） (2026-04-24T18:39:50Z)
• Epistemic Observability in Language Models [0.0]
  製造時に高い信頼性を報告できるモデルがあることがわかりました。 正式な仮定では、これは能力ギャップではなく観察的なギャップである。 我々は,計算副産物を輸出することで不合理性から逃れるテンソルインタフェースを構築した。
  論文  参考訳（メタデータ） (2026-03-20T21:59:34Z)
• Consistency-Guided Decoding with Proof-Driven Disambiguation for Three-Way Logical Question Answering [4.878198984786631]
  3方向の論理的質問応答(QA)は、$True/False/Unknown$を前提セット$S$の仮説に割り当てる。 CGD-PDは1つの3ウェイ分類器を$H$と$H$の機械式の両方でクエリする軽量なテスト時間層である。
  論文  参考訳（メタデータ） (2026-03-12T18:26:16Z)
• Causal Identification from Counterfactual Data: Completeness and Bounding Results [54.147490305295456]
  本研究では,任意のレイヤ3分布の集合から対実的なクエリを識別するアルゴリズムを開発した。 我々は、物理的に実現可能な分布から反事実を特定できる理論的限界を確立する。 我々は、そのような量の新たな解析的境界を、実現可能な対実データを用いて導出する。
  論文  参考訳（メタデータ） (2026-02-26T22:48:12Z)
• The Curse of Passive Data Collection in Batch Reinforcement Learning [82.6026077420886]
  高い利害関係のアプリケーションでは、アクティブな実験は危険すぎると考えられ、データはしばしば受動的に収集される。 バンディットやパッシブ、アクティブなデータ収集などの単純な場合も同様に効果的であるが、制御された状態のシステムからデータを集める場合、パッシブサンプリングの価格ははるかに高い。
  論文  参考訳（メタデータ） (2021-06-18T07:54:23Z)
• Provably Breaking the Quadratic Error Compounding Barrier in Imitation Learning, Optimally [58.463668865380946]
  状態空間 $mathcalS$ を用いたエピソードマルコフ決定過程 (MDPs) における模擬学習の統計的限界について検討する。 rajaraman et al (2020) におけるmdアルゴリズムを用いた準最適性に対する上限 $o(|mathcals|h3/2/n)$ を定式化する。 Omega(H3/2/N)$ $mathcalS|geq 3$ であるのに対して、未知の遷移条件はよりシャープレートに悩まされる。
  論文  参考訳（メタデータ） (2021-02-25T15:50:19Z)
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs [132.88757893161699]
  我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。 DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
  論文  参考訳（メタデータ） (2020-12-29T14:06:09Z)
• Nearly Minimax Optimal Reward-free Reinforcement Learning [88.75843804630772]
  本稿では、特にバッチ強化学習に適した報酬不要強化学習フレームワークと、複数の報酬関数に対するポリシーを必要とするシナリオについて検討する。 textbfStaged textbfSampling + textbfTruncated textbfPlanning (algoname) という新しい効率的なアルゴリズムを提供しています。
  論文  参考訳（メタデータ） (2020-10-12T17:51:19Z)

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

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