§2, p.3 — the state law is a probability distribution on
ProvedAuditAdapt.stateLaw_mem_simplexadaptivitymarkov-decision-processesp2o-gran-per-chapterp2o-plan-paperp2o-v1reinforcement-learning
Let be a finite-horizon MDP with initial law and kernels , and let be a Markov policy. For every state generated by running (that is, ), its law is a probability distribution on :
This is the paper's "". It makes the expectations of the covariance characterization genuine averages, and it gives that is a distribution on actions.
Formalization Note 0-based layers: the hypothesis in Lean covers the paper's .
Differences from the source:
- encoding: d^π_t for every state s_t the run generates (s_1, …, s_{H+1}) → stateLaw M π t for 0-based t ≤ H; reason: index shift only; beyond s_{H+1} the run generates no states
- 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)
Preamble
import Mathlib import Definitions.Def_FoundationsRL_RLBasics_Core import Definitions.Def_AuditAdapt_stateLaw
Formal statement
namespace AuditAdapt
open FoundationsRL.RLBasics
/-- **§2, p.3: `d^π_t ∈ Δ(S)`** (Aldridge, *Regret-based Characterization, Information Limits, and the Sample Complexity of Auditing
Adaptive Policies*, STOC 2027 submission (held version, sha256 3f6ad545…)). For a Markov policy `π`, the law of every
state `s_t` the run generates is a probability distribution on `S`.
**Formalization Note** 0-based layers: `t ≤ H` covers the paper's `s_1, …, s_{H+1}` (all states
the run generates; `s_{H+1} ∼ P_H(· | s_H, a_H)`). For `t > H` the published `Policy` is
unconstrained, so no claim is made there. -/
theorem stateLaw_mem_simplex {S A : Type*} [Fintype S] [Fintype A] [DecidableEq S] {H : ℕ}
(M : EpisodicMDP S A H) (π : Policy S A H) (hπ : IsPolicy H π) (t : ℕ) (ht : t ≤ H) :
(∀ s : S, 0 ≤ stateLaw M π t s) ∧ ∑ s : S, stateLaw M π t s = 1 := by sorry
end AuditAdapt
Source
Aldridge, Regret-based Characterization, Information Limits, and the Sample Complexity of Auditing Adaptive Policies, STOC 2027 submission (held version, sha256 3f6ad545b0454d8de6836d32bb81359da5022bbc373510a7c75452ab66ec9fc2), §2 "MDPs and policies", p.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.