Which solutions could I use to solve a multi-armed "multi-bandit" problem?

Question

Problem

I have 66 slot machines. For each of them, I have 7 possible actions/arms to choose from. At each trial, I have to choose one of 7 actions for each and every one of the 66 slots. The reward depends on the combination of these actions, but the slots are not equal, that is, pulling the same arm for different slots gives different results. I do not care about an initial state or feature vector, as the problem always starts from the same setting (it is not contextual). My reward depends on how I pull one of the 7 arms of all of the 66 bandits simultaneously, where, as said, each slot has its own unique properties towards the calculation of the total reward. Basically, the action space is a one-hot encoded 66x7 matrix.

My solution

I ignored the fact that I do not care about a feature vector or state and I treated the problem using a deep NN with a basic policy-gradient algorithm, where I increase directly the probability of each action depending on the reward I get. The state simply does not change, so the NN receive always the same input. This solution does work effectively in finding an approximately optimal strategy, however, it is very computationally expensive and something tells me I am overkilling the problem.

However, I do not see how I could apply standard solutions to MAB, such as epsilon-greedy. I need simultaneity between the different "slot machines", and, if I just take each possible permutation as a different action, in order to explore them with greedy methods, I get way too many actions (in the order of $10^{12}$). I have not found in the literature something similar to this multi-armed multi-bandit problem and I am clueless if anything like that has ever been considered - perhaps I am overthinking it and this can be somehow reduced to a normal MAB?

Answer 1

Although you can frame your problem as a bandit problem or RL, it has other workable interpretations. Critical information from your comments is that:

• Total reward is not a simple sum of all the results from 66 different machines. There are interactions between machines.

• Total reward is deterministic.

This looks like a problem in combinatorial optimisation. There are many possible techniques you can throw at this. Which ones work best will depend on how nonlinearities and dependence between choices on different machines affect the end results.

Best Case

With deterministic results, if changes between machines were completely isolated, you could search each machine in turn, because you can treat all other 65 components as a constant if you don't change their settings. That would be very simple to code and take $7 \times 66 = 462$ steps to find the optimimum result.

Worst Case

In the worst case, the dependencies are so strong and chaotic that there is essentially no predictable difference between changing a single machine's setting and all of them. Pseudo-random number generators and secure hashing functions have this property, as do many quite simple physical systems with feedback loops.

In the worst case, there will be a "magic setting" with best results, and only a brute force search through all combinations of levers will find it.

In order to apply any more efficient search method, you have to assume that the response to combinations of levers is not quite so chaotic.

How to Search?

It seems likely from your description, that the best search algorithm is going to be somewhere between simple machine-by-machine optimisation and an exhaustive global search. However, it is hard to tell just where on that spectrum it lies.

There are a few different ways to frame it as reinforcement learning. For instance, you could use current switch combination as state, and run 66 switch changes as an "episode".

I would suggest that genetic algorithms are a good match for this search task, assuming there is at least some local-only effect that means combining two good solutions is likley to result in a third good solution. Genetic algorithms don't need calculations for gradients, and fit nicely with discrete combinations. Your genome can simply be the 66 different switch positions, and the fitness rating your black box score for those positions.

Plenty of other combinatorial search algorithms are available. Enough to fill a book or two. One place you could look for inspiration is Clever Algorithms: Nature-Inspired Programming Recipes which is a free PDF.