Bandit-like setup but taking max reward over sequential choices 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.)
 A: 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.
