Pith. sign in

REVIEW 2 major objections 4 minor 58 references

Fast Multi-Agent Temporal-Difference Learning via Homotopy Stochastic Primal-Dual Optimization

T0 review · 2 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A distributed homotopy primal-dual algorithm achieves an O(log^2 T / T) optimality gap for multi-agent TD learning.

desk verdict A genuinely promising homotopy primal-dual algorithm for distributed GTD, but Theorem 1 as stated is not proven: the key lemma's product condition is missing and the displayed log^2 rate hides an extra log. read the letter →

arxiv 1908.02805 v4 pith:ICE2BBPN submitted 2019-08-07 math.OC cs.LGcs.MA

Dongsheng Ding , Xiaohan Wei , Zhuoran Yang , Zhaoran Wang , Mihailo R. Jovanović This is my paper · ORCID
classification math.OCcs.LGcs.MA MSC 90C2590C1590C47
keywords multi-agentreinforcementlearningtemporal-differencemean-squareprojectedBellmanerrorstochasticprimal-dualmethodhomotopyMarkoviansamplingdistributedoptimizationpolicyevaluation
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper develops a distributed algorithm for multi-agent temporal-difference learning in which agents share observed states but keep local actions and rewards private, and it proves a finite-time guarantee for minimizing the mean-square projected Bellman error (MSPBE) under Markovian, not i.i.d., sampling. The central claim is that the proposed distributed homotopy primal-dual (DHPD) algorithm attains an expected optimality gap of $O(\log^2 T / T)$ after $T$ total iterations, improving the previous best $O(1/\sqrt{T})$ for distributed gradient temporal-difference methods. This matters because policy evaluation is the inner loop of many multi-agent reinforcement learning systems: a faster rate means the same number of samples buys a more accurate value-function estimate, with the cost of network size and topology made explicit.

What carries the argument

The central object is the MSPBE objective $f(x) = \tfrac{1}{2}\|Ax - b\|^2_{C^{-1}}$ together with its Fenchel-dual saddle point reformulation, in which each local cost $f_j(x) = \max_{y_j \in Y}\, [ y_j^T(Ax - b_j) - \tfrac{1}{2} y_j^T C y_j ]$. This reformulation is what makes the problem amenable to stochastic gradient sampling, because products and inverses of expectations become linear in the samples. The proof is carried by three mechanisms: a doubly stochastic mixing matrix $W$ that performs consensus averaging in the primal updates; distributed dual averaging that controls the network disagreement term; and a homotopy restart schedule ($\eta_{k+1} = \eta_k/2$, $T_{k+1} = 2T_k$) that, combined with strong convexity in $x$ and strong concavity in $y$, turns the $O(1/\sqrt{T})$ primal-dual gap into an $O(1/T)$ gap. The Markovian part of the analysis splits each inner loop into a stationary segment and a short mixing tail of length $\tau$, leveraging a total-variation mixing-time bound.

What would settle it

Run DHPD on a fixed policy-evaluation problem with a feature dictionary chosen so that $A^T C^{-1} A$ has a known small or zero smallest eigenvalue, and compare the empirical optimality gap to $1/T$ and $1/\sqrt{T}$ curves. If the gap still decays as roughly $1/T$ when $\rho_x$ is zero, the strong-convexity assumption is not load-bearing; if the decay slows visibly as $\rho_x$ shrinks, that confirms Theorem 1's rate is tied to Assumption 4 rather than to the algorithm's averaging structure.

Watch

Extended reading notes

Core claim

The paper claims that minimizing the mean-square projected Bellman error over a connected network can be recast, via Fenchel duality, as a decentralized stochastic saddle point problem whose objective is convex in the parameter $x$ and strongly concave in the dual variables $y_j$. The DHPD algorithm solves this problem with distributed dual averaging for the primal update, local dual updates, and a homotopy schedule that halves the learning rate and doubles the inner horizon after each round. Its Theorem 1 bounds the averaged expected optimality gap by $C_1 G(RL+G)\log^2(T\sqrt{N})/(T(1-\sigma_2(W))) + C_2 G(G+RL)(1+T_1)/T$, giving $O(\log^2 T / T)$ when the initial horizon is constant. This is the paper's advertised improvement over the $O(1/\sqrt{T})$ rate of prior distributed GTD algorithms, and it holds with samples drawn from a causal on-policy Markov trajectory rather than from the stationary distribution directly.

Load-bearing premise

The proof requires each local cost $f_j(x)$ to be strongly convex with a known curvature $\rho_x > 0$, which holds only when the feature matrix $A$ is full column rank and $A^T C^{-1} A$ is positive definite; with redundant or ill-conditioned features, $\rho_x$ is zero or tiny, and the $O(\log^2 T / T)$ rate is not delivered.

Editorial extensions

If this is right

  • For a single agent, DHPD reduces to a fast GTD-type method whose $O(\log^2 T / T)$ bound improves the earlier $O(1/\sqrt{T})$ finite-sample guarantees in the Markov setting.
  • On a ring network the bound scales as $O(N^2 \log^2 T / T)$, so the price of decentralization is explicit: the same accuracy needs roughly a factor $N^2$ more iterations as the number of agents grows.
  • The rate matches, up to logarithms, the optimal $O(1/T)$ for stochastic convex optimization, indicating that further gains would require new structure rather than parameter tuning.
  • The per-iteration cost is $O(d N^2)$ ($O(d)$ per agent), so the faster convergence is not purchased at the price of prohibitive communication or computation.
  • Because the guarantee covers Markovian on-policy sampling, the algorithm applies directly to online data streams where agents cannot resample from the stationary distribution.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A testable consequence the paper does not draw: on feature dictionaries that are redundant or ill-conditioned, $\rho_x$ is small, and the observed convergence should degrade from roughly $1/T$ toward $1/\sqrt{T}$; whitening the features before running DHPD would directly test whether strong convexity is the operative mechanism.
  • The homotopy restart schedule is portable: any distributed stochastic saddle point problem with a strongly convex primal and strongly concave dual could inherit the $O(1/T)$ rate, and the same schedule could be tuned to the spectral gap of the network rather than to a worst-case mixing time.
  • The paper's assumption of a doubly stochastic mixing matrix excludes directed or time-varying networks; for those, the consensus error term changes, and the rate would likely slow unless the restart schedule is adapted.
  • An empirical diagnostic not reported: plotting the optimality gap against $1/T$ for different values of $\rho_x$ would show a phase transition that separates the regime where Theorem 1 applies from the regime where the old $O(1/\sqrt{T})$ bound is the best available description.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper studies distributed policy evaluation in multi-agent reinforcement learning with linear function approximation and Markovian state sampling. It formulates the MSPBE minimization as a distributed stochastic saddle point problem via Fenchel duality, and proposes the Distributed Homotopy Primal-Dual (DHPD) algorithm, which combines distributed dual averaging with homotopy-style restarting (halving the stepsize and doubling the horizon in each round). The main result, Theorem 1, claims an expected optimality-gap bound of order C1 G(RL+G) log^2(T sqrt(N)) / (T(1-sigma_2(W))) + C2 G(G+RL)(1+T1)/T for the final averaged iterates, under Assumptions 1-6, provided eta_1 >= 1/(4/rho_y + 2/rho_x) and T1 >= tau = Theta(log T). This is presented as improving the prior O(1/sqrt(T)) rate for distributed GTD. The paper also reports Mountain Car experiments for N=1 and N=100.

Significance. If Theorem 1 were established as stated, the paper would make a meaningful contribution: it combines homotopy restarting with distributed primal-dual methods, gives an explicit dependence on the network spectral gap, and handles Markovian sampling without an i.i.d. assumption. The paper is self-contained, with clearly stated assumptions and a proof assembled from lemmas; the algorithm is simple and the experiments support the qualitative benefit of the homotopy schedule. However, the main theorem as stated is not supported by the proof: the proof requires stronger parameter conditions, and the final rate derivation omits extra logarithmic factors introduced by the restart schedule. These issues are potentially repairable, but they require a careful re-derivation and a corrected theorem statement.

major comments (2)
  1. [Section III-C, Theorem 1 vs Section IV-C] The theorem states the bound for any eta_1 >= 1/(4/rho_y + 2/rho_x) and T1 >= tau, but the proof of the recurrence for the averaged surrogate gap requires eta_1 >= 4/rho' = 64/rho_y + 32/rho_x, as explicitly used in the sentence after Eq. (23) ('Since eta_1 >= 4/rho' ...'). Moreover, Lemma 9 requires rho_x eta_k T_k >= 16 in every round k. Because eta_k T_k = eta_1 T_1 is constant across rounds, this is a product condition rho_x eta_1 T_1 >= 16 that is absent from the theorem's hypotheses. For instance, with rho_x = rho_y = 1, T = 10^6, and T1 = tau ~ 14, the theorem's lower bound eta_1 >= 1/6 gives rho_x eta_1 T1 ~ 2.3 < 16, so Lemma 9 does not apply. Thus Theorem 1 is not established as stated; the parameter conditions in the theorem and the proof must be reconciled.
  2. [Section IV-C, unrolling of recurrence (24)] The final displayed bound in the proof of Theorem 1 claims the order C1 G(RL+G) log^2(T sqrt(N)) / (T(1-sigma_2(W))) + C2 G(G+RL)(1+T1)/T. However, the network term inherited from Lemma 2 contains (G/T_K) * (sum_{l=1}^K eta_l T_l) * log(sqrt(N) T_K) / (1-sigma_2(W)) = G K eta_1 T_1 log(...) / (T_K (1-sigma_2(W))). Since T_K >= T/2, K <= 1 + log(T/T1), and T1 >= tau = Theta(log T), this term is Theta(G log^3 T / (T(1-sigma_2(W)))) for the natural choice T1 = tau recommended in Remark 4. The proof's step 'K <= 1 + log(T/T1)' and the subsequent absorption of factors into the constants C1 and C2 do not resolve this, because C1 and C2 are claimed to be independent of T. The stated O(log^2 T / T) rate is therefore not derived; the proof yields an extra logarithmic factor unless T1 is O(1), which is incompatible with T1 >= tau. The rate needs to be re-derived with explicit dependence on T1, K, and eta_1.
minor comments (4)
  1. [Abstract and Section I-B] The abstract and the introduction claim an O(1/T) convergence rate, whereas Theorem 1 states a bound of order log^2(T sqrt(N))/T. Please align the abstract and the claimed rate with the precise theorem statement.
  2. [Remark 4] Remark 4 recommends choosing T1 = tau and claims this gives O(log^2(T sqrt(N))/T). In view of Major Comment 2, this choice makes the network term of order O(log^3 T / T) as the proof currently stands; the remark is not justified by the proof.
  3. [Section IV-C, parameter consistency] The sentence 'Since eta_1 >= 4/rho' and T1 >= 1, we have rho' eta_k T_k >= 4 ... Clearly, the assumption rho_x eta_k T_k >= 16 holds' introduces a condition on eta_1 that is not stated in Theorem 1. The theorem and the proof should state the same condition on eta_1, and the role of the product condition rho_x eta_1 T_1 >= 16 should be made explicit in both places.
  4. [Assumption 4 / Section III-B] The strong convexity parameter rho_x of the local MSPBE is load-bearing for the restart schedule through the condition rho_x eta_k T_k >= 16. The paper does not discuss how rho_x can be verified or estimated in practice, nor the behavior when features are redundant or ill-conditioned so that rho_x is zero or tiny. A remark on this limitation would help the reader assess the applicability of the result.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 1 is derived from Assumptions 1–6 with self-contained proof machinery; cited external tools are used as standard lemmas, not as unfalsifiable inputs.

full rationale

The paper's central claim is a finite-time convergence bound for a distributed homotopy primal-dual algorithm, proven from explicitly stated Assumptions 1–6. The proof chain is self-contained: Lemma 2 cites a standard distributed averaging bound from Duchi, Agarwal, and Wainwright, Lemma 3 cites Zinkevich's online convex programming lemma, and Lemma 4 proves a martingale concentration bound directly. The homotopy restart schedule is analyzed rather than assumed to give the rate; Lemma 9 derives a recursion under explicit hypotheses, and the final bound is obtained by unrolling that recursion. No parameter is fitted to the experimental data and then renamed as a prediction; the experiments are illustrative and not used as evidence for the theorem. The cited works by the authors' group (e.g., [14], [55]) appear in the introduction and experiments, but they are not load-bearing for the proof: [55] is cited only as an example of other fast-rate homotopy results, and [14] is used only to generate the Mountain Car dataset. The only apparent issue in the proof is a gap between the theorem's stated condition on eta_1 and the stronger condition eta_1 >= 4/rho' used in Section IV-C to ensure rho_x eta_k T_k >= 16 in Lemma 9; this is a correctness/parameter-regime concern, not circularity, because it does not make the conclusion an input of the derivation. The limiting remarks in Section VI concern nonlinearity, synchronous communication, and agent failures; none of these assert or imply that the proof assumes its own conclusion. Overall, the derivation is logical and independent of its target result, so the circularity score is 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The derivation rests on six stated assumptions from RL and optimization: uniform ergodicity of the state Markov chain, full-rank feature matrix A, positive definite covariance C, convex compact domains, strong concavity of the saddle function in the dual variable with strong convexity of the primal cost, and bounded Lipschitz stochastic gradients. No new physical or mathematical entities are introduced.

assumptions (6)
  • domain assumption Assumption 1: The Markov chain associated with the policy pi is aperiodic and irreducible, yielding geometric mixing with known constants Gamma and rho.
    This ensures a unique stationary distribution and the mixing-time bound in equation (12), which the ergodic analysis repeatedly uses.
  • domain assumption Assumption 2: The matrix A is full rank and C is positive definite.
    This makes the MSPBE objective strongly convex and guarantees a unique minimizer; it is the basis for Assumption 4 and for the homotopy restart argument.
  • domain assumption Assumption 3: X and Y are convex compact sets containing the origin with radius R.
    The projections in Algorithm 1 require these bounded domains, and R appears in the error bounds.
  • domain assumption Assumption 4: psi_j is convex in x and strongly concave in y, and f_j(x) = max_y psi_j(x,y) is strongly convex in x.
    Strong convexity in the primal variable is the engine of the O(1/T) rate via the recursion in Lemma 9; it is not implied by the saddle function's own convexity in x.
  • domain assumption Assumption 5: The stochastic gradients are bounded by G with probability one.
    Bounded gradients are used in Lemmas 2, 7, 8 and the martingale concentration bound in Lemma 4.
  • domain assumption Assumption 6: The stochastic gradients are Lipschitz in x and y with constant L.
    Lipschitz continuity is used to bound differences of gradients at shifted time indices in Lemma 8.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fast Multi-Agent Temporal-Difference Learning via Homotopy Stochastic Primal-Dual Optimization." pith.science (2026). https://pith.science/paper/ICE2BBPN

@misc{pith2026190802805,
  author       = {Pith},
  title        = {Pith review of: Fast Multi-Agent Temporal-Difference Learning via Homotopy Stochastic Primal-Dual Optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ICE2BBPN}},
  note         = {Machine review of arXiv:1908.02805}
}
abstract

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.

Figures

Figures reproduced from arXiv: 1908.02805 by the authors.

Figure 1
Figure 1. Interaction between environment and agents. There are six agents communicated over a connected graph [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Convergence speed comparison for the centralized case with [PITH_FULL_IMAGE:figures/full_fig_p022_2.png] view at source ↗
Figure 3
Figure 3. Convergence speed comparison for the distributed case with [PITH_FULL_IMAGE:figures/full_fig_p022_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

58 extracted references · 53 canonical work pages

  1. [13]

    Primal-dual algorithm for distributed reinforcement learning: distributed GTD,

    D. Lee, H. Yoon, and N. Hovakimyan, “Primal-dual algorithm for distributed reinforcement learning: distributed GTD,” in Proceedings of the IEEE Conference on Decision and Control , 2018, pp. 1967–1972

    work page 2018

  2. [48]

    Stochastic primal-dual algorithm for distributed gradient temporal difference learning,

    D. Lee, H. Yoon, V . Cichella, and N. Hovakimyan, “Stochastic primal-dual algorithm for distributed gradient temporal difference learning,” arXiv preprint arXiv:1805.07918 , 2018

    arXiv 2018

  3. [1]

    R. S. Sutton and A. G. Barto, Reinforcement learning: An introduction . MIT press, 2018

    2018

  4. [2]

    Learning to predict by the methods of temporal differences,

    R. S. Sutton, “Learning to predict by the methods of temporal differences,” Machine Learning, vol. 3, no. 1, pp. 9–44, 1988

    1988

  5. [3]

    D. P. Bertsekas and J. N. Tsitsiklis, Neuro-dynamic programming. Athena Scientific Belmont, MA, 1996, vol. 5

    work page 1996

  6. [4]

    Residual algorithms: reinforcement learning with function approximation,

    L. Baird, “Residual algorithms: reinforcement learning with function approximation,” in Proceedings of the International Conference on Machine Learning, 1995, pp. 30–37

    work page 1995

  7. [5]

    Human-level control through deep reinforcement learning,

    V . Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski et al., “Human-level control through deep reinforcement learning,” Nature, vol. 518, no. 7540, p. 529, 2015

    work page 2015

  8. [6]

    Mastering the game of Go with deep neural networks and tree search,

    D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V . Panneershelvam, M. Lanctot et al., “Mastering the game of Go with deep neural networks and tree search,” Nature, vol. 529, no. 7587, p. 484, 2016

    work page 2016

Show all 58 references
  1. [7]

    Residential energy management in smart grid: A Markov decision process-based approach,

    S. Misra, A. Mondal, S. Banik, M. Khatua, S. Bera, and M. S. Obaidat, “Residential energy management in smart grid: A Markov decision process-based approach,” in Proceedings of the IEEE International Conference on Green Computing and Communications and IEEE Internet of things ...

    2013

  2. [8]

    Multiagent reinforcement learning for urban traffic control using coordination graphs,

    L. Kuyer, S. Whiteson, B. Bakker, and N. Vlassis, “Multiagent reinforcement learning for urban traffic control using coordination graphs,” in Proceedings of the Joint European Conference on Machine Learning and Knowledge Discovery in Databases , 2008, pp. 656–671

    2008

  3. [9]

    A distributed actor-critic algorithm and applications to mobile sensor network coordination problems,

    P. Pennesi and I. C. Paschalidis, “A distributed actor-critic algorithm and applications to mobile sensor network coordination problems,” IEEE Trans. Autom. Control , vol. 55, no. 2, pp. 492–497, 2010

    2010

  4. [10]

    Reinforcement learning in robotics: A survey,

    J. Kober, J. A. Bagnell, and J. Peters, “Reinforcement learning in robotics: A survey,” Int. J. Robotics Res., vol. 32, no. 11, pp. 1238–1274, 2013

    2013

  5. [11]

    Distributed policy evaluation under multiple behavior strategies,

    S. V . Macua, J. Chen, S. Zazo, and A. H. Sayed, “Distributed policy evaluation under multiple behavior strategies,” IEEE Trans. Autom. Control, vol. 60, no. 5, pp. 1260–1274, 2014

    2014

  6. [12]

    Distributed reinforcement learning via gossip,

    A. Mathkar and V . S. Borkar, “Distributed reinforcement learning via gossip,” IEEE Trans. Autom. Control, vol. 62, no. 3, pp. 1465–1470, 2016

    2016

  7. [14]

    Multi-agent reinforcement learning via double averaging primal-dual optimization,

    H.-T. Wai, Z. Yang, Z. Wang, and M. Hong, “Multi-agent reinforcement learning via double averaging primal-dual optimization,” in Proceedings of the Advances in Neural Information Processing Systems , 2018, pp. 9649–9660

    2018

  8. [15]

    Multi-agent fully decentralized off-policy learning with linear convergence rates,

    L. Cassano, K. Yuan, and A. H. Sayed, “Multi-agent fully decentralized off-policy learning with linear convergence rates,” arXiv preprint arXiv:1810.07792, 2018

    2018 arXiv

  9. [16]

    Finite-time analysis of distributed TD(0) with linear function approximation on multi-agent reinforcement learning,

    T. Doan, S. Maguluri, and J. Romberg, “Finite-time analysis of distributed TD(0) with linear function approximation on multi-agent reinforcement learning,” in Proceedings of the International Conference on Machine Learning , 2019, pp. 1626–1635

    2019

  10. [17]

    Finite-time performance of distributed temporal difference learning with linear function approximation,

    T. T. Doan, S. T. Maguluri, and J. Romberg, “Finite-time performance of distributed temporal difference learning with linear function approximation,” arXiv preprint arXiv:1907.12530 , 2019

    1907 arXiv

  11. [18]

    Finite-sample analysis of decentralized temporal-difference learning with linear function approximation,

    J. Sun, G. Wang, G. B. Giannakis, Q. Yang, and Z. Yang, “Finite-sample analysis of decentralized temporal-difference learning with linear function approximation,” arXiv preprint arXiv:1911.00934 , 2019

    1911 arXiv

  12. [19]

    Asynchronous policy evaluation in distributed reinforcement learning over networks,

    X. Sha, J. Zhang, K. Zhang, K. You, and T. Bas ¸ar, “Asynchronous policy evaluation in distributed reinforcement learning over networks,” arXiv preprint arXiv:2003.00433 , 2020

    2003 arXiv

  13. [20]

    An analysis of temporal-difference learning with function approximation,

    J. N. Tsitsiklis and B. Van Roy, “An analysis of temporal-difference learning with function approximation,” IEEE Trans. Automat. Control, vol. 42, no. 5, pp. 674–690, 1997

    1997

  14. [21]

    Szepesv ´ari, Algorithms for Reinforcement Learning

    C. Szepesv ´ari, Algorithms for Reinforcement Learning . Morgan and Claypool Publishers, 2010

    2010

  15. [22]

    Linear least-squares algorithms for temporal difference learning,

    S. J. Bradtke and A. G. Barto, “Linear least-squares algorithms for temporal difference learning,” Machine learning, vol. 22, no. 1-3, pp. 33–57, 1996

    1996

  16. [23]

    A convergent O(n) temporal-difference algorithm for off-policy learning with linear function approximation,

    R. S. Sutton, H. R. Maei, and C. Szepesv ´ari, “A convergent O(n) temporal-difference algorithm for off-policy learning with linear function approximation,” in Proceedings of the Advances in Neural Information Processing Systems , 2009, pp. 1609–1616

    2009

  17. [24]

    Fast gradient-descent methods for temporal- difference learning with linear function approximation,

    R. S. Sutton, H. R. Maei, D. Precup, S. Bhatnagar, D. Silver, C. Szepesv ´ari, and E. Wiewiora, “Fast gradient-descent methods for temporal- difference learning with linear function approximation,” in Proceedings of the International Conference on Machine Learning , 2009, pp. 993–1000

    2009

  18. [25]

    The ode method for convergence of stochastic approximation and reinforcement learning,

    V . S. Borkar and S. P. Meyn, “The ode method for convergence of stochastic approximation and reinforcement learning,” SIAM J. Control Optim., vol. 38, no. 2, pp. 447–469, 2000

    2000

  19. [26]

    Finite sample analyses for TD (0) with function approximation,

    G. Dalal, B. Sz ¨or´enyi, G. Thoppe, and S. Mannor, “Finite sample analyses for TD (0) with function approximation,” in Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence , 2018

    2018

  20. [27]

    Finite sample analysis of two-time scale stochastic approximation with applications to reinforcement learning,

    G. Dalal, G. Thoppe, B. Sz ¨or´enyi, and S. Mannor, “Finite sample analysis of two-time scale stochastic approximation with applications to reinforcement learning,” in Proceedings of the Conference on Learning Theory , 2018, pp. 1199–1233

    2018

  21. [28]

    Linear stochastic approximation: How far does constant step-size and iterate averaging go?

    C. Lakshminarayanan and C. Szepesvari, “Linear stochastic approximation: How far does constant step-size and iterate averaging go?” in International Conference on Artificial Intelligence and Statistics , 2018, pp. 1347–1355. September 3, 2020 DRAFT 26

    2018

  22. [29]

    A finite time analysis of temporal difference learning with linear function approximation,

    J. Bhandari, D. Russo, and R. Singal, “A finite time analysis of temporal difference learning with linear function approximation,” in Proceedings of the Conference on Learning Theory , 2018, pp. 1691–1692

    2018

  23. [30]

    Finite-time error bounds for linear stochastic approximation and TD learning,

    R. Srikant and L. Ying, “Finite-time error bounds for linear stochastic approximation and TD learning,” in Proceedings of the Conference on Learning Theory , 2019, pp. 1–28

    2019

  24. [31]

    Finite-sample analysis for SARSA and Q-learning with linear function approximation,

    S. Zou, T. Xu, and Y . Liang, “Finite-sample analysis for SARSA and Q-learning with linear function approximation,” in Proceedings of the Advances In Neural Information Processing Systems , 2019, pp. 8665–8675

    2019

  25. [32]

    Characterizing the exact behaviors of temporal difference learning algorithms using markov jump linear system theory,

    B. Hu and U. Syed, “Characterizing the exact behaviors of temporal difference learning algorithms using markov jump linear system theory,” in Advances in Neural Information Processing Systems , 2019, pp. 8477–8488

    2019

  26. [33]

    Finite-sample analysis of proximal gradient TD algorithms,

    B. Liu, J. Liu, M. Ghavamzadeh, S. Mahadevan, and M. Petrik, “Finite-sample analysis of proximal gradient TD algorithms,” in Proceedings of the Conference on Uncertainty in Artificial Intelligence , 2015, pp. 504–513

    2015

  27. [34]

    Robust stochastic approximation approach to stochastic programming,

    A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro, “Robust stochastic approximation approach to stochastic programming,” SIAM J. Optim., vol. 19, no. 4, pp. 1574–1609, 2009

    2009

  28. [35]

    Finite sample analysis of the GTD policy evaluation algorithms in Markov setting,

    Y . Wang, W. Chen, Y . Liu, Z.-M. Ma, and T.-Y . Liu, “Finite sample analysis of the GTD policy evaluation algorithms in Markov setting,” in Proceedings of the Advances in Neural Information Processing Systems , 2017, pp. 5504–5513

    2017

  29. [36]

    Convergent TREE BACKUP and RETRACE with function approximation,

    A. Touati, P.-L. Bacon, D. Precup, and P. Vincent, “Convergent TREE BACKUP and RETRACE with function approximation,” in Proceedings of the International Conference on Machine Learning , 2018, pp. 4962–4971

    2018

  30. [37]

    Multi-agent temporal-difference learning with linear function approximation: Weak convergence under time-varying network topologies,

    M. S. Stankovi ´c and S. S. Stankovi ´c, “Multi-agent temporal-difference learning with linear function approximation: Weak convergence under time-varying network topologies,” in Proceedings of the American Control Conference , 2016, pp. 167–172

    2016

  31. [38]

    Gossip algorithms: Design, analysis and applications,

    S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah, “Gossip algorithms: Design, analysis and applications,” in Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies , vol. 3, 2005, pp. 1653–1664

    2005

  32. [39]

    Finite-time performance of distributed two-time-scale stochastic approximation,

    T. T. Doan and J. Romberg, “Finite-time performance of distributed two-time-scale stochastic approximation,” arXiv preprint arXiv:1912.10155, 2019

    1912 arXiv

  33. [40]

    On the averaged stochastic approximation for linear regression,

    L. Gy ¨orfi and H. Walk, “On the averaged stochastic approximation for linear regression,” SIAM J. Control Optim. , vol. 34, no. 1, pp. 31–61, 1996

    1996

  34. [41]

    Fully decentralized multi-agent reinforcement learning with networked agents,

    K. Zhang, Z. Yang, H. Liu, T. Zhang, and T. Basar, “Fully decentralized multi-agent reinforcement learning with networked agents,” in Proceedings of the International Conference on Machine Learning , 2018, pp. 5867–5876

    2018

  35. [42]

    Multi-agent reinforcement learning: A selective overview of theories and algorithms,

    K. Zhang, Z. Yang, and T. Bas ¸ar, “Multi-agent reinforcement learning: A selective overview of theories and algorithms,” arXiv preprint arXiv:1911.10635, 2019

    1911 arXiv

  36. [43]

    Decentralized multi-agent reinforcement learning with networked agents: Recent advances,

    ——, “Decentralized multi-agent reinforcement learning with networked agents: Recent advances,” arXiv preprint arXiv:1912.03821, 2019

    1912 arXiv

  37. [44]

    Optimization for reinforcement learning: From a single agent to cooperative agents,

    D. Lee, N. He, P. Kamalaruban, and V . Cevher, “Optimization for reinforcement learning: From a single agent to cooperative agents,” IEEE Signal Process Mag. , vol. 37, no. 3, pp. 123–135, 2020

    2020

  38. [45]

    Dual averaging for distributed optimization: Convergence analysis and network scaling,

    J. C. Duchi, A. Agarwal, and M. J. Wainwright, “Dual averaging for distributed optimization: Convergence analysis and network scaling,” IEEE Trans. Autom. Control , vol. 57, no. 3, pp. 592–606, 2012

    2012

  39. [46]

    A proximal-gradient homotopy method for the sparse least-squares problem,

    L. Xiao and T. Zhang, “A proximal-gradient homotopy method for the sparse least-squares problem,” SIAM J. Optim. , vol. 23, no. 2, pp. 1062–1091, 2013

    2013

  40. [47]

    Information-theoretic lower bounds on the oracle complexity of convex optimization,

    A. Agarwal, M. J. Wainwright, P. L. Bartlett, and P. K. Ravikumar, “Information-theoretic lower bounds on the oracle complexity of convex optimization,” in Proceedings of the Advances in Neural Information Processing Systems , 2009, pp. 1–9

    2009

  41. [49]

    Ergodic mirror descent,

    J. C. Duchi, A. Agarwal, M. Johansson, and M. I. Jordan, “Ergodic mirror descent,” SIAM J. Optim., vol. 22, no. 4, pp. 1549–1578, 2012

    2012

  42. [50]

    D. A. Levin and Y . Peres, Markov chains and mixing times . American Mathematical Soc., 2017, vol. 107

    2017

  43. [51]

    Distributed subgradient methods for multi-agent optimization,

    A. Nedic and A. Ozdaglar, “Distributed subgradient methods for multi-agent optimization,” IEEE Trans. Autom. Control , vol. 54, no. 1, p. 48, 2009

    2009

  44. [52]

    Distributed strongly convex optimization,

    K. I. Tsianos and M. G. Rabbat, “Distributed strongly convex optimization,” in Proceedings of the Allerton Conference on Communication, Control, and Computing , 2012, pp. 593–600

    2012

  45. [53]

    RSG: Beating subgradient method without smoothness and strong convexity,

    T. Yang and Q. Lin, “RSG: Beating subgradient method without smoothness and strong convexity,” The Journal of Machine Learning Research, vol. 19, no. 1, pp. 236–268, 2018

    2018

  46. [54]

    Homotopy smoothing for non-smooth problems with lower complexity than O (1/ϵ),

    Y . Xu, Y . Yan, Q. Lin, and T. Yang, “Homotopy smoothing for non-smooth problems with lower complexity than O (1/ϵ),” in Proceedings of the Advances In Neural Information Processing Systems , 2016, pp. 1208–1216

    2016

  47. [55]

    Solving non-smooth constrained programs with lower complexity than O (1/ε): A primal-dual homotopy smoothing approach,

    X. Wei, H. Yu, Q. Ling, and M. Neely, “Solving non-smooth constrained programs with lower complexity than O (1/ε): A primal-dual homotopy smoothing approach,” in Proceedings of the Advances in Neural Information Processing Systems , 2018, pp. 3999–4009

    2018

  48. [56]

    Online convex programming and generalized infinitesimal gradient ascent,

    M. Zinkevich, “Online convex programming and generalized infinitesimal gradient ascent,” in Proceedings of the International Conference on Machine Learning , 2003, pp. 928–936

    2003

  49. [57]

    Subgradient methods for saddle-point problems,

    A. Nedi ´c and A. Ozdaglar, “Subgradient methods for saddle-point problems,” J. Optim. Theory App. , vol. 142, no. 1, pp. 205–228, 2009

    2009

  50. [58]

    Optimum bounds for the distributions of martingales in Banach spaces,

    I. Pinelis, “Optimum bounds for the distributions of martingales in Banach spaces,” The Annals of Probability, vol. 22, no. 4, pp. 1679–1706, 1994. September 3, 2020 DRAFT

    1994

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.