Learning to Act Using Real-Time Dynamic Programming

By Andrew Barto, Steven J. Bradtke, Satinder Singh. 1995

Learning methods based on dynamic programming (DP) are receiving increasing attention in artificial intelligence. Researchers have argued that DP provides the appropriate basis for compiling planning results into reactive strategies for real-time control, as well as for learning such strategies when the system being controlled is incompletely known. We introduce an algorithm based on DP, which we call Real-Time DP (RTDP), by which an embedded system can improve its performance with experience. RTDP generalizes Korf''s Learning-Real-Time-A algorithm to problems involving uncertainty. We invoke results from the theory of asynchronous DP to prove that RTDP achieves optimal behavior in several different classes of problems. We also use the theory of asynchronous DP to illuminate aspects of other DP-based reinforcement learning methods such as Watkins'' Q-Learning algorithm. A secondary aim of this article is to provide a bridge between AI research on real-time planning and learning and relevant concepts and algorithms from control theory. This research was supported by grants to A.G. Barto from the National Science Foundation (ECS-8912623 and ECS-9214866) and the Air Force Office of Scientific Research, Bolling AFB (AFOSR-89-0526).

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

Hierarchical Reinforcement Learning with the MAXQ Value Function Decomposition (1999, methodology): “An interesting direction for future work is to apply online model-based methods such as ARTDP (Barto et al., 1995) or Prioritized Sweeping (Moore & Atkeson, 1993) in a similar way. The basic idea would be to apply stochastic approximation methods to construct models of Pi(s0js; a) and Ri(s0js; a) fo”
Online Meta-Learning (2019, neutral): “Prior works have also considered settings that combine joint training across tasks (in a sequential setting) with task-specific adaptation (Barto et al., 1995; Lowrey et al., 2019), but have not explicitly employed meta-learning.”
Plan Online, Learn Offline: Efficient Learning and Exploration via Model-Based Control (2018, background): “RTDP [34] considers learning value functions based on states visited by the agent, but does not explicitly employ the use of planning.”
Deep Variational Reinforcement Learning for POMDPs (2018, background): “…POMDP literature focusses on planning algorithms, where the transition and observation functions, as well as a representation of the latent state space, are known (Barto et al., 1995; McAllester & Singh, 1999; Pineau et al., 2003; Ross et al., 2008; Oliehoek et al., 2008; Roijers et al., 2015).”
Anytime Dynamic A*: An Anytime, Replanning Algorithm (2005, methodology): “To cope with imperfect information and dynamic environments, efficient replanning algorithms have been developed that correct previous solutions based on updated information (Stentz 1994; 1995; Koenig & Likhachev 2002b; 2002a; Ramalingam & Reps 1996; Barto, Bradtke, & Singh 1995).”
Online Planning Algorithms for POMDPs (2008, methodology): “An alternative approach to searching in AND-OR graphs is the RTDP algorithm (Barto et al., 1995) which has been adapted to solve POMDPs by Geffner and Bonet (1998).”
Adaptive Dynamic Programming for Control: A Survey and Recent Advances (2021, background): “[5], they introduced the so-called “adaptive real-time dynamic programming,” which was closely related to the topic reviewed in this article.”
Integrating a Partial Model into Model Free Reinforcement Learning (2012, methodology): “When a full model of state transitions is available, applying our method to Q-learning results in an algorithm known as Real Time Dynamic Programming (RTDP) (Barto et al., 1995).”
A Unified Analysis of Value-Function-Based Reinforcement-Learning Algorithms (1999, background): “Also, if we fix ct(x, a, y) = c(x, a, y) and pt(x, a, y) = Pr(y | x, a) for all t, x, y ∈ X and a ∈ A, this result implies that asynchronous dynamic programming converges to the optimal value function (Barto, Sutton, & Watkins, 1989; Bertsekas & Tsitsiklis, 1989; Barto et al., 1995).”
Reinforcement Learning and Its Relationship to Supervised Learning (2004, methodology): “There are policy-search methods that learn partial models to help compute gradients (Wang & Dietterich, 2003) and value function methods that learn partial models and perform incremental DP (Barto et al., 1995; Moore & Atkeson, 1993).”
Hierarchical Error Representation: A Computational Model of Anterior Cingulate and Dorsolateral Prefrontal Cortex (2015, methodology): “In our previous work, we suggested that multidimensional error signals generated by mPFC provide a plausible learning signal that may be used by a model-based RL algorithm, while other studies have associated activity in dlPFC with such a signal (Barto et al., 1995; Gläscher et al., 2010; Sutton, 19”
Average Reward Reinforcement Learning: Foundations, Algorithms, and Empirical Results (2005, methodology): “In our experiments, the temperature T was gradually decayed from an initial xed value using a decaying scheme similar to that described in [3].”
Elevator Group Control Using Multiple Reinforcement Learning Agents (1998, background): “Multi-agent RL combines some advantages of bottom-up and top-down approaches to the design of multi-agent systems.”
Reinforcement Learning in the Multi-Robot Domain (1997, background): “…the state representation used, reinforcement learning algorithms rely on their dynamic programming roots for clean theoretical convergence properties (Watkins and Dayan, 1992; Barto et al., 1993) which in turn require large numbers of learning trials that are prohibitive in physical robot domains .”
A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes (1999, methodology): “In this sense, our algorithm is clearly related to and inspired by classical look-ahead search techniques (Russell & Norvig, 1995) including various real-time search algorithms (Korf, 1990; Barto, Bradtke, & Singh, 1995; Bonet, Loerincs, & Geffner, 1997; Koenig & Simmons, 1998) and receding horizo”