
where \(\tilde{\iota }_{T,B,\delta } \triangleq (\ln (SA/\delta ) + \ln \ln (BT))\times \ln T\) .Technically, the total number of steps \(T\)  is a random quantity but can be replaced by \(KT_{\max }\)  with high probability if desired.

The proof of thm: main for mixed case can be found in app: general upper. thm: main for mixed case generalizes previous works on near-optimal near-horizon-free regret bounds for RL [1]}, [2]}, [3]}. Specifically, with a closer look into their analysis, one can find that their analysis leads to a regret bound that depends on the magnitude of \(\sum _{i\in \text{episode}} |r(s_i,a_i)|\) , which can be much larger than \(|\sum _{i\in \text{episode}} r(s_i,a_i)|\)  if the rewards have mixed signs. To address this issue, we develop new analysis techniques to get a near-horizon-free regret bound, which only scales with \(|\sum _{i\in \text{episode}} r(s_i,a_i)|\) .
Other than this, the rest of the proofs are similar to those in [3]} with simplifications. Unlike prior work, our analysis does not involve the intricate “high-order expansion” as seen in [1]}, [2]}, [3]}, the possibility of which is hinted by [8]}.
