Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Exact expected paid loss under two-point feedback

Definition
OrderedExperts_Supplement_twoExpLoss

by iris · Nov 18, 2026 · Mathlib 0df444a (Lean v4.33.1)

bandit-algorithmsonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1regret-bounds

For a randomized two-point learner, an oblivious recommendation sequence, an oblivious loss sequence, and a protocol-specific observation rule, the expected cumulative paid loss is defined recursively. On each round the learner pays the average of the losses at its two queried active recommendations, receives only the prescribed observation, and continues from the enlarged history.

This gives the expectation used in all two-point upper and lower bounds.

Formalization Note Rounds are 0-based. Every expectation is an exact finite sum over conditional pair laws, so there is no measurability, integrability, or default-value case.

Definition code
import Definitions.Def_OrderedExperts_Supplement_TwoPointPolicy
import Definitions.Def_OrderedExperts_chainPt

open Finset

namespace OrderedExperts.Supplement

/-- **Exact expected paid loss of a two-point learner.**
Zuo, *Online Learning with Ordered Experts (via Two-point Feedback)*, STOC 2027 submission
(held version), Sec. 2.2, pp. 5--6.

The learner pays the average loss of the two queried active recommendations.  The recursion sums
over the learner's conditional pair law and appends only the observation supplied by the feedback
protocol.

**Formalization Note.** Rounds are zero-based.  Since each conditional law is finite, this is the
expectation exactly and has no integrability or measurability default case. -/
noncomputable def twoExpLoss {A : Type*} [LinearOrder A] [OrderBot A] {n : ℕ} {O : Type*}
    (P : TwoPointPolicy A n O) (rec : ℕ → Fin n → A) (loss : ℕ → A → ℝ)
    (observe : ℕ → ℕ → ℕ → O) :
    ℕ → ℕ → List ((Fin n → A) × ℕ × ℕ × O) → ℝ
  | 0, _, _ => 0
  | k + 1, t, h =>
      ∑ a ∈ Icc 1 (chainSize rec t), ∑ b ∈ Icc 1 (chainSize rec t),
        P.mass (rec t) h a b *
          ((loss t (chainPt rec t a) + loss t (chainPt rec t b)) / 2 +
            twoExpLoss P rec loss observe k (t + 1)
              (h ++ [(rec t, a, b, observe t a b)]))

end OrderedExperts.Supplement
Source
Zuo, Online Learning with Ordered Experts (via Two-point Feedback), STOC 2027 submission (held version), Sec. 2.2, pp. 5–6

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me