Questionnements éthiques en recherche opérationnelle
Tutoriel proposé par le groupe de travail « Recherche Opérationnelle et Ethique » (ROET) de l’axe « Veille Scientifique et Actions Transverses » (VSAT) (ROET) du GDR RO
Par: Odile BELLENGUEZ
odile.bellenguez(at)imt-atlantique.fr
IMT Atlantique
Laboratoire des Sciences du Numérique de Nantes
|
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.
|
Reinforcement Learning and Markovian Bandits
Tutoriel proposé par l’axe « Décision, Modélisation, Evaluation, Incertitude » (DMEI) et l’action transverse « Données, Apprentissage Automatique et Optimisation » (DAAO) du GDR RO
Par: Bruno Gaujal
bruno.gaujal(at)inria.fr
Université Grenoble Alpes,
Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble
|
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.
|
Tools for graph partitioning and clustering
Tutoriel proposé par l’axe « Complexité, Approximation et Graphes pour la Decision et l’Optimisation » (CAGDO) du GDR RO
Par: Alantha Newman
alantha.newman(at)grenoble-inp.fr
CNRS, Université Grenoble-Alpes, Grenoble
|
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.
|
Polyhedra hidden behind min-max theorems
Tutoriel proposé par l’axe « Optimisation Mathématique / Optimisation Combinatoire et Programmation linéaire en nombres Entiers » (OM/OCPE) du GDR RO.
Par: Roland Grappe
grappe(at)lipn.fr
Université Sorbonne Paris Nord, LIPN, CNRS UMR 7030, F-93430, Villetaneuse, France
|
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.
|