In words, assum: weakened assumption assumes that there exists an optimal policy that is stationary and proper.
If such an optimal policy is not unique, we can take \(T_\star \)  to be the minimum over all such policies. Notice that the first part of assum: weakened assumption is sufficient for all our algorithms to work, though the regret bound has a \(\ln T\)  factor, which could be unbounded. That is why in the main text we introduced the stronger assum: proper and upper bound \(T\)  by the order of \(KT_{\max }\) . Below we show that with the additional second part of assum: weakened assumption and the algorithmic trick introduced in [1]}, the \(T_{\max }\)  dependency can be replaced by \(T_\star \) .
