App. B, p. 10 — Σ_k Σ_i 1(N_{t_k}(s,a) ≤ τ) ≤ 2τSA
ProvedPosteriorSamplingRL.Regret.appB_small_count_boundcountingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pigeonholereinforcement-learning
Let , , , be any sequence of state–action pairs in with , , and let be the number of occurrences of in the episodes before . Then for every ,
Each pair can be visited in an episode that starts with at most earlier visits at most times in total. The bound controls the part of the width sum in which the counts are still small.
Formalization Note The page says "fewer than 2τ times", but the count can equal (one pair visited times in each of two episodes); the display's is what is stated. The statement is deterministic: it holds for every visit sequence, in particular for the pairs visited by a PSRL run.
Preamble
import Mathlib import Definitions.Def_PosteriorSamplingRL_Regret_Confidence
Formal statement
namespace PosteriorSamplingRL.Regret
/-- App. B (arXiv:1306.0940v5, p. 10), first count: for any sequence of state–action pairs
`(s_{k,j}, a_{k,j})` (episode `k`, step `j`), with `N_{t_k}(s, a)` the number of visits before
episode `k`, `∑_{k=1}^m ∑_{i=1}^τ 1(N_{t_k}(s_{k,i}, a_{k,i}) ≤ τ) ≤ 2τSA`. -/
theorem appB_small_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 : ℝ) else 0)
≤ 2 * (τ : ℝ) * S * A := by sorry
end PosteriorSamplingRL.Regret
Source
arXiv:1306.0940v5, App. B, p. 10, first count
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.