3
$\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. The pulls for a given arm are IID.

Differences:

  1. I want to maximize the maximum reward. I do not care about the sum of rewards.
  2. Each arm has a list of the results of all of previous pulls attached to it.
  3. I access the arms sequentially. I can only access an arm's previous pulls while accessing that arm. After each new pull, I must decide whether to pull again or to continue to the next arm. A pull costs 1. The cost of going to the next arm is C, a strictly positive real number. (C is probably greater than 1, but I'll need to measure that).
  4. Each time I reach my last arm, I can start again, but for each pull I made, there will be one new arm with one pull recorded.
  5. I have a notebook in which I can write down a little information to carry from arm to arm.
  6. I am part of a small team. After each pass through the arms, we can confer and update our notebooks. Then we divide up the arms evenly among ourselves and start again.
  7. There is a limited budget. When we have spent everything, we stop.

Has this (or a similar) problem been studied? Similar problems could be quite helpful: for example, problems that ignore the sequential nature, the increasing number of arms, the costs, and/or the team. However, keeping only the maximum reward rather than all rewards is essential.

I made another question out of one useful simplification.

edit Clarified costs because of a comment by armen-aghajanyan

$\endgroup$
5
  • 1
    $\begingroup$ Could you please clarify what you mean by: "The cost of going to the next arm is C times the cost of a pull". Is the cost of the pull a separate constant? $\endgroup$ Dec 16, 2015 at 17:23
  • $\begingroup$ @ArmenAghajanyan I modified the description to clarify costs. The pull is a different constant, but since those are the only two budgetary factors, I can just divide the budget by the cost of a pull. So, in the description, I just set the cost of a pull to 1. $\endgroup$
    – Eponymous
    Dec 16, 2015 at 21:19
  • $\begingroup$ So is the goal to maximize the reward while minimizing the total cost? $\endgroup$ Dec 17, 2015 at 2:17
  • $\begingroup$ @ArmenAghajanyan The goal is to maximize the reward on a fixed budget. I find problems of the form "maximize x while minimizing y" to be ill-defined - you always have to specify some fudge factor for the tradeoff. I'd also be interested in maximizing the reward in a fixed number of passes through all the arms. $\endgroup$
    – Eponymous
    Dec 17, 2015 at 14:05
  • $\begingroup$ Thank you. I am currently working on a solution in my free time. I'll get back to you as soon as possible. $\endgroup$ Dec 18, 2015 at 3:50

0

Your Answer

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

Browse other questions tagged or ask your own question.