Efficient computation of optimal actions

Emanuel Todorov

Proceedings of the National Academy of Sciences · 2009 · 435 citations · 12 references

DOIFull text

Open access

Concepts

TL;DR

Optimal action selection is a fundamental problem across many disciplines, yet remains hard due to overly generic formulations, and progress is accelerated when problems are structured, as seen in linear systems theory. We propose a more structured formulation that simplifies constructing optimal control laws in discrete and continuous domains. The framework linearizes the problem, avoiding exhaustive action search and enabling efficient construction of optimal control laws in both discrete and continuous settings. It yields algorithms that outperform Dynamic Programming and Reinforcement Learning, enables novel computations such as mixing primitives, applying deterministic methods to stochastic systems, quantifying error‑tolerance benefits, and inferring goals from behavioral data, potentially impacting many fields.

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.

References

12