This paper presents a novel gradient ascent al-gorithm and nonlinear programming algorithm for finite state controller policies in constrained partially observable Markov decision processes (CPOMDPs). A key component of the gradient ascent algorithm is a constraint projection to ensure constraints are satisfied. Both an optimal and an approximate projection are formally defined. A theoretical analysis of the algorithm and its projections is presented, formally proving aspects of projection correctness and algorithm convergence. Experiments evaluate the baseline and novel algorithms, as well as both constraint projections, on seven CPOMDP benchmark domains. The proposed novel algorithm is demonstrated on an actual robot performing a navigation task in a real household environment.

This paper presents a novel policy representation for partially observable Markov decision processes (POMDPs) called circulant controllers and a provably efficient gradient-based algorithm for them. A formal mathematical description is provided that leverages circulant matrices for the controller’s stochastic node transitions. This structure is particularly effective for capturing decision-making patterns found in real-world domains with repeated periodic behaviors that adapt their cycles based on observation. This includes domains such as bipedal walking over varied terrain, pick-and-place tasks in warehouses, and home healthcare monitoring and medicine delivery in household environments. A performant gradient-based algorithm is presented with a detailed theoretical analysis, formally proving the algorithm’s improved performance, as well as circulant controllers’ structural properties. Experiments on these domains demonstrate that the proposed controller algorithm outperforms other state-of-the-art POMDP controller algorithms. The proposed novel controller approach is demonstrated on an actual robot performing a navigation task in a real household environment.