Prakash Panangaden

Guillaume Rabusseau

We study the approximate minimization problem of weighted finite automata (WFAs): given a WFA, we want to compute its optimal approximation … (see more)when restricted to a given size. We reformulate the problem as a rank-minimization task in the spectral norm, and propose a framework to apply Adamyan-Arov-Krein (AAK) theory to the approximation problem. This approach has already been successfully applied to the case of WFAs and language modelling black boxes over one-letter alphabets \citep{AAK-WFA,AAK-RNN}. Extending the result to multi-letter alphabets requires solving the following two steps. First, we need to reformulate the approximation problem in terms of noncommutative Hankel operators and noncommutative functions, in order to apply results from multivariable operator theory. Secondly, to obtain the optimal approximation we need a version of noncommutative AAK theory that is constructive. In this paper, we successfully tackle the first step, while the second challenge remains open.

2022-06-01

ArXiv (preprint)

Bisimulation metrics and norms for real-weighted automata

Borja Balle

Pascale Gourdeau

2022-01-01

Information and Computation (published)

Extracting Weighted Automata for Approximate Minimization in Language Modelling

Clara Lacroce

Guillaume Rabusseau

2021-08-25

Proceedings of the Fifteenth International Conference on Grammatical Inference (published)

proceedings.mlr.press

Optimal Spectral-Norm Approximate Minimization of Weighted Finite Automata

Borja Balle

Clara Lacroce

Doina Precup

Guillaume Rabusseau

We address the approximate minimization problem for weighted finite automata (WFAs) with weights in …

2021-02-13

ArXiv (preprint)

MICo: Improved representations via sampling-based state similarity for Markov decision processes

Pablo Samuel Castro

Tyler Kastner

Mark Rowland

We present a new behavioural distance over the state space of a Markov decision process, and demonstrate the use of this distance as an effe… (see more)ctive means of shaping the learnt representations of deep reinforcement learning agents. While existing notions of state similarity are typically difficult to learn at scale due to high computational cost and lack of sample-based algorithms, our newly-proposed distance addresses both of these issues. In addition to providing detailed theoretical analyses, we provide empirical evidence that learning this distance alongside the value function yields structured and informative representations, including strong results on the Arcade Learning Environment benchmark.

openreview.net

MICo: Learning improved representations via sampling-based state similarity for Markov decision processes

Pablo Samuel Castro

Tyler Kastner

Mark Rowland

We present a new behavioural distance over the state space of a Markov decision process, and demonstrate the use of this distance as an eﬀ… (see more)ective means of shaping the learnt representations of deep reinforcement learning agents. While existing notions of state similarity are typically diﬃcult to learn at scale due to high computational cost and lack of sample-based algorithms, our newly-proposed distance addresses both of these issues. In addition to providing detailed theoretical analysis

2021-01-01

arXiv.org (preprint)

dblp.uni-trier.de

Bisimulation metrics and norms for real-weighted automata

Borja Balle

Pascale Gourdeau

2020-11-01

Information and Computation (published)

A Distributional Analysis of Sampling-Based Reinforcement Learning Algorithms

Philip. Amortila

Doina Precup

Marc Gendron-Bellemare

We present a distributional approach to theoretical analyses of reinforcement learning algorithms for constant step-sizes. We demonstrate it… (see more)s effectiveness by presenting simple and unified proofs of convergence for a variety of commonly-used methods. We show that value-based methods such as TD(

2020-03-27

ArXiv (preprint)