Distributed Policy Evaluation Under Multiple Behavior Strategies

By Sergio Valcarcel Macua, Jianshu Chen, Santiago Zazo, Ali H. Sayed. 2013

110 citations recorded by the source corpus.

We apply diffusion strategies to develop a fully-distributed cooperative reinforcement learning algorithm in which agents in a network communicate only with their immediate neighbors to improve predictions about their environment. The algorithm can also be applied to off-policy learning, meaning that the agents can predict the response to a behavior different from the actual policies they are following. The proposed distributed strategy is efficient, with linear complexity in both computation time and memory footprint. We provide a mean-square-error performance analysis and establish convergence under constant step-size updates, which endow the network with continuous learning capabilities. The results show a clear gain from cooperation: when the individual agents can estimate the solution, cooperation increases stability and reduces bias and variance of the prediction error; but, more importantly, the network is able to approach the optimal solution even when none of the individual agents can (e.g., when the individual behavior policies restrict each agent to sample a small portion of the state space).

Subfields: Artificial Intelligence, Computer Networks and Communications, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Statistical and Nonlinear Physics

Citations in the corpus

Stochastic Primal-Dual Q-Learning (2018, neutral): “We expect that this fundamental framework will be useful to advance many subﬁelds of RL, such as the distributed RL (Kar et al., 2013; Macua et al., 2015; Zhang et al., 2018; Lee et al., 2018), Q-learning with function approximations (Sutton et al., 2009b,a), sparsity promoted RL (Mahadevan and…”
Smoothed Dual Embedding Control (2017, background): “Later on, it was realized that several of these gradient-based algorithms can be interpreted as solving a primal-dual problem (Mahadevan et al., 2014; Liu et al., 2015; Macua et al., 2015; Dai et al., 2016).”
A Kernel Loss for Solving the Bellman Equation (2019, methodology): “Furthermore, the solution found by our algorithm minimizes the projected Bellman error, as in prior works when specialized to the same settings (Sutton et al., 2009; Maei et al., 2010; Liu et al., 2015; Macua et al., 2015).”
Stochastic Variance Reduction Methods for Policy Evaluation (2017, methodology): “Liu et al. (2015) and Valcarcel Macua et al. (2015) independently showed that the GTD2 algorithm (Sutton et al., 2009b) is indeed a stochastic gradient method for solving the saddle-point problem (10), although they obtained the saddle-point formulation with different derivations.”
SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation (2017, background): “Later on, it was realized that several of these gradient-based algorithms can be interpreted as solving a primal-dual problem (Mahadevan et al., 2014; Liu et al., 2015; Macua et al., 2015; Dai et al., 2017).”
Multiagent Fully Decentralized Value Function Learning With Linear Convergence Rates (2018, methodology): “Second, while in some instances, the solutions in [15] and [16] may be biased due to the use of the mean square projected Bellman error (MSPBE) as a surrogate cost (this point is further clarified in Section II), the proposed method allows better control of the bias term due to a modification in the”
Distributed off-Policy Actor-Critic Reinforcement Learning with Policy Consensus (2019, methodology): “The works in [12–16] employ distributed optimization methods to evaluate a given ﬁxed policy in multi-agents systems.”
Scalable Bilinear π Learning Using State and Action Features (2018, background): “It should be noted that there is another line of research that studies saddle-point formulations that result from the ﬁxed-point (as opposed to LP) view of the Bellman equation for ﬁxed policy evaluation (Mahadevan et al., 2014; Macua et al., 2015; Du et al., 2017; Dai et al., 2017).”
Diff-DAC: Distributed Actor-Critic for Average Multitask Deep Reinforcement Learning (2017, methodology): “However, Diff-DAC usually achieves higher asymptotic performance and less variance, in both single task and multitask problems, which was also expected due to the already reported enhanced robustness against local optima of diffusion strategies for nonconvex optimization problems (Valcarcel Macua 20”
Primal-Dual Algorithm for Distributed Reinforcement Learning: Distributed GTD (2018, methodology): “The proposed method is mainly motivated by [7], where the GTD was interpreted as a primaldual algorithm using Lagrangian duality theory.”
Provably Convergent Two-Timescale Off-Policy Actor-Critic with Function Approximation (2019, background): “However, their analysis is conducted with the saddle-point formulation of the GTD objective (Liu et al., 2015; Macua et al., 2015) and requires a ﬁxed target policy, which is impractical in our control setting.”
Convergent Tree-Backup and Retrace with Function Approximation (2017, methodology): “Instead of adapting the derivation of Gradient Temporal Difference (GTD) learning from (Sutton et al., 2009c), we use a primal-dual saddle point formulation (Liu et al., 2015; Macua et al., 2015) which facilitates the derivation of sample complexity bounds.”
Diff-DAC: Distributed Actor-Critic for Multitask Deep Reinforcement Learning (2017, background): “In order to ensure that the information flows through the network, we require the following standard conditions on the connectivity matrix C (Valcarcel Macua et al. 2015): C>1 = 1, and clk ≥ 0 for k, l = 1, . . . , N, (8) trace [C] > 0, (9) Cτ = τ, (10) where 1 is a vector of ones.”
Linear convergence of primal-dual gradient methods and their performance in distributed optimization (2019, background): “Algorithms of the form (3) have been applied in various applications including but not limited to wireless systems [2], [3], power systems [4], reinforcement learning [5], and network utility maximization [6], [7].”
A review of cooperative multi-agent deep reinforcement learning (2019, methodology): “[68] 0 Q 1 (L,L) (L,L) (G,G) Consensus Zhang et al., 2018 [170] 1 AC 1 (G,G) (G,L) (L,L) Kar et al., 2013 [60] 1 Q 1 (G,G) (L,L) (L,L) Lee et al., 2018 [74] 1 Q 1 (G,G) (L,L) (L,L) Macua et al., 2015 [84] 1 Q 0 (L,L) (L,L) (G,G) Macua et al., 2018 [85] 1 AC 0 (L,L) (L,L) (L,L) Cassano et al., 2018 [”
Provably Convergent Off-Policy Actor-Critic with Function Approximation (2019, background): “However, their analysis is conducted with the saddle-point formulation of the GTD objective (Liu et al., 2015; Macua et al., 2014) and requires a fixed target policy, which is impractical in our control setting.”