Strategic Multi-Armed Bandit Problems Under Debt-Free Reporting

Summary

This paper considers a strategic variant of the multi-armed bandit problem with payments. It thereby builds upon a problem studied by Braverman et al. The paper formally introduces the problem formulation and proposes an algorithm, S-SE, that combines successive elimination with a meticulously chosen payment rule. It is shown that truthfulness is a dominant SPE under which the proposed algorithm suffers logarithmic regret. The paper also analyzes the utility of the arms under S-SE and the dominant SPE. Finally, the performance of the algorithm under arbitrary arm strategies is analyzed.

Strengths

- The studied problem, which is at the intersection of bandit learning and mechanism design, is very interesting. - The paper is well-written and easy to follow. - It is interesting to see that the regret achieved by Braverman et al. can be improved using an extension of successive elimination + payment rule (under debt-free reporting). - The paper proves that truthfulness is a *dominant* SPE. - The provided regret bound appears to be near-optimal and the dependence on the gaps $\Delta_{1k}$ and $\Delta_{2k}$ is quite interesting. - Overall, even though many aspects of this problem have already been studied by Braverman et al., I believe that this papers makes some insightful and novel contributions.

Weaknesses

- The paragraph **Tightness of Regret** is a very hand-wavy. In strategic settings like the one you study here, one easily mistakes an intuition about "rational agent behavior" for a rigorous argument. In particular, you write "The optimal arm only needs to report a slightly higher value than the second-best arm to be chosen by the player as the superior option [*you here assume a class of mechanisms that do in fact choose the arm with highest reported value in some specific way*]. Consequently, **all efficient low-regret mechanisms** must ensure truthfulness, at least for the two best arms." Intuitively, yes, I agree. However, this is a claim that, I think, is very difficult to prove rigorously. I recommend to adapt the language used in this paragraph and emphasize that you're providing intuition only. - Similar hand-wavy language and statements are used a few times in the text (not as bad as the above one). Please make sure to be clear whether you provide intuition (which is great) or you actually proved the statement (even better). - A minor thing that is also about the use of slightly imprecise language and might come across as nitpicking. Lemma 14 in Braverman et al. actually shows that you cannot achieve $(\alpha \mu_1 + (1-\alpha) \mu_2)T$ utility for *constant* $\alpha > 0$. Hence, you can achieve more than $\mu_2 T$ revenue, e.g., let $\alpha = 1/\sqrt{T}$, despite you saying in line 126 that "no mechanism can guarantee more than $\mu_2 T$ revenue". This is not a serious issue, since I think we can all agree that defining regret w.r.t. $\mu_2 T$ is still the right choice in view of Lemma 14. I still wanted to make you aware of this.

Questions

- Line 269: You say that the best arm is incentivized with a bonus of $O(\Delta_{12} T)$. Is this a typo? If the bonus payment would be of order $T$, then your regret bound would be of order $T$. It also doesn't seem necessary to make such a large bonus payment, since you'd only need to compensate the best arm for its truthful reporting in the first $\tau$ rounds. **Minor things:** - Consider splitting the text in Section 2 into several paragraphs to improve readability. Also, clearly highlighting the observational model and assumptions using \paragraph or some kind of \emph would be helpful, in my opinion. - Typos: "tof", "understrategy"

Rating

6

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

Limitations are adequately addressed in my opinion.

Summary

Multi-armed bandit problems capture explore-exploit scenarios under different reward structures including stochastic and adversarial. In this paper, the authors consider bandit problems where the arms report rewards strategically. To tackle such a problem, the authors devise a successive elimination scheme, where arms are eliminated till the best arm is identified (with high probability). To encourage truthful reporting, the authors devise a bonus scheme, so that the best arm is pulled unless it dips below the second-best arm, which encourages truthful reporting. In scenarios where arms fail to report truthfully, the authors develop regret bounds detailing the performance of algorithms.

Strengths

1. **Problem Formulation is Interesting** - The authors investigate debt-free reporting under the scenario of a bonus structure. The problem structure/formulation is interesting as it covers incentives, in the form of bandits reporting arms strategically, and the explore-exploit dilemma found across bandit works. 2. **Dominant Strategy is Detailed and Analyzed** - In Section 4, the authors characterize the dominant strategy for arms, under a certain type of bonus payoff, and show that this results in truthful reporting from arms. Such a characterization helps us better understand how no-regret algorithms can be derived and provides an important piece of information on these types of bandits. 3. **Regret Bounds in both Strategic and Non-Strategic Scenarios** - The authors derive regret bounds in both strategic and non-strategic scenarios. For non-strategic scenarios, the truthfulness of the arms makes it easier to determine optimal arm pulls, while for non-truthful scenarios, they use the upper bound on savings, M, to characterize regret. It would be nice to understand how the regret bound proved in Theorem 5.1 corresponds to some type of function of T. 4. **Bonus Structure as Payment Improves Regret Bounds** - Table 1 lists a comparison between the method proposed in their work (S-SE) and previous work (S-ETC). The two models differ in their bonuses, and they show that by modifying this, they go from a T^2/3 bound to a T^1/2 bound.

Weaknesses

1. **Lack of Empirical Verification** - On page 8, the authors discuss the tightness of the regret bounds, and argue that while the actual regret might change, the order of the regret is roughly the same across scenarios. However, it would be interesting to understand how tight such regret bounds are across different scenarios. Under what types of scenarios are the regret bounds tight and under which are regret bounds loose? An empirical analysis, with even simulated data, would provide a nice complement to the theoretical analysis proposed in this paper.

Questions

1. Could you further detail the types of scenarios or real-world regimes where such bandits exist?

Rating

8

Confidence

4

Soundness

3

Presentation

3

Contribution

2

Limitations

The future work section discusses additional questions that could be answered, though authors should more explicitly label this as a limitations section

Summary

The paper addresses a strategic bandit setting. Specifically, the player (algorithm) can select between K arms as in standard bandits but each arm can choose the reward it reports instead. Because of the debt-free assumptions, the reported value cannot exceed the realized reward. The papers gives an algorithm that rewards the arms based on the values they report. The regret is defined with respect to the second highest mean + the total payment given to the arms. The given algorithm can achieve logarithmic regret which is an improvement over the regret of [8].

Strengths

-The paper essentially resolves an open problem of [8] where the arms are only debt-free. -The paper also includes an additional bound which nicely characterizes the regret under deviations.

Weaknesses

-The motivation of the paper does not feel strong. Specifically, the paper answers a small question from reference [8]. -While [8] rewards using rounds, here the reward is through payment which gives higher flexibility. Can the algorithm be generalized to allow payments through rounds instead (assuming a fixed horizon T)? -If the player knows the minimum gap $\Delta$ can an explore then commit based algorithm similar to [8] be used to achieve log T regret? Below are Minor representation issues: -typo: t → $t$ in line 17 -Bullet 2 in the contribution: the regret having $\Delta_{2k}$ suggests that we should instead have $\mu_2 > \mu_3 $, i.e. strict inequality. -There is a latex problem for algorithm 1 block, it refers to the model on page 2 instead.

Questions

Please adress the above points under weaknesses.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Limitations are adequately addressed.

Summary

This paper studies a multi-armed bandit setting with stochastic arms but where the arms are strategic agents -- when an arm is pulled it can choose what fraction of the reward to keep for itself and what fraction of the reward to pass on to the principal (the learning algorithm picking the arms). The principal can only see the reward they receive (not the amount received by the agent), and all parties want to maximize their total reward. This setting was originally studied by Braverman et al., who showed that if the principal runs a standard no-regret learning algorithm then there are subgame perfect “colluding” equilibria where the principal receives nothing -- on the other hand, the principal can always asymptotically achieve the second highest average payoff by essentially running a second-price auction at the beginning of the game and only pulling the winner. This strategy proposed by Braverman et al. has two issues. One is that (naively implemented) it may require agents (the arms) to report a higher value in some early rounds than the value they actually achieve. Even if you fix this issue (by converting this idea into an explore-then-commit style algorithm), the regret of the principal -- the gap between their expected utility and actually receiving the second-highest average per round -- will be a suboptimal O(T^{2/3}). This paper shows how to get O(sqrt(TlogT)) instance-independent and O((log T)/Delta) instance-dependent regret bounds for this problem, on par with regret bounds achievable for standard bandit problems. The main idea is to adapt the Successive Elimination bandit algorithm (and its analysis) to this strategic setting. At a high level, the algorithm runs SE until there is only arm left, and then requires this arm to contribute (on average) at least the second-highest average reward per round. Finally, all participating agents are given a bonus designed to make bidding their true value incentive compatible.

Strengths

Understanding how to adapt standard learning algorithms to strategic settings is an important question. This paper provides an improved solution to a natural strategic learning environment and presents (what I would guess to be) tight regret bounds for learning in this environment. Although the algorithm is an adaptation of a standard no-regret algorithm (successive elimination), analyzing its performance in this strategic environment is non-trivial (as it involves pinning down the worst possible equilibrium behavior of the individual arms). The paper was well-written and easy to read.

Weaknesses

I think it is a little unsatisfactory that the optimal learning algorithm still takes the form “auction off the business to the best-arm for the second-best-arm’s price”, even if this auction is now done in a slightly smoother way (via successive arm elimination over several rounds, instead of a sublinear exploration period where arms simply reveal their price). I.e., both this algorithm and the previous algorithm have the property that after some stage of the game, they will only ever select one specific arm. I think it would be a more interesting result if the principal’s strategy was more time-stable and could e.g. handle arms entering or leaving the market (or adversarial rewards, although that would require more changes to the problem set-up). Another aspect of the solution that bothers me a little bit is that the new scheme requires bonuses that grow linearly in T. This seems to require a lot of trust on behalf of the agents that they will in fact eventually get reimbursed. In contrast, the previous algorithm of Braverman et al. also implements some bonus scheme (through rewarding the agents in some extra rounds at the end of the game), but these bonuses are sublinear in the time horizon.

Questions

Is it possible to modify the S-SE algorithm to work with sublinear bonuses? Do the regret lower bounds from standard bandits carry over? (I.e., are the regret bounds in this paper tight?). Feel free to reply to any other aspect of the review.

Rating

6

Confidence

4

Soundness

4

Presentation

3

Contribution

2

Limitations

Limitations are adequately addressed.

Thank you for your new experiments

Thank you for your clarifications and the new experiments. I am satisfied with these experiments and am happy to raise my score to an 8.