{'fraction_non_alphanumeric': 0.02564102564102564, 'fraction_numerical': 0.0, 'mean_word_length': 5.546583850931677, '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}}
Fast Approximate Dynamic Programming for Infinite-Horizon Continuous-State Markov Decision Processes

In this article, we consider the infinite-horizon, discounted cost, optimal control of discrete-time systems with separable cost and constraint in the state and input variables. Starting from deterministic linear dynamics, we introduce a novel numerical algorithm for implementation of the value iteration (VI) algorithm in the conjugate domain, using the Linear-time Legendre Transform algorithm. Detailed analyses of the convergence, complexity, and error of the proposed algorithm are provided. In particular, with a discretization of size X and U for the state and input spaces, respectively, the proposed approach can reduce the time complexity of each iteration of the VI algorithm from O(XU) to O(X), by replacing the minimization operation in the primal domain with a simple addition in the conjugate domain. Also discussed are the direct extensions of the proposed algorithm for nonlinear dynamics and stochastic dynamics with additive noise.