The Pareto Regret Frontier for Bandits
Given a multi-armed bandit problem it may be desirable to achieve a smallerthan-usual worst-case regret for some special actions. I show that the price for such unbalanced worst-case regret guarantees is rather high. Specifically, if an algorithm enjoys a worst-case regret of B with respect to some action, then there must exist another action for which the worst-case regret is at least Ω(nK/B), where n is the horizon and K the number of actions. I also give upper bounds in both the stochastic and adversarial settings showing that this result cannot be improved. For the stochastic case the pareto regret frontier is characterised exactly up to constant factors.
This paper addresses the minimax bandit problem in the stochastic setting. The case that is targeted is to bound specifically the regret for a particular arm and characterised how this deteriorates the regret on the remaining arms. The authors provide new theoretical material to prove an upper and lower bound on the repartition of the per-arm regret that match up to constants. The upper bound is based on the proposednew algorithm Unbalanced-Moss which is based on the Moss algorithm. They show that unlike in the expert case, guaranteeing a small regret for a particular arm comes to a greater cost (than in the expert case) for the remaining arms. Finally they design a new version of UCB (unbalanced UCB), that up to a logarithmic factor is 'unfair minimax' optimal and which at the same time and contrary to the MOSS algorithm possess asymptotic optimal problem-dependent regret. The paper addresses a problem of importance and seems in the most part of high value. My main concern is that I am not sure about the correctness of the lower bound proof. The question raised there should definitely be addressed.Some part of the proofs are quite compact and makes them hard to verify: passage (c)&(d) of proof of theorem 3. More intuition should be given to ease the reading of the proofs.--About the lower bound:Equation in line 143: Shouldn't it be an inequality instead of the last equality, as \epsilon_k is defined with respect to R_k which is a sup on R_\mu?  In line 126, it is assumed that \mu \in[0,1]**K, but in the example given in the proof (the \mu_k) it seems not always the case. I think this is an issue because, as mentioned above about line 143, we need to usethat R_k\geq R_\mu_k. You can see that \mu_k do not belong to [0,1]**K first of all because there are negative numbers (-\epsilon_1). Second, isn't there an issue with the constant c? In the end the constant c is put to 4 but it seems that, in some cases, the constant should be smaller than 1 by construction. Indeed we want \epsilon_k \leq 1 so that the \mu_k belong to [0,1]**K. So if the strategy \pi is such that the regret R_k on arm k is linear (R_k=n), as it could happen if the strategy never pulls k, then we would have \epsilon_k=c. So c\leq 1. But this creates a problem with the end of the proof where we need c > 2.In the passage (a) of line 150 why is there a T_k(n) appearing in the square root? It is not obvious from the mentioned standard entropy inequality.equation line 157: on the first equality the \epsilon_k should be \epsilon_1 as defined in \mu_1. This seems to create problem for the following reasoning in the same line. In this same line, in the 'last but one' term, I guess it should be already R_k instead of R_\mu_kMore generally, shouldn't the constant c depend on \pi? Because otherwise the Equation 2 is proving that any possible strategy is pulling all the arms at least linearly! (when c=4, as used in the proof). -- Other possible typos in the rest of paper: line 269: In the second part, at the end of the line: where is it proven that \Delta_i\E\tau_i\leq \sqrt{n_i*}. Is it useful? I see the part with n_i but not with n_i*.line 289: a should be \alpha?line (d) of Corollary 6. Shouldn't it be \alpha+1 and \alpha+1/2 in the denominator? Then the 'proof by graph' becomes even more fishy if their is a typo in the expression (though I guess it is not changing much).line 305: (b) it should be \Delta_i\geq 4*sqrt(n_i*) right?line 311: \tilde \Delta_l is not defined for l=0.