Proof of Proposition 2, p. 44 — ξ_u, ξ_v ∈ PB(ξ̃, C_p) and ⟨ξ_u,U⟩ = (u−C)/(u+C) ≤ 1 = ⟨ξ_v,U⟩, ⟨ξ_v,V⟩ = (v−C)/(v+C) ≤ 1 = ⟨ξ_u,V⟩
ProvedLuoSunLiu.PLBLower.two_point_constructionlinear-banditslower-boundp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1perturbed-linear-bandit
Let have positive entries, let be two coordinates with , , and let satisfy and . Let be the two actions and two parameters of the two-point construction, and . Then
- and , i.e. and ;
- the inner products are
So under the action is optimal and loses ; under the action is optimal and loses . This is the first step of the proof of the lower bound.
Formalization Note The statement is written with and . It holds for any two distinct coordinates; the paper's choice of the smallest and second smallest entries is only needed in the per-period bound. The hypothesis is the paper's implicit nonnegativity of the perturbation constant.
Preamble
import Mathlib import Definitions.Def_LuoSunLiu_PLBLower_Model import Definitions.Def_LuoSunLiu_PLBLower_TwoPoint
Formal statement
namespace LuoSunLiu.PLBLower
/-- Two-point construction (proof of Proposition 2, p. 44). With `C = C_p / 2`, i.e. `C_p = 2C`:
`ξ_u, ξ_v ∈ PB(ξ̃, C_p)`, `⟨ξ_u, U⟩ = (u − C)/(u + C) ≤ 1 = ⟨ξ_v, U⟩` and
`⟨ξ_v, V⟩ = (v − C)/(v + C) ≤ 1 = ⟨ξ_u, V⟩`, where `u = ξ̃_{ju}`, `v = ξ̃_{jv}`. -/
theorem two_point_construction {d : ℕ} (ξc : Fin d → ℝ) (hpos : ∀ i, 0 < ξc i)
(C : ℝ) (hC0 : 0 ≤ C) (ju jv : Fin d) (hne : ju ≠ jv)
(hCu : C < ξc ju) (hCv : C < ξc jv) :
xiU ξc C ju jv ∈ PB ξc (2 * C) ∧ xiV ξc C ju jv ∈ PB ξc (2 * C) ∧
xiU ξc C ju jv ⬝ᵥ actU ξc C ju = (ξc ju - C) / (ξc ju + C) ∧
(ξc ju - C) / (ξc ju + C) ≤ 1 ∧
xiV ξc C ju jv ⬝ᵥ actU ξc C ju = 1 ∧
xiV ξc C ju jv ⬝ᵥ actV ξc C jv = (ξc jv - C) / (ξc jv + C) ∧
(ξc jv - C) / (ξc jv + C) ≤ 1 ∧
xiU ξc C ju jv ⬝ᵥ actV ξc C jv = 1 := by sorry
end LuoSunLiu.PLBLower
Source
Luo, Sun and Liu, arXiv:2109.07340v2, App. A, proof of Proposition 2, p. 44
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.