Connected Superlevel Set in (Deep) Reinforcement Learning and its Application to Minimax Theorems

Sihan Zeng, Thinh T. Doan, Justin Romberg

Abstract

This research explores the topological structure of the reinforcement learning (RL) optimization landscape, specifically focusing on the connectedness of superlevel sets. While traditional analysis of policy optimization often relies on "gradient domination" to explain the convergence of local search methods, this property does not fully describe the global geometry of the policy space. This paper establishes that the "high-performance" regions of the policy space—sets of policies achieving a reward above a certain threshold—are connected in both tabular and over-parameterized deep RL settings. By introducing the property of "equiconnectedness," the authors provide the first formal proof of the existence of Nash equilibria in robust RL scenarios involving adversarial reward poisoning, leveraging Simons’ Minimax Theorem.

Introduction

Reinforcement learning (RL) is fundamentally an optimization problem over a notoriously non-convex landscape. To explain why simple algorithms like policy gradient often succeed despite this non-convexity, theorists have traditionally relied on the "gradient domination" property, which suggests that every stationary point is a global optimum. However, gradient domination provides an incomplete picture of the optimization landscape. It does not address whether the "high ground"—the set of policies that achieve at least a certain reward—is a single continuous landmass or a series of isolated islands.

If the landscape were "island-like," moving between two high-performing policies might require passing through a "valley" of poor performance, complicating both optimization and policy blending. This paper, presented at NeurIPS 2023, investigates this topological question and uses the resulting insights to solve a long-standing mystery in robust RL: the existence of stable Nash equilibria under reward attacks.

The Topology of Policy Space

The core of the researchers' analysis focuses on the superlevel set $\mathcal{U}_{\lambda,r}$, defined as the set of all policies $\pi$ that achieve an average reward $J_r(\pi) \geq \lambda$.

Tabular RL

In the tabular setting, where policies are represented as direct probability tables, the authors constructed a specific "path map." They demonstrated that for any two policies within a superlevel set, there exists a continuous path of intermediate policies that are guaranteed to perform at least as well as the starting points. This confirms that the high-performance regions in tabular RL are never disconnected islands.

Deep RL and Over-parameterization

The study extends these findings to deep neural networks, which introduce complex, non-linear mappings. The authors analyzed a class of over-parameterized networks where the first layer width ($n_1$) is at least twice the size of the state space ($|\mathcal{S}|$). By leveraging the properties of the softmax activation and the invertibility of specific network layers, they proved that this connectedness holds even within the high-dimensional parameter space of a neural network. This suggests that the inherent "niceness" of the RL objective is preserved by sufficiently wide neural architectures.

Equiconnectedness and the Minimax Theorem

A key contribution of the paper is the introduction of equiconnectedness. This is a stronger topological property where the path connecting two policies depends only on the policies themselves, rather than the specific reward function being optimized.

This property serves as the "secret sauce" for solving minimax problems in RL. Traditionally, proving the existence of a Nash equilibrium (where $\max \min f = \min \max f$) requires the objective function to be concave-convex. Since RL objectives are non-concave, this was previously unproven for robust RL. However, the authors realized that equiconnectedness allows the application of Simons’ Minimax Theorem, which establishes minimax equality for functions that possess this specific topological structure even in the absence of concavity.

Key Results and Implications

  • Formal Proof of Equiconnectedness: Theorems 1 and 2 in the paper formally establish that both tabular and sufficiently wide deep RL objectives are equiconnected.
  • Existence of Nash Equilibrium: The authors provide the first rigorous proof that a Nash equilibrium is guaranteed to exist in robust RL scenarios where an adversary modifies the reward function (reward poisoning).
  • Independence of Properties: The paper demonstrates that connectedness and gradient domination are independent properties. A landscape can have connected superlevel sets but still contain local "traps," or it can have no traps but possess disconnected islands of optimal solutions.

Limitations and Future Directions

While these theoretical results provide a new foundation for understanding RL optimization, they come with specific constraints:

  1. Architectural Requirements: The proof for deep RL relies on the condition $n_1 \geq 2|\mathcal{S}|$. In many real-world applications with massive state spaces, current neural networks are not this wide. Relaxing this assumption is a priority for future research.
  2. Observability: The findings assume a standard Markov Decision Process (MDP). In Partially Observable MDPs (POMDPs), the landscape is significantly more complex, and related work suggests that partial observability can break the connectedness of level sets.
  3. Algorithmic Design: The "path map" used in the proofs suggests a method for interpolating between policies without performance loss. This could lead to new, more stable algorithms for policy blending and multi-agent coordination.

Summary updated

Abstract

The aim of this paper is to improve the understanding of the optimization landscape for policy optimization problems in reinforcement learning. Specifically, we show that the superlevel set of the objective function with respect to the policy parameter is always a connected set both in the tabular setting and under policies represented by a class of neural networks. In addition, we show that the optimization objective as a function of the policy parameter and reward satisfies a stronger “equiconnectedness” property. To our best knowledge, these are novel and previously unknown discoveries. We present an application of the connectedness of these superlevel sets to the derivation of minimax theorems for robust reinforcement learning. We show that any minimax optimization program which is convex on one side and is equiconnected on the other side observes the minimax equality (i.e. has a Nash equilibrium). We find that this exact structure is exhibited by an interesting class of robust reinforcement learning problems under an adversarial reward attack, and the validity of its minimax equality immediately follows. This is the first time such a result is established in the literature.
BibTeX
@inproceedings{zeng2023connected,
  author = {Sihan Zeng and Thinh T. Doan and Justin Romberg},
  title = {{Connected Superlevel Set in (Deep) Reinforcement Learning and its Application to Minimax Theorems}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=WjDj6W872v},
}
Figure