Research map / Reinforcement learning / Policy gradient and actor-critic
On the Global Optimality of Policy Gradient Methods in General Utility Reinforcement Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Establishes global optimality guarantees for policy gradient in reinforcement learning with general utilities, via a gradient domination inequality in the tabular case and an MLE-based occupancy-measure approximation with policy gradient for large state-action spaces.
Problem
Policy gradient methods for RL with general (nonlinear, concave) utilities of the state-action occupancy measure lack global optimality guarantees, and existing occupancy estimation is tabular (count-based) and does not scale to large state-action spaces.
Approach
Shows the RLGU objective satisfies a gradient domination inequality in the tabular setting by reducing the pseudo-reward policy gradient to a standard expected-return gradient; for large spaces, estimates the occupancy measure by maximum likelihood over a parametric distribution class, so the sample complexity scales with the parameter dimension m rather than the state-action space size.
Key results
- Gradient domination inequality for concave general utilities in the tabular direct parametrization, giving global optimality for PG in RLGU.
- MLE occupancy estimation has TV error scaling with parameter dimension m with sample complexity O~(m eps^-2), independent of state-action space size.
- Global convergence sample complexity O~(m eps^-4) for PG with occupancy MLE under concave utilities and softmax policy assumptions; first-order stationarity O~(m eps^-4).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MLE occupancy estimation in a function class of dimension m | PG-OMA · RLGU, nonconcave utility | sample complexity: \tilde{\mathcal{O}}(m \epsilon^{-2}) | Helped |
| Use PG-OMA with occupancy measure MLE under concavity | RLGU · Concave general utility | sample complexity: \tilde{\mathcal{O}}(m \epsilon^{-4}) | Helped |
| Use PG-OMA for nonconcave utility | RLGU · Nonconcave general utility | sample complexity: \tilde{\mathcal{O}}(m \epsilon^{-2}) | Helped |
| Use direct policy parameterization with a concave utility | Tabular policy gradient · Tabular RLGU | global optimality | Helped |
| Use MLE rather than the discussed MSE occupancy estimator | Occupancy measure estimation · Large state-action spaces | scalability | Helped |
| Use MSE rather than MLE for occupancy estimation | Occupancy measure estimation · Large state-action spaces | scalability | Hurt |
Limitations
- Global optimality in the tabular case uses a direct policy parametrization; extension to softmax/general parametrizations relies on strong overparametrization assumptions.
- Assumes access to exact maximizer of the log-likelihood and i.i.d. samples from the occupancy measure.
- Realizability of the occupancy measure in the function approximation class is assumed.
Experimental setup
Metrics: sample complexity gradient norm function value gap
Baselines: Zhang et al. 2020 variational policy gradient Barakat et al. 2023 hidden convexity PG Mutti et al. MSE occupancy estimation
Builds on: policy gradient gradient domination (Agarwal et al.) hidden convexity for convex RL reinforce estimator
Closest papers by meaning
- Occupancy-based Policy Gradient: Estimation, Convergence, and Optimality (NeurIPS 2024 · similarity 0.90)
- Global Reinforcement Learning : Beyond Linear and Convex Rewards via Submodular Semi-gradient Methods (ICML 2024 · similarity 0.89)
- Robust Reinforcement Learning with General Utility (NeurIPS 2024 · similarity 0.89)
- Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity (ICML 2025 · similarity 0.89)
- Learning Optimal Deterministic Policies with Stochastic Policy Gradients (ICML 2024 · similarity 0.89)
- Exploration-Driven Policy Optimization in RLHF: Theoretical Insights on Efficient Data Utilization (ICML 2024 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.