Symbolic Dynamic Programming for First-Order MDPs

By Craig Boutilier, Raymond Reiter, Bob Price. 2001

292 citations recorded by the source corpus.

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

Fitted Q-Learning for Relational Domains (2020, background): “Consequently, a class of RL meth-ods, called Relational Markov Decision Process (RMDPs), have been developed for learning optimal behaviour in these worlds, and methods that directly learn and reason at the ﬁrst-order level have been developed in the broad area of Relational Reinforcement Learning (”
Towards Continual Reinforcement Learning: A Review and Perspectives (2020, background): “…to provide additional opportunities for generalization including relational MDPs (Guestrin, Koller, Gearhart, and Kanodia, 2003), first-order MDPs (Boutilier, Reiter, and Price, 2001), object-oriented MDPs (Diuk, Cohen, and Littman, 2008), and MDPs described by linear temporal logic (Vaezipoor,…”
Practical solution techniques for first-order MDPs (2009, methodology): “The first-order decision-theoretic regression (FODTR) (Boutilier et al., 2001) of this value function through an action A(~x) yields a case statement containing the logical descriptionof states and values that would give rise toV (s) after doing actionA(~x).”
Neural Logic Reinforcement Learning (2019, background): “Early attempts that represent states by ﬁrst-order logics in MDPs appeared at the beginning of this century (Boutilier et al., 2001; Yoon et al., 2002; Guestrin et al., 2003), however, these works focused on the situation that transitions and reward structures are known to the agent.”
Approximate Policy Iteration with a Policy Language Bias (2003, unknown): “More recent work extends these algorithms to use propositional [6, 11, 7, 12] as well as relational [ 8 ] state- space representations.”
Reasoning about Probabilities in Dynamic Systems using Goal Regression (2013, background): “There is one other thread of related work, that of symbolic dynamic programming (Boutilier et al., 2000, 2001) which also has recent continuous extensions (Sanner et al., 2011).”
Learning Symbolic Models of Stochastic Domains (2007, background): “…1998; Guestrin, Koller, Parr, & Venkataraman, 2003), and some ﬁrst-order representations have been developed, including probabilistic rules (Blum & Lang-ford, 1999), equivalence classes (Draper, Hanks, & Weld, 1994), and the situation calculus approach of Boutilier, Reiter, and Price (2001).”
An algebraic approach to abstraction in reinforcement learning (2004, background): “The proof of this statement follows along the lines of Dietterich [5].”
Approximate Policy Iteration with a Policy Language Bias: Solving Relational Markov Decision Processes (2011, methodology): “The Ground Logistics domain is originally from Boutilier et al. (2001), and was also used for evaluation in Yoon et al. (2002).”
Solving Relational and First-Order Logical Markov Decision Processes: A Survey (2012, methodology): “The first method is the symbolic dynamic programming ( SDP) approach (Boutilier et al, 2001) based on the situation calculus language (see Reiter, 2001).”
First Order Decision Diagrams for Relational MDPs (2007, methodology): “While relational value iteration was developed and specified in previous work (Boutilier et al., 2001), to our knowledge this is the first detailed proof of correctness and convergence for the algorithm.”
Relational Reinforcement Learning An Overview (2004, background): “Boutilier generalized the resulting explanation-based reinforcement learning (EBRL) to stochastic domains, whose reward models are described by structured Bayesian networks, thus making them amenable to symbolic reasoning (Boutilier et al., 2001).”
Generalizing plans to new environments in relational MDPs (2003, background): “[1] on symbolic value iteration computes first-order value func tions, which generalize over objects.”
A logical theory of robot localization (2014, background): “Finally, there has been recent work on Symbolic POMDPs, which are also based on first-order formalisms such as the situation calculus [36, 6].”