Information theoretic tools for stable adaptation and learning

Lyapunov design has never been systematic. In the adaptive control of complex multi‐input non‐linear systems, physical considerations, such as conservation of energy or entropy increase, represent one of the major tools in building Lyapunov‐like functions and providing stability and performance guarantees. In this paper we show that a physically motivated Lyapunov‐like function based on the concept of total information can be derived for large classes of non‐linear physical systems. We study how this function may be used for designing estimation, adaptation and learning mechanisms for such systems. In the process we revisit familiar notions such as controllability and observability from an information perspective, which in turns allows us to define ‘natural’ space‐time scales at which to observe and control a given complex system. By formulating control problems in algorithmic form, we emphasize the importance of computability and computational complexity for issues of control. Generic control problems are shown to be NP ‐hard: each additional complication, such as the presence of noise or the absence of complete system identification, moves the control problem further up the polynomial hierarchy of computational complexity. In some cases, requirements of ‘optimality’ may be unrealistic or irrelevant, since the solution to the problem of finding the optimal algorithm for control is uncomputable.