Thinking Beyond Visibility: A Near-Optimal Policy Framework for Locally Interdependent Multi-Agent MDPs

• URL: http://arxiv.org/abs/2506.04215v1
• Date: Wed, 04 Jun 2025 17:57:30 GMT
• Title: Thinking Beyond Visibility: A Near-Optimal Policy Framework for Locally Interdependent Multi-Agent MDPs
• Authors: Alex DeWeese, Guannan Qu,
• Abstract summary: We show how three closed-form policies can be tractable to compute in various situations and are exponentially close to optimal with respect to visibility.<n>These policies are able to remember agents beyond their visibilities which allows them to perform significantly better in many small and fixed visibility settings.<n>We also propose a generalized form of the Locally Interdependent Multi-Agent MDP that allows for transition dependence and extended reward dependence.
• Score: 6.015898117103069
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs) are known to be NEXP-Complete and intractable to solve. However, for problems such as cooperative navigation, obstacle avoidance, and formation control, basic assumptions can be made about local visibility and local dependencies. The work DeWeese and Qu 2024 formalized these assumptions in the construction of the Locally Interdependent Multi-Agent MDP. In this setting, it establishes three closed-form policies that are tractable to compute in various situations and are exponentially close to optimal with respect to visibility. However, it is also shown that these solutions can have poor performance when the visibility is small and fixed, often getting stuck during simulations due to the so called "Penalty Jittering" phenomenon. In this work, we establish the Extended Cutoff Policy Class which is, to the best of our knowledge, the first non-trivial class of near optimal closed-form partially observable policies that are exponentially close to optimal with respect to the visibility for any Locally Interdependent Multi-Agent MDP. These policies are able to remember agents beyond their visibilities which allows them to perform significantly better in many small and fixed visibility settings, resolve Penalty Jittering occurrences, and under certain circumstances guarantee fully observable joint optimal behavior despite the partial observability. We also propose a generalized form of the Locally Interdependent Multi-Agent MDP that allows for transition dependence and extended reward dependence, then replicate our theoretical results in this setting.

Related papers

• Generalization in Monitored Markov Decision Processes (Mon-MDPs) [9.81003561034599]
  In many real-world scenarios, rewards are not always observable, which can be modeled as a monitored Markov decision process (Mon-MDP)<n>This work explores Mon-MDPs using function approximation (FA) and investigates the challenges involved.<n>We show that combining function approximation with a learned reward model enables agents to generalize from monitored states with observable rewards, to unmonitored environment states with unobservable rewards.
  arXiv  Detail & Related papers  (2025-05-13T21:58:25Z)
• Offline Multi-agent Reinforcement Learning via Score Decomposition [51.23590397383217]
  offline cooperative multi-agent reinforcement learning (MARL) faces unique challenges due to distributional shifts.<n>This work is the first work to explicitly address the distributional gap between offline and online MARL.
  arXiv  Detail & Related papers  (2025-05-09T11:42:31Z)
• Locally Interdependent Multi-Agent MDP: Theoretical Framework for Decentralized Agents with Dynamic Dependencies [6.015898117103069]
  We analyze a decentralized model with dynamically varying dependencies called the Locally Interdependent Multi-Agent MDP. Despite the intractability that general partially observable multi-agent systems suffer from, we propose three closed-form policies.
  arXiv  Detail & Related papers  (2024-06-10T22:11:00Z)
• RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluation [73.2390735383842]
  We introduce the first sample-efficient algorithm for LMDPs without any additional structural assumptions. We show how these can be used to derive near-optimal guarantees of an optimistic exploration algorithm. These results can be valuable for a wide range of interactive learning problems beyond LMDPs, and especially, for partially observed environments.
  arXiv  Detail & Related papers  (2024-06-03T14:51:27Z)
• Score-Aware Policy-Gradient Methods and Performance Guarantees using Local Lyapunov Conditions: Applications to Product-Form Stochastic Networks and Queueing Systems [1.747623282473278]
  We introduce a policygradient method for model reinforcement learning (RL) that exploits a type of stationary distributions commonly obtained from decision processes (MDPs) in networks. Specifically, when the stationary distribution of the MDP is parametrized by policy parameters, we can improve existing policy methods for average-reward estimation.
  arXiv  Detail & Related papers  (2023-12-05T14:44:58Z)
• A Fully Polynomial Time Approximation Scheme for Constrained MDPs and Stochastic Shortest Path under Local Transitions [2.512827436728378]
  We study the structure of (C)C-MDP, particularly an important variant that involves local transition. In this work, we propose a fully-time approximation scheme for (C)C-MDP that computes (near) optimal deterministic policies.
  arXiv  Detail & Related papers  (2022-04-10T22:08:33Z)
• Proximal Reinforcement Learning: Efficient Off-Policy Evaluation in Partially Observed Markov Decision Processes [65.91730154730905]
  In applications of offline reinforcement learning to observational data, such as in healthcare or education, a general concern is that observed actions might be affected by unobserved factors. Here we tackle this by considering off-policy evaluation in a partially observed Markov decision process (POMDP) We extend the framework of proximal causal inference to our POMDP setting, providing a variety of settings where identification is made possible.
  arXiv  Detail & Related papers  (2021-10-28T17:46:14Z)
• Common Information based Approximate State Representations in Multi-Agent Reinforcement Learning [3.086462790971422]
  We develop a general compression framework with approximate common and private state representations, based on which decentralized policies can be constructed. The results shed light on designing practically useful deep-MARL network structures under the "centralized learning distributed execution" scheme.
  arXiv  Detail & Related papers  (2021-10-25T02:32:06Z)
• Convergence Rates of Average-Reward Multi-agent Reinforcement Learning via Randomized Linear Programming [41.30044824711509]
  We focus on the case that the global reward is a sum of local rewards, the joint policy factorizes into agents' marginals, and full state observability. We develop multi-agent extensions, whereby agents solve their local saddle point problems and then perform local weighted averaging. We establish that the sample complexity to obtain near-globally optimal solutions matches tight dependencies on the cardinality of the state and action spaces.
  arXiv  Detail & Related papers  (2021-10-22T03:48:41Z)
• Permutation Invariant Policy Optimization for Mean-Field Multi-Agent Reinforcement Learning: A Principled Approach [128.62787284435007]
  We propose the mean-field proximal policy optimization (MF-PPO) algorithm, at the core of which is a permutation-invariant actor-critic neural architecture. We prove that MF-PPO attains the globally optimal policy at a sublinear rate of convergence. In particular, we show that the inductive bias introduced by the permutation-invariant neural architecture enables MF-PPO to outperform existing competitors.
  arXiv  Detail & Related papers  (2021-05-18T04:35:41Z)
• Dealing with Non-Stationarity in Multi-Agent Reinforcement Learning via Trust Region Decomposition [52.06086375833474]
  Non-stationarity is one thorny issue in multi-agent reinforcement learning. We introduce a $delta$-stationarity measurement to explicitly model the stationarity of a policy sequence. We propose a trust region decomposition network based on message passing to estimate the joint policy divergence.
  arXiv  Detail & Related papers  (2021-02-21T14:46:50Z)
• Invariant Causal Prediction for Block MDPs [106.63346115341862]
  Generalization across environments is critical to the successful application of reinforcement learning algorithms to real-world challenges. We propose a method of invariant prediction to learn model-irrelevance state abstractions (MISA) that generalize to novel observations in the multi-environment setting.
  arXiv  Detail & Related papers  (2020-03-12T21:03:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.