Provably Efficient Actor-Critic for Risk-Sensitive and Robust Adversarial RL: A Linear-Quadratic Case

Yufeng Zhang, Zhuoran Yang, Zhaoran WangAISTATS 2021 · OpenReview

Abstract

Risk-sensitivity is a cornerstone of safety in artificial intelligence. This paper investigates the global convergence of the actor-critic algorithm for risk-sensitive reinforcement learning (RSRL) utilizing exponential utility. This setting is traditionally challenging for policy optimization due to a lack of linearity, which complicates the formulation of policy gradients. To address this, we leverage the mathematical equivalence between RSRL and robust adversarial reinforcement learning (RARL), formulated as a zero-sum Markov game with a hypothetical adversary. We focus on the linear-quadratic (LQ) game setting and introduce a Nested Natural Actor-Critic (NENAC) algorithm. Our work demonstrates that NENAC provably converges to the Nash Equilibrium (NE) at a sublinear rate. This represents the first model-free policy optimization algorithm to achieve such guarantees for RSRL and RARL in the LQ setting.

Introduction

Standard reinforcement learning (RL) typically focuses on maximizing the expected sum of rewards. However, in safety-critical domains such as autonomous robotics or financial engineering, the average outcome is often less important than the "worst-case" or high-variance outcomes. Two primary frameworks have emerged to address these concerns: Risk-Sensitive RL (RSRL), which uses exponential utility functions to penalize variance, and Robust Adversarial RL (RARL), which models environmental uncertainties as an adversarial agent.

Despite their importance, these frameworks present significant optimization hurdles. RSRL’s exponential utility is inherently non-linear, breaking the standard policy gradient theorems that RL relies upon. RARL, meanwhile, requires solving a minimax problem, which is notoriously unstable and prone to divergence or cycling in non-convex settings. Historically, solutions have been model-based, requiring perfect knowledge of the system's underlying physics. This paper bridges the gap by providing a model-free approach that is both provably robust and efficient.

The Equivalence Trick: Bridging Risk and Robustness

A key contribution of this work is the exploitation of a mathematical duality between log-moment generating functions and Kullback–Leibler (KL) divergence. In the Linear-Quadratic (LQ) setting—where transitions are linear and costs are quadratic—the authors show that RSRL, RARL, and zero-sum Markov games are essentially equivalent.

By reframing the risk-sensitivity problem as a zero-sum game, the non-linearity of the exponential utility is bypassed. Instead of differentiating a complex non-linear objective, the problem becomes one of finding the Nash Equilibrium (NE) of a game where a protagonist (the agent) minimizes costs while a hypothetical adversary maximizes them. The NE of this game yields a policy that is inherently robust to model perturbations.

The Nested Natural Actor-Critic (NENAC) Algorithm

To solve the resulting minimax problem without requiring a model of the environment, the authors propose the Nested Natural Actor-Critic (NENAC) algorithm. The "nested" structure is critical for maintaining stability during the competitive optimization process:

  1. Inner Loop (The Agent): The agent uses a Natural Actor-Critic approach to find the best response to the adversary's current strategy. Because the agent's sub-problem is a standard LQ regulator, this loop converges at a fast linear rate.
  2. Outer Loop (The Adversary): The adversary updates its strategy using a projected natural policy gradient based on the agent's current performance.
  3. The Critic: To remain model-free, the algorithm employs a variant of Gradient Temporal Difference (GTD). This allows the agent to estimate the parameters of the $Q$-function (the value of state-action pairs) directly from sample data (states, actions, and costs) rather than relying on known system matrices.

Theoretical Results and Convergence

This paper provides the first non-asymptotic convergence results for a model-free actor-critic algorithm in this context. The primary findings include:

  • Global Convergence: NENAC is guaranteed to converge to the Nash Equilibrium, ensuring the discovery of the optimal robust policy.
  • Efficiency: While the inner loop converges linearly, the overall algorithm converges at a sublinear rate of $O(1/\sqrt{N})$. This is a significant theoretical milestone, proving that robust policies can be learned efficiently from samples alone.
  • Stability: The nested update schedule—where the agent updates faster than the adversary—effectively prevents the "cycling" behavior often seen in competitive optimization (such as in Generative Adversarial Networks).

Discussion and Limitations

While this work provides a rigorous foundation for robust RL, it focuses on the Linear-Quadratic case. The LQ setting is the "Drosophila" of control theory—it is fundamental and provides deep insights, but real-world systems are frequently non-linear. Extending these proofs to general non-linear function approximations, such as deep neural networks, remains a significant open challenge.

Furthermore, while the algorithm is proven to be efficient (polynomial time), the exact sample complexity relative to non-robust methods remains a subject for future refinement. Finally, the practical application of RARL requires careful design of the adversary's constraints; an overly powerful adversary may lead to overly conservative policies, a trade-off that practitioners must balance.

Conclusion

By establishing a formal link between risk-sensitivity and adversarial robustness, this research provides a clear path for developing safe RL agents. The NENAC algorithm demonstrates that it is possible to achieve global convergence in complex minimax games using only model-free samples, shedding light on how we might scale robust reinforcement learning to more general and complex environments.

Summary updated

Abstract

Risk-sensitivity plays a central role in artificial intelligence safety. In this paper, we study the global convergence of the actor-critic algorithm for risk-sensitive reinforcement learning (RSRL) with exponential utility, which remains challenging for policy optimization as it lacks the linearity needed to formulate policy gradient. To bypass such an issue of nonlinearity, we resort to the equivalence between RSRL and robust adversarial reinforcement learning (RARL), which is formulated as a zero-sum Markov game with a hypothetical adversary. In particular, the Nash equilibrium (NE) of such a game yields the optimal policy for RSRL, which is provably robust. We focus on a simple yet fundamental setting known as linear-quadratic (LQ) game. To attain the optimal policy, we develop a nested natural actor-critic algorithm, which provably converges to the NE of the LQ game at a sublinear rate, thus solving both RSRL and RARL. To the best knowledge, the proposed nested actor-critic algorithm appears to be the first model-free policy optimization algorithm that provably attains the optimal policy for RSRL and RARL in the LQ setting, which sheds light on more general settings.
BibTeX
@inproceedings{zhang2021provably,
  author = {Yufeng Zhang and Zhuoran Yang and Zhaoran Wang},
  title = {{Provably Efficient Actor-Critic for Risk-Sensitive and Robust Adversarial RL: A Linear-Quadratic Case}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2021},
  url = {https://openreview.net/forum?id=xphGuJQcFu},
}
Figure