← Back to all news
arXiv Machine Learning

Finite-Time Guarantees for Constrained Reinforcement Learning under Partial Observability

The paper investigates reinforcement learning in constrained partially observable Markov decision processes (CPOMDPs), where an agent must maximize reward while respecting a cost constraint using incomplete state information. By approximating the CPOMDP with finite-memory models and treating observation-action windows as states of a constrained MDP, the authors develop a primal–dual algorithm that offers the first non-asymptotic guarantees on both average reward suboptimality and constraint violation. Under a filter‑stability assumption, they show that the approximation errors decay geometrically with the window length, and validate their method with experiments in partially observable gridworlds.

Related stories

arXiv Machine Learning
Sep 14

Independent Learning of Nash Equilibria in Partially Observable Markov Potential Games with Decoupled Dynamics

The paper investigates learning Nash equilibria in partially observable Markov games (POMGs) where agents cannot fully observe the state. By focusing on a subclass with independent state transitions and a Markov potential game structure, the authors propose an independent learning algorithm that allows agents to converge to an approximate Nash equilibrium using only their own observations and actions, without communication. Under a filter stability assumption, finite‑history policies are shown to approximate the POMG sufficiently, enabling a surrogate near‑potential Markov game and yielding quasi‑polynomial sample and computational complexity.

By Philip Jordan, Maryam Kamgarpour
agentsreinforcement-learning
More like this →
arXiv Machine Learning
Sep 30

Global Optimality for Constrained Exploration via Penalty Regularization

The paper introduces Policy Gradient Penalty (PGP), a single‑loop policy‑space method that enforces convex occupancy‑measure constraints via quadratic‑penalty regularization. PGP constructs pseudo‑rewards to estimate gradients of the penalized objective and uses the classical Policy Gradient Theorem, establishing smoothness and global last‑iterate convergence guarantees for an ε‑optimal constrained entropy value with ε‑bounded constraint violation. The authors validate PGP with ablations on a grid‑world benchmark and demonstrate scalability on two challenging continuous‑control tasks.

By Florian Wolf, Ilyas Fatkhullin, Niao He
reinforcement-learningbenchmarkssafety
More like this →
arXiv Machine Learning
Jul 1

End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions

arXiv:2603. 23461v2 Announce Type: replace Abstract: We study reinforcement learning (RL) with linear function approximation in Markov Decision Processes (MDPs) satisfying \emph{linear Bellman completeness} -- a fundamental setting where the Bellman backup of any linear value function remains linear.

By Zakaria Mhammedi, Alexander Rakhlin, Nneka Okolo
reinforcement-learning
More like this →