that action elimination is correct in high probability. Finally, we prove that Q-learning coupled with action elimination converges.

Advantages in action elimination
--------------------------------

Action elimination allows the agent to overcome some of the main difficulties in large action spaces, namely: Function Approximation and Sample Complexity.

*Function Approximation:* It is well known that errors in the Q-function estimates may cause the learning algorithm to converge to a suboptimal policy, a phenomenon that becomes more noticeable in environments with large action spaces [@thrun1993issues]. Action elimination may mitigate this effect by taking the $\max$ operator only on valid actions, thus, reducing potential overestimation errors. Another advantage of action elimination is that the Q-estimates need only be accurate for valid actions. The gain is two-fold: first, there is no need to sample invalid actions for the function approximation to converge. Second, the function approximation can learn a simpler mapping (i.e., only the Q-values of the valid state-action pairs), and therefore may converge faster and to a better solution by ignoring errors from states that are not explored by the Q-learning policy [@hester2017learning].

*Sample Complexity*: The sample complexity of the MDP measures the number of steps, during learning, in which the policy is not $\epsilon$-optimal 