Overcoming the Curse of Dimensionality in Reinforcement Learning Through Approximate Factorization
Reinforcement Learning (RL) algorithms are known to suffer from the curse of dimensionality, which refers to the fact that large-scale problems often lead to exponentially high sample complexity....
A Non-Asymptotic Theory of Seminorm Lyapunov Stability: From Deterministic to Stochastic Iterative Algorithms
We study the problem of solving fixed-point equations for seminorm-contractive operators and establish foundational results on the non-asymptotic behavior of iterative algorithms in both...
Reinforcement Learning with Imperfect Transition Predictions: A Bellman-Jensen Approach
Traditional reinforcement learning (RL) assumes the agents make decisions based on Markov decision processes (MDPs) with one-step transition models. In many real-world applications, such as energy...
Concentration of Contractive Stochastic Approximation: Additive and Multiplicative Noise
In this paper, we establish maximal concentration bounds for the iterates generated by a stochastic approximation (SA) algorithm under a contractive operator with respect to some arbitrary norm...
Global Convergence of Localized Policy Iteration in Networked Multi-Agent Reinforcement Learning
We study a multi-agent reinforcement learning (MARL) problem where the agents interact over a given network. The goal of the agents is to cooperatively maximize the average of their...
Approximate Global Convergence of Independent Learning in Multi-Agent Systems
Independent learning (IL), despite being a popular approach in practice to achieve scalability in large-scale multi-agent systems, usually lacks global convergence guarantees. In this paper, we...
A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games
We study two-player zero-sum stochastic games, and propose a form of independent learning dynamics called Doubly Smoothed Best-Response dynamics, which integrates a discrete and doubly smoothed...
Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Games
We consider two-player zero-sum stochastic games and propose a two-timescale $Q$-learning algorithm with function approximation that is payoff-based, convergent, rational, and symmetric between...
Target Network and Truncation Overcome The Deadly Triad in $Q$-Learning
$Q$-learning with function approximation is one of the most empirically successful while theoretically mysterious reinforcement learning (RL) algorithms, and was identified in Sutton (1999) as one...
Convergence Rates for Localized Actor-Critic in Networked Markov Potential Games
We introduce a class of networked Markov potential games in which agents are associated with nodes in a network. Each agent has its own local potential function, and the reward of each agent...
Stationary Behavior of Constant Stepsize SGD Type Algorithms: An Asymptotic Characterization
Stochastic approximation (SA) and stochastic gradient descent (SGD) algorithms are work-horses for modern machine learning algorithms. Their constant stepsize variants are preferred in practice...
Nested Vehicle Routing Problem: Optimizing Drone-Truck Surveillance Operations
Unmanned aerial vehicles or drones are becoming increasingly popular due to their low cost and high mobility. In this paper we address the routing and coordination of a drone-truck pairing where...
Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximation
In this paper, we develop a novel variant of off-policy natural actor-critic algorithm with linear function approximation and we establish a sample complexity of $\mathcal{O}(\epsilon^{-3})$,...
Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm
In this paper, we provide finite-sample convergence guarantees for an off-policy variant of the natural actor-critic (NAC) algorithm based on Importance Sampling. In particular, we show that the...
Finite-Sample Analysis of Off-Policy TD-Learning via Generalized Bellman Operators
In temporal difference (TD) learning, off-policy sampling is known to be more practical than on-policy sampling, and by decoupling learning from data collection, it enables data reuse. It is known...
A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants
This paper develops an unified framework to study finite-sample convergence guarantees of a large class of value-based asynchronous reinforcement learning (RL) algorithms. We do this by first...
Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning
Motivated by applications in reinforcement learning (RL), we study a nonlinear stochastic approximation (SA) algorithm under Markovian noise, and establish its finite-sample convergence bounds...
Finite-Sample Analysis of Stochastic Approximation Using Smooth Convex Envelopes
Stochastic Approximation (SA) is a popular approach for solving fixed-point equations where the information is corrupted by noise. In this paper, we consider an SA involving a contraction mapping...