Optimistic Actor-Critic with Parametric Policies for Linear Markov Decision Processes

Max Qiushi Lin; Reza Asad; Kevin Tan; Haque Ishfaq; Csaba Szepesvari; Sharan Vaswani

cs.LGMar 30, 2026

Optimistic Actor-Critic with Parametric Policies for Linear Markov Decision Processes

Authors: Max Qiushi Lin, Reza Asad, Kevin Tan, Haque Ishfaq, Csaba Szepesvari, Sharan Vaswani

Organizations: Simon Fraser University · University of Pennsylvania · Mila, McGill University · Google DeepMind, University of Alberta

Abstract

Although actor-critic methods have been successful in practice, their theoretical analyses have several limitations. Specifically, existing theoretical work either sidesteps the exploration problem by making strong assumptions or analyzes impractical methods with complicated algorithmic modifications. Moreover, the actor-critic methods analyzed for linear MDPs often employ natural policy gradient and construct "implicit" policies without explicit parameterization. Such policies are computationally expensive to sample from, making the environment interactions inefficient. To that end, we focus on the finite-horizon linear MDPs and propose an optimistic actor-critic framework that uses parametric log-linear policies. In particular, we introduce a tractable $\textit{logit-matching}$ regression objective for the actor. For the critic, we use approximate Thompson sampling via Langevin Monte Carlo to obtain optimistic value estimates. We prove that the resulting algorithm achieves $\widetilde{\mathcal{O}}(ε^{-4})$ and $\widetilde{\mathcal{O}}(ε^{-2})$ sample complexity in the on-policy and off-policy setting, respectively. Our results match prior theoretical work in achieving the state-of-the-art sample complexity, while our algorithm is more aligned with practice.

Figures & tables

Algorithm	Sample Complexity (On-Policy)	Sample Complexity (Off-Policy)	Policy Param.	Clipping Q-Function	Computational Cost for Policy Inference
Liu et al. (2023)	$\widetilde{\mathcal{O}}(\frac{1}{{\epsilon}^{4}})$	✗	implicit	yes	$\mathcal{O}(d_{{\bm{c}}}^{2}\,H\,\lvert\mathcal{A}\rvert\,{\epsilon}^{-2})$
Sherman et al. (2023)	✗	$\widetilde{\mathcal{O}}(\frac{1}{{\epsilon}^{2}})$	implicit	no	$\mathcal{O}(d_{{\bm{c}}}^{2}\,H\,\lvert\mathcal{A}\rvert\,{\epsilon}^{-2})$
Cassel and Rosenberg (2024)	✗	$\widetilde{\mathcal{O}}(\frac{1}{{\epsilon}^{2}})$	implicit	no
Ours	$\widetilde{\mathcal{O}}(\frac{1}{{\epsilon}^{4}})$	$\widetilde{\mathcal{O}}(\frac{1}{{\epsilon}^{2}})$	explicit	yes	$\mathcal{O}(d_{{\bm{a}}}^{2}\,H\,\lvert\mathcal{A}\rvert)$

Table 1: Comparison with the state-of-the-art algorithms for episodic finite-horizon linear MDPs (with feature dimension

d_{{\bm{c}}}

and horizon

H

). The sample complexity refers to the number of interactions required for outputting an

\epsilon

-optimal policy, whereas the cost of policy inference refers to the per-episode cost for interacting with the environment for

H

steps. Our proposed algorithm matches the optimal sample efficiency in both the on- and off-policy settings. Furthermore, in contrast to existing works, our algorithm employs an explicit policy parameterization (log-linear policies with dimension

d_{{\bm{a}}}

), resulting in lower computational cost for policy inference.

Figure 1: Comparison of LMC-NPG-EXP (our proposed algorithm), LMC-NPG-IMP (memory-intensive variant), and LMC (value-based baseline) in the Random MDP.

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Notation	Meaning
Problem Definition
${\mathcal{S}}$ , ${\mathcal{A}}$	state space and action space
$H$ , $h$	horizon length (total number of steps), current index of step
$r\in{\mathbb{R}}^{\|{\mathcal{S}}\|\times\|{\mathcal{A}}\|}$	reward function
${\mathbb{P}}\in{\mathbb{R}}^{\|{\mathcal{S}}\|\times\|{\mathcal{A}}\|\times\|{\mathcal{S}}\|}$	transition kernel
$\phi:{\mathcal{S}}\times{\mathcal{A}}\mapsto{\mathbb{R}}^{d_{{\bm{c}}}}$	features for the linear MDP environment

Appendix

Table 2: Notations for Problem Definition and Algorithm Design

Figure 2: Example of the Deep Sea environment from Osband et al. (2019) .

Hyperparameter	LMC	LMC-NPG-IMP	LMC-NPG-EXP
Policy Optimization Learning Rate ( $\eta$ )	✗	$[0.1,1,10,100]$	$[0.1,1,10,100]$
Inverse Temperature ( $\zeta^{-1}$ )	$[10^{-2},10^{-3},10^{-4},10^{-5}]$
Number of Critic Updates ( $J_{t}$ )	$100$
Critic Learning Rate ( $\alpha_{{\bm{c}}}$ )	$[10^{-2},10^{-3},10^{-4},10^{-5}]$
Number of Episodes ( $T$ )	$600$
Horizon Length ( $H$ )	$100$

Appendix

Table 3: Hyperparameter search space for our experiments in linear MDPs.

Figure 3: Comparison of LMC-NPG-EXP (our proposed framework), LMC-NPG-IMP (memory-intensive variant), and LMC (value-based baseline) in the Deep Sea environment.

Figure 4: Ablation of the exploration mechanism for LMc-NPG-EXP .

Figure 5: Effect of feature dimension $d$ in Deep Sea.

Figure 6: LMC-NPG-EXP exhibits robustness to different choices of $\zeta^{-1}$ .

Figure 7: LMC-NPG-EXP exhibits robustness to different choices of $M$ .

Hyperparameter	LMC-NPG-EXP	PPO
Reward normalization	✗	✗
Observation normalization	✗	✗
Orthogonal weight initialization	✓	✓
Value function clipping	✗	✗
Gradient clipping	✗	✓
Probability ratio clipping	✗	✓

Appendix

Table 4: Hyperparameters for the Atari experiments in the on-policy setting.

Hyperparameter	LMC-NPG-EXP	DQN
Reward normalization	✗	✗
Observation normalization	✗	✗
Orthogonal weight initialization	✗	✗
Value function clipping	✗	✗
Gradient clipping	✗	✗
Probability ratio clipping	✗	✗

Appendix

Table 5: Hyperparameters for the Atari experiments in the off-policy setting.

Figure 8: In the on-policy setting, LMC-NPG-EXP achieves comparable or better performance compared to PPO .

Figure 9: In the off-policy setting, LMC-NPG-EXP achieves comparable or better performance compared to DQN .

Actor-Critic Methods

Actor-critic methods train a policy alongside a value estimator to guide decisions in complex control and decision-making tasks.

See all 107 papers

Achieving $ε^{-2}$ Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions
May 13, 2026Ishaq Hamza, Zaiwei ChenPolicy Gradient Last-Iterate Convergence
IISc · Edwardson School of Industrial Engineering, Purdue University · Purdue IE
A Computationally Efficient and Rate-Optimal Algorithm for Adversarial Linear MDPs with (Aggregate) Bandit Feedback
Oct 22, 2026Haolin Liu, Chen-Yu Wei, Hanbin ZhouLinear Markov Decision Processes
University of Virginia · Hong Kong University of Science and Technology
Breaking the Computational Barrier: Provably Efficient Actor-Critic for Low-Rank MDPs
May 2, 2026Ruiquan Huang, Donghao Li, Yingbin Liang +1Markov Decision Processes Reinforcement Learning
University of Kentucky. · University of Virginia. · Ohio State University..

May 13, 2026J/K move · Enter open · S save

Achieving $ε^{-2}$ Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions

Ishaq Hamza, Zaiwei Chen

IISc · Edwardson School of Industrial Engineering, Purdue University · Purdue IE

Policy Gradient Last-Iterate Convergence Natural Policy Gradient Actor-Critic Methods Policy Learning Sample-Efficient RL+1

Open paper AskPDF arXiv

In this paper, we establish last-iterate convergence rates for off-policy actor--critic methods in reinforcement learning. In particular, under a single-loop, single-timescale implementation and a broad class of policy updates, including approximate policy iteration and natural policy gradient methods, we prove the first

\tilde{\mathcal{O}}(ε^{-2})

sample complexity guarantee for finding an

ε

-optimal policy under minimal assumptions, namely, the existence of a policy that induces an irreducible Markov chain. This stands in stark contrast to the existing literature, where an

\tilde{\mathcal{O}}(ε^{-2})

sample complexity is achieved only through nested-loop updates and/or under strong, algorithm-dependent assumptions on the policies, such as uniform mixing and uniform exploration. Technically, to address the challenges posed by the coupled update equations arising from the single-loop implementation, as well as the potentially unbounded iterates induced by off-policy learning, our analysis is based on a coupled Lyapunov drift framework. Specifically, we establish a geometric convergence rate for the actor and an

\tilde{\mathcal{O}}(1/T)

convergence rate for the critic, and combine the two Lyapunov drift inequalities through a cross-domination property. We believe this analytical framework is of independent interest and may be applicable to other coupled iterative algorithms with unbounded

Abstract

Actor-Critic Methods

Explore similar work

Achieving ε−2ε^{-2}ε−2 Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions

A Computationally Efficient and Rate-Optimal Algorithm for Adversarial Linear MDPs with (Aggregate) Bandit Feedback

Breaking the Computational Barrier: Provably Efficient Actor-Critic for Low-Rank MDPs

Achieving $ε^{-2}$ Sample Complexity for Single-Loop Actor-Critic under Minimal Assumptions