# Learning to Collaborate in Markov Decision Processes

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

## Key facts

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

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

- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games](https://mlsanity.com/paper/2102.04540/) (2021)
- [On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2110.05707/) (2021)
- [Performative Reinforcement Learning](https://mlsanity.com/paper/2207.00046/) (2022)
- [Defense Against Reward Poisoning Attacks in Reinforcement Learning](https://mlsanity.com/paper/2102.05776/) (2021)
- [Reinforcement Learning Under Algorithmic Triage](https://mlsanity.com/paper/2109.11328/) (2021)
- [Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structure](https://mlsanity.com/paper/2111.00781/) (2021)
- [Performative Reinforcement Learning in Gradually Shifting Environments](https://mlsanity.com/paper/2402.09838/) (2024)
- [Admissible Policy Teaching through Reward Design](https://mlsanity.com/paper/2201.02185/) (2022)
- [Interactive Inverse Reinforcement Learning for Cooperative Games](https://mlsanity.com/paper/2111.04698/) (2021)
- [Learning Meta Representations for Agents in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2108.12988/) (2021)
- [Dealing with Non-Stationarity in MARL via Trust-Region Decomposition](https://mlsanity.com/paper/2102.10616/) (2021)
- [Incorporating Human Flexibility through Reward Preferences in Human-AI Teaming](https://mlsanity.com/paper/2312.14292/) (2023)
- [Agent-Specific Effects: A Causal Effect Propagation Analysis in Multi-Agent MDPs](https://mlsanity.com/paper/2310.11334/) (2023)

## Abstract (arXiv)

We consider a two-agent MDP framework where agents repeatedly solve a task in a collaborative setting. We study the problem of designing a learning algorithm for the first agent (A1) that facilitates a successful collaboration even in cases when the second agent (A2) is adapting its policy in an unknown way. The key challenge in our setting is that the first agent faces non-stationarity in rewards and transitions because of the adaptive behavior of the second agent. We design novel online learning algorithms for agent A1 whose regret decays as O(T^max1-frac37 · α, frac14) with T learning episodes provided that the magnitude of agent A2's policy changes between any two consecutive episodes are upper bounded by O(T-α). Here, the parameter α is assumed to be strictly greater than 0, and we show that this assumption is necessary provided that the learning parity with noise problem is computationally hard. We show that sub-linear regret of agent A1 further implies near-optimality of the agents' joint return for MDPs that manifest the properties of a smooth game.