Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning
ℙ({ℰT1(λ)}C)\displaystyle\mathbb{P}(\{\mathcal{E}^{1}_{T}(\lambda)\}^{C}) ≤∑s,aℙ(∃t∈[1,T],:KLM^t|M(s,a) β1(Nt(s,a),λ)Nt(s,a))\displaystyle\leq\sum_{s,a}\mathbb{P}\left(\exists t\in[1,T],:{\rm KL}_{\hat{M}_{t}|M}(s,a) \frac{\beta_{1}(N_{t}(s,a),\lambda)}{N_{t}(s,a)}\right) =∑s,aℙ(∃t∈[1,T],:KLM^t|M(s,a)Nt(s,a) (S−1)log(e(1+Nt(s,...