§3.2, p. 43 — -nets of subsets of the unit ball have size at most
ProvedFoundationsRL.LinUCB.epsilon_net_unit_ballbandit-algorithmscovering-numbersp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let and . Then there is a finite set with
such that every is within Euclidean distance of some .
This is the covering estimate behind the extension of Proposition 7 to infinite classes: at it gives .
Differences from the source:
- reading: "of size at most " → an explicit bound for ; reason: the use requires a constant of the form , and no bound of this form can hold for large on a nonempty set.
- encoding: Euclidean distance → ; reason: vectors are
Fin d → ℝwith the dot product. - reading: an -net of → a net ; reason: the net is used to discretize the class, so its functions must stay in the class and in .
Preamble
import Mathlib open Matrix
Formal statement
namespace FoundationsRL.LinUCB
/-- The covering bound of §3.2 (Foster & Rakhlin, *Foundations of Reinforcement Learning and Interactive Decision Making*, arXiv:2312.16730v1, p. 43): every `Θ ⊆ B^d_2(1)` has, for `ε ∈ (0, 1]`, an `ε`-net
`N ⊆ Θ` of size at most `(3/ε)^d`, the book's "of size at most `O(ε^{−d})`".
**Formalization Note.** The book leaves the constant in `O(ε^{−d})` open. It must be of the form
`C^d`, for `log|N| ≲ d log T` at `ε ∼ 1/T`, so an explicit base is stated. The net lies inside `Θ`,
which keeps its functions in the class and in `[0, 1]`. -/
theorem epsilon_net_unit_ball {d : ℕ} (Θ : Set (Fin d → ℝ)) (hΘ : ∀ θ ∈ Θ, θ ⬝ᵥ θ ≤ 1)
(ε : ℝ) (hε0 : 0 < ε) (hε1 : ε ≤ 1) :
∃ N : Finset (Fin d → ℝ), (N : Set (Fin d → ℝ)) ⊆ Θ ∧ (N.card : ℝ) ≤ (3 / ε) ^ d ∧
∀ θ ∈ Θ, ∃ θ' ∈ N, (θ - θ') ⬝ᵥ (θ - θ') ≤ ε ^ 2 := by sorry
end FoundationsRL.LinUCB
Source
Foster & Rakhlin, Foundations of Reinforcement Learning and Interactive Decision Making, arXiv:2312.16730v1, §3.2, p. 43
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.