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, 2019PAC-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, 2018Minimising 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, 2018Angluin'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, 2018Fliess' 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, 2018The 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, 2018VC 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, 2018Generalized 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, 2019Strong 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, 2019Mean 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, 2019Separating 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, 2018Parity 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, 2018The 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, 2018Separation 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, 2018Value 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, 2018Universal 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, 2018The 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, 2018A 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, 2018Boundedness 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, 2019Part 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, 2019Monte 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, 2019The 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, 2019Course 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 ...