2
$\begingroup$

This is the problem: I have 66 slot-machines and 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 slots 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 and so on. 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?

$\endgroup$
  • $\begingroup$ Could you clarify whether and how rewards from one machine are dependent on levers pulled on different machines? Is there any kind of rule or constraint? If there are no constraints, and slot machine 65 can depend arbitrarily (at the setiup/design) on slot machine 3's lever or result, then you really do have one combined giant machine with $7^{66}$ actions here. If there are some rules or constraints - such as each machine actually produces an independent reward, but you cannot observe the rewards other than as a total sum, then there may be some good solutions. $\endgroup$ – Neil Slater Oct 29 '19 at 10:08
  • $\begingroup$ The reward comes out of a thermodynamic model (a black box) which needs as input 1 action (one of the 7 levers) for each building (the 66 machines). They are interdependendent in the sense that I only get the result of this combination out of the thermodynamic model, without knowing how and where one action correlated to the others. But I dont care about discovering this correlation, as my only concern is finding the best strategy overall - that is the best set of levers to pull at each machine. To be clear, the reward is unique, and I receive it once, when I pull a lever for each machine. $\endgroup$ – FS93 Oct 29 '19 at 11:16
  • $\begingroup$ To be more explicit: each lever regulate the thermal profile of my 66 buildings, each lever being one of 7 possible actions. After choosing one action for each building, I pass through the thermodynamic model which aggregates these inputs, does some more stuff and outputs the reward. There clearly is an interdependcy, indeed my simple policy gradient agent is able to exploit it to get high rewards, but I wonder - since there is not a context/feature vectore/state space - if there is a more suitable method than deep RL for solving this problem. $\endgroup$ – FS93 Oct 29 '19 at 11:23
  • $\begingroup$ Is the output stochasitic or deterministic? Does the exact same combination of all 66 levers result in the same total reward? $\endgroup$ – Neil Slater Oct 29 '19 at 13:23
  • $\begingroup$ Yes it does. No stochasticity is involved in the model. $\endgroup$ – FS93 Oct 29 '19 at 14:53
2
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks Neil. Genetic algorithms have indeed been tried in the past for a similar problem but with much poorer results than what I got with my simple PG. Let's say that I want to tackle it with RL: I did try to use as input features the position of the levers of the 66 machines as you suggest, however, I soon realized that giving this bit of information to the network was irrelevant. Now I have good results using a static initial state and then letting the deep NN trains as normal. $\endgroup$ – FS93 Oct 29 '19 at 16:28
  • $\begingroup$ In the solution you proposed, would I have to keep 65 switches the same while changing only one switch at the time, 66 times till the episode ends and then calculating the total reward, storing into memory the typical s,a,r,s' tuple in order to train the network? It is not clear to me how this could help, as I am now able to choose all the levers at the same time - wouldn't I slow down terribly the algorithm? Can you expand a bit more on this option? Thanks a lot for your help. $\endgroup$ – FS93 Oct 29 '19 at 16:30
  • $\begingroup$ @FS93: It might slow down the algorithm - that will depend on details of network architecture that yuo are already using. Given that your action preferences are currently arbitrary and could be trained direcly, I'd guess you have a very shallow network with "1" as an input and 66*7 weights, with softmax over each group of 7 to set the policy? I wouldn't really call that "deep" though or even technically a neural network, so it is not too clear. $\endgroup$ – Neil Slater Oct 29 '19 at 16:37
  • $\begingroup$ @FS93: The "best" solver for your problem is going to be determined empirically. I think you may still want to revisit GAs or at least some other combinatorial search methods, and check the implementation yourself so you understand whether it is a fair comparison. $\endgroup$ – Neil Slater Oct 29 '19 at 16:40
  • $\begingroup$ Well, at this moment I have one input layer of 66 (useless) then three dense layers 256,512,512 and then 66 outputs each with a softmax layer with 7 units and categorical cross-entropy as loss function. I choose action based on each of these 66 softmax output layers, and they get updated all at once given the total reward (simply more reward = higher probability for that action). $\endgroup$ – FS93 Oct 29 '19 at 16:40

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.