import Determinize.Proof.RewardModel.Executionimport Determinize.Proof.RewardModel.Safetyimport Determinize.Proof.RewardModel.Replayimport Determinize.Proof.FiniteModel.Initialnamespace Determinize.Proof.RewardModelopen Determinize.Finite Determinize.Proof.FiniteModel MeasureTheory Spec.RewardModelprivate theorem row_next (c : Reward.Candidate) {source : Spec.Paper.Core} {subject : Spec.FiniteModel.Subject} (valid : c.ReplayValid source subject) (i : Fin c.states.size) (tag : Evidence) (xs : List (Rat × State)) (action : step c.states[i] = .ok (.next tag xs)) : (c.row i).kind = .transient ∧ ((c.row i).edges.map fun e ↦ (e.probability, c.states[e.target]?.getD .rejected, e.reward)) = ((xs.filter fun x ↦ 0 < x.1).map fun x ↦ (x.1, (Reward.normalize x.2).2, (Reward.normalize x.2).1)) := by have h := (valid.2.2.2.2.2 i).2.2 simp only [Reward.step, action, bind, Except.bind, pure, Except.pure] at h refine ⟨h.1, ?_⟩ simpa [List.filter_map, List.map_map, Function.comp_def] using h.2.2private theorem row_no_failure (c : Reward.Candidate) {source : Spec.Paper.Core} {subject : Spec.FiniteModel.Subject} (valid : c.ReplayValid source subject) (i : Fin c.states.size) (e : Failure) : step c.states[i] ≠ .error e := by intro action have h := (valid.2.2.2.2.2 i).2.2 simp only [Reward.step, action, bind, Except.bind] at hprivate theorem row_covered (c : Reward.Candidate) {source : Spec.Paper.Core} {subject : Spec.FiniteModel.Subject} (valid : c.ReplayValid source subject) (i : Fin c.states.size) (tag : Evidence) (xs : List (Rat × State)) (action : step c.states[i] = .ok (.next tag xs)) (x : Rat × State) (member : x ∈ xs) (positive : 0 < x.1) : ∃ j : Fin c.states.size, c.states[j] = (Reward.normalize x.2).2 := by have encoded := (row_next c valid i tag xs action).2 have hm : (x.1, (Reward.normalize x.2).2, (Reward.normalize x.2).1) ∈ (c.row i).edges.map (fun e ↦ (e.probability, c.states[e.target]?.getD .rejected, e.reward)) := by rw [encoded] exact List.mem_map.mpr ⟨x, by simp [member, positive], rfl⟩ obtain ⟨edge, he, eq⟩ := List.mem_map.mp hm have bound := ((valid.2.2.2.2.2 i).1 edge he).1 refine ⟨⟨edge.target, bound⟩, ?_⟩ have same := congrArg (fun t : Rat × State × Rat ↦ t.2.1) eq simpa [bound] using sameprivate theorem replay_no_rewardFailure (c : Reward.Candidate) {source : Spec.Paper.Core} {subject : Spec.FiniteModel.Subject} (valid : c.ReplayValid source subject) (n : Nat) (i : Fin c.states.size) : ¬ RewardFailureWithin n c.states[i] := by induction n generalizing i with | zero => exact fun ⟨e, h⟩ ↦ row_no_failure c valid i e h | succ n ih => cases action : step c.states[i] with | error e => exact (row_no_failure c valid i e action).elim | ok result => cases result with | returned b => simp only [RewardFailureWithin, action, not_false_eq_true] | rejected => simp only [RewardFailureWithin, action, not_false_eq_true] | next tag xs => simp only [RewardFailureWithin, action] rintro ⟨x, member, positive, failed⟩ obtain ⟨j, same⟩ := row_covered c valid i tag xs action x member positive exact ih j (same ▸ failed)private theorem reachable_failure {root state : State} (reachable : MachineReachable root state) (n : Nat) (failed : FailureWithin n state) : ∃ k, FailureWithin k root := by induction reachable generalizing n with | initial => exact ⟨n, failed⟩ | next prev action member positive ih => exact ih (n + 1) (by simp only [FailureWithin, action]; exact ⟨_, member, positive, failed⟩)theorem replay_reachable_no_failure (c : Reward.Candidate) {source : Spec.Paper.Core} {subject : Spec.FiniteModel.Subject} (valid : c.ReplayValid source subject) {state : State} (reachable : MachineReachable (initialState source subject) state) (e : Failure) : step state ≠ .error e := by intro failed obtain ⟨n, hn⟩ := reachable_failure reachable 0 ⟨e, failed⟩ have initial : c.states[c.initial]'valid.2.1 = initialState source subject := by simpa [valid.2.1] using valid.2.2.1 apply replay_no_rewardFailure c valid n ⟨c.initial, valid.2.1⟩ change RewardFailureWithin n (c.states[c.initial]'valid.2.1) rw [initial] exact rewardFailureWithin_of_failureWithin n _ hnprivate theorem weightedOutput_filter_pos (xs : List (Rat × State)) (f : State → Measure ℝ) : weightedOutput (xs.filter fun x ↦ 0 < x.1) f = weightedOutput xs f := by induction xs with | nil => rfl | cons x xs ih => by_cases positive : 0 < x.1 · simpa [weightedOutput, positive] using congrArg (fun μ ↦ ENNReal.ofReal (x.1 : ℝ) • f x.2 + μ) ih · have zero : ENNReal.ofReal (x.1 : ℝ) = 0 := ENNReal.ofReal_eq_zero.mpr (by exact_mod_cast le_of_not_gt positive) simpa [List.filter_cons, positive, weightedOutput, zero] using ihprivate theorem replay_row_sum (c : Reward.Candidate) {source : Spec.Paper.Core} {subject : Spec.FiniteModel.Subject} (valid : c.ReplayValid source subject) (i : Fin c.states.size) (tag : Evidence) (xs : List (Rat × State)) (action : step c.states[i] = .ok (.next tag xs)) (f : State → Measure ℝ) : (((c.toModel valid).edges i).map fun e ↦ ENNReal.ofReal (e.probability : ℝ) • shift e.reward (f c.states[e.target])).sum = weightedOutput xs (fun s ↦ shift (Reward.normalize s).1 (f (Reward.normalize s).2)) := by have encoded := (row_next c valid i tag xs action).2 have mapped := congrArg (fun ys : List (Rat × State × Rat) ↦ (ys.map fun x ↦ ENNReal.ofReal (x.1 : ℝ) • shift x.2.2 (f x.2.1)).sum) encoded simp only [List.map_map, Function.comp_def] at mapped have left : (((c.toModel valid).edges i).map fun e ↦ ENNReal.ofReal (e.probability : ℝ) • shift e.reward (f c.states[e.target])).sum = ((c.row i).edges.map fun e ↦ ENNReal.ofReal (e.probability : ℝ) • shift e.reward (f (c.states[e.target]?.getD .rejected))).sum := by change ((c.modelEdges valid i).map _).sum = _ unfold Reward.Candidate.modelEdges simp only [List.map_map, Function.comp_def] congr 1 conv_rhs => rw [← List.attach_map_val (l := (c.row i).edges)] apply List.map_congr_left intro e _ simp [((valid.2.2.2.2.2 i).1 e.val e.property).1] rw [left, mapped] simpa only [weightedOutput] using weightedOutput_filter_pos xs (fun s ↦ shift (Reward.normalize s).1 (f (Reward.normalize s).2))theorem replay_outputWithin (c : Reward.Candidate) {source : Spec.Paper.Core} {subject : Spec.FiniteModel.Subject} (valid : c.ReplayValid source subject) (n : Nat) (i : Fin c.states.size) : (c.toModel valid).outputWithin n i = rewardOutput n c.states[i] := by induction n generalizing i with | zero => have row := (valid.2.2.2.2.2 i).2.2 cases action : step c.states[i] with | error e => exact (row_no_failure c valid i e action).elim | ok result => cases result <;> simp only [Reward.step, action, bind, Except.bind, pure, Except.pure] at row all_goals simp only [rewardOutput, action] all_goals simp [Model.outputWithin, row] | succ n ih => have row := (valid.2.2.2.2.2 i).2.2 cases action : step c.states[i] with | error e => exact (row_no_failure c valid i e action).elim | ok result => cases result with | returned b => simp only [Reward.step, action, bind, Except.bind, pure, Except.pure] at row simp only [rewardOutput, action] simp [Model.outputWithin, row] | rejected => simp only [Reward.step, action, bind, Except.bind, pure, Except.pure] at row simp only [rewardOutput, action] simp [Model.outputWithin, row] | next tag xs => have kind := (row_next c valid i tag xs action).1 simp only [Model.outputWithin, rewardOutput, action] change (match (c.row i).kind with | .returned b => Measure.dirac (b : ℝ) | .rejected => 0 | .transient => _) = _ rw [kind] simp_rw [ih] exact replay_row_sum c valid i tag xs action (rewardOutput n)theorem replay_matches (c : Reward.Candidate) {source : Spec.Paper.Core} {subject : Spec.FiniteModel.Subject} (valid : c.ReplayValid source subject) : (c.toModel valid).Matches (subject.program source) := by have meaning : ∀ state, MachineReachable (initialState source subject) state → ∀ result, step state = .ok result → StepMeaning state result := fun state reachable result action ↦ stepMeaning state (stateShape_of_reachable_initialState source subject state reachable) result action have noFailure := fun state reachable failure ↦ replay_reachable_no_failure c valid (state := state) reachable failure have initial : c.states[c.initial]'valid.2.1 = initialState source subject := by simpa [valid.2.1] using valid.2.2.1 have initialEqual : stateExpr (initialState source subject) = subject.program source := initial_reification source subject ((Binding.scoped_map source (fun q : Rat ↦ (q : ℝ)) 0).mpr valid.2.2.2.1) constructor · intro fuel rw [← initialEqual] exact execution_safe _ meaning noFailure fuel _ .initial · change (⨆ n, (c.toModel valid).outputWithin n _) = _ simp_rw [replay_outputWithin] change (⨆ n, rewardOutput n (c.states[c.initial]'valid.2.1)) = _ rw [initial, iSup_rewardOutput_eq_machineOutputMeasure, execution_output_eq _ meaning noFailure _ .initial, initialEqual]end Determinize.Proof.RewardModel