App. B, p. 10 — Σ_k Σ_i √(1(N_{t_k} > τ)/N_{t_k}) ≤ √(8SAmτ) (corrected from √(2SAT))
ProvedPosteriorSamplingRL.Regret.appB_sqrt_count_boundcountingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1reinforcement-learning
Let be any sequence of state–action pairs as above, with visit counts before episode , and write . Then for every number of episodes , with steps,
With the small-count bound, this controls and yields the rate of Theorem 1.
Formalization Note The page prints , which is false: its chain bounds by and then uses , while the integral equals . With one state–action pair and the left side is about , e.g. at . Correcting the integral in the page's own chain gives , which is stated. The statement is deterministic.
Preamble
import Mathlib import Definitions.Def_PosteriorSamplingRL_Regret_Confidence
Formal statement
namespace PosteriorSamplingRL.Regret
/-- App. B (arXiv:1306.0940v5, p. 10), the square-root sum, with the page's `√(2SAT)` corrected
to `√(8SAT)`, `T = mτ`: for any sequence of state–action pairs (episode `k`, step `j`),
`∑_{k=1}^m ∑_{i=1}^τ √(1(N_{t_k} > τ) / N_{t_k}) ≤ √(8 S A m τ)`, where
`N_{t_k} = N_{t_k}(s_{k,i}, a_{k,i})`. -/
theorem appB_sqrt_count_bound (S A τ : ℕ) (sa : ℕ → Fin τ → Fin S × Fin A) (m : ℕ) :
∑ k ∈ Finset.range m, ∑ j : Fin τ,
(if τ < visitCount sa k (sa k j) then 1 / Real.sqrt (visitCount sa k (sa k j)) else 0)
≤ Real.sqrt (8 * (S : ℝ) * A * ((m : ℝ) * τ)) := by sorry
end PosteriorSamplingRL.Regret
Source
arXiv:1306.0940v5, App. B, p. 10, square-root sum
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.