Feature-based methods for large scale dynamic programming

By John N. Tsitsiklis, Benjamin Van Roy. 1995

We develop a methodological framework and present a few different ways in which dynamic programming and compact representations can be combined to solve large scale stochastic control problems. In particular, we develop algorithms that employ two types of feature-based compact representations; that is, representations that involve feature extraction and a relatively simple approximation architecture. We prove the convergence of these algorithms and provide bounds on the approximation error. As an example, one of these algorithms is used to generate a strategy for the game of Tetris. Furthermore, we provide a counter-example illustrating the difficulties of integrating compact representations with dynamic programming, which exemplifies the shortcomings of certain simple approaches.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

An Emphatic Approach to the Problem of Off-policy Temporal-Difference Learning (2015, methodology): “using an argument similar to that given here about column sums and the Varga (1962) theorem for irreducibly diagonally dominant matrices (Yu 2015a, see also Mahmood et al.”
On Learning to Think: Algorithmic Information Theory for Novel Combinations of Reinforcement Learning Controllers and Recurrent Neural World Models (2015, methodology): “The parameters or weights of C are trained to maximize reward by a standard RL method such as Q-learning or similar methods [17, 292, 293, 172, 254, 212, 262, 10, 122, 188, 157, 281, 26, 216, 197, 272, 311, 9, 163, 174, 22, 27, 2, 137, 276, 156, 284].”
Interpolation-based Q-learning (2004, background): “In (Gordon, 1995) and indepentently in (Tsitsiklis & Van Roy, 1996) convergence results were derived for approximate dynamic programming when the “value-ﬁtting operator” was chosen to be a non-expansion or an ‘almost non-expansion’.”
Computing Factored Value Functions for Policies in Structured MDPs (1999, methodology): “This idea is best known under the name value function approximation, which is used frequently in the context or reinforcement learning [Tadepalli and Ok, 1996; Van Roy, 1998].”
Approximate modified policy iteration and its application to the game of Tetris (2015, background): “On the other hand, approximate PI (API) first finds an approximation of the value of the current policy and then generates the next policy as greedy w.r.t. this approximation (Bertsekas and Tsitsiklis, 1996; Munos, 2003; Lagoudakis and Parr, 2003a; Lazaric et al., 2010b, 2012).”
Near-Optimal Reinforcement Learning in Polynomial Time (2002, background): “While some results are available on reinforcement learning and function approximation (Sutton, 1988; Singh, Jaakkola, & Jordan, 1995; Gordon, 1995; Tsitsiklis & Roy, 1996), and for partially observable MDPs (Chrisman, 1992; Littman, Cassandra, & Kaelbling, 1995; Jaakkola, Singh, & Jordan, 1995),…”
Deep learning in neural networks: An overview (2014, background): “The contents of this paper may be used for educational and noncommercial purposes, including articles for Wikipedia and similar sites.”
Q-learning and enhanced policy iteration in discounted dynamic programming (2010, background): “The randomized policy encodes aspects of (or as a special case, may be equal to) the “current policy” and gives our algorithm a modified PI character.”
Learning near-optimal policies with Bellman-residual minimization based fitted policy iteration and a single sample path (2006, unknown): “Recent theoretical results mostly concern supremum-norm approximation errors [15, 16], where the main condition on the way intermediate iterates are mapped (projected) to the function space is that the corresponding operator, Π , must be a non-expansion.”
Towards Understanding Linear Value Decomposition in Cooperative Multi-Agent Q-Learning (2020, background): “Many counterexamples have been proposed to indicate certain function classes suffering from oscillation [35] or even unbounded divergence [36,37].”
A Survey of Deep Learning Applications to Autonomous Vehicle Control (2019, background): “The disadvantage of this approach is that there is no guarantee on the optimality of the learned policy [61], [62].”