The paper introduces a vector Bellman theory for multichain robust average‑reward Markov decision processes, addressing the state‑dependent optimal long‑run rewards that arise under uncertainty. It develops a gain‑first, bias‑second optimization principle for finite models with compact, post‑action $(s,a)$‑rectangular ambiguity, yielding a coupled vector gain‑bias system and stationary saddle strategies from all initial states. The authors also characterize solvability conditions, provide certificates for asymptotically affine trajectories of the robust Bellman operator, and design a robust approximately shifted Halpern planning algorithm that converges to the optimal gain vector and produces average‑optimal greedy controllers.
By Yue Wang, George Atia
arXiv:2506. 07040v4 Announce Type: replace-cross Abstract: We study model-free methods for distributionally robust infinite-horizon average-reward Markov decision processes (MDPs).
By Yang Xu, Swetha Ganesh, Vaneet Aggarwal
arXiv:2601. 18840v4 Announce Type: replace Abstract: Markov decision problems are most commonly solved via dynamic programming.
By Donghwan Lee, Hyukjun Yang
arXiv:2610.29024v1 Announce Type: new
Abstract: Reinforcement learning for stochastic systems typically optimizes expected cumulative rewards, while reliable and repeatable behavior also depends on h...
By Xun Shen, Yuepeng Wang, Daniyal Sajedi-Hosseini, Akifumi Wachi, Ken Kawano, Yoshihiko Fujisawa, Mehrshad Sadria, S\'ebastien Gros, Katsuki Fujisawa
arXiv:2607. 03168v1 Announce Type: cross Abstract: Entropy regularization is widely used in continuous-time reinforcement learning (RL) to reduce sensitivity to environmental perturbations, yet its robustness benefits lack a rigorous theoretical foundation.
By Jialun Cao, Fernando Acero, David \v{S}i\v{s}ka, Yufei Zhang
arXiv:2602. 03778v2 Announce Type: replace-cross Abstract: Tail-end risk measures such as static conditional value-at-risk (CVaR) are used in safety-critical applications to prevent rare, yet catastrophic events.
By Aneri Muni, Vincent Taboga, Esther Derman, Pierre-Luc Bacon, Erick Delage
We study infinite-horizon average-reward constrained Markov decision processes (CMDPs) under the weakly communicating assumption. Existing high-probability guarantees for this setting either require c...
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
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
arXiv:2606. 10979v1 Announce Type: new Abstract: Many Markov decision processes (MDPs) in operations research have feasible actions that are state dependent and defined implicitly by various operational constraints.
By Yi Chen (Lucy), Rushuai Yang (Lucy), Qiang Chen (Lucy), Dongyan (Lucy), Huo
The paper introduces an asynchronous value‑iteration RL algorithm for average‑reward multichain MDPs that requires only the transition graph and uses Bather’s decomposition to partition the state space into communicating subsystems and transient states. This hierarchical decomposition transforms the global decision problem into structured subproblems, enabling the algorithm to converge to the optimal gain and produce gain‑optimal policies in finite time. Two additional algorithms are presented: one that approximately solves the multichain average optimality equations for near gain‑optimality, and another that approximates the optimal bias function to achieve near bias‑optimality, both with almost‑sure convergence guarantees and improved transient performance.
whyItMatters":"The work offers the first essentially model‑free average‑reward RL algorithms for general multichain MDPs, avoiding reductions to discounted problems."
By Huizhen Yu, Isaiah Heidt
The paper introduces a computationally efficient algorithm for infinite-horizon average-reward constrained Markov decision processes (CMDPs) under weak communication. It achieves a high-probability regret and cumulative constraint violation of ×O(√T) in the tabular setting, matching optimal dependence up to logarithmic factors. The method augments the state with cumulative constraint violation, reshapes rewards using a Huber potential, and applies finite-horizon approximation with optimistic value iteration to maintain bounded per-step rewards.
By Kihyun Yu, Seoungbin Bae, Dabeen Lee