Algorithmic Learning Theory

1. Front Matter

   PDF

2. Editors’ Introduction

   1. Editors’ Introduction

      • Jyrki Kivinen, Csaba Szepesvári, Esko Ukkonen, Thomas Zeugmann

      Pages 1-13

3. Invited Papers

   1. Models for Autonomously Motivated Exploration in Reinforcement Learning

      • Peter Auer, Shiau Hong Lim, Chris Watkins

      Pages 14-17

   2. On the Expressive Power of Deep Architectures

      • Yoshua Bengio, Olivier Delalleau

      Pages 18-36

   3. Optimal Estimation

      • Jorma Rissanen

      Pages 37-37

   4. Learning from Label Preferences

      • Eyke Hüllermeier, Johannes Fürnkranz

      Pages 38-38

   5. Information Distance and Its Extensions

      • Ming Li

      Pages 39-39

4. Inductive Inference

   1. Iterative Learning from Positive Data and Counters

      • Timo Kötzing

      Pages 40-54

   2. Robust Learning of Automatic Classes of Languages

      • Sanjay Jain, Eric Martin, Frank Stephan

      Pages 55-69

   3. Learning and Classifying

      • Sanjay Jain, Eric Martin, Frank Stephan

      Pages 70-83

   4. Learning Relational Patterns

      • Michael Geilke, Sandra Zilles

      Pages 84-98

5. Regression

   1. Adaptive and Optimal Online Linear Regression on ℓ1-Balls

      • Sébastien Gerchinovitz, Jia Yuan Yu

      Pages 99-113

   2. Re-adapting the Regularization of Weights for Non-stationary Regression

      • Nina Vaits, Koby Crammer

      Pages 114-128

   3. Competing against the Best Nearest Neighbor Filter in Regression

      • Arnak S. Dalalyan, Joseph Salmon

      Pages 129-143

6. Bandit Problems

   1. Lipschitz Bandits without the Lipschitz Constant

      • Sébastien Bubeck, Gilles Stoltz, Jia Yuan Yu

      Pages 144-158

   2. Deviations of Stochastic Bandit Regret

      • Antoine Salomon, Jean-Yves Audibert

      Pages 159-173

   3. On Upper-Confidence Bound Policies for Switching Bandit Problems

      • Aurélien Garivier, Eric Moulines

      Pages 174-188

   4. Upper-Confidence-Bound Algorithms for Active Learning in Multi-armed Bandits

      • Alexandra Carpentier, Alessandro Lazaric, Mohammad Ghavamzadeh, Rémi Munos, Peter Auer

      Pages 189-203

7. Online Learning

   1. The Perceptron with Dynamic Margin

      • Constantinos Panagiotakopoulos, Petroula Tsampouka

      Pages 204-218

   2. Combining Initial Segments of Lists

      • Manfred K. Warmuth, Wouter M. Koolen, David P. Helmbold

      Pages 219-233

This book constitutes the refereed proceedings of the 22nd International Conference on Algorithmic Learning Theory, ALT 2011, held in Espoo, Finland, in October 2011, co-located with the 14th International Conference on Discovery Science, DS 2011.
The 28 revised full papers presented together with the abstracts of 5 invited talks were carefully reviewed and selected from numerous submissions. The papers are divided into topical sections of papers on inductive inference, regression, bandit problems, online learning, kernel and margin-based methods, intelligent agents and other learning models.

• algorithmic information theory
• game theory
• probability
• reinforcement learning
• universal artificial intelligence
• algorithm analysis and problem complexity

• Department of Computer Science, University of Helsinki, Helsinki, Finland

  Jyrki Kivinen, Esko Ukkonen

• Department of Computing Science, University of Alberta, Edmonton, Canada

  Csaba Szepesvári

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

  Thomas Zeugmann

Policies and ethics