{'fraction_non_alphanumeric': 0.01839464882943144, 'fraction_numerical': 0.0, 'mean_word_length': 5.170103092783505, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Region-Based Dynamic Programming for POMDPs

We present a major improvement to the dynamic programming (DP) algorithm for solving partially observable Markov decision processes (POMDPs). Our technique first targets the cross-sum pruning step of the DP update, a key source of complexity in POMDP algorithms. Unlike previous approaches, which reason about the whole belief space, the algorithms we present divide the belief space into smaller regions and perform independent pruning in each region. Because the number of useful vectors over each region can be much smaller than those over the whole belief space, we show that the linear programs used in the pruning process can be made exponentially smaller. With this exponential improvement to cross-sum pruning, we shift our attention to the next bottleneck, the maximization pruning step. Using the same region-based reasoning, we identify two types of structures in the belief space of a POMDP and show how to exploit them to reduce significantly the number of constraints in the linear programs used for maximization pruning. We discuss future research directions on extending these techniques to improve the scalability of POMDP algorithms.