Section 2, p. 531 — rule R₀ has asymptotic loss L(A, B, R₀) = δ, with maximum M₀ = 1/2 at (0, 1) and (1, 0)
ProvedRobbinsSeqDesign.StayOrSwitch.rule_R0_lossbandit-algorithmsp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1sequential-design
Let coins and have head probabilities , not both and not both , and let be as in (5). Under the rule (choose one of the coins at random and stick to it), the loss per toss tends to :
Moreover for every admissible , with at and at ; so the worst case of is , against for .
Formalization Note "At random" is the fair choice. The paper's parenthetical alternative "(or in tossing the two coins alternately)" is not part of this statement. The standing exclusion of the two corners is kept, as on the page.
Preamble
import Mathlib import Definitions.Def_RobbinsSeqDesign_StayOrSwitch_Rules open MeasureTheory ProbabilityTheory Filter Topology
Formal statement
namespace RobbinsSeqDesign.StayOrSwitch
/-- Section 2, p. 531, rule `R₀`: if `α, β` are not both `0` and not both `1`, the loss per toss
`max(α, β) − E(S_n/n)` of rule `R₀` tends to `L(A, B, R₀) = (γ + δ) − γ = δ`; and `δ` has the
maximum `M₀ = 1/2` over all admissible `(α, β)`, taken at `α = 0, β = 1` and at
`α = 1, β = 0`. -/
theorem rule_R0_loss :
(∀ α β : unitInterval, ¬((α : ℝ) = 0 ∧ (β : ℝ) = 0) → ¬((α : ℝ) = 1 ∧ (β : ℝ) = 1) →
Tendsto (fun n => max (α : ℝ) β - expectedAverage ruleR0 α β n) atTop
(𝓝 (delta α β))) ∧
(∀ α β : ℝ, 0 ≤ α → α ≤ 1 → 0 ≤ β → β ≤ 1 → ¬(α = 0 ∧ β = 0) → ¬(α = 1 ∧ β = 1) →
delta α β ≤ 1 / 2) ∧
delta 0 1 = 1 / 2 ∧ delta 1 0 = 1 / 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 (rule R₀, L(A, B, R₀), M₀)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.