Connected Superlevel Set in (Deep) Reinforcement Learning and its Application to Minimax Theorems
Not on the map. Why?
Abstract (arXiv)
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 robust reinforcement learning problem 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.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 37 of its 56 references that are in the map. First posted on arXiv 23 Mar 2023.
Builds on
37 of 56 references.
References · 37
- 2016Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Conditioncited by 526
- 2015Empirical Evaluation of Rectified Activations in Convolutional Networkcited by 515
- 2017A Brief Survey of Deep Reinforcement Learningcited by 466
- 2017Robust Adversarial Reinforcement Learningcited by 439
- 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
- 2020Robust Deep Reinforcement Learning against Adversarial Perturbations on State Observationscited by 235
- 2020Loss landscapes and optimization in over-parameterized non-linear systems and neural networkscited by 231
- 2018Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulatorcited by 211
- 2019On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shiftcited by 174
- 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 170
- 2019Action Robust Reinforcement Learning and Applications in Continuous Controlcited by 167
- 2019Solving a Class of Non-Convex Min-Max Games Using Iterative First Order Methodscited by 148
25 more
- 2019Global Optimality Guarantees For Policy Gradient Methodscited by 146
- 2019An Improved Analysis of Training Over-parameterized Deep Neural Networkscited by 120
- 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 120
- 2022On the Convergence Rates of Policy Gradient Methodscited by 115
- 2018The Limit Points of (Optimistic) Gradient Descent in Min-Max Optimizationcited by 98
- 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 82
- 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 81
- 2020Policy Teaching via Environment Poisoning: Training-time Adversarial Attacks against Reinforcement Learningcited by 81
- 2018Reinforcement Learning with Perturbed Rewardscited by 76
- 2020SGD for Structured Nonconvex Functions: Learning Rates, Minibatching and Interpolationcited by 66
- 2020Robust Reinforcement Learning using Adversarial Populationscited by 64
- 2019On Connected Sublevel Sets in Deep Learningcited by 51
- 2020On Linear Convergence of Policy Gradient Methods for Finite MDPscited by 51
- 2019Convergence and sample complexity of gradient methods for the model-free linear quadratic regulator problemcited by 35
- 2017Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problemscited by 32
- 2022First-order Policy Optimization for Robust Markov Decision Processcited by 31
- 2018Local Saddle Point Optimization: A Curvature Exploitation Approachcited by 28
- 2020A Decentralized Policy Gradient Approach to Multi-task Reinforcement Learningcited by 24
- 2023Robust Average-Reward Markov Decision Processescited by 22
- 2021Defense Against Reward Poisoning Attacks in Reinforcement Learningcited by 20
- 2021A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learningcited by 20
- 2020Optimizing Static Linear Feedback: Gradient Methodcited by 19
- 2022Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Gamescited by 18
- 2018Online Robust Policy Learning in the Presence of Unknown Adversariescited by 15
- 2022Reward Delay Attacks on Deep Reinforcement Learningcited by 5
Built on by
Citing papers per year: 2023: 1; 2024: 2.
3 papers.