The following proof follows the standard lower bound proof for multi-armed bandits [1]}. We create \(A\)  different instances of MDPs, where in each of them, the choice of the good action is different. We use \(\mathbb {P}_a\)  and \(\mathbb {E}_a\)  to denote the probability measure and the expectation under the instance where \(a\)  is chosen as the good action. We further introduce an instance where every action behaves the same and there is no good action. We use \(\mathbb {P}_\textrm {unif}\)  and \(\mathbb {E}_\textrm {unif}\)  to denote the probability and expectation under this instance.
