Efficient computation of optimal actions
- 14 July 2009
- journal article
- Published by Proceedings of the National Academy of Sciences in Proceedings of the National Academy of Sciences
- Vol. 106 (28), 11478-11483
- https://doi.org/10.1073/pnas.0710743106
Abstract
Optimal choice of actions is a fundamental problem relevant to fields as diverse as neuroscience, psychology, economics, computer science, and control engineering. Despite this broad relevance the abstract setting is similar: we have an agent choosing actions over time, an uncertain dynamical system whose state is affected by those actions, and a performance criterion that the agent seeks to optimize. Solving problems of this kind remains hard, in part, because of overly generic formulations. Here, we propose a more structured formulation that greatly simplifies the construction of optimal control laws in both discrete and continuous domains. An exhaustive search over actions is avoided and the problem becomes linear. This yields algorithms that outperform Dynamic Programming and Reinforcement Learning, and thereby solve traditional problems more efficiently. Our framework also enables computations that were not possible before: composing optimal control laws by mixing primitives, applying deterministic methods to stochastic systems, quantifying the benefits of error tolerance, and inferring goals from behavioral data via convex optimization. Development of a general class of easily solvable problems tends to accelerate progress--as linear systems theory has done, for example. Our framework may have similar impact in fields where optimal choice of actions is relevant.Keywords
This publication has 11 references indexed in Scilit:
- Eigenfunction approximation methods for linearly-solvable optimal control problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2009
- General duality between optimal control and estimationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2008
- Linear Theory for Control of Nonlinear Stochastic SystemsPhysical Review Letters, 2005
- Learning physics-based motion style with nonlinear inverse optimizationACM Transactions on Graphics, 2005
- Optimality principles in sensorimotor controlNature Neuroscience, 2004
- A Variational Approach to Nonlinear EstimationSIAM Journal on Control and Optimization, 2003
- Numerical Methods for Stochastic Control Problems in Continuous TimeStochastic Modelling and Applied Probability, 2001
- Reinforcement Learning: An IntroductionIEEE Transactions on Neural Networks, 1998
- Q-learningMachine Learning, 1992
- Optimal Control and Nonlinear Filtering for Nondegenerate Diffusion ProcessesStochastics, 1982