Theorem 3.1 — under SBAR(J), Regret(z,T,PEGE) ≤ a₁(‖z‖ + 1/‖z‖)r√T and Risk(T,PEGE) ≤ a₂ r√T
ProvedLinParamBandits.PEGE.pege_regret_boundbayes-risklinear-banditp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1regret
This is the main upper bound for the Phased Exploration and Greedy Exploitation policy.
- Let . There is a constant , depending only on , such that for every dimension , every arm set , error laws and exploration arms satisfying Assumption 1 with these constants and the SBAR() condition, every greedy rule, every and every ,
- Let in addition . There is a constant , depending only on , such that for every such , instance and greedy rule, every prior on with and , and every ,
Together with the lower bound of Theorem 2.1 this shows that PEGE attains the optimal order for arm sets with smooth best arm response, such as the unit sphere.
Formalization Note The constants are chosen before the dimension, the arm set, the error laws, the exploration arms, the greedy rule, the prior, and ; a constant allowed to depend on or on the instance would make the statement trivial, since the regret never exceeds . The moments of are lower Lebesgue integrals: is when charges the origin. Regret and risk take values in , so the bounds also assert finiteness.
Preamble
import Mathlib import Definitions.Def_LinParamBandits_PEGE_Model open MeasureTheory ProbabilityTheory
Formal statement
namespace LinParamBandits.PEGE
/-- Theorem 3.1 (Regret and Risk Under the Greedy Policy), Rusmevichientong, Tsitsiklis,
arXiv:0812.3465v2, p. 15. Under Assumption 1 and SBAR(`J`):
1. there is a positive constant `a₁`, depending only on `σ₀, ū, λ₀, J`, such that for any
`z ∈ ℝ^r \ {0}` and `T ≥ r`, `Regret(z, T, PEGE) ≤ a₁ (‖z‖ + 1/‖z‖) r √T`;
2. if moreover `E[‖Z‖] ≤ M` and `E[1/‖Z‖] ≤ M` for every `r ≥ 2`, there is a positive constant `a₂`,
depending only on `σ₀, ū, λ₀, J, M`, such that for any `T ≥ r`, `Risk(T, PEGE) ≤ a₂ r √T`.
The constants are chosen before the dimension `r`, the arm set, the error laws, the exploration
arms, the tie-breaking rule, the prior, `z` and `T`. -/
theorem pege_regret_bound :
(∀ σ₀ ū lam₀ J : ℝ, 0 < σ₀ → 0 < ū → 0 < lam₀ → 0 < J →
∃ a₁ : ℝ, 0 < a₁ ∧
∀ (r : ℕ), 2 ≤ r →
∀ (𝒰 : Set (LinParamBandits.LowerBound.Vec r)) (ν : LinParamBandits.LowerBound.Vec r → ProbabilityMeasure ℝ) (b : Fin r → LinParamBandits.LowerBound.Vec r)
(g : ℕ → LinParamBandits.LowerBound.Vec r → LinParamBandits.LowerBound.Vec r),
Assumption1 𝒰 ν b σ₀ ū lam₀ → SBAR 𝒰 J → GreedySelector 𝒰 g →
∀ (z : LinParamBandits.LowerBound.Vec r), z ≠ 0 → ∀ (T : ℕ), r ≤ T →
regret 𝒰 ν b g z T ≤ ENNReal.ofReal (a₁ * (‖z‖ + 1 / ‖z‖) * r * Real.sqrt T)) ∧
(∀ σ₀ ū lam₀ J M : ℝ, 0 < σ₀ → 0 < ū → 0 < lam₀ → 0 < J → 0 < M →
∃ a₂ : ℝ, 0 < a₂ ∧
∀ (r : ℕ), 2 ≤ r →
∀ (𝒰 : Set (LinParamBandits.LowerBound.Vec r)) (ν : LinParamBandits.LowerBound.Vec r → ProbabilityMeasure ℝ) (b : Fin r → LinParamBandits.LowerBound.Vec r)
(g : ℕ → LinParamBandits.LowerBound.Vec r → LinParamBandits.LowerBound.Vec r),
Assumption1 𝒰 ν b σ₀ ū lam₀ → SBAR 𝒰 J → GreedySelector 𝒰 g →
∀ (μ : Measure (LinParamBandits.LowerBound.Vec r)), IsProbabilityMeasure μ →
∫⁻ z, ‖z‖ₑ ∂μ ≤ ENNReal.ofReal M → ∫⁻ z, ‖z‖ₑ⁻¹ ∂μ ≤ ENNReal.ofReal M →
∀ (T : ℕ), r ≤ T →
risk μ 𝒰 ν b g T ≤ ENNReal.ofReal (a₂ * r * Real.sqrt T)) := by sorry
end LinParamBandits.PEGE
Source
Rusmevichientong, Tsitsiklis, Linearly Parameterized Bandits, arXiv:0812.3465v2, Theorem 3.1, p. 15
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.