Source lean/Determinize/Spec/RewardModel/Model.lean
import Determinize.Spec.FiniteModel.Model/-!# Reward modelsFinite models whose transitions are lists of edges, each paying a reward that is added to theeventual output.-/namespace Determinize.Spec.RewardModelopen MeasureTheory/-- An outgoing edge of a state. -/structure Edge (size : Nat) where  /-- The state the edge leads to. -/  target : Fin size  /-- The probability of taking the edge. -/  probability : Rat  /-- The reward added to the output when the edge is taken. -/  reward : Rat/-- Edge rewards translate successful outputs. Rejection and divergence discard them. -/structure Model where  /-- The number of states. -/  size : Nat  /-- The state in which evaluation starts. -/  initial : Fin size  /-- Whether each state is transient, returns a value, or rejects. -/  kind : Fin size → FiniteModel.StateKind  /-- The outgoing edges of each state. -/  edges : Fin size → List (Edge size)  nonnegative : ∀ i e, e ∈ edges i → 0 ≤ e.probability  normalized : ∀ i, ((edges i).map Edge.probability).sum = 1/-- The probability of moving from state `i` to state `j` in one step: the total probability ofthe edges from `i` to `j`. -/def controlWeight (model : Model) (i j : Fin model.size) : Rat :=  ((model.edges i).map fun e ↦ if e.target = j then e.probability else 0).sum/-- The law of `x + reward` when `x` has law `law`. -/noncomputable def shift (reward : Rat) (law : Measure ℝ) : Measure ℝ :=  law.map (fun x ↦ x + (reward : ℝ))/-- Unnormalized output accumulated within `steps` transitions from a state. Taking an edge addsits reward to the eventual output. -/noncomputable def Model.outputWithin (model : Model) : Nat → Fin model.size → Measure ℝ  | 0, state => match model.kind state with      | .returned value => Measure.dirac (value : ℝ)      | _ => 0  | steps + 1, state => match model.kind state with      | .returned value => Measure.dirac (value : ℝ)      | .rejected => 0      | .transient => ((model.edges state).map fun edge ↦          ENNReal.ofReal (edge.probability : ℝ) •            shift edge.reward (model.outputWithin steps edge.target)).sum/-- The output law from a state: the limit of `outputWithin` over the number of steps. -/noncomputable def Model.outputAt (model : Model) (state : Fin model.size) : Measure ℝ :=  ⨆ steps, model.outputWithin steps state/-- The output law of the model: the output law from its initial state. -/noncomputable def Model.outputMeasure (model : Model) : Measure ℝ :=  model.outputAt model.initial/-- Exact source correspondence includes failure freedom and the entire output law. -/def Model.Matches (model : Model) (program : Paper.Expr) : Prop :=  Paper.DomainSafe program ∧ model.outputMeasure = Paper.bigStepMeasure programend Determinize.Spec.RewardModel