論文の概要: Regret-based Characterization, Information Limits, and the Sample Complexity of Auditing Adaptive Policies
- arxiv url: http://arxiv.org/abs/2611.05227v1
- Date: Tue, 03 Nov 2026 17:13:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-07 13:37:28.607895
- Title: Regret-based Characterization, Information Limits, and the Sample Complexity of Auditing Adaptive Policies
- Title（参考訳）: 監査適応政策のレグレットに基づく評価, 情報限界, およびサンプル複雑度
- Abstract要約: J()-J()$が$sum_t tr Cov(Q_t,_t)$に等しいことを示す。
また, エピソードMDPのための重要サンプリング監査機も提供する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: A policy can earn its performance by where it locates on average or by reacting to information. For any Markov policy $π$ in a finite-horizon MDP, let $ν$ be its open-loop marginal, which plays $π$'s average action distribution at each step. We show that $J(π)-J(ν)$ equals $\sum_t tr Cov(Q^ν_t,π_t)$ under endogenous dynamics. Audits based on immediate costs alone can have the wrong sign. Writing the covariance as a joint-versus-product gap gives the bound $|J(π)-J(ν)|\le\sum_t span_t\sqrt{I(s_t;a_t)/2}$, with a sharp constant. Hence, an MDP's adaptivity gap is bounded by the information that its optimal policy uses. Estimating $J(π)-J(ν)$ from $π$'s own bandit-feedback logs takes $Θ(\barχ^2 \log(1/η)/δ^2)$ rounds, where $\barχ^2$ is an average $χ^2$-divergence. At the same time, deterministic non-constant policies cannot be audited at all. We also provide an importance-sampling auditor for episodic MDPs.
- Abstract（参考訳）: ポリシーは、平均的な位置や情報に反応することで、そのパフォーマンスを得ることができる。
有限ホライゾン MDP における任意のマルコフポリシー $π$ に対して、$ν$ を開ループ辺辺とする。
J(π)-J(ν)$が内在力学の下で$\sum_t tr Cov(Q^ν_t,π_t)$と等しいことを示す。
直近のコストのみに基づく監査は、間違ったサインを持つことができます。
共分散を結合対積ギャップとして記述すると、有界な$|J(π)-J(ν)|\le\sum_t span_t\sqrt{I(s_t;a_t)/2} が、鋭い定数で与えられる。
したがって、MDPの適応性ギャップは、その最適方針が使用する情報によって制限される。
π$ から$J(π)-J(ν)$ を推定すると、$π$ のバンディット・フィードバック・ログは、$ ^2 \log(1/η)/δ^2$ のラウンドを取る。
同時に、決定論的非一貫性政策は、全く監査できない。
また, エピソードMDPのための重要サンプリング監査機も提供する。
関連論文リスト
- Explore Once, Evaluate Many: Multiple Policy Evaluation for Stochastic Linear Bandits [24.636690767654333]
線形報酬構造を持つコンテキスト帯において,K$ターゲットポリシーを同時に評価する方法を検討する。
PRISMAは、全ての目標ポリシーの値を、少なくとも1-$の確率で精度$varepsilon$に推定するアルゴリズムである。
論文 参考訳（メタデータ） (2026-10-15T17:22:59Z) - Parameter-Free Interval-Dynamic Regret under Heavy-Tailed Noise [55.29259818039367]
オンライン凸最適化を1ラウンドに1つの偏りのない下位段階と、未知の有限条件の雑音モーメントであるp$th, $1ple2$で検討する。
長さ$n$の固定区間$I$に対して、学習者は最適な全水平静的レートを含む1+log(T/n)$を達成する。
論文 参考訳（メタデータ） (2026-09-30T21:03:03Z) - The Variance of Thought: Policy Variance, Critical Forks, and Local Credit Assignment [2.6994604905555004]
政策分散はリターン分散の唯一の源であり、臨界フォークと呼ばれる状態において離散パルスに注入される。
ブートストラッピングは、生存確率の積を和に変換することによってモンテカルロの利点推定を除去する。
論文 参考訳（メタデータ） (2026-08-23T15:46:56Z) - Minimax PAC Bounds for Learning in Exogenous Contextual MDPs [26.599514971653615]
PAC学習は、割引係数$$、有限状態空間$mathcal X$、アクション空間$mathcal A$、コンテキスト空間$mathcal Z$を含む割引決定プロセスにおける。
論文 参考訳（メタデータ） (2026-06-23T21:02:18Z) - Near Sample-Optimal Reduction-based Policy Learning for Average Reward
MDP [58.13930707612128]
この研究は、平均報酬マルコフ決定過程(AMDP)における$varepsilon$-Optimal Policyを得る際のサンプルの複雑さを考察する。
我々は、状態-作用対当たりの$widetilde O(H varepsilon-3 ln frac1delta)$サンプルを証明し、$H := sp(h*)$は任意の最適ポリシーのバイアスのスパンであり、$varepsilon$は精度、$delta$は失敗確率である。
論文 参考訳（メタデータ） (2022-12-01T15:57:58Z) - Horizon-Free and Variance-Dependent Reinforcement Learning for Latent
Markov Decision Processes [62.90204655228324]
我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。
我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
論文 参考訳（メタデータ） (2022-10-20T21:32:01Z) - Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討
我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
論文 参考訳（メタデータ） (2022-10-05T22:52:00Z) - Horizon-Free Reinforcement Learning in Polynomial Time: the Power of
Stationary Policies [88.75843804630772]
我々は既存の境界に対して,$Oleft(mathrmpoly(S,A,log K)sqrtKright)を後悔するアルゴリズムを設計する。
この結果は、定常政策の近似力、安定性、および濃度特性を確立する新しい構造補題の列に依存している。
論文 参考訳（メタデータ） (2022-03-24T08:14:12Z) - The Curse of Passive Data Collection in Batch Reinforcement Learning [82.6026077420886]
高い利害関係のアプリケーションでは、アクティブな実験は危険すぎると考えられ、データはしばしば受動的に収集される。
バンディットやパッシブ、アクティブなデータ収集などの単純な場合も同様に効果的であるが、制御された状態のシステムからデータを集める場合、パッシブサンプリングの価格ははるかに高い。
論文 参考訳（メタデータ） (2021-06-18T07:54:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。