# Maximum Multi-armed Bandit

My problem is similar to the multi-armed bandit problem in that I need to allocate "pulls" between n options, each giving a stochastic real reward and the pulls for a given arm are IID.

Differences:

1. I only get to keep the maximum reward, not all rewards
2. I have a (usually short) history of rewards for each arm
3. I must allocate k pulls all at once in advance and do not get to change them as they are made.

Has this problem been studied? (Note that this is a simplification of another question I wrote)

I think (but I'm not in 100% sure) I have seen something similar to your problem and it was a simple algorithm playing GO or chess. I would recommend you to search for something like: UCT: Bandit based Monte-Carlo planning in games by Levente Kocsis and Csaba Szepesvari. In Bandit based Monte-Carlo Planning 9th reference points to UCT.

Ad. 1: Maximum reward would be an ultimate win. Probably you won't have game states to expand, but you would rather stay in a single state (that's not a problem) and try to make single optimal move. The more rewarding a particular arm is, the more often it will be used.

Ad. 2: The history for each arm is stored as an oridnary fraction.

Ad. 3: That could be a bit problematic. The decision of which arm to try in next move is based on the fractions mentioned above. If k is not so big, it would be fairly possible to make more or less proper decisions in advance, but generally I think that should be impossible to decide how to make optimal moves in advance, because with each move we discover more knowledge about the game.

• k=1 is doable. But I pay a cost per group of k (proportional to the sum of all previous groups of k added to a fixed starting cost), so there is a tradeoff between size of group and information cost. However, this is a really good pointer. Thank you. Feb 25, 2016 at 2:32