Proof of Theorem 5.2, p.18:
ProvedStationaryBwK.ratio_minimizationadversarial-banditsbandits-with-knapsacksmartingalesonline-learningp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let , , and for . Then:
- for every ;
- if , is non-increasing on and non-decreasing on ;
- if , then ;
- for every ,
The guaranteed fraction of is for the unknown ; its worst case over is the competitive ratio of Theorem 5.2.
Differences from the source:
- reading: 'The above term is decreasing in x while x ≤ ρ/σc and increasing afterwards. This means that the minimizing x is ρ/σc, which proves the desired competitive ratio'; 'The theorem trivially holds if σc ≤ ρ' → clauses 2–4: monotonicity on (0, min{1, ρ/σc}] and [ρ/σc, 1] for σc > 0, the value f(ρ/σc) = ρ + σr(σc − ρ) when ρ ≤ σc, and the lower bound f ≥ ρ + σr(σc − ρ)⁺ on (0, 1]; reason: this is what the sentences assert on the domain x = T*/T ∈ (0, 1]; when σc < ρ the minimizer is x = 1, the 'trivial' case, and clause 4 covers it
- reading: decreasing / increasing → AntitoneOn / MonotoneOn (non-strict); reason: f is constant in x when σr = 0 or σr = 1 on the respective pieces, so strict monotonicity is false there; the minimization only needs the non-strict form
Preamble
import Mathlib
Formal statement
namespace StationaryBwK
/-- **The worst case over `x`** (Fikioris & Tardos, arXiv:2302.14686v2, proof of Theorem 5.2,
p.18, last display and the sentence after it). For `ρ ∈ (0, 1]`, `σr, σc ∈ [0, 1]` and
`f(x) = max{ρ, σc x} (1 + σr (1 − x)/x)` on `x ∈ (0, 1]`:
1. `f(x) = max{ρ + ρσr (1 − x)/x, σrσc + σc x (1 − σr)}`;
2. if `σc > 0`, `f` is decreasing while `x ≤ ρ/σc` and increasing afterwards;
3. if `ρ ≤ σc`, the minimizing value is `f(ρ/σc) = ρ + σr(σc − ρ)`;
4. `f(x) ≥ ρ + σr (σc − ρ)⁺` for every `x ∈ (0, 1]` (the competitive ratio of Theorem 5.2; the
case `σc ≤ ρ` is the one the proof calls trivial).
**Formalization Note.** "Decreasing"/"increasing" are `AntitoneOn`/`MonotoneOn` (non-strict),
on `(0, min{1, ρ/σc}]` and `[ρ/σc, 1]`. `(σc − ρ)⁺` is `max (σc − ρ) 0`. -/
theorem ratio_minimization (ρ σr σc : ℝ) (hρ₀ : 0 < ρ) (hρ₁ : ρ ≤ 1) (hσr₀ : 0 ≤ σr)
(hσr₁ : σr ≤ 1) (hσc₀ : 0 ≤ σc) (hσc₁ : σc ≤ 1) :
(∀ x ∈ Set.Ioc (0 : ℝ) 1,
max ρ (σc * x) * (1 + σr * (1 - x) / x) =
max (ρ + ρ * σr * (1 - x) / x) (σr * σc + σc * x * (1 - σr))) ∧
(0 < σc →
AntitoneOn (fun x : ℝ => max ρ (σc * x) * (1 + σr * (1 - x) / x))
(Set.Ioc 0 (min 1 (ρ / σc))) ∧
MonotoneOn (fun x : ℝ => max ρ (σc * x) * (1 + σr * (1 - x) / x))
(Set.Icc (ρ / σc) 1)) ∧
(ρ ≤ σc →
max ρ (σc * (ρ / σc)) * (1 + σr * (1 - ρ / σc) / (ρ / σc)) = ρ + σr * (σc - ρ)) ∧
(∀ x ∈ Set.Ioc (0 : ℝ) 1,
ρ + σr * max (σc - ρ) 0 ≤ max ρ (σc * x) * (1 + σr * (1 - x) / x)) := by sorry
end StationaryBwK
Source
G. Fikioris and É. Tardos, Approximately Stationary Bandits with Knapsacks, arXiv:2302.14686v2 [cs.LG] (preprint, 8 Jul 2023), https://arxiv.org/abs/2302.14686v2, proof of Theorem 5.2, p.18, last display and the two sentences after it
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.