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

• URL: http://arxiv.org/abs/2603.28595v2
• Date: Wed, 01 Apr 2026 08:42:08 GMT
• Title: Optimistic Actor-Critic with Parametric Policies for Linear Markov Decision Processes
• Abstract summary: We propose an optimistic actor-critic framework that uses parametric log-linear policies.<n>We prove that the resulting algorithm achieves $widetildemathcalO(-4)$ and $widetildemathcalO(-2)$ sample complexity in the on-policy and off-policy setting.
• Score: 10.020260914307919
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Optimal Posterior Sampling for Policy Identification in Tabular Markov Decision Processes [3.2959629354399484]
  We study the $(varepsilon, )$PAC-PAC policy identification problem in finite-horizon episodic Markov Decision.<n>We propose a randomized and computationally efficient algorithm for best policy identification that combines posterior sampling with an online learning algorithm to guide MDP.
  arXiv  Detail & Related papers  (2026-05-05T16:16:57Z)
• Revisiting Weighted Strategy for Non-stationary Parametric Bandits and MDPs [56.246783503873225]
  This paper revisits the weighted strategy for non-stationary parametric bandits.<n>We propose a simpler weight-based algorithm that is as efficient as window/restart-based algorithms.<n>Our framework can be used to improve regret bounds of other parametric bandits.
  arXiv  Detail & Related papers  (2026-01-03T04:50:21Z)
• Achieving $\widetilde{\mathcal{O}}(\sqrt{T})$ Regret in Average-Reward POMDPs with Known Observation Models [69.1820058966619]
  We tackle average-reward infinite-horizon POMDPs with an unknown transition model.<n>We present a novel and simple estimator that overcomes this barrier.
  arXiv  Detail & Related papers  (2025-01-30T22:29:41Z)
• Efficient Learning of POMDPs with Known Observation Model in Average-Reward Setting [56.92178753201331]
  We propose the Observation-Aware Spectral (OAS) estimation technique, which enables the POMDP parameters to be learned from samples collected using a belief-based policy. We show the consistency of the OAS procedure, and we prove a regret guarantee of order $mathcalO(sqrtT log(T)$ for the proposed OAS-UCRL algorithm.
  arXiv  Detail & Related papers  (2024-10-02T08:46:34Z)
• Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimization [11.11876897168701]
  We consider the problem of learning in adversarial Markov decision processes with an oblivious adversary.<n>We propose an algorithm, called APO-MVP, that achieves a regret bound of order $tildemathcalO(mathrmpoly(H)sqrtSAT)$.
  arXiv  Detail & Related papers  (2024-07-08T08:06:45Z)
• Learning Optimal Deterministic Policies with Stochastic Policy Gradients [62.81324245896716]
  Policy gradient (PG) methods are successful approaches to deal with continuous reinforcement learning (RL) problems. In common practice, convergence (hyper)policies are learned only to deploy their deterministic version. We show how to tune the exploration level used for learning to optimize the trade-off between the sample complexity and the performance of the deployed deterministic policy.
  arXiv  Detail & Related papers  (2024-05-03T16:45:15Z)
• Low-Switching Policy Gradient with Exploration via Online Sensitivity Sampling [23.989009116398208]
  We design a low-switching sample-efficient policy optimization algorithm, LPO, with general non-linear function approximation. We show that, our algorithm obtains an $varepsilon$-optimal policy with only $widetildeO(fractextpoly(d)varepsilon3)$ samples.
  arXiv  Detail & Related papers  (2023-06-15T23:51:46Z)
• A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes [13.466249082564213]
  We propose an optimistic variant of PPO for episodic adversarial linear MDPs with full-information feedback. Compared with existing policy-based algorithms, we achieve the state-of-the-art regret bound in both linear MDPs and adversarial linear MDPs with full information.
  arXiv  Detail & Related papers  (2023-05-15T17:55:24Z)
• Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees [56.848265937921354]
  Inverse reinforcement learning (IRL) aims to recover the reward function and the associated optimal policy. Many algorithms for IRL have an inherently nested structure. We develop a novel single-loop algorithm for IRL that does not compromise reward estimation accuracy.
  arXiv  Detail & Related papers  (2022-10-04T17:13:45Z)
• Provably Correct Optimization and Exploration with Non-linear Policies [65.60853260886516]
  ENIAC is an actor-critic method that allows non-linear function approximation in the critic. We show that under certain assumptions, the learner finds a near-optimal policy in $O(poly(d))$ exploration rounds. We empirically evaluate this adaptation and show that it outperforms priors inspired by linear methods.
  arXiv  Detail & Related papers  (2021-03-22T03:16:33Z)
• A Nonparametric Off-Policy Policy Gradient [32.35604597324448]
  Reinforcement learning (RL) algorithms still suffer from high sample complexity despite outstanding recent successes. We build on the general sample efficiency of off-policy algorithms. We show that our approach has better sample efficiency than state-of-the-art policy gradient methods.
  arXiv  Detail & Related papers  (2020-01-08T10:13:08Z)

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.