Section 2, Eqs. (6), (8) and M₁ — staying on heads and switching on tails loses at most 3 − 2^{3/2} per toss in the long run
ProvedRobbinsSeqDesign.StayOrSwitch.stay_or_switch_asymptotic_loss_lebandit-algorithmsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sequential-design
Let coins and have head probabilities , not both and not both , put , , and let be the total payoff of the first tosses under the rule : toss a fairly chosen coin first, then keep the coin after a head and switch to the other coin after a tail. Then
- ;
- the loss per toss relative to always tossing the better coin converges to the asymptotic loss
- ;
- when , , and when , .
So a person who uses loses in the long run at most per toss, whatever the coins, against for a rule that ignores the outcomes.
Formalization Note The asymptotic loss is stated as the limit of , not defined by its closed form. is written 2 * Real.sqrt 2. The head probabilities are elements of unitInterval; the attainment clause quantifies over the elements of unitInterval with the stated real values (, so it is not vacuous).
Preamble
import Mathlib import Definitions.Def_RobbinsSeqDesign_StayOrSwitch_Rules open MeasureTheory ProbabilityTheory Filter Topology
Formal statement
namespace RobbinsSeqDesign.StayOrSwitch
/-- Section 2, Eqs. (6), (8) and the maximum `M₁`, p. 531 (goal). For coins with head
probabilities `0 ≤ α, β ≤ 1`, not both `0` and not both `1`, under rule `R₁`:
`lim E(S_n/n) = γ + δ²/(1 − γ)`, the loss per toss `max(α, β) − E(S_n/n)` tends to
`L(A, B, R₁) = δ[1 − δ/(1 − γ)]`, and `0 ≤ L(A, B, R₁) ≤ M₁ = 3 − 2^{3/2}`, with
`L(A, B, R₁) = M₁` at `α = 0, β = 2 − 2^{1/2}` and at `α = 2 − 2^{1/2}, β = 0`. -/
theorem stay_or_switch_asymptotic_loss_le :
(∀ α β : unitInterval, ¬((α : ℝ) = 0 ∧ (β : ℝ) = 0) → ¬((α : ℝ) = 1 ∧ (β : ℝ) = 1) →
Tendsto (fun n => expectedAverage ruleR1 α β n) atTop
(𝓝 (gamma α β + delta α β ^ 2 / (1 - gamma α β))) ∧
Tendsto (fun n => max (α : ℝ) β - expectedAverage ruleR1 α β n) atTop
(𝓝 (delta α β * (1 - delta α β / (1 - gamma α β)))) ∧
0 ≤ delta α β * (1 - delta α β / (1 - gamma α β)) ∧
delta α β * (1 - delta α β / (1 - gamma α β)) ≤ 3 - 2 * Real.sqrt 2) ∧
(∀ α β : unitInterval,
((α : ℝ) = 0 ∧ (β : ℝ) = 2 - Real.sqrt 2) ∨ ((α : ℝ) = 2 - Real.sqrt 2 ∧ (β : ℝ) = 0) →
Tendsto (fun n => max (α : ℝ) β - expectedAverage ruleR1 α β n) atTop
(𝓝 (3 - 2 * Real.sqrt 2))) := by sorry
end RobbinsSeqDesign.StayOrSwitch
Source
Robbins, Some aspects of the sequential design of experiments, Bull. Amer. Math. Soc. 58 (1952), p. 531, Section 2, Eqs. (6), (8) and the maximum M₁
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.