BanditRLlib
Lean gate passed before this site build; local proof declarations are shown as compiled.Lean-verified build · exact declarations linked.

Lean module · Finite-horizon RL

BanditRLProof.RL.FiniteHorizonAdaptiveCumulativeUCBVISameSourceConfidence

This module starts the statistical producer on the actual finite episode law. For a fixed state/action/next-state coordinate, the residual at a generated stage is

Module map

Declarations
42
Placeholders
0

Imports

BanditRLProof.RL.FiniteHorizonAdaptiveCumulativeUCBVIClippedPlanner, BanditRLProof.RL.FiniteHorizonStageTransitionJointFactorization, BanditRLProof.ConcentrationFixedMGF, BanditRLProof.ConcentrationSubGaussian

Imported by

BanditRLProof.RL.FiniteHorizonAdaptiveCumulativeUCBVIBernsteinConfidence

Declarations

Open an item to read its exact compact statement and source link. Detailed teaching notes are linked when registered.

def BanditRLProof.FiniteHorizonRL.MDP.transitionResidualHead Compiled

One transition-coordinate residual on a chronological trace head.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.MDP.transitionResidualHead

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

def transitionResidualHead (mdp : MDP State Action) (targetState : State) (targetAction : Action) (targetNextState : State) (currentState : State) (head : Action × State) : Real
def BanditRLProof.FiniteHorizonRL.MDP.transitionVisitHead Compiled

The realized visit charged by one transition-coordinate residual.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.MDP.transitionVisitHead

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

def transitionVisitHead (_mdp : MDP State Action) (targetState : State) (targetAction : Action) (currentState : State) (head : Action × State) : Real
def BanditRLProof.FiniteHorizonRL.MDP.transitionResidualFrom Compiled

Sum of one fixed transition residual over the remaining generated trace.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.MDP.transitionResidualFrom

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

def transitionResidualFrom (mdp : MDP State Action) (targetState : State) (targetAction : Action) (targetNextState : State) : (remaining : Nat) -> State -> StepTrace Action State remaining -> Real | 0, _currentState, _trace => 0 | remaining + 1, currentState, trace => mdp.transitionResidualHead targetState targetAction targetNextState currentState (trace 0) + mdp.transitionResidualFrom targetState targetAction targetNextState remaining (trace 0).2 (Fin.tail trace) /-- Sum of actual visits to one state-action coordinate over the remaining trace. -/ def transitionVisitFrom (mdp : MDP State Action) (targetState : State) (targetAction : Action) : (remaining : Nat) -> State -> StepTrace Action State remaining -> Real | 0, _currentState, _trace => 0 | remaining + 1, currentState, trace => mdp.transitionVisitHead targetState targetAction currentState (trace 0) + mdp.transitionVisitFrom targetState targetAction remaining (trace 0).2 (Fin.tail trace) omit [Nonempty State] [Nonempty Action] in theorem measurable_transitionResidualFrom (mdp : MDP State Action) (targetState : State) (targetAction : Action) (targetNextState : State) (remaining : Nat) : Measurable (fun p : State × StepTrace Action State remaining => mdp.transitionResidualFrom targetState targetAction targetNextState remaining p.1 p.2)
def BanditRLProof.FiniteHorizonRL.MDP.transitionVisitFrom Compiled

Sum of actual visits to one state-action coordinate over the remaining trace.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.MDP.transitionVisitFrom

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

def transitionVisitFrom (mdp : MDP State Action) (targetState : State) (targetAction : Action) : (remaining : Nat) -> State -> StepTrace Action State remaining -> Real | 0, _currentState, _trace => 0 | remaining + 1, currentState, trace => mdp.transitionVisitHead targetState targetAction currentState (trace 0) + mdp.transitionVisitFrom targetState targetAction remaining (trace 0).2 (Fin.tail trace) omit [Nonempty State] [Nonempty Action] in theorem measurable_transitionResidualFrom (mdp : MDP State Action) (targetState : State) (targetAction : Action) (targetNextState : State) (remaining : Nat) : Measurable (fun p : State × StepTrace Action State remaining => mdp.transitionResidualFrom targetState targetAction targetNextState remaining p.1 p.2)
theorem BanditRLProof.FiniteHorizonRL.MDP.measurable_transitionResidualFrom Compiled

No declaration docstring is present; use the chapter context and exact statement below.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.MDP.measurable_transitionResidualFrom

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem measurable_transitionResidualFrom (mdp : MDP State Action) (targetState : State) (targetAction : Action) (targetNextState : State) (remaining : Nat) : Measurable (fun p : State × StepTrace Action State remaining => mdp.transitionResidualFrom targetState targetAction targetNextState remaining p.1 p.2)
theorem BanditRLProof.FiniteHorizonRL.MDP.measurable_transitionVisitFrom Compiled

No declaration docstring is present; use the chapter context and exact statement below.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.MDP.measurable_transitionVisitFrom

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem measurable_transitionVisitFrom (mdp : MDP State Action) (targetState : State) (targetAction : Action) (remaining : Nat) : Measurable (fun p : State × StepTrace Action State remaining => mdp.transitionVisitFrom targetState targetAction remaining p.1 p.2)
theorem BanditRLProof.FiniteHorizonRL.MDP.transitionResidualHead_compensated_hasMGFUpperBoundAt Compiled

No declaration docstring is present; use the chapter context and exact statement below.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.MDP.transitionResidualHead_compensated_hasMGFUpperBoundAt

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem transitionResidualHead_compensated_hasMGFUpperBoundAt (mdp : MDP State Action) (targetState : State) (targetAction : Action) (targetNextState : State) (currentState : State) (chosenAction : Action) (tilt : Real) : Concentration.HasMGFUpperBoundAt (fun nextState => tilt * mdp.transitionResidualHead targetState targetAction targetNextState currentState (chosenAction, nextState) - (tilt ^ 2 / 8) * mdp.transitionVisitHead targetState targetAction currentState (chosenAction, nextState)) 1 0 (mdp.transition (currentState, chosenAction))
theorem BanditRLProof.FiniteHorizonRL.MDP.actionStateKernel_transitionResidualHead_compensated_hasMGFUpperBoundAt Compiled

One generated action/transition head pays only its realized visit budget.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.MDP.actionStateKernel_transitionResidualHead_compensated_hasMGFUpperBoundAt

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem actionStateKernel_transitionResidualHead_compensated_hasMGFUpperBoundAt (mdp : MDP State Action) (policy : MarkovPolicy mdp) (targetState : State) (targetAction : Action) (targetNextState : State) (currentState : State) (stage : Fin mdp.horizon) (tilt : Real) : Concentration.HasMGFUpperBoundAt (fun head : Action × State => tilt * mdp.transitionResidualHead targetState targetAction targetNextState currentState head - (tilt ^ 2 / 8) * mdp.transitionVisitHead targetState targetAction currentState head) 1 0 (policy.actionStateKernel stage currentState)
theorem BanditRLProof.FiniteHorizonRL.MDP.trajectoryKernelRemaining_transitionResidual_compensated_hasMGFUpperBoundAt Compiled

The whole generated finite trace satisfies the same fixed-tilt exponential bound, with compensator equal to its literal state-action visit count.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.MDP.trajectoryKernelRemaining_transitionResidual_compensated_hasMGFUpperBoundAt

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem trajectoryKernelRemaining_transitionResidual_compensated_hasMGFUpperBoundAt (mdp : MDP State Action) (policy : MarkovPolicy mdp) (targetState : State) (targetAction : Action) (targetNextState : State) (tilt : Real) (remaining : Nat) (hremaining : remaining <= mdp.horizon) (currentState : State) : Concentration.HasMGFUpperBoundAt (fun trace => tilt * mdp.transitionResidualFrom targetState targetAction targetNextState remaining currentState trace - (tilt ^ 2 / 8) * mdp.transitionVisitFrom targetState targetAction remaining currentState trace) 1 0 (policy.trajectoryKernelRemaining remaining hremaining currentState)
theorem BanditRLProof.FiniteHorizonRL.MDP.transitionResidualFrom_eq_sum Compiled

Residual recursion is exactly the chronological finite sum.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.MDP.transitionResidualFrom_eq_sum

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem transitionResidualFrom_eq_sum (mdp : MDP State Action) (targetState : State) (targetAction : Action) (targetNextState : State) (remaining : Nat) (currentState : State) (trace : StepTrace Action State remaining) : mdp.transitionResidualFrom targetState targetAction targetNextState remaining currentState trace = ∑ stage : Fin remaining, mdp.transitionResidualHead targetState targetAction targetNextState (StepTrace.stateAt currentState trace stage) (trace stage)
theorem BanditRLProof.FiniteHorizonRL.MDP.transitionVisitFrom_eq_sum Compiled

Visit recursion is exactly the chronological finite sum.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.MDP.transitionVisitFrom_eq_sum

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem transitionVisitFrom_eq_sum (mdp : MDP State Action) (targetState : State) (targetAction : Action) (remaining : Nat) (currentState : State) (trace : StepTrace Action State remaining) : mdp.transitionVisitFrom targetState targetAction remaining currentState trace = ∑ stage : Fin remaining, mdp.transitionVisitHead targetState targetAction (StepTrace.stateAt currentState trace stage) (trace stage)
theorem BanditRLProof.FiniteHorizonRL.MDP.transitionResidualFrom_eq_aggregateCounts Compiled

The full-trace residual is the aggregate transition count minus the true singleton mass times the aggregate visit count.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.MDP.transitionResidualFrom_eq_aggregateCounts

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem transitionResidualFrom_eq_aggregateCounts (mdp : MDP State Action) (targetState : State) (targetAction : Action) (targetNextState : State) (trajectory : State × StepTrace Action State mdp.horizon) : mdp.transitionResidualFrom targetState targetAction targetNextState mdp.horizon trajectory.1 trajectory.2 = ((mdp.episodeBatchOfTrajectories 1 (fun _ => trajectory)) |>.transitionCountSummary.aggregateTransitionCount targetState targetAction targetNextState : Real) - ((mdp.episodeBatchOfTrajectories 1 (fun _ => trajectory)) |>.transitionCountSummary.aggregateVisitCount targetState targetAction : Real) * (mdp.transition (targetState, targetAction)).real {targetNextState}
theorem BanditRLProof.FiniteHorizonRL.MDP.transitionVisitFrom_eq_aggregateVisitCount Compiled

The full-trace compensator is the aggregate visit count of its one-batch image.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.MDP.transitionVisitFrom_eq_aggregateVisitCount

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem transitionVisitFrom_eq_aggregateVisitCount (mdp : MDP State Action) (targetState : State) (targetAction : Action) (trajectory : State × StepTrace Action State mdp.horizon) : mdp.transitionVisitFrom targetState targetAction mdp.horizon trajectory.1 trajectory.2 = ((mdp.episodeBatchOfTrajectories 1 (fun _ => trajectory)) |>.transitionCountSummary.aggregateVisitCount targetState targetAction : Real)
theorem BanditRLProof.FiniteHorizonRL.MDP.trajectoryMeasure_transitionResidual_compensated_hasMGFUpperBoundAt Compiled

The compensated fixed-tilt witness after integrating the random initial state.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.MDP.trajectoryMeasure_transitionResidual_compensated_hasMGFUpperBoundAt

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem trajectoryMeasure_transitionResidual_compensated_hasMGFUpperBoundAt (mdp : MDP State Action) (policy : MarkovPolicy mdp) (initialState : Measure State) [IsProbabilityMeasure initialState] (targetState : State) (targetAction : Action) (targetNextState : State) (tilt : Real) : Concentration.HasMGFUpperBoundAt (fun trajectory => tilt * mdp.transitionResidualFrom targetState targetAction targetNextState mdp.horizon trajectory.1 trajectory.2 - (tilt ^ 2 / 8) * mdp.transitionVisitFrom targetState targetAction mdp.horizon trajectory.1 trajectory.2) 1 0 (policy.trajectoryMeasure initialState)
def BanditRLProof.FiniteHorizonRL.EpisodeBatch.aggregateTransitionResidual Compiled

The generated one-batch aggregate transition residual.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.EpisodeBatch.aggregateTransitionResidual

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

noncomputable def aggregateTransitionResidual {mdp : MDP State Action} (batch : EpisodeBatch mdp 1) (state : State) (action : Action) (nextState : State) : Real
def BanditRLProof.FiniteHorizonRL.EpisodeBatch.aggregateVisitReal Compiled

The generated one-batch aggregate state-action visit count as a real.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.EpisodeBatch.aggregateVisitReal

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

def aggregateVisitReal {mdp : MDP State Action} (batch : EpisodeBatch mdp 1) (state : State) (action : Action) : Real
theorem BanditRLProof.FiniteHorizonRL.EpisodeBatch.measurable_aggregateTransitionResidual Compiled

No declaration docstring is present; use the chapter context and exact statement below.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.EpisodeBatch.measurable_aggregateTransitionResidual

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem measurable_aggregateTransitionResidual {mdp : MDP State Action} (state : State) (action : Action) (nextState : State) : Measurable (fun batch : EpisodeBatch mdp 1 => batch.aggregateTransitionResidual state action nextState)
theorem BanditRLProof.FiniteHorizonRL.EpisodeBatch.measurable_aggregateVisitReal Compiled

No declaration docstring is present; use the chapter context and exact statement below.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.EpisodeBatch.measurable_aggregateVisitReal

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem measurable_aggregateVisitReal {mdp : MDP State Action} (state : State) (action : Action) : Measurable (fun batch : EpisodeBatch mdp 1 => batch.aggregateVisitReal state action)
theorem BanditRLProof.FiniteHorizonRL.EpisodeBatch.aggregateVisitCount_le_horizon Compiled

One generated episode contributes at most one pooled visit per stage.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.EpisodeBatch.aggregateVisitCount_le_horizon

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem aggregateVisitCount_le_horizon {mdp : MDP State Action} (batch : EpisodeBatch mdp 1) (state : State) (action : Action) : batch.transitionCountSummary.aggregateVisitCount state action <= mdp.horizon
theorem BanditRLProof.FiniteHorizonRL.EpisodeBatch.abs_aggregateTransitionResidual_le_two_mul_horizon Compiled

The one-episode transition residual is bounded by twice the horizon.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.EpisodeBatch.abs_aggregateTransitionResidual_le_two_mul_horizon

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem abs_aggregateTransitionResidual_le_two_mul_horizon {mdp : MDP State Action} (batch : EpisodeBatch mdp 1) (state : State) (action : Action) (nextState : State) : |batch.aggregateTransitionResidual state action nextState| <= 2 * (mdp.horizon : Real)
theorem BanditRLProof.FiniteHorizonRL.MarkovPolicy.iidEpisodeBatchMeasure_one_aggregateTransitionResidual_compensated_hasMGFUpperBoundAt Compiled

The exact one-episode generated batch law inherits the trace-level compensated MGF; no independent empirical batch is introduced.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.MarkovPolicy.iidEpisodeBatchMeasure_one_aggregateTransitionResidual_compensated_hasMGFUpperBoundAt

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem iidEpisodeBatchMeasure_one_aggregateTransitionResidual_compensated_hasMGFUpperBoundAt {mdp : MDP State Action} (policy : MarkovPolicy mdp) (initialState : Measure State) [IsProbabilityMeasure initialState] (state : State) (action : Action) (nextState : State) (tilt : Real) : Concentration.HasMGFUpperBoundAt (fun batch : EpisodeBatch mdp 1 => tilt * batch.aggregateTransitionResidual state action nextState - (tilt ^ 2 / 8) * batch.aggregateVisitReal state action) 1 0 (policy.iidEpisodeBatchMeasure initialState 1)
def BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.batchPrefixFiltration Compiled

Canonical finite-prefix filtration presented with the actual `frestrictLe` history object consumed by `AdaptiveEpisodeBatchSource`. It is extensionally the usual product filtration, but this presentation keeps conditional kernels definitionally aligned with the generated source.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.batchPrefixFiltration

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

noncomputable def batchPrefixFiltration {mdp : MDP State Action} (episodes : Nat) : @Filtration (EpisodeBatchTrajectory mdp episodes) Nat _ MeasurableSpace.pi where
theorem BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.hasCondMGFUpperBoundAt_of_condExpKernel_map_eq Compiled

Transport pointwise fixed-tilt MGF bounds through an identified conditional kernel map. This is the fixed-MGF analogue of the repository's centered sub-Gaussian condExpKernel bridge.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.hasCondMGFUpperBoundAt_of_condExpKernel_map_eq

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem hasCondMGFUpperBoundAt_of_condExpKernel_map_eq {Omega : Type*} [mOmega : MeasurableSpace Omega] [StandardBorelSpace Omega] (mu : Measure Omega) [IsFiniteMeasure mu] (mcond : MeasurableSpace Omega) (hmcond : mcond <= mOmega) (X : Omega -> Real) (hX : @Measurable Omega Real mOmega inferInstance X) (tilt budget : Real) (target : Omega -> Measure Real) (hintegrable : ∀ s, Integrable (fun omega => Real.exp (s * X omega)) mu) (hmap : Filter.Eventually (fun omega => @Measure.map Omega Real mOmega inferInstance X ((@ProbabilityTheory.condExpKernel Omega mOmega _ mu _ mcond) omega) = target omega) (ae (@MeasureTheory.Measure.trim Omega mcond mOmega mu hmcond))) (htarget : Filter.Eventually (fun omega => Concentration.HasMGFUpperBoundAt id tilt budget (target omega)) (ae (@MeasureTheory.Measure.trim Omega mcond mOmega mu hmcond))) : Concentration.HasCondMGFUpperBoundAt mcond hmcond X tilt budget mu
theorem BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.hasCondMGFUpperBoundAt_congr_measurableSpace Compiled

Transport a fixed-tilt conditional MGF certificate across propositionally equal conditioning measurable spaces.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.hasCondMGFUpperBoundAt_congr_measurableSpace

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem hasCondMGFUpperBoundAt_congr_measurableSpace {Omega : Type*} [mOmega : MeasurableSpace Omega] [StandardBorelSpace Omega] (mu : Measure Omega) [IsFiniteMeasure mu] (mcond mcond' : MeasurableSpace Omega) (hmcond : mcond <= mOmega) (hmcond' : mcond' <= mOmega) (hspaces : mcond = mcond') (X : Omega -> Real) (tilt budget : Real) (h : Concentration.HasCondMGFUpperBoundAt mcond hmcond X tilt budget mu) : Concentration.HasCondMGFUpperBoundAt mcond' hmcond' X tilt budget mu
def BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.aggregateTransitionResidualPrefix Compiled

Residual of the last batch visible in a finite generated prefix.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.aggregateTransitionResidualPrefix

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

noncomputable def aggregateTransitionResidualPrefix {mdp : MDP State Action} {initialState : Measure State} [IsProbabilityMeasure initialState] (source : AdaptiveEpisodeBatchSource mdp initialState 1) (state : State) (action : Action) (nextState : State) (round : Nat) (history : EpisodeBatchPrefix mdp 1 round) : Real
def BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.aggregateVisitPrefix Compiled

Visit count of the last batch visible in a finite generated prefix.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.aggregateVisitPrefix

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

def aggregateVisitPrefix {mdp : MDP State Action} {initialState : Measure State} [IsProbabilityMeasure initialState] (source : AdaptiveEpisodeBatchSource mdp initialState 1) (state : State) (action : Action) (round : Nat) (history : EpisodeBatchPrefix mdp 1 round) : Real
theorem BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.measurable_aggregateTransitionResidualPrefix Compiled

No declaration docstring is present; use the chapter context and exact statement below.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.measurable_aggregateTransitionResidualPrefix

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem measurable_aggregateTransitionResidualPrefix {mdp : MDP State Action} {initialState : Measure State} [IsProbabilityMeasure initialState] (source : AdaptiveEpisodeBatchSource mdp initialState 1) (state : State) (action : Action) (nextState : State) (round : Nat) : Measurable (source.aggregateTransitionResidualPrefix state action nextState round)
theorem BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.measurable_aggregateVisitPrefix Compiled

No declaration docstring is present; use the chapter context and exact statement below.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.measurable_aggregateVisitPrefix

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem measurable_aggregateVisitPrefix {mdp : MDP State Action} {initialState : Measure State} [IsProbabilityMeasure initialState] (source : AdaptiveEpisodeBatchSource mdp initialState 1) (state : State) (action : Action) (round : Nat) : Measurable (source.aggregateVisitPrefix state action round)
def BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.aggregateTransitionResidualIncrement Compiled

The actual one-episode transition residual at adaptive coordinate `round`.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.aggregateTransitionResidualIncrement

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

noncomputable def aggregateTransitionResidualIncrement {mdp : MDP State Action} {initialState : Measure State} [IsProbabilityMeasure initialState] (source : AdaptiveEpisodeBatchSource mdp initialState 1) (state : State) (action : Action) (nextState : State) (round : Nat) (trajectory : EpisodeBatchTrajectory mdp 1) : Real
def BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.aggregateVisitIncrement Compiled

The actual pooled visit count at adaptive coordinate `round`.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.aggregateVisitIncrement

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

def aggregateVisitIncrement {mdp : MDP State Action} {initialState : Measure State} [IsProbabilityMeasure initialState] (source : AdaptiveEpisodeBatchSource mdp initialState 1) (state : State) (action : Action) (round : Nat) (trajectory : EpisodeBatchTrajectory mdp 1) : Real
theorem BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.measurable_aggregateTransitionResidualIncrement Compiled

No declaration docstring is present; use the chapter context and exact statement below.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.measurable_aggregateTransitionResidualIncrement

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem measurable_aggregateTransitionResidualIncrement {mdp : MDP State Action} {initialState : Measure State} [IsProbabilityMeasure initialState] (source : AdaptiveEpisodeBatchSource mdp initialState 1) (state : State) (action : Action) (nextState : State) (round : Nat) : Measurable (source.aggregateTransitionResidualIncrement state action nextState round)
theorem BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.measurable_aggregateVisitIncrement Compiled

No declaration docstring is present; use the chapter context and exact statement below.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.measurable_aggregateVisitIncrement

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem measurable_aggregateVisitIncrement {mdp : MDP State Action} {initialState : Measure State} [IsProbabilityMeasure initialState] (source : AdaptiveEpisodeBatchSource mdp initialState 1) (state : State) (action : Action) (round : Nat) : Measurable (source.aggregateVisitIncrement state action round)
theorem BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.aggregateTransitionResidual_compensated_stronglyAdapted_piLE Compiled

The compensated residual process is adapted to the canonical prefix filtration.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.aggregateTransitionResidual_compensated_stronglyAdapted_piLE

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem aggregateTransitionResidual_compensated_stronglyAdapted_piLE {mdp : MDP State Action} {initialState : Measure State} [IsProbabilityMeasure initialState] (source : AdaptiveEpisodeBatchSource mdp initialState 1) (state : State) (action : Action) (nextState : State) (tilt varianceCoeff : Real) : StronglyAdapted (batchPrefixFiltration (mdp := mdp) 1) (fun round trajectory => tilt * source.aggregateTransitionResidualIncrement state action nextState round trajectory - varianceCoeff * source.aggregateVisitIncrement state action round trajectory)
theorem BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.trajectoryMeasure_condDistrib_batchStatistic Compiled

Any measurable real statistic of the next generated episode has exactly the mapped history kernel as its regular conditional law. This reusable bridge is stated for the whole generated batch, so downstream confidence proofs do not replace the recurrent process by an offline batch model.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.trajectoryMeasure_condDistrib_batchStatistic

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem trajectoryMeasure_condDistrib_batchStatistic {mdp : MDP State Action} {initialState : Measure State} [IsProbabilityMeasure initialState] {episodes : Nat} [StandardBorelSpace (EpisodeBatch mdp episodes)] (source : AdaptiveEpisodeBatchSource mdp initialState episodes) (n : Nat) (statistic : EpisodeBatch mdp episodes -> Real) (hstatistic : Measurable statistic) : ProbabilityTheory.condDistrib (fun trajectory : EpisodeBatchTrajectory mdp episodes => statistic (trajectory (n + 1))) (Preorder.frestrictLe n) source.trajectoryMeasure =ᵐ[ source.trajectoryMeasure.map (Preorder.frestrictLe n)] (source.batchKernel n).map statistic
theorem BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.condExpKernel_map_batchStatistic_eq_batchKernel Compiled

Trimmed conditional-expectation-kernel law for an arbitrary measurable real statistic of the next generated episode.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.condExpKernel_map_batchStatistic_eq_batchKernel

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem condExpKernel_map_batchStatistic_eq_batchKernel {mdp : MDP State Action} {initialState : Measure State} [IsProbabilityMeasure initialState] {episodes : Nat} [StandardBorelSpace (EpisodeBatch mdp episodes)] [StandardBorelSpace (EpisodeBatchTrajectory mdp episodes)] (source : AdaptiveEpisodeBatchSource mdp initialState episodes) (n : Nat) (statistic : EpisodeBatch mdp episodes -> Real) (hstatistic : Measurable statistic) : Filter.Eventually (fun trajectory : EpisodeBatchTrajectory mdp episodes => Measure.map (fun path : EpisodeBatchTrajectory mdp episodes => statistic (path (n + 1))) (ProbabilityTheory.condExpKernel source.trajectoryMeasure ((inferInstance : MeasurableSpace (EpisodeBatchPrefix mdp episodes n)).comap (Preorder.frestrictLe n)) trajectory) = ((source.batchKernel n).map statistic) (Preorder.frestrictLe n trajectory)) (ae (source.trajectoryMeasure.trim (Preorder.measurable_frestrictLe n).comap_le))
theorem BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.integrable_exp_mul_aggregateTransitionResidual_compensatedIncrement Compiled

Every compensated adaptive residual increment is globally exponentially integrable.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.integrable_exp_mul_aggregateTransitionResidual_compensatedIncrement

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem integrable_exp_mul_aggregateTransitionResidual_compensatedIncrement {mdp : MDP State Action} {initialState : Measure State} [IsProbabilityMeasure initialState] (source : AdaptiveEpisodeBatchSource mdp initialState 1) (state : State) (action : Action) (nextState : State) (round : Nat) (tilt varianceCoeff s : Real) : Integrable (fun trajectory : EpisodeBatchTrajectory mdp 1 => Real.exp (s * (tilt * source.aggregateTransitionResidualIncrement state action nextState round trajectory - varianceCoeff * source.aggregateVisitIncrement state action round trajectory))) source.trajectoryMeasure
theorem BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.aggregateTransitionResidual_succ_compensated_hasCondMGFUpperBoundAt Compiled

At every successor episode, the actual transition residual has the same visit-charged fixed-tilt conditional MGF under the recurrent source law.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.aggregateTransitionResidual_succ_compensated_hasCondMGFUpperBoundAt

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem aggregateTransitionResidual_succ_compensated_hasCondMGFUpperBoundAt {mdp : MDP State Action} {initialState : Measure State} [IsProbabilityMeasure initialState] [StandardBorelSpace (EpisodeBatch mdp 1)] [StandardBorelSpace (EpisodeBatchTrajectory mdp 1)] (source : AdaptiveEpisodeBatchSource mdp initialState 1) (state : State) (action : Action) (nextState : State) (n : Nat) (tilt : Real) : Concentration.HasCondMGFUpperBoundAt (mΩ := MeasurableSpace.pi) (batchPrefixFiltration (mdp := mdp) 1 n) ((batchPrefixFiltration (mdp := mdp) 1).le n) (fun trajectory => tilt * source.aggregateTransitionResidualIncrement state action nextState (n + 1) trajectory - (tilt ^ 2 / 8) * source.aggregateVisitIncrement state action (n + 1) trajectory) 1 0 source.trajectoryMeasure
theorem BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.aggregateTransitionResidual_zero_compensated_hasMGFUpperBoundAt Compiled

Coordinate zero has the same compensated MGF certificate under the exact initial marginal of the generated recurrent trajectory.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.aggregateTransitionResidual_zero_compensated_hasMGFUpperBoundAt

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem aggregateTransitionResidual_zero_compensated_hasMGFUpperBoundAt {mdp : MDP State Action} {initialState : Measure State} [IsProbabilityMeasure initialState] (source : AdaptiveEpisodeBatchSource mdp initialState 1) (state : State) (action : Action) (nextState : State) (tilt : Real) : Concentration.HasMGFUpperBoundAt (fun trajectory : EpisodeBatchTrajectory mdp 1 => tilt * source.aggregateTransitionResidualIncrement state action nextState 0 trajectory - (tilt ^ 2 / 8) * source.aggregateVisitIncrement state action 0 trajectory) 1 0 source.trajectoryMeasure
theorem BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.sum_aggregateTransitionResidualIncrement_eq_prefixAggregateResidual Compiled

Summing the adaptive one-batch residuals through coordinate `round` recovers the exact pooled numerator minus its true transition mass.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.sum_aggregateTransitionResidualIncrement_eq_prefixAggregateResidual

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem sum_aggregateTransitionResidualIncrement_eq_prefixAggregateResidual {mdp : MDP State Action} {initialState : Measure State} [IsProbabilityMeasure initialState] (source : AdaptiveEpisodeBatchSource mdp initialState 1) (trajectory : EpisodeBatchTrajectory mdp 1) (round : Nat) (state : State) (action : Action) (nextState : State) : (∑ i ∈ Finset.range (round + 1), source.aggregateTransitionResidualIncrement state action nextState i trajectory) = (adaptiveCumulativeAggregateTransitionCountAt trajectory round state action nextState : Real) - (adaptiveCumulativeAggregateVisitCountAt trajectory round state action : Real) * (mdp.transition (state, action)).real {nextState}
theorem BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.sum_aggregateVisitIncrement_eq_prefixAggregateVisitCount Compiled

The compensator sum is literally the aggregate visit denominator used by the recurrent planner at the same generated prefix.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.sum_aggregateVisitIncrement_eq_prefixAggregateVisitCount

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem sum_aggregateVisitIncrement_eq_prefixAggregateVisitCount {mdp : MDP State Action} {initialState : Measure State} [IsProbabilityMeasure initialState] (source : AdaptiveEpisodeBatchSource mdp initialState 1) (trajectory : EpisodeBatchTrajectory mdp 1) (round : Nat) (state : State) (action : Action) : (∑ i ∈ Finset.range (round + 1), source.aggregateVisitIncrement state action i trajectory) = (adaptiveCumulativeAggregateVisitCountAt trajectory round state action : Real)
theorem BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.measure_aggregateTransitionResidualSum_ge_inter_visitSum_le Compiled

Fixed-tilt, actual-count upper tail for one pooled transition coordinate on a finite prefix of the generated recurrent process. The random count is retained in the event; no expected-occupancy lower bound is substituted.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.measure_aggregateTransitionResidualSum_ge_inter_visitSum_le

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem measure_aggregateTransitionResidualSum_ge_inter_visitSum_le {mdp : MDP State Action} {initialState : Measure State} [IsProbabilityMeasure initialState] [StandardBorelSpace (EpisodeBatch mdp 1)] [StandardBorelSpace (EpisodeBatchTrajectory mdp 1)] (source : AdaptiveEpisodeBatchSource mdp initialState 1) (state : State) (action : Action) (nextState : State) (rounds : Nat) (tilt threshold visitBudget : Real) (htilt : 0 < tilt) : source.trajectoryMeasure {trajectory | threshold <= ∑ i ∈ Finset.range rounds, source.aggregateTransitionResidualIncrement state action nextState i trajectory ∧ (∑ i ∈ Finset.range rounds, source.aggregateVisitIncrement state action i trajectory) <= visitBudget} <= ENNReal.ofReal (Real.exp (-tilt * threshold + (tilt ^ 2 / 8) * visitBudget))
theorem BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.measure_abs_aggregateTransitionResidualSum_ge_inter_visitSum_le Compiled

Two-sided version of the exact-count prefix tail. Both signs are proved from the same generated conditional law; the factor two is only the final finite union.

Used in these reading views: Bandit Book · Reinforcement Learning Book

9. Finite-horizon reinforcement learning

Canonical node identitydeclaration:BanditRLProof.FiniteHorizonRL.AdaptiveEpisodeBatchSource.measure_abs_aggregateTransitionResidualSum_ge_inter_visitSum_le

Reading membership is not a proof dependency. Exact assumptions remain in the Lean statement.

theorem measure_abs_aggregateTransitionResidualSum_ge_inter_visitSum_le {mdp : MDP State Action} {initialState : Measure State} [IsProbabilityMeasure initialState] [StandardBorelSpace (EpisodeBatch mdp 1)] [StandardBorelSpace (EpisodeBatchTrajectory mdp 1)] (source : AdaptiveEpisodeBatchSource mdp initialState 1) (state : State) (action : Action) (nextState : State) (rounds : Nat) (tilt threshold visitBudget : Real) (htilt : 0 < tilt) : source.trajectoryMeasure {trajectory | threshold <= |∑ i ∈ Finset.range rounds, source.aggregateTransitionResidualIncrement state action nextState i trajectory| ∧ (∑ i ∈ Finset.range rounds, source.aggregateVisitIncrement state action i trajectory) <= visitBudget} <= 2 * ENNReal.ofReal (Real.exp (-tilt * threshold + (tilt ^ 2 / 8) * visitBudget))