Programme > Tutoriels

Résumé - L’éthique des algorithmes est de plus en plus évoquée dans l’actualité, sans nécessairement que soit questionné ce qu’un tel concept recouvrerait. Cette présentation s’arrêtera donc d’abord sur différents éléments de compréhension à mobiliser quand on parle d’éthique. Nous verrons ainsi en quoi la recherche opérationnelle ne peut s’affranchir des interrogations et transformations en cours. Dans un second temps, nous reviendrons sur différents travaux amorcés il y a plusieurs décennies pour approcher des questions d’éthique ou de responsabilité, en aide à la décision notamment. Certains mettent ainsi en évidence de potentiels effets secondaires, tout autant que différentes difficultés méthodologiques et pratiques à les éviter. Enfin, nous aborderons ce que l'ampleur actuelle des développements renouvelle ou modifie dans ce questionnement ouvert.

Résumé - In this talk, I will first present the main principles of model based reinforcement learning in Markov Decision Processes.
I will  explain the different frameworks where  learning can be done and  give the definition of the most popular performance measure, namely the regret. I will also present the ideas and techniques supporting the construction of no-regret algorithms for general MDPs, mainly optimism in the face of uncertainty and concentration inequalities for differences of Martingales.
Several learning algorithms (UCRL2 and UCBVI), based on these principles and with near optimal regret, will be discussed.
 
The second part of the talk will present Markovian multi-armed bandits  and the construction of an optimal policy using  Gittins index.
I will then show how to leverage on the optimality of Gittins index policies to design adapted reinforcement learning algorithms
whose regret and time complexity scale (sub)linearly with the number of arms.
 
This talk is based on  a joint work with Nicolas Gast and Kimang Khun.

Résumé -Many methods for classifying and organizing data use some form of partitioning or clustering, and many basic problems in discrete optimization can be modeled as graph partitioning or clustering problems.  In this tutorial, we give an overview of some algorithmic approaches for partitioning and clustering problems, where the techniques are based on tools from mathematical programming and approximation algorithms.  Our focus is on discrete optimization problems in which the objective is to partition a graph into possibly many pieces such as max-k-cut and correlation clustering.

Résumé - The well-known MaxFlow-MinCut theorem asserts that, in a directed graph with a source s, a sink t and (integer) capacities on the arcs, the maximum amount of (integer) flow equals the minimum capacity of an st-cut. This min-max result has the desirable property that it still holds when flow requirements are added on each arc.

In terms of linear systems, the addition of bounds on the arc variables preserves the min-max theorem. This comes from the combination of integrality properties of the associated linear system (called total dual integrality) and of the associated polyhedron (called box-total dual integrality). More precisely, the properties of the linear system yield the min-max theorem, that of the polyhedron allow the addition of bounds.

In this tutorial, we will mainly focus on the polyhedral part of such min-max results. Box-totally dual integral polyhedra were introduced in the 80's, and received a renewed interest since around 2008. At a gentle pace, we will review some of their recent characterizations, which will involve geometrical and matricial considerations. We will discuss consequences and applications to specific polyhedra, and this will be accompanied by exercises and open problems.