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.


  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)


1 Answer 1


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.

  • $\begingroup$ 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. $\endgroup$
    – Eponymous
    Commented Feb 25, 2016 at 2:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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