Policy-based average-reward and robust Markov decision processes and reinforcement learning

This thesis addresses critical challenges in applying Reinforcement Learning (RL) to complex, real-world control problems by developing and analyzing policy-based algorithms for Markov Decision Processes (MDPs) under average-reward, robust (risk-sensitive), and countable-space settings. Traditional RL methods often fall short due to assumptions of finite state/action spaces, bounded costs, or reliance on discounted reward criteria, which may not align with long-run performance objectives in dynamic systems. The research presented herein makes several key contributions. First, for average-reward MDPs, we establish rigorous finite-time performance bounds for Approximate Policy Iteration (API) and prove global convergence with $O(\log(T))$ regret for Projected Policy Gradient (PPG) methods, notably by proving the smoothness of the average-reward function. We also demonstrate global convergence for Natural Policy Gradient (NPG)/Mirror Descent Methods (MDM) in the tabular average-reward setting. Second, to tackle problems with countably infinite state spaces and unbounded costs, common in queuing systems, we develop an NPG algorithm with state-dependent step sizes derived from novel policy-independent bounds on the relative value function, achieving non-trivial $O(\sqrt{T})$ regret bounds and relaxing learning error assumptions. Third, for robust decision-making under model uncertainty and cost variability, we introduce Modified Policy Iteration (MPI) for risk-sensitive exponential cost average-cost MDPs, proving its finite-time convergence. This is extended to an Approximate MPI (AMPI) framework and an Approximate PI framework, providing the first convergence guarantees for approximate methods in this risk-sensitive, robust setting and deriving a unified stability condition for error propagation across risk-neutral and risk-sensitive regimes. Collectively, this work advances the theoretical understanding and practical applicability of policy-based RL, providing new algorithms, convergence guarantees, and analytical tools for optimizing long-run performance in large-scale, uncertain, and risk-aware environments.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Electrical & Computer Engr

Grantor

University of Illinois Urbana-Champaign

Year dc:date

2025

Author dc:creator

• Murthy, Yashaswini

Contributors dc:contributor

• Srikant, Rayadurgam
• Hajek, Bruce
• Stolyar, Aleksandr
• Hu, Bin

• Reinforcement Learning
• Markov Decision Processes

Statement dc:rights

• Copyright 2025 Yashaswini Murthy

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/129852

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F129852