Actor-Critic or Critic-Actor? A Tale of Two Time Scales

• URL: http://arxiv.org/abs/2210.04470v5
• Date: Wed, 12 Jun 2024 09:14:21 GMT
• Title: Actor-Critic or Critic-Actor? A Tale of Two Time Scales
• Authors: Shalabh Bhatnagar, Vivek S. Borkar, Soumyajit Guin,
• Abstract summary: We provide a proof of convergence and compare the two empirically with and without function approximation. Our proposed critic-actor algorithm performs on par with actor-critic in terms of both accuracy and computational effort.
• Score: 5.945710235932345
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We revisit the standard formulation of tabular actor-critic algorithm as a two time-scale stochastic approximation with value function computed on a faster time-scale and policy computed on a slower time-scale. This emulates policy iteration. We observe that reversal of the time scales will in fact emulate value iteration and is a legitimate algorithm. We provide a proof of convergence and compare the two empirically with and without function approximation (with both linear and nonlinear function approximators) and observe that our proposed critic-actor algorithm performs on par with actor-critic in terms of both accuracy and computational effort.

Related papers

• Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximation [5.945710235932345]
  We present the first two-timescale critic-actor algorithm with function approximation in the long-run average reward setting. A notable feature of our analysis is that unlike recent single-timescale actor-critic algorithms, we present a complete convergence analysis of our scheme.
  arXiv  Detail & Related papers  (2024-02-02T12:48:49Z)
• Learning the Positions in CountSketch [49.57951567374372]
  We consider sketching algorithms which first compress data by multiplication with a random sketch matrix, and then apply the sketch to quickly solve an optimization problem. In this work, we propose the first learning-based algorithms that also optimize the locations of the non-zero entries.
  arXiv  Detail & Related papers  (2023-06-11T07:28:35Z)
• Efficient distributed representations with linear-time attention scores normalization [3.8673630752805437]
  We propose a linear-time approximation of the attention score normalization constants for embedding vectors with bounded norms. The accuracy of our estimation formula surpasses competing kernel methods by even orders of magnitude. The proposed algorithm is highly interpretable and easily adapted to an arbitrary embedding problem.
  arXiv  Detail & Related papers  (2023-03-30T15:48:26Z)
• Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality [131.45028999325797]
  We develop a doubly robust off-policy AC (DR-Off-PAC) for discounted MDP. DR-Off-PAC adopts a single timescale structure, in which both actor and critics are updated simultaneously with constant stepsize. We study the finite-time convergence rate and characterize the sample complexity for DR-Off-PAC to attain an $epsilon$-accurate optimal policy.
  arXiv  Detail & Related papers  (2021-02-23T18:56:13Z)
• Variance Penalized On-Policy and Off-Policy Actor-Critic [60.06593931848165]
  We propose on-policy and off-policy actor-critic algorithms that optimize a performance criterion involving both mean and variance in the return. Our approach not only performs on par with actor-critic and prior variance-penalization baselines in terms of expected return, but also generates trajectories which have lower variance in the return.
  arXiv  Detail & Related papers  (2021-02-03T10:06:16Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)
• Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms [58.57004511121862]
  Actor-critic (AC) and natural actor-critic (NAC) algorithms are often executed in two ways for finding optimal policies. We show that two time-scale AC requires the overall sample complexity at the order of $mathcalO(epsilon-2.5log3(epsilon-1))$ to attain an $epsilon$-accurate stationary point. We develop novel techniques for bounding the bias error of the actor due to dynamically changing Markovian sampling.
  arXiv  Detail & Related papers  (2020-05-07T15:42:31Z)
• A Finite Time Analysis of Two Time-Scale Actor Critic Methods [87.69128666220016]
  We provide a non-asymptotic analysis for two time-scale actor-critic methods under non-i.i.d. setting. We prove that the actor-critic method is guaranteed to find a first-order stationary point. This is the first work providing finite-time analysis and sample complexity bound for two time-scale actor-critic methods.
  arXiv  Detail & Related papers  (2020-05-04T09:45:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.