Algebraic optimization of sequential decision problems

DOI10.1016/J.JSC.2023.102241MaRDI QIDQ6051114zbMATH OpenFDO

Authors

Publication date 19 September 2023

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2211.09439

algebraic degree partially observable Markov decision process polynomial optimization state aggregation state-action frequencies

Mathematics Subject Classification ID

Algebraic statistics (62R01) Polynomial optimization (90C23) Markov and semi-Markov decision processes (90C40)

Abstract: We study the optimization of the expected long-term reward in finite partially observable Markov decision processes over the set of stationary stochastic policies. In the case of deterministic observations, also known as state aggregation, the problem is equivalent to optimizing a linear objective subject to quadratic constraints. We characterize the feasible set of this problem as the intersection of a product of affine varieties of rank one matrices and a polytope. Based on this description, we obtain bounds on the number of critical points of the optimization problem. Finally, we conduct experiments in which we solve the KKT equations or the Lagrange equations over different boundary components of the feasible set, and compare the result to the theoretical bounds and to other constrained optimization methods.

Recommendations

Cites work

This page was built for publication: Algebraic optimization of sequential decision problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6051114)