A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach

• URL: http://arxiv.org/abs/2407.18878v3
• Date: Mon, 05 May 2025 18:24:22 GMT
• Title: A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
• Authors: Swetha Ganesh, Washim Uddin Mondal, Vaneet Aggarwal,
• Abstract summary: This work examines average-reward reinforcement learning with general policy parametrization.<n>We propose a Multi-level Monte Carlo-based Natural Actor-Critic (MLMC-NAC) algorithm.<n>Our work is the first to achieve a global convergence rate of $tildemathcalO (1/sqrtT)$ for average-reward Markov Decision Processes.
• Score: 31.343919501963416
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This work examines average-reward reinforcement learning with general policy parametrization. Existing state-of-the-art (SOTA) guarantees for this problem are either suboptimal or hindered by several challenges, including poor scalability with respect to the size of the state-action space, high iteration complexity, and dependence on knowledge of mixing times and hitting times. To address these limitations, we propose a Multi-level Monte Carlo-based Natural Actor-Critic (MLMC-NAC) algorithm. Our work is the first to achieve a global convergence rate of $\tilde{\mathcal{O}}(1/\sqrt{T})$ for average-reward Markov Decision Processes (MDPs) (where $T$ is the horizon length), without requiring the knowledge of mixing and hitting times. Moreover, the convergence rate does not scale with the size of the state space, therefore even being applicable to infinite state spaces.

Related papers

• Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach [33.38582292895673]
  We propose a Natural Actor-Critic with order-optimal regret of $tildeO(sqrtT)$ in infinite-reward average-reward Decision Processes.<n> NACB employs function approximation for both actor and the critic, enabling scalability to large state potential periodicity and action spaces.
  arXiv  Detail & Related papers  (2025-05-26T13:43:02Z)
• Mean-Field Sampling for Cooperative Multi-Agent Reinforcement Learning [4.899818550820576]
  We propose a new algorithm for multi-agent reinforcement learning. We show that this learned policy converges to the optimal policy on the order of $tildeO (1/sqrtk)$ as the number of subsampled agents increases.
  arXiv  Detail & Related papers  (2024-12-01T03:45:17Z)
• Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles [83.85151306138007]
  Multi-level Actor-Critic (MAC) framework incorporates a Multi-level Monte-Carlo (MLMC) estimator. We demonstrate that MAC outperforms the existing state-of-the-art policy gradient-based method for average reward settings.
  arXiv  Detail & Related papers  (2024-03-18T16:23:47Z)
• Strictly Low Rank Constraint Optimization -- An Asymptotically $\mathcal{O}(\frac{1}{t^2})$ Method [5.770309971945476]
  We propose a class of non-text and non-smooth problems with textitrank regularization to promote sparsity in optimal solution. We show that our algorithms are able to achieve a singular convergence of $Ofrac(t2)$, which is exactly same as Nesterov's optimal convergence for first-order methods on smooth convex problems.
  arXiv  Detail & Related papers  (2023-07-04T16:55:41Z)
• Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlo [104.9535542833054]
  We present a scalable and effective exploration strategy based on Thompson sampling for reinforcement learning (RL) We instead directly sample the Q function from its posterior distribution, by using Langevin Monte Carlo. Our approach achieves better or similar results compared with state-of-the-art deep RL algorithms on several challenging exploration tasks from the Atari57 suite.
  arXiv  Detail & Related papers  (2023-05-29T17:11:28Z)
• Scalable Primal-Dual Actor-Critic Method for Safe Multi-Agent RL with General Utilities [12.104551746465932]
  We investigate safe multi-agent reinforcement learning, where agents seek to collectively maximize an aggregate sum of local objectives while satisfying their own safety constraints. Our algorithm converges to a first-order stationary point (FOSP) at the rate of $mathcalOleft(T-2/3right)$. In the sample-based setting, we demonstrate that, with high probability, our algorithm requires $widetildemathcalOleft(epsilon-3.5right)$ samples to achieve an $epsilon$-FOSP.
  arXiv  Detail & Related papers  (2023-05-27T20:08:35Z)
• Policy Mirror Descent Inherently Explores Action Space [10.772560347950053]
  We establish for the first time an $tildemathcalO (1/epsilon2)$ sample complexity for online policy gradient methods without any exploration strategies. New policy gradient methods can prevent repeatedly committing to potentially high-risk actions when searching for optimal policies.
  arXiv  Detail & Related papers  (2023-03-08T05:19:08Z)
• Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Critic [61.968469104271676]
  We propose an RL methodology attuned to the mixing time by employing a multi-level Monte Carlo estimator for the critic, the actor, and the average reward embedded within an actor-critic (AC) algorithm. We experimentally show that these alleviated restrictions on the technical conditions required for stability translate to superior performance in practice for RL problems with sparse rewards.
  arXiv  Detail & Related papers  (2023-01-28T04:12:56Z)
• Finite-Time Analysis of Fully Decentralized Single-Timescale Actor-Critic [4.94128206910124]
  We introduce a fully decentralized Actor-Critic (AC) algorithm, where actor, critic, and global reward estimator are updated in an alternating manner. We show that our algorithm has sample complexity of $tildemathcalO(epsilon-2)$ under Markovian sampling. We also provide a local action privacy-preserving version of our algorithm and its analysis.
  arXiv  Detail & Related papers  (2022-06-12T13:14:14Z)
• Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning [82.31436758872715]
  We develop an algorithm that achieves the same PAC guarantee while using only $O(1)$ episodes of environment interactions. We establish a connection between value functions in discounted and finite-horizon Markov decision processes.
  arXiv  Detail & Related papers  (2021-11-01T00:21:24Z)
• A general sample complexity analysis of vanilla policy gradient [101.16957584135767]
  Policy gradient (PG) is one of the most popular reinforcement learning (RL) problems. "vanilla" theoretical understanding of PG trajectory is one of the most popular methods for solving RL problems.
  arXiv  Detail & Related papers  (2021-07-23T19:38:17Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  We investigate the active pure exploration problem in Markov Decision Processes. Agent sequentially selects actions and, from the resulting system trajectory, aims at the best as fast as possible.
  arXiv  Detail & Related papers  (2021-06-05T09:16:28Z)
• Softmax Policy Gradient Methods Can Take Exponential Time to Converge [60.98700344526674]
  The softmax policy gradient (PG) method is arguably one of the de facto implementations of policy optimization in modern reinforcement learning. We demonstrate that softmax PG methods can take exponential time -- in terms of $mathcalS|$ and $frac11-gamma$ -- to converge.
  arXiv  Detail & Related papers  (2021-02-22T18:56:26Z)
• Finite Sample Analysis of Two-Time-Scale Natural Actor-Critic Algorithm [21.91930554261688]
  Actor-critic style two-time-scale algorithms are very popular in reinforcement learning. In this paper, we characterize the global convergence of an online natural actor-critic algorithm. We employ $epsilon$-greedy sampling in order to ensure enough exploration.
  arXiv  Detail & Related papers  (2021-01-26T01:12:07Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
  arXiv  Detail & Related papers  (2020-06-04T17:51:00Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator) We first consider $gamma$-discounted infinite-horizon Markov decision processes (MDPs) with state space $mathcalS$ and action space $mathcalA$. We prove that a plain model-based planning algorithm suffices to achieve minimax-optimal sample complexity given any target accuracy level.
  arXiv  Detail & Related papers  (2020-05-26T17:53: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.