2017

Environment-Independent Task Specifications via GLTL

Littman, Michael L., Topcu, Ufuk, Fu, Jie et al.

Understand

We propose a new task-specification language for Markov decision processes that is designed to be an improvement over reward functions by being environment independent.

The language is a variant of Linear Temporal Logic (LTL) that is extended to probabilistic specifications in a way that permits approximations to be learned in finite time.
We provide several small environments that demonstrate the advantages of our geometric LTL (GLTL) language and illustrate how it can be used to specify standard reinforcement-learning tasks straightforwardly.

Built on

Neuronlike adaptive elements that can solve difficult learning control problems
Barto, Andrew G., Sutton, Richard S., and Anderson, Charles W · 1983
Earlier work this paper cites.
Learning from Delayed Rewards
Watkins, Christopher J. C. H · 1989
Earlier work this paper cites.
Variable resolution dynamic programming: Efficiently learning action maps in multivariate real-valued spaces
Moore, Andrew W · 1991
Earlier work this paper cites.
The Temporal Logic of Reactive & Concurrent Sys.
Manna, Zohar and Pnueli, Amir · 1992
Earlier work this paper cites.
Using local trajectory optimizers to speed up global optimization in dynamic programming
Atkeson, Christopher G · 1994
Earlier work this paper cites.
Efficient reinforcement learning
Fiechter, Claude-Nicolas · 1994
Earlier work this paper cites.
Markov Decision Processes—Discrete Stochastic Dynamic Programming
Puterman, Martin L · 1994
Earlier work this paper cites.
Artificial Intelligence: A Modern Approach
Russell, Stuart J. and Norvig, Peter · 1994
Earlier work this paper cites.
Rewarding behaviors
Bacchus, Fahiem, Boutilier, Craig, and Grove, Adam · 1996
Earlier work this paper cites.
Formal verification of probabilistic systems
De Alfaro, Luca · 1998
Earlier work this paper cites.

Similar

Near-optimal reinforcement learning in polynomial time
Kearns, Michael and Singh, Satinder · 1998
Cited alongside, same era.
Decision-theoretic planning: Structural assumptions and computational leverage
Boutilier, Craig, Dean, Thomas, and Hanks, Steve · 1999
Cited alongside, same era.
Hierarchical reinforcement learning with the MAXQ value function decomposition
Dietterich, Thomas G · 2000
Cited alongside, same era.
R-MAX—a general polynomial time algorithm for near-optimal reinforcement learning
Brafman, Ronen I. and Tennenholtz, Moshe · 2002
Cited alongside, same era.
Near-optimal reinforcement learning in polynomial time
Kearns, Michael J. and Singh, Satinder P · 2002
Cited alongside, same era.
Prism: Probabilistic symbolic model checker
Kwiatkowska, Marta, Norman, Gethin, and Parker, David · 2002
Cited alongside, same era.
Discounting the future in systems theory
De Alfaro, Luca, Henzinger, Thomas A, and Majumdar, Rupak · 2003
Cited alongside, same era.
Model checking discounted temporal properties
De Alfaro, Luca, Faella, Marco, Henzinger, Thomas A, Majumdar, Rupak, and Stoelinga, Mariëlle · 2004
Cited alongside, same era.
Exploration and apprenticeship learning in reinforcement learning
Abbeel, Pieter and Ng, Andrew Y · 2005
Cited alongside, same era.
Principles of Model Checking
Baier, Christel and Katoen, Joost-Pieter · 2008
Cited alongside, same era.

Then

Temporal-logic-based reactive mission and motion planning
Kress-Gazit, H., Fainekos, G.E., and Pappas, G.J · 2009
Later among the works it cites.
Reinforcement learning in finite MDPs: PAC analysis
Strehl, Alexander L., Li, Lihong, and Littman, Michael L · 2009
Later among the works it cites.
Ltl control in uncertain environments with probabilistic satisfaction guarantees
Original
Ding, Xu Chu, Smith, Stephen L., Belta, Calin, and Rus, Daniela · 2011
Later among the works it cites.
Correct, reactive robot control from abstraction and temporal logic specifications
Kress-Gazit, H., Wongpiromsarn, T., and Topcu, U · 2011
Later among the works it cites.
Control of Markov decision processes from PCTL specifications
Lahijanian, M., Andersson, S. B., and Belta, C · 2011
Later among the works it cites.
Knows what it knows: A framework for self-aware learning
Li, Lihong, Littman, Michael L., Walsh, Thomas J., and Strehl, Alexander L · 2011
Later among the works it cites.
Robust control of uncertain markov decision processes with temporal logic specifications
Wolff, Eric M., Topcu, Ufuk, and Murray, Richard M · 2012
Later among the works it cites.
Receding horizon temporal logic planning
Wongpiromsarn, T., Topcu, U., and Murray, R.M · 2012
Later among the works it cites.
Synthesis of reactive switching protocols from temporal logic specifications
Liu, Jun, Ozay, Necmiye, Topcu, Ufuk, and Murray, Richard M · 2013
Later among the works it cites.
Discounting in ltl
Almagor, Shaull, Boker, Udi, and Kupferman, Orna · 2014
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…