only admissible state-action pairs and chooses the best action in the next state from its admissible actions. We allow the base Q-learning algorithm to be any algorithm that converges to $Q^*$ with probability $1$ after observing each state-action infinitely often.

If the elimination is done based on the concentration bounds of the linear contextual bandits, we can ensure that Action Elimination Q-learning converges, as can be seen in Proposition \[prop:convergenceProp\] (See Appendix A for a full proof).

[prop]{}[convergenceProp]{} \[prop:convergenceProp\] Assume that all state action pairs $(s,a)$ are visited infinitely often unless eliminated according to $\hat{\theta}_{t-1,a}^Tx(s)-\sqrt{\beta_{t-1}(\tilde{\delta})x(s)^T\bar{V}_{t-1,a}^{-1}x(s)}>\ell$. Then, with a probability of at least $1-\delta$, action elimination Q-learning converges to the optimal Q-function for any valid state-action pairs. In addition, actions which should be eliminated are visited at most $T_{s,a}(t)\le 4\beta_t/\br{u-\ell}^2+1$ times.

Notice that when there is no noise in the elimination signal ($R=0$), we correctly eliminate actions with probability 1, and invalid actions will be sampled a finite number of times. Otherwise, under very mild assumptions, invalid actions will be sampled a logarithmic number of times.

Method
======

Using raw features like *word2vec*, directly for control, results in exhaustive computations. Moreover, raw features are typically not realizable, i,.e., the assumption that 