Prakash Panangaden

2021-12-31

Information and Computation (publié)

Continuous MDP Homomorphisms and Homomorphic Policy Gradient

Sahand Rezaei-Shoshtari

Abstraction has been widely studied as a way to improve the efficiency and generalization of reinforcement learning algorithms. In this pape… (voir plus)r, we study abstraction in the continuous-control setting. We extend the definition of MDP homomorphisms to encompass continuous actions in continuous state spaces. We derive a policy gradient theorem on the abstract MDP, which allows us to leverage approximate symmetries of the environment for policy optimization. Based on this theorem, we propose an actor-critic algorithm that is able to learn the policy and the MDP homomorphism map simultaneously, using the lax bisimulation metric. We demonstrate the effectiveness of our method on benchmark tasks in the DeepMind Control Suite. Our method's ability to utilize MDP homomorphisms for representation learning leads to improved performance when learning from pixel observations.

2021-12-31

Advances in Neural Information Processing Systems 35 (NeurIPS 2022) (publié)

openreview.net

Riemannian Diffusion Models

Avishek Joey Bose

Diffusion models are recent state-of-the-art methods for image generation and likelihood estimation. In this work, we generalize continuous-… (voir plus)time diffusion models to arbitrary Riemannian manifolds and derive a variational framework for likelihood estimation. Computationally, we propose new methods for computing the Riemannian divergence which is needed in the likelihood estimation. Moreover, in generalizing the Euclidean case, we prove that maximizing this variational lower-bound is equivalent to Riemannian score matching. Empirically, we demonstrate the expressive power of Riemannian diffusion models on a wide spectrum of smooth manifolds, such as spheres, tori, hyperboloids, and orthogonal groups. Our proposed method achieves new state-of-the-art likelihoods on all benchmarks.

2021-12-31

Advances in Neural Information Processing Systems 35 (NeurIPS 2022) (publié)

openreview.net

Interpreting Lambda Calculus in Domain-Valued Random Variables

Robert Furber

Radu Mardare

Douglas Scott

2021-12-11

ArXiv (prépublication)

Weighted automata are compact and actively learnable

Artem Kaznatcheev

2021-09-30

Information Processing Letters (publié)

Proceedings 17th International Conference on Quantum Physics and Logic

Benoît Valiron

Shane Mansfield

Pablo Arrighi

This volume contains the proceedings of the 17th International Conference on Quantum Physics and Logic (QPL 2020), which was held June 2-6, … (voir plus)2020. Quantum Physics and Logic is an annual conference that brings together researchers working on mathematical foundations of quantum physics, quantum computing, and related areas, with a focus on structural perspectives and the use of logical tools, ordered algebraic and category-theoretic structures, formal languages, semantical methods, and other computer science techniques applied to the study of physical behavior in general. Work that applies structures and methods inspired by quantum theory to other fields (including computer science) is also welcome.

2021-09-05

Electronic Proceedings in Theoretical Computer Science (publié)

Extracting Weighted Automata for Approximate Minimization in Language Modelling

Clara Lacroce

Guillaume Rabusseau

In this paper we study the approximate minimization problem for language modelling. We assume we are given some language model as a black bo… (voir plus)x. The objective is to obtain a weighted finite automaton (WFA) that fits within a given size constraint and which mimics the behaviour of the original model while minimizing some notion of distance between the black box and the extracted WFA. We provide an algorithm for the approximate minimization of black boxes trained for language modelling of sequential data over a one-letter alphabet. By reformulating the problem in terms of Hankel matrices, we leverage classical results on the approximation of Hankel operators, namely the celebrated Adamyan-Arov-Krein (AAK) theory. This allows us to use the spectral norm to measure the distance between the black box and the WFA. We provide theoretical guarantees to study the potentially infinite-rank Hankel matrix of the black box, without accessing the training data, and we prove that our method returns an asymptotically-optimal approximation.

2021-08-24

Proceedings of the Fifteenth International Conference on Grammatical Inference (publié)

proceedings.mlr.press

Fixed-Points for Quantitative Equational Logics

Radu Mardare

Gordon Plotkin

We develop a fixed-point extension of quantitative equational logic and give semantics in one-bounded complete quantitative algebras. Unlike… (voir plus) previous related work about fixed-points in metric spaces, we are working with the notion of approximate equality rather than exact equality. The result is a novel theory of fixed points which can not only provide solutions to the traditional fixed-point equations but we can also define the rate of convergence to the fixed point. We show that such a theory is the quantitative analogue of a Conway theory and also of an iteration theory; and it reflects the metric coinduction principle. We study the Bellman equation for a Markov decision process as an illustrative example.

2021-07-01

2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (publié)

Universal Semantics for the Stochastic λ-Calculus

Pedro H. Azevedo de Amorim

Dexter Kozen

Radu Mardare

Michael Roberts

We define sound and adequate denotational and operational semantics for the stochastic lambda calculus. These two semantic approaches build … (voir plus)on previous work that used an explicit source of randomness to reason about higher-order probabilistic programs.

2021-07-01

2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (publié)

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… (voir plus)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.

2020-12-31

Advances in Neural Information Processing Systems 34 (NeurIPS 2021) (publié)

openreview.net

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

Pablo Samuel Castro

Tyler Kastner