can be found using the Q-learning algorithm [@watkins1992q], and the optimal policy is given by $\pi^*(s)=\arg\max_aQ^*(s,a)$.

After executing an action, the agent also observes a binary elimination signal $e(s,a),$ which equals $1$ if action $a$ may be eliminated in state $s$; that is, any optimal policy in state $s$ will never choose action $a$ (and $0$ otherwise). The elimination signal can help the agent determine which actions not to take, thus aiding in mitigating the problem of large discrete action spaces. We start with the following definitions:

Valid state-action pairs with respect to an elimination signal are state action pairs which the elimination process should not eliminate.

As stated before, we assume that the set of valid state-action pairs contains all of the state-action pairs that are a part of some optimal policy, i.e., only strictly suboptimal state-actions can be invalid.

Admissible state-action pairs with respect to an elimination algorithm are state action pairs which the elimination algorithm does not eliminate.

In the following section, we present the main advantages of action elimination in MDPs with large action spaces. Afterward, we show that under the framework of linear contextual bandits [@chu2011contextual], probability concentration results [@abbasi2011improved] can be adapted to guarantee 