Proposition 5.3, p. 32 — A-armed bandit, M̄(π) = Ber(1/2): dec_γ(M^∞_{ε_γ}(M̄), M̄) ≥ 2⁻⁶·A/γ for γ ≥ A/3, ε_γ = A/(12γ)
ProvedStatComplexityDM.MAB.mab_localized_dec_lower_boundConsider the multi-armed bandit problem with actions and rewards in , and the reference model for every arm. For every , with ,
where is the Decision-Estimation Coefficient and is the -localized class (12).
Combined with the paper's in-expectation lower bound (Theorem 3.2), this yields the minimax regret lower bound for multi-armed bandits, matching the DEC upper bounds of Propositions 5.1 and 5.2 up to constants.
Formalization Note The model class is the Bernoulli bandits (reward distributions supported on ), a subclass of the paper's class of all distributions on ; since the localized class shrinks and the DEC decreases when passing to a subclass, this bound implies the paper's. The bound holds for every selector of optimal arms. The constant is the page's; its proof yields .
import Mathlib import Definitions.Def_FoundationsRL_GeneralDM_DEC import Definitions.Def_StatComplexityDM_LowerBound_Core import Definitions.Def_StatComplexityDM_MAB_Bernoulli
namespace StatComplexityDM.MAB
open FoundationsRL.GeneralDM
/-- Proposition 5.3 (arXiv:2112.13487v3, p. 32): for the multi-armed bandit with `A ≥ 2` arms,
rewards in `[0, 1]` and reference model `M̄(π) = Ber(1/2)`,
`dec_γ(M^∞_{ε_γ}(M̄), M̄) ≥ 2⁻⁶ · A/γ` for all `γ ≥ A/3`, where `ε_γ = A/(12γ)`.
The class is the Bernoulli bandits (a subclass of the paper's, which makes the bound stronger),
`dec_γ` is `decGf` (2) and `M^∞_ε(M̄)` is `linfLocalized` (12); the bound holds for every selector
`piStar` of maximizers of the mean reward. -/
theorem mab_localized_dec_lower_bound (A : ℕ) (hA : 2 ≤ A)
(piStar : (Fin A → Bool → ℝ) → Fin A) (hpiStar : StatComplexityDM.LowerBound.IsArgmaxSel berRew piStar)
(γ : ℝ) (hγ : (A : ℝ) / 3 ≤ γ) :
(2 : ℝ) ^ (-6 : ℤ) * ((A : ℝ) / γ) ≤
decGf (StatComplexityDM.LowerBound.linfLocalized (bernoulliBandits A) berRew piStar (fun _ => ber (1 / 2))
((A : ℝ) / (12 * γ)))
berRew piStar γ (fun _ => ber (1 / 2)) := by sorry
end StatComplexityDM.MAB
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.