Abstract

Optimal choice of actions is relevant to fields as diverse as neuroscience, psychology, economics, operations research, computer science, robotics and automation, aerospace engineering. Despite this broad relevance the abstract setting is similar: we have an agent choosing actions over time, a dynamical system whose state is affected by those actions, and a cumulative performance criterion which the agent seeks to optimize. Designing synthetic agents that can solve problems of this kind, or understanding how natural agents manage to do so, remains hard. The difficulties are partly due to overly generic problem formulations. Here we propose a more structured formulation in which optimal choice of actions is greatly simplified: it is reduced to a linear problem, in both discrete and continuous domains. This facilitates the computation of solutions, gives rise to unique theoretical properties, and yields original algorithms that solve existing problems faster than Dynamic Programming and Reinforcement Learning. Discovery of a general class of easily solvable problems tends to motivate researchers to reformulate or approximate their problems within the new class. Our results suggest that in many cases this will be possible. The new framework is likely to find applications in diverse fields of science and engineering.