Metraipolis › archive › dc_df7e7e9bf571

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-04T21:53:29.356Z
SHA-256 of the archived text
a760c0ff080f735702f20df9dcd2f23c601f3f2cedf90bd9b43d624a6474257e
Stable URL of this page
https://metraipolis.com/documento/dc_df7e7e9bf571

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_df7e7e9bf571 (Metraipolis archive dc_df7e7e9bf571, sha256 a760c0ff080f735702f20df9dcd2f23c601f3f2cedf90bd9b43d624a6474257e)
BibTeX
@misc{dcdf7e7e9bf571,
  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_df7e7e9bf571; sha256 a760c0ff080f735702f20df9dcd2f23c601f3f2cedf90bd9b43d624a6474257e},
  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-04T21:38:49.837Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).