We consider algorithms that compute a deterministic policy \(\pi _k: \mathcal {S}\times [H]\rightarrow \mathcal {A}\)  at the start of each episode \(k\in [K]\) . One can show that if an optimal policy exists, there is a deterministic optimal policy [1]}. The agent samples feedback from the environment by: selecting an action, \(a_{h}^{k} = \pi _{k}(s_{h}^{k}, h)\) ; receiving a reward, \(r_{h}^{k} = R_{h}(s_{h}^{k}, a_{h}^{k})\) ; and transitioning to the next state, \(s_{h + 1}^{k} \sim P_{h}(\cdot \vert s_{h}^{k}, a_{h}^{k})\) ; for each \(h = 1, \cdots ,H\) .
