Algorithmic Learning Theory

1. Front Matter

   PDF

2. Editors’ Introduction

   • Peter Auer, Alexander Clark, Thomas Zeugmann, Sandra Zilles

   Pages 1-7

3. Full Invited Papers

   1. Cellular Tree Classifiers

      • Gérard Biau, Luc Devroye

      Pages 8-17

   2. A Survey of Preference-Based Online Learning with Bandit Algorithms

      • Róbert Busa-Fekete, Eyke Hüllermeier

      Pages 18-39

4. Regular Contributions

   1. Inductive Inference

      1. A Map of Update Constraints in Inductive Inference

         • Timo Kötzing, Raphaela Palenta

         Pages 40-54

      2. On the Role of Update Constraints and Text-Types in Iterative Learning

         • Sanjay Jain, Timo Kötzing, Junqi Ma, Frank Stephan

         Pages 55-69

      3. Parallel Learning of Automatic Classes of Languages

         • Sanjay Jain, Efim Kinber

         Pages 70-84

      4. Algorithmic Identification of Probabilities Is Hard

         • Laurent Bienvenu, Benoît Monin, Alexander Shen

         Pages 85-95

   2. Exact Learning from Queries

      1. Learning Boolean Halfspaces with Small Weights from Membership Queries

         • Hasan Abasi, Ali Z. Abdi, Nader H. Bshouty

         Pages 96-110

      2. On Exact Learning Monotone DNF from Membership Queries

         • Hasan Abasi, Nader H. Bshouty, Hanna Mazzawi

         Pages 111-124

      3. Learning Regular Omega Languages

         • Dana Angluin, Dana Fisman

         Pages 125-139

   3. Reinforcement Learning

      1. Selecting Near-Optimal Approximate State Representations in Reinforcement Learning

         • Ronald Ortner, Odalric-Ambrym Maillard, Daniil Ryabko

         Pages 140-154

      2. Policy Gradients for CVaR-Constrained MDPs

         • L. A. Prashanth

         Pages 155-169

      3. Bayesian Reinforcement Learning with Exploration

         • Tor Lattimore, Marcus Hutter

         Pages 170-184

      4. Extreme State Aggregation beyond MDPs

         • Marcus Hutter

         Pages 185-199

   4. Online Learning and Learning with Bandit Information

      1. On Learning the Optimal Waiting Time

         • Tor Lattimore, András György, Csaba Szepesvári

         Pages 200-214

      2. Bandit Online Optimization over the Permutahedron

         • Nir Ailon, Kohei Hatano, Eiji Takimoto

         Pages 215-229

      3. Offline to Online Conversion

         • Marcus Hutter

         Pages 230-244

   5. Statistical Learning Theory

      1. A Chain Rule for the Expected Suprema of Gaussian Processes

         • Andreas Maurer

         Pages 245-259

      2. Generalization Bounds for Time Series Prediction with Non-stationary Processes

         • Vitaly Kuznetsov, Mehryar Mohri

         Pages 260-274

This book constitutes the proceedings of the 25th International Conference on Algorithmic Learning Theory, ALT 2014, held in Bled, Slovenia, in October 2014, and co-located with the 17th International Conference on Discovery Science, DS 2014. The 21 papers presented in this volume were carefully reviewed and selected from 50 submissions. In addition the book contains 4 full papers summarizing the invited talks. The papers are organized in topical sections named: inductive inference; exact learning from queries; reinforcement learning; online learning and learning with bandit information; statistical learning theory; privacy, clustering, MDL, and Kolmogorov complexity.

• Kolmogorov complexity
• algorithmic learning theory
• artificial intelligence
• bandit theory
• computational complexity
• inductive inference
• machine learning theory
• online learning
• query learning
• reinforcemant learning
• semi-supervised learning
• statistical learning theory
• theory and algorithms for application domanins
• theory of computation

• Montanuniversitaet Leoben, Leoben, Austria

  Peter Auer

• Department of Philosophy, King’s College, London, UK

  Alexander Clark

• Division of Computer Science, Hokkaido University, Sapporo, Japan

  Thomas Zeugmann

• Department of Computer Science, University of Regina, Regina, Canada

  Sandra Zilles

Policies and ethics