ρ-POMDPs have Lipschitz-Continuous -Optimal Value Functions
Many state-of-the-art algorithms for solving Partially Observable Markov Decision Processes (POMDPs) rely on turning the problem into a "fully observable" problem-a belief MDP-and exploiting the piece-wise linearity and convexity (PWLC) of the optimal value function in this new state space (the belief simplex ∆). This approach has been extended to solving ρ-POMDPs-i.e., for informationoriented criteria-when the reward ρ is convex in ∆. General ρ-POMDPs can also be turned into "fully observable" problems, but with no means to exploit the PWLC property. In this paper, we focus on POMDPs and ρ-POMDPs with λ ρ -Lipschitz reward function, and demonstrate that, for finite horizons, the optimal value function is Lipschitz-continuous. Then, value function approximators are proposed for both upper-and lower-bounding the optimal value function, which are shown to provide uniformly improvable bounds. This allows proposing two algorithms derived from HSVI which are empirically evaluated on various benchmark problems.
post-rebuttal: I have a small suggestion for the authors to include the related work in the paper if they can and to put a small experiment in the paper where surveillance is the goal of the agent. This is the main motivation of the paper. Overall I am happy with the paper and response.   ----- Summary: This paper presents a method for solving POMDPs (offline POMDP planning) when the value function of the POMDP is not necessarily convex (mainly breaking the PWLC property exploited by most POMDP planners). The paper presents a new POMDP planner based on heuristic search value iteration that does not rely on convexity of the optimal value function to compute it. The idea is to use upper and lower bound on the value function (and then tighten them at various beliefs) to compute the optimal value function (or an approximation of it). The property that the paper exploits to generate these upper and lower bounds is that the optimal value function has to be Lipschitz continuous. The paper also shows that if the immediate expected reward is Lipschitz continuous then the optimal value function is guaranteed to be Lipschitz continuous and then exploits this property of the value function to propose upper and lower bounds on the value function by obtaining an expression for the Lipschitz contant for the curves (cones in this case) to upper and lower bound the value function. Finally, the paper gives empirical results on standard POMDP problems in literature.   Quality - This is a good quality paper; thorough and rigorous for most parts.   Clarity: The paper is clear and well-written.   Originality: The paper presents original work.   Significance: I think the paper presents significant results that are relevant to this community.   Strength: I believe the main strength of the paper is the carefully designed and principle method for obtaining Lipschitz continuous upper and lower bound on the value function of a POMDP.   Weakness:  - I am quite not convinced by the experimental results of this paper. The paper sets to solve POMDP problem with non-convex value function. To motivate the case for their solution the examples of POMDP problem with non-convex value functions used are: (a) surveillance in museums with thresholded rewards; (b) privacy preserving data collection.  So then the first question is when the case we are trying to solve are above two, why is there not a single experiment on such a setting, not even a simulated one? This basically makes the experiments section not quite useful.   - How does the reader know that the reward definitions of rho for this tasks necessitates a non-convex reward function. Surveillance and data collection has been studied in POMDP context by many papers. Fortunately/unfortunately, many of these papers show that the increase in the reward due to a rho based PWLC reward in comparison to a corresponding PWLC state-based reward (R(s,a)) is not that big. (Papers from Mykel Kochenderfer, Matthijs Spaan, Shimon Whiteson are some I can remember from top of my head.) The related work section while missing from the paper, if existed, should cover papers from these groups, some on exactly the same topic (surveillance and data collection).   - This basically means that we have devised a new method for solving non-convex value function POMDPs, but do we really need to do all that work?  The current version of the paper does not answer this question to me. Also, follow up question would be exactly what situation do I want to use the methodology proposed by this paper vs the existing methods.   In terms of critisim of significance, the above points can be summarized as why should I care about this method when I do not see the results on problem the method is supposedly designed for.