2026-09-21T14:08:45Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/129852 2025-10-25 col_2142_5131 col_2142_8888 com_2142_5130 com_2142_8887 com_2142_234

application/pdf en text Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2025-10-20 without embargo terms The student, Yashaswini Murthy, accepted the attached license on 2025-07-09 at 18:14. The student, Yashaswini Murthy, submitted this Dissertation for approval on 2025-07-10 at 18:49. This Dissertation was approved for publication on 2025-07-11 at 15:46. DSpace SAF Submission Ingestion Package generated from Vireo submission #22474 on 2025-10-20 at 16:57:39 Policy-based average-reward and robust Markov decision processes and reinforcement learning Murthy, Yashaswini 2025-07-11 Srikant, Rayadurgam Srikant, Rayadurgam Hajek, Bruce Stolyar, Aleksandr Hu, Bin Reinforcement Learning Markov Decision Processes eng 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. 2025-08 Text https://hdl.handle.net/2142/129852 Copyright 2025 Yashaswini Murthy Electrical & Computer Eng Electrical & Computer Engr University of Illinois Urbana-Champaign Ph.D. Dissertation