# Time efficient way to implement Multi-Armed-Bandits?

I'm doing a research on Multi-Armed Bandit (MAB) problem with approx. 1 million arms. In contrast, the number of iterations is of course much larger, about 10-20 million.

Most MAB-algorithms require an argmax operator (argmax of the action space) that has to be executed in each iteration in order to select the current arm (which maximizes a given selection criterion). Regardless of the chosen programming language for implementation, this procedure/ this argmax operator over the entire action space (1 million arms) is very time-consuming.

Does anyone have some ideas on how to implement MAB algorithms in a time-efficient way?

Store the values in a priority queue. Typically, in each iteration you will update the value for only a single arm, so you need to change the key of a single value in the priority queue, which can be done in $$O(\log n)$$ time, where $$n$$ is the number of arms. You can also find the argmax in $$O(\log n)$$ time.
Also, along the lines of what D.W said, but even faster, if you use a max-heap as an implementation for the priority queue, you can actually get the max value in $$O(1)$$ (updating the "value" of each arm, would be $$O(\lg N)$$).