We show how to approximate least fixpoints of a (higher-dimensional) function over the non-negative reals, where the function is not known precisely, but is represented by a sequence of approximating functions that converge to it. We concentrate on monotone and non-expansive functions, for which uniqueness of fixpoints is not guaranteed and standard fixpoint iteration schemes might get stuck at a fixpoint that is not the least. Our contribution is to show that a Mann iteration scheme with a dampening factor guarantees convergence to the least fixpoint for exact functions and even for approximated functions, under certain conditions. In particular, these results are interesting in the context of model-based reinforcement learning for Markov Decision Processes (MDPs) and we show that MDPs satisfy the required conditions. Even for functions where the conditions are not satisfied we explain how one can still iterate to the least fixpoint almost surely by requiring that the approximating functions are sampled in a way that is compatible with the convergence rate.
This is joint work with Paolo Baldan, Sebastian Gurke, Tommaso Padoan, Florian Wittbold.