A Journey into Algorithmic Learning Theory
Authors: Marc Abeille, Julien Zhou & Corentin Pla.
The Algorithmic Learning Theory (ALT) 2025 conference, held in Milan at the end of February, was a significant event in the field of machine learning and theoretical computer science. This one-track conference brought together hundred researchers and practitioners to discuss the latest advancements in algorithmic learning theory. The format of the conference allows for having a complete overview of all the accepted papers and encourages interactivity while providing networking opportunities.
Criteo had a strong presence at the conference, contributing to the discussions and presenting cutting-edge research that showcased our commitment to innovation and excellence in the field. One of our papers received an Outstanding Paper Award 🎉
Criteo was proud to be a sponsor of the event, further demonstrating our dedication to supporting the advancement of knowledge and collaboration with the industry.
Keynote Highlights
The keynote speeches at ALT 2025 set the tone for the conference, providing valuable insights into the current state and future directions of algorithmic learning.
RL beyond expectations: Planning for utility functions by Claire Vernade
One of the most impactful keynote addresses was delivered by Claire Vernade, from the University of Tübingen, who presented her recent work on risk-averse reinforcement learning. Claire highlighted the challenges and opportunities in this area of research which is not so much explored in reinforcement learning. She discussed how traditional methods often focus on average performance, but in many practical scenarios, it is essential to consider the variability and potential downsides of decisions. This approach is particularly relevant in fields like finance, where managing risk is as important as maximizing returns. Her work aims to develop methods that can achieve a balance between performance and risk, providing more robust and reliable solutions. Her inspiring presentation demonstrated that this field of research is very promising.
Interview with Nicolò Cesa-Bianchi
Another memorable keynote was given by Nicolò Cesa-Bianchi from Polytechnic University of Milan, a renowned researcher in machine learning in general and of online learning in particular. Criteo awarded him a Faculty Award in 2017 for his work. Cesa-Bianchi’s interview session provided a fascinating look into his career and the evolution of the field. He emphasized the importance of collaboration and the interconnectedness of the academic and industrial ecosystems. His insights into the development of machine learning algorithms and the role of interdisciplinary research were particularly inspiring for the attendees.
Criteo Paper Presentations
Criteo’s team presented two papers at ALT 2025, both of which were well-received by the conference attendees.
Both papers focused on the theory of bandits, a sub-field of reinforcement learning. A bandit problem involves a scenario where an agent must choose between multiple options (or “arms” of a slot machine) to maximize its reward, without knowing the reward distribution of each option beforehand. The agent learns to balance exploration (trying new options) and exploitation (choosing the best-known option) to optimize its long-term gains.
Let’s quickly discuss both papers.
When and why randomised exploration works (in linear bandits) (Marc Abeille, David Janz, Ciara Pike-Burke)
Marc Abeille’s paper, which received an Outstanding Paper Award, specifically discussed the gap between optimistic and randomised strategies, showing the later to match the former in the linear bandit setting.
When and why randomised exploration works (in linear bandits)
We provide an approach for the analysis of randomised exploration algorithms like Thompson sampling that does not rely…
arxiv.org
State-of-the-art bandit algorithms mainly build on optimism or structured randomness. The optimistic approach involves maintaining an estimation of the potential rewards of different actions and always trying the most promising one, even if previous attempts were not successful. The structured randomness approach (leveraging Thompson or posterior sampling), on the other hand, involves simulating different possibilities for actions based on observed data and using these simulations to make decisions.
Marc’s paper demonstrated that structured randomness approaches can be as effective as optimistic approaches in linear bandits (a type of bandit problem where the reward for each action is assumed to be a linear function of some known features, representing the different actions or options available to the agent). This was a significant finding in the field and partially answering a question left open for the last 15 years. To get to this result, the authors were forced to adopt a different approach from the classical one (mapping the structured randomness to the optimistic case) and thus to examine how actions influence the dynamics of the learning process, through the evolution of the confidence sets.
Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Bandit (Julien Zhou, Pierre Gaillard, Thibaud Rahier, Julyan Arbel)
Julien Zhou’s paper, co-authored with Thibaud, another Criteo, emphasized the importance of exploiting the underlying structures of the problem at hand (in this case, the reward function) to learn more efficiently.
Logarithmic Regret for Unconstrained Submodular Maximization Stochastic Bandit
We address the online unconstrained submodular maximization problem (Online USM), in a setting with stochastic bandit…
arxiv.org
Specifically, the paper discussed combinatorial bandits with decreasing marginal gains. This means that adding an item to a set increases the set’s value, but the incremental value decreases as the set grows (e.g., a combination of items at a restraurant — entrée, main course, and dessert — as a set menu is typically cheaper than ordering each item separately).
Zhou’s presentation highlighted the importance of exploiting such underlying structures to enhance learning speed and accuracy. This paper demonstrated significant advancements in the field, offering new methods for optimizing decision-making processes in complex environments.
Highlighted Paper Presentations
The team particularly appreciated two papers:
Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem (Avrim Blum, Kavya Ravichandran)
This presentation focused on the problem of ‘improving bandits’, where the performance of each arm improves as it is pulled more frequently. The challenge is to identify the best arm, which has the highest asymptotic performance. The presentation highlighted the concave nature of the performance improvement, meaning that the rate of improvement decreases over time.
Nearly-tight Approximation Guarantees for the Improving Multi-Armed Bandits Problem
We give nearly-tight upper and lower bounds for the improving multi-armed bandits problem. An instance of this problem…
arxiv.org
The team appreciated the possible connection they saw with the problem of user acquisition at Criteo, where the goal is to identify and retain users whose performance improves over time. The paper provided guarantees on the competitive ratio between the optimal algorithm and a randomized algorithm. (The randomized algorithm starts by pulling all arms uniformly and then exploits the best arm identified). Beyond the theoretical interest, the team appreciated the elegance of the demonstration.
A Unified Theory of Supervised Online Learnability (Vinod Raman, Unique Subedi, Ambuj Tewari)
The paper, which also got an Outstanding Paper Award, aims to unify various approaches to online learnability. It introduces a meta-dimension that characterizes the difficulty of learning any given problem online. This meta-dimension is designed to provide a comprehensive framework for understanding the complexity of different learning tasks.
A Unified Theory of Supervised Online Learnability
We study the online learnability of hypothesis classes with respect to arbitrary, but bounded loss functions. No…
openreview.net
The paper discusses the concept of Littlestone dimension for classifiers, which is a measure of how easily a class of functions can be learned. For example, if we are trying to classify images sequentially, the Little Stone dimension indicates how difficult it is to learn the classification function based on the images provided. The higher the Littlestone dimension, the more challenging it is to learn the function accurately.
The paper focuses on the adversarial setting, where an adversary can adapt to the learner’s responses and provide inputs that make learning more difficult. This setting is crucial for understanding the robustness of learning algorithms online in real-world scenarios. This approach brought a new point of view or approach to study those online systems.
The great result of the paper is that it unifies different learning problems that were previously solved individually with their own measures. It creates a meta-dimension that can characterize the difficulty of learning any problem, whether it involves classification, regression, or other types of learning tasks. This unification provides a more elegant and comprehensive understanding of online learnability.
Reflections and Takeaways
Reflecting on the conference, Criteo’s team members shared their experiences and insights gained from ALT 2025:
- Marc Abeille reflected on the research community and emphasized the importance of maintaining a strong presence in theoretical research, in an era dominated by experimental approaches. He noted that the conference highlighted the ongoing relevance and impact of theoretical work in the field. In addition, Marc observed the interest of both parties, academic and industry, to mix and exchange.
- Julien Zhou found the keynote by Claire Vernade particularly inspiring, as it resonated with his own research in reinforcement learning. He appreciated the depth of Vernade’s analysis and the potential applications of her work in various domains.
- Corentin Pla appreciated the exchange of experience of Nicolo and in particular the fact that writing his book was for him a huge source of research ideas, reminding him that the process of writing or explaining deepen one’s understanding of the subject matter.
Overall, the conference provided valuable lessons and new ideas for future research. The team’s participation in ALT 2025 reinforced the importance of interdisciplinary collaboration and the need to stay at the forefront of innovation in machine learning.
ALT 2025 was a significant event for Criteo, showcasing our contributions to the field of algorithmic learning and reinforcing our commitment to excellence in research. The conference provided a platform for sharing knowledge, exploring new ideas, and building relationships within the academic and industrial communities. As we look forward to future conferences, we remain dedicated to advancing the field and driving innovation through our research.
For more information about the ALT 2025 conference, visit the website of the conference. You can also watch the recordings of the presentations on the playlist of the conference 👇
