Example 8.1, p. 79 — for every stationary deterministic strategy some prior p₀ makes 𝔼[Regret(T)] grow linearly
ProvedTSTutorial.KnownStandard.stationary_deterministic_linear_regretConsider the known-standard problem of Example 8.1 (p. 79): two actions , a parameter , action paying and action paying if and if . A stationary deterministic strategy chooses for one fixed function , where is the Bayes posterior (4.2).
Claim. For every stationary deterministic strategy there exist a prior probability and a constant such that for every horizon
where is the expected cumulative regret under the prior (p. 71).
The example shows that sublinear Bayesian regret bounds, such as those for Thompson sampling, cannot be achieved by a strategy that is both stationary and deterministic: a stationary strategy must randomize, or a deterministic one must depend on time, as UCB algorithms do.
Formalization Note Paper actions are Lean 0, 1 : Fin 2, and is true. The quantifiers are in the paper's order: for every there is a (the prior may depend on the strategy). "Grows linearly with time" is read as a linear lower bound with for all ; an upper bound holds for every strategy and is not part of the claim. as in the text, and because it is a probability.
import Mathlib import Definitions.Def_TSTutorial_KnownStandard_Setting
namespace TSTutorial.KnownStandard
theorem stationary_deterministic_linear_regret (f : Strategy) :
∃ p₀ : ℝ, 0 < p₀ ∧ p₀ ≤ 1 ∧
∃ c : ℝ, 0 < c ∧ ∀ T : ℕ, c * T ≤ expRegret f p₀ T := by sorry
end TSTutorial.KnownStandard
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.