# Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structure

arXiv: https://arxiv.org/abs/2111.00781 · HTML: https://mlsanity.com/paper/2111.00781/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 49 references that are in the map.
- First posted on arXiv 1 Nov 2021.

## Builds on (most cited first, 27 of 27)

- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [Corralling a Band of Bandit Algorithms](https://mlsanity.com/paper/1612.06246/) (2016)
- [Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games](https://mlsanity.com/paper/2106.01969/) (2021)
- [When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?](https://mlsanity.com/paper/2110.04184/) (2021)
- [Social Learning in Multi Agent Multi Armed Bandits](https://mlsanity.com/paper/1910.02100/) (2019)
- [Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Games](https://mlsanity.com/paper/2110.05682/) (2021)
- [Sample-Efficient Learning of Stackelberg Equilibria in General-Sum Games](https://mlsanity.com/paper/2102.11494/) (2021)
- [The Gossiping Insert-Eliminate Algorithm for Multi-Agent Bandits](https://mlsanity.com/paper/2001.05452/) (2020)
- [Distributed Cooperative Decision Making in Multi-agent Multi-armed Bandits](https://mlsanity.com/paper/2003.01312/) (2020)
- [Independent Natural Policy Gradient Always Converges in Markov Potential Games](https://mlsanity.com/paper/2110.10614/) (2021)
- [On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2110.05707/) (2021)
- [Gradient play in stochastic games: stationary points, convergence, and sample complexity](https://mlsanity.com/paper/2106.00198/) (2021)
- [Decentralized Multi-Agent Reinforcement Learning with Networked Agents: Recent Advances](https://mlsanity.com/paper/1912.03821/) (2019)
- [Corralling Stochastic Bandit Algorithms](https://mlsanity.com/paper/2006.09255/) (2020)
- [Robust Multi-Agent Multi-Armed Bandits](https://mlsanity.com/paper/2007.03812/) (2020)
- [Online Learning in Markov Decision Processes with Adversarially Chosen Transition Probability Distributions](https://mlsanity.com/paper/1303.3055/) (2013)
- [Learning to Collaborate in Markov Decision Processes](https://mlsanity.com/paper/1901.08029/) (2019)
- [Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisions](https://mlsanity.com/paper/2011.03896/) (2020)
- [Game of Thrones: Fully Distributed Learning for Multi-Player Bandits](https://mlsanity.com/paper/1810.11162/) (2018)
- [Online Learning for Cooperative Multi-Player Multi-Armed Bandits](https://mlsanity.com/paper/2109.03818/) (2021)
- [Bayesian Algorithms for Decentralized Stochastic Bandits](https://mlsanity.com/paper/2010.10569/) (2020)
- [A Dynamic Observation Strategy for Multi-agent Multi-armed Bandit Problem](https://mlsanity.com/paper/2004.03793/) (2020)

## Built on by (most cited first, 14 of 14)

- [Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergence](https://mlsanity.com/paper/2202.04129/) (2022)
- [Online Learning in Stackelberg Games with an Omniscient Follower](https://mlsanity.com/paper/2301.11518/) (2023)
- [Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Games](https://mlsanity.com/paper/2401.15240/) (2024)
- [Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instruments](https://mlsanity.com/paper/2208.11040/) (2022)
- [Optimal Cooperative Multiplayer Learning Bandits with Noisy Rewards and No Communication](https://mlsanity.com/paper/2311.06210/) (2023)
- [The Synergy Between Optimal Transport Theory and Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2401.10949/) (2024)
- [Impact of Decentralized Learning on Player Utilities in Stackelberg Games](https://mlsanity.com/paper/2403.00188/) (2024)
- [Multiplayer Information Asymmetric Contextual Bandits](https://mlsanity.com/paper/2503.08961/) (2025)
- [Efficient Morphology-Control Co-Design via Stackelberg Proximal Policy Optimization](https://mlsanity.com/paper/2603.15388/) (2026)
- [Provably Efficient Model-free RL in Leader-Follower MDP with Linear Function Approximation](https://mlsanity.com/paper/2211.15792/) (2022)
- [Decentralized Online Learning in General-Sum Stackelberg Games](https://mlsanity.com/paper/2405.03158/) (2024)
- [Policy Iteration for Two-Player General-Sum Stochastic Stackelberg Games](https://mlsanity.com/paper/2405.06689/) (2024)
- [Hierarchical Dataset Selection for High-Quality Data Sharing](https://mlsanity.com/paper/2512.10952/) (2025)
- [Optimal Budgeted Adaptation of Large Language Models](https://mlsanity.com/paper/2602.00952/) (2026)

## Abstract (arXiv)

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 widetildeO(√ABT) and a near-optimal gap-dependent regret of 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 widetildeO(√H7S2ABT) 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.