Theorem 3.4, p.3 — covariance characterization:
ProvedAuditAdapt.theorem_3_4Let be a finite-horizon MDP with finite state and action sets, and let be a (randomized, time-dependent) Markov policy. Let be its open-loop marginal, with , and write , with . Let be the joint law of , with marginals and . Then
Moreover, each summand of (3) and of (4) is unchanged if is replaced by , for any .
The identity holds under fully endogenous dynamics: actions influence future states, and this feedback is accounted for by averaging over the policy's own state laws and by scoring actions with the action-values of , not of and not the immediate costs. The adaptivity cost is therefore a sum of covariances between the action-values of the open-loop marginal and the policy's state-dependent action distribution; the invariance allows to be replaced by the advantage .
Formalization Note The MDP, policies, and are those of the published FoundationsRL.RLBasics layer, with = d1 and = R t. is the form of §2 (trCov), and the summands of (4) are jointMinusProduct. The only hypothesis on is that it is a Markov policy; that is one is a theorem of the mission, not an assumption.
Differences from the source:
- encoding: steps t = 1, …, H and the terminal convention V^μ_{H+1} ≡ 0 → 0-based layers t ∈ Finset.range H, terminal V M μ H = 0; reason: index shift only (layer t is the paper's step t + 1)
- encoding: Markov policy π = (π_t)_{t≤H} with π_t(· | s) ∈ Δ(A) → π : ℕ → S → A → ℝ with IsPolicy H π (a distribution at every layer < H and every state); reason: values at layers ≥ H are never used; same instances
- encoding: kernels P_t(· | s, a) ∈ Δ(S) for t ≤ H → EpisodicMDP field P h, a distribution for every h ∈ ℕ (P_sum_one); reason: kernels beyond the horizon are never used; every paper MDP extends (repeat P_H)
- encoding: bounded costs ℓ_t : S × A → ℝ → EpisodicMDP field R t, an arbitrary real function (documented on the platform as a mean reward); reason: S and A are finite, so every real function is bounded; R is used as the cost with no sign change
- encoding: J(π) = E^π[Σ_t ℓ_t(s_t, a_t)] → totalCost M π = Σ_t Σ_s d^π_t(s) Σ_a π_t(a | s) ℓ_t(s, a); reason: linearity of expectation over the law P_t(s,a) = d^π_t(s) π_t(a | s) of (s_t, a_t); same value
- reading: "each summand is unchanged" (the sentence does not say whether the summands of (3) or of (4) are meant) → the invariance is stated for the summands of both (3) and (4), at every step; reason: the stronger of the two readings; the proof on p.3 shows both
import Mathlib import Definitions.Def_FoundationsRL_RLBasics_Core import Definitions.Def_AuditAdapt_stateLaw import Definitions.Def_AuditAdapt_totalCost import Definitions.Def_AuditAdapt_openLoopMarginal import Definitions.Def_AuditAdapt_trCov import Definitions.Def_AuditAdapt_jointMinusProduct
namespace AuditAdapt
open FoundationsRL.RLBasics
/-- **Theorem 3.4 (Covariance characterization), p.3** (Aldridge, *Regret-based Characterization, Information Limits, and the Sample Complexity of Auditing
Adaptive Policies*, STOC 2027 submission (held version, sha256 3f6ad545…)). For every finite-horizon
MDP and every Markov policy `π`, with `ν = ν^π`,
`J(π) − J(ν) = ∑_{t=1}^H tr Cov(q_t, z_t)` (3)
`= ∑_{t=1}^H (E_{(s,a)∼P_t}[Q^ν_t(s,a)] − E_{(s,a)∼P^S_t⊗P^A_t}[Q^ν_t(s,a)])` (4).
Moreover, each summand is unchanged if `Q^ν_t(s,a)` is replaced by `Q^ν_t(s,a) − g_t(s)` for any
`g_t : S → ℝ`.
**Formalization Note** 0-based layers: `t ∈ Finset.range H` is the paper's `t = 1, …, H`; the
published `V M μ H = 0` is `V^μ_{H+1} ≡ 0`. `q_t = Q^ν_t(s_t, ·)`, `z_t = π_t(· | s_t)`, `s_t ∼ d^π_t`,
where `d^π_t` is the `ρ`-mixture `stateLaw` of the published `stateDist`. The cost `ℓ_t` is the
field `M.R t` (documented as a mean reward on the platform; the identity is linear, so no sign
change). `J` is `∑_t E_{d^π_t}⟨ℓ_t, π_t⟩` (`totalCost`), and `tr Cov` is the form
`E⟨q,z⟩ − ⟨Eq,Ez⟩` (`trCov`). "Each summand" is stated for the summands of both (3) and (4). -/
theorem theorem_3_4 {S A : Type*} [Fintype S] [Fintype A] [DecidableEq S] {H : ℕ}
(M : EpisodicMDP S A H) (π : Policy S A H) (hπ : IsPolicy H π) :
(totalCost M π - totalCost M (openLoopMarginal M π) =
∑ t ∈ Finset.range H, trCov M π t (Q M (openLoopMarginal M π) t)) ∧
(totalCost M π - totalCost M (openLoopMarginal M π) =
∑ t ∈ Finset.range H, jointMinusProduct M π t (Q M (openLoopMarginal M π) t)) ∧
(∀ g : ℕ → S → ℝ, ∀ t, t < H →
trCov M π t (fun s a => Q M (openLoopMarginal M π) t s a - g t s) =
trCov M π t (Q M (openLoopMarginal M π) t) ∧
jointMinusProduct M π t (fun s a => Q M (openLoopMarginal M π) t s a - g t s) =
jointMinusProduct M π t (Q M (openLoopMarginal M π) t)) := by sorry
end AuditAdapt
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.