Example 8.1, p. 79 — if x₁ = 2 for all p₀ > 0, then x_t = 2 for all t and 𝔼[Regret(T)] = T·(1 − p₀)/4
ProvedTSTutorial.KnownStandard.case_first_action_twobayesian-regretmulti-armed-banditp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1thompson-sampling
Consider the known-standard problem of Example 8.1: two actions, , action paying , action paying if and if . Let be a stationary deterministic strategy, , where is the posterior probability that given .
Suppose that for every , i.e. the strategy selects for every prior . Then for every prior and every horizon :
- on every history of positive probability, for every ;
- the expected cumulative regret is exactly
The posterior stays in , so the strategy keeps playing action , which loses per period when . This is the second case of the argument of Example 8.1; for the regret grows linearly in .
Formalization Note Paper actions are Lean 0, 1 : Fin 2. "For all " is read as for all , the values a prior probability can take. "A history of positive probability" is .
Preamble
import Mathlib import Definitions.Def_TSTutorial_KnownStandard_Setting
Formal statement
namespace TSTutorial.KnownStandard
theorem case_first_action_two (f : Strategy) (hf : ∀ p : ℝ, 0 < p → p ≤ 1 → f p = 1)
(p₀ : ℝ) (hp₀ : 0 < p₀) (hp₁ : p₀ ≤ 1) (T : ℕ) :
(∀ h : Hist T, 0 < ∑ θ : Bool, prior p₀ θ * lawGiven f p₀ T θ h →
∀ s : Fin T, (h s).1 = 1) ∧
expRegret f p₀ T = T * ((1 - p₀) / 4) := by sorry
end TSTutorial.KnownStandard
Source
Russo, Van Roy, Kazerouni, Osband, Wen, A Tutorial on Thompson Sampling, Found. Trends Mach. Learn. 11(1) (2018), p. 79, §8.1.3, Example 8.1 (second paragraph, fifth sentence)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.