Seminars

View all Seminars  |  Download ICal for this event

A Trilogy of Finite-Time Guarantees: Stochastic Approximation, Average-Reward Reinforcement Learning, and Reinforcement Learning Beyond Markovianity

Series: Ph.D. Colloquium

Speaker: Avik Kar, Ph.D (Engg.) student, Dept. of C.S.A, IISc.,

Date/Time: Jul 31 11:00:00

Location: CSA Auditorium, (Room No. 104, Ground Floor)

Faculty Advisor: Prof. Shalabh Bhatnagar

Abstract:
In this thesis, we investigate finite-time guarantees for learning algorithms in two fundamental settings: first-order optimization and reinforcement learning (RL). First-order optimization seeks to minimize an objective using gradient information or noisy estimates of it. In RL, one studies sequential decision-making in an unknown environment, where an agent learns through interaction to select actions that optimize a certain reward criterion. Unlike asymptotic guarantees, finite-time bounds quantify the data, computation, or interaction required to attain a given level of performance. They characterize how the performance gap decreases with the number of observations or interactions and how this rate depends on confidence, temporal dependence, dimensionality, and complexity of the problem. Such bounds are useful for assessing practical feasibility and comparing algorithmic designs.

Stochastic approximation provides a common framework for analyzing many algorithms in optimization and RL, including stochastic gradient descent (SGD), policy gradient, temporal difference (TD) learning, and Q-learning. The first part of the trilogy studies stochastic approximation under two settings that fall outside the standard contractive theory. We first consider SGD for smooth objectives that satisfy the Polyak-L{}ojasiewicz (PL) condition, in which the gradient update is generally neither contractive nor non-expansive. In applications such as decentralized optimization, privacy-preserving subsampling, online system identification, stochastic control, and RL, gradient samples may also be generated along a Markov process, producing temporally correlated noise. We analyze SGD for PL{} objectives when the gradient noise contains both Markovian and martingale-difference components and may grow with the function value and gradient norm. We establish the first uniform-in-time high-probability bound for SGD in this setting, with suboptimality decreasing at a $widetilde{O}(1/n)$ rate, up to a logarithmic factor. The prefactor has a quadratic dependence on the mixing time of the underlying Markov chain. We also obtain an $O(1/n)$ rate for the expected suboptimality, with only linear dependence on the mixing time. The analysis combines a Poisson-equation decomposition of the Markovian noise with a probabilistic induction argument that handles the absence of almost-sure bounds on the objective values and noise.

We next study stochastic Krasnosel skiu{i}-Mann iterations driven by an operator, $T$ that is non-expansive with respect to an arbitrary norm, $|cdot|$ on a finite-dimensional space. The objective is to characterize the decay of the fixed-point residual $|x_n-Tx_n|$. The iterate-dependent martingale-difference noise may grow with this residual. Using a noise-averaging transformation and residual bounds for inexact Krasnosel skiu{i}-Mann iterations, we obtain an expected residual rate of $widetilde{mathcal{O}}(n^{-1/6})$. We also derive the first uniform-in-time high-probability rate of $widetilde{mathcal{O}}(n^{-1/6+epsilon})$ for every $epsilon>0$.

The second part of the trilogy concerns infinite-horizon average-reward RL. For finite unichain MDPs, we analyze synchronous relative value iteration (RVI) $Q$-learning through an auxiliary recursion that falls within the nonexpansive stochastic approximation framework developed in the first part. By relating the auxiliary and original residuals and using a bounded hitting-time condition to control the sampling noise, we obtain finite-time expected and high-probability bounds on the RVI fixed-point residual. Since this residual upper-bounds the suboptimality of the greedy policy with respect to the Q iterates, we obtain an expected policy-suboptimality rate of $widetilde{mathcal{O}}(n^{-1/6})$, improving upon the previously known $widetilde{mathcal{O}}(n^{-1/10})$ rate, and the first uniform-in-time high-probability rate of $widetilde{mathcal{O}}(n^{-1/6+epsilon})$ for every $epsilon>0$.

We then study average-reward RL in continuous state and action spaces. A common approach is to discretize the state-action space uniformly and apply a finite-space algorithm. Such methods allocate comparable statistical and computational resources to near-optimal and clearly suboptimal regions, causing their performance to depend on the full ambient dimension. Adaptive discretization avoids this inefficiency by refining only regions that remain potentially optimal.

We develop ZoRL, a model-based algorithm that combines the principle of optimism and adaptive discretization. It designs an optimistic model for the underlying MDP based on observation to compensate for statistical uncertainty and discretization error. The algorithm, based on the optimism principle, when combined with the adaptive discretization rule, zooms in on promising state-action regions. We measure performance through regret, defined as the cumulative performance gap relative to an optimal policy over $N$ interaction steps. ZoRL achieves a regret bound of $O(N^{1-1/d_{mathrm{eff}}})$ up to a logarithmic factor, where $d_{mathrm{eff}}=2d_S+d_z+3$, where $d_z$ is a zooming dimension measuring the size of the near-optimal state-action region. $d_z$ is bounded by the ambient state-action dimension but may be much smaller in benign instances. Thereby, the bound captures the gain arising from adaptivity.

When prior knowledge or computational constraints specify a structured comparator class of policies, even adaptive exploration of the full state-action space may be unnecessarily expensive. We therefore introduce Policy Zooming, which directly explores a prescribed policy class. The algorithm maintains a set of active policies, selectively refines promising portions of the policy space, and plays the policy that maximizes an optimistic estimate of the average reward among the active policies. We proposed model-free and model-based methods to compute optimistic estimates of the average reward. We show that after $N$ interaction, the regret is bounded by $widetilde{mathcal{O}}(N^{1-1/d_{mathrm{eff}}})$, where $d_{mathrm{eff}}=d_z^Phi+2$ for the model-free algorithm and $d_{mathrm{eff}}=2d_S+d_z^Phi+3$ for the model-based counterpart. Here, $d_z^Phi$ measures the joint complexity of the underlying MDP and the near-optimal portion of the policy class $Phi$. We introduce two adaptive algorithms for average-reward RL in continuous spaces: ZoRL adapts to the geometry of near-optimal state-action pairs, whereas Policy Zooming exploits structure within a prescribed policy class.

The final part of our trilogy studies RL in non-Markovian environments. In a non-Markovian decision process, observations and rewards may depend on the entire interaction history. In such problems, optimal decision-making generally requires the full history, which grows over time, making direct policy optimization impractical. Existing methods often either fix an internal state-update function (agent-state dynamics) or learn it via auxiliary predictive objectives, while the control policy is learned to maximize the reward criterion. We, instead, learn the agent-state dynamics and the control policy jointly and directly to maximize the reward criterion. We derive policy-gradient theorems for episodic and infinite-horizon discounted non-Markovian decision processes and obtain unbiased trajectory-based gradient estimators that exploit the recursive agent state update scheme. This leads to the Agent State-Markov Policy Gradient algorithm, for which we establish a finite-time rate of $O(1/sqrt{n})$ for the time-averaged squared gradient norm and almost-sure convergence under decreasing stepsizes. Experiments on partially observed and history-dependent environments show that directly optimizing the internal state for reward can outperform methods based on predictive representation learning.

The three parts of this thesis address finite-time learning under different forms of difficulty, such as optimization in the presence of Markovian noise, solving for fixed points of non-contractive maps with noisy observations, and sequential decision-making for systems with continuous spaces and non-Markovian systems, while drawing tools ranging from classical analysis of average reward MDPs, the principle of optimism, to modern treatments in non-expansive stochastic approximation theory and policy-gradient methods.