CS Paper Radar

POMDPs with Lipschitz-Continuous Belief-Dependent Rewards Have Lipschitz-Continuous Value Functions

Timothy L. Molloy

eess.SY ·submitted 2026-10-24 05:16 UTC · v1
published

Abstract

We establish the vector (or elementwise) Lipschitz continuity of value functions for partially observed Markov decision processes (POMDPs) with reward functions that are Lipschitz-continuous functions of the posterior probability distribution of the state (i.e., the belief). Our results significantly tighten existing Lipschitz results for this class of POMDPs on infinite horizons, with previous results only yielding finite constants for discount factors less than 0.5, while our results yield finite Lipschitz constants for all discount factors less than 1. The significance of our Lipschitz constants is illustrated through their use in heuristic search value iteration (HSVI) to construct (finite) piecewise-linear value function approximations.

Comment
7 pages, 3 figures, accepted for presentation at 2026 IEEE Conference on Decision and Control (CDC)

Closest papers

Nearest neighbours by meaning across the whole index.

Finite-Time Convergence and Regret Guarantees for Neural Reinforcement Learning in POMDPs

cs.LG cs.AI ·2026-11-04 ·Jingjuan Huang, Zhiyao Zhang, Alvaro Velasquez, Nathaniel D. Bastian, Jia Liu
theory similarity 0.64
Abstract · 33 pages, 5 figures

Reinforcement learning (RL) in Partially Observable Markov Decision Processes (POMDPs) is computationally challenging due to the curse of long-range dependence on history. Fortunately, recent studies have shown that a range of POMDPs that satisfy the filter stability assumption can be well approximated by a superstate Markov Decision Process (MDP) based on a truncated history in a finite-memory window, with a value gap that decays with the window length. However, existing finite-time convergence analyses on such superstate MDP surrogates are either limited to over-simplified linear function approximation or rely on an i.i.d. sampling oracle that is violated by POMDP trajectories, both of which severely limit the applicability of these theoretical results in practice. This motivates us to bridge the gap by investigating RL in POMDPs with nonlinear neural value function approximation. Our main contributions are threefold: i) We first establish a new finite-state MDP point-wise approximation error bound, which lays the foundation for our RL algorithm design and analysis in POMDPs; ii) By applying Temporal-Difference (TD) learning to POMDP-generated superstate transitions and targeting the Bellman fixed point of the superstate MDP, we prove a finite-time critic error bound with nonlinear neural value function approximation; and iii) By combining the neural critic function approximation error bound with the policy mirror descent framework, we obtain a finite-time sublinear regret against the optimal POMDP value. To the best of our knowledge, such a finite-time sublinear regret based on neural function approximation is the first in the literature for finite-memory POMDPs. Our numerical experiments also verify our theoretical results.

0.15

Belief Embedding Tree Search

cs.AI cs.LG ·2026-10-10 ·Christopher Solinas, Radovan Haluška, Martin Schmid, Michael Buro, Nathan R. Sturtevant +1 more
similarity 0.63
Abstract

Beliefs in a Partially Observable Markov Decision Process (POMDP) are posterior distributions over the hidden state given the agent's history of actions and observations. They summarize everything the history says about the state, so planning in a POMDP is planning in a Markov decision process (MDP) over beliefs. Belief MDPs have continuous state spaces even for finite POMDPs, and exact planning in them is intractable in general. Planners must therefore approximate beliefs and estimate values. Monte Carlo planners do both inside a search tree, with an approximate belief at every node and a value estimate at every leaf. Approximations usually consist of sets of sampled states, with leaf values coming from rollouts, hand-designed bounds, or learned networks. Policies and values computed from these approximations are limited by their quality, and prior methods with learned networks rely on hand-chosen summaries of the sampled states. A belief representation should be computable from the parent node's representation through the POMDP's dynamics, let the search sample from it, and be learned so that it provides the information that policies and value functions need. We present Belief Embedding Tree Search (BETS), a Monte Carlo planner that meets these requirements by representing each node's belief with a generative distribution embedding (GDE) while updating it through the POMDP dynamics. BETS trains its belief model alongside its policy and value networks through experience, with the realized hidden state of the POMDP as the belief model's training target. We evaluate BETS on six configurations of RockSample, LightDark, and PocMan against BetaZero and three planners without learned components. BETS is competitive or leading on all six, while every baseline falls far behind on at least one. Where beliefs are highest-dimensional, it outperforms them by a large margin, even without search.

0.26

Subprocess-Constrained Markov Decision Processes

cs.AI ·2026-11-16 ·Jiarui Gan, Debmalya Mandal
top venuecode/data similarity 0.63
Abstract · To appear at NeurIPS '26. Code available at https://github.com/jrgan/VSI

Constrained Markov decision processes (CMDPs) typically bound expected cumulative cost from an initial state. Such a guarantee can be insufficient when a policy must remain feasible after every history it may encounter. We introduce \emph{subprocess-constrained MDPs} (S-CMDPs), which require the expected discounted cost of each continuation, conditional on any reachable history, to satisfy a bound determined by the current state. This stronger requirement changes the structure and complexity of the problem: we show that stationary policies can be strictly suboptimal, and finding even an approximately optimal stationary policy is NP-hard. We adapt a recently introduced value-set iteration framework to show that history-dependent policies surprisingly overcome both obstacles. Our polynomial-time algorithm represents such a policy implicitly: its expected reward is within $ε$ of the optimal feasible value, it violates each subprocess cost bound by at most $δ$, and its action distribution can be computed in polynomial time for any given history.

0.49

Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation

cs.LG ·2026-09-30 ·Kihyun Yu, Seoungbin Bae, Dabeen Lee
similarity 0.62
Abstract

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 computationally inefficient algorithms or have suboptimal dependence on the number of interactions $T$. We propose, to the best of our knowledge, the first computationally efficient algorithm that achieves $\widetilde{\mathcal{O}}(\sqrt{T})$ regret and cumulative constraint violation with high probability in the tabular setting. The $\sqrt{T}$ dependence is optimal up to logarithmic factors. Our approach incorporates cumulative constraint violation into the state and defines a reshaped reward through differences of a Huber potential. The added state determines the penalty on further violations while the reward function remains fixed on the augmented state space. Since the added state has known deterministic dynamics, only the original transition kernel needs to be estimated. The bounded slope of the Huber potential keeps the per-step reward bounded, and the potential differences telescope to relate the reshaped return to the original cumulative reward and the terminal potential. These properties allow us to apply finite-horizon approximation and optimistic value iteration with clipping, as used in unconstrained average-reward MDPs, without worsening the regret rate in $T$.

0.25

Risk-Averse Online POMDP Planning via CVaR of the Immediate Cost with Performance Guarantees

cs.AI ·2026-09-26 ·Yaacov Pariente, Vadim Indelman
similarity 0.62
Abstract

Online POMDP planners optimize the expected cumulative cost, which can mask dangerous states when the belief places significant mass on high-cost states. Existing risk-averse methods apply static or dynamic Conditional Value at Risk (CVaR) to the value function, capturing trajectory-level risk, but share two gaps: (i) by retaining the immediate cost as an expectation of a state-dependent cost over the belief, the risk \emph{within} the belief is left unaddressed; and (ii) by modifying the value function, they require new tailored algorithms rather than reusing existing expectation-based planners. We instead apply CVaR to the immediate cost over the belief at each step, directly targeting per-step uncertainty about the current state. The standard expected cumulative return is retained as the objective, so the resulting problem has a standard MDP structure: any expectation-based POMDP planner can be made risk-sensitive by changing only the cost computation. We inherit finite-time guarantees for policy evaluation and sparse sampling---with estimation error independent of the risk level---and, as our central theoretical result, prove a finite-time bound on the gap between the particle belief MDP surrogate and the original POMDP, which together yield an end-to-end guarantee from the true POMDP value to the algorithmic estimate. In the risk-neutral limit, the formulation recovers standard expectation-based planning.

0.13

Finite-Time Guarantees for Constrained Reinforcement Learning under Partial Observability

cs.LG ·2026-10-15 ·Valentina Zaccaria, Philip Jordan, Tingting Ni, Gian Antonio Susto, Maryam Kamgarpour
similarity 0.61
Abstract

We study reinforcement learning in constrained partially observable Markov decision processes (CPOMDPs), where an agent maximizes reward subject to a cost constraint using only incomplete information about the underlying state. The lack of state observability may require optimal policies to depend on arbitrarily long observation-action histories, making planning and learning challenging. We leverage recent advances in finite-memory approximations of POMDPs and represent finite history windows as states of a constrained MDP. We then develop a primal--dual algorithm that provides the first non-asymptotic guarantees that jointly bound average reward suboptimality and constraint violation in the original CPOMDP. A key challenge is that this finite-window approximation affects both reward values and the set of feasible policies. Under a filter-stability assumption, we derive bounds relating optimality and feasibility in the finite-state model to those in the original CPOMDP, with approximation errors that decay geometrically with the window length. Experiments in partially observable gridworlds demonstrate the effectiveness of our approach.

0.10

Near-Optimal Sample Complexity for Recursive Entropic Risk Reinforcement Learning with a Generative Model

cs.LG stat.ML ·2026-10-03 ·Amirparsa Bahrami, Oliver Mortensen, Mohammad Sadegh Talebi
similarity 0.60
Abstract

In this paper, we study the sample complexities of value and policy learning in finite discounted Markov decision processes (MDPs) under recursive entropic risk preferences with risk parameter \(β\neq 0\), assuming access to a generative model of the MDP. We provide a refined analysis of model-based risk-sensitive Q-value iteration (MB-RS-QVI), a plug-in model-based method introduced in prior work, and derive \((\varepsilon,δ)\)-PAC guarantees for both learning the optimal \(Q\)-value function and an \(\varepsilon\)-optimal policy. Our bounds improve the exponential dependence on the effective horizon \(1/(1-γ)\) compared with the best existing guarantees for this setting. In particular, they match the existing lower bounds in their exponential dependence on \(|β|/(1-γ)\), as well as in \(S\), \(A\), \(\varepsilon\), and \(|β|\), up to logarithmic factors. Consequently, our analysis removes the exponential gap between the previously known upper and lower bounds, leaving only a polynomial gap in the effective horizon.

0.13

Optimal Threshold Type Policies for Partially Observable Restless Bandits

eess.SY ·2026-09-12 ·Anu Krishna, Rahul Meshram, Kesav Ram Kaza
similarity 0.60
Abstract

We study a finite-state partially observable restless multi-armed bandit (PO-RMAB) motivated by resource-constrained wildlife monitoring. The underlying condition of each location evolves independently, while only a limited number of locations can be actively monitored at each decision epoch. Activation reveals the current state, whereas passive operation provides no observation, yielding a collapsing-bandit belief dynamics. Our main contribution is a structural characterisation of optimal policies for the multidimensional belief-state problem. We establish sufficient conditions under which an activation advantage is monotone with respect to the belief state, and hence the optimal policy has the threshold type structure over the $(M-1)$-dimensional belief simplex. The key result is obtained by bounding the variation of the value function through a model-dependent Lipschitz constant. We further specialise the result to one-step birth-death dynamics and derive explicit bounds.

0.05