Two-time-scale optimization is a framework introduced in Zeng et al. (2024) that abstracts a range of policy evaluation and policy optimization problems in reinforcement learning (RL). Akin to bi-level optimization under a particular type of stochastic oracle, the two-time-scale optimization framework has an upper level objective whose gradient evaluation depends on the solution of a lower level problem, which is to find the root of a strongly monotone operator. In this work, we propose a new method for solving two-time-scale optimization that achieves significantly faster convergence than the prior arts. The key idea of our approach is to leverage an averaging step to improve the estimates of the operators in both lower and upper levels before using them to update the decision variables. These additional averaging steps eliminate the direct coupling between the main variables, enabling the accelerated performance of our algorithm. We characterize the finite-time convergence rates of the proposed algorithm under various conditions of the underlying objective function, including strong convexity, convexity, Polyak-Lojasiewicz condition, and general non-convexity. These rates significantly improve over the best-known complexity of the standard two-time-scale stochastic approximation algorithm. When applied to RL, we show how the proposed algorithm specializes to novel online sample-based methods that surpass or match the performance of the existing state of the art. Finally, we support our theoretical results with numerical simulations in RL.

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.

Dynamic spectrum access (DSA) has been introduced as a promising technology that allows a secondary system to access the licensed spectrum of the primary system to improve spectrum utilization. In this paper, we introduce Fed-MADRL by incorporating federated learning (FL) and multi-agent deep reinforcement learning (MADRL) to design a collaborative DSA strategy. Our Fed-MADRL scheme employs FL to enable multiple users to collaboratively optimize the system goal without sharing their training data. By keeping all the training data at the user end, FL improves the communication efficiency and strengthens user data privacy. To further reduce the communication overheads, each user only shares quantized information. We provide the convergence analysis to characterize the trade-off between the communication efficiency and the system performance. In particular, we show that the introduced method converges at a rate$\mathcal {O}(1/K^{1/4})$, where$K$is the number of FL iterations. To the best of our knowledge, Fed-MADRL is the first work that utilizes FL in DSA networks under quantized communication. Performance evaluation results show that the introduced Fed-MADRL method outperforms the independent learning method and achieves comparable performance with the centralized MADRL method, which requires much higher communication overheads.

We study the problem of finding the Nash equilibrium in a two-player zero-sum Markov game. Due to its formulation as a minimax optimization program, a natural approach to solve the problem is to perform gradient descent/ascent with respect to each player in an alternating fashion. However, due to the non-convexity/non-concavity of the underlying objective function, theoretical understandings of this method are limited. In our paper, we consider solving an entropy-regularized variant of the Markov game. The regularization introduces structures into the optimization landscape that make the solutions more identifiable and allow the problem to be solved more efficiently. Our main contribution is to show that under proper choices of the regularization parameter, the gradient descent ascent algorithm converges to the Nash equilibrium of the original unregularized problem. We explicitly characterize the finite-time performance of the last iterate of our algorithm, which vastly improves over the existing convergence bound of the gradient descent ascent algorithm without regularization. Finally, we complement the analysis with numerical simulations that illustrate the accelerated convergence of the algorithm.

Many outages of cloud computing services are caused by the natural disasters or common causes such as software failure, hardware failure, cyber attacks, and power outage. As a result, it is critical to develop resilient and robust cyber-physical system (CPS) to support continuity of service for smart and connected communities (S&CC). In spite of considerate research efforts on virtual machine (VM) migration for enhancing failure-resilience of datacenters, one issue still needs to be effectively addressed: how to determine the best destination for VM migration to avoid the influence from a given failure and enable edge nodes to connect to the VMs continuously. In this paper, we aim to handle these important issues to build a resilient and robust edge-cloud (or fog) network system supporting CPS for S&CC. We propose a machine learning based method for VM migration destination determination for the VMs in the predicted failure domains. We also propose a continuous edge-cloud connection method in wireless network component that enables edge nodes to continuously connect with the VMs through intermediate edge nodes when they cannot directly connect to their original VMs due to VM migration. Our experimental results show our proposed system reduces the number of job failures by 1.8 times and reduces the total job completion time by 48% for completed jobs compared to the case without our system.

We develop a mathematical framework for solving multi-task reinforcement learning (MTRL) problems based on a type of policy gradient method. The goal in MTRL is to learn a common policy that operates effectively in different environments; these environments have similar (or overlapping) state spaces, but have different rewards and dynamics. We highlight two fundamental challenges in MTRL that are not present in its single task counterpart, and illustrate them with simple examples. We then develop a decentralized entropyregularized policy gradient method for solving the MTRL problem, and study its finite-time convergence rate. We demonstrate the effectiveness of the proposed method using a series of numerical experiments. These experiments range from small-scale "GridWorld" problems that readily demonstrate the trade-offs involved in multi-task learning to large-scale problems, where common policies are learned to navigate an airborne drone in multiple (simulated) environments.

We study the policy evaluation problem in multi-agent reinforcement learning. In this problem, a group of agents works cooperatively to evaluate the value function for the global discounted accumulative reward problem, which is composed of local rewards observed by the agents. Over a series of time steps, the agents act, get rewarded, update their local estimate of the value function, then communicate with their neighbors. The local update at each agent can be interpreted as a distributed consensus-based variant of the popular temporal difference learning algorithm TD(0). While distributed reinforcement learning algorithms have been presented in the literature, almost nothing is known about their convergence rate. Our main contribution is providing a finite-time analysis for the convergence of the distributed TD(0) algorithm. We do this when the communication network between the agents is time-varying in general. We obtain an explicit upper bound on the rate of convergence of this algorithm as a function of the network topology and the discount factor. Our results mirror what we would expect from using distributed stochastic gradient descent for solving convex optimization problems.