Proof of Theorem 3, p.11: is monotone and
ProvedAggStatePG.bellmanOpt_mono_shiftmarkov-decision-processp2o-gran-per-chapterp2o-plan-paperp2o-v1policy-gradientreinforcement-learningstate-aggregation
Throughout, is a finite Markov decision process: finite state and action sets, a real reward (no bound), transition probabilities , a discount factor and an initial distribution on . is the set of stationary randomized policies , the value function of , , , and the discounted state occupancy measure.
- If element-wise, then ;
- for every real , , where is the vector of ones.
These are the two properties of the Bellman optimality operator cited from Bertsekas (1995) to iterate .
Differences from the source:
- encoding: finite action space A = {1, …, |A|} → a finite nonempty action type ([Nonempty A]); reason: Δ(A) and Π are empty for an empty action set; the paper's MDP has policies (an optimal one exists, p.4)
- encoding: TV(s) = max_{d∈Δ(A)} [r(s,d) + γ Σ_{s′} P(s′|s,d)V(s′)] → bellmanOpt = sSup of the image of Δ(A); reason: for nonempty finite A the image is a nonempty compact set, so sSup is the maximum
Preamble
import Mathlib import Definitions.Def_FoundationsML_ReinforcementLearning_IsTransitionKernel import Definitions.Def_AggStatePG_bellmanOpt open FoundationsML.ReinforcementLearning
Formal statement
namespace AggStatePG
/-- **Monotonicity and constant shift of `T`** (Russo, *Approximation Benefits of Policy Gradient Methods with Aggregated States*, arXiv:2007.11684v3, proof of Theorem 3, p.11): "Using the
monotonicity of Bellman operators and the fact that `T(V + ce) = TV + γce` [Bertsekas, 1995]".
1. If `V ⪯ W` element-wise then `TV ⪯ TW`;
2. for every real `c`, `T(V + ce) = TV + γce`, `e` the vector of ones.
**Formalization Note.** `T = bellmanOpt`. The action type is nonempty. -/
theorem bellmanOpt_mono_shift {S A : Type*} [Fintype S] [Fintype A] [Nonempty A]
(P : S → A → S → ℝ) (hP : IsTransitionKernel P) (r : S → A → ℝ)
(γ : ℝ) (hγ0 : 0 < γ) (hγ1 : γ < 1) :
(∀ V W : S → ℝ, (∀ s, V s ≤ W s) → ∀ s, bellmanOpt P r γ V s ≤ bellmanOpt P r γ W s) ∧
(∀ (V : S → ℝ) (c : ℝ) (s : S),
bellmanOpt P r γ (fun s' => V s' + c) s = bellmanOpt P r γ V s + γ * c) := by sorry
end AggStatePG
Source
Russo, Approximation Benefits of Policy Gradient Methods with Aggregated States, arXiv:2007.11684v3, proof of Theorem 3, p.11
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.