Fast Multi-Agent Temporal-Difference Learning via Homotopy Stochastic Primal-Dual Optimization
We study the policy evaluation problem in multi-agent reinforcement learning where a group of agents, with jointly observed states and private local actions and rewards, collaborate to learn the value function of a given policy via local computation and communication over a connected undirected network. This problem arises in various large-scale multi-agent systems, including power grids, intelligent transportation systems, wireless sensor networks, and multi-agent robotics. When the dimension of state-action space is large, the temporal-difference learning with linear function approximation is widely used. In this paper, we develop a new distributed temporal-difference learning algorithm and quantify its finite-time performance. Our algorithm combines a distributed stochastic primal-dual method with a homotopy-based approach to adaptively adjust the learning rate in order to minimize the mean-square projected Bellman error by taking fresh online samples from a causal on-policy trajectory. We explicitly take into account the Markovian nature of sampling and improve the best-known finite-time error bound from $O(1/\sqrt{T})$ to~$O(1/T)$, where $T$ is the total number of iterations.
Code (0)
등록된 구현이 없습니다.
Tasks
Multi-agent Reinforcement LearningReinforcement LearningStochastic OptimizationSimilar Papers 제목 키워드 기반
Strong homotopy of digitally continuous functions
We introduce a new type of homotopy relation for digitally continuous functions which we call ``strong homotopy.'' Both digital homotopy and strong homotopy are natural digitizations of classical topological homotopy: th…
Homotopy-aware Multi-agent Navigation via Distributed Model Predictive Control
Multi-agent trajectory planning requires ensuring both safety and efficiency, yet deadlocks remain a significant challenge, especially in obstacle-dense environments. Such deadlocks frequently occur when multiple agents …
Trajectory PlanningDigital homotopy relations and digital homology theories
In this paper we prove results relating to two homotopy relations and four homology theories developed in the topology of digital images. We introduce a new type of homotopy relation for digitally continuous functions wh…
Can We Find Nash Equilibria at a Linear Rate in Markov Games?
We study decentralized learning in two-player zero-sum discounted Markov games where the goal is to design a policy optimization algorithm for either agent satisfying two properties. First, the player does not need to kn…
A Fast Randomized Method to Find Homotopy Classes for Socially-Aware Navigation
We introduce and show preliminary results of a fast randomized method that finds a set of K paths lying in distinct homotopy classes. We frame the path planning task as a graph search problem, where the navigation graph …