4
$\begingroup$

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)

Improve this question
$\endgroup$
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\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
    Feb 25 '16 at 2:32

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.