# Exploiting Fast Decaying and Locality in Multi-Agent MDP with Tree Dependence Structure

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Sep 2019.

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

- [LLM-Driven Stationarity-Aware Expert Demonstrations for Multi-Agent Reinforcement Learning in Mobile Systems](https://mlsanity.com/paper/2511.19368/) (2025)
- [LEED: A Highly Efficient and Scalable LLM-Empowered Expert Demonstrations Framework for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2509.14680/) (2025)
- [Dimension-Free Rates for Natural Policy Gradient in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2109.11692/) (2021)
- [Hypergraphon Mean Field Games](https://mlsanity.com/paper/2203.16223/) (2022)
- [A Microscopic Pandemic Simulator for Pandemic Prediction Using Scalable Million-Agent Reinforcement Learning](https://mlsanity.com/paper/2108.06589/) (2021)
- [Distributed Policy Gradient for Linear Quadratic Networked Control with Limited Communication Range](https://mlsanity.com/paper/2403.03055/) (2024)
- [Structured Cooperative Multi-Agent Reinforcement Learning: a Bayesian Network Perspective](https://mlsanity.com/paper/2510.09937/) (2025)
- [Explicit Credit Assignment through Local Rewards and Dependence Graphs in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2601.21523/) (2026)

## Abstract (arXiv)

This paper considers a multi-agent Markov Decision Process (MDP), where there are n agents and each agent i is associated with a state si and action ai taking values from a finite set. Though the global state space size and action space size are exponential in n, we impose local dependence structures and focus on local policies that only depend on local states, and we propose a method that finds nearly optimal local policies in polynomial time (in n) when the dependence structure is a one directional tree. The algorithm builds on approximated reward functions which are evaluated using locally truncated Markov process. Further, under some special conditions, we prove that the gap between the approximated reward function and the true reward function is decaying exponentially fast as the length of the truncated Markov process gets longer. The intuition behind this is that under some assumptions, the effect of agent interactions decays exponentially in the distance between agents, which we term "fast decaying property".