BanditAlgorithm.adversarial_bandit_exp3_regret_bound
Proved(Exp3, improved bound, GOAL) Let be an adversarial bandit with arms and horizon , and let be Exp3 with learning rate . Then
import Definitions.Def_AdversarialBandit import Definitions.Def_exp3Policy open MeasureTheory ProbabilityTheory
theorem BanditAlgorithm.adversarial_bandit_exp3_regret_bound
{k : ℕ} (hk : 1 < k) (n : ℕ) (hn : 0 < n)
(x : ℕ → Fin k → ℝ) (hx : ∀ t : ℕ, ∀ i : Fin k, x t i ∈ Set.Icc (0 : ℝ) 1)
(π : BanditPolicy k)
(hπ : IsExp3Policy (Real.sqrt (2 * Real.log k / (n * k))) π) :
adversarialRegret n x π ≤ Real.sqrt (2 * n * k * Real.log k) := by
sorry
Read-back
What the Lean code literally says, in plain math · claude-fable-5
Setup (all notions unfolded from the underlying definitions). Fix an arm count and write . A history of length is a sequence of pairs , ; a policy gives, for each and each length- history , a probability measure on , measurably in . Given a reward table of reals, the -round adversarial law on length- histories is defined recursively: is the point mass at the empty history, and is the law of extended by the pair , where and — the reward recorded at round is deterministically .
For a real parameter , the Exp3 estimates and probabilities are defined by the joint recursion and
where is the length- prefix of and its last entry (so unplayed arms gain per round and the played arm gains ). " is an Exp3() policy" means: for every and every length- history (reachable or not), the nonnegative weights being read into .
The expected regret is
— the hindsight best single-arm total minus the expected sum of recorded rewards. (The first term is a real-valued supremum over the finite arm set, a genuine maximum since under the hypotheses below.)
Assertion. With (naturals cast to reals), the theorem claims
Hypotheses:
- with (at least two arms).
- with .
- (closed interval) for every round — not merely the rounds that are actually played — and every arm .
- is any policy satisfying the Exp3() predicate at the specific learning rate .
Edge cases and caveats:
- The conclusion is asserted only for this exact pinned learning rate; nothing is claimed for any other .
- The Exp3 predicate constrains at every history of every length, including unreachable ones; the theorem is universally quantified over policies satisfying it and does not itself assert that such a policy exists.
- is the real square root, which returns on negative inputs; here every radicand is positive (, and ).
- The integral in is a Bochner integral ( by convention for non-integrable integrands; here the integrand almost surely takes finitely many values, so it is the genuine expectation).
- The conclusion is a non-strict inequality, and the comparator in the regret is the best single arm in hindsight.
Confirmed by the mission captain (proposal self-audit).