Regret-based Characterization, Information Limits, and the Sample Complexity of Auditing Adaptive Policies

Irene Aldridge

Papers from arXiv.org

Abstract: A policy can earn its performance by where it locates on average or by reacting to information. For any Markov policy $\pi$ in a finite-horizon MDP, let $\nu$ be its open-loop marginal, which plays $\pi$'s average action distribution at each step. We show that $J(\pi)-J(\nu)$ equals $\sum_t tr Cov(Q^\nu_t,\pi_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(\pi)-J(\nu)|\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(\pi)-J(\nu)$ from $\pi$'s own bandit-feedback logs takes $\Theta(\bar\chi^2 \log(1/\eta)/\delta^2)$ rounds, where $\bar\chi^2$ is an average $\chi^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.

Date: 2026-11
References: Add references at CitEc
Citations:

Downloads: (external link)
https://arxiv.org/pdf/2611.05227 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2611.05227

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().