More Like this

1. Generalization in portfolio-based algorithm selection

   Balcan, M.-F.; Sandholm, T.; Vitercik, E. (January 2021, Proceedings of the AAAI Conference on Artificial Intelligence)

   null (Ed.)

   Portfolio-based algorithm selection has seen tremendous practical success over the past two decades. This algorithm configuration procedure works by first selecting a portfolio of diverse algorithm parameter settings, and then, on a given problem instance, using an algorithm selector to choose a parameter setting from the portfolio with strong predicted performance. Oftentimes, both the portfolio and the algorithm selector are chosen using a training set of typical problem instances from the application domain at hand. In this paper, we provide the first provable guarantees for portfolio-based algorithm selection. We analyze how large the training set should be to ensure that the resulting algorithm selector's average performance over the training set is close to its future (expected) performance. This involves analyzing three key reasons why these two quantities may diverge: 1) the learning-theoretic complexity of the algorithm selector, 2) the size of the portfolio, and 3) the learning-theoretic complexity of the algorithm's performance as a function of its parameters. We introduce an end-to-end learning-theoretic analysis of the portfolio construction and algorithm selection together. We prove that if the portfolio is large, overfitting is inevitable, even with an extremely simple algorithm selector. With experiments, we illustrate a tradeoff exposed by our theoretical analysis: as we increase the portfolio size, we can hope to include a well-suited parameter setting for every possible problem instance, but it becomes impossible to avoid overfitting. 

   more » « less
2. Intrinsic Motivation in Dynamical Control Systems

   https://doi.org/10.1103/PRXLife.2.033009  

   Tiomkin, Stas; Nemenman, Ilya; Polani, Daniel; Tishby, Naftali (August 2024, PRX Life)

   Biological systems often choose actions without an explicit reward signal, a phenomenon known as intrinsic motivation. The computational principles underlying this behavior remain poorly understood. In this study, we investigate an information-theoretic approach to intrinsic motivation, based on maximizing an agent's empowerment (the mutual information between its past actions and future states). We show that this approach generalizes previous attempts to formalize intrinsic motivation, and we provide a computationally efficient algorithm for computing the necessary quantities. We test our approach on several benchmark control problems, and we explain its success in guiding intrinsically motivated behaviors by relating our information-theoretic control function to fundamental properties of the dynamical system representing the combined agent-environment system. This opens the door for designing practical artificial, intrinsically motivated controllers and for linking animal behaviors to their dynamical properties. Published by the American Physical Society2024 

   more » « less
3. Quasi-Stochastic Approximation: Design Principles With Applications to Extremum Seeking Control

   https://doi.org/10.1109/MCS.2023.3291884  

   Lauand, Caio Kalil; Meyn, Sean (October 2023, IEEE Control Systems)

   From the summary: The goal of this article is two-fold: survey the emerging theory of QSA (quasi-stochastic approximation) and its implication to design, and explain the intimate connection between QSA and ESC (extremum seeking control). The contributions go in two directions: ESC algorithm design can benefit by applying concepts from QSA theory, and the broader research community with interest in gradient-free optimization can benefit from the control theoretic approach inherent to ESC. 

   more » « less
4. Information Theoretic Regret Bounds for Online Nonlinear Control

   Kakade, Sham; Krishnamurthy, Akshay; Lowrey, Kendall; Ohnishi, Motoya; Sun, Wen (January 2020, Advances in neural information processing systems)

   null (Ed.)

   This work studies the problem of sequential control in an unknown, nonlinear dynamical system, where we model the underlying system dynamics as an unknown function in a known Reproducing Kernel Hilbert Space. This framework yields a general setting that permits discrete and continuous control inputs as well as non-smooth, non-differentiable dynamics. Our main result, the Lower Confidence-based Continuous Control (LC3) algorithm, enjoys a near-optimal "root T" regret bound against the optimal controller in episodic settings, where T is the number of episodes. The bound has no explicit dependence on dimension of the system dynamics, which could be infinite, but instead only depends on information theoretic quantities. We empirically show its application to a number of nonlinear control tasks and demonstrate the benefit of exploration for learning model dynamics. 

   more » « less
5. An insertion algorithm for diagram algebras

   Colmenarejo, Laura; Orellana, Rosa; Saliola, Franco; Schilling, Anne; Zabrocki, Mike (January 2020, Séminaire Lotharingien de Combinatoire)

   We generalize the Robinson–Schensted–Knuth algorithm to the insertion of two row arrays of multisets. This generalization leads to an algorithm from parti- tion diagrams to pairs of a standard tableau and a standard multiset tableau of the same shape, which has the remarkable property that it is well-behaved with respect to restricting a representation to a subalgebra. This insertion algorithm matches recent representation-theoretic results of Halverson and Jacobson. 

   more » « less