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

Overview & Synopsis

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.