Theorem 1, p. 12 — under covariate diversity the two-armed Greedy Bandit has R_T ≤ A log T + A + 160 b_max x³_max d/λ₀ + 2x_max b_max
ProvedMostlyExplorationFree.GreedyBandit.theorem_1contextual-banditcovariate-diversitygreedy-algorithmp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1regret
Consider the Greedy Bandit (Algorithm 1) on the two-armed linear contextual bandit in dimension , with -sub-Gaussian noise (), under Assumption 1 (contexts bounded by and parameters by in ), Assumption 2 (margin condition with constant ) and Assumption 3 (covariate diversity with constant ). Let
Then for every horizon the cumulative expected regret satisfies
In particular : an algorithm that never explores attains the optimal logarithmic regret rate of the two-armed contextual bandit once the context distribution is diverse enough. This is the paper's main result.
Formalization Note
- The bound is the one the proof establishes (p. 42). The printed display (3) also multiplies by , which the proof never produces; whenever (every with ) the bound stated here is at least as strong as (3). The consequence "" follows at once from for and is not restated.
- is assumed because divides by (the paper's own range needs it); because divide by .
- Noise sub-Gaussianity is two-sided and the context law need not have a density; see the model definition.
Preamble
import Mathlib import Definitions.Def_MostlyExplorationFree_GreedyBandit_Model open Matrix MeasureTheory ProbabilityTheory
Formal statement
namespace MostlyExplorationFree.GreedyBandit
theorem theorem_1 {Ω : Type*} [MeasurableSpace Ω] (P : Measure Ω) {d : ℕ} (hd : 2 ≤ d)
(μ : Measure (Fin d → ℝ)) (X : ℕ → Ω → Fin d → ℝ) (ε : Fin 2 → ℕ → Ω → ℝ)
(W : ℕ → Ω → Bool) (σ : ℝ) (hσ : 0 < σ) (β : Fin 2 → Fin d → ℝ)
(xmax bmax C0 lam0 : ℝ)
(hmodel : IsGreedyModel P μ X ε W σ) (hA1 : ParameterSet μ β xmax bmax)
(hA2 : MarginCondition μ β C0) (hA3 : CovariateDiversity μ lam0)
(T : ℕ) (hT : 3 ≤ T) :
regret β X ε W P T
≤ 128 * C0 * Cbar d * xmax ^ 4 * σ ^ 2 * d * Real.log d ^ (3 / 2 : ℝ) / lam0 ^ 2
* Real.log T
+ (128 * C0 * Cbar d * xmax ^ 4 * σ ^ 2 * d * Real.log d ^ (3 / 2 : ℝ) / lam0 ^ 2
+ 160 * bmax * xmax ^ 3 * d / lam0 + 2 * xmax * bmax) := by sorry
end MostlyExplorationFree.GreedyBandit
Source
Bastani, Bayati & Khosravi, arXiv:1704.09011v8, p. 12, Theorem 1 and display (4) (bound in the form proved on p. 42, Appendix C)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.