4 papers
An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction
Tim van Erven, Jack Mayo, Julia Olkhovskaya +1
We present an oracle-efficient, near-optimal algorithm for linear contextual bandits with adversarial losses and stochastic action sets, only requiring a linear optimization oracle…
Generalization Guarantees via Algorithm-dependent Rademacher Complexity
Sarah Sachs, Tim van Erven, Liam Hodgkinson +2
Algorithm- and data-dependent generalization bounds are required to explain the generalization behavior of modern machine learning algorithms. In this context, there exists informa…
The Risks of Recourse in Binary Classification
Hidde Fokkema, Damien Garreau, Tim van Erven
Algorithmic recourse provides explanations that help users overturn an unfavorable decision by a machine learning system. But so far very little attention has been paid to whether…
Towards Characterizing the First-order Query Complexity of Learning (Approximate) Nash Equilibria in Zero-sum Matrix Games
Hédi Hadiji, Sarah Sachs, Tim van Erven +1
In the first-order query model for zero-sum matrix games, players observe the expected pay-offs for all their possible actions under the randomized action played by the…