Similar to my other question Bandit-like setup but taking max reward over multiple heads?, I'm interested in situations like the Multi-Armed Bandit setup, except where the reward is aggregated a maximising way rather than a summation.

This question is similarly about an altered scenario where the per-round reward is the maximum of a set of choices, but it allows me more information than my previous one.

Imagine per 'round' I can sequentially choose up to $k$ of my $n$ options. My choice of next option can depend both on the result of the previous ones this round as well as the usual dependence on the entire history of plays to this point. After $k$ pulls, my reward is the maximum of the outcomes of those $k$. Then a new round begins. My overall reward is the sum over rounds.

Can you share with me any literature analysing performance and regret of solutions to this kind of problem, perhaps under additional assumptions? Or can you think of any appropriate heuristics or transformations of the problem which could lead to a well-performing solution?

As in the other question, potentially there is a treatment as a $\binom n k$-armed bandit while taking care of the correlations between these 'combo arms'.

An additional approach for this special case could be to treat the initial choice as if $k=1$ (i.e. any standard MAB algorithm), then treat subsequent choices also as $k=1$ MABs, but yielding 'incremental reward' of max(0, new_reward - current_best_reward). That would presumably require some special alteration to the reward estimation to zero out any reward mass below the 'current max'. But I haven't worked out how to do this appropriately yet and how it might interact with explore-exploit properties of existing algorithms.

As an illustrative example, I am a lone treasure-hunter. Every day the sea washes in junk or treasure to various of $n=100$ beaches and nearby islands. I have time to search $k=10$ beaches in order, but my pockets are only big enough to carry the single best thing I find! At the end of the day, the sea washes everything away. I take whatever best thing I found and add it to my treasure stash, and get ready for the next day. (I am not clever or rich enough to get bigger pockets. Travel time between beaches is fixed and I won't find anything better by searching the same beach multiple times on the same day.)

  • $\begingroup$ Hey Oly, I think I am missing some crucial part of the problem when reading it. I would assume that, in the spirit of the original bandit problem, different islands in your example behave like random variables with potentially different means, so the goal is to discover which islands are likely to give more cash and then focus on those later. Is this correct? If yes, then, clearly, the treasure hunter needs to model entire probability distributions of each island. If we have good loot already, we can only improve by going for high-risk high-reward islands, so knowing means is not enough $\endgroup$ Aug 20, 2021 at 17:03
  • $\begingroup$ @AleksejsFomins it sounds like you indeed grasp the problem. I agree, once an island has yielded something of value, an important consideration for subsequent islands is the estimated spread of their yields, as well as any central tendency. So a policy should take that into account. But, like in the standard MAB problem, there remains an issue of efficient exploration. $\endgroup$
    – Oly
    Aug 21, 2021 at 11:51
  • 1
    $\begingroup$ I see. Problem sounds very interesting, but also very hard. I'll post if I get any bright ideas. So far it seems that making progress without assumptions on the class of probability distributions each island is allowed to follow would be hard or even impossible, as there is no way to tell how close the estimated distribution after N samples is to the true distribution $\endgroup$ Aug 22, 2021 at 11:01
  • $\begingroup$ Thanks! Yes. I would certainly be interested in any solutions (or pointers or gestures) which leaned on further assumptions, for example boundedness or unimodality or subgaussian-ness or even Gaussian $\endgroup$
    – Oly
    Aug 22, 2021 at 22:22
  • $\begingroup$ I don't see an actual question here. What is it you want to know about this type of model? $\endgroup$
    – Ben
    Aug 24, 2021 at 4:13

1 Answer 1


I don't know any relevant paper discussing a similar scenario, but this is also not my main area of expertise.

If I understand you correctly, you have $n$ arms and can pull only $k \ll n$ of them at a time. Your reward is the maximum of the rewards of the $k$ explored arms. The rewards are accumulated over time, so you aim at the highest possible total reward.

Honestly, it doesn't sound that far from the basic case of the multi-armed bandit. In the standard multi-armed bandit, you pick the arm with the highest expected payoff (of course there is the exploration-exploitation trade-off to consider). In your case, you just need to pick the $k$ arms with the highest expected payoff instead of a single arm.

The question remains, how would you update the payoff history for the arms? Given your description, I can imagine two scenarios:

  • Either the reward that you observe is just the maximum of the $k$ arms and you are not able to observe the individual payoffs. In such a case, append the payoff history of all the $k$ arms with the same reward. This would make your payoff history noisy since you are not recording the exact rewards, but only an aggregate (max). In many statistical problems, you are dealing only with aggregated data and still able to learn from it.
  • Alternative reading of your description is that you are allowed to observe the payoffs of all the $k$ arms, but can "keep" only the highest one. This case is actually much simpler because it is as if you were cheating in the standard multi-armed bandit problem by looking at the possible rewards of the remaining arms. In such a case, record all the individual payoffs, even if you didn't collect them, they give you relevant information on the payoff distribution of the arms. You are having a cookie and eating a cookie at the same time!

It sounds like this can be solved within the standard multi-armed bandit framework, with minimal changes to the algorithms.


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.