[@kakade2003sample]. Assume that there are $A'$ actions that should be eliminated and are $\epsilon$-optimal, i.e., their value is at least $V^*(s)-\epsilon$. According to lower bounds by [@lattimore2012pac], We need at least $\epsilon^{-2}(1-\gamma)^{-3}\log 1/\delta$ samples per state-action pair to converge with probability $1-\delta$. If, for example, the eliminated action returns no reward and doesn’t change the state, the action gap is $\epsilon=(1-\gamma)V^*(s)$, which translates to ${V^*(s)}^{-2}(1-\gamma)^{-5}\log1/\delta$ ’wasted’ samples for learning each invalid state-action pair. For large $\gamma$, this can lead to a tremendous number of samples (e.g., for $\gamma=0.99,\enspace (1-\gamma)^{-5}=10^{10}$). Practically, elimination algorithms can eliminate these actions substantially faster, and can, therefore, speed up the learning process approximately by $A/A'$ (such that learning is effectively performed on the valid state-action pairs).

Embedding the elimination signal into the MDP is not trivial. One option is to shape the original reward by adding an elimination penalty. That is, decreasing the rewards when selecting the wrong actions. Reward shaping, however, is tricky to tune, may slow the convergence of the function approximation, and is not sample efficient (irrelevant actions are explored). Another option is to design a policy that is optimized by interleaved policy gradient updates on the two signals, maximizing the reward and 