Private and Byzantine-Proof Cooperative Decision-Making
The cooperative bandit problem is a multi-agent decision problem involving a
group of agents that interact simultaneously with a multi-armed bandit, while
communicating over a network with delays. The central idea in this problem is
to design algorithms that can efficiently leverage communication to obtain
improvements over acting in isolation. In this paper, we investigate the
stochastic bandit problem under two settings - (a) when the agents wish to make
their communication private with respect to the action sequence, and (b) when
the agents can be byzantine, i.e., they provide (stochastically) incorrect
information. For both these problem settings, we provide upper-confidence bound
algorithms that obtain optimal regret while being (a) differentially-private
and (b) tolerant to byzantine agents. Our decentralized algorithms require no
information about the network of connectivity between agents, making them
scalable to large dynamic systems. We test our algorithms on a competitive
benchmark of random graphs and demonstrate their superior performance with
respect to existing robust algorithms. We hope that our work serves as an
important step towards creating distributed decision-making systems that
maintain privacy.