I really started doing research during my Master’s thesis at ENS Lyon under the supervision of Maurice Nivat in 1989. This was more than 30 years ago so I thought I can take a look back.
Of course I stand behind all my papers but some of them have a special flavor.
This list presents my favorite results, starting from my PhD and ending with my most recent papers.
The selection is purely personal and is based on the pleasure I had to work on them, the fact that they came at a real surprise to me or because I think and hope they can have an impact or be useful to others.
Recursive Equations for Timed Petri nets: this is my first published paper (1991) [REF]. It shows stochastic monotonicity of the throughputs in a free choice net with respect to the service times.
My first attempts to do research combined Petri nets (a formal model of distributed systems with partial synchronizations) and queueing theory (probability models for performance evaluation). This was rather enlightening and further convinced me that fruitful research can be done combining algorithmic and complexity theory on one hand and numerical stochastic techniques on the other.
Separable monotone framework for free choice Petri nets: This is a short chapter (Chap. 8) of my PhD thesis [REF] that I never published elsewhere but I liked very much the simplicity and power of the approach. By changing the state variable in the evolution equations of a free choice net, I show that the monotone separable framework developed by Francois Baccelli can be used to assess stability of free choice nets under general stationary and ergodic inputs.
Optimal allocation sequences for two processes sharing a ressource This research report, published in 1994 [REF], is my first foray into regular sequences and most precisely Sturmian words. The result was later extended by Thierry Bousch and Jean Mairesse to disprove a conjecture by Jeff Lagarias on the joint spectrum of operators.
Shortest paths for energy consumption We proved with Nicolas Navet that the speed profile that minimizes the energy consumption of a processor executing jobs with deadlines can be seen as a shortest path in a polytope in the plane [REF]. More recently this helped us design linear time algorithm to compute it as well as online optimal algorithms [REF1], [REF2].
Blocking a Transition in a Petri net This was a fun paper to write. It constitutes my most sophisticated effort on Petri nets (I mostly stopped working on this subject after this paper). With Stefan Haar and Jean Mairesse we showed that blocking a transition in a free choice net leads to a unique configuration of the tokens. In stochastic terms, we used this to develop a renewal theory for Petri nets [REF].
Retiming revisited With Jean Mairesse we showed that he famous retiming technique introduced by Leiserson and Saxe is not always sufficient to minimize the number of memory cache in synchronous digital circuits: duplication is sometimes needed to get the absolute minimum [REF].
Multimodularity for optimisation This was the subject of several papers and a book, fruits of my collaboration with Eitan Altman and Arie Hordijk on studying the property of Sturmian words and the related stochastic marked processes as optimal input sequences in networks. This work was continued in the PhD of Emmanuel Hyon (my first PhD student).
Perfect simulation with splitting With Ana Busic, Jean-Marc Vincent and others, we showed how to handle perfect simulation of non-monotone Markov chains almost as efficiently as monotone ones using a series of techniques: envelopes, splitting, skipping and rejection [REF].
Mean field for optimisation This was the subject of the thesis of Nicolas Gast. We proved that mean field techniques can be used for optimisation purposes, in particular to solve large Markov Decision Problems [REF].
Average complexity of best response The best response algorithm is known to converge to Nash equilibria in potential games, albeit with exponential complexity in the worst case. With Stephane Durand and Federica Garin, we proved that its average complexity is linear in the number of players and that it is optimal among all local search algorithms [REF].
Distributed algorithms for optimal routing With Panayotis Mertikopoulos and Pierre Coucheney, [] we have been working on finding distributed optimisation algorithms to compute the optimal paths in communication networks under increasingly demanding conditions: local information only, noisy measurements, delayed information, zero-th order gradient estimations.
Reinforcement Learning in Structured MDPs, with several collaborators (Jonatha Anselmi, Victor Boone, Nicolas Gast, Kimang Khun, Louis-Sébastien Rebuffi) we started a long term project on the design and analysis of reinforcement learning algorithms in MDPs by leveraging on the structure of the MDP. First results include a new RL algorithm whose regret and complexity are (sub)linear in the number of arms for rested bandits and regret bounds for learning in birth and death processes that do not depend on the number of states. [REF].
Higher Order Reinforcement Learning. With Victor Boone, we are investigating RL techniques to identify high order optimal policy (such as bias optimal policies or even Blackwell optimal policies) [REF]. We also introduced a second order measure for RL algorithm, the sliding regret, and designed new algorithms whose sliding regret is sublinear while all previous RL algorithms have linear sliding regret.
I hope this list is not over yet…
