Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Launch Supplement

University of Alberta

$12,500.00

Advances in Average-Cost Markov Decision Processes and Reinforcement Learning

FY 2024-25

Summary
Our proposed research program aims to advance the theories of Markov decision processes (MDPs) and reinforcement learning (RL). MDPs are versatile mathematical models for decision-making in stochastic environments. Beyond traditional management/engineering applications, they are also pivotal in RL, a core component of modern AI and machine learning. Advanced AI/RL technologies, such as AlphaFold, AlphaGo, and ChatGPT, hold tremendous potential to accelerate scientific discoveries, drive economic growth, and reshape industries and daily life. Developing a deep understanding of MDPs and RL and innovating within these fields is not merely an academic endeavor; it is crucial for addressing real-world challenges and harnessing the full potential of modern AI. In our pursuit to advance the theories of MDPs and RL, we will focus specifically on the important average-cost optimality criteria. These criteria serve as natural performance measures in various engineering applications and in RL tasks with long-term safety requirements. However, analyzing infinite-space average-cost MDPs poses substantial challenges, with most existing results limited to semicontinuous or uniformly ergodic MDPs, restricting their applicability. Even in finite spaces, RL algorithms for average-cost MDPs remain underdeveloped. Our research will extend the theory of general-space average-cost MDPs to encompass a broader class of MDPs, venturing into unexplored territory not bound by commonly required continuity, compactness, or strong ergodicity conditions. We aim to establish new optimality results for these MDPs, including optimality conditions and the validity of dynamic programming relations, which form the foundation for computational methods. We will also investigate convergent iterative algorithms. In the medium to long term, our analysis will expand to cover semi--Markovian and partially observable problems, as well as robust/risk--sensitive criteria. Regarding RL, our focus will be on developing mathematically sound RL algorithms for the average--cost criteria. These algorithms will offer practical solutions for handling large average--cost MDPs and will push the boundaries of RL theory, which has traditionally concentrated on episodic and discounted--cost problems. Additionally, we aim to relax the stringent conditions imposed by current RL theory on the communicating structures of MDPs. Initially, our algorithmic research will focus on finite-space problems before expanding to infinite-space ones. Success in this research will make foundational contributions to the fields of MDPs and RL, benefiting both traditional applications and modern AI systems. In the near term, it will deepen our understanding of average--cost MDPs, allowing for more precise modeling of real--world problems and the design of more reliable RL algorithms. This, in turn, will instill greater confidence in their application to complex automation systems.
Program
Discovery Launch Supplement
Location
Alberta, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
DGECR-2024-00312
Name nom
Yu, Huizhen
Department département
Department of Computing Science
Organization id
9
Institution établissement
University of Alberta
Province en
Alberta
Province fr
Alberta
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2024
Award amount
12500
Program id
DGECR
Program name en
Discovery Launch Supplement
Program name fr
Supplément Tremplin vers la découverte
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
Research subject code
2956
Research subject group en
Applied mathematics
Research subject group fr
Mathématiques appliquées
Research subject en
Optimisation and optimal control theory
Research subject fr
Optimisation et théories de commande optimale
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Advances in Average-Cost Markov Decision Processes and Reinforcement Learning
Keywords
markov decision processes; reinforcement learning; artificial intelligence; machine learning; average-cost optimality criteria; optimality analysis; semi-markovian problems; partially observable problems; stochastic approximation; temporal-difference learning
Application summary
Our proposed research program aims to advance the theories of Markov decision processes (MDPs) and reinforcement learning (RL). MDPs are versatile mathematical models for decision-making in stochastic environments. Beyond traditional management/engineering applications, they are also pivotal in RL, a core component of modern AI and machine learning. Advanced AI/RL technologies, such as AlphaFold, AlphaGo, and ChatGPT, hold tremendous potential to accelerate scientific discoveries, drive economic growth, and reshape industries and daily life. Developing a deep understanding of MDPs and RL and innovating within these fields is not merely an academic endeavor; it is crucial for addressing real-world challenges and harnessing the full potential of modern AI. In our pursuit to advance the theories of MDPs and RL, we will focus specifically on the important average-cost optimality criteria. These criteria serve as natural performance measures in various engineering applications and in RL tasks with long-term safety requirements. However, analyzing infinite-space average-cost MDPs poses substantial challenges, with most existing results limited to semicontinuous or uniformly ergodic MDPs, restricting their applicability. Even in finite spaces, RL algorithms for average-cost MDPs remain underdeveloped. Our research will extend the theory of general-space average-cost MDPs to encompass a broader class of MDPs, venturing into unexplored territory not bound by commonly required continuity, compactness, or strong ergodicity conditions. We aim to establish new optimality results for these MDPs, including optimality conditions and the validity of dynamic programming relations, which form the foundation for computational methods. We will also investigate convergent iterative algorithms. In the medium to long term, our analysis will expand to cover semi--Markovian and partially observable problems, as well as robust/risk--sensitive criteria. Regarding RL, our focus will be on developing mathematically sound RL algorithms for the average--cost criteria. These algorithms will offer practical solutions for handling large average--cost MDPs and will push the boundaries of RL theory, which has traditionally concentrated on episodic and discounted--cost problems. Additionally, we aim to relax the stringent conditions imposed by current RL theory on the communicating structures of MDPs. Initially, our algorithmic research will focus on finite-space problems before expanding to infinite-space ones. Success in this research will make foundational contributions to the fields of MDPs and RL, benefiting both traditional applications and modern AI systems. In the near term, it will deepen our understanding of average--cost MDPs, allowing for more precise modeling of real--world problems and the design of more reliable RL algorithms. This, in turn, will instill greater confidence in their application to complex automation systems.