Is there a term or name (or better yet, strategies) for the following problem?

Take a 'standard' $k$-armed multi-armed bandit problem (stochastic real rewards, IID pulls for a given arm), but instead of maximizing the mean sum of rewards across $H$ pulls, maximize the mean maximum reward across $H$ pulls.

(I know that classically this is formulated as minimizing regret instead.)

Intuitively, strategies for solving this would have substantially more variance-seeking than strategies for a standard multi-armed bandit problem - if you're in an exploit phase with sufficient pulls left and arm A is known to have a somewhat higher mean, but somewhat lower variance, than arm B, a strategy for a normal multi-armed bandit problem would likely pick A, whereas a strategy for this would likely pick B.

  • $\begingroup$ you may be looking for the distinction between "simplex regret" and "cumulative regret" $\endgroup$ May 8, 2023 at 19:46
  • $\begingroup$ I went to search the term 'simplex regret' and this question was on the first page of the results :/ $\endgroup$
    – TLW
    May 9, 2023 at 0:41
  • $\begingroup$ I am aware of the mathematical concept of a simplex; I do not see how it applies in this situation. I have changed the reward function, not the feasibility region. Please elaborate? $\endgroup$
    – TLW
    May 9, 2023 at 1:23
  • $\begingroup$ oh sorry, I meant to say "simple regret" $\endgroup$ May 9, 2023 at 1:26
  • $\begingroup$ Mm. Both simple and cumulative regret are measured w.r.t. the arm with the highest mean however, which may not be the optimal choice in this setting. Or am I missing subtleties here? $\endgroup$
    – TLW
    May 9, 2023 at 1:36

1 Answer 1


After much hunting, this appears to be known as, imaginatively (/s), the Max Bandit Problem. (This is annoyingly difficult to search for, as 'max' appears in almost all descriptions of the 'standard' k-armed bandit problem.)

I have implemented the algorithm described in Kikkawa & Ohno, 2022, and it appears to suffice for my usecase.


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.