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.
By Valentina Zaccaria, Philip Jordan, Tingting Ni, Gian Antonio Susto, Maryam Kamgarpour
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
arXiv:2606. 16729v1 Announce Type: new Abstract: While there is an extensive body of work characterizing the sample complexity of discounted cumulative-reward MDPs, finite sample analyses for average-reward MDPs have been limited, and most existing works rely on restrictive assumptions such as ergodicity or access to a generative model.
By Jongmin Lee, Ernest K. Ryu, Vaneet Aggarwal
The paper introduces a model-based bootstrap framework for uncertainty quantification in offline policy evaluation (OPE) within finite-horizon, time-inhomogeneous Markov decision processes. Unlike traditional bootstrap methods that resample entire episodes, this approach regenerates trajectories from an estimated MDP, enabling use of diverse offline data formats such as complete trajectories, transition-level observations, and trajectory fragments. The authors prove bootstrap distributional consistency, asymptotically valid confidence intervals, and consistent variance estimation, and demonstrate through simulations that the method yields tighter confidence intervals and more accurate variance estimates compared to existing techniques.
By Weiwei Wang, Yuqiang Li, Xianyi Wu, Bingyi Jing
The paper introduces a framework for reinforcement learning in Markov decision processes where policies are ordered by the information they provide, allowing data from one policy to estimate the performance of others. An epoch‑based algorithm is developed for infinite‑horizon average‑cost MDPs with continuous state and action spaces, achieving regret that scales with the width of the policy class’s information order. The authors apply the framework to lost‑sales inventory, dual‑sourcing, and state‑dependent queueing systems, demonstrating improved regret bounds and empirical performance without requiring global convexity or specific arrival‑rate structures.
By Zhongjun Zhang, Shipra Agrawal, Ilan Lobel, Sean R. Sinclair, Christina Lee Yu
arXiv:2607. 17201v1 Announce Type: cross Abstract: In this work we study the Best Policy Identification (BPI) problem in online, tabular Reinforcement Learning.
By Joseph Lazzaro, Alessio Russo, Aldo Pacchiano
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
arXiv:2510. 02149v2 Announce Type: replace Abstract: We introduce Action-Triggered Sporadically Traceable Markov Decision Processes (ATST-MDPs), a reinforcement learning framework for partial observability in which full state observations occur stochastically at each step, with probability determined by the chosen action.
By Alexander Ryabchenko, Wenlong Mou
The paper investigates best‑policy identification in finite‑horizon, risk‑sensitive reinforcement learning using the entropic risk measure. It identifies a gap between known lower bounds ≥ η(e^{|eta|H}) and upper bounds ≤ O(e^{2|eta|H}) for sample complexity, attributing the excess factor to loose concentration bounds for exponential utilities. By employing a forward‑model algorithm with KL‑based exploration bonuses and a novel stopping rule, the authors achieve a sample complexity that matches the lower bound, closing the previously open exponential gap.
By Amer Essakine, Claire Vernade
arXiv:2603. 03480v2 Announce Type: replace Abstract: We study reinforcement learning with delayed state observation, where the agent observes the current state after some random number of time steps.
By Harin Lee, Kevin Jamieson
arXiv:2607. 17823v1 Announce Type: new Abstract: Reinforcement Learning is a cornerstone technique for modern large reasoning models.
By Riccardo Poiani, Martino Bernasconi, Andrea Celli
arXiv:2512. 06244v2 Announce Type: replace Abstract: The exploration-exploitation dilemma in reinforcement learning (RL) is a fundamental challenge to efficient RL algorithms.
By Caleb Ju, Guanghui Lan