Best-arm complexity optimization bridge
DisprovedBanditAlgorithm.baiComplexity_mul_le_total_of_information_constraintsbanditsbest-arm-identificationinformation-theorylower-boundsoptimization
Fix a bandit environment in a class . Let be nonnegative sampling weights and let . Suppose every alternative environment satisfies the information constraint
Then the characteristic best-arm-identification time obeys
This is the optimization step that converts per-alternative change-of-measure inequalities into the closed-form sample-complexity lower bound.
Formalization Note All quantities are extended nonnegative reals, including zero and infinite boundary cases.
Preamble
import Definitions.Def_BanditTrajectory open MeasureTheory ProbabilityTheory InformationTheory ENNReal
Formal statement
theorem BanditAlgorithm.baiComplexity_mul_le_total_of_information_constraints
{k : ℕ} (𝓔 : Set (StochasticBandit k)) (ν : StochasticBandit k)
(c : Fin k → ℝ≥0∞) (L : ℝ≥0∞)
(hinfo : ∀ ν' ∈ baiAlternatives 𝓔 ν,
L ≤ ∑ i, c i * klDiv (ν.P i) (ν'.P i)) :
baiComplexity ν 𝓔 * L ≤ ∑ i, c i := by
sorrySource
Lattimore and Szepesvári, Bandit Algorithms (CUP 2020), proof of Theorem 33.5, printed p. 407, Eq. (33.7).