BanditAlgorithm.contextual_bandit_exp4_regret_bound
Proved(Exp4 regret bound, GOAL — L&S Theorem 18.1) Let and
For any adversarial rewards and any oblivious experts whose advice rows lie in the probability simplex, the regret of Exp4 against the best expert satisfies
(Eq. (18.7)).
import Definitions.Def_ContextualAdversarialBandit import Definitions.Def_exp4Policy open MeasureTheory ProbabilityTheory
theorem BanditAlgorithm.contextual_bandit_exp4_regret_bound
{k M : ℕ} (hk : 0 < k) (hM : 1 < M) (n : ℕ) (hn : 0 < n)
(x : ℕ → Fin k → ℝ) (hx : ∀ t : ℕ, ∀ a : Fin k, x t a ∈ Set.Icc (0 : ℝ) 1)
(E : ℕ → Fin M → Fin k → ℝ)
(hE0 : ∀ t : ℕ, ∀ m : Fin M, ∀ a : Fin k, 0 ≤ E t m a)
(hE1 : ∀ t : ℕ, ∀ m : Fin M, ∑ a, E t m a = 1)
(π : BanditPolicy k)
(hπ : IsExp4Policy (Real.sqrt (2 * Real.log M / (n * k))) 0 E π) :
exp4Regret n x E π ≤ Real.sqrt (2 * n * k * Real.log M) := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Setup and notation. A -armed adversarial bandit with deterministic reward table (, ) is played by a policy with the advice of experts . The interaction law on length- histories draws, at each round , the arm from the policy's Markov kernel applied to the past history and records the pair . The regret against the experts is
The policy is assumed to be an Exp4 policy: writing , , , and , the policy's kernel at every round and every history equals — here with the specific parameters
Assertion.
Hypotheses.
- , (strictly ), and .
- Rewards are bounded: (closed interval) for every — all rounds, not only — and every arm .
- Advice rows are probability vectors at every round: and for all and all .
- is an Exp4 policy for and the given advice , in the exact kernel-equality sense above.
Edge cases.
- With , the estimator's divisor is alone; if the division yields by convention.
- Since , , so is a genuine positive real and the right-hand side is a positive real square root.
- The bound is on the expected-regret quantity (a Bochner integral appears in its definition; convention if non-integrable); this is not a high-probability statement.
- The Exp4-policy hypothesis is an exact measure equality required at every history; if no policy satisfies it for the given data, the statement is vacuously true for that data.
Confirmed by the mission captain (proposal self-audit).