Algorithmic Learning Theory

Marcus Hutter received his masters in computer sciences in 1992 at the Technical University in Munich, Germany. After his PhD in theoretical particle physics he developed algorithms in a medical software company for 5 years. For four years he has been working as a researcher at the AI institute IDSIA in Lugano, Switzerland. His current interests are centered around reinforcement learning, algorithmic information theory and statistics, universal induction schemes, adaptive control theory, and related areas.

Editors' Introduction.- Editors' Introduction.- Invited Papers.- Towards General Algorithms for Grammatical Inference.- The Blessing and the Curse of the Multiplicative Updates.- Discovery of Abstract Concepts by a Robot.- Contrast Pattern Mining and Its Application for Building Robust Classifiers.- Optimal Online Prediction in Adversarial Environments.- Regular Contributions.- An Algorithm for Iterative Selection of Blocks of Features.- Bayesian Active Learning Using Arbitrary Binary Valued Queries.- Approximation Stability and Boosting.- A Spectral Approach for Probabilistic Grammatical Inference on Trees.- PageRank Optimization in Polynomial Time by Stochastic Shortest Path Reformulation.- Inferring Social Networks from Outbreaks.- Distribution-Dependent PAC-Bayes Priors.- PAC Learnability of a Concept Class under Non-atomic Measures: A Problem by Vidyasagar.- A PAC-Bayes Bound for Tailored Density Estimation.- Compressed Learning with Regular Concept.- A Lower Bound for Learning Distributions Generated by Probabilistic Automata.- Lower Bounds on Learning Random Structures with Statistical Queries.- Recursive Teaching Dimension, Learning Complexity, and Maximum Classes.- Toward a Classification of Finite Partial-Monitoring Games.- Switching Investments.- Prediction with Expert Advice under Discounted Loss.- A Regularization Approach to Metrical Task Systems.- Solutions to Open Questions for Non-U-Shaped Learning with Memory Limitations.- Learning without Coding.- Learning Figures with the Hausdorff Metric by Fractals.- Inductive Inference of Languages from Samplings.- Optimality Issues of Universal Greedy Agents with Static Priors.- Consistency of Feature Markov Processes.- Algorithms for Adversarial Bandit Problems with Multiple Plays.- Online Multiple KernelLearning: Algorithms and Mistake Bounds.- An Identity for Kernel Ridge Regression.