Metraipolis › archive › dc_ca99b54adcd5
Regret-based Characterization, Information Limits, and the Sample Complexity of Auditing Adaptive Policies — arXiv:2611.05227
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.05227
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-04T12:42:53.468Z
- SHA-256 of the archived text
d324d5bfc8ee41df00e1c36d92ba24e1a0b7a3db9641d6bd9752ae0313b04176- Stable URL of this page
https://metraipolis.com/documento/dc_ca99b54adcd5
How to cite
Regret-based Characterization, Information Limits, and the Sample Complexity of Auditing Adaptive Policies — arXiv:2611.05227 — arXiv (en), https://arxiv.org/abs/2611.05227 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ca99b54adcd5 (Metraipolis archive dc_ca99b54adcd5, sha256 d324d5bfc8ee41df00e1c36d92ba24e1a0b7a3db9641d6bd9752ae0313b04176)
BibTeX
@misc{dcca99b54adcd5,
title = {Regret-based Characterization, Information Limits, and the Sample Complexity of Auditing Adaptive Policies — arXiv:2611.05227},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.05227},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ca99b54adcd5; sha256 d324d5bfc8ee41df00e1c36d92ba24e1a0b7a3db9641d6bd9752ae0313b04176},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05227. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Econometrics (econ.EM) ; Information Theory (cs.IT); Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2611.05227 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T12:29:47.410Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).