Frontend
Regret-based Characterization, Information Limits, and the Sample Complexity of Auditing Adaptive Policies
arXiv math.IT0 views
arXiv:2611.05227v1 Announce Type: cross 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.
Source:https://arxiv.org/abs/2611.05227PreviousDo Ray-Traced Cities Make a Better Channel Prior for an Unseen Site? A Pre-Registered Study in Simulation, and a Test on Measured Channels that Reverses ItNextDomain-Adaptive Deep Joint Source-Channel Coding for Image Classification
Related posts

Backend Interview Question: Why Does Loading 20 Orders Run 21 Queries?
0dev.to
A New Go API for JSON
0Hacker News
How to Add LocalBusiness Schema to a WordPress Site (and Check It Works)
0dev.to Tutorial
I got tired of dead invite codes, so I started checking them every week
0dev.to Beginners
Tencent launches Hy4 with visual understanding and computer-use features
0dev.to OpenSource
Run TypeScript in Node.js Without a Build Step: Type Stripping Tested on Node 22, 24 and 26
0dev.to TypeScript