Search

This paper discusses the model problem presented in "A model for system uncertainty in reinforcement learning", Systems and Control Letters, 2018, for certain tasks in reinforcement learning. The model provides a framework to deal with situations in which the system dynamics is not known and encodes the available information about the state dynamics as a measure on the space of functions. Such a measure is updated in time, taking into account all the previous measurements of the state variable and extracting new information from them. Here we will mainly focus on the differences between the present model and central algorithms used in reinforcement learning (i.e. value iteration and Thompson sampling).

The paper studies a distributed gradient descent (DGD) process and considers the problem of showing that in nonconvex optimization problems, DGD typically converges to local minima rather than saddle points. The paper considers unconstrained minimization of a smooth objective function. In centralized settings, the problem of demonstrating nonconvergence to saddle points of gradient descent (and variants) is typically handled by way of the stable-manifold theorem from classical dynamical systems theory. However, the classical stable-manifold theorem is not applicable in distributed settings. The paper develops an appropriate stable-manifold theorem for DGD showing that convergence to saddle points may only occur from a low-dimensional stable manifold. Under appropriate assumptions (e.g., coercivity), this result implies that DGD typically converges to local minima and not to saddle points.

The paper studies properties of best-response (BR) dynamics in potential games with continuous action sets. It is known that BR dynamics converge to the set of Nash equilibria (NE) in potential games. The set of NE in potential games is composed of local maximizers and saddle points of the potential function. The paper studies non-convergence of BR dynamics to saddle points of the potential function. Under relatively mild assumptions it is shown that BR dynamics may only converge to an interior saddle-point from a measure-zero set of initial conditions. This provides a weak stable manifold theorem in this context.