Interdisciplinary Institute in Artificial Intelligence

Reinforcement learning algorithms have grown in popularity and achieved tremendous success in recent years. They are now used to solve optimization problems that were thought to be nearly impossible just a few years ago. Yet, despite this empirical success, they consume a great deal of computational resources, and there are very few algorithms with performance guarantees. The performance of a reinforcement learning algorithm can be measured using various metrics: sample efficiency measures how many samples (from a simulator or a real environment) an algorithm needs to find a “good” policy, whereas computational efficiency measures the amount of computation (or memory) required. Finally, regret measures the gap between the sequential rewards obtained by the learning algorithm and the rewards of the optimal policy (which is unknown).

The goal of a reinforcement learning algorithm is to gather information about the unknown system being explored by the learner in order to better understand its dynamical properties and exploit them to optimize its behavior. Whenever the learner has prior offline information about the system, it can leverage this knowledge to learn its optimal behavior more efficiently. This approach is known as structured learning.

This leads us to the research question we aim to address with the FunRL project:

How can we design algorithms with optimal theoretical guarantees that exploit a (known or unknown) structure of the problem to be solved?
 
This question will be explored in three directions.

First, we will address the online control of queueing networks, which raises the important issue of stability and rarely visited states. These are Markov decision processes (MDPs), which are stochastic dynamical systems that can be controlled. The main originality of this research area compared to the others is that these dynamical systems are constrained by the structure of the problem; the challenge lies in efficiently utilizing our knowledge of this structure. Third, we will study parametric learning, where a learner adapts its policy to a problem with a known structure but whose parameters are unknown. This has applications to auto-scaling problems in cloud computing, resource allocation, and sequential decision-making.