A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic

Abstract

This paper analyzes a two-timescale stochastic algorithm framework for bilevel optimization. Bilevel optimization is a class of problems which exhibit a two-level structure, and its goal is to minimize an outer objective function with variables which are constrained to be the optimal solution to an (inner) optimization problem. We consider the case when the inner problem is unconstrained and strongly convex, while the outer problem is constrained and has a smooth objective function. We propose a two-timescale stochastic approximation (TTSA) algorithm for tackling such a bilevel problem. In the algorithm, a stochastic gradient update with a larger step size is used for the inner problem, while a projected stochastic gradient update with a smaller step size is used for the outer problem. We analyze the convergence rates for the TTSA algorithm under various settings: when the outer problem is strongly convex (resp.~weakly convex), the TTSA algorithm finds an $\mathcal{O}(K^{-2/3})$-optimal (resp.~$\mathcal{O}(K^{-2/5})$-stationary) solution, where $K$ is the total iteration number. As an application, we show that a two-timescale natural actor-critic proximal policy optimization algorithm can be viewed as a special case of our TTSA framework. Importantly, the natural actor-critic algorithm is shown to converge at a rate of $\mathcal{O}(K^{-1/4})$ in terms of the gap in expected discounted reward compared to a global optimal policy.

Minor revision

References in corpus (11)

• Finite-Sample Analysis of Proximal Gradient TD Algorithms
• Information-Theoretic Considerations in Batch Reinforcement Learning
• Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples
• A Finite Time Analysis of Two Time-Scale Actor Critic Methods
• Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms
• Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise
• Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learning
• A Generic First-Order Algorithmic Framework for Bi-Level Programming Beyond Lower-Level Singleton
• Improved Bilevel Model: Fast and Optimal Algorithm with Theoretical Guarantee
• A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Bound
• UFO-BLO: Unbiased First-Order Bilevel Optimization

Cited by in corpus (22)

• Learning to Continuously Optimize Wireless Resource in a Dynamic Environment: A Bilevel Optimization Perspective
• Towards Understanding Asynchronous Advantage Actor-critic: Convergence and Linear Speedup
• Bilevel methods for image reconstruction
• An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods
• Beyond backpropagation: bilevel optimization through implicit differentiation and equilibrium propagation
• Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
• Lower Bounds and Accelerated Algorithms for Bilevel Optimization
• Provably Faster Algorithms for Bilevel Optimization
• BiAdam: Fast Adaptive Bilevel Optimization Methods
• Sign-MAML: Efficient Model-Agnostic Meta-Learning by SignSGD
• Randomized Stochastic Variance-Reduced Methods for Multi-Task Stochastic Bilevel Optimization
• Finite-Time Convergence Rates of Nonlinear Two-Time-Scale Stochastic Approximation under Markovian Noise
• Enhanced Bilevel Optimization via Bregman Distance
• Bilevel Optimization for Machine Learning: Algorithm Design and Convergence Analysis
• A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning
• Minimax Problems with Coupled Linear Constraints: Computational Complexity, Duality and Solution Methods
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization
• Finite-Time Complexity of Online Primal-Dual Natural Actor-Critic Algorithm for Constrained Markov Decision Processes
• Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximation
• Analysis of a Target-Based Actor-Critic Algorithm with Linear Function Approximation
• On the Convergence Rate of Off-Policy Policy Optimization Methods with Density-Ratio Correction
• Wasserstein Flow Meets Replicator Dynamics: A Mean-Field Analysis of Representation Learning in Actor-Critic