Research map / Reinforcement learning / MDPs and planning

Exploration from a Primal-Dual Lens: Value-Incentivized Actor-Critic Methods for Sample-Efficient Online RL

NeurIPS 2025 · Reinforcement learning › MDPs and planning · approach: Policy optimization theory · 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.

Proposes value-incentivized actor-critic (VAC), a single-objective, non-bilevel actor-critic method for online RL derived from a primal-dual (Lagrangian) view of MEX, with near-optimal regret under linear MDPs.

Problem

Sample-efficient model-free online RL with function approximation needs exploration-exploitation balance with provable guarantees, but the existing MEX objective is bilevel and hard to optimize with first-order methods.

Approach

Reinterpret MEX's optimistic regularization as a regularized Lagrangian of a value maximization problem constrained by the Bellman consistency equation (not optimality), jointly optimizing Q-function and policy in one differentiable objective with a double-sampling-free reparameterization of the dual variable.

Key results

• VAC achieves regret O~(dH^2 sqrt(T)) under episodic linear MDPs with high probability, near-optimal up to sqrt(H) versus the lower bound O~(d sqrt(H^3 T)).
• In the infinite-horizon discounted setting, sample complexity is O~(d^2 / ((1-gamma)^5 eps^2)).
• The regret analysis is purely theoretical; no empirical experiments are reported in the paper.

Limitations

• No empirical validation; the claimed practicality is untested.
• Regret bound is only near-optimal up to sqrt(H) and relies on linear MDP and log-linear policy assumptions.
• General function approximation results rely on additional assumptions deferred to the appendix.

Experimental setup

Metrics: regret

Baselines: MEX

Builds on: MEX (Maximize to Explore) reward-biased optimism double-sampling trick for Bellman residual Lagrangians Freedman's inequality

Closest papers by meaning

• Beyond Optimism: Exploration With Partially Observable Rewards (NeurIPS 2024 · similarity 0.89)
• Minimax Optimal Reinforcement Learning with Quasi-Optimism (ICLR 2025 · similarity 0.89)
• SOMBRL: Scalable and Optimistic Model-Based RL (NeurIPS 2025 · similarity 0.89)
• MaxInfoRL: Boosting exploration in reinforcement learning through information gain maximization (ICLR 2025 · similarity 0.88)
• NeoRL: Efficient Exploration for Nonepisodic RL (NeurIPS 2024 · similarity 0.88)
• Exploration-Driven Policy Optimization in RLHF: Theoretical Insights on Efficient Data Utilization (ICML 2024 · similarity 0.88)