Essentially Sharp Estimates on the Entropy Regularization Error in Discrete Discounted Markov Decision Processes

• URL: http://arxiv.org/abs/2406.04163v2
• Date: Tue, 25 Jun 2024 10:26:49 GMT
• Title: Essentially Sharp Estimates on the Entropy Regularization Error in Discrete Discounted Markov Decision Processes
• Authors: Johannes Müller, Semih Cayci,
• Abstract summary: We show that for entropy-regularized natural policy gradient methods the overall error decays exponentially in the square root of the number of improving existing sublinear guarantees.
• Score: 4.714840786221651
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the error introduced by entropy regularization of infinite-horizon discrete discounted Markov decision processes. We show that this error decreases exponentially in the inverse regularization strength both in a weighted KL-divergence and in value with a problem-specific exponent. We provide a lower bound matching our upper bound up to a polynomial factor. Our proof relies on the correspondence of the solutions of entropy-regularized Markov decision processes with gradient flows of the unregularized reward with respect to a Riemannian metric common in natural policy gradient methods. Further, this correspondence allows us to identify the limit of the gradient flow as the generalized maximum entropy optimal policy, thereby characterizing the implicit bias of the Kakade gradient flow which corresponds to a time-continuous version of the natural policy gradient method. We use this to show that for entropy-regularized natural policy gradient methods the overall error decays exponentially in the square root of the number of iterations improving existing sublinear guarantees.

Related papers

• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  Proximal point methods have attracted considerable interest owing to their numerical stability and robustness against imperfect tuning. This paper presents a comprehensive analysis of a broad range of variations of the proximal point method (SPPM)
  arXiv  Detail & Related papers  (2024-05-24T21:09:19Z)
• A Fisher-Rao gradient flow for entropy-regularised Markov decision processes in Polish spaces [10.777806006475297]
  We study the global convergence of a Fisher-Rao policy gradient flow for infinite-horizon entropy-regularised Markov decision processes with Polish state and action space. We establish the global well-posedness of the gradient flow and demonstrate its exponential convergence to the optimal policy.
  arXiv  Detail & Related papers  (2023-10-04T16:41:36Z)
• First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
  We present a unified approach for the theoretical analysis of first-order variation methods. Our approach covers both non-linear gradient and strongly Monte Carlo problems. We provide bounds that match the oracle strongly in the case of convex method optimization problems.
  arXiv  Detail & Related papers  (2023-05-25T11:11:31Z)
• On the Importance of Gradient Norm in PAC-Bayesian Bounds [92.82627080794491]
  We propose a new generalization bound that exploits the contractivity of the log-Sobolev inequalities. We empirically analyze the effect of this new loss-gradient norm term on different neural architectures.
  arXiv  Detail & Related papers  (2022-10-12T12:49:20Z)
• On the Convergence Rates of Policy Gradient Methods [9.74841674275568]
  We consider geometrically discounted dominance problems with finite state sub spaces. We show that with direct gradient pararization in a sample we can analyze the general complexity of a gradient.
  arXiv  Detail & Related papers  (2022-01-19T07:03:37Z)
• Convergence of policy gradient for entropy regularized MDPs with neural network approximation in the mean-field regime [0.0]
  We study the global convergence of policy gradient for infinite-horizon, continuous state and action space, entropy-regularized Markov decision processes (MDPs) Our results rely on the careful analysis of non-linear Fokker--Planck--Kolmogorov equation.
  arXiv  Detail & Related papers  (2022-01-18T20:17:16Z)
• Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularization [20.651913793555163]
  We revisit the classical entropy regularized policy gradient methods with the soft-max policy parametrization. We establish a global optimality convergence result and a sample complexity of $widetildemathcalO(frac1epsilon2)$ for the proposed algorithm.
  arXiv  Detail & Related papers  (2021-10-19T17:21:09Z)
• Linear Convergence of Entropy-Regularized Natural Policy Gradient with Linear Function Approximation [30.02577720946978]
  We establish finite-time convergence analyses of entropy-regularized NPG with linear function approximation. We prove that entropy-regularized NPG exhibits emphlinear convergence up to a function approximation error.
  arXiv  Detail & Related papers  (2021-06-08T04:30:39Z)
• Benign Overfitting of Constant-Stepsize SGD for Linear Regression [122.70478935214128]
  inductive biases are central in preventing overfitting empirically. This work considers this issue in arguably the most basic setting: constant-stepsize SGD for linear regression. We reflect on a number of notable differences between the algorithmic regularization afforded by (unregularized) SGD in comparison to ordinary least squares.
  arXiv  Detail & Related papers  (2021-03-23T17:15:53Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  We study methods that use a collection of random observations to compute approximate solutions by searching over a known low-dimensional subspace of the Hilbert space. We show how our results precisely characterize the error of a class of temporal difference learning methods for the policy evaluation problem with linear function approximation.
  arXiv  Detail & Related papers  (2020-12-09T20:19:32Z)
• Approximation Schemes for ReLU Regression [80.33702497406632]
  We consider the fundamental problem of ReLU regression. The goal is to output the best fitting ReLU with respect to square loss given to draws from some unknown distribution.
  arXiv  Detail & Related papers  (2020-05-26T16:26:17Z)

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.