import Determinize.Proof.RewardModel.Controlimport Determinize.Finite.Statisticsimport Determinize.Proof.RewardModel.Boundaryimport Determinize.Proof.RewardModel.Certificatesnamespace Determinize.Finite.Rewardopen Proof.FiniteModeldef Equations (model : Spec.FiniteModel.Model) (rhs values : Fin model.size → Rat) : Prop := ∀ i, values i = rhs i + if model.kind i = .transient then ∑ j, model.transition i j * values j else 0instance (model : Spec.FiniteModel.Model) (rhs values : Fin model.size → Rat) : Decidable (Equations model rhs values) := inferInstanceAs (Decidable (∀ _, _))private def solveRhs (model : Spec.FiniteModel.Model) (rhs : Fin model.size → Rat) : Except String {values : Fin model.size → Rat // Equations model rhs values} := do let A := fun i j : Fin model.size ↦ let identity : Rat := if i = j then 1 else 0 if model.kind i = .transient then identity - model.transition i j else identity let some solution := Proof.LinearAlgebra.solve model.size A rhs | throw "singular additive reward equations" return ⟨solution.val, by intro i have h := solution.property i by_cases transient : model.kind i = .transient · simp only [transient, ↓reduceIte, sub_mul, ite_mul, one_mul, zero_mul, Finset.sum_sub_distrib, Finset.sum_ite_eq, Finset.mem_univ, A] at h simp only [transient, ↓reduceIte] exact (sub_eq_iff_eq_add.mp h) · simpa [A, transient] using h⟩def firstRhs (model : Spec.RewardModel.Model) (dead : Fin model.size → Bool) (mass : Fin model.size → Rat) (i : Fin model.size) : Rat := if dead i then 0 else match model.kind i with | .returned b => b | .rejected => 0 | .transient => ((model.edges i).map fun e ↦ e.probability * e.reward * mass e.target).sumdef secondRhs (model : Spec.RewardModel.Model) (dead : Fin model.size → Bool) (mass first : Fin model.size → Rat) (i : Fin model.size) : Rat := if dead i then 0 else match model.kind i with | .returned b => b * b | .rejected => 0 | .transient => ((model.edges i).map fun e ↦ e.probability * (2 * e.reward * first e.target + e.reward * e.reward * mass e.target)).sum/-- Checked linear equations; source correspondence and integral interpretation are separate. -/structure Solution (model : Spec.RewardModel.Model) where boundary : Boundary model.control paths : Paths (cut model.control boundary.dead) paths_valid : paths.Valid (cut model.control boundary.dead) mass : Fin model.size → Rat mass_valid : ValueEquations (rewards (cut model.control boundary.dead) Moment.mass.rational) mass first : Fin model.size → Rat first_valid : Equations (cut model.control boundary.dead) (firstRhs model boundary.dead mass) first second : Fin model.size → Rat second_valid : Equations (cut model.control boundary.dead) (secondRhs model boundary.dead mass first) second rejection : Fin model.size → Rat rejection_valid : ValueEquations (rejectionQuery model.control boundary.dead) rejectiontheorem Solution.moments_valid {model : Spec.RewardModel.Model} (solution : Solution model) : Proof.RewardModel.MomentEquations (Proof.RewardModel.cut model solution.boundary.dead) (fun moment ↦ match moment with | .mass => solution.mass | .first => solution.first | .second => solution.second) := by intro moment i have mass := solution.mass_valid i have first := solution.first_valid i have second := solution.second_valid i cases moment <;> cases dead : solution.boundary.dead i <;> cases kind : model.kind i <;> simp_all [Proof.RewardModel.cut, cut, rewards, Spec.RewardModel.Model.control, firstRhs, secondRhs, Proof.RewardModel.translatedValue, Moment.rational, mul_add, List.sum_map_add, ← Proof.RewardModel.sum_controlWeight_mul, pow_two, mul_assoc, add_comm, add_assoc]def solve (model : Spec.RewardModel.Model) (limits : SolveLimits := {}) : Except String (Solution model) := do if model.size > limits.maxStates then throw s!"exact solver state limit exceeded ({model.size} > {limits.maxStates})" let boundary ← analyze model.control let stopped := cut model.control boundary.dead let paths ← findPaths stopped boundary.rank let mass ← solveValues (rewards stopped Moment.mass.rational) limits let first ← solveRhs stopped (firstRhs model boundary.dead mass.val) let second ← solveRhs stopped (secondRhs model boundary.dead mass.val first.val) let rejection ← solveValues (rejectionQuery model.control boundary.dead) limits return ⟨boundary, paths.val, paths.property, mass.val, mass.property, first.val, first.property, second.val, second.property, rejection.val, rejection.property⟩def Solution.statistics {model : Spec.RewardModel.Model} (solution : Solution model) : Spec.FiniteModel.OutputStatistics := ⟨solution.mass model.initial, solution.first model.initial, solution.second model.initial⟩end Determinize.Finite.Reward