$QD$-Learning: A Collaborative Distributed Strategy for Multi-Agent Reinforcement Learning Through Consensus + Innovations

Soummya Kar; Jose' M. F. Moura; H. Vincent Poor

Source-linked AI summary

$QD$-Learning: A Collaborative Distributed Strategy for Multi-Agent Reinforcement Learning Through Consensus + Innovations

Soummya Kar, Jose' M. F. Moura, H. Vincent Poor

arXiv:1205.0047v2Apr 30, 2012stat.MLcs.LGcs.MAmath.OCmath.PR

TL;DR

The paper addresses distributed reinforcement learning for multi-agent MDPs when agents lack prior transition and local-cost statistics and observe only local online costs. It proposes QD-learning, which combines local computation, sparse-network information exchange, and consensus-plus-innovations updates. Under weak connectivity, the agents almost surely converge asymptotically to the desired value function and optimal stationary policy, while the analysis develops mixed-time-scale stochastic methods of independent interest.

Problem
The paper addresses learning a network-averaged infinite horizon discounted-cost policy without prior global transition or local agent-cost statistics when each agent observes only local online costs.
Method
QD-learning is a distributed Q-learning scheme in which agents combine local computation, locally sensed costs, and mutual information exchange over a sparse communication network.
Results
Under weak connectivity, QD-learning almost surely achieves asymptotically optimal learning, with agents reaching consensus on the desired value function and corresponding optimal stationary policy.
Takeaways & Limitations
The paper’s consensus-plus-innovations analysis is of independent interest for distributed information processing and control problems with memory.
Takeaways & Limitations
The formulation does not address partial state observation or decentralized actuation and assumes agents perfectly observe the global state and remote control actions.

Abstract

from arXiv · show

The paper considers a class of multi-agent Markov decision processes (MDPs), in which the network agents respond differently (as manifested by the instantaneous one-stage random costs) to a global controlled state and the control actions of a remote controller. The paper investigates a distributed reinforcement learning setup with no prior information on the global state transition and local agent cost statistics. Specifically, with the agents' objective consisting of minimizing a network-averaged infinite horizon discounted cost, the paper proposes a distributed version of $Q$-learning, $\mathcal{QD}$-learning, in which the network agents collaborate by means of local processing and mutual information exchange over a sparse (possibly stochastic) communication network to achieve the network goal. Under the assumption that each agent is only aware of its local online cost data and the inter-agent communication network is \emph{weakly} connected, the proposed distributed scheme is almost surely (a.s.) shown to yield asymptotically the desired value function and the optimal stationary control policy at each network agent. The analytical techniques developed in the paper to address the mixed time-scale stochastic dynamics of the \emph{consensus + innovations} form, which arise as a result of the proposed interactive distributed scheme, are of independent interest.

A. Background and Motivation

The paper studies distributed multi-agent decision-making with a shared controlled global state but locally observed, heterogeneous costs. It motivates QD-learning as a fully distributed alternative that combines local computation with neighbor communication to learn a common welfare objective.

Problem setting: The setup models a network of agents affected by a controlled global state and a remote controller.Applications include smart-building temperature control, energy networks, robotic networks, and financial or social systems.
Problem setting: The network seeks a stationary policy minimizing the network-averaged infinite horizon discounted one-stage cost.The global objective aggregates heterogeneous local agent costs.
Motivation: Classical reinforcement learning avoids requiring prior transition and local-cost statistics by learning from state-action trajectory samples.Q-learning generates sequential stochastic value-function approximations from online or simulated trajectories.
Motivation: A centralized implementation would require continuous access to every agent’s instantaneous cost, which may be infeasible under limited energy and bit-budgeted communication.Local costs are observed only at their respective agents, creating a need for distributed information exchange.
Proposed direction: QD-learning lets agents learn through local computation and mutual communication over a sparse, possibly time-varying network.Its consensus-plus-innovations updates combine neighbor information with locally sensed costs.
Scope and assumptions: The formulation assumes full global-state observation and remote global control, leaving partial observation and decentralized actuation outside its scope.Agents are also assumed to know the remote control actions, which may limit some applications.
Expected outcome: Under sufficient information diffusion, the agents asymptotically reach consensus on the desired value function and optimal stationary strategy.The paper also presents mixed-time-scale analysis intended for broader distributed information-processing and control problems with memory.

B. Notation

This section establishes notation for vector and matrix spaces, norms, graph structure, probability, time indexing, and almost-sure interpretation.

Algebraic notation: R^k denotes k-dimensional Euclidean space, while R and R+ denote the reals and non-negative reals.Componentwise ordering and matrix spaces are also introduced.
Matrix and graph notation: The paper defines standard matrix operations and spectral notation, including Kronecker products, eigenvalue ordering, norms, and graph Laplacians.For connected graphs, the second Laplacian eigenvalue is positive and represents algebraic connectivity.
Probability and time: Time is slotted on T+; P and E denote probability and expectation, and inequalities involving random objects are interpreted almost surely unless stated otherwise.Indicator variables take value one on an event and zero otherwise.

2. SYSTEM MODEL

The system is a finite-state controlled Markov decision process with heterogeneous agent costs and an unknown model, where Q-learning estimates the discounted optimum from trajectories rather than known statistics.

Controlled Markov model: The state process is a finite-state controlled Markov chain with a finite action set and transition probabilities conditioned on state and action.A stationary policy selects actions as a function of the current state.
Cost objective: Each agent incurs a random one-stage cost, while the objective is the network’s global infinite horizon discounted cost.The discount factor satisfies 0 < γ < 1.
Optimal control: The MDP seeks the optimal discounted value function and its associated stationary policy.The centralized dynamic-programming operator has the optimal value as a fixed point.
Dynamic programming: For γ < 1, the dynamic-programming operator is a strict contraction, so its fixed point is unique and iterates converge to it.This contraction property underlies classical policy-iteration evaluation.
Learning without a model: Classical dynamic programming requires expected costs and transition probabilities to be known in advance, whereas Q-learning uses state-action trajectory samples.Q-learning estimates state-action values from online or simulated responses and recovers the desired value function from them.
Distributed motivation: In the multi-agent setting, centralized Q-learning requires transmitting every local instantaneous cost to a central resource at all times.Limited energy and bit-budgeted communication motivate collaborative local computation and communication.

3. QD-LEARNING: DISTRIBUTED COLLABORATIVE Q-LEARNING

QD-learning is a distributed collaborative Q-learning scheme in which agents use local processing and neighborhood message exchanges to learn a common network-wide value function. Its analysis accommodates sparse, time-varying, stochastic communication under weak connectivity and mixed time-scale consensus-plus-innovations dynamics.

Distributed scheme: QD-learning distributes multi-agent Q-learning through local processing and mutual information exchange among network agents.The scheme uses local online state-action trajectories, costs, and information obtained from neighboring agents.
Distributed scheme: Each agent has access to locally sensed costs and neighbor messages rather than the complete network reward history.The local information set is generally a strict subset of the global information set when communication is not complete.
Distributed scheme: The collaboration objective is for every agent to obtain an accurate estimate of the desired value function through long-run network-wide information dissemination.The paper identifies sufficient dissemination as a central design goal of distributed message exchange and local processing.
Communication assumptions: The communication model permits time-varying stochastic graphs, packet losses, spatially correlated link failures, and disconnected instantaneous graph realizations.The required condition is average connectivity, expressed through a positive second eigenvalue of the expected graph Laplacian; quantized exchange is not considered.
Analysis: The convergence analysis develops stochastic-approximation techniques for the mixed time-scale dynamics generated by the proposed scheme.The paper studies consensus and innovations behavior while assuming controlled Markov transitions and suitable moment conditions on one-stage random costs.

A. Main Result

The main result establishes convergence of the QD-learning iterates under assumptions (M.1)–(M.5). It further identifies the limiting value-function quantities for every network agent.

A. Main Result: Under (M.1)–(M.5), the QD-learning iterates at each network agent converge to a common Q∗ in R^{|X×U|}.The result is stated for the successive iterates obtained through the distributed update rules (10) and (13).
A. Main Result: For each network agent n, the limiting Q-function yields the value function through V∗_i = max_{u∈U} Q∗_{i,u}.The supplied result passages state the relationship between the limiting Q-function and the value function for each state i.

4. INTERMEDIATE APPROXIMATION RESULTS

Section 4 develops stochastic approximation results for analyzing QD-learning, including bounds, consensus-subspace contraction, and convergence of noise-driven recursions.

The section provides approximation results used in the subsequent analysis of QD-learning.
A stochastic contraction result quantifies convergence toward network-averaged behavior for recursions driven by random graph Laplacians.
The consensus-space framework decomposes vectors into consensus and orthogonal components, enabling analysis of disagreement dynamics.
Under the stated assumptions, the auxiliary process z_i,u(t) converges to zero almost surely.
The auxiliary recursion remains small after a random time, while the Laplacian-dependent term may be removed when its weight sequence is identically zero.
The order-preserving property of the update operator supports comparison arguments used in the convergence proofs.

5. CONVERGENCE OF QD-LEARNING

Section 5 analyzes QD-learning convergence through boundedness of the iterates, asymptotic consensus, and the resulting averaged network dynamics.

The convergence analysis first establishes boundedness of QD-learning iterates.
It then establishes consensus of agent updates with respect to network-averaged behavior.
The proof concludes by studying the properties of the resulting averaged network dynamics.

A. QD-learning: Boundedness

The boundedness analysis shows that QD-learning iterates remain pathwise bounded, using a scaled-noise recursion, order preservation, and a contradiction argument.

The section is devoted to obtaining boundedness of the QD-learning iterates.
Each agent’s successive refinement sequence is pathwise bounded almost surely.
A contradiction argument rules out divergence of the iterates on any event of positive probability.
The proof scales the noise by an adaptive envelope and analyzes the resulting zero-initialized recursion.
Order preservation of the update operator propagates upper and lower bounds through the recursion.

B. QD-learning: Asymptotic Consensus

The asymptotic-consensus analysis studies disagreement between local Q-values and their network average, showing that this disagreement vanishes almost surely.

Because the argument applies to every state-action pair and the local process is a piecewise-constant interpolation, the local iterates merge with the network average.
The agents reach consensus asymptotically for each state-action pair.
Each local update combines a Laplacian consensus term with an innovation involving the averaged iterate and stochastic noise.
The proof samples the piecewise-constant local process at stopping times and analyzes the resulting adapted recursion.
The residual between each sampled iterate and the component-wise average converges to zero almost surely.
Specifically, (k + 1)^τ b z_k converges to zero almost surely for τ in the stated interval, implying b z_k → 0.

C. QD-learning: Averaged Dynamics

The network-averaged QD iterate is analyzed through consensus and innovation dynamics, establishing almost-sure convergence to the unique fixed point Q∗ of the centralized Q-learning operator.

Asymptotic consensus reduces the distributed analysis to convergence of the network-averaged iterate {Qt}.
The centralized Q-learning operator G is a contraction with a unique fixed point Q∗.
The auxiliary scalar process z_i,u(t) converges to zero almost surely when its adapted perturbation ε_i,u(t) vanishes almost surely.
The proof decomposes the averaged recursion into martingale noise and vanishing error terms, then applies the auxiliary-process lemma.
The bounded averaged iterate converges almost surely to Q∗, completing the convergence argument used in Theorem 3.1.

6. SIMULATION STUDIES

Simulations compare distributed QD-learning with centralized Q-learning in a 40-agent, low-dimensional setting with stochastic communication losses. The distributed factors reach consensus and exhibit convergence behavior close to the centralized method.

N = 40 agents with binary-valued state and action spaces form the simulation network.The state-action space has cardinality 4.
The communication topology uses two neighbors on either side, with each link independently erased with probability 0.5.
The simulation compares centralized Q-learning with distributed QD-learning on a single randomly generated state-action trajectory.
The distributed Q-factors at 10 randomly selected agents reach consensus for each state-action pair.
QD-learning has a convergence rate reasonably close to centralized Q-learning, with its per-step convergence factor approaching the centralized factor asymptotically.The paper attributes this to consensus dominating innovations, allowing agents to track the network-aggregated innovation at large t.
The convergence-rate inference is drawn from a low-dimensional four-state-action-pair setup, while absolute rates may decline as dimensionality increases.

7. CONCLUSION

The paper develops QD-learning for collaborative multi-agent MDPs with local observations and communication, targeting network-average discounted cost without prior model or cost statistics. It proves asymptotic optimal learning under weak connectivity and reports close-to-centralized simulated convergence rates.

The problem is to learn an optimal stationary strategy minimizing network-average infinite-horizon discounted costs without prior transition or local-cost statistics.
QD-learning uses local computation and communication so geographically distributed agents can learn collaboratively rather than forwarding every instantaneous cost to a centralized supervisor.
Under minimal connectivity assumptions, agents asymptotically reach consensus on the desired value function and corresponding optimal stationary control strategy.
The analysis handles mixed-time-scale, potentially non-Markovian stochastic evolutions caused by generic dependence in the state-action trajectories.
The analysis techniques are expected to apply to broader distributed information-processing and control problems with memory.
The considered setting assumes a globally observable state for local agents and a remote controller; partial state information and distributed actuation remain future challenges.