Bounds on expected discounted stopping duration
ProvedBanditAlgorithm.integral_discountedStoppedSum_one_boundsbanditsgeometric-seriesoptimal-stopping
If an admissible stopping rule plays for at least one round, its expected discounted duration lies between and the full geometric duration .
Preamble
import Theorems.Thm_BanditAlgorithm_integrable_discountedStoppedSum_one open MeasureTheory ProbabilityTheory
Formal statement
theorem BanditAlgorithm.integral_discountedStoppedSum_one_bounds
{S : Type*} [MeasurableSpace S]
(P : Kernel S S) [IsMarkovKernel P]
{α : ℝ} (hα0 : 0 ≤ α) (hα1 : α < 1) (x : S)
{τ : (ℕ → S) → ℕ∞} (hτ : IsTrajStoppingTime τ)
(hτ1 : ∀ ω, 1 ≤ τ ω) :
1 ≤ (∫ ω, discountedStoppedSum α (fun _ : S ↦ 1) τ ω
∂markovChainMeasure P x) ∧
(∫ ω, discountedStoppedSum α (fun _ : S ↦ 1) τ ω
∂markovChainMeasure P x) ≤ ∑' t : ℕ, α ^ t := by
sorrySource
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), denominator in Eq. (35.9), printed p.448.