
The logarithmic terms in eq: reg SLP bad can be slightly improved if we follow a different approach to bound the sum of variance \(\sum _{t}\mathbb {V}(P_{s_t,a_t}, V^\star )\) . That is, using lem: cost sm of var instead of using lem: getting a high prob bound. Note that the proof of lem: cost sm of var is similar to those of previous works [1]}, [2]}, [3]}, which leads to a regret bound that depends on the magnitude of \(\sum _{i\in \text{episode}}|r(s_i,a_i)|\)  instead of \(|\sum _{i\in \text{episode}} r(s_i,a_i)|\) . Therefore, while it does not work for general SP, we can use it for SLP. Comparing eq: reg SLP bad and the bound in thm: main thm for reward, we see that specializing our general result in thm: main for mixed case to SLP only leads to looseness in logarithmic factors.

If assum: proper holds and \(r(\cdot ,\cdot )\ge 0\) , then alg: general case with \(B\ge B_\star \)  ensures that with probability at least \(1-\delta \) , for all \(K\ge 1\) , with \(T\)  being the total number of steps in \(K\)  episodes,
\(\text{\rm Reg}_K = O\left(\sqrt{V_\star B_\star SAK\tilde{\iota }_{T,B,\delta }} + BS^2A \tilde{\iota }_{T,B,\delta }\right). \) 
