Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structure
Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structure
复制标题
DOI：
--
复制
发表时间：
2021-11
期刊：
影响因子：
--
通讯作者：
Hsu Kao;Chen-Yu Wei;V. Subramanian
中科院分区：
文献类型：
--
作者：
Hsu Kao;Chen-Yu Wei;V. Subramanian
由于信息不对称，多智能体强化学习(MAIL)问题具有挑战性。为了克服这一挑战，现有的方法通常需要代理之间的高级别协调或沟通。我们考虑了应用中出现的具有分层信息结构的两智能体多臂土匪(MAB)和马尔可夫决策过程(MDP)，并利用它们提出了不需要协调或通信的更简单、更有效的算法。在这种结构中，在每一步中，“领导者”首先选择自己的动作，然后“跟随者”在观察领导者的动作后决定自己的动作。这两个代理根据他们的联合行动观察相同的奖励(以及MDP设置中的相同状态转换)。对于盗贼环境，我们提出了一种分级盗贼算法，该算法获得了一个近似最优的空位无关的悔恨和一个几乎最优的空位无关的后悔，其中$A$和$B$分别是领导者和跟随者的行动次数，$T$是步数。我们进一步扩展到多个追随者的情况和具有深层次的情况，其中我们都获得了接近最优的后悔界。对于MDP设置，我们获得$\widetilde{\mathcal{O}}(\SQRT{H^7S^2ABT})$RELERY，其中$H$是每集的步数，$S$是状态数，$T$是集数。这与现有的$A、B$和$T$下限相匹配。
Multi-agent reinforcement learning (MARL) problems are challenging due to information asymmetry. To overcome this challenge, existing methods often require high level of coordination or communication between the agents. We consider two-agent multi-armed bandits (MABs) and Markov decision processes (MDPs) with a hierarchical information structure arising in applications, which we exploit to propose simpler and more efficient algorithms that require no coordination or communication. In the structure, in each step the ``leader"chooses her action first, and then the ``follower"decides his action after observing the leader's action. The two agents observe the same reward (and the same state transition in the MDP setting) that depends on their joint action. For the bandit setting, we propose a hierarchical bandit algorithm that achieves a near-optimal gap-independent regret of $\widetilde{\mathcal{O}}(\sqrt{ABT})$ and a near-optimal gap-dependent regret of $\mathcal{O}(\log(T))$, where $A$ and $B$ are the numbers of actions of the leader and the follower, respectively, and $T$ is the number of steps. We further extend to the case of multiple followers and the case with a deep hierarchy, where we both obtain near-optimal regret bounds. For the MDP setting, we obtain $\widetilde{\mathcal{O}}(\sqrt{H^7S^2ABT})$ regret, where $H$ is the number of steps per episode, $S$ is the number of states, $T$ is the number of episodes. This matches the existing lower bound in terms of $A, B$, and $T$.