PAC Learning with Improvements

This repository contains the experimental code and datasets accompanying the ICML 2025 (to appear) paper: "PAC Learning with Improvements".

Overview

TL;DR: We show that the learnability of agents that can improve is not characterized by the VC dimension, analyze the sample complexity of learning several fundamental concept classes in this setting and provide an empirical study on real datasets.

Contents of the repository

• data_curation/ – Python notebooks for generating the synthetic data and sourcing the adult dataset. Other datasets are from here.
• analysis_cleaning/ – Scripts for data cleaning and preprocessing, and for basic data analysis and exploration (Section E.1).
• datasets/ – Original and preprocessed datasets (csv files) used in the experiments.
• fstar_classifiers/ – Python notebooks for the singly defined and multi-defined fstar modes (Section E.2).
• improvement/ – A sample notebook for evaluating the improvement-aware classifiers on OULAD dataset (Figures 10c & 10d).
• requirements.txt – A list of some packages or dependencies needed to run the project.

Getting started

Prerequisites

• Python 3.11.5
• Recommended: Use anaconda or miniconda from here.

Basic usage

1. Clone the repository:

   git clone https://github.com/ripl/PLI.git
   cd PLI

2. Install the required packages:

   pip install -r requirements.txt

Citation

If you find this work useful in your research, please cite our paper:

@article{attias2025paclearningimprovements,
	title        = {{PAC Learning with Improvements}},
	author       = {Idan Attias and Avrim Blum and Keziah Naggita and Donya Saless and Dravyansh Sharma and Matthew Walter},
	year         = 2025,
	url          = {https://arxiv.org/abs/2503.03184},
	note         = {ICML 2025 (to appear)}
}

License

This project is licensed under the MIT License. See the LICENSE file for details.

Contact

For questions or collaborations, please contact us here.