Seminars
View all Seminars | Download ICal for this eventStochastic Approximation and Reinforcement Learning: Convergence Analysis Beyond Classical Settings
Series: Ph.D. Colloquium
Speaker: Ankur Naskar, Ph.D (Engg.) student, Dept. of CSA, IISc.,
Date/Time: Aug 14 10:00:00
Location: CSA Seminar Hall (Room No. 254, First Floor)
Faculty Advisor: Prof. Gugan C.M Thoppe
Abstract:
In this thesis, we study the design and convergence analysis of stochastic-approximation-based algorithms for Reinforcement Learning (RL). Stochastic approximation provides a common framework for algorithms that learn from noisy observations, including TD(0), Q-learning, and actor-critic methods. Classical convergence analyses of these algorithms, however, often rely on restrictive assumptions. This thesis develops convergence guarantees beyond these classical settings, with particular emphasis on distributed and federated learning, nonlinear driving functions, and risk-sensitive objectives. The thesis is divided into the following key parts:
Parameter-Free Optimal Convergence of Federated RL: Federated learning enables multiple agents to train local models on independently collected data and periodically aggregate them via a central server, thereby reducing communication, energy, and privacy costs. A key advantage is the potential for an $N$-fold speedup in convergence when $N$ agents participate. This is particularly valuable in reinforcement learning, where learning accurate policies requires extensive interaction with the environment: federated reinforcement learning distributes this burden of exploration across multiple agents. It also offers practical advantages in communication, energy consumption, and data privacy. Existing federated RL analyses, however, largely focus on homogeneous environments and IID sampling. These assumptions are restrictive because different agents may experience distinct transition dynamics and reward functions, while RL data are naturally generated along temporally dependent trajectories. The average-reward setting, which directly captures long-term performance in continuing tasks, also remains comparatively underexplored. Moreover, existing optimal guarantees typically require step sizes tuned using unknown problem parameters, limiting their practical applicability.
We address these challenges by developing federated average-reward policy-evaluation algorithms that combine two-timescale stochastic approximation with Polyak??Ruppert averaging. We establish the first optimal convergence guarantees for federated policy evaluation using parameter-free step sizes. Our framework accommodates heterogeneous local environments while retaining the linear-convergence speedup with respect to the number of participating agents. We first establish these results under IID sampling and then extend them to the more realistic setting of Markovian trajectories.
Seminorm Contractive Fixed-Point Iterations: Nonlinear stochastic fixed-point iterations governed by contractive operators arise across many fields. Canonical examples include Temporal-Difference (TD) learning and Q-learning in reinforcement learning; decentralized learning and Nash-equilibrium computation; regularized least squares for overparameterized models; low-rank matrix completion; and the analysis and control of nonlinear dynamical systems, particularly in robotics. Establishing optimal convergence guarantees for these algorithms is therefore of broad interest. In several important applications, however, the underlying operator is contractive only with respect to a seminorm. The lack of monotonicity of such seminorms prevents the direct application of standard Polyak??Ruppert averaging analyses, leaving parameter-free optimal convergence largely unresolved. We overcome this difficulty through a new proof technique that decomposes the nonlinear update into a perturbed linear stochastic-approximation recursion. We control the linear component using seminorm contraction and bound the nonlinear perturbation by coupling the seminorm with a suitable monotone norm and exploiting the quotient-space geometry it induces. This framework yields the first parameter-free optimal convergence guarantees for general nonlinear seminorm-contractive stochastic fixed-point iterations. Our results apply directly to synchronous and asynchronous Q-learning in both single-agent and distributed settings.
Neural Actor??Critic Methods for Average-Reward CMDPs: Many sequential decision-making problems require an agent not only to maximize performance but also to satisfy safety, operational, or resource constraints. Constrained Markov decision processes provide a framework for such problems by optimizing long-run average performance subject to long-term constraints. In large environments, actor??critic methods use an actor to improve the decision-making policy and a neural-network-based critic to evaluate its long-term consequences. The main challenge is that accurately training the neural critic can be prohibitively expensive. Existing methods face a bias??cost trade-off: reducing the critics systematic error requires long trajectories and many optimization steps, preventing the overall actor??critic algorithm from attaining the optimal convergence rate. This difficulty is amplified in average-reward problems because observations are temporally dependent and the rate at which the system approaches its long-run behavior is generally unknown. We overcome this bottleneck using a hierarchical multilevel Monte Carlo (MLMC) critic. MLMC combines inexpensive, low-accuracy estimates with randomly selected corrections at increasingly accurate levels, thereby achieving the low bias of a long computation at much lower expected cost. Our hierarchical construction applies this idea to both trajectory sampling and neural-critic optimization. Embedding the resulting estimator into a primal??dual Natural Actor??Critic algorithm yields $O??(1/sqrt T??)$ rates for both the optimality gap and constraint violation without requiring mixing-time knowledge. These are the first order-optimal guarantees for average-reward constrained RL with general policy parametrizations and neural critics.
Finite-time Convergence of Exponential-Utility RL: Standard reinforcement learning maximizes expected cumulative reward, treating two policies with the same expected return as equally desirable even when one carries a much greater risk of severe losses. This limitation is consequential in safety-critical and high-stakes applications, where rare but unfavorable outcomes cannot be offset by strong average performance alone. Risk-sensitive reinforcement learning addresses this issue by accounting for the distribution of returns rather than only their expectation. Exponential utility is a classical risk-sensitive criterion that adjusts the agents behavior through a risk-sensitivity parameter, allowing it to place greater emphasis on avoiding adverse outcomes. The discounted exponential-utility setting is nevertheless structurally difficult. The direct objective produces a dynamic-programming recursion in which the effective risk-sensitivity parameter changes across stages, preventing a standard time-homogeneous Bellman formulation. Recent work introduced a Bellman-compatible surrogate with a fixed risk parameter and proposed one- and two-timescale model-free algorithms for learning its solution. However, its general convergence guarantees were only asymptotic and therefore did not quantify how many samples are required to achieve a desired accuracy. Establishing finite-time guarantees presents distinct challenges for the two algorithms. The one-timescale method uses additive stochastic updates, whereas its underlying power-law operator contracts under a logarithmic, multiplicative geometry; consequently, standard stochastic fixed-point arguments do not apply. The two-timescale method must instead control how accurately its faster recursion tracks a moving target set by the slower recursion, while also accounting for time-dependent observations. We establish the first general finite-time guarantees for both algorithms under asynchronous Markovian sampling. For the one-timescale method, we derive a local contraction of the relative-error dynamics and combine it with a Moreau-envelope Lyapunov function and Polyak??Ruppert averaging. For the two-timescale method, we jointly control tracking, mixing, and contraction errors. Both algorithms achieve the optimal $O(1/sqrt {T})$ convergence rate with parameter-free step sizes. Numerical experiments further demonstrate that the learned policies become increasingly cautious as the risk-sensitivity parameter grows.
Distributed Stochastic Approximation with Momentum: Distributed stochastic approximation is a fundamental framework for decentralized machine learning and multi-agent reinforcement learning, in which agents alternate between local computation and communication. Momentum-based variants are particularly attractive because of their potential to accelerate convergence. However, existing analyses of distributed momentum methods typically require restrictive assumptions, including doubly stochastic communication matrices, uniformly bounded noise, and unique fixed points. These conditions exclude many practical decentralized systems and stochastic approximation problems. We address these limitations through a unified analytical framework based on generalized row-stochasticity. This framework establishes the asymptotic convergence of distributed variants of several popular momentum schemes while permitting row-stochastic communication matrices, linearly growing noise, and limiting dynamics with multiple equilibria or non-singleton attractors.
Fundamentally, this thesis develops theoretical convergence guarantees for several stochastic approximation and reinforcement learning algorithms. It introduces new analytical and algorithmic tools for settings where restrictive assumptions and standard analyses fail. Across these settings, the thesis emphasizes parameter-free algorithms that retain optimal convergence rates without requiring prior knowledge of the underlying system dynamics.
Microsoft Teams link:
Link