---
title: "Regret-based Characterization, Information Limits, and the Sample Complexity of Auditing Adaptive Policies"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2611.05227v1"
permalink: "https://feed.astralor.com/items/itm_94b6d93af079a79f99f91be0"
published: "2026-11-03T17:13:24.000Z"
score: 56
channel: "ai"
tags: ["RAG","Regret-based Characterization","Information Limits","Sample Complexity","Auditing Adaptive Policies","For","Markov","MDP"]
---

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

## At a glance

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 dist…

## Key points

- 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.

## Full text

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.

---

Verify against the original before citing; curated by Astral Feed: https://feed.astralor.com/items/itm_94b6d93af079a79f99f91be0