A two-state lower bound for constant-step natural policy gradient in finite-horizon Markov decision processes

The amplified product family A(H, Delta) and the exact optimality gap. For every horizon H >= 2, every constant step size eta >= 0 and every T >= 1 there is a finite-horizon MDP with |S| = 2, |A| = 2 and rewards in [0,1] – H-1 independent two-armed bandits with action-value gap exactly 1 behind one delay-amplifier layer whose flat alternative is worse by Delta_T = (H-1) S_T(eta)/T, S_T(eta) = sum_(t<T) 1/(1+e^(eta t)) – on which the T-th iterate of constant-step-eta NPG from the uniform initialization satisfies EXACTLY V*¹(s0) - V^(pi_T,1)(s0) = ((H-1)/(1+e^(eta T)) + Delta_T)/2, hence >= (H-1) S_T(eta)/(2T)

The eta-free term of the source's Theorem 1 cannot be deleted: for every H >= 2, every eta >= 0 and every T >= 1 the family A(H, Delta_T) has V*¹(s0) - V^(pi_T,1)(s0) >= (H-1)/(4T), a bound that does not decay as the step size grows – so no upper bound of the form (H-h+1)log|A|/(eta T) alone can hold, and the shape of Theorem 1 (an eta-free term with a positive power of H) is correct

The first term of the source's Theorem 1 is tight up to a constant at |A| = 2: for every H >= 2, every eta > 0 and every T >= 1 with eta*T >= 1 the same family has V*¹(s0) - V^(pi_T,1)(s0) >= (H-1)/(8 eta T), against Theorem 1's (H-h+1)log|A|/(eta T) + (H-h+1)²/T at h = 1. Proved from S_T(eta) >= 1/((1+e) eta) by counting the ceil(1/eta) terms with eta*t <= 1, and Real.expₒneₗt_d9 for the constant

A finite-horizon MDP model and exact NPG in Lean, from scratch over the reals: the tuple (S, A, H, P, R) with the kernel axioms; the layer-indexed value recursion with V^(pi,H+1) = 0 and the source's one-step identity V^(pi,h)(s) = sumₐ piʰ(a|s) Q^(pi,h)(s,a); backward induction with a maximum, with a proof that no policy beats it; and NPG in logit coordinates Lₜ₊₁ = Lₜ + eta Q^(piₜ) from L₀ = 0, certified to BE the source's algorithm by npgPol_zero (uniform initialization), npgPolₛucc (their Eq. (2) verbatim, in multiplicative form with the normalizer Zₜʰ(s)) and npgPolᵢsPolicy. Plus the reformulation npgLogitₑq_cumulative: Lₜ = eta * sum_(k<t) Q^(piₖ), i.e. each (h,s) runs exponential weights on the CUMULATIVE action-value vector

Constant-step NPG is not iterated policy iteration at any step size: on A(H, Delta_T) exact policy iteration from the uniform policy is already optimal at step 2 (and hence at every T >= 2), while the T-th NPG iterate is strictly suboptimal for every eta >= 0, however large, its gap being at least (H-1)/(4T). This is the sense in which the source's remark 'As eta -> infinity, the NPG update approaches the greedy policy-improvement step of exact policy iteration with respect to Q^(piₜ,h)' – true of one update from a fixed piₜ – does not extend to the iterate sequence: by npgLogitₑq_cumulative the large-eta iterate follows the leader on sum_(k<t) Q^(piₖ), not on Q^(piₜ₋₁)

Numerical reproduction and the exact cumulative-gap reduction identities. (a) The compute-first-values gate: a from-scratch simulator implementing the source's Eq. (2) multiplicatively in 200-digit Decimal reproduces the strategy journal's 80 float64 cells (gap/bound in [1.0000000, 1.0054816], matching its reported [1.00000, 1.00548]) and 330 further cells for rows N2 and N3, with the source's own Theorem 1 upper bound checked as a control on 125 family cells and 270 random MDPs (H <= 5, |S| <= 3, |A| in 2,3) with zero violations. (b) The four exact reduction identities of the strategy journal – gapₜʰ(s) = E_(P(.|s,a*))[gapₜʰ⁺¹] + A^(piₜ,h)(s,a*), C_T = sumᵢ sumₛ d^(h->i,pi*)(s) R_Tⁱ(s), A^(piₜ)(a*) = piₜ(b) deltaₜ and piₜ(b) = 1/(1+e^(eta Dₜ)) – re-verified in 60-digit arithmetic on 648 random MDPs to a maximum residual of 1.4e-57, against the strategy journal's 4.9e-14 in float64