Description:

Minimax Problems in Reinforcement Learning

Justin Romberg, Schlumberger Professor in the School of Electrical and Computer Engineering, Georgia Institute of Technology

Abstract: We will discuss progress on two minimax problems in reinforcement learning.  The first is a standard Markov game, where two agents are competing for rewards in an environment described by a Markov decision process.  Given a description of this environment, our goal is to compute a Nash equilibrium, a pair of policies that neither agent can improve on in response to the other.  We show that a simple gradient descent/ascent algorithm converges linearly for a regularized version of this problem, and we can achieve sublinear convergence to the true equilibrium through careful manipulation of the regularization parameter.

In the second part of the talk, we will discuss a standard form of robust reinforcement learning where a (single) agent searches for a policy that has the best worst-case performance over a convex set of reward functions.  Although this problem is convex in one variable but non-concave in the other, we show that there is minimax equality.  Key to this result is showing that the superlevel sets of the long-term reward for the agent are connected.  We also show that the minimax result extends to policies that are parameterized with neural networks.

This is joint work with Sihan Zeng and Thinh Doan.