Equation (3.1) — the fixed-point equation always has a solution in
ProvedCalibeatBandit.eq_3_1_solvablebandit-feedbackcalibeatingonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1swap-regret
Let , let be column-stochastic matrices and . Then there is a probability vector with
This guarantees that the learner of Algorithm 1 can always choose a mixed strategy satisfying (3.1); the map maps the simplex into itself.
Formalization Note is Pi.single J 1, is the identity matrix.
Differences from the source:
- generalization: the algorithm's and column-stochastic → every and all column-stochastic ; reason: the paper's Brouwer argument uses only these properties; the algorithm's quantities are instances
- encoding: actions →
Fin K; reason: a relabelling
Preamble
import Mathlib import Definitions.Def_CalibeatBandit_IsColStochastic set_option autoImplicit false open MeasureTheory Matrix
Formal statement
namespace CalibeatBandit
/-- **Equation (3.1) always has a solution** (§3 "Choosing a mixed strategy", p.9).
For a mixing weight `λ ∈ [0, 1]`, column-stochastic `M^SR`, `M^Rec` and an action `J`, there is a
mixed strategy `p ∈ Δ(𝒜)` with `(I − λ M^SR) p = (1 − λ) M^Rec e_J`.
Hartline, Wang, Wu, *Calibeating Bandit Advice* (manuscript, sha256 a65ccb08…), §3, eq. (3.1) and the paragraph after (3.2), p.9.
**Formalization Note.** `e_J` is `Pi.single J 1`; `I` is the identity matrix `1`. The paper
states the claim for the algorithm's `λ_t` and `M^a_t`; it is stated here for every
`λ ∈ [0, 1]` and all column-stochastic matrices, which is what its Brouwer argument shows. -/
theorem eq_3_1_solvable {K : ℕ} (lam : ℝ) (hlam0 : 0 ≤ lam) (hlam1 : lam ≤ 1)
(MSR MRec : Matrix (Fin K) (Fin K) ℝ) (hSR : IsColStochastic MSR)
(hRec : IsColStochastic MRec) (J : Fin K) :
∃ p : Fin K → ℝ, IsProbVec p ∧
(1 - lam • MSR) *ᵥ p = (1 - lam) • (MRec *ᵥ Pi.single J 1) := by sorry
end CalibeatBandit
Source
Hartline, Wang, Wu, Calibeating Bandit Advice (manuscript, STOC 2027 submission, sha256 a65ccb0880e6e4698eee1717d9a7121019b84a5ebcb4dfaa2e1614dbd3de0b44), §3, eq. (3.1) and the paragraph after (3.2), p.9 (PDF 9)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.