Research map / Reinforcement learning / Policy gradient and actor-critic

Breaking the Bias Barrier in Concave Multi-Objective Reinforcement Learning

NeurIPS 2026 · Reinforcement learning › Policy gradient and actor-critic · approach: Variance-reduced policy gradients · 0 citations (OpenAlex)

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.

Shows concave-scalarized multi-objective RL suffers an O(eps^-4) policy-gradient barrier from plug-in bias, and closes it to O(eps^-2) with NPG plus an MLMC gradient estimator (or vanilla NPG under second-order smoothness of f).

Problem

Policy-gradient methods for maximizing a concave scalarization f(J_1,...,J_M) of multiple expected discounted returns suffer biased gradient estimates from plug-in return estimates, giving a known O(eps^-4) sample complexity versus O(eps^-2) for standard RL.

Approach

Use a natural policy gradient update with a multi-level Monte Carlo estimator of the nonlinear scalarization gradient to reduce bias at logarithmic expected sampling cost; under second-order smoothness of f the first-order bias cancels so vanilla NPG with empirical returns suffices.

Key results

• MLMC-NPG achieves O~(eps^-2) sample complexity for an eps-optimal policy under Lipschitz partial derivatives of f, without extra assumptions beyond prior work.
• Vanilla NPG with empirical return estimates achieves O~(eps^-2) when f is second-order smooth, since first-order bias drops to O(1/B).
• Existing policy-gradient methods for concave MORL are shown to have an intrinsic O~(eps^-4) sample complexity due to plug-in bias.

Surprising findings

• Plug-in gradient bias from nonlinearity of f, not variance, is the bottleneck: the empirical estimator's O(B^-1/2) bias forces large batches each iteration.

Limitations

• Results are theoretical; no experiments are reported.
• Requires Fisher non-degeneracy and bounded score-function assumptions, and an expressivity assumption giving bias epsilon_bias.
• Second-order smoothness result needs stronger assumptions on f; alpha-fairness only satisfies it on domains bounded away from zero.

Experimental setup

Metrics: sample complexity optimality gap

Baselines: prior policy-gradient concave MORL method (O(eps^-4)) model-based concave MORL regret methods

Builds on: natural policy gradient multi-level Monte Carlo reinforcement learning with general utilities

Closest papers by meaning

• On the Second-Order Convergence of Biased Policy Gradient Algorithms (ICML 2024 · similarity 0.88)
• A Theoretical Understanding of Gradient Bias in Meta-Reinforcement Learning (NeurIPS 2022 · similarity 0.88)
• Multi-Objective Reinforcement Learning: Convexity, Stationarity and Pareto Optimality (ICLR 2023 · similarity 0.88)
• Preference Conditioned Multi-Objective Reinforcement Learning: Decomposed, Diversity-Driven Policy Optimization (NeurIPS 2026 · similarity 0.88)
• Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Framework (NeurIPS 2026 · similarity 0.87)
• Finite-Time Convergence and Sample Complexity of Actor-Critic Multi-Objective Reinforcement Learning (ICML 2024 · similarity 0.87)