import Determinize.Proof.RewardModel.Stackimport Determinize.Proof.RewardModel.Normalizationnamespace Determinize.Proof.RewardModelopen Determinize.Finite Determinize.Proof.FiniteModel MeasureTheory Spec.RewardModeldef additionStack (offsets : List Rat) : List Frame := offsets.map fun c ↦ .right .add (.number c)theorem numeric_addition_output (offsets : List Rat) (b : Rat) (n : Nat) : machineOutput (n + offsets.length) (.deliver (.number b) (additionStack offsets)) = Measure.dirac ((b + offsets.sum : Rat) : ℝ) := by induction offsets generalizing b with | nil => cases n <;> simp [additionStack, machineOutput, step] | cons c cs ih => rw [List.length_cons, Nat.add_succ] simp only [additionStack, List.map_cons, machineOutput, step, binary, pure, bind, Except.bind, Except.pure] simp only [weightedOutput, List.map_cons, List.map_nil, List.sum_cons, List.sum_nil, Rat.cast_one, ENNReal.ofReal_one, one_smul, add_zero] rw [← additionStack, ih] congr 1 simp only [Rat.cast_add] ringprivate theorem draw_not_terminal (site : Spec.Paper.DistributionAction × Spec.Paper.Op) (args : List Rat) (stack : List Frame) (result : Finite.Step) (action : draw site args stack = .ok result) : ∃ tag outcomes, result = .next tag outcomes := by unfold draw at action cases law : finiteLaw site.2 site.1 args with | error e => simp [law, bind, Except.bind] at action | ok xs => simp only [law, bind, Except.bind, pure, Except.pure, Except.ok.injEq] at action exact ⟨_, _, action.symm⟩theorem step_terminal (state : State) (result : Finite.Step) (action : step state = .ok result) : (∃ tag outcomes, result = .next tag outcomes) ∨ (∃ b, state = .deliver (.number b) [] ∧ result = .returned b) ∨ (state = .rejected ∧ result = .rejected) := by cases state with | rejected => simp only [step, Except.ok.injEq] at action; exact Or.inr (Or.inr ⟨rfl, action.symm⟩) | eval expression env stack => apply Or.inl cases expression <;> simp only [step, pure, bind, Except.bind, Except.pure] at action all_goals repeat' (split at action) all_goals first | contradiction | exact ⟨_, _, (Except.ok.inj action).symm⟩ | deliver value stack => cases stack with | nil => cases value <;> simp only [step, Except.ok.injEq] at action all_goals first | contradiction | exact Or.inr (Or.inl ⟨_, rfl, action.symm⟩) | cons frame stack => apply Or.inl cases frame with | discrete kind => cases pv : value.probabilities? with | none => simp only [step, pv] at action; contradiction | some ps => simp only [step, pv] at action exact draw_not_terminal _ _ _ _ action | draw site pending env args => cases value <;> simp only [step, pure, bind, Except.bind, Except.pure] at action all_goals try contradiction rename_i x cases pending with | nil => exact draw_not_terminal _ _ _ _ action | cons next rest => exact ⟨_, _, (Except.ok.inj action).symm⟩ | unary op => cases op <;> cases value <;> simp only [step, unary, pure, bind, Except.bind, Except.pure] at action all_goals first | contradiction | exact ⟨_, _, (Except.ok.inj action).symm⟩ | right op left => cases op <;> cases left <;> cases value <;> simp only [step, binary, pure, bind, Except.bind, Except.pure] at action all_goals repeat' (split at action) all_goals first | contradiction | exact ⟨_, _, (Except.ok.inj action).symm⟩ | left op rhs env => exact ⟨_, _, (Except.ok.inj action).symm⟩ | letBody body env => exact ⟨_, _, (Except.ok.inj action).symm⟩ | choose yes no env => cases value <;> simp only [step, pure, bind, Except.bind, Except.pure] at action all_goals first | contradiction | exact ⟨_, _, (Except.ok.inj action).symm⟩ | matchSum left right env => cases value <;> simp only [step, pure, bind, Except.bind, Except.pure] at action all_goals first | contradiction | exact ⟨_, _, (Except.ok.inj action).symm⟩ | matchList nilCase consCase env => cases value <;> simp only [step, pure, bind, Except.bind, Except.pure] at action all_goals first | contradiction | exact ⟨_, _, (Except.ok.inj action).symm⟩private theorem shift_weightedOutput (r : Rat) (xs : List (Rat × State)) (f : State → Measure ℝ) : shift r (weightedOutput xs f) = weightedOutput xs (fun s ↦ shift r (f s)) := by induction xs with | nil => simp [weightedOutput] | cons x xs ih => simp only [weightedOutput, List.map_cons, List.sum_cons] at ih ⊢ rw [shift_add_measure, shift_smul, ih]private theorem weightedOutput_extend (outer : List Frame) (xs : List (Rat × State)) (f : State → Measure ℝ) : weightedOutput (extend outer xs) f = weightedOutput xs (fun s ↦ f (pushStack s outer)) := by simp [weightedOutput, extend, List.map_map, Function.comp_def]theorem addition_output_lower (offsets : List Rat) (n : Nat) (state : State) : shift offsets.sum (machineOutput n state) ≤ machineOutput (n + offsets.length) (pushStack state (additionStack offsets)) := by induction n generalizing state with | zero => cases action : step state with | error e => simp [machineOutput, action, Measure.zero_le] | ok result => rcases step_terminal state result action with ⟨tag, xs, rfl⟩ | ⟨b, rfl, rfl⟩ | ⟨rfl, rfl⟩ · simp [machineOutput, action, Measure.zero_le] · simpa [machineOutput, step, pushStack, shift_dirac, add_comm] using (numeric_addition_output offsets b 0).ge · simp [machineOutput, step, Measure.zero_le] | succ n ih => cases action : step state with | error e => simp [machineOutput, action, Measure.zero_le] | ok result => rcases step_terminal state result action with ⟨tag, xs, rfl⟩ | ⟨b, rfl, rfl⟩ | ⟨rfl, rfl⟩ · have lifted := step_pushStack state (additionStack offsets) tag xs action rw [Nat.succ_add] simp only [machineOutput, action, lifted] rw [shift_weightedOutput, weightedOutput_extend] exact weightedOutput_mono _ _ _ (fun e _ _ ↦ ih e.2) · simpa [machineOutput, step, pushStack, shift_dirac, add_comm] using (numeric_addition_output offsets b (n + 1)).ge · simp [machineOutput, step, Measure.zero_le]private theorem draw_error_push (site : Spec.Paper.DistributionAction × Spec.Paper.Op) (args : List Rat) (inner outer : List Frame) (failure : Failure) (action : draw site args inner = .error failure) : draw site args (inner ++ outer) = .error failure := by unfold draw at action ⊢ cases law : finiteLaw site.2 site.1 args <;> simp only [bind, Except.bind, law, Except.error.injEq, pure, Except.pure, reduceCtorEq] at action ⊢ exact actiontheorem addition_failure (state : State) (offsets : List Rat) (failure : Failure) (action : step state = .error failure) : ∃ error, step (pushStack state (additionStack offsets)) = .error error := by cases state with | rejected => simp [step] at action | eval expression env stack => refine ⟨failure, ?_⟩ cases expression <;> simp only [step, pushStack, pure, bind, Except.bind, Except.pure] at action ⊢ all_goals repeat' (split at action) all_goals simp_all | deliver value stack => cases stack with | nil => cases value <;> simp only [step] at action all_goals try contradiction all_goals cases offsets with | nil => exact ⟨_, action⟩ | cons c cs => exact ⟨_, rfl⟩ | cons frame stack => refine ⟨failure, ?_⟩ cases frame with | discrete kind => cases pv : value.probabilities? with | none => simp only [step, pv] at action simpa only [step, pushStack, List.cons_append, pv] using action | some ps => simp only [step, pv] at action simpa [pushStack, step, pv, bind, Except.bind, Except.pure] using draw_error_push (kind, .discrete ps.length) ps stack (additionStack offsets) failure action | draw site pending env args => cases value <;> simp only [step, pure, bind, Except.bind, Except.pure] at action all_goals try (simpa [pushStack, step, pure, bind, Except.bind, Except.pure] using action) rename_i x cases pending with | nil => simpa [pushStack, step, bind, Except.bind, Except.pure] using draw_error_push site (args ++ [x]) stack (additionStack offsets) failure action | cons next rest => contradiction | unary op => cases op <;> cases value <;> simp_all [pushStack, step, unary, pure, bind, Except.bind, Except.pure] | right op left => cases op <;> cases left <;> cases value <;> simp only [step, binary, pure, bind, Except.bind, Except.pure] at action all_goals try split_ifs at action all_goals repeat' (split at action) all_goals simp_all [step, binary, pushStack, bind, Except.bind] | left op rhs env => contradiction | letBody body env => contradiction | choose yes no env => cases value <;> simp_all [pushStack, step, pure, bind, Except.bind, Except.pure] | matchSum left right env => cases value <;> simp_all [pushStack, step, pure, bind, Except.bind, Except.pure] | matchList nilCase consCase env => cases value <;> simp_all [pushStack, step, pure, bind, Except.bind, Except.pure]theorem numeric_addition_upper (offsets : List Rat) (b : Rat) (n : Nat) : machineOutput n (.deliver (.number b) (additionStack offsets)) ≤ Measure.dirac ((b + offsets.sum : Rat) : ℝ) := by induction offsets generalizing b n with | nil => cases n <;> simp [additionStack, machineOutput, step] | cons c cs ih => cases n with | zero => simp [additionStack, machineOutput, step, binary, pure, bind, Except.bind, Except.pure, Measure.zero_le] | succ n => simp only [additionStack, List.map_cons, machineOutput, step, binary, pure, bind, Except.bind, Except.pure] simp only [weightedOutput, List.map_cons, List.map_nil, List.sum_cons, List.sum_nil, Rat.cast_one, ENNReal.ofReal_one, one_smul, add_zero] convert ih (c + b) n using 1 <;> congr 1 simp only [Rat.cast_add] ringtheorem addition_output_upper (offsets : List Rat) (n : Nat) (state : State) : machineOutput n (pushStack state (additionStack offsets)) ≤ shift offsets.sum (machineOutput n state) := by induction n generalizing state with | zero => cases action : step state with | error e => obtain ⟨err, herr⟩ := addition_failure state offsets e action simp [machineOutput, action, herr] | ok result => rcases step_terminal state result action with ⟨tag, xs, rfl⟩ | ⟨b, rfl, rfl⟩ | ⟨rfl, rfl⟩ · simp [machineOutput, action, step_pushStack state (additionStack offsets) tag xs action] · simpa [pushStack, machineOutput, step, shift_dirac] using numeric_addition_upper offsets b 0 · simp [pushStack, machineOutput, step] | succ n ih => cases action : step state with | error e => obtain ⟨err, herr⟩ := addition_failure state offsets e action simp [machineOutput, action, herr] | ok result => rcases step_terminal state result action with ⟨tag, xs, rfl⟩ | ⟨b, rfl, rfl⟩ | ⟨rfl, rfl⟩ · simp only [machineOutput, action, step_pushStack state (additionStack offsets) tag xs action] rw [shift_weightedOutput, weightedOutput_extend] exact weightedOutput_mono _ _ _ (fun e _ _ ↦ ih e.2) · simpa [pushStack, machineOutput, step, shift_dirac] using numeric_addition_upper offsets b (n + 1) · simp [pushStack, machineOutput, step]theorem numeric_addition_exact (offsets : List Rat) (b : Rat) (n : Nat) : machineOutput n (.deliver (.number b) (additionStack offsets)) = if offsets.length ≤ n then Measure.dirac ((b + offsets.sum : Rat) : ℝ) else 0 := by induction offsets generalizing b n with | nil => cases n <;> simp [additionStack, machineOutput, step] | cons c cs ih => cases n with | zero => simp [additionStack, machineOutput, step, binary, pure, bind, Except.bind, Except.pure] | succ n => simp only [additionStack, List.map_cons, machineOutput, step, binary, pure, bind, Except.bind, Except.pure] simp only [weightedOutput, List.map_cons, List.map_nil, List.sum_cons, List.sum_nil, Rat.cast_one, ENNReal.ofReal_one, one_smul, add_zero] rw [← additionStack, ih] simp only [List.length_cons, Nat.add_le_add_iff_right] split_ifs <;> try rfl congr 1 simp only [Rat.cast_add] ringtheorem addition_guard_upper (offsets : List Rat) (nonempty : offsets ≠ []) (n : Nat) (state : State) : machineOutput n (pushStack state (additionStack offsets)) ≤ shift offsets.sum (machineOutput n (pushStack state (additionStack [0]))) := by have numeric (b : Rat) (n : Nat) : machineOutput n (pushStack (.deliver (.number b) []) (additionStack offsets)) ≤ shift offsets.sum (machineOutput n (pushStack (.deliver (.number b) []) (additionStack [0]))) := by simp only [pushStack, List.nil_append, numeric_addition_exact] by_cases enough : offsets.length ≤ n · have one : 1 ≤ n := by have := List.length_pos_iff.mpr nonempty omega simp only [ite_eq_left enough, List.length_singleton, ite_eq_left one, List.sum_cons, List.sum_nil, add_zero, shift_dirac] rfl · simp [enough, Measure.zero_le] induction n generalizing state with | zero => cases action : step state with | error e => obtain ⟨err, herr⟩ := addition_failure state offsets e action simp [machineOutput, herr, Measure.zero_le] | ok result => rcases step_terminal state result action with ⟨tag, xs, rfl⟩ | ⟨b, rfl, rfl⟩ | ⟨rfl, rfl⟩ · simp [machineOutput, step_pushStack state (additionStack offsets) tag xs action, Measure.zero_le] · exact numeric b 0 · simp [pushStack, machineOutput, step] | succ n ih => cases action : step state with | error e => obtain ⟨err, herr⟩ := addition_failure state offsets e action simp [machineOutput, herr, Measure.zero_le] | ok result => rcases step_terminal state result action with ⟨tag, xs, rfl⟩ | ⟨b, rfl, rfl⟩ | ⟨rfl, rfl⟩ · simp only [machineOutput, step_pushStack state (additionStack offsets) tag xs action, step_pushStack state (additionStack [0]) tag xs action] rw [shift_weightedOutput, weightedOutput_extend, weightedOutput_extend] exact weightedOutput_mono _ _ _ (fun e _ _ ↦ ih e.2) · exact numeric b (n + 1) · simp [pushStack, machineOutput, step]end Determinize.Proof.RewardModel