Dual Approximation Policy Optimization

• URL: http://arxiv.org/abs/2410.01249v1
• Date: Wed, 2 Oct 2024 05:49:11 GMT
• Title: Dual Approximation Policy Optimization
• Authors: Zhihan Xiong, Maryam Fazel, Lin Xiao,
• Abstract summary: We propose Dual Approximation Policy Optimization (DAPO), a framework that incorporates general function approximation into policy mirror descent methods. This duality framework has both theoretical and practical implications.
• Score: 20.787309027373208
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose Dual Approximation Policy Optimization (DAPO), a framework that incorporates general function approximation into policy mirror descent methods. In contrast to the popular approach of using the $L_2$-norm to measure function approximation errors, DAPO uses the dual Bregman divergence induced by the mirror map for policy projection. This duality framework has both theoretical and practical implications: not only does it achieve fast linear convergence with general function approximation, but it also includes several well-known practical methods as special cases, immediately providing strong convergence guarantees.

Related papers

• Strongly-polynomial time and validation analysis of policy gradient methods [3.722665817361884]
  This paper proposes a novel termination criterion, termed the advantage gap function, for finite state and action Markov decision processes (MDP) and reinforcement learning (RL) By incorporating this advantage gap function into the design of step size rules, we deriving a new linear rate of convergence that is independent of the stationary state distribution of the optimal policy. This is the first time that such strong convergence properties have been established for policy gradient methods.
  arXiv  Detail & Related papers  (2024-09-28T18:56:48Z)
• Convergence of a L2 regularized Policy Gradient Algorithm for the Multi Armed Bandit [0.0]
  Multi Armed Bandit (MAB) on one hand and the policy gradient approach on the other hand are among the most used frameworks of Reinforcement Learning. We investigate in this work the convergence of such a procedure for the situation when a $L2$ regularization term is present jointly with the'softmax' parametrization.
  arXiv  Detail & Related papers  (2024-02-09T13:10:04Z)
• Provably Convergent Policy Optimization via Metric-aware Trust Region Methods [21.950484108431944]
  Trust-region methods are pervasively used to stabilize policy optimization in reinforcement learning. We exploit more flexible metrics and examine two natural extensions of policy optimization with Wasserstein and Sinkhorn trust regions. We show that WPO guarantees a monotonic performance improvement, and SPO provably converges to WPO as the entropic regularizer diminishes.
  arXiv  Detail & Related papers  (2023-06-25T05:41:38Z)
• Last-Iterate Convergent Policy Gradient Primal-Dual Methods for Constrained MDPs [107.28031292946774]
  We study the problem of computing an optimal policy of an infinite-horizon discounted Markov decision process (constrained MDP) We develop two single-time-scale policy-based primal-dual algorithms with non-asymptotic convergence of their policy iterates to an optimal constrained policy. To the best of our knowledge, this work appears to be the first non-asymptotic policy last-iterate convergence result for single-time-scale algorithms in constrained MDPs.
  arXiv  Detail & Related papers  (2023-06-20T17:27:31Z)
• Local Optimization Achieves Global Optimality in Multi-Agent Reinforcement Learning [139.53668999720605]
  We present a multi-agent PPO algorithm in which the local policy of each agent is updated similarly to vanilla PPO. We prove that with standard regularity conditions on the Markov game and problem-dependent quantities, our algorithm converges to the globally optimal policy at a sublinear rate.
  arXiv  Detail & Related papers  (2023-05-08T16:20:03Z)
• Policy Optimization over General State and Action Spaces [3.722665817361884]
  Reinforcement learning (RL) problems over general state and action spaces are notoriously challenging. We first present a substantial generalization of the recently developed policy mirror descent method to deal with general state and action spaces. We introduce new approaches to incorporate function approximation into this method, so that we do not need to use explicit policy parameterization at all.
  arXiv  Detail & Related papers  (2022-11-30T03:44:44Z)
• Linear Convergence of Natural Policy Gradient Methods with Log-Linear Policies [115.86431674214282]
  We consider infinite-horizon discounted Markov decision processes and study the convergence rates of the natural policy gradient (NPG) and the Q-NPG methods with the log-linear policy class. We show that both methods attain linear convergence rates and $mathcalO (1/epsilon2)$ sample complexities using a simple, non-adaptive geometrically increasing step size.
  arXiv  Detail & Related papers  (2022-10-04T06:17:52Z)
• Proximal Point Imitation Learning [48.50107891696562]
  We develop new algorithms with rigorous efficiency guarantees for infinite horizon imitation learning. We leverage classical tools from optimization, in particular, the proximal-point method (PPM) and dual smoothing. We achieve convincing empirical performance for both linear and neural network function approximation.
  arXiv  Detail & Related papers  (2022-09-22T12:40:21Z)
• Policy Mirror Descent for Regularized Reinforcement Learning: A Generalized Framework with Linear Convergence [60.20076757208645]
  This paper proposes a general policy mirror descent (GPMD) algorithm for solving regularized RL. We demonstrate that our algorithm converges linearly over an entire range learning rates, in a dimension-free fashion, to the global solution.
  arXiv  Detail & Related papers  (2021-05-24T02:21:34Z)
• Provably Correct Optimization and Exploration with Non-linear Policies [65.60853260886516]
  ENIAC is an actor-critic method that allows non-linear function approximation in the critic. We show that under certain assumptions, the learner finds a near-optimal policy in $O(poly(d))$ exploration rounds. We empirically evaluate this adaptation and show that it outperforms priors inspired by linear methods.
  arXiv  Detail & Related papers  (2021-03-22T03:16:33Z)
• Convergence Proof for Actor-Critic Methods Applied to PPO and RUDDER [6.9478331974594045]
  We show convergence of the well known Proximal Policy Optimization (PPO) and of the recently introduced RUDDER. Our results are valid for actor-critic methods that use episodic samples and that have a policy that becomes more greedy during learning.
  arXiv  Detail & Related papers  (2020-12-02T18:47:06Z)

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.