Distributed Learning for Multi-Stage Bandits: No-Regret Algorithm and Lower Bound

Motivated by the distributed nature of many network applications, this paper proposes a new online learning problem called multi-stage bandits. In multi-stage bandits, a job needs to go through multiple stages, each managed by a different agent, before generating an outcome. Each agent can only control its own action and learn the final outcome of the job. It has neither knowledge nor control on actions taken by agents in the next stage. The goal of this paper is to develop distributed online learning algorithms that achieve sublinear regret in adversarial environments. The setting of this paper significantly expands the traditional multi-armed bandit problem, which considers only one agent and one stage. In addition to the exploration-exploitation dilemma in the traditional multi-armed bandit problem, we show that the consideration of multiple stages introduces a third component, education, where an agent needs to choose its actions to facilitate the learning of agents in the next stage. To solve this newly introduced exploration-exploitation-education trilemma, we propose a simple distributed online learning algorithm, ϵ−EXP3. We theoretically prove that the ϵ−EXP3 algorithm is a no-regret policy that achieves sublinear regret. We also show that the regret of ϵ−EXP3 is close to the regret lower bound under a class of time-homogeneous oracle policies. Finally, we conduct simulation studies on a variety of network applications. Simulation results show that the ϵ−EXP3 algorithm significantly outperforms existing no-regret online learning algorithms for the traditional multi-armed bandit problem.