The question then is how to show that optimism holds along the way. Because we start from \(B=1\)  and only increases \(B\)  when we are sure that \(B<B_\star \) , one might suspect that the bonus term \(b_t\)  defined through \(B\)  is insufficient at the beginning, and the optimism might fail. Because of this, [1]} and [2]} bound the regret in the \(B<B_\star \)  regime by a term linear in \(K\) . However, one key observation in the analysis is that the original purpose of the bonus term is to compensate the deviation of \((P_{s_t,a_t}-\bar{P}_t)V_t\) , where \(|V_t|\le B\)  by our algorithm. Since \(V_t\)  is history-dependent, a common trick in the analysis [3]}, [4]} is to replace \(V_t\)  by \(V^\star \)  and bound the deviation of \((P_{s_t,a_t}-\bar{P}_t)V^\star \)  using Freedman's inequality, for which a bonus term defined through \(B_\star \)  is required. To deal with our case, instead of replacing \(V_t\)  by \(V^\star \) , we replace it by \(V_{[B]}^{\star }\triangleq \max \lbrace -B, V^\star \rbrace \)  and use Freedman's inequality on \((P_{s_t,a_t}-\bar{P}_t)V_{[B]}^{\star }\) , for which a bonus term defined through \(B\)  suffices. We can further connect \(V^\star _{[B]}\)  back to \(V^\star \)  using the property \(V^\star _{[B]}\ge V^\star \) . The details are provided in lem: MVP for cost, where we show that with high probability, \(Q_{t}(s,a)\ge Q^\star (s,a)\)  holds for all \(t,s,a\) , even if \(B\)  is smaller than \(B_\star \)  along the learning process. The formal guarantee of our algorithm is given by the following theorem, with proof deferred to app: upper bound SSP.


alg: cost case parameter free guarantees for SSP problems that with probability at least \(1-O(\delta )\) , \(\text{\rm Reg}_K=\tilde{O}(\sqrt{V_\star B_\star SAK} + B_\star S^2A)\) .
