Source author record

Raphaël Jungers

Raphaël Jungers appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

11works
12topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

11 published item(s)

preprint2022arXiv

A model-based approach to meta-Reinforcement Learning: Transformers and tree search

Meta-learning is a line of research that develops the ability to leverage past experiences to efficiently solve new learning problems. Meta-Reinforcement Learning (meta-RL) methods demonstrate a capability to learn behaviors that efficiently acquire and exploit information in several meta-RL problems. In this context, the Alchemy benchmark has been proposed by Wang et al. [2021]. Alchemy features a rich structured latent space that is challenging for state-of-the-art model-free RL methods. These methods fail to learn to properly explore then exploit. We develop a model-based algorithm. We train a model whose principal block is a Transformer Encoder to fit the symbolic Alchemy environment dynamics. Then we define an online planner with the learned model using a tree search method. This algorithm significantly outperforms previously applied model-free RL methods on the symbolic Alchemy problem. Our results reveal the relevance of model-based approaches with online planning to perform exploration and exploitation successfully in meta-RL. Moreover, we show the efficiency of the Transformer architecture to learn complex dynamics that arise from latent spaces present in meta-RL problems.

preprint2022arXiv

PAC-learning gains of Turing machines over circuits and neural networks

A caveat to many applications of the current Deep Learning approach is the need for large-scale data. One improvement suggested by Kolmogorov Complexity results is to apply the minimum description length principle with computationally universal models. We study the potential gains in sample efficiency that this approach can bring in principle. We use polynomial-time Turing machines to represent computationally universal models and Boolean circuits to represent Artificial Neural Networks (ANNs) acting on finite-precision digits. Our analysis unravels direct links between our question and Computational Complexity results. We provide lower and upper bounds on the potential gains in sample efficiency between the MDL applied with Turing machines instead of ANNs. Our bounds depend on the bit-size of the input of the Boolean function to be learned. Furthermore, we highlight close relationships between classical open problems in Circuit Complexity and the tightness of these.

preprint2022arXiv

Systems with both constant and time-varying delays: a switched systems approach and application to observer-controller co-design

In this paper, we study the application of switched systems stability criteria to derive delay-dependent conditions for systems affected by both a constant and a time-varying delay. The main novelty of our approach lies on the use of path-complete Lyapunov techniques along with the proposition of a new modified functional to obtain convex analysis conditions while avoiding the need of computing a dwell time for each mode in a switched system representation, as usual in the \textit{switched approach} for time-delay systems. Furthermore, we leverage the developed analysis to obtain LMIs for the closed-loop stabilization of systems with time-varying sensor delays by means of an observer-based compensator. A numerical example illustrates the proposed methods.

preprint2021arXiv

A linear bound on the k-rendezvous time for primitive sets of NZ matrices

A set of nonnegative matrices is called primitive if there exists a product of these matrices that is entrywise positive. Motivated by recent results relating synchronizing automata and primitive sets, we study the length of the shortest product of a primitive set having a column or a row with k positive entries, called its k-rendezvous time (k-RT}), in the case of sets of matrices having no zero rows and no zero columns. We prove that the k-RT is at most linear w.r.t. the matrix size n for small k, while the problem is still open for synchronizing automata. We provide two upper bounds on the k-RT: the second is an improvement of the first one, although the latter can be written in closed form. We then report numerical results comparing our upper bounds on the k-RT with heuristic approximation methods.

preprint2016arXiv

Efficient Method for Computing Lower Bounds on the $p$-radius of Switched Linear Systems

This paper proposes lower bounds on a quantity called $L^p$-norm joint spectral radius, or in short, $p$-radius, of a finite set of matrices. Despite its wide range of applications to, for example, stability analysis of switched linear systems and the equilibrium analysis of switched linear economical models, algorithms for computing the $p$-radius are only available in a very limited number of particular cases. The proposed lower bounds are given as the spectral radius of an average of the given matrices weighted via Kronecker products and do not place any requirements on the set of matrices. We show that the proposed lower bounds theoretically extend and also can practically improve the existing lower bounds. A Markovian extension of the proposed lower bounds is also presented.

preprint2016arXiv

Extremal storage functions and minimal realizations of discrete-time linear switching systems

We study the $\mathcal{L}_p$ induced gain of discrete-time linear switching systems with graph-constrained switching sequences. We first prove that, for stable systems in a minimal realization, for every $p \geq 1$, the $\mathcal{L}_p$-gain is exactly characterized through switching storage functions. These functions are shown to be the $p$th power of a norm. In order to consider general systems, we provide an algorithm for computing minimal realizations. These realizations are \emph{rectangular systems}, with a state dimension that varies according to the mode of the system. We apply our tools to the study on the of $\mathcal{L}_2$-gain. We provide algorithms for its approximation, and provide a converse result for the existence of quadratic switching storage functions. We finally illustrate the results with a physically motivated example.

preprint2016arXiv

The Four Bars Problem

A four-bar linkage is a mechanism consisting of four rigid bars which are joined by their endpoints in a polygonal chain and which can rotate freely at the joints (or vertices). We assume that the linkage lies in the 2-dimensional plane so that one of the bars is held horizontally fixed. In this paper we consider the problem of reconfiguring a four-bar linkage using an operation called a \emph{pop}. Given a polygonal cycle, a pop reflects a vertex across the line defined by its two adjacent vertices along the polygonal chain. Our main result shows that for certain conditions on the lengths of the bars of the four-bar linkage, the neighborhood of any configuration that can be reached by smooth motion can also be reached by pops. The proof relies on the fact that pops are described by a map on the circle with an irrational number of rotation.

preprint2014arXiv

Joint Spectral Radius and Path-Complete Graph Lyapunov Functions

We introduce the framework of path-complete graph Lyapunov functions for approximation of the joint spectral radius. The approach is based on the analysis of the underlying switched system via inequalities imposed among multiple Lyapunov functions associated to a labeled directed graph. Inspired by concepts in automata theory and symbolic dynamics, we define a class of graphs called path-complete graphs, and show that any such graph gives rise to a method for proving stability of the switched system. This enables us to derive several asymptotically tight hierarchies of semidefinite programming relaxations that unify and generalize many existing techniques such as common quadratic, common sum of squares, and maximum/minimum-of-quadratics Lyapunov functions. We compare the quality of approximation obtained by certain classes of path-complete graphs including a family of dual graphs and all path-complete graphs with two nodes on an alphabet of two matrices. We provide approximation guarantees for several families of path-complete graphs, such as the De Bruijn graphs, establishing as a byproduct a constructive converse Lyapunov theorem for maximum/minimum-of-quadratics Lyapunov functions.

preprint2014arXiv

Polytopic uncertainty for linear systems: New and old complexity results

We survey the problem of deciding the stability or stabilizability of uncertain linear systems whose region of uncertainty is a polytope. This natural setting has applications in many fields of applied science, from Control Theory to Systems Engineering to Biology. We focus on the algorithmic decidability of this property when one is given a particular polytope. This setting gives rise to several different algorithmic questions, depending on the nature of time (discrete/continuous), the property asked (stability/stabilizability), or the type of uncertainty (fixed/switching). Several of these questions have been answered in the literature in the last thirty years. We point out the ones that have remained open, and we answer all of them, except one which we raise as an open question. In all the cases, the results are negative in the sense that the questions are NP-hard. As a byproduct, we obtain complexity results for several other matrix problems in Systems and Control.

preprint2013arXiv

Sorting under Partial Information (without the Ellipsoid Algorithm)

We revisit the well-known problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of P. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (J. Comput. System Sci. 51 (3), 390-399, 1995) showed that there exists a polynomial-time algorithm for the problem achieving this bound up to a constant factor. Their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it impractical. We develop efficient algorithms for sorting under partial information. Like Kahn and Kim, our approach relies on graph entropy. However, our algorithms differ in essential ways from theirs. Rather than resorting to convex programming for computing the entropy, we approximate the entropy, or make sure it is computed only once, in a restricted class of graphs, permitting the use of a simpler algorithm. Specifically, we present: - an O(n^2) algorithm performing O(log n log e(P)) comparisons; - an O(n^2.5) algorithm performing at most (1+ epsilon) log e(P) + O_epsilon (n) comparisons; - an O(n^2.5) algorithm performing O(log e(P)) comparisons. All our algorithms can be implemented in such a way that their computational bottleneck is confined in a preprocessing phase, while the sorting phase is completed in O(q) + O(n) time, where q denotes the number of comparisons performed.

preprint2011arXiv

Policy Iteration is well suited to optimize PageRank

The question of knowing whether the policy Iteration algorithm (PI) for solving Markov Decision Processes (MDPs) has exponential or (strongly) polynomial complexity has attracted much attention in the last 50 years. Recently, Fearnley proposed an example on which PI needs an exponential number of iterations to converge. Though, it has been observed that Fearnley's example leaves open the possibility that PI behaves well in many particular cases, such as in problems that involve a fixed discount factor, or that are restricted to deterministic actions. In this paper, we analyze a large class of MDPs and we argue that PI is efficient in that case. The problems in this class are obtained when optimizing the PageRank of a particular node in the Markov chain. They are motivated by several practical applications. We show that adding natural constraints to this PageRank Optimization problem (PRO) makes it equivalent to the problem of optimizing the length of a stochastic path, which is a widely studied family of MDPs. Finally, we conjecture that PI runs in a polynomial number of iterations when applied to PRO. We give numerical arguments as well as the proof of our conjecture in a number of particular cases of practical importance.