A Decentralized Partially Observable Team Decision Methodology with Delayed Information Sharing

Core Problem and Motivation§

This paper addresses decentralized partially observable Markov decision processes (Dec-POMDPs) with two key challenges: (1) unknown system dynamics and (2) delayed common information sharing among team members. Traditional solutions rely on centralized training or coordination, which is infeasible in many real-world multi-agent settings (e.g., robot swarms, distributed sensor networks). The authors propose a fully decentralized framework where each agent independently learns an approximate low-rank MDP and computes its policy using only local private information and delayed shared information.

The central insight is to combine team-theoretic equivalence with low-rank model representations to decompose the centralized team problem into independent per-agent subproblems, while providing finite-sample guarantees.

Technical Approach§

Problem Formulation§

The team decision problem is a decentralized POMDP defined by:

• State space $\mathcal{S}$, action space $\mathcal{A} = \prod_{i=1}^N \mathcal{A}_i$
• Transition kernel $P(s'|s,a)$ (unknown)
• Observation space $\mathcal{O} = \prod_{i=1}^N \mathcal{O}_i$ with observation kernel $O(o|s,a)$
• Reward function $r(s,a)$

Each agent $i$ receives a private observation $o_i^t$ and a delayed common information $c_i^t$ (e.g., past actions/observations of other agents shared with delay $\tau$). The goal is to find a decentralized policy $\pi = (\pi_i)_{i=1}^N$ that maximizes the expected discounted return:

$$ J(\pi) = \mathbb{E}\left[ \sum_{t=0}^\infty \gamma^t r(s_t, a_t) \right] $$

Low-Rank MDP Representation§

The transition and observation dynamics are assumed to admit a low-rank factorization:

$$ P(s'|s,a) = \sum_{k=1}^r \phi_k(s,a) \psi_k(s'), \quad O(o|s,a) = \sum_{k=1}^r \mu_k(s,a) \nu_k(o) $$

where $r \ll |\mathcal{S}|$ is the rank. This enables sample-efficient learning from limited data. Each agent learns these factors using least-squares value iteration (LSVI) on its local history.

Team-Theoretic Decomposition§

Using the team-theoretic equivalence, the centralized team-optimal policy can be decomposed into per-agent policies under a common information structure. Each agent $i$ solves a local MDP defined by:

• Local state: $s_i = (o_i, c_i)$ (private + delayed common info)
• Local action: $a_i$
• Local reward: $r_i(s_i, a_i) = \mathbb{E}[r(s,a) | s_i, a_i]$

Despite partial observability and delayed information, the algorithm recovers an approximate team-optimal policy: $\pi_i \approx \pi_i^*$ for each agent.

Algorithm: Decentralized LSVI§

Each agent runs least-squares value iteration on its local low-rank MDP. The Q-function is approximated as:

$$ Q(s,a) \approx \sum_{k=1}^r w_k \phi_k(s,a) $$

where $w_k$ are weights learned by solving a regularized least-squares problem:

$$ w = \arg\min_{w} \sum_{(s,a,r,s')} \left( r + \gamma V(s') - w^\top \phi(s,a) \right)^2 + \lambda \|w\|_2^2 $$

This is repeated for each iteration of value iteration, followed by policy extraction and execution.

Finite-Sample Guarantees§

The authors prove a sample-complexity bound for the algorithm: to achieve an $\epsilon$-optimal policy with high probability, each agent requires

$$ \tilde{\mathcal{O}}\left( \frac{r \cdot H^3 \cdot |\mathcal{A}|}{\epsilon^2} \right) $$

samples, where $H$ is the horizon and $r$ is the rank. This matches the dependence of centralized low-rank MDPs, showing that decentralization does not degrade sample efficiency.

Implementation Sketch§

Below is a Python/PyTorch snippet for a single agent's learning loop:

import torch
import torch.nn as nn

class LowRankLSVI(nn.Module):
    def __init__(self, state_dim, action_dim, rank, gamma=0.99, lamb=1e-3):
        super().__init__()
        self.phi = nn.Linear(state_dim + action_dim, rank)  # feature map
        self.gamma = gamma
        self.lamb = lamb
        self.w = torch.zeros(rank)

    def q_value(self, s, a):
        features = self.phi(torch.cat([s, a], dim=-1))
        return (features * self.w).sum(-1)

    def fit(self, s, a, r, s_next, done, policy):
        # compute target using next state values
        with torch.no_grad():
            v_next = torch.zeros_like(r)
            for a_next in range(policy.action_dim):
                v_next = torch.maximum(v_next, self.q_value(s_next, a_next))
            target = r + self.gamma * (1 - done) * v_next
        features = self.phi(torch.cat([s, a], dim=-1))
        # regularized least squares
        A = features.T @ features + self.lamb * torch.eye(self.phi.out_features)
        b = features.T @ target
        self.w = torch.linalg.solve(A, b)

    def update_policy(self):
        # extract greedy policy w.r.t. Q
        pass

Each agent independently maintains its own LowRankLSVI instance and updates it using only local data and delayed common information. No central coordinator is needed, and the algorithm scales linearly with the number of agents.

Key Contributions§

1. Decentralized learning without centralized training or coordination.
2. Low-rank MDP learning from partial observability and delayed information.
3. Team-theoretic decomposition that recovers an approximate team-optimal policy per agent.
4. Finite-sample guarantees with a sample-complexity bound that matches centralized settings.

Practical Implications§

This work is relevant for distributed multi-agent systems where communication is limited or delayed, such as autonomous vehicle fleets, distributed robotics, and federated reinforcement learning. The methodology provides a theoretically grounded path to decentralized decision-making with performance guarantees.