Regret-based Characterization, Information Limits, and the Sample Complexity of Auditing Adaptive Policies
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 ∑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(ν)|≤∑t spant√(I(st;at)/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 Θ(χ̅2 log(1/η)/δ2) rounds, where χ̅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.
Related
- Finite-sample certification of coverage regret for budgeted document selection under adaptive stratified auditing
- Adaptive Probe Design for Auditing AI Agents
- Adaptive auditing of AI systems with anytime-valid guarantees
- The optimal information complexity of VC learning
- On the Adaptive Covering Complexity of Strings: Unifying Relative and Self-Referential Compression
BibTeX
@misc{aldridge2026regretbased,
title = {{Regret-based Characterization, Information Limits, and the Sample Complexity of Auditing Adaptive Policies}},
author = {Irene Aldridge},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05227},
eprint = {2611.05227},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05227},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Regret-based Characterization, Information Limits, and the Sample Complexity of Auditing Adaptive Policies
AU - Irene Aldridge
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.05227
UR - https://arxiv.org/abs/2611.05227
AB - 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 ∑_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(ν)|≤∑_t span_t√(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 Θ(χ̅^2 log(1/η)/δ^2) rounds, where χ̅^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.
ER -