Appendix A Lower Bound In this section, we establish a lower bound on the expected regret of any algorithm for our multi-agent