Proof of Theorem 1, p. 12 — D(π_0, π*) ≤ log|A| for the uniform initial policy π_0
ProvedAvgRewardPMD.SPMD.kl_uniform_le_logkl-divergencep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1policy-mirror-descent
Let be the uniform policy, any feasible policy and any distribution on states. Then
This bounds the initial distance in the telescoped Lemma 4, and with the choice of the stepsize it yields the constants of Theorem 1.
Formalization Note is built into kl; the second argument is positive whenever a policy exists.
Differences from the source:
- generalization: ν*, the stationary distribution of the optimal policy → any distribution ν on states; reason: ν* is an instance
- generalization: π*, an optimal policy → any feasible policy; reason: an optimal policy is an instance
Preamble
import Mathlib import Definitions.Def_AvgRewardPMD_SPMD_Setting
Formal statement
namespace AvgRewardPMD.SPMD
open FoundationsML.ReinforcementLearning
theorem kl_uniform_le_log {S A : Type*} [Fintype S] [Fintype A] [DecidableEq S] [DecidableEq A]
(ν : S → ℝ) (hν : ν ∈ stdSimplex ℝ S) (πstar : S → A → ℝ) (hπstar : IsPolicy πstar) :
stationaryKL ν (fun _ _ => 1 / (Fintype.card A : ℝ)) πstar ≤ Real.log (Fintype.card A) := by sorry
end AvgRewardPMD.SPMD
Source
Li, Wu, Lan, Stochastic first-order methods for average-reward Markov decision processes, arXiv:2205.05800v6, p. 12, proof of Theorem 1, 'the upper bound D(π0, π∗) ≤ log |A|'
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.