# By categories

• ## Learning theory

March 26, 2019

### Weighted automata and matrix factorisations

We discuss extensions of Fliess' theorem which says that the smallest weighted automaton for a function is exactly the rank of its Hankel matrix. The goal is to extend this theorem to subclasses of weighted automata such as probabilistic automat...

March 26, 2019

### PAC-learning and compression schemes

We state and prove the equivalence between PAC-learnability, finite VC dimension, and the existence of compression schemes. Many thanks to Borja Balle, Pascale Gourdeau, and Pierre Ohlmann, for discussions on compression schemes and for the joint...

October 19, 2018

### Minimising weighted tree automata and context-free grammars

We discuss an extension of Fliess' theorem for minimising weighted tree automata. This post is somehow a follow-up of this one, but it can be read independently. Minimising weighted tree automata We consider tree formal series (here over the ...

April 13, 2018

### Angluin's style learning for weighted automata

We show that weighted automata over the reals can be learned efficiently in Angluin's supervised scenario. This post uses all the notations of the previous post, and the result presented here was proved in this paper. The scenario is Angluinâ€™s...

April 12, 2018

### Fliess' theorem for minimising weighted automata

We state and prove Fliess' theorem, which says that the minimal automaton recognising a given formal series has size the rank of its Hankel matrix. A formal series (here over the reals) is a function $f : \Sigma^* \to \R$. The Hankel matrix o...

April 02, 2018

### The fundamental theorem of statistical learning

We state and prove the fundamental theorem of statistical learning, which says that a class of functions is learnable if and only if it has finite VC dimension. This post uses all the notations of the previous post. Theorem: If $H$ has...

March 15, 2018

### VC dimension, Rademacher complexity, and growth function

We define the VC dimension, the Rademacher complexity, and the growth function of a class of functions. Let $X$ be the set of inputs. The general learning question we consider is the following: we want to learn a target function \(f : X \to \lef...

• ## Games

December 02, 2019

### Populations of Markov decision processes, what we know and an open question

We present the model of populations of Markov decision processes, discuss our recent result on this model, and show an intriguing open question. The adversarial setting The model of populations of Markov decision processes is directly inspired...

August 03, 2018

### Generalized reachability games

This post is about generalized reachability games. The main purpose is to pose an open problem: what is the complexity of solving 2-generalized reachability games? This post is about this paper. This is the first research paper I have worked o...

• ## Parity games

September 01, 2019

### Parity games, the quasipolynomial era

This post is an overview on my recent research related to the quasipolynomial time algorithms for parity games. It can serve as a roadmap for various posts on this blog. Another piece of material for these results is the slides for my invited ...

March 25, 2019

### Strong and weak separating automata

This post discusses the difference between strong and weak separating automata. The goal of this post is to discuss the notion of separating automata, which already appear in many previous posts, see this post and this post for parity games, t...

February 10, 2019

### Mean payoff games and universal graphs

This post discusses using separating automata for constructing algorithms for solving mean payoff games. The goal of this post is to present the main results of this paper, meaning upper and lower bounds on separating automata for mean payoff g...

February 09, 2019

### Separating automata and universal graphs

This post discusses the equivalence between separating automata and universal graphs beyond parity games. The goal of this post is to present again the result of this paper, which is a joint work with Thomas Colcombet, but this time in more gen...

October 12, 2018

### Parity games and universal graphs

This post introduces the notion of universal graphs and their applications to parity games. The goal of this post is to prove the main result of this paper, meaning that separating automata have at least quasipolynomial size. This quasipolynom...

October 11, 2018

### The fundamental theorem of parity games

This post proves a very important theorem about parity games, showing the interplay with (universal) trees. The goal of this post is to prove the following result. This is the key technical point of a recent joint work with Thomas Colcombet pro...

October 10, 2018

### Separation for parity games

This post discusses a framework for reducing parity games to safety games by the construction of an automaton. There are three quasipolynomial time algorithms for parity games, namely the statistics games of Calude, Jain, Khoussainov, Li, and ...

August 10, 2018

### Value iteration for parity games

This post presents a generic value iteration algorithm for parity games parametrised by universal trees. As special cases this extends the small progress measure of Jurdziński and the succinct progress measure of Jurdziński and Lazi&#...

August 03, 2018

### Universal trees

This post introduces the notion of universal trees, and shows upper and lower bounds. The bounds are almost matching, leaving an open problem: what is the exact size of the smallest universal tree? The motivation for studying universal trees ...

• ## Automata

November 10, 2019

### The complexity of solving games with combination of objectives

We investigate the use of separation automata (or equivalently, universal graphs) for combination of objectives. The general idea is to find ways of combining the solutions for each of the objective into one for the combination, as much as possi...

August 08, 2018

### The universality problem for automata with bounded ambiguity

We prove that the universality problem for automata with fixed ambiguity is decidable in polynomial time. Given an automaton $\A$ on alphabet $A$ recognising the language $L(\A)$, the universality problem asks whether \[\forall w \in A^*, w \i...

• ## Weighted automata

April 06, 2019

### A polynomial time algorithm for the equivalence problem of weighted automata over a field

We present an algebraic algorithm solving the equivalence problem for weighted automata over a field (in particular probabilistic automata) in polynomial time. Edits 29/03/2020: Clarified the model to avoid a terminology clash We consider weig...

September 04, 2018

### A robust class of sequences

We introduce a subclass of linear recurrence sequences (LRS). We show that this class is robust by giving several characterisations. The results presented here are mostly due to Corentin Barloy, who took a summer internship in LaBRI, Bordeaux,...

August 15, 2018

### Boundedness for (min,plus)-automata

We prove that the boundedness problem for (min,plus)-automata is decidable. One of the main application of this result is that the star-heigh problem of regular expressions reduces to (a slight extension of) it. The main point is to present a ve...

• ## Reinforcement learning

November 28, 2019

### Part 3, Monte Carlo approaches, temporal differences, and off-policy learning

We consider the setting where the MDP is only known through simulation and show how to adapt the previous algorithms using statistics instead of exact computations. The basic notations are given in the course outline. The first part about dynam...

November 27, 2019

### Part 2, Markov decision processes and dynamic algorithms

We present the model of MDPS, some fundamental properties and the two dynamic algorithms, value iteration and policy iteration. A Markov decision process is given by a set of states $S$, a set of actions $A$, and a transition function \[\Delta...

November 25, 2019

### Monte Carlo Tree Search

We present the Monte Carlo tree search algorithm for finding an optimal strategy in a two-player game. There is an accompanying github repository for implementations of some algorithms solving Tic-Tac-Toe. The setting we consider is two-player...

November 20, 2019

### The upper confidence bound (UCB) analysis for multi-armed bandits

We present a proof that the upper confidence bound yields an (asymptotically) optimal algorithm for regret minimisation of multi-armed bandits. There is an accompanying github repository for experimenting with different algorithms for the multi...

September 26, 2019

### Course outline

We present the outline of a course on reinforcement learning. The reference book and key inspiration for this course and for reinforcement learning in general is the book by Sutton and Barto (it can be downloaded for free at that address). The ...

• ## Program synthesis

November 11, 2019

### DeepCoder, Learning to write programs

This post is a short presentation of the DeepCoder paper, which proposed in 2017 a very interesting line of attack for improving program synthesis using machine learning. The DeepCoder paper can be found here. It is a great source of inspiration ...