Talk on Approximating Fixed Points of Approximated Functions
Date:
Long version of the CAV presentation associated to the paper of the same name.
Fixpoints play a critical role in many areas in computer science and there exist many often used results to find (least) fixpoints of a given contractive or monotone function. Standard fixpoint iteration schemes like the Kleene iteration assume complete knowledge of the target function. In reinforcement learning and many other practical applications, however, the exact function is not known but can only be approximated or sampled. In this talk, we take a look at how to approximate the least fixpoint of a (higher-dimensional) function over the non-negative reals, when the target function is not known precisely, but is represented by a sequence of approximating functions that converge to it. To achieve this, we consider a dampened version of a Mann iteration that, under suitable conditions, can be proven to converge to the least fixpoint of the function of interest. We will then see how these results can be applied to achieve convergence results for (model-based) reinforcement learning algorithms for (non-discounted) Markov decision processes.