Mechanism design with multi-armed bandit

Although the paper provides an approach with computational efficiency, the LP studied in this paper differs from and looks more accessible than the prior work (Osogami et al., 2023).

The LP studied in Osogami et al. (2023) is a special case of the LP studied in this paper. Specifically, letting $\theta\equiv 0$ and $\rho=0$ in our LP gives the LP in Osogami et al. (2023). Notice that even the LP in Osogami et al. (2023) is unlikely to admit analytical solutions in general, and this is the key technical challenge. Our Lemma 1 gives a sufficient condition that allows us to analytically solve the LP under consideration. Lemma 2 shows that this sufficient condition is necessary whenever types are independent, so our analytical solution is optimal for a wide range of interesting cases in mechanism design.

The theoretical results' organization is not easy to follow.

We appreciate your suggestion. We agree that the presentation can be improved. However, some of the intermediate results are of independent interest and are worth being formally stated. For example, Lemma 1 contains essential information that is not contained in Corollary 1.

Thank you very much for your review.

I would love to hear the author's opinion on the novelty of the BME design in this work.

BME has not been studied as a problem of MAB (i.e. from the perspective of sample complexity), although related problem of estimating the best mean from given sample (i.e. bias correction) has been widely studied in machine learning (as we discuss in Line 161). As is acknowledged in your review, a key novelty is in the connection from mechanism design to multi-armed bandits, where we reveal that the sample complexity of BME is a relevant problem. Although we only discuss its relevance to mechanism design, BME is a fundamental problem that may find a wide range of applications, such as those that require estimating the worst case expected cost (Worst Mean Estimation). For this new problem of BME, we show that a simple approach can achieve the best possible sample complexity. Although the approach is simple, it is nontrivial that this simple approach matches the lower bound (as we discuss in paragraphs staring at 154, 365, and 404). As you suggest in your review, there may be more efficient approaches that improve constant factors, have better instance-dependent complexity, etc., and we expect that our results will provide a basis for such extensions.

Thank you very much for your review.

[W1] In this regard, in Section 5, the authors are essentially stating the fact "LP has a solution only when the feasible region of the constraints is non-empty", which is really trivial.

Although it is trivial that every LP has a solution only when the feasible region of the constraints is non-empty, this does not mean that one can analytically derive optimal solutions to all LPs. Our Lemma 1 gives a sufficient condition that allows us to analytically solve the LP under consideration. Lemma 2 shows that this sufficient condition is necessary whenever types are independent, so our analytical solution is optimal for a wide range of interesting cases in mechanism design. Note also that the (special case of) LP under consideration has been solved numerically in the prior work of mechanism design (e.g. Osogami [2023]), which also indicates the nontriviality of our results in Section 5.

[W2] Similar to the first point, the method described by the authors in the Section 6 is essentially just the basic mean estimation of each arm's reward in stochastic MAB.

The suggested approach of estimating the mean reward of each arm with $O((1/\varepsilon^2) \log(1/\delta))$ samples can only guarantee that the best mean is estimated within error \varepsilon with probability at least $(1-\delta)^K$. To provide a $(\varepsilon,\delta)$-PAC guarantee, one would need $\Omega((1/\varepsilon^2) \log(K/\delta))$ samples from each arm, resulting in the suboptimal sample complexity of $\Omega((K/\varepsilon^2) \log(K/\delta))$. The novelty of our MAB results lies in proving that $O((K/\varepsilon^2) \log(1/\delta))$ samples are sufficient for best mean estimation, and that this is the best possible sample complexity (Theorem 1).

[W3] However, in Section 3, the authors do not introduce any information regarding MAB.

The background on MAB is not needed until Section 6, and we are concerned that some of the readers would not remember what has been stated in Section 3 when they read Section 6. However, we would appreciate the reviewer's guidance on what specific information about MAB would be most helpful to include in Section 3.

[W4] These two statements seem to conflict.

The two statements do not conflict. As is stated in Section 3, the types ($t_1, t_2, ..., t_N$) are generated from a fixed distribution $P$. For this fixed distribution $P$, we consider a conditional distribution $P(\cdot\mid t_n)$ and take i.i.d. sample from $P(\cdot\mid t_n)$ in Section 6.

[Q2] Prior to line 346, the paper does not mention MAB at all. Are the authors assuming that $t_n\in[K]$ for all $n\in[N]$ here?

Yes. Note that we assume a finite number of players $N$ and a finite size of each type space $K$ (line 185). In Section 6, we state our results on general MAB problems (using the language of MAB), which are then connected to mechanism design at the end of Section 6 (Theorem 2 and Proposition 3). Specifically, for each player $n\in[N]$, the type space $\mathcal{T}_n$ corresponds to the set of arms $[K]$.