1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Are you perhaps doing a 0-order search which requires you to evaluate every choice? If you have the ability to parameterize the selection criteria analytically you could find the maxima faster using 1st or even 2nd-order methods.

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)$).

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.