Example 8.1, p. 79 — if x₁ = 1 for some p₀ > 0, then p_t = p₀, x_t = 1 for all t and 𝔼[Regret(T)] = T·p₀/4
ProvedTSTutorial.KnownStandard.case_first_action_onebayesian-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 and , i.e. the strategy selects . Then for every horizon :
- on every history of positive probability, for every and for every ;
- the expected cumulative regret is exactly
Since action 's reward is uninformative about , the posterior never moves and the strategy keeps playing action , which loses per period when . This is the first case of the argument of Example 8.1; the regret grows linearly in .
Formalization Note Paper actions are Lean 0, 1 : Fin 2. "A history of positive probability" is . The case is included (the text only requires ).
Preamble
import Mathlib import Definitions.Def_TSTutorial_KnownStandard_Setting
Formal statement
namespace TSTutorial.KnownStandard
theorem case_first_action_one (f : Strategy) (p₀ : ℝ) (hp₀ : 0 < p₀) (hp₁ : p₀ ≤ 1)
(hf : f p₀ = 0) (T : ℕ) :
(∀ h : Hist T, 0 < ∑ θ : Bool, prior p₀ θ * lawGiven f p₀ T θ h →
post p₀ h = p₀ ∧ ∀ s : Fin T, post p₀ (histPrefix h s) = p₀ ∧ (h s).1 = 0) ∧
expRegret f p₀ T = T * (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, third and fourth sentences)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.